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 uint64_t version_type;
  25             typedef Lock lock_type;
  26
  27             enum class version_flags : version_type
  28             {
  29                 unlinked = 1,
  30                 growing = 2,
  31                 shrinking = 4,
  32                 grow_count_increment = 1 << 3,
  33                 grow_count_mask = 0xff << 3,
  34                 shrink_count_increment = 1 << 11,
  35                 ignore_grow = ~(growing | grow_count_mask)
  36             };
  37
  38             atomics::atomic< int >          m_nHeight;  ///< Node height
  39             atomics::atomic<version_type>   m_nVersion; ///< Version bits
  40             atomics::atomic<node_type *>    m_pParent;  ///< Parent node
  41             atomics::atomic<node_type *>    m_pLeft;    ///< Left child
  42             atomics::atomic<node_type *>    m_pRight;   ///< Right child
  43             lock_type                       m_Lock;     ///< Node-level lock
  44
  45             atomics::atomic<node_type *>& child( int nDirection ) const
  46             {
  47                 assert( nDirection != 0 );
  48                 return nDirection < 0 ? m_pLeft : m_pRight;
  49             }
  50
  51             version_type version( atomics::memory_order order ) const
  52             {
  53                 return m_nVersion.load( order );
  54             }
  55
  56             template <typename BackOff>
  57             void wait_until_shrink_completed( atomics::memory_order order ) const
  58             {
  59                 BackOff bkoff;
  60                 while ( version( order ) & version_flags::shrinking )
  61                     bkoff();
  62             }
  63         };
  64
  65         template <typename Key, typename T, typename Lock>
  66         struct node : public link< Key, T, Lock >
  67         {
  68             typedef Key key_type;
  69             typedef T   mapped_type;
  70             typedef link< key_type, mapped_type, Lock > base_class;
  71
  72             key_type const  m_key;
  73             atomics::atomic<mapped_type *>  m_pValue;
  74
  75             template <typename Q>
  76             node( Q&& key )
  77                 : m_key( std::forward<Q>(key) )
  78                 , m_pValue( nullptr )
  79             {}
  80
  81             template <typename Q>
  82             node( Q&& key, mapped_type * pVal )
  83                 : m_key( std::forward<Q>(key) )
  84                 , m_pValue( pVal )
  85             {}
  86
  87             T * value( atomics::memory_order order ) const
  88             {
  89                 return m_pValue.load( order );
  90             }
  91         };
  92         //@endcond
  93
  94         /// BronsonAVLTreeMap internal statistics
  95         template <typename Counter = cds::atomicity::event_counter>
  96         struct stat {
  97             typedef Counter   event_counter; ///< Event counter type
  98
  99             event_counter   m_nFindSuccess; ///< Count of success \p find() call
 100             event_counter   m_nFindFailed;  ///< Count of failed \p find() call
 101             event_counter   m_nFindRetry;   ///< Count of retries during \p find()
 102             event_counter   m_nFindWaitShrinking;   ///< Count of waiting until shrinking completed duting \p find() call
 103
 104             //@cond
 105             void onFindSuccess()        { ++m_nFindSuccess      ; }
 106             void onFindFailed()         { ++m_nFindFailed       ; }
 107             void onFindRetry()          { ++m_nFindRetry        ; }
 108             void onFindWaitShrinking()  { ++m_nFindWaitShrinking; }
 109
 110             //@endcond
 111         };
 112
 113         /// BronsonAVLTreeMap empty statistics
 114         struct empty_stat {
 115             //@cond
 116             void onFindSuccess()        const {}
 117             void onFindFailed()         const {}
 118             void onFindRetry()          const {}
 119             void onFindWaitShrinking()  const {}
 120             //@endcond
 121         };
 122
 123         /// BronsnAVLTreeMap traits
 124         /**
 125             Note that there are two main specialization of Bronson et al AVL-tree:
 126             - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
 127             - 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.
 128
 129             Depends on tree specialization, different traits member can be used.
 130         */
 131         struct traits
 132         {
 133             /// Key comparison functor
 134             /**
 135                 No default functor is provided. If the option is not specified, the \p less is used.
 136
 137                 See \p cds::opt::compare option description for functor interface.
 138
 139                 You should provide \p compare or \p less functor.
 140             */
 141             typedef opt::none                       compare;
 142
 143             /// Specifies binary predicate used for key compare.
 144             /**
 145                 See \p cds::opt::less option description for predicate interface.
 146
 147                 You should provide \p compare or \p less functor.
 148             */
 149             typedef opt::none                       less;
 150
 151             /// Allocator for internal node
 152             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 153
 154             /// Disposer (only for pointer-oriented tree specialization)
 155             /**
 156                 The functor used for dispose removed values.
 157                 The user-provided disposer is used only for pointer-oriented tree specialization
 158                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 159                 the disposer will be called to signal that the memory for the value can be safely freed.
 160                 Default is \ref cds::intrusive::opt::v::delete_disposer "cds::container::opt::v::delete_disposer" which calls \p delete operator.
 161             */
 162             typedef opt::v::delete_disposer         disposer;
 163
 164             /// Node lock
 165             typedef cds::SpinLock                   lock_type;
 166
 167             /// Item counter
 168             /**
 169                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
 170                 To enable it use \p atomicity::item_counter
 171             */
 172             typedef atomicity::empty_item_counter     item_counter;
 173
 174             /// C++ memory ordering model
 175             /**
 176                 List of available memory ordering see \p opt::memory_model
 177             */
 178             typedef opt::v::relaxed_ordering        memory_model;
 179
 180             /// Internal statistics
 181             /**
 182                 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
 183                 To enable it use \p ellen_bintree::stat.
 184             */
 185             typedef empty_stat                      stat;
 186
 187             /// Back-off strategy
 188             typedef cds::backoff::empty             back_off;
 189
 190             /// RCU deadlock checking policy (only for \ref cds_intrusive_BronsonAVLTree_rcu "RCU-based BronsonAVLTree")
 191             /**
 192                 List of available options see \p opt::rcu_check_deadlock
 193             */
 194             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 195
 196             //@cond
 197             // Internal traits, not for direct usage
 198             typedef opt::none   node_type;
 199             //@endcond
 200         };
 201
 202         /// Metafunction converting option list to BronsonAVLTreeMap traits
 203         /**
 204             Note that there are two main specialization of Bronson et al AVL-tree:
 205             - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
 206             - 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.
 207
 208             Depends on tree specialization, different options can be specified.
 209
 210             \p Options are:
 211             - \p opt::compare - key compare functor. No default functor is provided.
 212                 If the option is not specified, \p %opt::less is used.
 213             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
 214             - \p opt::allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
 215             - \ref cds::intusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
 216                 The user-provided disposer is used only for pointer-oriented tree specialization
 217                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
 218                 the disposer will be called to signal that the memory for the value can be safely freed.
 219                 Default is \ref cds::intrusive::opt::v::delete_disposer "cds::container::opt::v::delete_disposer" which calls \p delete operator.
 220                 Due the nature of GC schema the disposer may be called asynchronously.
 221             - \p opt::lock_type - node lock type, default is \p cds::SpinLock
 222             - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
 223                 To enable it use \p atomicity::item_counter
 224             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 225                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 226             - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
 227                 To enable statistics use \p \p bronson_avltree::stat
 228             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
 229             - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
 230         */
 231         template <typename... Options>
 232         struct make_traits {
 233 #   ifdef CDS_DOXYGEN_INVOKED
 234             typedef implementation_defined type ;   ///< Metafunction result
 235 #   else
 236             typedef typename cds::opt::make_options<
 237                 typename cds::opt::find_type_traits< traits, Options... >::type
 238                 ,Options...
 239             >::type   type;
 240 #   endif
 241         };
 242
 243
 244     } // namespace bronson_avltree
 245
 246     // Forwards
 247     template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
 248     class BronsonAVLTreeMap;
 249
 250 }} // namespace cds::container
 251
 252
 253 #endif // #ifndef __CDS_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H