2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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 )
82 link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
83 : m_nHeight( nHeight )
84 , m_nVersion( version )
85 , m_pParent( pParent )
91 node_type * parent( atomics::memory_order order ) const
93 return m_pParent.load( order );
96 void parent( node_type * p, atomics::memory_order order )
98 m_pParent.store( p, order );
101 node_type * child( int nDirection, atomics::memory_order order ) const
103 assert( nDirection != 0 );
104 return nDirection < 0 ? m_pLeft.load( order ) : m_pRight.load( order );
107 void child( node_type * pChild, int nDirection, atomics::memory_order order )
109 assert( nDirection != 0 );
110 if ( nDirection < 0 )
111 m_pLeft.store( pChild, order );
113 m_pRight.store( pChild, order );
116 version_type version( atomics::memory_order order ) const
118 return m_nVersion.load( order );
121 void version( version_type ver, atomics::memory_order order )
123 m_nVersion.store( ver, order );
126 int height( atomics::memory_order order ) const
128 return m_nHeight.load( order );
131 void height( int h, atomics::memory_order order )
133 m_nHeight.store( h, order );
136 template <typename BackOff>
137 void wait_until_shrink_completed( atomics::memory_order order ) const
140 while ( is_shrinking( order ) )
144 bool is_unlinked( atomics::memory_order order ) const
146 return m_nVersion.load( order ) == unlinked;
149 bool is_shrinking( atomics::memory_order order ) const
151 return (m_nVersion.load( order ) & shrinking) != 0;
154 mapped_type * value( atomics::memory_order order ) const
156 return m_pValue.load( order );
159 bool is_valued( atomics::memory_order order ) const
161 return value( order ) != nullptr;
166 /// BronsonAVLTree internal node
167 template <typename Key, typename T, typename SyncMonitor >
168 struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
171 typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
174 typedef Key key_type; ///< key type
175 typedef T mapped_type; ///< value type
177 typedef typename base_class::version_type version_type;
180 key_type const m_key; ///< Key
181 node * m_pNextRemoved; ///< thread-local list of removed node
185 template <typename Q>
188 , m_key( std::forward<Q>( key ) )
189 , m_pNextRemoved( nullptr )
192 template <typename Q>
193 node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
194 : base_class( nHeight, version, pParent, pLeft, pRight )
195 , m_key( std::forward<Q>( key ) )
196 , m_pNextRemoved( nullptr )
201 /// BronsonAVLTreeMap internal statistics
202 template <typename Counter = cds::atomicity::event_counter>
204 typedef Counter event_counter; ///< Event counter type
206 event_counter m_nFindSuccess; ///< Count of success \p find() call
207 event_counter m_nFindFailed; ///< Count of failed \p find() call
208 event_counter m_nFindRetry; ///< Count of retries during \p find()
209 event_counter m_nFindWaitShrinking; ///< Count of waiting until shrinking completed duting \p find() call
211 event_counter m_nInsertSuccess; ///< Count of inserting data node
212 event_counter m_nInsertFailed; ///< Count of insert failures
213 event_counter m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
214 event_counter m_nInsertRetry; ///< Count of insert retries via concurrent operations
215 event_counter m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
216 event_counter m_nUpdateRetry; ///< Count of update retries via concurrent operations
217 event_counter m_nUpdateRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p update() call
218 event_counter m_nUpdateSuccess; ///< Count of updating data node
219 event_counter m_nUpdateUnlinked; ///< Count of attempts to update unlinked node
220 event_counter m_nDisposedNode; ///< Count of disposed node
221 event_counter m_nDisposedValue; ///< Count of disposed value
222 event_counter m_nExtractedValue; ///< Count of extracted value
223 event_counter m_nRemoveSuccess; ///< Count of successfully \p erase() call
224 event_counter m_nRemoveFailed; ///< Count of failed \p erase() call
225 event_counter m_nRemoveRetry; ///< Count o erase/extract retries
226 event_counter m_nExtractSuccess; ///< Count of successfully \p extract() call
227 event_counter m_nExtractFailed; ///< Count of failed \p extract() call
228 event_counter m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
229 event_counter m_nRemoveRootWaitShrinking; ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
230 event_counter m_nMakeRoutingNode; ///< How many nodes were converted to routing (valueless) nodes
232 event_counter m_nRightRotation; ///< Count of single right rotation
233 event_counter m_nLeftRotation; ///< Count of single left rotation
234 event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation
235 event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation
237 event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
238 event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
239 event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
241 event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation
242 event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation
243 event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation
245 event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation
246 event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation
247 event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation
248 event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation
250 event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting
251 event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing
254 void onFindSuccess() { ++m_nFindSuccess ; }
255 void onFindFailed() { ++m_nFindFailed ; }
256 void onFindRetry() { ++m_nFindRetry ; }
257 void onFindWaitShrinking() { ++m_nFindWaitShrinking; }
259 void onInsertSuccess() { ++m_nInsertSuccess; }
260 void onInsertFailed() { ++m_nInsertFailed; }
261 void onRelaxedInsertFailed() { ++m_nRelaxedInsertFailed; }
262 void onInsertRetry() { ++m_nInsertRetry ; }
263 void onUpdateWaitShrinking() { ++m_nUpdateWaitShrinking; }
264 void onUpdateRetry() { ++m_nUpdateRetry; }
265 void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
266 void onUpdateSuccess() { ++m_nUpdateSuccess; }
267 void onUpdateUnlinked() { ++m_nUpdateUnlinked; }
268 void onDisposeNode() { ++m_nDisposedNode; }
269 void onDisposeValue() { ++m_nDisposedValue; }
270 void onExtractValue() { ++m_nExtractedValue; }
271 void onRemove(bool bSuccess)
278 void onExtract( bool bSuccess )
285 void onRemoveRetry() { ++m_nRemoveRetry; }
286 void onRemoveWaitShrinking() { ++m_nRemoveWaitShrinking; }
287 void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
288 void onMakeRoutingNode() { ++m_nMakeRoutingNode; }
290 void onRotateRight() { ++m_nRightRotation; }
291 void onRotateLeft() { ++m_nLeftRotation; }
292 void onRotateRightOverLeft() { ++m_nRightLeftRotation; }
293 void onRotateLeftOverRight() { ++m_nLeftRightRotation; }
295 void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
296 void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
297 void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
299 void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; }
300 void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; }
301 void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; }
303 void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; }
304 void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; }
305 void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; }
306 void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; }
308 void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
309 void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
313 /// BronsonAVLTreeMap empty statistics
316 void onFindSuccess() const {}
317 void onFindFailed() const {}
318 void onFindRetry() const {}
319 void onFindWaitShrinking() const {}
321 void onInsertSuccess() const {}
322 void onInsertFailed() const {}
323 void onRelaxedInsertFailed() const {}
324 void onInsertRetry() const {}
325 void onUpdateWaitShrinking() const {}
326 void onUpdateRetry() const {}
327 void onUpdateRootWaitShrinking() const {}
328 void onUpdateSuccess() const {}
329 void onUpdateUnlinked() const {}
330 void onDisposeNode() const {}
331 void onDisposeValue() const {}
332 void onExtractValue() const {}
333 void onRemove(bool /*bSuccess*/) const {}
334 void onExtract(bool /*bSuccess*/) const {}
335 void onRemoveRetry() const {}
336 void onRemoveWaitShrinking() const {}
337 void onRemoveRootWaitShrinking() const {}
338 void onMakeRoutingNode() const {}
340 void onRotateRight() const {}
341 void onRotateLeft() const {}
342 void onRotateRightOverLeft() const {}
343 void onRotateLeftOverRight() const {}
345 void onRotateAfterRightRotation() const {}
346 void onRemoveAfterRightRotation() const {}
347 void onDamageAfterRightRotation() const {}
349 void onRotateAfterLeftRotation() const {}
350 void onRemoveAfterLeftRotation() const {}
351 void onDamageAfterLeftRotation() const {}
353 void onRotateAfterRLRotation() const {}
354 void onRemoveAfterRLRotation() const {}
355 void onRotateAfterLRRotation() const {}
356 void onRemoveAfterLRRotation() const {}
358 void onInsertRebalanceRequired() const {}
359 void onRemoveRebalanceRequired() const {}
363 /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
365 By default, this option is disabled and the new node is created under its parent lock.
366 In this case, it is guaranteed the new node will be attached to its parent.
367 On the other hand, constructing of the new node can be too complex to make it under the lock,
368 that can lead to lock contention.
370 When this option is enabled, the new node is created before locking the parent node.
371 After that, the parent is locked and checked whether the new node can be attached to the parent.
372 In this case, false node creating can be performed, but locked section can be significantly small.
374 template <bool Enable>
375 struct relaxed_insert {
377 template <typename Base> struct pack : public Base
379 enum { relaxed_insert = Enable };
384 /// \p BronsonAVLTreeMap traits
386 Note that there are two main specialization of Bronson et al AVL-tree:
387 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
388 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
390 Depends on tree specialization, different traits member can be used.
394 /// Key comparison functor
396 No default functor is provided. If the option is not specified, the \p less is used.
398 See \p cds::opt::compare option description for functor interface.
400 You should provide \p compare or \p less functor.
402 typedef opt::none compare;
404 /// Specifies binary predicate used for key compare.
406 See \p cds::opt::less option description for predicate interface.
408 You should provide \p compare or \p less functor.
410 typedef opt::none less;
412 /// Allocator for internal node
413 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
415 /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
416 typedef CDS_DEFAULT_ALLOCATOR allocator;
418 /// Disposer (only for pointer-oriented tree specialization)
420 The functor used for dispose removed values.
421 The user-provided disposer is used only for pointer-oriented tree specialization
422 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
423 the disposer will be called to signal that the memory for the value can be safely freed.
424 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
426 typedef opt::v::delete_disposer<> disposer;
428 /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
429 typedef cds::sync::injecting_monitor<cds::sync::spin> sync_monitor;
431 /// Enable relaxed insertion.
433 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
434 By default, this option is disabled.
436 static bool const relaxed_insert = false;
440 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
441 To enable it use \p atomicity::item_counter
443 typedef atomicity::empty_item_counter item_counter;
445 /// C++ memory ordering model
447 List of available memory ordering see \p opt::memory_model
449 typedef opt::v::relaxed_ordering memory_model;
451 /// Internal statistics
453 By default, internal statistics is disabled (\p ellen_bintree::empty_stat).
454 To enable it use \p ellen_bintree::stat.
456 typedef empty_stat stat;
458 /// Back-off strategy
459 typedef cds::backoff::empty back_off;
461 /// RCU deadlock checking policy (only for \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based BronsonAVLTree")
463 List of available options see \p opt::rcu_check_deadlock
465 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
468 /// Metafunction converting option list to BronsonAVLTreeMap traits
470 Note that there are two main specialization of Bronson et al AVL-tree:
471 - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
472 - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
474 Depends on tree specialization, different options can be specified.
477 - \p opt::compare - key compare functor. No default functor is provided.
478 If the option is not specified, \p %opt::less is used.
479 - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
480 - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
481 - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
482 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
483 - \p cds::intrusive::opt::disposer - the functor used for dispose removed values.
484 The user-provided disposer is used only for pointer-oriented tree specialization
485 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
486 the disposer will be called to signal that the memory for the value can be safely freed.
487 Default is \p cds::intrusive::opt::delete_disposer which calls \p delete operator.
488 Due the nature of GC schema the disposer may be called asynchronously.
489 - \p opt::sync_monitor - @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
490 default is \p cds::sync::injecting_monitor<cds::sync::spin>
491 - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
492 @ref bronson_avltree::relaxed_insert "relaxed insertion"
493 - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
494 To enable it use \p atomicity::item_counter
495 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
496 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
497 - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
498 To enable statistics use \p \p bronson_avltree::stat
499 - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
500 - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
502 template <typename... Options>
504 # ifdef CDS_DOXYGEN_INVOKED
505 typedef implementation_defined type ; ///< Metafunction result
507 typedef typename cds::opt::make_options<
508 typename cds::opt::find_type_traits< traits, Options... >::type
513 } // namespace bronson_avltree
516 template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
517 class BronsonAVLTreeMap;
519 }} // namespace cds::container
521 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H