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 node_type * child( int nDirection, atomics::memory_order order ) const
75 assert( nDirection != 0 );
76 return nDirection < 0 ? m_pLeft.load( order ) : m_pRight.load( order );
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_nRemoveSuccess; ///< Count of successfully \p erase() call
196 event_counter m_nRemoveFailed; ///< Count of failed \p erase() call
197 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
198 event_counter m_nExtractSuccess; ///< Count of successfully \p extract() call
199 event_counter m_nExtractFailed; ///< Count of failed \p extract() call
200 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
201 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
202 event_counter m_nMakeRoutingNode; ///< How many nodes were converted to routing (valueless) nodes
204 event_counter m_nRightRotation; ///< Count of single right rotation
205 event_counter m_nLeftRotation; ///< Count of single left rotation
206 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
207 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
209 event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
210 event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
211 event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
213 event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation
214 event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation
215 event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation
217 event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation
218 event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation
219 event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation
220 event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation
222 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
223 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
226 void onFindSuccess() { ++m_nFindSuccess ; }
227 void onFindFailed() { ++m_nFindFailed ; }
228 void onFindRetry() { ++m_nFindRetry ; }
229 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
231 void onInsertSuccess() { ++m_nInsertSuccess; }
232 void onInsertFailed() { ++m_nInsertFailed; }
233 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
234 void onInsertRetry() { ++m_nInsertRetry ; }
235 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
236 void onUpdateRetry() { ++m_nUpdateRetry; }
237 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
238 void onUpdateSuccess() { ++m_nUpdateSuccess; }
239 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
240 void onDisposeNode() { ++m_nDisposedNode; }
241 void onDisposeValue() { ++m_nDisposedValue; }
242 void onExtractValue() { ++m_nExtractedValue; }
243 void onRemove(bool bSuccess)
250 void onExtract( bool bSuccess )
257 void onRemoveRetry() { ++m_nRemoveRetry; }
258 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
259 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
260 void onMakeRoutingNode() { ++m_nMakeRoutingNode; }
262 void onRotateRight() { ++m_nRightRotation; }
263 void onRotateLeft() { ++m_nLeftRotation; }
264 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
265 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
267 void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
268 void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
269 void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
271 void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; }
272 void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; }
273 void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; }
275 void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; }
276 void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; }
277 void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; }
278 void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; }
280 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
281 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
285 /// BronsonAVLTreeMap empty statistics
288 void onFindSuccess() const {}
289 void onFindFailed() const {}
290 void onFindRetry() const {}
291 void onFindWaitShrinking() const {}
293 void onInsertSuccess() const {}
294 void onInsertFailed() const {}
295 void onRelaxedInsertFailed() const {}
296 void onInsertRetry() const {}
297 void onUpdateWaitShrinking() const {}
298 void onUpdateRetry() const {}
299 void onUpdateRootWaitShrinking() const {}
300 void onUpdateSuccess() const {}
301 void onUpdateUnlinked() const {}
302 void onDisposeNode() const {}
303 void onDisposeValue() const {}
304 void onExtractValue() const {}
305 void onRemove(bool /*bSuccess*/) const {}
306 void onExtract(bool /*bSuccess*/) const {}
307 void onRemoveRetry() const {}
308 void onRemoveWaitShrinking() const {}
309 void onRemoveRootWaitShrinking() const {}
310 void onMakeRoutingNode() const {}
312 void onRotateRight() const {}
313 void onRotateLeft() const {}
314 void onRotateRightOverLeft() const {}
315 void onRotateLeftOverRight() const {}
317 void onRotateAfterRightRotation() const {}
318 void onRemoveAfterRightRotation() const {}
319 void onDamageAfterRightRotation() const {}
321 void onRotateAfterLeftRotation() const {}
322 void onRemoveAfterLeftRotation() const {}
323 void onDamageAfterLeftRotation() const {}
325 void onRotateAfterRLRotation() const {}
326 void onRemoveAfterRLRotation() const {}
327 void onRotateAfterLRRotation() const {}
328 void onRemoveAfterLRRotation() const {}
330 void onInsertRebalanceRequired() const {}
331 void onRemoveRebalanceRequired() const {}
335 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
337 By default, this option is disabled and the new node is created under its parent lock.
338 In this case, it is guaranteed the new node will be attached to its parent.
339 On the other hand, constructing of the new node can be too complex to make it under the lock,
340 that can lead to lock contention.
342 When this option is enabled, the new node is created before locking the parent node.
343 After that, the parent is locked and checked whether the new node may be attached to the parent.
344 In this case, false node creating can be performed, but locked section can be significantly small.
346 template <bool Enable>
347 struct relaxed_insert {
349 template <typename Base> struct pack : public Base
351 enum { relaxed_insert = Enable };
356 /// \p BronsonAVLTreeMap traits
358 Note that there are two main specialization of Bronson et al AVL-tree:
359 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
360 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
362 Depends on tree specialization, different traits member can be used.
366 /// Key comparison functor
368 No default functor is provided. If the option is not specified, the \p less is used.
370 See \p cds::opt::compare option description for functor interface.
372 You should provide \p compare or \p less functor.
374 typedef opt::none compare;
376 /// Specifies binary predicate used for key compare.
378 See \p cds::opt::less option description for predicate interface.
380 You should provide \p compare or \p less functor.
382 typedef opt::none less;
384 /// Allocator for internal node
385 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
387 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
388 typedef CDS_DEFAULT_ALLOCATOR allocator;
390 /// Disposer (only for pointer-oriented tree specialization)
392 The functor used for dispose removed values.
393 The user-provided disposer is used only for pointer-oriented tree specialization
394 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
395 the disposer will be called to signal that the memory for the value can be safely freed.
396 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
398 typedef opt::v::delete_disposer<> disposer;
400 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
401 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
403 /// Enable relaxed insertion.
405 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
406 By default, this option is disabled.
408 static bool const relaxed_insert = false;
412 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
413 To enable it use \p atomicity::item_counter
415 typedef atomicity::empty_item_counter item_counter;
417 /// C++ memory ordering model
419 List of available memory ordering see \p opt::memory_model
421 typedef opt::v::relaxed_ordering memory_model;
423 /// Internal statistics
425 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
426 To enable it use \p ellen_bintree::stat.
428 typedef empty_stat stat;
430 /// Back-off strategy
431 typedef cds::backoff::empty back_off;
433 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
435 List of available options see \p opt::rcu_check_deadlock
437 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
440 /// Metafunction converting option list to BronsonAVLTreeMap traits
442 Note that there are two main specialization of Bronson et al AVL-tree:
443 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
444 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
446 Depends on tree specialization, different options can be specified.
449 - \p opt::compare - key compare functor. No default functor is provided.
450 If the option is not specified, \p %opt::less is used.
451 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
452 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
453 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
454 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
455 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
456 The user-provided disposer is used only for pointer-oriented tree specialization
457 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
458 the disposer will be called to signal that the memory for the value can be safely freed.
459 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
460 Due the nature of GC schema the disposer may be called asynchronously.
461 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
462 default is \p cds::sync::injecting_monitor<cds::sync::spin>
463 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
464 @ref bronson_avltree::relaxed_insert "relaxed insertion"
465 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
466 To enable it use \p atomicity::item_counter
467 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
468 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
469 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
470 To enable statistics use \p \p bronson_avltree::stat
471 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
472 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
474 template <typename... Options>
476 # ifdef CDS_DOXYGEN_INVOKED
477 typedef implementation_defined type ; ///< Metafunction result
479 typedef typename cds::opt::make_options<
480 typename cds::opt::find_type_traits< traits, Options... >::type
485 } // namespace bronson_avltree
488 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
489 class BronsonAVLTreeMap;
491 }} // namespace cds::container
493 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H