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 SyncMonitor>
24 typedef Node node_type;
25 typedef uint32_t version_type; ///< version type (internal)
31 version_flags = shrinking | unlinked
32 // the rest is version counter
35 atomics::atomic< int > m_nHeight; ///< Node height
36 atomics::atomic<version_type> m_nVersion; ///< Version bits
37 atomics::atomic<node_type *> m_pParent; ///< Parent node
38 atomics::atomic<node_type *> m_pLeft; ///< Left child
39 atomics::atomic<node_type *> m_pRight; ///< Right child
40 typename SyncMonitor::node_injection m_SyncMonitorInjection; ///< @ref cds_sync_monitor "synchronization monitor" injected data
47 , m_pParent( nullptr )
52 link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
53 : m_nHeight( nHeight )
54 , m_nVersion( version )
55 , m_pParent( pParent )
60 atomics::atomic<node_type *>& child( int nDirection )
62 assert( nDirection != 0 );
63 return nDirection < 0 ? m_pLeft : m_pRight;
66 void child( node_type * pChild, int nDirection, atomics::memory_order order )
68 assert( nDirection != 0 );
70 m_pLeft.store( pChild, order );
72 m_pRight.store( pChild, order );
75 version_type version( atomics::memory_order order ) const
77 return m_nVersion.load( order );
80 void version( version_type ver, atomics::memory_order order )
82 m_nVersion.store( ver, order );
85 int height( atomics::memory_order order ) const
87 return m_nHeight.load( order );
90 void height( int h, atomics::memory_order order )
92 m_nHeight.store( h, order );
95 template <typename BackOff>
96 void wait_until_shrink_completed( atomics::memory_order order ) const
99 while ( is_shrinking( order ) )
103 bool is_unlinked( atomics::memory_order order ) const
105 return m_nVersion.load( order ) == unlinked;
108 bool is_shrinking( atomics::memory_order order ) const
110 return (m_nVersion.load( order ) & shrinking) != 0;
116 // BronsonAVLTree internal node
117 template <typename Key, typename T, typename SyncMonitor >
118 struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, SyncMonitor >
120 typedef link_node< node<Key, T*, SyncMonitor>, SyncMonitor > base_class;
122 typedef Key key_type; ///< key type
123 typedef T mapped_type; ///< value type
124 typedef typename base_class::version_type version_type;
126 key_type const m_key; ///< Key
127 atomics::atomic<mapped_type *> m_pValue; ///< Value
128 node * m_pNextRemoved; ///< thread-local list of removed node
132 template <typename Q>
135 , m_key( std::forward<Q>( key ) )
136 , m_pValue( nullptr )
137 , m_pNextRemoved( nullptr )
140 template <typename Q>
141 node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
142 : base_class( nHeight, version, pParent, pLeft, pRight )
143 , m_key( std::forward<Q>( key ) )
144 , m_pValue( nullptr )
145 , m_pNextRemoved( nullptr )
147 T * value( atomics::memory_order order ) const
149 return m_pValue.load( order );
152 bool is_valued( atomics::memory_order order ) const
154 return value( order ) != nullptr;
159 /// BronsonAVLTreeMap internal statistics
160 template <typename Counter = cds::atomicity::event_counter>
162 typedef Counter event_counter; ///< Event counter type
164 event_counter m_nFindSuccess; ///< Count of success \p find() call
165 event_counter m_nFindFailed; ///< Count of failed \p find() call
166 event_counter m_nFindRetry; ///< Count of retries during \p find()
167 event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
169 event_counter m_nInsertSuccess; ///< Count of inserting data node
170 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
171 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
172 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed duting \p update() call
173 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
174 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
175 event_counter m_nUpdateSuccess; ///< Count of updating data node
176 event_counter m_nUpdateUnlinked; ///< Count of updating of unlinked node attempts
177 event_counter m_nDisposedNode; ///< Count of disposed node
178 event_counter m_nDisposedValue; ///< Count of disposed value
179 event_counter m_nExtractedValue; ///< Count of extracted value
181 event_counter m_nRightRotation; ///< Count of single right rotation
182 event_counter m_nLeftRotation; ///< Count of single left rotation
183 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
184 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
187 void onFindSuccess() { ++m_nFindSuccess ; }
188 void onFindFailed() { ++m_nFindFailed ; }
189 void onFindRetry() { ++m_nFindRetry ; }
190 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
192 void onInsertSuccess() { ++m_nInsertSuccess ; }
193 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
194 void onInsertRetry() { ++m_nInsertRetry ; }
195 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
196 void onUpdateRetry() { ++m_nUpdateRetry; }
197 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
198 void onUpdateSuccess() { ++m_nUpdateSuccess; }
199 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
200 void onDisposeNode() { ++m_nDisposedNode; }
201 void onDisposeValue() { ++m_nDisposedValue; }
202 void onExtractValue() { ++m_nExtractedValue; }
204 void onRotateRight() { ++m_nRightRotation; }
205 void onRotateLeft() { ++m_nLeftRotation; }
206 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
207 void onRotateLeftOverRight() { ++m_nLeftRghtRotation; }
211 /// BronsonAVLTreeMap empty statistics
214 void onFindSuccess() const {}
215 void onFindFailed() const {}
216 void onFindRetry() const {}
217 void onFindWaitShrinking() const {}
219 void onInsertSuccess() const {}
220 void onRelaxedInsertFailed() const {}
221 void onInsertRetry() const {}
222 void onUpdateWaitShrinking() const {}
223 void onUpdateRetry() const {}
224 void onUpdateRootWaitShrinking() const {}
225 void onUpdateSuccess() const {}
226 void onUpdateUnlinked() const {}
227 void onDisposeNode() const {}
228 void onDisposeValue() const {}
229 void onExtractValue() const {}
231 void onRotateRight() const {}
232 void onRotateLeft() const {}
233 void onRotateRightOverLeft() const {}
234 void onRotateLeftOverRight() const {}
238 /// Option to allow relaxed insert into Bronson et al AVL-tree
240 By default, this opton is disabled and the new node is created under its parent lock.
241 In this case, it is guaranteed the new node will be attached to its parent.
242 On the other hand, constructing of the new node can be too complex to make it under the lock,
243 that can lead to lock contention.
245 When this option is enabled, the new node is created before locking the parent node.
246 After that, the parent is locked and checked whether the new node can be attached to the parent.
247 In this case, false node creating can be performed, but locked section can be significantly small.
249 template <bool Enable>
250 struct relaxed_insert {
252 template <typename Base> struct pack : public Base
254 enum { relaxed_insert = Enable };
259 /// BronsnAVLTreeMap traits
261 Note that there are two main specialization of Bronson et al AVL-tree:
262 - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
263 - 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.
265 Depends on tree specialization, different traits member can be used.
269 /// Key comparison functor
271 No default functor is provided. If the option is not specified, the \p less is used.
273 See \p cds::opt::compare option description for functor interface.
275 You should provide \p compare or \p less functor.
277 typedef opt::none compare;
279 /// Specifies binary predicate used for key compare.
281 See \p cds::opt::less option description for predicate interface.
283 You should provide \p compare or \p less functor.
285 typedef opt::none less;
287 /// Allocator for internal node
288 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
290 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
291 typedef CDS_DEFAULT_ALLOCATOR allocator;
293 /// Disposer (only for pointer-oriented tree specialization)
295 The functor used for dispose removed values.
296 The user-provided disposer is used only for pointer-oriented tree specialization
297 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
298 the disposer will be called to signal that the memory for the value can be safely freed.
299 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
301 typedef opt::v::delete_disposer<> disposer;
303 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
304 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
306 /// Enable relaxed insertion.
308 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
309 By default, this option is disabled.
311 static bool const relaxed_insert = false;
315 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
316 To enable it use \p atomicity::item_counter
318 typedef atomicity::empty_item_counter item_counter;
320 /// C++ memory ordering model
322 List of available memory ordering see \p opt::memory_model
324 typedef opt::v::relaxed_ordering memory_model;
326 /// Internal statistics
328 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
329 To enable it use \p ellen_bintree::stat.
331 typedef empty_stat stat;
333 /// Back-off strategy
334 typedef cds::backoff::empty back_off;
336 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
338 List of available options see \p opt::rcu_check_deadlock
340 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
343 /// Metafunction converting option list to BronsonAVLTreeMap traits
345 Note that there are two main specialization of Bronson et al AVL-tree:
346 - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
347 - 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.
349 Depends on tree specialization, different options can be specified.
352 - \p opt::compare - key compare functor. No default functor is provided.
353 If the option is not specified, \p %opt::less is used.
354 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
355 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
356 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
357 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
358 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
359 The user-provided disposer is used only for pointer-oriented tree specialization
360 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
361 the disposer will be called to signal that the memory for the value can be safely freed.
362 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
363 Due the nature of GC schema the disposer may be called asynchronously.
364 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
365 default is \p cds::sync::injecting_monitor<cds::sync::spin>
366 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
367 @ref bronson_avltree::relaxed_insert "relaxed insertion"
368 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
369 To enable it use \p atomicity::item_counter
370 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
371 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
372 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
373 To enable statistics use \p \p bronson_avltree::stat
374 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
375 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
377 template <typename... Options>
379 # ifdef CDS_DOXYGEN_INVOKED
380 typedef implementation_defined type ; ///< Metafunction result
382 typedef typename cds::opt::make_options<
383 typename cds::opt::find_type_traits< traits, Options... >::type
388 } // namespace bronson_avltree
391 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
392 class BronsonAVLTreeMap;
394 }} // namespace cds::container
397 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H