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 )
70 m_pParent.store( p, 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_nInsertFailed; ///< Count of insert failures
185 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
186 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
187 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
188 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
189 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
190 event_counter m_nUpdateSuccess; ///< Count of updating data node
191 event_counter m_nUpdateUnlinked; ///< Count of attempts to update unlinked node
192 event_counter m_nDisposedNode; ///< Count of disposed node
193 event_counter m_nDisposedValue; ///< Count of disposed value
194 event_counter m_nExtractedValue; ///< Count of extracted value
195 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
196 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
197 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
199 event_counter m_nRightRotation; ///< Count of single right rotation
200 event_counter m_nLeftRotation; ///< Count of single left rotation
201 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
202 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
204 event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
205 event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
206 event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
208 event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation
209 event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation
210 event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation
212 event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation
213 event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation
214 event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation
215 event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation
217 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
218 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
221 void onFindSuccess() { ++m_nFindSuccess ; }
222 void onFindFailed() { ++m_nFindFailed ; }
223 void onFindRetry() { ++m_nFindRetry ; }
224 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
226 void onInsertSuccess() { ++m_nInsertSuccess; }
227 void onInsertFailed() { ++m_nInsertFailed; }
228 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
229 void onInsertRetry() { ++m_nInsertRetry ; }
230 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
231 void onUpdateRetry() { ++m_nUpdateRetry; }
232 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
233 void onUpdateSuccess() { ++m_nUpdateSuccess; }
234 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
235 void onDisposeNode() { ++m_nDisposedNode; }
236 void onDisposeValue() { ++m_nDisposedValue; }
237 void onExtractValue() { ++m_nExtractedValue; }
238 void onRemoveRetry() { ++m_nRemoveRetry; }
239 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
240 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
242 void onRotateRight() { ++m_nRightRotation; }
243 void onRotateLeft() { ++m_nLeftRotation; }
244 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
245 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
247 void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
248 void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
249 void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
251 void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; }
252 void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; }
253 void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; }
255 void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; }
256 void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; }
257 void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; }
258 void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; }
260 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
261 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
265 /// BronsonAVLTreeMap empty statistics
268 void onFindSuccess() const {}
269 void onFindFailed() const {}
270 void onFindRetry() const {}
271 void onFindWaitShrinking() const {}
273 void onInsertSuccess() const {}
274 void onInsertFailed() const {}
275 void onRelaxedInsertFailed() const {}
276 void onInsertRetry() const {}
277 void onUpdateWaitShrinking() const {}
278 void onUpdateRetry() const {}
279 void onUpdateRootWaitShrinking() const {}
280 void onUpdateSuccess() const {}
281 void onUpdateUnlinked() const {}
282 void onDisposeNode() const {}
283 void onDisposeValue() const {}
284 void onExtractValue() const {}
285 void onRemoveRetry() const {}
286 void onRemoveWaitShrinking() const {}
287 void onRemoveRootWaitShrinking() const {}
289 void onRotateRight() const {}
290 void onRotateLeft() const {}
291 void onRotateRightOverLeft() const {}
292 void onRotateLeftOverRight() const {}
294 void onRotateAfterRightRotation() const {}
295 void onRemoveAfterRightRotation() const {}
296 void onDamageAfterRightRotation() const {}
298 void onRotateAfterLeftRotation() const {}
299 void onRemoveAfterLeftRotation() const {}
300 void onDamageAfterLeftRotation() const {}
302 void onRotateAfterRLRotation() const {}
303 void onRemoveAfterRLRotation() const {}
304 void onRotateAfterLRRotation() const {}
305 void onRemoveAfterLRRotation() const {}
307 void onInsertRebalanceRequired() const {}
308 void onRemoveRebalanceRequired() const {}
312 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
314 By default, this option is disabled and the new node is created under its parent lock.
315 In this case, it is guaranteed the new node will be attached to its parent.
316 On the other hand, constructing of the new node can be too complex to make it under the lock,
317 that can lead to lock contention.
319 When this option is enabled, the new node is created before locking the parent node.
320 After that, the parent is locked and checked whether the new node may be attached to the parent.
321 In this case, false node creating can be performed, but locked section can be significantly small.
323 template <bool Enable>
324 struct relaxed_insert {
326 template <typename Base> struct pack : public Base
328 enum { relaxed_insert = Enable };
333 /// \p BronsonAVLTreeMap traits
335 Note that there are two main specialization of Bronson et al AVL-tree:
336 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
337 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
339 Depends on tree specialization, different traits member can be used.
343 /// Key comparison functor
345 No default functor is provided. If the option is not specified, the \p less is used.
347 See \p cds::opt::compare option description for functor interface.
349 You should provide \p compare or \p less functor.
351 typedef opt::none compare;
353 /// Specifies binary predicate used for key compare.
355 See \p cds::opt::less option description for predicate interface.
357 You should provide \p compare or \p less functor.
359 typedef opt::none less;
361 /// Allocator for internal node
362 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
364 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
365 typedef CDS_DEFAULT_ALLOCATOR allocator;
367 /// Disposer (only for pointer-oriented tree specialization)
369 The functor used for dispose removed values.
370 The user-provided disposer is used only for pointer-oriented tree specialization
371 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
372 the disposer will be called to signal that the memory for the value can be safely freed.
373 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
375 typedef opt::v::delete_disposer<> disposer;
377 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
378 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
380 /// Enable relaxed insertion.
382 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
383 By default, this option is disabled.
385 static bool const relaxed_insert = false;
389 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
390 To enable it use \p atomicity::item_counter
392 typedef atomicity::empty_item_counter item_counter;
394 /// C++ memory ordering model
396 List of available memory ordering see \p opt::memory_model
398 typedef opt::v::relaxed_ordering memory_model;
400 /// Internal statistics
402 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
403 To enable it use \p ellen_bintree::stat.
405 typedef empty_stat stat;
407 /// Back-off strategy
408 typedef cds::backoff::empty back_off;
410 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
412 List of available options see \p opt::rcu_check_deadlock
414 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
417 /// Metafunction converting option list to BronsonAVLTreeMap traits
419 Note that there are two main specialization of Bronson et al AVL-tree:
420 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
421 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
423 Depends on tree specialization, different options can be specified.
426 - \p opt::compare - key compare functor. No default functor is provided.
427 If the option is not specified, \p %opt::less is used.
428 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
429 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
430 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
431 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
432 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
433 The user-provided disposer is used only for pointer-oriented tree specialization
434 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
435 the disposer will be called to signal that the memory for the value can be safely freed.
436 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
437 Due the nature of GC schema the disposer may be called asynchronously.
438 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
439 default is \p cds::sync::injecting_monitor<cds::sync::spin>
440 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
441 @ref bronson_avltree::relaxed_insert "relaxed insertion"
442 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
443 To enable it use \p atomicity::item_counter
444 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
445 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
446 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
447 To enable statistics use \p \p bronson_avltree::stat
448 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
449 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
451 template <typename... Options>
453 # ifdef CDS_DOXYGEN_INVOKED
454 typedef implementation_defined type ; ///< Metafunction result
456 typedef typename cds::opt::make_options<
457 typename cds::opt::find_type_traits< traits, Options... >::type
462 } // namespace bronson_avltree
465 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
466 class BronsonAVLTreeMap;
468 }} // namespace cds::container
470 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H