cds/container/details/bronson_avltree_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
   4 #define CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
   5
   6 #include <cds/container/details/base.h>
   7 #include <cds/opt/compare.h>
   8 #include <cds/urcu/options.h>
   9 #include <cds/sync/spinlock.h>
  10 #include <cds/sync/injecting_monitor.h>
  11
  12 namespace cds { namespace container {
  13
  14     /// BronsonAVLTree related declarations
  15     namespace bronson_avltree {
  16
  17         template <typename Key, typename T, typename SyncMonitor >
  18         struct node;
  19
  20         //@cond
  21         template <typename Node, typename T, typename SyncMonitor>
  22         struct link_node
  23         {
  24             typedef Node     node_type;
  25             typedef T        mapped_type;
  26             typedef uint32_t version_type;  ///< version type (internal)
  27
  28             enum
  29             {
  30                 shrinking = 1,
  31                 unlinked = 2,
  32                 version_flags = shrinking | unlinked
  33                 // the rest is version counter
  34             };
  35
  36             atomics::atomic< int >          m_nHeight;  ///< Node height
  37             atomics::atomic<version_type>   m_nVersion; ///< Version bits
  38             atomics::atomic<node_type *>    m_pParent;  ///< Parent node
  39             atomics::atomic<node_type *>    m_pLeft;    ///< Left child
  40             atomics::atomic<node_type *>    m_pRight;   ///< Right child
  41             typename SyncMonitor::node_injection m_SyncMonitorInjection;    ///< @ref cds_sync_monitor "synchronization monitor" injected data
  42             atomics::atomic<mapped_type *>  m_pValue;   ///< Value
  43
  44         public:
  45             //@cond
  46             link_node()
  47                 : m_nHeight( 0 )
  48                 , m_nVersion( 0 )
  49                 , m_pParent( nullptr )
  50                 , m_pLeft( nullptr )
  51                 , m_pRight( nullptr )
  52                 , m_pValue( nullptr )
  53             {}
  54
  55             link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
  56                 : m_nHeight( nHeight )
  57                 , m_nVersion( version )
  58                 , m_pParent( pParent )
  59                 , m_pLeft( pLeft )
  60                 , m_pRight( pRight )
  61                 , m_pValue( nullptr )
  62             {}
  63
  64             atomics::atomic<node_type *>& child( int nDirection )
  65             {
  66                 assert( nDirection != 0 );
  67                 return nDirection < 0 ? m_pLeft : m_pRight;
  68             }
  69
  70             void child( node_type * pChild, int nDirection, atomics::memory_order order )
  71             {
  72                 assert( nDirection != 0 );
  73                 if ( nDirection < 0 )
  74                     m_pLeft.store( pChild, order );
  75                 else
  76                     m_pRight.store( pChild, order );
  77             }
  78
  79             version_type version( atomics::memory_order order ) const
  80             {
  81                 return m_nVersion.load( order );
  82             }
  83
  84             void version( version_type ver, atomics::memory_order order )
  85             {
  86                 m_nVersion.store( ver, order );
  87             }
  88
  89             int height( atomics::memory_order order ) const
  90             {
  91                 return m_nHeight.load( order );
  92             }
  93
  94             void height( int h, atomics::memory_order order )
  95             {
  96                 m_nHeight.store( h, order );
  97             }
  98
  99             template <typename BackOff>
 100             void wait_until_shrink_completed( atomics::memory_order order ) const
 101             {
 102                 BackOff bkoff;
 103                 while ( is_shrinking( order ) )
 104                     bkoff();
 105             }
 106
 107             bool is_unlinked( atomics::memory_order order ) const
 108             {
 109                 return m_nVersion.load( order ) == unlinked;
 110             }
 111
 112             bool is_shrinking( atomics::memory_order order ) const
 113             {
 114                 return (m_nVersion.load( order ) & shrinking) != 0;
 115             }
 116
 117             mapped_type * value( atomics::memory_order order ) const
 118             {
 119                 return m_pValue.load( order );
 120             }
 121
 122             bool is_valued( atomics::memory_order order ) const
 123             {
 124                 return value( order ) != nullptr;
 125             }
 126
 127             //@endcond
 128         };
 129         //@endcond
 130
 131         /// BronsonAVLTree internal node
 132         template <typename Key, typename T, typename SyncMonitor >
 133         struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
 134         {
 135             //@cond
 136             typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
 137             //@endcond
 138
 139             typedef Key key_type;       ///< key type
 140             typedef T   mapped_type;    ///< value type
 141             typedef typename base_class::version_type version_type;
 142
 143             key_type const                  m_key;      ///< Key
 144             node *                          m_pNextRemoved; ///< thread-local list of removed node
 145
 146         public:
 147             //@cond
 148             template <typename Q>
 149             node( Q&& key )
 150                 : base_class()
 151                 , m_key( std::forward<Q>( key ) )
 152                 , m_pNextRemoved( nullptr )
 153             {}
 154
 155             template <typename Q>
 156             node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
 157                 : base_class( nHeight, version, pParent, pLeft, pRight )
 158                 , m_key( std::forward<Q>( key ) )
 159                 , m_pNextRemoved( nullptr )
 160             {}
 161             //@endcond
 162         };
 163
 164         /// Base value type for BronsonAVLTreeMap
 165         /**
 166             If value type for \p BronsonAVLTreeMap is based on this struct,
 167             the map will support some additional methods like \p BronsonAVLTreeMap::get().
 168             Moreover, the disposer behaviour is different for ordinal values and
 169             values based on \p %bronson_avltree::value:
 170             - for ordinal value, its disposer is called immediately after removing
 171               the node from the tree. It this case it is not possible to support
 172               map's methods that return raw pointer to the tree's value.
 173             - if the value type is based on \p %bronson_avltree::value,
 174               i.e. \p std::is_base_of( bronson_avltree::value, value_type )::value is \p true,
 175               the disposer is called via full RCU cycle. It means that under
 176               RCU lock the methods returning raw pointer can be implemented.
 177         */
 178         struct value
 179         {
 180             value *     m_pNextRetired;
 181
 182             value()
 183                 : m_pNextRetired(nullptr)
 184             {}
 185         };
 186
 187         /// BronsonAVLTreeMap internal statistics
 188         template <typename Counter = cds::atomicity::event_counter>
 189         struct stat {
 190             typedef Counter   event_counter; ///< Event counter type
 191
 192             event_counter   m_nFindSuccess; ///< Count of success \p find() call
 193             event_counter   m_nFindFailed;  ///< Count of failed \p find() call
 194             event_counter   m_nFindRetry;   ///< Count of retries during \p find()
 195             event_counter   m_nFindWaitShrinking;   ///< Count of waiting until shrinking completed duting \p find() call
 196
 197             event_counter   m_nInsertSuccess;       ///< Count of inserting data node
 198             event_counter   m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
 199             event_counter   m_nInsertRetry;         ///< Count of insert retries via concurrent operations
 200             event_counter   m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
 201             event_counter   m_nUpdateRetry;         ///< Count of update retries via concurrent operations
 202             event_counter   m_nUpdateRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p update() call
 203             event_counter   m_nUpdateSuccess;       ///< Count of updating data node
 204             event_counter   m_nUpdateUnlinked;      ///< Count of updating of unlinked node attempts
 205             event_counter   m_nDisposedNode;        ///< Count of disposed node
 206             event_counter   m_nDisposedValue;       ///< Count of disposed value
 207             event_counter   m_nExtractedValue;      ///< Count of extracted value
 208             event_counter   m_nRemoveRetry;         ///< Count o erase/extract retries
 209             event_counter   m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
 210             event_counter   m_nRemoveRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
 211
 212             event_counter   m_nRightRotation;       ///< Count of single right rotation
 213             event_counter   m_nLeftRotation;        ///< Count of single left rotation
 214             event_counter   m_nLeftRightRotation;   ///< Count of double left-over-right rotation
 215             event_counter   m_nRightLeftRotation;   ///< Count of double right-over-left rotation
 216
 217             //@cond
 218             void onFindSuccess()        { ++m_nFindSuccess      ; }
 219             void onFindFailed()         { ++m_nFindFailed       ; }
 220             void onFindRetry()          { ++m_nFindRetry        ; }
 221             void onFindWaitShrinking()  { ++m_nFindWaitShrinking; }
 222
 223             void onInsertSuccess()          { ++m_nInsertSuccess    ; }
 224             void onRelaxedInsertFailed()    { ++m_nRelaxedInsertFailed; }
 225             void onInsertRetry()            { ++m_nInsertRetry      ; }
 226             void onUpdateWaitShrinking()    { ++m_nUpdateWaitShrinking; }
 227             void onUpdateRetry()            { ++m_nUpdateRetry; }
 228             void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
 229             void onUpdateSuccess()          { ++m_nUpdateSuccess;  }
 230             void onUpdateUnlinked()         { ++m_nUpdateUnlinked; }
 231             void onDisposeNode()            { ++m_nDisposedNode; }
 232             void onDisposeValue()           { ++m_nDisposedValue; }
 233             void onExtractValue()           { ++m_nExtractedValue; }
 234             void onRemoveRetry()            { ++m_nRemoveRetry; }
 235             void onRemoveWaitShrinking()    { ++m_nRemoveWaitShrinking; }
 236
 237             void onRotateRight()            { ++m_nRightRotation; }
 238             void onRotateLeft()             { ++m_nLeftRotation; }
 239             void onRotateRightOverLeft()    { ++m_nRightLeftRotation; }
 240             void onRotateLeftOverRight()    { ++m_nLeftRghtRotation; }
 241             //@endcond
 242         };
 243
 244         /// BronsonAVLTreeMap empty statistics
 245         struct empty_stat {
 246             //@cond
 247             void onFindSuccess()        const {}
 248             void onFindFailed()         const {}
 249             void onFindRetry()          const {}
 250             void onFindWaitShrinking()  const {}
 251
 252             void onInsertSuccess()          const {}
 253             void onRelaxedInsertFailed()    const {}
 254             void onInsertRetry()            const {}
 255             void onUpdateWaitShrinking()    const {}
 256             void onUpdateRetry()            const {}
 257             void onUpdateRootWaitShrinking() const {}
 258             void onUpdateSuccess()          const {}
 259             void onUpdateUnlinked()         const {}
 260             void onDisposeNode()            const {}
 261             void onDisposeValue()           const {}
 262             void onExtractValue()           const {}
 263             void onRemoveRetry()            const {}
 264             void onRemoveWaitShrinking()    const {}
 265             void onRemoveRootWaitShrinking() const {}
 266
 267             void onRotateRight()            const {}
 268             void onRotateLeft()             const {}
 269             void onRotateRightOverLeft()    const {}
 270             void onRotateLeftOverRight()    const {}
 271             //@endcond
 272         };
 273
 274         /// Option to allow relaxed insert into Bronson et al AVL-tree
 275         /**
 276             By default, this opton is disabled and the new node is created under its parent lock.
 277             In this case, it is guaranteed the new node will be attached to its parent.
 278             On the other hand, constructing of the new node can be too complex to make it under the lock,
 279             that can lead to lock contention.
 280
 281             When this option is enabled, the new node is created before locking the parent node.
 282             After that, the parent is locked and checked whether the new node can be attached to the parent.
 283             In this case, false node creating can be performed, but locked section can be significantly small.
 284         */
 285         template <bool Enable>
 286         struct relaxed_insert {
 287             //@cond
 288             template <typename Base> struct pack : public Base
 289             {
 290                 enum { relaxed_insert = Enable };
 291             };
 292             //@endcond
 293         };
 294
 295         /// BronsnAVLTreeMap traits
 296         /**
 297             Note that there are two main specialization of Bronson et al AVL-tree:
 298             - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
 299             - data-oriented - the tree node contains a copy of values: <tt>BronsonAVLTreeMap<GC, Key, T, Traits> </tt> where \p T is not a pointer type.
 300
 301             Depends on tree specialization, different traits member can be used.
 302         */
 303         struct traits
 304         {
 305             /// Key comparison functor
 306             /**
 307                 No default functor is provided. If the option is not specified, the \p less is used.
 308
 309                 See \p cds::opt::compare option description for functor interface.
 310
 311                 You should provide \p compare or \p less functor.
 312             */
 313             typedef opt::none                       compare;
 314
 315             /// Specifies binary predicate used for key compare.
 316             /**
 317                 See \p cds::opt::less option description for predicate interface.
 318
 319                 You should provide \p compare or \p less functor.
 320             */
 321             typedef opt::none                       less;
 322
 323             /// Allocator for internal node
 324             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 325
 326             /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
 327             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 328
 329             /// Disposer (only for pointer-oriented tree specialization)
 330             /**
 331                 The functor used for dispose removed values.
 332                 The user-provided disposer is used only for pointer-oriented tree specialization
 333                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 334                 the disposer will be called to signal that the memory for the value can be safely freed.
 335                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
 336             */
 337             typedef opt::v::delete_disposer<>       disposer;
 338
 339             /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
 340             typedef cds::sync::injecting_monitor<cds::sync::spin>  sync_monitor;
 341
 342             /// Enable relaxed insertion.
 343             /**
 344                 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
 345                 By default, this option is disabled.
 346             */
 347             static bool const relaxed_insert = false;
 348
 349             /// Item counter
 350             /**
 351                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
 352                 To enable it use \p atomicity::item_counter
 353             */
 354             typedef atomicity::empty_item_counter     item_counter;
 355
 356             /// C++ memory ordering model
 357             /**
 358                 List of available memory ordering see \p opt::memory_model
 359             */
 360             typedef opt::v::relaxed_ordering        memory_model;
 361
 362             /// Internal statistics
 363             /**
 364                 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
 365                 To enable it use \p ellen_bintree::stat.
 366             */
 367             typedef empty_stat                      stat;
 368
 369             /// Back-off strategy
 370             typedef cds::backoff::empty             back_off;
 371
 372             /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
 373             /**
 374                 List of available options see \p opt::rcu_check_deadlock
 375             */
 376             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 377         };
 378
 379         /// Metafunction converting option list to BronsonAVLTreeMap traits
 380         /**
 381             Note that there are two main specialization of Bronson et al AVL-tree:
 382             - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
 383             - data-oriented - the tree node contains a copy of values: <tt>BronsonAVLTreeMap<GC, Key, T, Traits> </tt> where \p T is not a pointer type.
 384
 385             Depends on tree specialization, different options can be specified.
 386
 387             \p Options are:
 388             - \p opt::compare - key compare functor. No default functor is provided.
 389                 If the option is not specified, \p %opt::less is used.
 390             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 391             - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
 392             - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
 393                 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
 394             - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
 395                 The user-provided disposer is used only for pointer-oriented tree specialization
 396                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 397                 the disposer will be called to signal that the memory for the value can be safely freed.
 398                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
 399                 Due the nature of GC schema the disposer may be called asynchronously.
 400             - \p opt::sync_monitor -  @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
 401                 default is \p cds::sync::injecting_monitor<cds::sync::spin>
 402             - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
 403                 @ref bronson_avltree::relaxed_insert "relaxed insertion"
 404             - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
 405                 To enable it use \p atomicity::item_counter
 406             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 407                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 408             - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
 409                 To enable statistics use \p \p bronson_avltree::stat
 410             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 411             - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
 412         */
 413         template <typename... Options>
 414         struct make_traits {
 415 #   ifdef CDS_DOXYGEN_INVOKED
 416             typedef implementation_defined type ;   ///< Metafunction result
 417 #   else
 418             typedef typename cds::opt::make_options<
 419                 typename cds::opt::find_type_traits< traits, Options... >::type
 420                 ,Options...
 421             >::type   type;
 422 #   endif
 423         };
 424     } // namespace bronson_avltree
 425
 426     // Forwards
 427     template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
 428     class BronsonAVLTreeMap;
 429
 430 }} // namespace cds::container
 431
 432
 433 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H