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 duting \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
 184             event_counter   m_nRightRotation;       ///< Count of single right rotation
 185             event_counter   m_nLeftRotation;        ///< Count of single left rotation
 186             event_counter   m_nLeftRightRotation;   ///< Count of double left-over-right rotation
 187             event_counter   m_nRightLeftRotation;   ///< Count of double right-over-left rotation
 188
 189             //@cond
 190             void onFindSuccess()        { ++m_nFindSuccess      ; }
 191             void onFindFailed()         { ++m_nFindFailed       ; }
 192             void onFindRetry()          { ++m_nFindRetry        ; }
 193             void onFindWaitShrinking()  { ++m_nFindWaitShrinking; }
 194
 195             void onInsertSuccess()          { ++m_nInsertSuccess    ; }
 196             void onRelaxedInsertFailed()    { ++m_nRelaxedInsertFailed; }
 197             void onInsertRetry()            { ++m_nInsertRetry      ; }
 198             void onUpdateWaitShrinking()    { ++m_nUpdateWaitShrinking; }
 199             void onUpdateRetry()            { ++m_nUpdateRetry; }
 200             void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
 201             void onUpdateSuccess()          { ++m_nUpdateSuccess;  }
 202             void onUpdateUnlinked()         { ++m_nUpdateUnlinked; }
 203             void onDisposeNode()            { ++m_nDisposedNode; }
 204             void onDisposeValue()           { ++m_nDisposedValue; }
 205             void onExtractValue()           { ++m_nExtractedValue; }
 206
 207             void onRotateRight()            { ++m_nRightRotation; }
 208             void onRotateLeft()             { ++m_nLeftRotation; }
 209             void onRotateRightOverLeft()    { ++m_nRightLeftRotation; }
 210             void onRotateLeftOverRight()    { ++m_nLeftRghtRotation; }
 211             //@endcond
 212         };
 213
 214         /// BronsonAVLTreeMap empty statistics
 215         struct empty_stat {
 216             //@cond
 217             void onFindSuccess()        const {}
 218             void onFindFailed()         const {}
 219             void onFindRetry()          const {}
 220             void onFindWaitShrinking()  const {}
 221
 222             void onInsertSuccess()          const {}
 223             void onRelaxedInsertFailed()    const {}
 224             void onInsertRetry()            const {}
 225             void onUpdateWaitShrinking()    const {}
 226             void onUpdateRetry()            const {}
 227             void onUpdateRootWaitShrinking() const {}
 228             void onUpdateSuccess()          const {}
 229             void onUpdateUnlinked()         const {}
 230             void onDisposeNode()            const {}
 231             void onDisposeValue()           const {}
 232             void onExtractValue()           const {}
 233
 234             void onRotateRight()            const {}
 235             void onRotateLeft()             const {}
 236             void onRotateRightOverLeft()    const {}
 237             void onRotateLeftOverRight()    const {}
 238             //@endcond
 239         };
 240
 241         /// Option to allow relaxed insert into Bronson et al AVL-tree
 242         /**
 243             By default, this opton is disabled and the new node is created under its parent lock.
 244             In this case, it is guaranteed the new node will be attached to its parent.
 245             On the other hand, constructing of the new node can be too complex to make it under the lock,
 246             that can lead to lock contention.
 247
 248             When this option is enabled, the new node is created before locking the parent node.
 249             After that, the parent is locked and checked whether the new node can be attached to the parent.
 250             In this case, false node creating can be performed, but locked section can be significantly small.
 251         */
 252         template <bool Enable>
 253         struct relaxed_insert {
 254             //@cond
 255             template <typename Base> struct pack : public Base
 256             {
 257                 enum { relaxed_insert = Enable };
 258             };
 259             //@endcond
 260         };
 261
 262         /// BronsnAVLTreeMap traits
 263         /**
 264             Note that there are two main specialization of Bronson et al AVL-tree:
 265             - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
 266             - 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.
 267
 268             Depends on tree specialization, different traits member can be used.
 269         */
 270         struct traits
 271         {
 272             /// Key comparison functor
 273             /**
 274                 No default functor is provided. If the option is not specified, the \p less is used.
 275
 276                 See \p cds::opt::compare option description for functor interface.
 277
 278                 You should provide \p compare or \p less functor.
 279             */
 280             typedef opt::none                       compare;
 281
 282             /// Specifies binary predicate used for key compare.
 283             /**
 284                 See \p cds::opt::less option description for predicate interface.
 285
 286                 You should provide \p compare or \p less functor.
 287             */
 288             typedef opt::none                       less;
 289
 290             /// Allocator for internal node
 291             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 292
 293             /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
 294             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 295
 296             /// Disposer (only for pointer-oriented tree specialization)
 297             /**
 298                 The functor used for dispose removed values.
 299                 The user-provided disposer is used only for pointer-oriented tree specialization
 300                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 301                 the disposer will be called to signal that the memory for the value can be safely freed.
 302                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
 303             */
 304             typedef opt::v::delete_disposer<>       disposer;
 305
 306             /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
 307             typedef cds::sync::injecting_monitor<cds::sync::spin>  sync_monitor;
 308
 309             /// Enable relaxed insertion.
 310             /**
 311                 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
 312                 By default, this option is disabled.
 313             */
 314             static bool const relaxed_insert = false;
 315
 316             /// Item counter
 317             /**
 318                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
 319                 To enable it use \p atomicity::item_counter
 320             */
 321             typedef atomicity::empty_item_counter     item_counter;
 322
 323             /// C++ memory ordering model
 324             /**
 325                 List of available memory ordering see \p opt::memory_model
 326             */
 327             typedef opt::v::relaxed_ordering        memory_model;
 328
 329             /// Internal statistics
 330             /**
 331                 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
 332                 To enable it use \p ellen_bintree::stat.
 333             */
 334             typedef empty_stat                      stat;
 335
 336             /// Back-off strategy
 337             typedef cds::backoff::empty             back_off;
 338
 339             /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
 340             /**
 341                 List of available options see \p opt::rcu_check_deadlock
 342             */
 343             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 344         };
 345
 346         /// Metafunction converting option list to BronsonAVLTreeMap traits
 347         /**
 348             Note that there are two main specialization of Bronson et al AVL-tree:
 349             - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
 350             - 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.
 351
 352             Depends on tree specialization, different options can be specified.
 353
 354             \p Options are:
 355             - \p opt::compare - key compare functor. No default functor is provided.
 356                 If the option is not specified, \p %opt::less is used.
 357             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 358             - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
 359             - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
 360                 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
 361             - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
 362                 The user-provided disposer is used only for pointer-oriented tree specialization
 363                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 364                 the disposer will be called to signal that the memory for the value can be safely freed.
 365                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
 366                 Due the nature of GC schema the disposer may be called asynchronously.
 367             - \p opt::sync_monitor -  @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
 368                 default is \p cds::sync::injecting_monitor<cds::sync::spin>
 369             - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
 370                 @ref bronson_avltree::relaxed_insert "relaxed insertion"
 371             - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
 372                 To enable it use \p atomicity::item_counter
 373             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 374                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 375             - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
 376                 To enable statistics use \p \p bronson_avltree::stat
 377             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 378             - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
 379         */
 380         template <typename... Options>
 381         struct make_traits {
 382 #   ifdef CDS_DOXYGEN_INVOKED
 383             typedef implementation_defined type ;   ///< Metafunction result
 384 #   else
 385             typedef typename cds::opt::make_options<
 386                 typename cds::opt::find_type_traits< traits, Options... >::type
 387                 ,Options...
 388             >::type   type;
 389 #   endif
 390         };
 391     } // namespace bronson_avltree
 392
 393     // Forwards
 394     template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
 395     class BronsonAVLTreeMap;
 396
 397 }} // namespace cds::container
 398
 399
 400 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H