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