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 atomics::atomic<node_type *>& child( int nDirection )
65 assert( nDirection != 0 );
66 return nDirection < 0 ? m_pLeft : m_pRight;
69 void child( node_type * pChild, int nDirection, atomics::memory_order order )
71 assert( nDirection != 0 );
73 m_pLeft.store( pChild, order );
75 m_pRight.store( pChild, order );
78 version_type version( atomics::memory_order order ) const
80 return m_nVersion.load( order );
83 void version( version_type ver, atomics::memory_order order )
85 m_nVersion.store( ver, order );
88 int height( atomics::memory_order order ) const
90 return m_nHeight.load( order );
93 void height( int h, atomics::memory_order order )
95 m_nHeight.store( h, order );
98 template <typename BackOff>
99 void wait_until_shrink_completed( atomics::memory_order order ) const
102 while ( is_shrinking( order ) )
106 bool is_unlinked( atomics::memory_order order ) const
108 return m_nVersion.load( order ) == unlinked;
111 bool is_shrinking( atomics::memory_order order ) const
113 return (m_nVersion.load( order ) & shrinking) != 0;
116 mapped_type * value( atomics::memory_order order ) const
118 return m_pValue.load( order );
121 bool is_valued( atomics::memory_order order ) const
123 return value( order ) != nullptr;
128 /// BronsonAVLTree internal node
129 template <typename Key, typename T, typename SyncMonitor >
130 struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
133 typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
136 typedef Key key_type; ///< key type
137 typedef T mapped_type; ///< value type
139 typedef typename base_class::version_type version_type;
142 key_type const m_key; ///< Key
143 node * m_pNextRemoved; ///< thread-local list of removed node
147 template <typename Q>
150 , m_key( std::forward<Q>( key ) )
151 , m_pNextRemoved( nullptr )
154 template <typename Q>
155 node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
156 : base_class( nHeight, version, pParent, pLeft, pRight )
157 , m_key( std::forward<Q>( key ) )
158 , m_pNextRemoved( nullptr )
163 /// BronsonAVLTreeMap internal statistics
164 template <typename Counter = cds::atomicity::event_counter>
166 typedef Counter event_counter; ///< Event counter type
168 event_counter m_nFindSuccess; ///< Count of success \p find() call
169 event_counter m_nFindFailed; ///< Count of failed \p find() call
170 event_counter m_nFindRetry; ///< Count of retries during \p find()
171 event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
173 event_counter m_nInsertSuccess; ///< Count of inserting data node
174 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
175 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
176 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
177 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
178 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
179 event_counter m_nUpdateSuccess; ///< Count of updating data node
180 event_counter m_nUpdateUnlinked; ///< Count of attempts to update unlinked node
181 event_counter m_nDisposedNode; ///< Count of disposed node
182 event_counter m_nDisposedValue; ///< Count of disposed value
183 event_counter m_nExtractedValue; ///< Count of extracted value
184 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
185 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
186 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
188 event_counter m_nRightRotation; ///< Count of single right rotation
189 event_counter m_nLeftRotation; ///< Count of single left rotation
190 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
191 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
193 event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
194 event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
195 event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
197 event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation
198 event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation
199 event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation
201 event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation
202 event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation
203 event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation
204 event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation
206 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
207 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
210 void onFindSuccess() { ++m_nFindSuccess ; }
211 void onFindFailed() { ++m_nFindFailed ; }
212 void onFindRetry() { ++m_nFindRetry ; }
213 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
215 void onInsertSuccess() { ++m_nInsertSuccess ; }
216 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
217 void onInsertRetry() { ++m_nInsertRetry ; }
218 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
219 void onUpdateRetry() { ++m_nUpdateRetry; }
220 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
221 void onUpdateSuccess() { ++m_nUpdateSuccess; }
222 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
223 void onDisposeNode() { ++m_nDisposedNode; }
224 void onDisposeValue() { ++m_nDisposedValue; }
225 void onExtractValue() { ++m_nExtractedValue; }
226 void onRemoveRetry() { ++m_nRemoveRetry; }
227 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
228 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
230 void onRotateRight() { ++m_nRightRotation; }
231 void onRotateLeft() { ++m_nLeftRotation; }
232 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
233 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
235 void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
236 void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
237 void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
239 void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; }
240 void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; }
241 void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; }
243 void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; }
244 void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; }
245 void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; }
246 void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; }
248 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
249 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
253 /// BronsonAVLTreeMap empty statistics
256 void onFindSuccess() const {}
257 void onFindFailed() const {}
258 void onFindRetry() const {}
259 void onFindWaitShrinking() const {}
261 void onInsertSuccess() const {}
262 void onRelaxedInsertFailed() const {}
263 void onInsertRetry() const {}
264 void onUpdateWaitShrinking() const {}
265 void onUpdateRetry() const {}
266 void onUpdateRootWaitShrinking() const {}
267 void onUpdateSuccess() const {}
268 void onUpdateUnlinked() const {}
269 void onDisposeNode() const {}
270 void onDisposeValue() const {}
271 void onExtractValue() const {}
272 void onRemoveRetry() const {}
273 void onRemoveWaitShrinking() const {}
274 void onRemoveRootWaitShrinking() const {}
276 void onRotateRight() const {}
277 void onRotateLeft() const {}
278 void onRotateRightOverLeft() const {}
279 void onRotateLeftOverRight() const {}
281 void onRotateAfterRightRotation() const {}
282 void onRemoveAfterRightRotation() const {}
283 void onDamageAfterRightRotation() const {}
285 void onRotateAfterLeftRotation() const {}
286 void onRemoveAfterLeftRotation() const {}
287 void onDamageAfterLeftRotation() const {}
289 void onRotateAfterRLRotation() const {}
290 void onRemoveAfterRLRotation() const {}
291 void onRotateAfterLRRotation() const {}
292 void onRemoveAfterLRRotation() const {}
294 void onInsertRebalanceRequired() const {}
295 void onRemoveRebalanceRequired() const {}
299 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
301 By default, this option is disabled and the new node is created under its parent lock.
302 In this case, it is guaranteed the new node will be attached to its parent.
303 On the other hand, constructing of the new node can be too complex to make it under the lock,
304 that can lead to lock contention.
306 When this option is enabled, the new node is created before locking the parent node.
307 After that, the parent is locked and checked whether the new node may be attached to the parent.
308 In this case, false node creating can be performed, but locked section can be significantly small.
310 template <bool Enable>
311 struct relaxed_insert {
313 template <typename Base> struct pack : public Base
315 enum { relaxed_insert = Enable };
320 /// \p BronsonAVLTreeMap traits
322 Note that there are two main specialization of Bronson et al AVL-tree:
323 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
324 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
326 Depends on tree specialization, different traits member can be used.
330 /// Key comparison functor
332 No default functor is provided. If the option is not specified, the \p less is used.
334 See \p cds::opt::compare option description for functor interface.
336 You should provide \p compare or \p less functor.
338 typedef opt::none compare;
340 /// Specifies binary predicate used for key compare.
342 See \p cds::opt::less option description for predicate interface.
344 You should provide \p compare or \p less functor.
346 typedef opt::none less;
348 /// Allocator for internal node
349 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
351 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
352 typedef CDS_DEFAULT_ALLOCATOR allocator;
354 /// Disposer (only for pointer-oriented tree specialization)
356 The functor used for dispose removed values.
357 The user-provided disposer is used only for pointer-oriented tree specialization
358 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
359 the disposer will be called to signal that the memory for the value can be safely freed.
360 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
362 typedef opt::v::delete_disposer<> disposer;
364 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
365 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
367 /// Enable relaxed insertion.
369 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
370 By default, this option is disabled.
372 static bool const relaxed_insert = false;
376 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
377 To enable it use \p atomicity::item_counter
379 typedef atomicity::empty_item_counter item_counter;
381 /// C++ memory ordering model
383 List of available memory ordering see \p opt::memory_model
385 typedef opt::v::relaxed_ordering memory_model;
387 /// Internal statistics
389 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
390 To enable it use \p ellen_bintree::stat.
392 typedef empty_stat stat;
394 /// Back-off strategy
395 typedef cds::backoff::empty back_off;
397 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
399 List of available options see \p opt::rcu_check_deadlock
401 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
404 /// Metafunction converting option list to BronsonAVLTreeMap traits
406 Note that there are two main specialization of Bronson et al AVL-tree:
407 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
408 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
410 Depends on tree specialization, different options can be specified.
413 - \p opt::compare - key compare functor. No default functor is provided.
414 If the option is not specified, \p %opt::less is used.
415 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
416 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
417 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
418 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
419 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
420 The user-provided disposer is used only for pointer-oriented tree specialization
421 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
422 the disposer will be called to signal that the memory for the value can be safely freed.
423 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
424 Due the nature of GC schema the disposer may be called asynchronously.
425 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
426 default is \p cds::sync::injecting_monitor<cds::sync::spin>
427 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
428 @ref bronson_avltree::relaxed_insert "relaxed insertion"
429 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
430 To enable it use \p atomicity::item_counter
431 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
432 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
433 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
434 To enable statistics use \p \p bronson_avltree::stat
435 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
436 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
438 template <typename... Options>
440 # ifdef CDS_DOXYGEN_INVOKED
441 typedef implementation_defined type ; ///< Metafunction result
443 typedef typename cds::opt::make_options<
444 typename cds::opt::find_type_traits< traits, Options... >::type
449 } // namespace bronson_avltree
452 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
453 class BronsonAVLTreeMap;
455 }} // namespace cds::container
458 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H