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