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