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