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_nRemoveRetry; ///< Count o erase/extract retries
199 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
200 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
202 event_counter m_nRightRotation; ///< Count of single right rotation
203 event_counter m_nLeftRotation; ///< Count of single left rotation
204 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
205 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
207 event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
208 event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
209 event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
211 event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation
212 event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation
213 event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation
215 event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation
216 event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation
217 event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation
218 event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation
220 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
221 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
224 void onFindSuccess() { ++m_nFindSuccess ; }
225 void onFindFailed() { ++m_nFindFailed ; }
226 void onFindRetry() { ++m_nFindRetry ; }
227 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
229 void onInsertSuccess() { ++m_nInsertSuccess; }
230 void onInsertFailed() { ++m_nInsertFailed; }
231 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
232 void onInsertRetry() { ++m_nInsertRetry ; }
233 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
234 void onUpdateRetry() { ++m_nUpdateRetry; }
235 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
236 void onUpdateSuccess() { ++m_nUpdateSuccess; }
237 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
238 void onDisposeNode() { ++m_nDisposedNode; }
239 void onDisposeValue() { ++m_nDisposedValue; }
240 void onExtractValue() { ++m_nExtractedValue; }
241 void onRemoveRetry() { ++m_nRemoveRetry; }
242 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
243 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
245 void onRotateRight() { ++m_nRightRotation; }
246 void onRotateLeft() { ++m_nLeftRotation; }
247 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
248 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
250 void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
251 void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
252 void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
254 void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; }
255 void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; }
256 void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; }
258 void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; }
259 void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; }
260 void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; }
261 void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; }
263 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
264 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
268 /// BronsonAVLTreeMap empty statistics
271 void onFindSuccess() const {}
272 void onFindFailed() const {}
273 void onFindRetry() const {}
274 void onFindWaitShrinking() const {}
276 void onInsertSuccess() const {}
277 void onInsertFailed() const {}
278 void onRelaxedInsertFailed() const {}
279 void onInsertRetry() const {}
280 void onUpdateWaitShrinking() const {}
281 void onUpdateRetry() const {}
282 void onUpdateRootWaitShrinking() const {}
283 void onUpdateSuccess() const {}
284 void onUpdateUnlinked() const {}
285 void onDisposeNode() const {}
286 void onDisposeValue() const {}
287 void onExtractValue() const {}
288 void onRemoveRetry() const {}
289 void onRemoveWaitShrinking() const {}
290 void onRemoveRootWaitShrinking() const {}
292 void onRotateRight() const {}
293 void onRotateLeft() const {}
294 void onRotateRightOverLeft() const {}
295 void onRotateLeftOverRight() const {}
297 void onRotateAfterRightRotation() const {}
298 void onRemoveAfterRightRotation() const {}
299 void onDamageAfterRightRotation() const {}
301 void onRotateAfterLeftRotation() const {}
302 void onRemoveAfterLeftRotation() const {}
303 void onDamageAfterLeftRotation() const {}
305 void onRotateAfterRLRotation() const {}
306 void onRemoveAfterRLRotation() const {}
307 void onRotateAfterLRRotation() const {}
308 void onRemoveAfterLRRotation() const {}
310 void onInsertRebalanceRequired() const {}
311 void onRemoveRebalanceRequired() const {}
315 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
317 By default, this option is disabled and the new node is created under its parent lock.
318 In this case, it is guaranteed the new node will be attached to its parent.
319 On the other hand, constructing of the new node can be too complex to make it under the lock,
320 that can lead to lock contention.
322 When this option is enabled, the new node is created before locking the parent node.
323 After that, the parent is locked and checked whether the new node may be attached to the parent.
324 In this case, false node creating can be performed, but locked section can be significantly small.
326 template <bool Enable>
327 struct relaxed_insert {
329 template <typename Base> struct pack : public Base
331 enum { relaxed_insert = Enable };
336 /// \p BronsonAVLTreeMap traits
338 Note that there are two main specialization of Bronson et al AVL-tree:
339 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
340 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
342 Depends on tree specialization, different traits member can be used.
346 /// Key comparison functor
348 No default functor is provided. If the option is not specified, the \p less is used.
350 See \p cds::opt::compare option description for functor interface.
352 You should provide \p compare or \p less functor.
354 typedef opt::none compare;
356 /// Specifies binary predicate used for key compare.
358 See \p cds::opt::less option description for predicate interface.
360 You should provide \p compare or \p less functor.
362 typedef opt::none less;
364 /// Allocator for internal node
365 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
367 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
368 typedef CDS_DEFAULT_ALLOCATOR allocator;
370 /// Disposer (only for pointer-oriented tree specialization)
372 The functor used for dispose removed values.
373 The user-provided disposer is used only for pointer-oriented tree specialization
374 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
375 the disposer will be called to signal that the memory for the value can be safely freed.
376 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
378 typedef opt::v::delete_disposer<> disposer;
380 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
381 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
383 /// Enable relaxed insertion.
385 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
386 By default, this option is disabled.
388 static bool const relaxed_insert = false;
392 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
393 To enable it use \p atomicity::item_counter
395 typedef atomicity::empty_item_counter item_counter;
397 /// C++ memory ordering model
399 List of available memory ordering see \p opt::memory_model
401 typedef opt::v::relaxed_ordering memory_model;
403 /// Internal statistics
405 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
406 To enable it use \p ellen_bintree::stat.
408 typedef empty_stat stat;
410 /// Back-off strategy
411 typedef cds::backoff::empty back_off;
413 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
415 List of available options see \p opt::rcu_check_deadlock
417 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
420 /// Metafunction converting option list to BronsonAVLTreeMap traits
422 Note that there are two main specialization of Bronson et al AVL-tree:
423 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
424 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
426 Depends on tree specialization, different options can be specified.
429 - \p opt::compare - key compare functor. No default functor is provided.
430 If the option is not specified, \p %opt::less is used.
431 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
432 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
433 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
434 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
435 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
436 The user-provided disposer is used only for pointer-oriented tree specialization
437 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
438 the disposer will be called to signal that the memory for the value can be safely freed.
439 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
440 Due the nature of GC schema the disposer may be called asynchronously.
441 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
442 default is \p cds::sync::injecting_monitor<cds::sync::spin>
443 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
444 @ref bronson_avltree::relaxed_insert "relaxed insertion"
445 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
446 To enable it use \p atomicity::item_counter
447 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
448 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
449 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
450 To enable statistics use \p \p bronson_avltree::stat
451 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
452 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
454 template <typename... Options>
456 # ifdef CDS_DOXYGEN_INVOKED
457 typedef implementation_defined type ; ///< Metafunction result
459 typedef typename cds::opt::make_options<
460 typename cds::opt::find_type_traits< traits, Options... >::type
465 } // namespace bronson_avltree
468 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
469 class BronsonAVLTreeMap;
471 }} // namespace cds::container
473 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H