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