cds/container/details/bronson_avltree_base.h

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