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
180 void onFindSuccess() { ++m_nFindSuccess ; }
181 void onFindFailed() { ++m_nFindFailed ; }
182 void onFindRetry() { ++m_nFindRetry ; }
183 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
185 void onInsertSuccess() { ++m_nInsertSuccess ; }
186 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
187 void onInsertRetry() { ++m_nInsertRetry ; }
188 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
189 void onUpdateRetry() { ++m_nUpdateRetry; }
190 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
191 void onUpdateSuccess() { ++m_nUpdateSuccess; }
192 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
193 void onDisposeNode() { ++m_nDisposedNode; }
198 /// BronsonAVLTreeMap empty statistics
201 void onFindSuccess() const {}
202 void onFindFailed() const {}
203 void onFindRetry() const {}
204 void onFindWaitShrinking() const {}
206 void onInsertSuccess() const {}
207 void onRelaxedInsertFailed() const {}
208 void onInsertRetry() const {}
209 void onUpdateWaitShrinking() const {}
210 void onUpdateRetry() const {}
211 void onUpdateRootWaitShrinking() const {}
212 void onUpdateSuccess() const {}
213 void onUpdateUnlinked() const {}
214 void onDisposeNode() const {}
219 /// Option to allow relaxed insert into Bronson et al AVL-tree
221 By default, this opton is disabled and the new node is created under its parent lock.
222 In this case, it is guaranteed the new node will be attached to its parent.
223 On the other hand, constructing of the new node can be too complex to make it under the lock,
224 that can lead to lock contention.
226 When this option is enabled, the new node is created before locking the parent node.
227 After that, the parent is locked and checked whether the new node can be attached to the parent.
228 In this case, false node creating can be performed, but locked section can be significantly small.
230 template <bool Enable>
231 struct relaxed_insert {
233 template <typename Base> struct pack : public Base
235 enum { relaxed_insert = Enable };
240 /// BronsnAVLTreeMap traits
242 Note that there are two main specialization of Bronson et al AVL-tree:
243 - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
244 - 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.
246 Depends on tree specialization, different traits member can be used.
250 /// Key comparison functor
252 No default functor is provided. If the option is not specified, the \p less is used.
254 See \p cds::opt::compare option description for functor interface.
256 You should provide \p compare or \p less functor.
258 typedef opt::none compare;
260 /// Specifies binary predicate used for key compare.
262 See \p cds::opt::less option description for predicate interface.
264 You should provide \p compare or \p less functor.
266 typedef opt::none less;
268 /// Allocator for internal node
269 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
271 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
272 typedef CDS_DEFAULT_ALLOCATOR allocator;
274 /// Disposer (only for pointer-oriented tree specialization)
276 The functor used for dispose removed values.
277 The user-provided disposer is used only for pointer-oriented tree specialization
278 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
279 the disposer will be called to signal that the memory for the value can be safely freed.
280 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
282 typedef opt::v::delete_disposer<> disposer;
284 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
285 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
287 /// Enable relaxed insertion.
289 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
290 By default, this option is disabled.
292 static bool const relaxed_insert = false;
296 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
297 To enable it use \p atomicity::item_counter
299 typedef atomicity::empty_item_counter item_counter;
301 /// C++ memory ordering model
303 List of available memory ordering see \p opt::memory_model
305 typedef opt::v::relaxed_ordering memory_model;
307 /// Internal statistics
309 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
310 To enable it use \p ellen_bintree::stat.
312 typedef empty_stat stat;
314 /// Back-off strategy
315 typedef cds::backoff::empty back_off;
317 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
319 List of available options see \p opt::rcu_check_deadlock
321 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
324 /// Metafunction converting option list to BronsonAVLTreeMap traits
326 Note that there are two main specialization of Bronson et al AVL-tree:
327 - pointer-oriented - the tree node stores an user-provided pointer to value: <tt>BronsonAVLTreeMap<GC, Key, T *, Traits> </tt>
328 - 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.
330 Depends on tree specialization, different options can be specified.
333 - \p opt::compare - key compare functor. No default functor is provided.
334 If the option is not specified, \p %opt::less is used.
335 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
336 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
337 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
338 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
339 - \ref cds::intrusive::opt::disposer "container::opt::disposer" - the functor used for dispose removed values.
340 The user-provided disposer is used only for pointer-oriented tree specialization
341 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
342 the disposer will be called to signal that the memory for the value can be safely freed.
343 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
344 Due the nature of GC schema the disposer may be called asynchronously.
345 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
346 default is \p cds::sync::injecting_monitor<cds::sync::spin>
347 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
348 @ref bronson_avltree::relaxed_insert "relaxed insertion"
349 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
350 To enable it use \p atomicity::item_counter
351 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
352 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
353 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
354 To enable statistics use \p \p bronson_avltree::stat
355 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
356 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
358 template <typename... Options>
360 # ifdef CDS_DOXYGEN_INVOKED
361 typedef implementation_defined type ; ///< Metafunction result
363 typedef typename cds::opt::make_options<
364 typename cds::opt::find_type_traits< traits, Options... >::type
369 } // namespace bronson_avltree
372 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
373 class BronsonAVLTreeMap;
375 }} // namespace cds::container
378 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H