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