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 struct implementation_tag;
20 template <typename Key, typename T, typename SyncMonitor >
24 template <typename Node, typename T, typename SyncMonitor>
27 typedef Node node_type;
28 typedef T mapped_type;
29 typedef uint32_t version_type; ///< version type (internal)
35 version_flags = shrinking | unlinked
36 // the rest is version counter
39 atomics::atomic< int > m_nHeight; ///< Node height
40 atomics::atomic<version_type> m_nVersion; ///< Version bits
41 atomics::atomic<node_type *> m_pParent; ///< Parent node
42 atomics::atomic<node_type *> m_pLeft; ///< Left child
43 atomics::atomic<node_type *> m_pRight; ///< Right child
44 typename SyncMonitor::node_injection m_SyncMonitorInjection; ///< @ref cds_sync_monitor "synchronization monitor" injected data
45 atomics::atomic<mapped_type *> m_pValue; ///< Value
51 , m_pParent( nullptr )
57 link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
58 : m_nHeight( nHeight )
59 , m_nVersion( version )
60 , m_pParent( pParent )
66 node_type * parent( atomics::memory_order order ) const
68 return m_pParent.load( order );
71 void parent( node_type * p, atomics::memory_order order )
73 m_pParent.store( p, order );
76 atomics::atomic<node_type *> const& child( int nDirection ) const
78 assert( nDirection != 0 );
79 return nDirection < 0 ? m_pLeft : m_pRight;
82 void child( node_type * pChild, int nDirection, atomics::memory_order order )
84 assert( nDirection != 0 );
86 m_pLeft.store( pChild, order );
88 m_pRight.store( pChild, order );
91 version_type version( atomics::memory_order order ) const
93 return m_nVersion.load( order );
96 void version( version_type ver, atomics::memory_order order )
98 m_nVersion.store( ver, order );
101 int height( atomics::memory_order order ) const
103 return m_nHeight.load( order );
106 void height( int h, atomics::memory_order order )
108 m_nHeight.store( h, order );
111 template <typename BackOff>
112 void wait_until_shrink_completed( atomics::memory_order order ) const
115 while ( is_shrinking( order ) )
119 bool is_unlinked( atomics::memory_order order ) const
121 return m_nVersion.load( order ) == unlinked;
124 bool is_shrinking( atomics::memory_order order ) const
126 return (m_nVersion.load( order ) & shrinking) != 0;
129 mapped_type * value( atomics::memory_order order ) const
131 return m_pValue.load( order );
134 bool is_valued( atomics::memory_order order ) const
136 return value( order ) != nullptr;
141 /// BronsonAVLTree internal node
142 template <typename Key, typename T, typename SyncMonitor >
143 struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
146 typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
149 typedef Key key_type; ///< key type
150 typedef T mapped_type; ///< value type
152 typedef typename base_class::version_type version_type;
155 key_type const m_key; ///< Key
156 node * m_pNextRemoved; ///< thread-local list of removed node
160 template <typename Q>
163 , m_key( std::forward<Q>( key ) )
164 , m_pNextRemoved( nullptr )
167 template <typename Q>
168 node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
169 : base_class( nHeight, version, pParent, pLeft, pRight )
170 , m_key( std::forward<Q>( key ) )
171 , m_pNextRemoved( nullptr )
176 /// BronsonAVLTreeMap internal statistics
177 template <typename Counter = cds::atomicity::event_counter>
179 typedef Counter event_counter; ///< Event counter type
181 event_counter m_nFindSuccess; ///< Count of success \p find() call
182 event_counter m_nFindFailed; ///< Count of failed \p find() call
183 event_counter m_nFindRetry; ///< Count of retries during \p find()
184 event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
186 event_counter m_nInsertSuccess; ///< Count of inserting data node
187 event_counter m_nInsertFailed; ///< Count of insert failures
188 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
189 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
190 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
191 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
192 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
193 event_counter m_nUpdateSuccess; ///< Count of updating data node
194 event_counter m_nUpdateUnlinked; ///< Count of attempts to update unlinked node
195 event_counter m_nDisposedNode; ///< Count of disposed node
196 event_counter m_nDisposedValue; ///< Count of disposed value
197 event_counter m_nExtractedValue; ///< Count of extracted value
198 event_counter m_nRemoveSuccess; ///< Count of successfully \p erase() call
199 event_counter m_nRemoveFailed; ///< Count of failed \p erase() call
200 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
201 event_counter m_nExtractSuccess; ///< Count of successfully \p extract() call
202 event_counter m_nExtractFailed; ///< Count of failed \p extract() call
203 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
204 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
205 event_counter m_nMakeRoutingNode; ///< How many nodes were converted to routing (valueless) nodes
207 event_counter m_nRightRotation; ///< Count of single right rotation
208 event_counter m_nLeftRotation; ///< Count of single left rotation
209 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
210 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
212 event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
213 event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
214 event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
216 event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation
217 event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation
218 event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation
220 event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation
221 event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation
222 event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation
223 event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation
225 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
226 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
229 void onFindSuccess() { ++m_nFindSuccess ; }
230 void onFindFailed() { ++m_nFindFailed ; }
231 void onFindRetry() { ++m_nFindRetry ; }
232 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
234 void onInsertSuccess() { ++m_nInsertSuccess; }
235 void onInsertFailed() { ++m_nInsertFailed; }
236 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
237 void onInsertRetry() { ++m_nInsertRetry ; }
238 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
239 void onUpdateRetry() { ++m_nUpdateRetry; }
240 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
241 void onUpdateSuccess() { ++m_nUpdateSuccess; }
242 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
243 void onDisposeNode() { ++m_nDisposedNode; }
244 void onDisposeValue() { ++m_nDisposedValue; }
245 void onExtractValue() { ++m_nExtractedValue; }
246 void onRemove(bool bSuccess)
253 void onExtract( bool bSuccess )
260 void onRemoveRetry() { ++m_nRemoveRetry; }
261 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
262 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
263 void onMakeRoutingNode() { ++m_nMakeRoutingNode; }
265 void onRotateRight() { ++m_nRightRotation; }
266 void onRotateLeft() { ++m_nLeftRotation; }
267 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
268 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
270 void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
271 void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
272 void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
274 void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; }
275 void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; }
276 void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; }
278 void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; }
279 void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; }
280 void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; }
281 void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; }
283 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
284 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
288 /// BronsonAVLTreeMap empty statistics
291 void onFindSuccess() const {}
292 void onFindFailed() const {}
293 void onFindRetry() const {}
294 void onFindWaitShrinking() const {}
296 void onInsertSuccess() const {}
297 void onInsertFailed() const {}
298 void onRelaxedInsertFailed() const {}
299 void onInsertRetry() const {}
300 void onUpdateWaitShrinking() const {}
301 void onUpdateRetry() const {}
302 void onUpdateRootWaitShrinking() const {}
303 void onUpdateSuccess() const {}
304 void onUpdateUnlinked() const {}
305 void onDisposeNode() const {}
306 void onDisposeValue() const {}
307 void onExtractValue() const {}
308 void onRemove(bool /*bSuccess*/) const {}
309 void onExtract(bool /*bSuccess*/) const {}
310 void onRemoveRetry() const {}
311 void onRemoveWaitShrinking() const {}
312 void onRemoveRootWaitShrinking() const {}
313 void onMakeRoutingNode() const {}
315 void onRotateRight() const {}
316 void onRotateLeft() const {}
317 void onRotateRightOverLeft() const {}
318 void onRotateLeftOverRight() const {}
320 void onRotateAfterRightRotation() const {}
321 void onRemoveAfterRightRotation() const {}
322 void onDamageAfterRightRotation() const {}
324 void onRotateAfterLeftRotation() const {}
325 void onRemoveAfterLeftRotation() const {}
326 void onDamageAfterLeftRotation() const {}
328 void onRotateAfterRLRotation() const {}
329 void onRemoveAfterRLRotation() const {}
330 void onRotateAfterLRRotation() const {}
331 void onRemoveAfterLRRotation() const {}
333 void onInsertRebalanceRequired() const {}
334 void onRemoveRebalanceRequired() const {}
338 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
340 By default, this option is disabled and the new node is created under its parent lock.
341 In this case, it is guaranteed the new node will be attached to its parent.
342 On the other hand, constructing of the new node can be too complex to make it under the lock,
343 that can lead to lock contention.
345 When this option is enabled, the new node is created before locking the parent node.
346 After that, the parent is locked and checked whether the new node may be attached to the parent.
347 In this case, false node creating can be performed, but locked section can be significantly small.
349 template <bool Enable>
350 struct relaxed_insert {
352 template <typename Base> struct pack : public Base
354 enum { relaxed_insert = Enable };
359 /// \p BronsonAVLTreeMap traits
361 Note that there are two main specialization of Bronson et al AVL-tree:
362 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
363 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
365 Depends on tree specialization, different traits member can be used.
369 /// Key comparison functor
371 No default functor is provided. If the option is not specified, the \p less is used.
373 See \p cds::opt::compare option description for functor interface.
375 You should provide \p compare or \p less functor.
377 typedef opt::none compare;
379 /// Specifies binary predicate used for key compare.
381 See \p cds::opt::less option description for predicate interface.
383 You should provide \p compare or \p less functor.
385 typedef opt::none less;
387 /// Allocator for internal node
388 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
390 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
391 typedef CDS_DEFAULT_ALLOCATOR allocator;
393 /// Disposer (only for pointer-oriented tree specialization)
395 The functor used for dispose removed values.
396 The user-provided disposer is used only for pointer-oriented tree specialization
397 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
398 the disposer will be called to signal that the memory for the value can be safely freed.
399 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
401 typedef opt::v::delete_disposer<> disposer;
403 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
404 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
406 /// Enable relaxed insertion.
408 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
409 By default, this option is disabled.
411 static bool const relaxed_insert = false;
415 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
416 To enable it use \p atomicity::item_counter
418 typedef atomicity::empty_item_counter item_counter;
420 /// C++ memory ordering model
422 List of available memory ordering see \p opt::memory_model
424 typedef opt::v::relaxed_ordering memory_model;
426 /// Internal statistics
428 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
429 To enable it use \p ellen_bintree::stat.
431 typedef empty_stat stat;
433 /// Back-off strategy
434 typedef cds::backoff::empty back_off;
436 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
438 List of available options see \p opt::rcu_check_deadlock
440 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
443 /// Metafunction converting option list to BronsonAVLTreeMap traits
445 Note that there are two main specialization of Bronson et al AVL-tree:
446 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
447 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
449 Depends on tree specialization, different options can be specified.
452 - \p opt::compare - key compare functor. No default functor is provided.
453 If the option is not specified, \p %opt::less is used.
454 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
455 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
456 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
457 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
458 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
459 The user-provided disposer is used only for pointer-oriented tree specialization
460 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
461 the disposer will be called to signal that the memory for the value can be safely freed.
462 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
463 Due the nature of GC schema the disposer may be called asynchronously.
464 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
465 default is \p cds::sync::injecting_monitor<cds::sync::spin>
466 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
467 @ref bronson_avltree::relaxed_insert "relaxed insertion"
468 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
469 To enable it use \p atomicity::item_counter
470 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
471 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
472 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
473 To enable statistics use \p \p bronson_avltree::stat
474 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
475 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
477 template <typename... Options>
479 # ifdef CDS_DOXYGEN_INVOKED
480 typedef implementation_defined type ; ///< Metafunction result
482 typedef typename cds::opt::make_options<
483 typename cds::opt::find_type_traits< traits, Options... >::type
488 } // namespace bronson_avltree
491 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
492 class BronsonAVLTreeMap;
494 }} // namespace cds::container
496 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H