cds/container/details/bronson_avltree_base.h

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