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
49 , m_pParent( nullptr )
55 link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
56 : m_nHeight( nHeight )
57 , m_nVersion( version )
58 , m_pParent( pParent )
64 atomics::atomic<node_type *>& child( int nDirection )
66 assert( nDirection != 0 );
67 return nDirection < 0 ? m_pLeft : m_pRight;
70 void child( node_type * pChild, int nDirection, atomics::memory_order order )
72 assert( nDirection != 0 );
74 m_pLeft.store( pChild, order );
76 m_pRight.store( pChild, order );
79 version_type version( atomics::memory_order order ) const
81 return m_nVersion.load( order );
84 void version( version_type ver, atomics::memory_order order )
86 m_nVersion.store( ver, order );
89 int height( atomics::memory_order order ) const
91 return m_nHeight.load( order );
94 void height( int h, atomics::memory_order order )
96 m_nHeight.store( h, order );
99 template <typename BackOff>
100 void wait_until_shrink_completed( atomics::memory_order order ) const
103 while ( is_shrinking( order ) )
107 bool is_unlinked( atomics::memory_order order ) const
109 return m_nVersion.load( order ) == unlinked;
112 bool is_shrinking( atomics::memory_order order ) const
114 return (m_nVersion.load( order ) & shrinking) != 0;
117 mapped_type * value( atomics::memory_order order ) const
119 return m_pValue.load( order );
122 bool is_valued( atomics::memory_order order ) const
124 return value( order ) != nullptr;
131 /// BronsonAVLTree internal node
132 template <typename Key, typename T, typename SyncMonitor >
133 struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
136 typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
139 typedef Key key_type; ///< key type
140 typedef T mapped_type; ///< value type
141 typedef typename base_class::version_type version_type;
143 key_type const m_key; ///< Key
144 node * m_pNextRemoved; ///< thread-local list of removed node
148 template <typename Q>
151 , m_key( std::forward<Q>( key ) )
152 , m_pNextRemoved( nullptr )
155 template <typename Q>
156 node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
157 : base_class( nHeight, version, pParent, pLeft, pRight )
158 , m_key( std::forward<Q>( key ) )
159 , m_pNextRemoved( nullptr )
164 /// Base value type for BronsonAVLTreeMap
166 If value type for \p BronsonAVLTreeMap is based on this struct,
167 the map will support some additional methods like \p BronsonAVLTreeMap::get().
168 Moreover, the disposer behaviour is different for ordinal values and
169 values based on \p %bronson_avltree::value:
170 - for ordinal value, its disposer is called immediately after removing
171 the node from the tree. It this case it is not possible to support
172 map's methods that return raw pointer to the tree's value.
173 - if the value type is based on \p %bronson_avltree::value,
174 i.e. \p std::is_base_of( bronson_avltree::value, value_type )::value is \p true,
175 the disposer is called via full RCU cycle. It means that under
176 RCU lock the methods returning raw pointer can be implemented.
180 value * m_pNextRetired;
183 : m_pNextRetired(nullptr)
187 /// BronsonAVLTreeMap internal statistics
188 template <typename Counter = cds::atomicity::event_counter>
190 typedef Counter event_counter; ///< Event counter type
192 event_counter m_nFindSuccess; ///< Count of success \p find() call
193 event_counter m_nFindFailed; ///< Count of failed \p find() call
194 event_counter m_nFindRetry; ///< Count of retries during \p find()
195 event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
197 event_counter m_nInsertSuccess; ///< Count of inserting data node
198 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
199 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
200 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
201 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
202 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
203 event_counter m_nUpdateSuccess; ///< Count of updating data node
204 event_counter m_nUpdateUnlinked; ///< Count of updating of unlinked node attempts
205 event_counter m_nDisposedNode; ///< Count of disposed node
206 event_counter m_nDisposedValue; ///< Count of disposed value
207 event_counter m_nExtractedValue; ///< Count of extracted value
208 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
209 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
210 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
212 event_counter m_nRightRotation; ///< Count of single right rotation
213 event_counter m_nLeftRotation; ///< Count of single left rotation
214 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
215 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
218 void onFindSuccess() { ++m_nFindSuccess ; }
219 void onFindFailed() { ++m_nFindFailed ; }
220 void onFindRetry() { ++m_nFindRetry ; }
221 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
223 void onInsertSuccess() { ++m_nInsertSuccess ; }
224 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
225 void onInsertRetry() { ++m_nInsertRetry ; }
226 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
227 void onUpdateRetry() { ++m_nUpdateRetry; }
228 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
229 void onUpdateSuccess() { ++m_nUpdateSuccess; }
230 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
231 void onDisposeNode() { ++m_nDisposedNode; }
232 void onDisposeValue() { ++m_nDisposedValue; }
233 void onExtractValue() { ++m_nExtractedValue; }
234 void onRemoveRetry() { ++m_nRemoveRetry; }
235 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
237 void onRotateRight() { ++m_nRightRotation; }
238 void onRotateLeft() { ++m_nLeftRotation; }
239 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
240 void onRotateLeftOverRight() { ++m_nLeftRghtRotation; }
244 /// BronsonAVLTreeMap empty statistics
247 void onFindSuccess() const {}
248 void onFindFailed() const {}
249 void onFindRetry() const {}
250 void onFindWaitShrinking() const {}
252 void onInsertSuccess() const {}
253 void onRelaxedInsertFailed() const {}
254 void onInsertRetry() const {}
255 void onUpdateWaitShrinking() const {}
256 void onUpdateRetry() const {}
257 void onUpdateRootWaitShrinking() const {}
258 void onUpdateSuccess() const {}
259 void onUpdateUnlinked() const {}
260 void onDisposeNode() const {}
261 void onDisposeValue() const {}
262 void onExtractValue() const {}
263 void onRemoveRetry() const {}
264 void onRemoveWaitShrinking() const {}
265 void onRemoveRootWaitShrinking() const {}
267 void onRotateRight() const {}
268 void onRotateLeft() const {}
269 void onRotateRightOverLeft() const {}
270 void onRotateLeftOverRight() const {}
274 /// Option to allow relaxed insert into Bronson et al AVL-tree
276 By default, this opton is disabled and the new node is created under its parent lock.
277 In this case, it is guaranteed the new node will be attached to its parent.
278 On the other hand, constructing of the new node can be too complex to make it under the lock,
279 that can lead to lock contention.
281 When this option is enabled, the new node is created before locking the parent node.
282 After that, the parent is locked and checked whether the new node can be attached to the parent.
283 In this case, false node creating can be performed, but locked section can be significantly small.
285 template <bool Enable>
286 struct relaxed_insert {
288 template <typename Base> struct pack : public Base
290 enum { relaxed_insert = Enable };
295 /// BronsnAVLTreeMap traits
297 Note that there are two main specialization of Bronson et al AVL-tree:
298 - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
299 - data-oriented - the tree node contains a copy of values: <tt>BronsonAVLTreeMap<GC, Key, T, Traits> </tt> where \p T is not a pointer type.
301 Depends on tree specialization, different traits member can be used.
305 /// Key comparison functor
307 No default functor is provided. If the option is not specified, the \p less is used.
309 See \p cds::opt::compare option description for functor interface.
311 You should provide \p compare or \p less functor.
313 typedef opt::none compare;
315 /// Specifies binary predicate used for key compare.
317 See \p cds::opt::less option description for predicate interface.
319 You should provide \p compare or \p less functor.
321 typedef opt::none less;
323 /// Allocator for internal node
324 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
326 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
327 typedef CDS_DEFAULT_ALLOCATOR allocator;
329 /// Disposer (only for pointer-oriented tree specialization)
331 The functor used for dispose removed values.
332 The user-provided disposer is used only for pointer-oriented tree specialization
333 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
334 the disposer will be called to signal that the memory for the value can be safely freed.
335 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
337 typedef opt::v::delete_disposer<> disposer;
339 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
340 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
342 /// Enable relaxed insertion.
344 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
345 By default, this option is disabled.
347 static bool const relaxed_insert = false;
351 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
352 To enable it use \p atomicity::item_counter
354 typedef atomicity::empty_item_counter item_counter;
356 /// C++ memory ordering model
358 List of available memory ordering see \p opt::memory_model
360 typedef opt::v::relaxed_ordering memory_model;
362 /// Internal statistics
364 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
365 To enable it use \p ellen_bintree::stat.
367 typedef empty_stat stat;
369 /// Back-off strategy
370 typedef cds::backoff::empty back_off;
372 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
374 List of available options see \p opt::rcu_check_deadlock
376 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
379 /// Metafunction converting option list to BronsonAVLTreeMap traits
381 Note that there are two main specialization of Bronson et al AVL-tree:
382 - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
383 - data-oriented - the tree node contains a copy of values: <tt>BronsonAVLTreeMap<GC, Key, T, Traits> </tt> where \p T is not a pointer type.
385 Depends on tree specialization, different options can be specified.
388 - \p opt::compare - key compare functor. No default functor is provided.
389 If the option is not specified, \p %opt::less is used.
390 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
391 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
392 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
393 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
394 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
395 The user-provided disposer is used only for pointer-oriented tree specialization
396 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
397 the disposer will be called to signal that the memory for the value can be safely freed.
398 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
399 Due the nature of GC schema the disposer may be called asynchronously.
400 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
401 default is \p cds::sync::injecting_monitor<cds::sync::spin>
402 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
403 @ref bronson_avltree::relaxed_insert "relaxed insertion"
404 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
405 To enable it use \p atomicity::item_counter
406 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
407 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
408 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
409 To enable statistics use \p \p bronson_avltree::stat
410 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
411 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
413 template <typename... Options>
415 # ifdef CDS_DOXYGEN_INVOKED
416 typedef implementation_defined type ; ///< Metafunction result
418 typedef typename cds::opt::make_options<
419 typename cds::opt::find_type_traits< traits, Options... >::type
424 } // namespace bronson_avltree
427 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
428 class BronsonAVLTreeMap;
430 }} // namespace cds::container
433 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H