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