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