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 /// BronsonAVLTreeMap internal statistics
165 template <typename Counter = cds::atomicity::event_counter>
167 typedef Counter event_counter; ///< Event counter type
169 event_counter m_nFindSuccess; ///< Count of success \p find() call
170 event_counter m_nFindFailed; ///< Count of failed \p find() call
171 event_counter m_nFindRetry; ///< Count of retries during \p find()
172 event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
174 event_counter m_nInsertSuccess; ///< Count of inserting data node
175 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
176 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
177 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
178 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
179 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
180 event_counter m_nUpdateSuccess; ///< Count of updating data node
181 event_counter m_nUpdateUnlinked; ///< Count of attempts to update unlinked node
182 event_counter m_nDisposedNode; ///< Count of disposed node
183 event_counter m_nDisposedValue; ///< Count of disposed value
184 event_counter m_nExtractedValue; ///< Count of extracted value
185 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
186 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
187 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
189 event_counter m_nRightRotation; ///< Count of single right rotation
190 event_counter m_nLeftRotation; ///< Count of single left rotation
191 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
192 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
195 void onFindSuccess() { ++m_nFindSuccess ; }
196 void onFindFailed() { ++m_nFindFailed ; }
197 void onFindRetry() { ++m_nFindRetry ; }
198 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
200 void onInsertSuccess() { ++m_nInsertSuccess ; }
201 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
202 void onInsertRetry() { ++m_nInsertRetry ; }
203 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
204 void onUpdateRetry() { ++m_nUpdateRetry; }
205 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
206 void onUpdateSuccess() { ++m_nUpdateSuccess; }
207 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
208 void onDisposeNode() { ++m_nDisposedNode; }
209 void onDisposeValue() { ++m_nDisposedValue; }
210 void onExtractValue() { ++m_nExtractedValue; }
211 void onRemoveRetry() { ++m_nRemoveRetry; }
212 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
213 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
215 void onRotateRight() { ++m_nRightRotation; }
216 void onRotateLeft() { ++m_nLeftRotation; }
217 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
218 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
222 /// BronsonAVLTreeMap empty statistics
225 void onFindSuccess() const {}
226 void onFindFailed() const {}
227 void onFindRetry() const {}
228 void onFindWaitShrinking() const {}
230 void onInsertSuccess() const {}
231 void onRelaxedInsertFailed() const {}
232 void onInsertRetry() const {}
233 void onUpdateWaitShrinking() const {}
234 void onUpdateRetry() const {}
235 void onUpdateRootWaitShrinking() const {}
236 void onUpdateSuccess() const {}
237 void onUpdateUnlinked() const {}
238 void onDisposeNode() const {}
239 void onDisposeValue() const {}
240 void onExtractValue() const {}
241 void onRemoveRetry() const {}
242 void onRemoveWaitShrinking() const {}
243 void onRemoveRootWaitShrinking() const {}
245 void onRotateRight() const {}
246 void onRotateLeft() const {}
247 void onRotateRightOverLeft() const {}
248 void onRotateLeftOverRight() const {}
252 /// Option to allow relaxed insert into Bronson et al AVL-tree
254 By default, this opton is disabled and the new node is created under its parent lock.
255 In this case, it is guaranteed the new node will be attached to its parent.
256 On the other hand, constructing of the new node can be too complex to make it under the lock,
257 that can lead to lock contention.
259 When this option is enabled, the new node is created before locking the parent node.
260 After that, the parent is locked and checked whether the new node may be attached to the parent.
261 In this case, false node creating can be performed, but locked section can be significantly small.
263 template <bool Enable>
264 struct relaxed_insert {
266 template <typename Base> struct pack : public Base
268 enum { relaxed_insert = Enable };
273 /// BronsnAVLTreeMap traits
275 Note that there are two main specialization of Bronson et al AVL-tree:
276 - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
277 - 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.
279 Depends on tree specialization, different traits member can be used.
283 /// Key comparison functor
285 No default functor is provided. If the option is not specified, the \p less is used.
287 See \p cds::opt::compare option description for functor interface.
289 You should provide \p compare or \p less functor.
291 typedef opt::none compare;
293 /// Specifies binary predicate used for key compare.
295 See \p cds::opt::less option description for predicate interface.
297 You should provide \p compare or \p less functor.
299 typedef opt::none less;
301 /// Allocator for internal node
302 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
304 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
305 typedef CDS_DEFAULT_ALLOCATOR allocator;
307 /// Disposer (only for pointer-oriented tree specialization)
309 The functor used for dispose removed values.
310 The user-provided disposer is used only for pointer-oriented tree specialization
311 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
312 the disposer will be called to signal that the memory for the value can be safely freed.
313 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
315 typedef opt::v::delete_disposer<> disposer;
317 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
318 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
320 /// Enable relaxed insertion.
322 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
323 By default, this option is disabled.
325 static bool const relaxed_insert = false;
329 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
330 To enable it use \p atomicity::item_counter
332 typedef atomicity::empty_item_counter item_counter;
334 /// C++ memory ordering model
336 List of available memory ordering see \p opt::memory_model
338 typedef opt::v::relaxed_ordering memory_model;
340 /// Internal statistics
342 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
343 To enable it use \p ellen_bintree::stat.
345 typedef empty_stat stat;
347 /// Back-off strategy
348 typedef cds::backoff::empty back_off;
350 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
352 List of available options see \p opt::rcu_check_deadlock
354 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
357 /// Metafunction converting option list to BronsonAVLTreeMap traits
359 Note that there are two main specialization of Bronson et al AVL-tree:
360 - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
361 - 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.
363 Depends on tree specialization, different options can be specified.
366 - \p opt::compare - key compare functor. No default functor is provided.
367 If the option is not specified, \p %opt::less is used.
368 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
369 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
370 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
371 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
372 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - 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 rounting 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.
377 Due the nature of GC schema the disposer may be called asynchronously.
378 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
379 default is \p cds::sync::injecting_monitor<cds::sync::spin>
380 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
381 @ref bronson_avltree::relaxed_insert "relaxed insertion"
382 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
383 To enable it use \p atomicity::item_counter
384 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
385 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
386 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
387 To enable statistics use \p \p bronson_avltree::stat
388 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
389 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
391 template <typename... Options>
393 # ifdef CDS_DOXYGEN_INVOKED
394 typedef implementation_defined type ; ///< Metafunction result
396 typedef typename cds::opt::make_options<
397 typename cds::opt::find_type_traits< traits, Options... >::type
402 } // namespace bronson_avltree
405 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
406 class BronsonAVLTreeMap;
408 }} // namespace cds::container
411 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H