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