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