3 #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
4 #define CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
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>
11 namespace cds { namespace container {
13 /// BronsonAVLTree related declarations
14 namespace bronson_avltree {
16 template <typename Key, typename T>
20 template <typename Key, typename T, typename Lock>
23 typedef node<Key, T> node_type;
24 typedef uint32_t version_type;
25 typedef Lock lock_type;
31 version_flags = shrinking | unlinked
32 // the rest is version counter
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
42 node_type * m_pNextRemoved; ///< thread-local list o removed node
47 , m_pParent( nullptr )
50 , m_pNextRemoved( nullptr )
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 )
59 , m_pNextRemoved( nullptr )
62 atomics::atomic<node_type *>& child( int nDirection ) const
64 assert( nDirection != 0 );
65 return nDirection < 0 ? m_pLeft : m_pRight;
68 void child( node_type * pChild, int nDirection, atomics::memory_order order )
70 assert( nDirection != 0 );
72 m_pLeft.store( pChild, order );
74 m_pRight.store( pChild, order );
77 version_type version( atomics::memory_order order ) const
79 return m_nVersion.load( order );
82 void version( version_type ver, atomics::memory_order order )
84 m_nVersion.store( ver, order );
87 int height( atomics::memory_order order ) const
89 return m_nHeight.load( order );
92 void height( int h, atomics::memory_order order )
94 m_nHeight.store( h, order );
96 template <typename BackOff>
97 void wait_until_shrink_completed( atomics::memory_order order ) const
100 while ( is_shrinking( order ))
104 bool is_unlinked( atomics::memory_order order ) const
106 return (m_nVersion.load( order ) & unlinked) != 0;
109 bool is_shrinking( atomics::memory_order order ) const
111 return (m_nVersion.load( order ) & shrinking) != 0;
115 template <typename Key, typename T, typename Lock>
116 struct node : public link< Key, T, Lock >
118 typedef Key key_type;
119 typedef T mapped_type;
120 typedef link< key_type, mapped_type, Lock > base_class;
122 key_type const m_key;
123 atomics::atomic<mapped_type *> m_pValue;
125 template <typename Q>
127 : m_key( std::forward<Q>(key) )
128 , m_pValue( nullptr )
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 )
138 T * value( atomics::memory_order order ) const
140 return m_pValue.load( order );
145 /// BronsonAVLTreeMap internal statistics
146 template <typename Counter = cds::atomicity::event_counter>
148 typedef Counter event_counter; ///< Event counter type
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
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
166 void onFindSuccess() { ++m_nFindSuccess ; }
167 void onFindFailed() { ++m_nFindFailed ; }
168 void onFindRetry() { ++m_nFindRetry ; }
169 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
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; }
184 /// BronsonAVLTreeMap empty statistics
187 void onFindSuccess() const {}
188 void onFindFailed() const {}
189 void onFindRetry() const {}
190 void onFindWaitShrinking() const {}
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 {}
205 /// Option to allow relaxed insert into Bronson et al AVL-tree
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.
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.
216 template <bool Enable>
217 struct relaxed_insert {
219 template <typename Base> struct pack : public Base
221 enum { relaxed_insert = Enable };
226 /// BronsnAVLTreeMap traits
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.
232 Depends on tree specialization, different traits member can be used.
236 /// Key comparison functor
238 No default functor is provided. If the option is not specified, the \p less is used.
240 See \p cds::opt::compare option description for functor interface.
242 You should provide \p compare or \p less functor.
244 typedef opt::none compare;
246 /// Specifies binary predicate used for key compare.
248 See \p cds::opt::less option description for predicate interface.
250 You should provide \p compare or \p less functor.
252 typedef opt::none less;
254 /// Allocator for internal node
255 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
257 /// Disposer (only for pointer-oriented tree specialization)
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.
265 typedef opt::v::delete_disposer<> disposer;
268 typedef std::mutex lock_type;
270 /// Enable relaxed insertion.
272 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
273 By default, this option is disabled.
275 static bool const relaxed_insert = false;
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
282 typedef atomicity::empty_item_counter item_counter;
284 /// C++ memory ordering model
286 List of available memory ordering see \p opt::memory_model
288 typedef opt::v::relaxed_ordering memory_model;
290 /// Internal statistics
292 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
293 To enable it use \p ellen_bintree::stat.
295 typedef empty_stat stat;
297 /// Back-off strategy
298 typedef cds::backoff::empty back_off;
300 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
302 List of available options see \p opt::rcu_check_deadlock
304 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
307 /// Metafunction converting option list to BronsonAVLTreeMap traits
309 Note that there are two main specialization of Bronson et al AVL-tree:
310 - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
311 - 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.
313 Depends on tree specialization, different options can be specified.
316 - \p opt::compare - key compare functor. No default functor is provided.
317 If the option is not specified, \p %opt::less is used.
318 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
319 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
320 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
321 The user-provided disposer is used only for pointer-oriented tree specialization
322 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
323 the disposer will be called to signal that the memory for the value can be safely freed.
324 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
325 Due the nature of GC schema the disposer may be called asynchronously.
326 - \p opt::lock_type - node lock type, default is \p std::mutex
327 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
328 @ref bronson_avltree::relaxed_insert "relaxed insertion"
329 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
330 To enable it use \p atomicity::item_counter
331 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
332 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
333 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
334 To enable statistics use \p \p bronson_avltree::stat
335 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
336 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
338 template <typename... Options>
340 # ifdef CDS_DOXYGEN_INVOKED
341 typedef implementation_defined type ; ///< Metafunction result
343 typedef typename cds::opt::make_options<
344 typename cds::opt::find_type_traits< traits, Options... >::type
351 } // namespace bronson_avltree
354 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
355 class BronsonAVLTreeMap;
357 }} // namespace cds::container
360 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H