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