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