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_nRemoveSuccess;       ///< Count of successfully \p erase() call
 199             event_counter   m_nRemoveFailed;        ///< Count of failed \p erase() call
 200             event_counter   m_nRemoveRetry;         ///< Count o erase/extract retries
 201             event_counter   m_nExtractSuccess;      ///< Count of successfully \p extract() call
 202             event_counter   m_nExtractFailed;       ///< Count of failed \p extract() call
 203             event_counter   m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
 204             event_counter   m_nRemoveRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
 205             event_counter   m_nMakeRoutingNode;     ///< How many nodes were converted to routing (valueless) nodes
 206
 207             event_counter   m_nRightRotation;       ///< Count of single right rotation
 208             event_counter   m_nLeftRotation;        ///< Count of single left rotation
 209             event_counter   m_nLeftRightRotation;   ///< Count of double left-over-right rotation
 210             event_counter   m_nRightLeftRotation;   ///< Count of double right-over-left rotation
 211
 212             event_counter   m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
 213             event_counter   m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
 214             event_counter   m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
 215
 216             event_counter   m_nRotateAfterLeftRotation;  ///< Count of rotation required after signle left rotation
 217             event_counter   m_nRemoveAfterLeftRotation;  ///< Count of removal required after single left rotation
 218             event_counter   m_nDamageAfterLeftRotation;  ///< Count of damaged node after single left rotation
 219
 220             event_counter   m_nRotateAfterRLRotation;    ///< Count of rotation required after right-over-left rotation
 221             event_counter   m_nRemoveAfterRLRotation;    ///< Count of removal required after right-over-left rotation
 222             event_counter   m_nRotateAfterLRRotation;    ///< Count of rotation required after left-over-right rotation
 223             event_counter   m_nRemoveAfterLRRotation;    ///< Count of removal required after left-over-right rotation
 224
 225             event_counter   m_nInsertRebalanceReq;  ///< Count of rebalance required after inserting
 226             event_counter   m_nRemoveRebalanceReq;  ///< Count of rebalance required after removing
 227
 228             //@cond
 229             void onFindSuccess()        { ++m_nFindSuccess      ; }
 230             void onFindFailed()         { ++m_nFindFailed       ; }
 231             void onFindRetry()          { ++m_nFindRetry        ; }
 232             void onFindWaitShrinking()  { ++m_nFindWaitShrinking; }
 233
 234             void onInsertSuccess()          { ++m_nInsertSuccess; }
 235             void onInsertFailed()           { ++m_nInsertFailed; }
 236             void onRelaxedInsertFailed()    { ++m_nRelaxedInsertFailed; }
 237             void onInsertRetry()            { ++m_nInsertRetry      ; }
 238             void onUpdateWaitShrinking()    { ++m_nUpdateWaitShrinking; }
 239             void onUpdateRetry()            { ++m_nUpdateRetry; }
 240             void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
 241             void onUpdateSuccess()          { ++m_nUpdateSuccess;  }
 242             void onUpdateUnlinked()         { ++m_nUpdateUnlinked; }
 243             void onDisposeNode()            { ++m_nDisposedNode; }
 244             void onDisposeValue()           { ++m_nDisposedValue; }
 245             void onExtractValue()           { ++m_nExtractedValue; }
 246             void onRemove(bool bSuccess)
 247             {
 248                 if ( bSuccess )
 249                     ++m_nRemoveSuccess;
 250                 else
 251                     ++m_nRemoveFailed;
 252             }
 253             void onExtract( bool bSuccess )
 254             {
 255                 if ( bSuccess )
 256                     ++m_nExtractSuccess;
 257                 else
 258                     ++m_nExtractFailed;
 259             }
 260             void onRemoveRetry()            { ++m_nRemoveRetry; }
 261             void onRemoveWaitShrinking()    { ++m_nRemoveWaitShrinking; }
 262             void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
 263             void onMakeRoutingNode()        { ++m_nMakeRoutingNode; }
 264
 265             void onRotateRight()            { ++m_nRightRotation; }
 266             void onRotateLeft()             { ++m_nLeftRotation; }
 267             void onRotateRightOverLeft()    { ++m_nRightLeftRotation; }
 268             void onRotateLeftOverRight()    { ++m_nLeftRightRotation; }
 269
 270             void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
 271             void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
 272             void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
 273
 274             void onRotateAfterLeftRotation()  { ++m_nRotateAfterLeftRotation; }
 275             void onRemoveAfterLeftRotation()  { ++m_nRemoveAfterLeftRotation; }
 276             void onDamageAfterLeftRotation()  { ++m_nDamageAfterLeftRotation; }
 277
 278             void onRotateAfterRLRotation()    { ++m_nRotateAfterRLRotation; }
 279             void onRemoveAfterRLRotation()    { ++m_nRemoveAfterRLRotation; }
 280             void onRotateAfterLRRotation()    { ++m_nRotateAfterLRRotation; }
 281             void onRemoveAfterLRRotation()    { ++m_nRemoveAfterLRRotation; }
 282
 283             void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
 284             void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
 285             //@endcond
 286         };
 287
 288         /// BronsonAVLTreeMap empty statistics
 289         struct empty_stat {
 290             //@cond
 291             void onFindSuccess()        const {}
 292             void onFindFailed()         const {}
 293             void onFindRetry()          const {}
 294             void onFindWaitShrinking()  const {}
 295
 296             void onInsertSuccess()          const {}
 297             void onInsertFailed()           const {}
 298             void onRelaxedInsertFailed()    const {}
 299             void onInsertRetry()            const {}
 300             void onUpdateWaitShrinking()    const {}
 301             void onUpdateRetry()            const {}
 302             void onUpdateRootWaitShrinking() const {}
 303             void onUpdateSuccess()          const {}
 304             void onUpdateUnlinked()         const {}
 305             void onDisposeNode()            const {}
 306             void onDisposeValue()           const {}
 307             void onExtractValue()           const {}
 308             void onRemove(bool /*bSuccess*/) const {}
 309             void onExtract(bool /*bSuccess*/) const {}
 310             void onRemoveRetry()            const {}
 311             void onRemoveWaitShrinking()    const {}
 312             void onRemoveRootWaitShrinking() const {}
 313             void onMakeRoutingNode()        const {}
 314
 315             void onRotateRight()            const {}
 316             void onRotateLeft()             const {}
 317             void onRotateRightOverLeft()    const {}
 318             void onRotateLeftOverRight()    const {}
 319
 320             void onRotateAfterRightRotation() const {}
 321             void onRemoveAfterRightRotation() const {}
 322             void onDamageAfterRightRotation() const {}
 323
 324             void onRotateAfterLeftRotation()  const {}
 325             void onRemoveAfterLeftRotation()  const {}
 326             void onDamageAfterLeftRotation()  const {}
 327
 328             void onRotateAfterRLRotation()    const {}
 329             void onRemoveAfterRLRotation()    const {}
 330             void onRotateAfterLRRotation()    const {}
 331             void onRemoveAfterLRRotation()    const {}
 332
 333             void onInsertRebalanceRequired() const {}
 334             void onRemoveRebalanceRequired() const {}
 335             //@endcond
 336         };
 337
 338         /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
 339         /**
 340             By default, this option is disabled and the new node is created under its parent lock.
 341             In this case, it is guaranteed the new node will be attached to its parent.
 342             On the other hand, constructing of the new node can be too complex to make it under the lock,
 343             that can lead to lock contention.
 344
 345             When this option is enabled, the new node is created before locking the parent node.
 346             After that, the parent is locked and checked whether the new node may be attached to the parent.
 347             In this case, false node creating can be performed, but locked section can be significantly small.
 348         */
 349         template <bool Enable>
 350         struct relaxed_insert {
 351             //@cond
 352             template <typename Base> struct pack : public Base
 353             {
 354                 enum { relaxed_insert = Enable };
 355             };
 356             //@endcond
 357         };
 358
 359         /// \p BronsonAVLTreeMap traits
 360         /**
 361             Note that there are two main specialization of Bronson et al AVL-tree:
 362             - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
 363             - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
 364
 365             Depends on tree specialization, different traits member can be used.
 366         */
 367         struct traits
 368         {
 369             /// Key comparison functor
 370             /**
 371                 No default functor is provided. If the option is not specified, the \p less is used.
 372
 373                 See \p cds::opt::compare option description for functor interface.
 374
 375                 You should provide \p compare or \p less functor.
 376             */
 377             typedef opt::none                       compare;
 378
 379             /// Specifies binary predicate used for key compare.
 380             /**
 381                 See \p cds::opt::less option description for predicate interface.
 382
 383                 You should provide \p compare or \p less functor.
 384             */
 385             typedef opt::none                       less;
 386
 387             /// Allocator for internal node
 388             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 389
 390             /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
 391             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 392
 393             /// Disposer (only for pointer-oriented tree specialization)
 394             /**
 395                 The functor used for dispose removed values.
 396                 The user-provided disposer is used only for pointer-oriented tree specialization
 397                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
 398                 the disposer will be called to signal that the memory for the value can be safely freed.
 399                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
 400             */
 401             typedef opt::v::delete_disposer<>       disposer;
 402
 403             /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
 404             typedef cds::sync::injecting_monitor<cds::sync::spin>  sync_monitor;
 405
 406             /// Enable relaxed insertion.
 407             /**
 408                 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
 409                 By default, this option is disabled.
 410             */
 411             static bool const relaxed_insert = false;
 412
 413             /// Item counter
 414             /**
 415                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
 416                 To enable it use \p atomicity::item_counter
 417             */
 418             typedef atomicity::empty_item_counter     item_counter;
 419
 420             /// C++ memory ordering model
 421             /**
 422                 List of available memory ordering see \p opt::memory_model
 423             */
 424             typedef opt::v::relaxed_ordering        memory_model;
 425
 426             /// Internal statistics
 427             /**
 428                 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
 429                 To enable it use \p ellen_bintree::stat.
 430             */
 431             typedef empty_stat                      stat;
 432
 433             /// Back-off strategy
 434             typedef cds::backoff::empty             back_off;
 435
 436             /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
 437             /**
 438                 List of available options see \p opt::rcu_check_deadlock
 439             */
 440             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 441         };
 442
 443         /// Metafunction converting option list to BronsonAVLTreeMap traits
 444         /**
 445             Note that there are two main specialization of Bronson et al AVL-tree:
 446             - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
 447             - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
 448
 449             Depends on tree specialization, different options can be specified.
 450
 451             \p Options are:
 452             - \p opt::compare - key compare functor. No default functor is provided.
 453                 If the option is not specified, \p %opt::less is used.
 454             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 455             - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
 456             - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
 457                 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
 458             - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
 459                 The user-provided disposer is used only for pointer-oriented tree specialization
 460                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 461                 the disposer will be called to signal that the memory for the value can be safely freed.
 462                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
 463                 Due the nature of GC schema the disposer may be called asynchronously.
 464             - \p opt::sync_monitor -  @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
 465                 default is \p cds::sync::injecting_monitor<cds::sync::spin>
 466             - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
 467                 @ref bronson_avltree::relaxed_insert "relaxed insertion"
 468             - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
 469                 To enable it use \p atomicity::item_counter
 470             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 471                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 472             - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
 473                 To enable statistics use \p \p bronson_avltree::stat
 474             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 475             - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
 476         */
 477         template <typename... Options>
 478         struct make_traits {
 479 #   ifdef CDS_DOXYGEN_INVOKED
 480             typedef implementation_defined type ;   ///< Metafunction result
 481 #   else
 482             typedef typename cds::opt::make_options<
 483                 typename cds::opt::find_type_traits< traits, Options... >::type
 484                 ,Options...
 485             >::type   type;
 486 #   endif
 487         };
 488     } // namespace bronson_avltree
 489
 490     // Forwards
 491     template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
 492     class BronsonAVLTreeMap;
 493
 494 }} // namespace cds::container
 495
 496 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H