3 #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
4 #define CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
6 #include <type_traits> // is_base_of
7 #include <cds/container/details/bronson_avltree_base.h>
8 #include <cds/urcu/details/check_deadlock.h>
9 #include <cds/urcu/exempt_ptr.h>
11 namespace cds { namespace container {
13 /// Bronson et al AVL-tree (RCU specialization for storing pointer to values)
14 /** @ingroup cds_nonintrusive_map
15 @ingroup cds_nonintrusive_tree
16 @headerfile cds/container/bronson_avltree_map_rcu.h
17 @anchor cds_container_BronsonAVLTreeMap_rcu_ptr
19 This is the specialization of \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based Bronson et al AVL-tree"
20 for "key -> value pointer" map. This specialization stores the pointer to user-allocated values instead of the copy
21 of the value. When a tree node is removed, the algorithm does not free the value pointer directly, instead, it call
22 the disposer functor provided by \p Traits template parameter.
24 <b>Template arguments</b>:
25 - \p RCU - one of \ref cds_urcu_gc "RCU type"
27 - \p T - value type to be stored in tree's nodes. Note, the specialization stores the pointer to user-allocated
29 - \p Traits - tree traits, default is \p bronson_avltree::traits
30 It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
31 instead of \p Traits template argument.
33 @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
34 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
40 # ifdef CDS_DOXYGEN_INVOKED
41 typename Traits = bronson_avltree::traits
46 class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
49 typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
50 typedef Key key_type; ///< type of a key stored in the map
51 typedef T * mapped_type; ///< type of value stored in the map
52 typedef Traits traits; ///< Traits template parameter
54 # ifdef CDS_DOXYGEN_INVOKED
55 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
57 typedef typename opt::details::make_comparator< key_type, traits >::type key_comparator;
59 typedef typename traits::item_counter item_counter; ///< Item counting policy
60 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
61 typedef typename traits::node_allocator node_allocator_type; ///< allocator for maintaining internal nodes
62 typedef typename traits::stat stat; ///< internal statistics
63 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
64 typedef typename traits::back_off back_off; ///< Back-off strategy
65 typedef typename traits::disposer disposer; ///< Value disposer
66 typedef typename traits::sync_monitor sync_monitor; ///< @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
68 /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
69 static CDS_CONSTEXPR bool const c_bRelaxedInsert = traits::relaxed_insert;
71 /// Group of \p extract_xxx functions does not require external locking
72 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false;
74 # ifdef CDS_DOXYGEN_INVOKED
75 /// Returned pointer to \p mapped_type of extracted node
76 typedef cds::urcu::exempt_ptr< gc, T, T, disposer, void > exempt_ptr;
78 typedef cds::urcu::exempt_ptr< gc,
79 typename std::remove_pointer<mapped_type>::type,
80 typename std::remove_pointer<mapped_type>::type,
86 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
90 typedef bronson_avltree::node< key_type, mapped_type, sync_monitor > node_type;
91 typedef typename node_type::version_type version_type;
93 typedef cds::details::Allocator< node_type, node_allocator_type > cxx_allocator;
94 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock > check_deadlock_policy;
96 enum class find_result
113 result_inserted = allow_insert,
114 result_updated = allow_update,
121 nothing_required = -3,
122 rebalance_required = -2,
131 typedef typename sync_monitor::template scoped_lock<node_type> node_scoped_lock;
136 template <typename K>
137 static node_type * alloc_node( K&& key, int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
139 return cxx_allocator().New( std::forward<K>( key ), nHeight, version, pParent, pLeft, pRight );
142 static void free_node( node_type * pNode )
144 // Free node without disposer
145 assert( !pNode->is_valued( memory_model::memory_order_relaxed ));
146 assert( pNode->m_SyncMonitorInjection.check_free());
147 cxx_allocator().Delete( pNode );
150 static void free_value( mapped_type pVal )
155 static node_type * child( node_type * pNode, int nDir, atomics::memory_order order = memory_model::memory_order_relaxed )
157 return pNode->child( nDir ).load( order );
160 static node_type * parent( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
162 return pNode->m_pParent.load( order );
168 node_type * m_pRetiredList; ///< head of retired node list
169 mapped_type m_pRetiredValue; ///< value retired
173 : m_pRetiredList( nullptr )
174 , m_pRetiredValue( nullptr )
182 void dispose( node_type * pNode )
184 assert( !pNode->is_valued( memory_model::memory_order_relaxed ));
185 pNode->m_pNextRemoved = m_pRetiredList;
186 m_pRetiredList = pNode;
189 void dispose_value( mapped_type pVal )
191 assert( m_pRetiredValue == nullptr );
192 m_pRetiredValue = pVal;
196 struct internal_disposer
198 void operator()( node_type * p ) const
206 assert( !gc::is_locked() );
208 // TODO: use RCU::batch_retire
211 for ( node_type * p = m_pRetiredList; p; ) {
212 node_type * pNext = static_cast<node_type *>( p->m_pNextRemoved );
213 // Value already disposed
214 gc::template retire_ptr<internal_disposer>( p );
219 if ( m_pRetiredValue )
220 gc::template retire_ptr<disposer>( m_pRetiredValue );
228 typename node_type::base_class m_Root;
230 item_counter m_ItemCounter;
231 mutable sync_monitor m_Monitor;
236 /// Creates empty map
238 : m_pRoot( static_cast<node_type *>( &m_Root ))
249 The \p key_type should be constructible from a value of type \p K.
251 RCU \p synchronize() can be called. RCU should not be locked.
253 Returns \p true if inserting successful, \p false otherwise.
255 template <typename K>
256 bool insert( K const& key, mapped_type pVal )
258 return do_update(key, key_comparator(),
259 [pVal]( node_type * pNode ) -> mapped_type
261 assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
265 update_flags::allow_insert
266 ) == update_flags::result_inserted;
269 /// Updates the value for \p key
271 The operation performs inserting or updating the value for \p key with lock-free manner.
272 If \p bInsert is \p false, only updating of existing node is possible.
274 If \p key is not found and inserting is allowed (i.e. \p bInsert is \p true),
275 then the new node created from \p key will be inserted into the map; note that in this case the \ref key_type should be
276 constructible from type \p K.
277 Otherwise, the value for \p key will be changed to \p pVal.
279 RCU \p synchronize() method can be called. RCU should not be locked.
281 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
282 \p second is \p true if new node has been added or \p false if the node with \p key
285 template <typename K>
286 std::pair<bool, bool> update( K const& key, mapped_type pVal, bool bInsert = true )
288 int result = do_update( key, key_comparator(),
289 [pVal]( node_type * ) -> mapped_type
293 update_flags::allow_update | (bInsert ? update_flags::allow_insert : 0)
295 return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
299 template <typename K>
300 std::pair<bool, bool> ensure( K const& key, mapped_type pVal )
302 return update( key, pVal, true );
307 /// Delete \p key from the map
309 RCU \p synchronize() method can be called. RCU should not be locked.
311 Return \p true if \p key is found and deleted, \p false otherwise
313 template <typename K>
314 bool erase( K const& key )
319 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true; }
323 /// Deletes the item from the map using \p pred predicate for searching
325 The function is an analog of \p erase(K const&)
326 but \p pred is used for key comparing.
327 \p Less functor has the interface like \p std::less.
328 \p Less must imply the same element order as the comparator used for building the map.
330 template <typename K, typename Less>
331 bool erase_with( K const& key, Less pred )
336 cds::opt::details::make_comparator_from_less<Less>(),
337 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true; }
341 /// Delete \p key from the map
343 The function searches an item with key \p key, calls \p f functor
344 and deletes the item. If \p key is not found, the functor is not called.
346 The functor \p Func interface:
349 void operator()( key_type const& key, std::remove_pointer<mapped_type>::type& val) { ... }
353 RCU \p synchronize method can be called. RCU should not be locked.
355 Return \p true if key is found and deleted, \p false otherwise
357 template <typename K, typename Func>
358 bool erase( K const& key, Func f )
363 [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
366 disp.dispose_value(pVal);
372 /// Deletes the item from the map using \p pred predicate for searching
374 The function is an analog of \p erase(K const&, Func)
375 but \p pred is used for key comparing.
376 \p Less functor has the interface like \p std::less.
377 \p Less must imply the same element order as the comparator used for building the map.
379 template <typename K, typename Less, typename Func>
380 bool erase_with( K const& key, Less pred, Func f )
385 cds::opt::details::make_comparator_from_less<Less>(),
386 [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
389 disp.dispose_value(pVal);
395 /// Extracts a value with minimal key from the map
397 Returns \p exempt_ptr to the leftmost item.
398 If the tree is empty, returns empty \p exempt_ptr.
400 Note that the function returns only the value for minimal key.
401 To retrieve its key use \p extract_min( Func ) member function.
403 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
404 It means that the function gets leftmost leaf of the tree and tries to unlink it.
405 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
406 So, the function returns the item with minimum key at the moment of tree traversing.
408 RCU \p synchronize method can be called. RCU should NOT be locked.
409 The function does not free the item.
410 The deallocator will be implicitly invoked when the returned object is destroyed or when
411 its \p release() member function is called.
413 exempt_ptr extract_min()
415 return exempt_ptr(do_extract_min( []( key_type const& ) {}));
418 /// Extracts minimal key key and corresponding value
420 Returns \p exempt_ptr to the leftmost item.
421 If the tree is empty, returns empty \p exempt_ptr.
423 \p Func functor is used to store minimal key.
424 \p Func has the following signature:
427 void operator()( key_type const& key );
430 If the tree is empty, \p f is not called.
431 Otherwise, is it called with minimal key, the pointer to corresponding value is returned
434 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
435 It means that the function gets leftmost leaf of the tree and tries to unlink it.
436 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
437 So, the function returns the item with minimum key at the moment of tree traversing.
439 RCU \p synchronize method can be called. RCU should NOT be locked.
440 The function does not free the item.
441 The deallocator will be implicitly invoked when the returned object is destroyed or when
442 its \p release() member function is called.
444 template <typename Func>
445 exempt_ptr extract_min( Func f )
447 return exempt_ptr(do_extract_min( [&f]( key_type const& key ) { f(key); }));
450 /// Extracts minimal key key and corresponding value
452 This function is a shortcut for the following call:
455 exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } );
457 \p key_type should be copy-assignable. The copy of minimal key
458 is returned in \p min_key argument.
460 typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
461 extract_min_key( key_type& min_key )
463 return exempt_ptr(do_extract_min( [&min_key]( key_type const& key ) { min_key = key; }));
466 /// Extracts a value with maximal key from the tree
468 Returns \p exempt_ptr pointer to the rightmost item.
469 If the set is empty, returns empty \p exempt_ptr.
471 Note that the function returns only the value for maximal key.
472 To retrieve its key use \p extract_max( Func ) member function.
474 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
475 It means that the function gets rightmost leaf of the tree and tries to unlink it.
476 During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
477 So, the function returns the item with maximum key at the moment of tree traversing.
479 RCU \p synchronize method can be called. RCU should NOT be locked.
480 The function does not free the item.
481 The deallocator will be implicitly invoked when the returned object is destroyed or when
482 its \p release() is called.
484 exempt_ptr extract_max()
486 return exempt_ptr(do_extract_max( []( key_type const& ) {}));
489 /// Extracts the maximal key and corresponding value
491 Returns \p exempt_ptr pointer to the rightmost item.
492 If the set is empty, returns empty \p exempt_ptr.
494 \p Func functor is used to store maximal key.
495 \p Func has the following signature:
498 void operator()( key_type const& key );
501 If the tree is empty, \p f is not called.
502 Otherwise, is it called with maximal key, the pointer to corresponding value is returned
505 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
506 It means that the function gets rightmost leaf of the tree and tries to unlink it.
507 During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
508 So, the function returns the item with maximum key at the moment of tree traversing.
510 RCU \p synchronize method can be called. RCU should NOT be locked.
511 The function does not free the item.
512 The deallocator will be implicitly invoked when the returned object is destroyed or when
513 its \p release() is called.
515 template <typename Func>
516 exempt_ptr extract_max( Func f )
518 return exempt_ptr(do_extract_max( [&f]( key_type const& key ) { f(key); }));
521 /// Extracts the maximal key and corresponding value
523 This function is a shortcut for the following call:
526 exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } );
528 \p key_type should be copy-assignable. The copy of maximal key
529 is returned in \p max_key argument.
531 typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
532 extract_max_key( key_type& max_key )
534 return exempt_ptr(do_extract_max( [&max_key]( key_type const& key ) { max_key = key; }));
537 /// Extracts an item from the map
539 The function searches an item with key equal to \p key in the tree,
540 unlinks it, and returns \p exempt_ptr pointer to a value found.
541 If \p key is not found the function returns an empty \p exempt_ptr.
543 RCU \p synchronize method can be called. RCU should NOT be locked.
544 The function does not destroy the value found.
545 The disposer will be implicitly invoked when the returned object is destroyed or when
546 its \p release() member function is called.
548 template <typename Q>
549 exempt_ptr extract( Q const& key )
551 return exempt_ptr(do_extract( key ));
555 /// Extracts an item from the map using \p pred for searching
557 The function is an analog of \p extract(Q const&)
558 but \p pred is used for key compare.
559 \p Less has the interface like \p std::less.
560 \p pred must imply the same element order as the comparator used for building the tree.
562 template <typename Q, typename Less>
563 exempt_ptr extract_with( Q const& key, Less pred )
565 return exempt_ptr(do_extract_with( key, pred ));
568 /// Find the key \p key
570 The function searches the item with key equal to \p key and calls the functor \p f for item found.
571 The interface of \p Func functor is:
574 void operator()( key_type const& key, mapped_type& item );
577 where \p item is the item found.
578 The functor is called under node-level lock.
580 The function applies RCU lock internally.
582 The function returns \p true if \p key is found, \p false otherwise.
584 template <typename K, typename Func>
585 bool find( K const& key, Func f )
587 return do_find( key, key_comparator(),
588 [&f]( node_type * pNode ) -> bool {
589 assert( pNode != nullptr );
590 mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
592 f( pNode->m_key, *pVal );
600 /// Finds the key \p val using \p pred predicate for searching
602 The function is an analog of \p find(K const&, Func)
603 but \p pred is used for key comparing.
604 \p Less functor has the interface like \p std::less.
605 \p Less must imply the same element order as the comparator used for building the map.
607 template <typename K, typename Less, typename Func>
608 bool find_with( K const& key, Less pred, Func f )
611 return do_find( key, cds::opt::details::make_comparator_from_less<Less>(),
612 [&f]( node_type * pNode ) -> bool {
613 assert( pNode != nullptr );
614 mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
616 f( pNode->m_key, *pVal );
624 /// Find the key \p key
626 The function searches the item with key equal to \p key
627 and returns \p true if it is found, and \p false otherwise.
629 The function applies RCU lock internally.
631 template <typename K>
632 bool find( K const& key )
634 return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
637 /// Finds the key \p val using \p pred predicate for searching
639 The function is an analog of \p find(K const&)
640 but \p pred is used for key comparing.
641 \p Less functor has the interface like \p std::less.
642 \p Less must imply the same element order as the comparator used for building the map.
644 template <typename K, typename Less>
645 bool find_with( K const& key, Less pred )
648 return do_find( key, cds::opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
651 /// Clears the tree (thread safe, not atomic)
653 The function unlink all items from the tree.
654 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
658 assert( set.empty() );
660 the assertion could be raised.
662 For each node the \ref disposer will be called after unlinking.
664 RCU \p synchronize method can be called. RCU should not be locked.
668 while ( extract_min() );
671 /// Clears the tree (not thread safe)
673 This function is not thread safe and may be called only when no other thread deals with the tree.
674 The function is used in the tree destructor.
678 clear(); // temp solution
682 /// Checks if the map is empty
685 return m_Root.m_pRight.load( memory_model::memory_order_relaxed ) == nullptr;
688 /// Returns item count in the map
690 Only leaf nodes containing user data are counted.
692 The value returned depends on item counter type provided by \p Traits template parameter.
693 If it is \p atomicity::empty_item_counter this function always returns 0.
695 The function is not suitable for checking the tree emptiness, use \p empty()
696 member function for this purpose.
700 return m_ItemCounter;
703 /// Returns const reference to internal statistics
704 stat const& statistics() const
709 /// Returns reference to \p sync_monitor object
710 sync_monitor& monitor()
715 sync_monitor const& monitor() const
721 /// Checks internal consistency (not atomic, not thread-safe)
723 The debugging function to check internal consistency of the tree.
725 bool check_consistency() const
727 return check_consistency([]( size_t /*nLevel*/, size_t /*hLeft*/, size_t /*hRight*/ ){} );
730 /// Checks internal consistency (not atomic, not thread-safe)
732 The debugging function to check internal consistency of the tree.
733 The functor \p Func is called if a violation of internal tree structure
737 void operator()( size_t nLevel, size_t hLeft, size_t hRight );
741 - \p nLevel - the level where the violation is found
742 - \p hLeft - the height of left subtree
743 - \p hRight - the height of right subtree
745 The functor is called for each violation found.
747 template <typename Func>
748 bool check_consistency( Func f ) const
750 node_type * pChild = child( m_pRoot, right_child );
753 do_check_consistency( pChild, 1, f, nErrors );
761 template <typename Func>
762 size_t do_check_consistency( node_type * pNode, size_t nLevel, Func f, size_t& nErrors ) const
766 node_type * pLeft = child( pNode, left_child );
767 node_type * pRight = child( pNode, right_child );
768 if ( pLeft && cmp( pLeft->m_key, pNode->m_key ) > 0 )
770 if ( pRight && cmp( pNode->m_key, pRight->m_key ) > 0 )
773 size_t hLeft = do_check_consistency( pLeft, nLevel + 1, f, nErrors );
774 size_t hRight = do_check_consistency( pRight, nLevel + 1, f, nErrors );
776 if ( hLeft >= hRight ) {
777 if ( hLeft - hRight > 1 ) {
778 f( nLevel, hLeft, hRight );
784 if ( hRight - hLeft > 1 ) {
785 f( nLevel, hLeft, hRight );
794 template <typename Q, typename Compare, typename Func>
795 bool do_find( Q& key, Compare cmp, Func f ) const
800 result = try_find( key, cmp, f, m_pRoot, 1, 0 );
802 assert( result != find_result::retry );
803 return result == find_result::found;
806 template <typename K, typename Compare, typename Func>
807 int do_update( K const& key, Compare cmp, Func funcUpdate, int nFlags )
809 check_deadlock_policy::check();
811 rcu_disposer removed_list;
814 return try_update_root( key, cmp, nFlags, funcUpdate, removed_list );
818 template <typename K, typename Compare, typename Func>
819 bool do_remove( K const& key, Compare cmp, Func func )
821 // Func must return true if the value was disposed
822 // or false if the value was extracted
824 check_deadlock_policy::check();
826 rcu_disposer removed_list;
829 return try_remove_root( key, cmp, func, removed_list );
833 template <typename Func>
834 mapped_type do_extract_min( Func f )
836 mapped_type pExtracted = nullptr;
839 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
844 template <typename Func>
845 mapped_type do_extract_max( Func f )
847 mapped_type pExtracted = nullptr;
850 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
855 template <typename Func>
856 void do_extract_minmax( int nDir, Func func )
858 check_deadlock_policy::check();
860 rcu_disposer removed_list;
864 int result = update_flags::failed;
866 // get right child of root
867 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
869 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
870 if ( nChildVersion & node_type::shrinking ) {
871 m_stat.onRemoveRootWaitShrinking();
872 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
873 result = update_flags::retry;
875 else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
876 result = try_extract_minmax( nDir, func, m_pRoot, pChild, nChildVersion, removed_list );
879 } while ( result == update_flags::retry );
883 template <typename Q>
884 mapped_type do_extract( Q const& key )
886 mapped_type pExtracted = nullptr;
890 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
895 template <typename Q, typename Less>
896 mapped_type do_extract_with( Q const& key, Less pred )
899 mapped_type pExtracted = nullptr;
902 cds::opt::details::make_comparator_from_less<Less>(),
903 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
911 static int height( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
914 return pNode->m_nHeight.load( order );
916 static void set_height( node_type * pNode, int h, atomics::memory_order order = memory_model::memory_order_relaxed )
919 pNode->m_nHeight.store( h, order );
921 static int height_null( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
923 return pNode ? height( pNode, order ) : 0;
926 template <typename Q, typename Compare, typename Func>
927 find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
929 assert( gc::is_locked() );
933 node_type * pChild = child( pNode, nDir );
935 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
936 m_stat.onFindRetry();
937 return find_result::retry;
940 m_stat.onFindFailed();
941 return find_result::not_found;
944 int nCmp = cmp( key, pChild->m_key );
946 if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
948 node_scoped_lock l( m_Monitor, *pChild );
949 if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
951 m_stat.onFindSuccess();
952 return find_result::found;
957 m_stat.onFindFailed();
958 return find_result::not_found;
961 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
962 if ( nChildVersion & node_type::shrinking ) {
963 m_stat.onFindWaitShrinking();
964 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
966 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
967 m_stat.onFindRetry();
968 return find_result::retry;
971 else if ( nChildVersion != node_type::unlinked ) {
972 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
973 m_stat.onFindRetry();
974 return find_result::retry;
977 find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
978 if ( found != find_result::retry )
982 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
983 m_stat.onFindRetry();
984 return find_result::retry;
989 template <typename K, typename Compare, typename Func>
990 int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
992 assert( gc::is_locked() );
996 // get right child of root
997 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
999 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1000 if ( nChildVersion & node_type::shrinking ) {
1001 m_stat.onUpdateRootWaitShrinking();
1002 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1003 result = update_flags::retry;
1005 else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
1006 result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1009 result = update_flags::retry;
1012 // the tree is empty
1013 if ( nFlags & update_flags::allow_insert ) {
1014 // insert into tree as right child of the root
1016 node_scoped_lock l( m_Monitor, *m_pRoot );
1017 if ( child( m_pRoot, right_child, memory_model::memory_order_acquire ) != nullptr ) {
1018 result = update_flags::retry;
1022 node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr );
1023 mapped_type pVal = funcUpdate( pNew );
1024 assert( pVal != nullptr );
1025 pNew->m_pValue.store( pVal, memory_model::memory_order_release );
1027 m_pRoot->child( pNew, right_child, memory_model::memory_order_relaxed );
1028 set_height( m_pRoot, 2 );
1032 m_stat.onInsertSuccess();
1033 return update_flags::result_inserted;
1036 return update_flags::failed;
1038 } while ( result == update_flags::retry );
1042 template <typename K, typename Compare, typename Func>
1043 bool try_remove_root( K const& key, Compare cmp, Func func, rcu_disposer& disp )
1045 assert( gc::is_locked() );
1049 // get right child of root
1050 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1052 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1053 if ( nChildVersion & node_type::shrinking ) {
1054 m_stat.onRemoveRootWaitShrinking();
1055 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1056 result = update_flags::retry;
1058 else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
1059 result = try_remove( key, cmp, func, m_pRoot, pChild, nChildVersion, disp );
1062 result = update_flags::retry;
1066 } while ( result == update_flags::retry );
1068 return result == update_flags::result_removed;
1071 template <typename K, typename Compare, typename Func>
1072 int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1074 assert( gc::is_locked() );
1075 assert( nVersion != node_type::unlinked );
1077 int nCmp = cmp( key, pNode->m_key );
1079 if ( nFlags & update_flags::allow_update ) {
1080 return try_update_node( funcUpdate, pNode, nVersion, disp );
1082 return update_flags::failed;
1087 node_type * pChild = child( pNode, nCmp );
1088 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1089 m_stat.onUpdateRetry();
1090 return update_flags::retry;
1093 if ( pChild == nullptr ) {
1095 if ( nFlags & update_flags::allow_insert )
1096 result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
1098 result = update_flags::failed;
1102 result = update_flags::retry;
1103 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1104 if ( nChildVersion & node_type::shrinking ) {
1105 m_stat.onUpdateWaitShrinking();
1106 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1109 else if ( pChild == child( pNode, nCmp )) {
1110 // this second read is important, because it is protected by nChildVersion
1112 // validate the read that our caller took to get to node
1113 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1114 m_stat.onUpdateRetry();
1115 return update_flags::retry;
1118 // At this point we know that the traversal our parent took to get to node is still valid.
1119 // The recursive implementation will validate the traversal from node to
1120 // child, so just prior to the node nVersion validation both traversals were definitely okay.
1121 // This means that we are no longer vulnerable to node shrinks, and we don't need
1122 // to validate node version any more.
1123 result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1127 if ( result == update_flags::retry && pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1128 m_stat.onUpdateRetry();
1129 return update_flags::retry;
1131 } while ( result == update_flags::retry );
1135 template <typename K, typename Compare, typename Func>
1136 int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1138 assert( gc::is_locked() );
1139 assert( nVersion != node_type::unlinked );
1141 int nCmp = cmp( key, pNode->m_key );
1143 return try_remove_node( pParent, pNode, nVersion, func, disp );
1147 node_type * pChild = child( pNode, nCmp );
1148 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1149 m_stat.onRemoveRetry();
1150 return update_flags::retry;
1153 if ( pChild == nullptr ) {
1154 return update_flags::failed;
1158 result = update_flags::retry;
1159 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1160 if ( nChildVersion & node_type::shrinking ) {
1161 m_stat.onRemoveWaitShrinking();
1162 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1165 else if ( pChild == child( pNode, nCmp )) {
1166 // this second read is important, because it is protected by nChildVersion
1168 // validate the read that our caller took to get to node
1169 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1170 m_stat.onRemoveRetry();
1171 return update_flags::retry;
1174 // At this point we know that the traversal our parent took to get to node is still valid.
1175 // The recursive implementation will validate the traversal from node to
1176 // child, so just prior to the node nVersion validation both traversals were definitely okay.
1177 // This means that we are no longer vulnerable to node shrinks, and we don't need
1178 // to validate node version any more.
1179 result = try_remove( key, cmp, func, pNode, pChild, nChildVersion, disp );
1183 if ( result == update_flags::retry && pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1184 m_stat.onRemoveRetry();
1185 return update_flags::retry;
1187 } while ( result == update_flags::retry );
1191 template <typename Func>
1192 int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1194 assert( gc::is_locked() );
1195 assert( nVersion != node_type::unlinked );
1199 node_type * pChild = child( pNode, nDir );
1200 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1201 m_stat.onRemoveRetry();
1202 return update_flags::retry;
1205 if ( pChild == nullptr ) {
1207 return try_remove_node( pParent, pNode, nVersion, func, disp );
1210 result = update_flags::retry;
1211 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1212 if ( nChildVersion & node_type::shrinking ) {
1213 m_stat.onRemoveWaitShrinking();
1214 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1217 else if ( pChild == child( pNode, nDir )) {
1218 // this second read is important, because it is protected by nChildVersion
1220 // validate the read that our caller took to get to node
1221 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1222 m_stat.onRemoveRetry();
1223 return update_flags::retry;
1226 // At this point we know that the traversal our parent took to get to node is still valid.
1227 // The recursive implementation will validate the traversal from node to
1228 // child, so just prior to the node nVersion validation both traversals were definitely okay.
1229 // This means that we are no longer vulnerable to node shrinks, and we don't need
1230 // to validate node version any more.
1231 result = try_extract_minmax( nDir, func, pNode, pChild, nChildVersion, disp );
1235 if ( result == update_flags::retry && pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1236 m_stat.onRemoveRetry();
1237 return update_flags::retry;
1239 } while ( result == update_flags::retry );
1243 template <typename K, typename Func>
1244 int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
1248 auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
1249 mapped_type pVal = funcUpdate( pNew );
1250 assert( pVal != nullptr );
1251 pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1254 if ( c_bRelaxedInsert ) {
1255 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1256 || child( pNode, nDir ) != nullptr )
1258 m_stat.onInsertRetry();
1259 return update_flags::retry;
1262 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1265 node_type * pDamaged;
1267 assert( pNode != nullptr );
1268 node_scoped_lock l( m_Monitor, *pNode );
1270 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1271 || child( pNode, nDir ) != nullptr )
1273 if ( c_bRelaxedInsert ) {
1274 mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
1275 pNew->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1278 m_stat.onRelaxedInsertFailed();
1281 m_stat.onInsertRetry();
1282 return update_flags::retry;
1285 if ( !c_bRelaxedInsert )
1286 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1288 pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
1289 pDamaged = fix_height_locked( pNode );
1293 m_stat.onInsertSuccess();
1296 fix_height_and_rebalance( pDamaged, disp );
1297 m_stat.onInsertRebalanceRequired();
1300 return update_flags::result_inserted;
1303 template <typename Func>
1304 int try_update_node( Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1307 assert( pNode != nullptr );
1309 node_scoped_lock l( m_Monitor, *pNode );
1311 if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1312 m_stat.onUpdateRetry();
1313 return update_flags::retry;
1316 if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
1317 m_stat.onUpdateUnlinked();
1318 return update_flags::retry;
1321 pOld = pNode->value( memory_model::memory_order_relaxed );
1322 mapped_type pVal = funcUpdate( pNode );
1326 assert( pVal != nullptr );
1327 pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1332 disp.dispose_value(pOld);
1333 m_stat.onDisposeValue();
1336 m_stat.onUpdateSuccess();
1337 return update_flags::result_updated;
1340 template <typename Func>
1341 int try_remove_node( node_type * pParent, node_type * pNode, version_type nVersion, Func func, rcu_disposer& disp )
1343 assert( pParent != nullptr );
1344 assert( pNode != nullptr );
1346 if ( !pNode->is_valued( atomics::memory_order_relaxed ) )
1347 return update_flags::failed;
1349 if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) {
1350 node_type * pDamaged;
1353 node_scoped_lock lp( m_Monitor, *pParent );
1354 if ( pParent->is_unlinked( atomics::memory_order_relaxed ) || parent( pNode ) != pParent )
1355 return update_flags::retry;
1358 node_scoped_lock ln( m_Monitor, *pNode );
1359 pOld = pNode->value( memory_model::memory_order_relaxed );
1360 if ( !( pNode->version( memory_model::memory_order_acquire ) == nVersion
1362 && try_unlink_locked( pParent, pNode, disp )))
1364 return update_flags::retry;
1367 pDamaged = fix_height_locked( pParent );
1371 if ( func( pNode->m_key, pOld, disp )) // calls pOld disposer inside
1372 m_stat.onDisposeValue();
1374 m_stat.onExtractValue();
1377 fix_height_and_rebalance( pDamaged, disp );
1378 m_stat.onRemoveRebalanceRequired();
1380 return update_flags::result_removed;
1383 int result = update_flags::retry;
1386 node_scoped_lock ln( m_Monitor, *pNode );
1387 pOld = pNode->value( atomics::memory_order_relaxed );
1388 if ( pNode->version( atomics::memory_order_acquire ) == nVersion && pOld ) {
1389 pNode->m_pValue.store( nullptr, atomics::memory_order_relaxed );
1390 result = update_flags::result_removed;
1394 if ( result == update_flags::result_removed ) {
1396 if ( func( pNode->m_key, pOld, disp )) // calls pOld disposer inside
1397 m_stat.onDisposeValue();
1399 m_stat.onExtractValue();
1406 bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1408 // pParent and pNode must be locked
1409 assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
1411 node_type * pParentLeft = child( pParent, left_child );
1412 node_type * pParentRight = child( pParent, right_child );
1413 if ( pNode != pParentLeft && pNode != pParentRight ) {
1414 // node is no longer a child of parent
1418 assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ) );
1419 assert( pParent == parent( pNode ));
1421 node_type * pLeft = child( pNode, left_child );
1422 node_type * pRight = child( pNode, right_child );
1423 if ( pLeft != nullptr && pRight != nullptr ) {
1424 // splicing is no longer possible
1427 node_type * pSplice = pLeft ? pLeft : pRight;
1429 if ( pParentLeft == pNode )
1430 pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
1432 pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
1435 pSplice->m_pParent.store( pParent, memory_model::memory_order_release );
1437 // Mark the node as unlinked
1438 pNode->version( node_type::unlinked, memory_model::memory_order_release );
1440 // The value will be disposed by calling function
1441 pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1443 disp.dispose( pNode );
1444 m_stat.onDisposeNode();
1451 private: // rotations
1453 int estimate_node_condition( node_type * pNode )
1455 node_type * pLeft = child( pNode, left_child );
1456 node_type * pRight = child( pNode, right_child );
1458 if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed ))
1459 return unlink_required;
1461 int h = height( pNode );
1462 int hL = height_null( pLeft );
1463 int hR = height_null( pRight );
1465 int hNew = 1 + std::max( hL, hR );
1466 int nBalance = hL - hR;
1468 if ( nBalance < -1 || nBalance > 1 )
1469 return rebalance_required;
1471 return h != hNew ? hNew : nothing_required;
1474 node_type * fix_height( node_type * pNode )
1476 assert( pNode != nullptr );
1477 node_scoped_lock l( m_Monitor, *pNode );
1478 return fix_height_locked( pNode );
1481 node_type * fix_height_locked( node_type * pNode )
1483 // pNode must be locked!!!
1484 int h = estimate_node_condition( pNode );
1486 case rebalance_required:
1487 case unlink_required:
1489 case nothing_required:
1492 set_height( pNode, h );
1493 return parent( pNode );
1497 void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
1499 while ( pNode && parent( pNode )) {
1500 int nCond = estimate_node_condition( pNode );
1501 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
1504 if ( nCond != unlink_required && nCond != rebalance_required )
1505 pNode = fix_height( pNode );
1507 node_type * pParent = parent( pNode );
1508 assert( pParent != nullptr );
1510 node_scoped_lock lp( m_Monitor, *pParent );
1511 if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode ) == pParent ) {
1512 node_scoped_lock ln( m_Monitor, *pNode );
1513 pNode = rebalance_locked( pParent, pNode, disp );
1520 node_type * rebalance_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1522 // pParent and pNode should be locked.
1523 // Returns a damaged node, or nullptr if no more rebalancing is necessary
1524 assert( parent( pNode ) == pParent );
1526 node_type * pLeft = child( pNode, left_child );
1527 node_type * pRight = child( pNode, right_child );
1529 if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1530 if ( try_unlink_locked( pParent, pNode, disp ))
1531 return fix_height_locked( pParent );
1533 // retry needed for pNode
1538 assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1540 int h = height( pNode );
1541 int hL = height_null( pLeft );
1542 int hR = height_null( pRight );
1543 int hNew = 1 + std::max( hL, hR );
1544 int balance = hL - hR;
1547 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
1548 else if ( balance < -1 )
1549 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
1550 else if ( hNew != h ) {
1551 set_height( pNode, hNew );
1553 // pParent is already locked
1554 return fix_height_locked( pParent );
1560 node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
1562 assert( parent( pNode ) == pParent );
1563 assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1565 // pParent and pNode is locked yet
1566 // pNode->pLeft is too large, we will rotate-right.
1567 // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
1570 assert( pLeft != nullptr );
1571 node_scoped_lock l( m_Monitor, *pLeft );
1572 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
1573 return pNode; // retry for pNode
1575 int hL = height( pLeft );
1577 return pNode; // retry
1579 node_type * pLRight = child( pLeft, right_child );
1580 int hLR = height_null( pLRight );
1581 node_type * pLLeft = child( pLeft, left_child );
1582 int hLL = height_null( pLLeft );
1586 return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1589 assert( pLRight != nullptr );
1591 node_scoped_lock lr( m_Monitor, *pLRight );
1592 if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
1593 return pNode; // retry
1595 hLR = height( pLRight );
1597 return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1599 int hLRL = height_null( child( pLRight, left_child ));
1600 int balance = hLL - hLRL;
1601 if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
1602 // nParent.child.left won't be damaged after a double rotation
1603 return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
1607 // focus on pLeft, if necessary pNode will be balanced later
1608 return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
1613 node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
1615 assert( parent( pNode ) == pParent );
1616 assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1618 // pParent and pNode is locked yet
1620 assert( pRight != nullptr );
1621 node_scoped_lock l( m_Monitor, *pRight );
1622 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
1623 return pNode; // retry for pNode
1625 int hR = height( pRight );
1626 if ( hL - hR >= -1 )
1627 return pNode; // retry
1629 node_type * pRLeft = child( pRight, left_child );
1630 int hRL = height_null( pRLeft );
1631 node_type * pRRight = child( pRight, right_child );
1632 int hRR = height_null( pRRight );
1634 return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1637 assert( pRLeft != nullptr );
1638 node_scoped_lock lrl( m_Monitor, *pRLeft );
1639 if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
1640 return pNode; // retry
1642 hRL = height( pRLeft );
1644 return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1646 node_type * pRLRight = child( pRLeft, right_child );
1647 int hRLR = height_null( pRLRight );
1648 int balance = hRR - hRLR;
1649 if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
1650 return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
1652 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
1656 static void begin_change( node_type * pNode, version_type version )
1658 assert(pNode->version(memory_model::memory_order_acquire) == version );
1659 assert( (version & node_type::shrinking) == 0 );
1660 pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
1662 static void end_change( node_type * pNode, version_type version )
1664 // Clear shrinking and unlinked flags and increment version
1665 pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
1668 node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
1670 version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1671 node_type * pParentLeft = child( pParent, left_child );
1673 begin_change( pNode, nodeVersion );
1675 pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1676 if ( pLRight != nullptr )
1677 pLRight->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1679 atomics::atomic_thread_fence( memory_model::memory_order_release );
1681 pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1682 pNode->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1684 atomics::atomic_thread_fence( memory_model::memory_order_release );
1686 if ( pParentLeft == pNode )
1687 pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1689 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1690 pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
1692 pLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1694 atomics::atomic_thread_fence( memory_model::memory_order_release );
1696 // fix up heights links
1697 int hNode = 1 + std::max( hLR, hR );
1698 set_height( pNode, hNode );
1699 set_height( pLeft, 1 + std::max( hLL, hNode ));
1701 end_change( pNode, nodeVersion );
1702 m_stat.onRotateRight();
1704 // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
1705 // parent.child). pNode is the deepest. Perform as many fixes as we can
1706 // with the locks we've got.
1708 // We've already fixed the height for pNode, but it might still be outside
1709 // our allowable balance range. In that case a simple fix_height_locked()
1711 int nodeBalance = hLR - hR;
1712 if ( nodeBalance < -1 || nodeBalance > 1 ) {
1713 // we need another rotation at pNode
1714 m_stat.onRotateAfterRightRotation();
1718 // we've fixed balance and height damage for pNode, now handle
1719 // extra-routing node damage
1720 if ( (pLRight == nullptr || hR == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) {
1721 // we need to remove pNode and then repair
1722 m_stat.onRemoveAfterRightRotation();
1726 // we've already fixed the height at pLeft, do we need a rotation here?
1727 int leftBalance = hLL - hNode;
1728 if ( leftBalance < -1 || leftBalance > 1 ) {
1729 m_stat.onRotateAfterRightRotation();
1733 // pLeft might also have routing node damage (if pLeft.left was null)
1734 if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_relaxed) ) {
1735 m_stat.onDamageAfterRightRotation();
1739 // try to fix the parent height while we've still got the lock
1740 return fix_height_locked( pParent );
1743 node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
1745 version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1746 node_type * pParentLeft = child( pParent, left_child );
1748 begin_change( pNode, nodeVersion );
1750 // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
1751 pNode->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1752 if ( pRLeft != nullptr )
1753 pRLeft->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1755 atomics::atomic_thread_fence( memory_model::memory_order_release );
1757 pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1758 pNode->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1760 atomics::atomic_thread_fence( memory_model::memory_order_release );
1762 if ( pParentLeft == pNode )
1763 pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
1765 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1766 pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1768 pRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1770 atomics::atomic_thread_fence( memory_model::memory_order_release );
1773 int hNode = 1 + std::max( hL, hRL );
1774 set_height( pNode, hNode );
1775 set_height( pRight, 1 + std::max( hNode, hRR ));
1777 end_change( pNode, nodeVersion );
1778 m_stat.onRotateLeft();
1780 int nodeBalance = hRL - hL;
1781 if ( nodeBalance < -1 || nodeBalance > 1 ) {
1782 m_stat.onRotateAfterLeftRotation();
1786 if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
1787 m_stat.onRemoveAfterLeftRotation();
1791 int rightBalance = hRR - hNode;
1792 if ( rightBalance < -1 || rightBalance > 1 ) {
1793 m_stat.onRotateAfterLeftRotation();
1797 if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_relaxed) ) {
1798 m_stat.onDamageAfterLeftRotation();
1802 return fix_height_locked( pParent );
1805 node_type * rotate_right_over_left_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLRL )
1807 version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1808 version_type leftVersion = pLeft->version( memory_model::memory_order_acquire );
1810 node_type * pPL = child( pParent, left_child );
1811 node_type * pLRL = child( pLRight, left_child );
1812 node_type * pLRR = child( pLRight, right_child );
1813 int hLRR = height_null( pLRR );
1815 begin_change( pNode, nodeVersion );
1816 begin_change( pLeft, leftVersion );
1818 // fix up pNode links, careful about the order!
1819 pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
1820 if ( pLRR != nullptr )
1821 pLRR->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1822 atomics::atomic_thread_fence( memory_model::memory_order_release );
1824 pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
1825 if ( pLRL != nullptr )
1826 pLRL->m_pParent.store( pLeft, memory_model::memory_order_relaxed );
1827 atomics::atomic_thread_fence( memory_model::memory_order_release );
1829 pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1830 pLeft->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1831 atomics::atomic_thread_fence( memory_model::memory_order_release );
1833 pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1834 pNode->m_pParent.store( pLRight, memory_model::memory_order_relaxed );
1835 atomics::atomic_thread_fence( memory_model::memory_order_release );
1838 pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1840 assert( child( pParent, right_child ) == pNode );
1841 pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
1843 pLRight->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1844 atomics::atomic_thread_fence( memory_model::memory_order_release );
1847 int hNode = 1 + std::max( hLRR, hR );
1848 set_height( pNode, hNode );
1849 int hLeft = 1 + std::max( hLL, hLRL );
1850 set_height( pLeft, hLeft );
1851 set_height( pLRight, 1 + std::max( hLeft, hNode ));
1853 end_change( pNode, nodeVersion );
1854 end_change( pLeft, leftVersion );
1855 m_stat.onRotateRightOverLeft();
1857 // caller should have performed only a single rotation if pLeft was going
1858 // to end up damaged
1859 assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
1860 assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_relaxed )));
1862 // We have damaged pParent, pLR (now parent.child), and pNode (now
1863 // parent.child.right). pNode is the deepest. Perform as many fixes as we
1864 // can with the locks we've got.
1866 // We've already fixed the height for pNode, but it might still be outside
1867 // our allowable balance range. In that case a simple fix_height_locked()
1869 int nodeBalance = hLRR - hR;
1870 if ( nodeBalance < -1 || nodeBalance > 1 ) {
1871 // we need another rotation at pNode
1872 m_stat.onRotateAfterRLRotation();
1876 // pNode might also be damaged by being an unnecessary routing node
1877 if ( (pLRR == nullptr || hR == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1878 // repair involves splicing out pNode and maybe more rotations
1879 m_stat.onRemoveAfterRLRotation();
1883 // we've already fixed the height at pLRight, do we need a rotation here?
1884 int balanceLR = hLeft - hNode;
1885 if ( balanceLR < -1 || balanceLR > 1 ) {
1886 m_stat.onRotateAfterRLRotation();
1890 // try to fix the parent height while we've still got the lock
1891 return fix_height_locked( pParent );
1894 node_type * rotate_left_over_right_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRR, int hRLR )
1896 version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1897 version_type rightVersion = pRight->version( memory_model::memory_order_acquire );
1899 node_type * pPL = child( pParent, left_child );
1900 node_type * pRLL = child( pRLeft, left_child );
1901 node_type * pRLR = child( pRLeft, right_child );
1902 int hRLL = height_null( pRLL );
1904 begin_change( pNode, nodeVersion );
1905 begin_change( pRight, rightVersion );
1907 // fix up pNode links, careful about the order!
1908 pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
1909 if ( pRLL != nullptr )
1910 pRLL->m_pParent.store( pNode, memory_model::memory_order_relaxed );
1911 atomics::atomic_thread_fence( memory_model::memory_order_release );
1913 pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
1914 if ( pRLR != nullptr )
1915 pRLR->m_pParent.store( pRight, memory_model::memory_order_relaxed );
1916 atomics::atomic_thread_fence( memory_model::memory_order_release );
1918 pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1919 pRight->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1920 atomics::atomic_thread_fence( memory_model::memory_order_release );
1922 pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1923 pNode->m_pParent.store( pRLeft, memory_model::memory_order_relaxed );
1924 atomics::atomic_thread_fence( memory_model::memory_order_release );
1927 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
1929 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1930 pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1932 pRLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed );
1933 atomics::atomic_thread_fence( memory_model::memory_order_release );
1936 int hNode = 1 + std::max( hL, hRLL );
1937 set_height( pNode, hNode );
1938 int hRight = 1 + std::max( hRLR, hRR );
1939 set_height( pRight, hRight );
1940 set_height( pRLeft, 1 + std::max( hNode, hRight ));
1942 end_change( pNode, nodeVersion );
1943 end_change( pRight, rightVersion );
1944 m_stat.onRotateLeftOverRight();
1946 assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
1948 int nodeBalance = hRLL - hL;
1949 if ( nodeBalance < -1 || nodeBalance > 1 ) {
1950 m_stat.onRotateAfterLRRotation();
1954 if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
1955 m_stat.onRemoveAfterLRRotation();
1959 int balRL = hRight - hNode;
1960 if ( balRL < -1 || balRL > 1 ) {
1961 m_stat.onRotateAfterLRRotation();
1965 return fix_height_locked( pParent );
1970 }} // namespace cds::container
1972 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H