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             //@cond
 136             typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
 137             //@endcond
 138
 139             typedef Key key_type;       ///< key type
 140             typedef T   mapped_type;    ///< value type
 141             typedef typename base_class::version_type version_type;
 142
 143             key_type const                  m_key;      ///< Key
 144             node *                          m_pNextRemoved; ///< thread-local list of removed node
 145
 146         public:
 147             //@cond
 148             template <typename Q>
 149             node( Q&& key )
 150                 : base_class()
 151                 , m_key( std::forward<Q>( key ) )
 152                 , m_pNextRemoved( nullptr )
 153             {}
 154
 155             template <typename Q>
 156             node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
 157                 : base_class( nHeight, version, pParent, pLeft, pRight )
 158                 , m_key( std::forward<Q>( key ) )
 159                 , m_pNextRemoved( nullptr )
 160             {}
 161             //@endcond
 162         };
 163
 164         /// Base value type for BronsonAVLTreeMap
 165         /**
 166             If value type for \p BronsonAVLTreeMap is based on this struct,
 167             the map will support some additional methods like \p BronsonAVLTreeMap::get().
 168             Moreover, the disposer behaviour is different for ordinal values and
 169             values based on \p %bronson_avltree::value:
 170             - for ordinal value, its disposer is called immediately after removing
 171               the node from the tree. It this case it is not possible to support
 172               map's methods that return raw pointer to the tree's value.
 173             - if the value type is based on \p %bronson_avltree::value,
 174               i.e. <tt>std::is_base_of( bronson_avltree::value, value_type )::value</tt> is \p true,
 175               the disposer is called via full RCU cycle. It means that under
 176               RCU lock the methods returning raw pointer can be implemented.
 177         */
 178         struct value
 179         {
 180             //@cond
 181             value *     m_pNextRetired;
 182
 183             value()
 184                 : m_pNextRetired(nullptr)
 185             {}
 186             //@endcond
 187         };
 188
 189         /// BronsonAVLTreeMap internal statistics
 190         template <typename Counter = cds::atomicity::event_counter>
 191         struct stat {
 192             typedef Counter   event_counter; ///< Event counter type
 193
 194             event_counter   m_nFindSuccess; ///< Count of success \p find() call
 195             event_counter   m_nFindFailed;  ///< Count of failed \p find() call
 196             event_counter   m_nFindRetry;   ///< Count of retries during \p find()
 197             event_counter   m_nFindWaitShrinking;   ///< Count of waiting until shrinking completed duting \p find() call
 198
 199             event_counter   m_nInsertSuccess;       ///< Count of inserting data node
 200             event_counter   m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
 201             event_counter   m_nInsertRetry;         ///< Count of insert retries via concurrent operations
 202             event_counter   m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
 203             event_counter   m_nUpdateRetry;         ///< Count of update retries via concurrent operations
 204             event_counter   m_nUpdateRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p update() call
 205             event_counter   m_nUpdateSuccess;       ///< Count of updating data node
 206             event_counter   m_nUpdateUnlinked;      ///< Count of updating of unlinked node attempts
 207             event_counter   m_nDisposedNode;        ///< Count of disposed node
 208             event_counter   m_nDisposedValue;       ///< Count of disposed value
 209             event_counter   m_nExtractedValue;      ///< Count of extracted value
 210             event_counter   m_nRemoveRetry;         ///< Count o erase/extract retries
 211             event_counter   m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
 212             event_counter   m_nRemoveRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
 213
 214             event_counter   m_nRightRotation;       ///< Count of single right rotation
 215             event_counter   m_nLeftRotation;        ///< Count of single left rotation
 216             event_counter   m_nLeftRightRotation;   ///< Count of double left-over-right rotation
 217             event_counter   m_nRightLeftRotation;   ///< Count of double right-over-left rotation
 218
 219             //@cond
 220             void onFindSuccess()        { ++m_nFindSuccess      ; }
 221             void onFindFailed()         { ++m_nFindFailed       ; }
 222             void onFindRetry()          { ++m_nFindRetry        ; }
 223             void onFindWaitShrinking()  { ++m_nFindWaitShrinking; }
 224
 225             void onInsertSuccess()          { ++m_nInsertSuccess    ; }
 226             void onRelaxedInsertFailed()    { ++m_nRelaxedInsertFailed; }
 227             void onInsertRetry()            { ++m_nInsertRetry      ; }
 228             void onUpdateWaitShrinking()    { ++m_nUpdateWaitShrinking; }
 229             void onUpdateRetry()            { ++m_nUpdateRetry; }
 230             void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
 231             void onUpdateSuccess()          { ++m_nUpdateSuccess;  }
 232             void onUpdateUnlinked()         { ++m_nUpdateUnlinked; }
 233             void onDisposeNode()            { ++m_nDisposedNode; }
 234             void onDisposeValue()           { ++m_nDisposedValue; }
 235             void onExtractValue()           { ++m_nExtractedValue; }
 236             void onRemoveRetry()            { ++m_nRemoveRetry; }
 237             void onRemoveWaitShrinking()    { ++m_nRemoveWaitShrinking; }
 238
 239             void onRotateRight()            { ++m_nRightRotation; }
 240             void onRotateLeft()             { ++m_nLeftRotation; }
 241             void onRotateRightOverLeft()    { ++m_nRightLeftRotation; }
 242             void onRotateLeftOverRight()    { ++m_nLeftRghtRotation; }
 243             //@endcond
 244         };
 245
 246         /// BronsonAVLTreeMap empty statistics
 247         struct empty_stat {
 248             //@cond
 249             void onFindSuccess()        const {}
 250             void onFindFailed()         const {}
 251             void onFindRetry()          const {}
 252             void onFindWaitShrinking()  const {}
 253
 254             void onInsertSuccess()          const {}
 255             void onRelaxedInsertFailed()    const {}
 256             void onInsertRetry()            const {}
 257             void onUpdateWaitShrinking()    const {}
 258             void onUpdateRetry()            const {}
 259             void onUpdateRootWaitShrinking() const {}
 260             void onUpdateSuccess()          const {}
 261             void onUpdateUnlinked()         const {}
 262             void onDisposeNode()            const {}
 263             void onDisposeValue()           const {}
 264             void onExtractValue()           const {}
 265             void onRemoveRetry()            const {}
 266             void onRemoveWaitShrinking()    const {}
 267             void onRemoveRootWaitShrinking() const {}
 268
 269             void onRotateRight()            const {}
 270             void onRotateLeft()             const {}
 271             void onRotateRightOverLeft()    const {}
 272             void onRotateLeftOverRight()    const {}
 273             //@endcond
 274         };
 275
 276         /// Option to allow relaxed insert into Bronson et al AVL-tree
 277         /**
 278             By default, this opton is disabled and the new node is created under its parent lock.
 279             In this case, it is guaranteed the new node will be attached to its parent.
 280             On the other hand, constructing of the new node can be too complex to make it under the lock,
 281             that can lead to lock contention.
 282
 283             When this option is enabled, the new node is created before locking the parent node.
 284             After that, the parent is locked and checked whether the new node may be attached to the parent.
 285             In this case, false node creating can be performed, but locked section can be significantly small.
 286         */
 287         template <bool Enable>
 288         struct relaxed_insert {
 289             //@cond
 290             template <typename Base> struct pack : public Base
 291             {
 292                 enum { relaxed_insert = Enable };
 293             };
 294             //@endcond
 295         };
 296
 297         /// BronsnAVLTreeMap traits
 298         /**
 299             Note that there are two main specialization of Bronson et al AVL-tree:
 300             - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
 301             - 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.
 302
 303             Depends on tree specialization, different traits member can be used.
 304         */
 305         struct traits
 306         {
 307             /// Key comparison functor
 308             /**
 309                 No default functor is provided. If the option is not specified, the \p less is used.
 310
 311                 See \p cds::opt::compare option description for functor interface.
 312
 313                 You should provide \p compare or \p less functor.
 314             */
 315             typedef opt::none                       compare;
 316
 317             /// Specifies binary predicate used for key compare.
 318             /**
 319                 See \p cds::opt::less option description for predicate interface.
 320
 321                 You should provide \p compare or \p less functor.
 322             */
 323             typedef opt::none                       less;
 324
 325             /// Allocator for internal node
 326             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 327
 328             /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
 329             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 330
 331             /// Disposer (only for pointer-oriented tree specialization)
 332             /**
 333                 The functor used for dispose removed values.
 334                 The user-provided disposer is used only for pointer-oriented tree specialization
 335                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 336                 the disposer will be called to signal that the memory for the value can be safely freed.
 337                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
 338             */
 339             typedef opt::v::delete_disposer<>       disposer;
 340
 341             /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
 342             typedef cds::sync::injecting_monitor<cds::sync::spin>  sync_monitor;
 343
 344             /// Enable relaxed insertion.
 345             /**
 346                 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
 347                 By default, this option is disabled.
 348             */
 349             static bool const relaxed_insert = false;
 350
 351             /// Item counter
 352             /**
 353                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
 354                 To enable it use \p atomicity::item_counter
 355             */
 356             typedef atomicity::empty_item_counter     item_counter;
 357
 358             /// C++ memory ordering model
 359             /**
 360                 List of available memory ordering see \p opt::memory_model
 361             */
 362             typedef opt::v::relaxed_ordering        memory_model;
 363
 364             /// Internal statistics
 365             /**
 366                 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
 367                 To enable it use \p ellen_bintree::stat.
 368             */
 369             typedef empty_stat                      stat;
 370
 371             /// Back-off strategy
 372             typedef cds::backoff::empty             back_off;
 373
 374             /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
 375             /**
 376                 List of available options see \p opt::rcu_check_deadlock
 377             */
 378             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 379         };
 380
 381         /// Metafunction converting option list to BronsonAVLTreeMap traits
 382         /**
 383             Note that there are two main specialization of Bronson et al AVL-tree:
 384             - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
 385             - 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.
 386
 387             Depends on tree specialization, different options can be specified.
 388
 389             \p Options are:
 390             - \p opt::compare - key compare functor. No default functor is provided.
 391                 If the option is not specified, \p %opt::less is used.
 392             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 393             - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
 394             - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
 395                 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
 396             - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
 397                 The user-provided disposer is used only for pointer-oriented tree specialization
 398                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 399                 the disposer will be called to signal that the memory for the value can be safely freed.
 400                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
 401                 Due the nature of GC schema the disposer may be called asynchronously.
 402             - \p opt::sync_monitor -  @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
 403                 default is \p cds::sync::injecting_monitor<cds::sync::spin>
 404             - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
 405                 @ref bronson_avltree::relaxed_insert "relaxed insertion"
 406             - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
 407                 To enable it use \p atomicity::item_counter
 408             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 409                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 410             - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
 411                 To enable statistics use \p \p bronson_avltree::stat
 412             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 413             - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
 414         */
 415         template <typename... Options>
 416         struct make_traits {
 417 #   ifdef CDS_DOXYGEN_INVOKED
 418             typedef implementation_defined type ;   ///< Metafunction result
 419 #   else
 420             typedef typename cds::opt::make_options<
 421                 typename cds::opt::find_type_traits< traits, Options... >::type
 422                 ,Options...
 423             >::type   type;
 424 #   endif
 425         };
 426     } // namespace bronson_avltree
 427
 428     // Forwards
 429     template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
 430     class BronsonAVLTreeMap;
 431
 432 }} // namespace cds::container
 433
 434
 435 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H