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_nFindNotFoundRetry; ///< Count of ???
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
194 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
195 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
198 void onFindSuccess() { ++m_nFindSuccess ; }
199 void onFindFailed() { ++m_nFindFailed ; }
200 void onFindRetry() { ++m_nFindRetry ; }
201 void onFindNotFoundRetry() { ++m_nFindNotFoundRetry; }
202 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
204 void onInsertSuccess() { ++m_nInsertSuccess ; }
205 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
206 void onInsertRetry() { ++m_nInsertRetry ; }
207 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
208 void onUpdateRetry() { ++m_nUpdateRetry; }
209 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
210 void onUpdateSuccess() { ++m_nUpdateSuccess; }
211 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
212 void onDisposeNode() { ++m_nDisposedNode; }
213 void onDisposeValue() { ++m_nDisposedValue; }
214 void onExtractValue() { ++m_nExtractedValue; }
215 void onRemoveRetry() { ++m_nRemoveRetry; }
216 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
217 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
219 void onRotateRight() { ++m_nRightRotation; }
220 void onRotateLeft() { ++m_nLeftRotation; }
221 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
222 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
224 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
225 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
229 /// BronsonAVLTreeMap empty statistics
232 void onFindSuccess() const {}
233 void onFindFailed() const {}
234 void onFindRetry() const {}
235 void onFindNotFoundRetry() const {}
236 void onFindWaitShrinking() const {}
238 void onInsertSuccess() const {}
239 void onRelaxedInsertFailed() const {}
240 void onInsertRetry() const {}
241 void onUpdateWaitShrinking() const {}
242 void onUpdateRetry() const {}
243 void onUpdateRootWaitShrinking() const {}
244 void onUpdateSuccess() const {}
245 void onUpdateUnlinked() const {}
246 void onDisposeNode() const {}
247 void onDisposeValue() const {}
248 void onExtractValue() const {}
249 void onRemoveRetry() const {}
250 void onRemoveWaitShrinking() const {}
251 void onRemoveRootWaitShrinking() const {}
253 void onRotateRight() const {}
254 void onRotateLeft() const {}
255 void onRotateRightOverLeft() const {}
256 void onRotateLeftOverRight() const {}
258 void onInsertRebalanceRequired() const {}
259 void onRemoveRebalanceRequired() const {}
263 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
265 By default, this option is disabled and the new node is created under its parent lock.
266 In this case, it is guaranteed the new node will be attached to its parent.
267 On the other hand, constructing of the new node can be too complex to make it under the lock,
268 that can lead to lock contention.
270 When this option is enabled, the new node is created before locking the parent node.
271 After that, the parent is locked and checked whether the new node may be attached to the parent.
272 In this case, false node creating can be performed, but locked section can be significantly small.
274 template <bool Enable>
275 struct relaxed_insert {
277 template <typename Base> struct pack : public Base
279 enum { relaxed_insert = Enable };
284 /// \p BronsonAVLTreeMap traits
286 Note that there are two main specialization of Bronson et al AVL-tree:
287 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
288 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
290 Depends on tree specialization, different traits member can be used.
294 /// Key comparison functor
296 No default functor is provided. If the option is not specified, the \p less is used.
298 See \p cds::opt::compare option description for functor interface.
300 You should provide \p compare or \p less functor.
302 typedef opt::none compare;
304 /// Specifies binary predicate used for key compare.
306 See \p cds::opt::less option description for predicate interface.
308 You should provide \p compare or \p less functor.
310 typedef opt::none less;
312 /// Allocator for internal node
313 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
315 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
316 typedef CDS_DEFAULT_ALLOCATOR allocator;
318 /// Disposer (only for pointer-oriented tree specialization)
320 The functor used for dispose removed values.
321 The user-provided disposer is used only for pointer-oriented tree specialization
322 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
323 the disposer will be called to signal that the memory for the value can be safely freed.
324 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
326 typedef opt::v::delete_disposer<> disposer;
328 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
329 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
331 /// Enable relaxed insertion.
333 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
334 By default, this option is disabled.
336 static bool const relaxed_insert = false;
340 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
341 To enable it use \p atomicity::item_counter
343 typedef atomicity::empty_item_counter item_counter;
345 /// C++ memory ordering model
347 List of available memory ordering see \p opt::memory_model
349 typedef opt::v::relaxed_ordering memory_model;
351 /// Internal statistics
353 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
354 To enable it use \p ellen_bintree::stat.
356 typedef empty_stat stat;
358 /// Back-off strategy
359 typedef cds::backoff::empty back_off;
361 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
363 List of available options see \p opt::rcu_check_deadlock
365 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
368 /// Metafunction converting option list to BronsonAVLTreeMap traits
370 Note that there are two main specialization of Bronson et al AVL-tree:
371 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
372 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
374 Depends on tree specialization, different options can be specified.
377 - \p opt::compare - key compare functor. No default functor is provided.
378 If the option is not specified, \p %opt::less is used.
379 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
380 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
381 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
382 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
383 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
384 The user-provided disposer is used only for pointer-oriented tree specialization
385 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
386 the disposer will be called to signal that the memory for the value can be safely freed.
387 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
388 Due the nature of GC schema the disposer may be called asynchronously.
389 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
390 default is \p cds::sync::injecting_monitor<cds::sync::spin>
391 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
392 @ref bronson_avltree::relaxed_insert "relaxed insertion"
393 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
394 To enable it use \p atomicity::item_counter
395 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
396 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
397 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
398 To enable statistics use \p \p bronson_avltree::stat
399 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
400 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
402 template <typename... Options>
404 # ifdef CDS_DOXYGEN_INVOKED
405 typedef implementation_defined type ; ///< Metafunction result
407 typedef typename cds::opt::make_options<
408 typename cds::opt::find_type_traits< traits, Options... >::type
413 } // namespace bronson_avltree
416 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
417 class BronsonAVLTreeMap;
419 }} // namespace cds::container
422 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H