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 int height( atomics::memory_order order ) const
130 return m_nHeight.load( order );
133 void height( int h, atomics::memory_order order )
135 m_nHeight.store( h, order );
138 template <typename BackOff>
139 void wait_until_shrink_completed( atomics::memory_order order ) const
142 while ( is_shrinking( order ))
146 bool is_unlinked( atomics::memory_order order ) const
148 return m_nVersion.load( order ) == unlinked;
151 bool is_shrinking( atomics::memory_order order ) const
153 return (m_nVersion.load( order ) & shrinking) != 0;
156 mapped_type * value( atomics::memory_order order ) const
158 return m_pValue.load( order );
161 bool is_valued( atomics::memory_order order ) const
163 return value( order ) != nullptr;
168 /// BronsonAVLTree internal node
169 template <typename Key, typename T, typename SyncMonitor >
170 struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
173 typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
176 typedef Key key_type; ///< key type
177 typedef T mapped_type; ///< value type
179 typedef typename base_class::version_type version_type;
182 key_type const m_key; ///< Key
183 node * m_pNextRemoved; ///< thread-local list of removed node
187 template <typename Q>
190 , m_key( std::forward<Q>( key ))
191 , m_pNextRemoved( nullptr )
194 template <typename Q>
195 node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
196 : base_class( nHeight, version, pParent, pLeft, pRight )
197 , m_key( std::forward<Q>( key ))
198 , m_pNextRemoved( nullptr )
203 /// BronsonAVLTreeMap internal statistics
204 template <typename Counter = cds::atomicity::event_counter>
206 typedef Counter event_counter; ///< Event counter type
208 event_counter m_nFindSuccess; ///< Count of success \p find() call
209 event_counter m_nFindFailed; ///< Count of failed \p find() call
210 event_counter m_nFindRetry; ///< Count of retries during \p find()
211 event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
213 event_counter m_nInsertSuccess; ///< Count of inserting data node
214 event_counter m_nInsertFailed; ///< Count of insert failures
215 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
216 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
217 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
218 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
219 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
220 event_counter m_nUpdateSuccess; ///< Count of updating data node
221 event_counter m_nUpdateUnlinked; ///< Count of attempts to update unlinked node
222 event_counter m_nDisposedNode; ///< Count of disposed node
223 event_counter m_nDisposedValue; ///< Count of disposed value
224 event_counter m_nExtractedValue; ///< Count of extracted value
225 event_counter m_nRemoveSuccess; ///< Count of successfully \p erase() call
226 event_counter m_nRemoveFailed; ///< Count of failed \p erase() call
227 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
228 event_counter m_nExtractSuccess; ///< Count of successfully \p extract() call
229 event_counter m_nExtractFailed; ///< Count of failed \p extract() call
230 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
231 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
232 event_counter m_nMakeRoutingNode; ///< How many nodes were converted to routing (valueless) nodes
234 event_counter m_nRightRotation; ///< Count of single right rotation
235 event_counter m_nLeftRotation; ///< Count of single left rotation
236 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
237 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
239 event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
240 event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
241 event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
243 event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation
244 event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation
245 event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation
247 event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation
248 event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation
249 event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation
250 event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation
252 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
253 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
256 void onFindSuccess() { ++m_nFindSuccess ; }
257 void onFindFailed() { ++m_nFindFailed ; }
258 void onFindRetry() { ++m_nFindRetry ; }
259 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
261 void onInsertSuccess() { ++m_nInsertSuccess; }
262 void onInsertFailed() { ++m_nInsertFailed; }
263 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
264 void onInsertRetry() { ++m_nInsertRetry ; }
265 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
266 void onUpdateRetry() { ++m_nUpdateRetry; }
267 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
268 void onUpdateSuccess() { ++m_nUpdateSuccess; }
269 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
270 void onDisposeNode() { ++m_nDisposedNode; }
271 void onDisposeValue() { ++m_nDisposedValue; }
272 void onExtractValue() { ++m_nExtractedValue; }
273 void onRemove(bool bSuccess)
280 void onExtract( bool bSuccess )
287 void onRemoveRetry() { ++m_nRemoveRetry; }
288 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
289 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
290 void onMakeRoutingNode() { ++m_nMakeRoutingNode; }
292 void onRotateRight() { ++m_nRightRotation; }
293 void onRotateLeft() { ++m_nLeftRotation; }
294 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
295 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
297 void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
298 void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
299 void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
301 void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; }
302 void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; }
303 void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; }
305 void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; }
306 void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; }
307 void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; }
308 void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; }
310 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
311 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
315 /// BronsonAVLTreeMap empty statistics
318 void onFindSuccess() const {}
319 void onFindFailed() const {}
320 void onFindRetry() const {}
321 void onFindWaitShrinking() const {}
323 void onInsertSuccess() const {}
324 void onInsertFailed() const {}
325 void onRelaxedInsertFailed() const {}
326 void onInsertRetry() const {}
327 void onUpdateWaitShrinking() const {}
328 void onUpdateRetry() const {}
329 void onUpdateRootWaitShrinking() const {}
330 void onUpdateSuccess() const {}
331 void onUpdateUnlinked() const {}
332 void onDisposeNode() const {}
333 void onDisposeValue() const {}
334 void onExtractValue() const {}
335 void onRemove(bool /*bSuccess*/) const {}
336 void onExtract(bool /*bSuccess*/) const {}
337 void onRemoveRetry() const {}
338 void onRemoveWaitShrinking() const {}
339 void onRemoveRootWaitShrinking() const {}
340 void onMakeRoutingNode() const {}
342 void onRotateRight() const {}
343 void onRotateLeft() const {}
344 void onRotateRightOverLeft() const {}
345 void onRotateLeftOverRight() const {}
347 void onRotateAfterRightRotation() const {}
348 void onRemoveAfterRightRotation() const {}
349 void onDamageAfterRightRotation() const {}
351 void onRotateAfterLeftRotation() const {}
352 void onRemoveAfterLeftRotation() const {}
353 void onDamageAfterLeftRotation() const {}
355 void onRotateAfterRLRotation() const {}
356 void onRemoveAfterRLRotation() const {}
357 void onRotateAfterLRRotation() const {}
358 void onRemoveAfterLRRotation() const {}
360 void onInsertRebalanceRequired() const {}
361 void onRemoveRebalanceRequired() const {}
365 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
367 By default, this option is disabled and the new node is created under its parent lock.
368 In this case, it is guaranteed the new node will be attached to its parent.
369 On the other hand, constructing of the new node can be too complex to make it under the lock,
370 that can lead to lock contention.
372 When this option is enabled, the new node is created before locking the parent node.
373 After that, the parent is locked and checked whether the new node can be attached to the parent.
374 In this case, false node creating can be performed, but locked section can be significantly small.
376 template <bool Enable>
377 struct relaxed_insert {
379 template <typename Base> struct pack : public Base
381 enum { relaxed_insert = Enable };
386 /// \p BronsonAVLTreeMap traits
388 Note that there are two main specialization of Bronson et al AVL-tree:
389 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
390 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
392 Depends on tree specialization, different traits member can be used.
396 /// Key comparison functor
398 No default functor is provided. If the option is not specified, the \p less is used.
400 See \p cds::opt::compare option description for functor interface.
402 You should provide \p compare or \p less functor.
404 typedef opt::none compare;
406 /// Specifies binary predicate used for key compare.
408 See \p cds::opt::less option description for predicate interface.
410 You should provide \p compare or \p less functor.
412 typedef opt::none less;
414 /// Allocator for internal node
415 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
417 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
418 typedef CDS_DEFAULT_ALLOCATOR allocator;
420 /// Disposer (only for pointer-oriented tree specialization)
422 The functor used for dispose removed values.
423 The user-provided disposer is used only for pointer-oriented tree specialization
424 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
425 the disposer will be called to signal that the memory for the value can be safely freed.
426 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
428 typedef opt::v::delete_disposer<> disposer;
430 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
431 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
433 /// Enable relaxed insertion.
435 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
436 By default, this option is disabled.
438 static bool const relaxed_insert = false;
442 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
443 To enable it use \p atomicity::item_counter
445 typedef atomicity::empty_item_counter item_counter;
447 /// C++ memory ordering model
449 List of available memory ordering see \p opt::memory_model
451 typedef opt::v::relaxed_ordering memory_model;
453 /// Internal statistics
455 By default, internal statistics is disabled (\p bronson_avltree::empty_stat).
456 To enable it use \p bronson_avltree::stat.
458 typedef empty_stat stat;
460 /// Back-off strategy
461 typedef cds::backoff::empty back_off;
463 /// RCU deadlock checking policy
465 List of available options see \p opt::rcu_check_deadlock
467 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
470 /// Metafunction converting option list to BronsonAVLTreeMap traits
472 Note that there are two main specialization of Bronson et al AVL-tree:
473 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
474 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
476 Depends on tree specialization, different options can be specified.
479 - \p opt::compare - key compare functor. No default functor is provided.
480 If the option is not specified, \p %opt::less is used.
481 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
482 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
483 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
484 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
485 - \p cds::intrusive::opt::disposer - the functor used for dispose removed values.
486 The user-provided disposer is used only for pointer-oriented tree specialization
487 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
488 the disposer will be called to signal that the memory for the value can be safely freed.
489 Default is \p cds::intrusive::opt::delete_disposer which calls \p delete operator.
490 Due the nature of GC schema the disposer may be called asynchronously.
491 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
492 default is \p cds::sync::injecting_monitor<cds::sync::spin>
493 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
494 @ref bronson_avltree::relaxed_insert "relaxed insertion"
495 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
496 To enable it use \p atomicity::item_counter
497 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
498 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
499 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
500 To enable statistics use \p \p bronson_avltree::stat
501 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
502 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
504 template <typename... Options>
506 # ifdef CDS_DOXYGEN_INVOKED
507 typedef implementation_defined type ; ///< Metafunction result
509 typedef typename cds::opt::make_options<
510 typename cds::opt::find_type_traits< traits, Options... >::type
515 } // namespace bronson_avltree
518 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
519 class BronsonAVLTreeMap;
521 }} // namespace cds::container
523 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H