2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
32 #define CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
34 #include <cds/container/details/base.h>
35 #include <cds/opt/compare.h>
36 #include <cds/urcu/options.h>
37 #include <cds/sync/spinlock.h>
38 #include <cds/sync/injecting_monitor.h>
40 namespace cds { namespace container {
42 /// BronsonAVLTree related declarations
43 namespace bronson_avltree {
45 template <typename Key, typename T, typename SyncMonitor >
49 template <typename Node, typename T, typename SyncMonitor>
52 typedef Node node_type;
53 typedef T mapped_type;
54 typedef uint32_t version_type; ///< version type (internal)
60 version_flags = shrinking | unlinked
61 // the rest is version counter
64 atomics::atomic< int > m_nHeight; ///< Node height
65 atomics::atomic<version_type> m_nVersion; ///< Version bits
66 atomics::atomic<node_type *> m_pParent; ///< Parent node
67 atomics::atomic<node_type *> m_pLeft; ///< Left child
68 atomics::atomic<node_type *> m_pRight; ///< Right child
69 typename SyncMonitor::node_injection m_SyncMonitorInjection; ///< @ref cds_sync_monitor "synchronization monitor" injected data
70 atomics::atomic<mapped_type *> m_pValue; ///< Value
76 , m_pParent( nullptr )
80 m_pValue.store( nullptr, atomics::memory_order_release );
83 link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
84 : m_nHeight( nHeight )
85 , m_nVersion( version )
86 , m_pParent( pParent )
90 m_pValue.store( nullptr, atomics::memory_order_release );
93 node_type * parent( atomics::memory_order order ) const
95 return m_pParent.load( order );
98 void parent( node_type * p, atomics::memory_order order )
100 m_pParent.store( p, order );
103 node_type * child( int nDirection, atomics::memory_order order ) const
105 assert( nDirection != 0 );
106 return nDirection < 0 ? m_pLeft.load( order ) : m_pRight.load( order );
109 void child( node_type * pChild, int nDirection, atomics::memory_order order )
111 assert( nDirection != 0 );
112 if ( nDirection < 0 )
113 m_pLeft.store( pChild, order );
115 m_pRight.store( pChild, order );
118 version_type version( atomics::memory_order order ) const
120 return m_nVersion.load( order );
123 void version( version_type ver, atomics::memory_order order )
125 m_nVersion.store( ver, order );
128 void exchange_version( version_type ver, atomics::memory_order order )
130 m_nVersion.exchange( ver, order );
133 int height( atomics::memory_order order ) const
135 return m_nHeight.load( order );
138 void height( int h, atomics::memory_order order )
140 m_nHeight.store( h, order );
143 template <typename BackOff>
144 void wait_until_shrink_completed( atomics::memory_order order ) const
147 while ( is_shrinking( order ))
151 bool is_unlinked( atomics::memory_order order ) const
153 return m_nVersion.load( order ) == unlinked;
156 bool is_shrinking( atomics::memory_order order ) const
158 return (m_nVersion.load( order ) & shrinking) != 0;
161 mapped_type * value( atomics::memory_order order ) const
163 return m_pValue.load( order );
166 bool is_valued( atomics::memory_order order ) const
168 return value( order ) != nullptr;
173 /// BronsonAVLTree internal node
174 template <typename Key, typename T, typename SyncMonitor >
175 struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
178 typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
181 typedef Key key_type; ///< key type
182 typedef T mapped_type; ///< value type
184 typedef typename base_class::version_type version_type;
187 key_type const m_key; ///< Key
188 node * m_pNextRemoved; ///< thread-local list of removed node
192 template <typename Q>
195 , m_key( std::forward<Q>( key ))
196 , m_pNextRemoved( nullptr )
199 template <typename Q>
200 node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
201 : base_class( nHeight, version, pParent, pLeft, pRight )
202 , m_key( std::forward<Q>( key ))
203 , m_pNextRemoved( nullptr )
208 /// BronsonAVLTreeMap internal statistics
209 template <typename Counter = cds::atomicity::event_counter>
211 typedef Counter event_counter; ///< Event counter type
213 event_counter m_nFindSuccess; ///< Count of success \p find() call
214 event_counter m_nFindFailed; ///< Count of failed \p find() call
215 event_counter m_nFindRetry; ///< Count of retries during \p find()
216 event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
218 event_counter m_nInsertSuccess; ///< Count of inserting data node
219 event_counter m_nInsertFailed; ///< Count of insert failures
220 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
221 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
222 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
223 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
224 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
225 event_counter m_nUpdateSuccess; ///< Count of updating data node
226 event_counter m_nUpdateUnlinked; ///< Count of attempts to update unlinked node
227 event_counter m_nDisposedNode; ///< Count of disposed node
228 event_counter m_nDisposedValue; ///< Count of disposed value
229 event_counter m_nExtractedValue; ///< Count of extracted value
230 event_counter m_nRemoveSuccess; ///< Count of successfully \p erase() call
231 event_counter m_nRemoveFailed; ///< Count of failed \p erase() call
232 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
233 event_counter m_nExtractSuccess; ///< Count of successfully \p extract() call
234 event_counter m_nExtractFailed; ///< Count of failed \p extract() call
235 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
236 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
237 event_counter m_nMakeRoutingNode; ///< How many nodes were converted to routing (valueless) nodes
239 event_counter m_nRightRotation; ///< Count of single right rotation
240 event_counter m_nLeftRotation; ///< Count of single left rotation
241 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
242 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
244 event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
245 event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
246 event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
248 event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation
249 event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation
250 event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation
252 event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation
253 event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation
254 event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation
255 event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation
257 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
258 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
261 void onFindSuccess() { ++m_nFindSuccess ; }
262 void onFindFailed() { ++m_nFindFailed ; }
263 void onFindRetry() { ++m_nFindRetry ; }
264 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
266 void onInsertSuccess() { ++m_nInsertSuccess; }
267 void onInsertFailed() { ++m_nInsertFailed; }
268 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
269 void onInsertRetry() { ++m_nInsertRetry ; }
270 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
271 void onUpdateRetry() { ++m_nUpdateRetry; }
272 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
273 void onUpdateSuccess() { ++m_nUpdateSuccess; }
274 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
275 void onDisposeNode() { ++m_nDisposedNode; }
276 void onDisposeValue() { ++m_nDisposedValue; }
277 void onExtractValue() { ++m_nExtractedValue; }
278 void onRemove(bool bSuccess)
285 void onExtract( bool bSuccess )
292 void onRemoveRetry() { ++m_nRemoveRetry; }
293 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
294 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
295 void onMakeRoutingNode() { ++m_nMakeRoutingNode; }
297 void onRotateRight() { ++m_nRightRotation; }
298 void onRotateLeft() { ++m_nLeftRotation; }
299 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
300 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
302 void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
303 void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
304 void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
306 void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; }
307 void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; }
308 void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; }
310 void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; }
311 void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; }
312 void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; }
313 void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; }
315 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
316 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
320 /// BronsonAVLTreeMap empty statistics
323 void onFindSuccess() const {}
324 void onFindFailed() const {}
325 void onFindRetry() const {}
326 void onFindWaitShrinking() const {}
328 void onInsertSuccess() const {}
329 void onInsertFailed() const {}
330 void onRelaxedInsertFailed() const {}
331 void onInsertRetry() const {}
332 void onUpdateWaitShrinking() const {}
333 void onUpdateRetry() const {}
334 void onUpdateRootWaitShrinking() const {}
335 void onUpdateSuccess() const {}
336 void onUpdateUnlinked() const {}
337 void onDisposeNode() const {}
338 void onDisposeValue() const {}
339 void onExtractValue() const {}
340 void onRemove(bool /*bSuccess*/) const {}
341 void onExtract(bool /*bSuccess*/) const {}
342 void onRemoveRetry() const {}
343 void onRemoveWaitShrinking() const {}
344 void onRemoveRootWaitShrinking() const {}
345 void onMakeRoutingNode() const {}
347 void onRotateRight() const {}
348 void onRotateLeft() const {}
349 void onRotateRightOverLeft() const {}
350 void onRotateLeftOverRight() const {}
352 void onRotateAfterRightRotation() const {}
353 void onRemoveAfterRightRotation() const {}
354 void onDamageAfterRightRotation() const {}
356 void onRotateAfterLeftRotation() const {}
357 void onRemoveAfterLeftRotation() const {}
358 void onDamageAfterLeftRotation() const {}
360 void onRotateAfterRLRotation() const {}
361 void onRemoveAfterRLRotation() const {}
362 void onRotateAfterLRRotation() const {}
363 void onRemoveAfterLRRotation() const {}
365 void onInsertRebalanceRequired() const {}
366 void onRemoveRebalanceRequired() const {}
370 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
372 By default, this option is disabled and the new node is created under its parent lock.
373 In this case, it is guaranteed the new node will be attached to its parent.
374 On the other hand, constructing of the new node can be too complex to make it under the lock,
375 that can lead to lock contention.
377 When this option is enabled, the new node is created before locking the parent node.
378 After that, the parent is locked and checked whether the new node can be attached to the parent.
379 In this case, false node creating can be performed, but locked section can be significantly small.
381 template <bool Enable>
382 struct relaxed_insert {
384 template <typename Base> struct pack : public Base
386 enum { relaxed_insert = Enable };
391 /// \p BronsonAVLTreeMap traits
393 Note that there are two main specialization of Bronson et al AVL-tree:
394 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
395 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
397 Depends on tree specialization, different traits member can be used.
401 /// Key comparison functor
403 No default functor is provided. If the option is not specified, the \p less is used.
405 See \p cds::opt::compare option description for functor interface.
407 You should provide \p compare or \p less functor.
409 typedef opt::none compare;
411 /// Specifies binary predicate used for key compare.
413 See \p cds::opt::less option description for predicate interface.
415 You should provide \p compare or \p less functor.
417 typedef opt::none less;
419 /// Allocator for internal node
420 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
422 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
423 typedef CDS_DEFAULT_ALLOCATOR allocator;
425 /// Disposer (only for pointer-oriented tree specialization)
427 The functor used for dispose removed values.
428 The user-provided disposer is used only for pointer-oriented tree specialization
429 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
430 the disposer will be called to signal that the memory for the value can be safely freed.
431 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
433 typedef opt::v::delete_disposer<> disposer;
435 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
436 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
438 /// Enable relaxed insertion.
440 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
441 By default, this option is disabled.
443 static bool const relaxed_insert = false;
447 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
448 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter.
450 typedef atomicity::empty_item_counter item_counter;
452 /// C++ memory ordering model
454 List of available memory ordering see \p opt::memory_model
456 typedef opt::v::relaxed_ordering memory_model;
458 /// Internal statistics
460 By default, internal statistics is disabled (\p bronson_avltree::empty_stat).
461 To enable it use \p bronson_avltree::stat.
463 typedef empty_stat stat;
465 /// Back-off strategy
466 typedef cds::backoff::empty back_off;
468 /// RCU deadlock checking policy
470 List of available options see \p opt::rcu_check_deadlock
472 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
475 /// Metafunction converting option list to BronsonAVLTreeMap traits
477 Note that there are two main specialization of Bronson et al AVL-tree:
478 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
479 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
481 Depends on tree specialization, different options can be specified.
484 - \p opt::compare - key compare functor. No default functor is provided.
485 If the option is not specified, \p %opt::less is used.
486 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
487 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
488 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
489 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
490 - \p cds::intrusive::opt::disposer - the functor used for dispose removed values.
491 The user-provided disposer is used only for pointer-oriented tree specialization
492 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
493 the disposer will be called to signal that the memory for the value can be safely freed.
494 Default is \p cds::intrusive::opt::delete_disposer which calls \p delete operator.
495 Due the nature of GC schema the disposer may be called asynchronously.
496 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
497 default is \p cds::sync::injecting_monitor<cds::sync::spin>
498 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
499 @ref bronson_avltree::relaxed_insert "relaxed insertion"
500 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
501 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
502 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
503 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
504 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
505 To enable statistics use \p \p bronson_avltree::stat
506 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
507 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
509 template <typename... Options>
511 # ifdef CDS_DOXYGEN_INVOKED
512 typedef implementation_defined type ; ///< Metafunction result
514 typedef typename cds::opt::make_options<
515 typename cds::opt::find_type_traits< traits, Options... >::type
520 } // namespace bronson_avltree
523 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
524 class BronsonAVLTreeMap;
526 }} // namespace cds::container
528 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H