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>
10 #include <cds/sync/injecting_monitor.h>
12 namespace cds { namespace container {
14 /// BronsonAVLTree related declarations
15 namespace bronson_avltree {
17 template <typename Key, typename T, typename SyncMonitor >
21 template <typename Node, typename T, typename SyncMonitor>
24 typedef Node node_type;
25 typedef T mapped_type;
26 typedef uint32_t version_type; ///< version type (internal)
32 version_flags = shrinking | unlinked
33 // the rest is version counter
36 atomics::atomic< int > m_nHeight; ///< Node height
37 atomics::atomic<version_type> m_nVersion; ///< Version bits
38 atomics::atomic<node_type *> m_pParent; ///< Parent node
39 atomics::atomic<node_type *> m_pLeft; ///< Left child
40 atomics::atomic<node_type *> m_pRight; ///< Right child
41 typename SyncMonitor::node_injection m_SyncMonitorInjection; ///< @ref cds_sync_monitor "synchronization monitor" injected data
42 atomics::atomic<mapped_type *> m_pValue; ///< Value
48 , m_pParent( nullptr )
54 link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
55 : m_nHeight( nHeight )
56 , m_nVersion( version )
57 , m_pParent( pParent )
63 node_type * parent( atomics::memory_order order ) const
65 return m_pParent.load( order );
68 void parent( node_type * p, atomics::memory_order order )
73 atomics::atomic<node_type *> const& child( int nDirection ) const
75 assert( nDirection != 0 );
76 return nDirection < 0 ? m_pLeft : m_pRight;
79 void child( node_type * pChild, int nDirection, atomics::memory_order order )
81 assert( nDirection != 0 );
83 m_pLeft.store( pChild, order );
85 m_pRight.store( pChild, order );
88 version_type version( atomics::memory_order order ) const
90 return m_nVersion.load( order );
93 void version( version_type ver, atomics::memory_order order )
95 m_nVersion.store( ver, order );
98 int height( atomics::memory_order order ) const
100 return m_nHeight.load( order );
103 void height( int h, atomics::memory_order order )
105 m_nHeight.store( h, order );
108 template <typename BackOff>
109 void wait_until_shrink_completed( atomics::memory_order order ) const
112 while ( is_shrinking( order ) )
116 bool is_unlinked( atomics::memory_order order ) const
118 return m_nVersion.load( order ) == unlinked;
121 bool is_shrinking( atomics::memory_order order ) const
123 return (m_nVersion.load( order ) & shrinking) != 0;
126 mapped_type * value( atomics::memory_order order ) const
128 return m_pValue.load( order );
131 bool is_valued( atomics::memory_order order ) const
133 return value( order ) != nullptr;
138 /// BronsonAVLTree internal node
139 template <typename Key, typename T, typename SyncMonitor >
140 struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
143 typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
146 typedef Key key_type; ///< key type
147 typedef T mapped_type; ///< value type
149 typedef typename base_class::version_type version_type;
152 key_type const m_key; ///< Key
153 node * m_pNextRemoved; ///< thread-local list of removed node
157 template <typename Q>
160 , m_key( std::forward<Q>( key ) )
161 , m_pNextRemoved( nullptr )
164 template <typename Q>
165 node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
166 : base_class( nHeight, version, pParent, pLeft, pRight )
167 , m_key( std::forward<Q>( key ) )
168 , m_pNextRemoved( nullptr )
173 /// BronsonAVLTreeMap internal statistics
174 template <typename Counter = cds::atomicity::event_counter>
176 typedef Counter event_counter; ///< Event counter type
178 event_counter m_nFindSuccess; ///< Count of success \p find() call
179 event_counter m_nFindFailed; ///< Count of failed \p find() call
180 event_counter m_nFindRetry; ///< Count of retries during \p find()
181 event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
183 event_counter m_nInsertSuccess; ///< Count of inserting data node
184 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
185 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
186 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
187 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
188 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
189 event_counter m_nUpdateSuccess; ///< Count of updating data node
190 event_counter m_nUpdateUnlinked; ///< Count of attempts to update unlinked node
191 event_counter m_nDisposedNode; ///< Count of disposed node
192 event_counter m_nDisposedValue; ///< Count of disposed value
193 event_counter m_nExtractedValue; ///< Count of extracted value
194 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
195 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
196 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
198 event_counter m_nRightRotation; ///< Count of single right rotation
199 event_counter m_nLeftRotation; ///< Count of single left rotation
200 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
201 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
203 event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
204 event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
205 event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
207 event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation
208 event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation
209 event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation
211 event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation
212 event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation
213 event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation
214 event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation
216 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
217 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
220 void onFindSuccess() { ++m_nFindSuccess ; }
221 void onFindFailed() { ++m_nFindFailed ; }
222 void onFindRetry() { ++m_nFindRetry ; }
223 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
225 void onInsertSuccess() { ++m_nInsertSuccess ; }
226 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
227 void onInsertRetry() { ++m_nInsertRetry ; }
228 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
229 void onUpdateRetry() { ++m_nUpdateRetry; }
230 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
231 void onUpdateSuccess() { ++m_nUpdateSuccess; }
232 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
233 void onDisposeNode() { ++m_nDisposedNode; }
234 void onDisposeValue() { ++m_nDisposedValue; }
235 void onExtractValue() { ++m_nExtractedValue; }
236 void onRemoveRetry() { ++m_nRemoveRetry; }
237 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
238 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
240 void onRotateRight() { ++m_nRightRotation; }
241 void onRotateLeft() { ++m_nLeftRotation; }
242 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
243 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
245 void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
246 void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
247 void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
249 void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; }
250 void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; }
251 void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; }
253 void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; }
254 void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; }
255 void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; }
256 void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; }
258 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
259 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
263 /// BronsonAVLTreeMap empty statistics
266 void onFindSuccess() const {}
267 void onFindFailed() const {}
268 void onFindRetry() const {}
269 void onFindWaitShrinking() const {}
271 void onInsertSuccess() const {}
272 void onRelaxedInsertFailed() const {}
273 void onInsertRetry() const {}
274 void onUpdateWaitShrinking() const {}
275 void onUpdateRetry() const {}
276 void onUpdateRootWaitShrinking() const {}
277 void onUpdateSuccess() const {}
278 void onUpdateUnlinked() const {}
279 void onDisposeNode() const {}
280 void onDisposeValue() const {}
281 void onExtractValue() const {}
282 void onRemoveRetry() const {}
283 void onRemoveWaitShrinking() const {}
284 void onRemoveRootWaitShrinking() const {}
286 void onRotateRight() const {}
287 void onRotateLeft() const {}
288 void onRotateRightOverLeft() const {}
289 void onRotateLeftOverRight() const {}
291 void onRotateAfterRightRotation() const {}
292 void onRemoveAfterRightRotation() const {}
293 void onDamageAfterRightRotation() const {}
295 void onRotateAfterLeftRotation() const {}
296 void onRemoveAfterLeftRotation() const {}
297 void onDamageAfterLeftRotation() const {}
299 void onRotateAfterRLRotation() const {}
300 void onRemoveAfterRLRotation() const {}
301 void onRotateAfterLRRotation() const {}
302 void onRemoveAfterLRRotation() const {}
304 void onInsertRebalanceRequired() const {}
305 void onRemoveRebalanceRequired() const {}
309 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
311 By default, this option is disabled and the new node is created under its parent lock.
312 In this case, it is guaranteed the new node will be attached to its parent.
313 On the other hand, constructing of the new node can be too complex to make it under the lock,
314 that can lead to lock contention.
316 When this option is enabled, the new node is created before locking the parent node.
317 After that, the parent is locked and checked whether the new node may be attached to the parent.
318 In this case, false node creating can be performed, but locked section can be significantly small.
320 template <bool Enable>
321 struct relaxed_insert {
323 template <typename Base> struct pack : public Base
325 enum { relaxed_insert = Enable };
330 /// \p BronsonAVLTreeMap traits
332 Note that there are two main specialization of Bronson et al AVL-tree:
333 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
334 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
336 Depends on tree specialization, different traits member can be used.
340 /// Key comparison functor
342 No default functor is provided. If the option is not specified, the \p less is used.
344 See \p cds::opt::compare option description for functor interface.
346 You should provide \p compare or \p less functor.
348 typedef opt::none compare;
350 /// Specifies binary predicate used for key compare.
352 See \p cds::opt::less option description for predicate interface.
354 You should provide \p compare or \p less functor.
356 typedef opt::none less;
358 /// Allocator for internal node
359 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
361 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
362 typedef CDS_DEFAULT_ALLOCATOR allocator;
364 /// Disposer (only for pointer-oriented tree specialization)
366 The functor used for dispose removed values.
367 The user-provided disposer is used only for pointer-oriented tree specialization
368 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
369 the disposer will be called to signal that the memory for the value can be safely freed.
370 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
372 typedef opt::v::delete_disposer<> disposer;
374 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
375 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
377 /// Enable relaxed insertion.
379 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
380 By default, this option is disabled.
382 static bool const relaxed_insert = false;
386 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
387 To enable it use \p atomicity::item_counter
389 typedef atomicity::empty_item_counter item_counter;
391 /// C++ memory ordering model
393 List of available memory ordering see \p opt::memory_model
395 typedef opt::v::relaxed_ordering memory_model;
397 /// Internal statistics
399 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
400 To enable it use \p ellen_bintree::stat.
402 typedef empty_stat stat;
404 /// Back-off strategy
405 typedef cds::backoff::empty back_off;
407 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
409 List of available options see \p opt::rcu_check_deadlock
411 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
414 /// Metafunction converting option list to BronsonAVLTreeMap traits
416 Note that there are two main specialization of Bronson et al AVL-tree:
417 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
418 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
420 Depends on tree specialization, different options can be specified.
423 - \p opt::compare - key compare functor. No default functor is provided.
424 If the option is not specified, \p %opt::less is used.
425 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
426 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
427 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
428 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
429 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
430 The user-provided disposer is used only for pointer-oriented tree specialization
431 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
432 the disposer will be called to signal that the memory for the value can be safely freed.
433 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
434 Due the nature of GC schema the disposer may be called asynchronously.
435 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
436 default is \p cds::sync::injecting_monitor<cds::sync::spin>
437 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
438 @ref bronson_avltree::relaxed_insert "relaxed insertion"
439 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
440 To enable it use \p atomicity::item_counter
441 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
442 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
443 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
444 To enable statistics use \p \p bronson_avltree::stat
445 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
446 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
448 template <typename... Options>
450 # ifdef CDS_DOXYGEN_INVOKED
451 typedef implementation_defined type ; ///< Metafunction result
453 typedef typename cds::opt::make_options<
454 typename cds::opt::find_type_traits< traits, Options... >::type
459 } // namespace bronson_avltree
462 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
463 class BronsonAVLTreeMap;
465 }} // namespace cds::container
468 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H