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->parent( 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, right_child, 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;
867 // get right child of root
868 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
870 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
871 if ( nChildVersion & node_type::shrinking ) {
872 m_stat.onRemoveRootWaitShrinking();
873 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
874 result = update_flags::retry;
876 else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
877 result = try_extract_minmax( nDir, func, m_pRoot, pChild, nChildVersion, removed_list );
880 result = update_flags::retry;
885 if ( result == update_flags::retry )
886 m_stat.onRemoveRetry();
891 template <typename Q>
892 mapped_type do_extract( Q const& key )
894 mapped_type pExtracted = nullptr;
898 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
903 template <typename Q, typename Less>
904 mapped_type do_extract_with( Q const& key, Less pred )
907 mapped_type pExtracted = nullptr;
910 cds::opt::details::make_comparator_from_less<Less>(),
911 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
919 static int height( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
922 return pNode->m_nHeight.load( order );
924 static void set_height( node_type * pNode, int h, atomics::memory_order order = memory_model::memory_order_relaxed )
927 pNode->m_nHeight.store( h, order );
929 static int height_null( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
931 return pNode ? height( pNode, order ) : 0;
934 template <typename Q, typename Compare, typename Func>
935 find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
937 assert( gc::is_locked() );
941 node_type * pChild = child( pNode, nDir );
943 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
944 return find_result::retry;
946 m_stat.onFindFailed();
947 return find_result::not_found;
950 int nCmp = cmp( key, pChild->m_key );
952 if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
954 node_scoped_lock l( m_Monitor, *pChild );
955 if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
957 m_stat.onFindSuccess();
958 return find_result::found;
963 m_stat.onFindFailed();
964 return find_result::not_found;
967 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
968 if ( nChildVersion & node_type::shrinking ) {
969 m_stat.onFindWaitShrinking();
970 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
972 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
973 return find_result::retry;
975 else if ( nChildVersion != node_type::unlinked && child( pNode, nDir ) == pChild )
977 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
978 return find_result::retry;
980 find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
981 if ( found != find_result::retry )
985 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
986 return find_result::retry;
988 m_stat.onFindRetry();
992 template <typename K, typename Compare, typename Func>
993 int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
995 assert( gc::is_locked() );
1000 // get right child of root
1001 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1003 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1004 if ( nChildVersion & node_type::shrinking ) {
1005 m_stat.onUpdateRootWaitShrinking();
1006 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1007 result = update_flags::retry;
1009 else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire ))
1010 result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1012 result = update_flags::retry;
1015 // the tree is empty
1016 if ( nFlags & update_flags::allow_insert ) {
1017 // insert into tree as right child of the root
1019 node_scoped_lock l( m_Monitor, *m_pRoot );
1020 if ( child( m_pRoot, right_child, memory_model::memory_order_acquire ) != nullptr ) {
1021 result = update_flags::retry;
1025 node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr );
1026 mapped_type pVal = funcUpdate( pNew );
1027 assert( pVal != nullptr );
1028 pNew->m_pValue.store( pVal, memory_model::memory_order_release );
1030 m_pRoot->child( pNew, right_child, memory_model::memory_order_relaxed );
1031 set_height( m_pRoot, 2 );
1035 m_stat.onInsertSuccess();
1036 return update_flags::result_inserted;
1039 return update_flags::failed;
1042 if ( result == update_flags::retry )
1043 m_stat.onUpdateRetry();
1049 template <typename K, typename Compare, typename Func>
1050 bool try_remove_root( K const& key, Compare cmp, Func func, rcu_disposer& disp )
1052 assert( gc::is_locked() );
1057 // get right child of root
1058 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1060 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1061 if ( nChildVersion & node_type::shrinking ) {
1062 m_stat.onRemoveRootWaitShrinking();
1063 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1064 result = update_flags::retry;
1066 else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
1067 result = try_remove( key, cmp, func, m_pRoot, pChild, nChildVersion, disp );
1070 result = update_flags::retry;
1075 if ( result == update_flags::retry )
1076 m_stat.onRemoveRetry();
1078 return result == update_flags::result_removed;
1082 template <typename K, typename Compare, typename Func>
1083 int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1085 assert( gc::is_locked() );
1086 assert( nVersion != node_type::unlinked );
1088 int nCmp = cmp( key, pNode->m_key );
1090 return try_update_node( nFlags, funcUpdate, pNode, nVersion, disp );
1094 node_type * pChild = child( pNode, nCmp );
1095 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1096 return update_flags::retry;
1098 if ( pChild == nullptr ) {
1100 if ( nFlags & update_flags::allow_insert )
1101 result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
1103 result = update_flags::failed;
1107 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1108 if ( nChildVersion & node_type::shrinking ) {
1109 m_stat.onUpdateWaitShrinking();
1110 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1112 result = update_flags::retry;
1114 else if ( pChild == child( pNode, nCmp )) {
1115 // this second read is important, because it is protected by nChildVersion
1117 // validate the read that our caller took to get to node
1118 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1119 return update_flags::retry;
1121 // At this point we know that the traversal our parent took to get to node is still valid.
1122 // The recursive implementation will validate the traversal from node to
1123 // child, so just prior to the node nVersion validation both traversals were definitely okay.
1124 // This means that we are no longer vulnerable to node shrinks, and we don't need
1125 // to validate node version any more.
1126 result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1129 result = update_flags::retry;
1132 if ( result == update_flags::retry ) {
1133 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1134 return update_flags::retry;
1135 m_stat.onUpdateRetry();
1142 template <typename K, typename Compare, typename Func>
1143 int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1145 assert( gc::is_locked() );
1146 assert( nVersion != node_type::unlinked );
1148 int nCmp = cmp( key, pNode->m_key );
1150 return try_remove_node( pParent, pNode, nVersion, func, disp );
1155 node_type * pChild = child( pNode, nCmp );
1156 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1157 return update_flags::retry;
1159 if ( pChild == nullptr )
1160 return update_flags::failed;
1163 result = update_flags::retry;
1164 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1165 if ( nChildVersion & node_type::shrinking ) {
1166 m_stat.onRemoveWaitShrinking();
1167 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1170 else if ( pChild == child( pNode, nCmp )) {
1171 // this second read is important, because it is protected by nChildVersion
1173 // validate the read that our caller took to get to node
1174 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1175 return update_flags::retry;
1177 // At this point we know that the traversal our parent took to get to node is still valid.
1178 // The recursive implementation will validate the traversal from node to
1179 // child, so just prior to the node nVersion validation both traversals were definitely okay.
1180 // This means that we are no longer vulnerable to node shrinks, and we don't need
1181 // to validate node version any more.
1182 result = try_remove( key, cmp, func, pNode, pChild, nChildVersion, disp );
1185 result = update_flags::retry;
1188 if ( result == update_flags::retry ) {
1189 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1190 return update_flags::retry;
1191 m_stat.onRemoveRetry();
1198 template <typename Func>
1199 int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1201 assert( gc::is_locked() );
1202 assert( nVersion != node_type::unlinked );
1206 node_type * pChild = child( pNode, nDir );
1207 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1208 return update_flags::retry;
1210 if ( pChild == nullptr ) {
1212 return try_remove_node( pParent, pNode, nVersion, func, disp );
1215 //result = update_flags::retry;
1216 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1217 if ( nChildVersion & node_type::shrinking ) {
1218 m_stat.onRemoveWaitShrinking();
1219 pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1221 result = update_flags::retry;
1223 else if ( pChild == child( pNode, nDir )) {
1224 // this second read is important, because it is protected by nChildVersion
1226 // validate the read that our caller took to get to node
1227 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1228 return update_flags::retry;
1230 // At this point we know that the traversal our parent took to get to node is still valid.
1231 // The recursive implementation will validate the traversal from node to
1232 // child, so just prior to the node nVersion validation both traversals were definitely okay.
1233 // This means that we are no longer vulnerable to node shrinks, and we don't need
1234 // to validate node version any more.
1235 result = try_extract_minmax( nDir, func, pNode, pChild, nChildVersion, disp );
1238 result = update_flags::retry;
1241 if ( result == update_flags::retry ) {
1242 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1243 return update_flags::retry;
1244 m_stat.onRemoveRetry();
1251 template <typename K, typename Func>
1252 int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
1256 auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
1257 mapped_type pVal = funcUpdate( pNew );
1258 assert( pVal != nullptr );
1259 pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1262 if ( c_bRelaxedInsert ) {
1263 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1264 || child( pNode, nDir ) != nullptr )
1266 m_stat.onInsertRetry();
1267 return update_flags::retry;
1270 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1273 node_type * pDamaged;
1275 assert( pNode != nullptr );
1276 node_scoped_lock l( m_Monitor, *pNode );
1278 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1279 || child( pNode, nDir ) != nullptr )
1281 if ( c_bRelaxedInsert ) {
1282 mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
1283 pNew->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1286 m_stat.onRelaxedInsertFailed();
1289 m_stat.onInsertRetry();
1290 return update_flags::retry;
1293 if ( !c_bRelaxedInsert )
1294 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1296 pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
1297 pDamaged = fix_height_locked( pNode );
1301 m_stat.onInsertSuccess();
1304 fix_height_and_rebalance( pDamaged, disp );
1305 m_stat.onInsertRebalanceRequired();
1308 return update_flags::result_inserted;
1311 template <typename Func>
1312 int try_update_node( int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1315 assert( pNode != nullptr );
1317 node_scoped_lock l( m_Monitor, *pNode );
1319 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1320 return update_flags::retry;
1322 if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
1323 m_stat.onUpdateUnlinked();
1324 return update_flags::retry;
1327 if ( pNode->is_valued( memory_model::memory_order_relaxed ) && !(nFlags & update_flags::allow_update) ) {
1328 m_stat.onInsertFailed();
1329 return update_flags::failed;
1332 pOld = pNode->value( memory_model::memory_order_relaxed );
1333 mapped_type pVal = funcUpdate( pNode );
1337 assert( pVal != nullptr );
1338 pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1343 disp.dispose_value(pOld);
1344 m_stat.onDisposeValue();
1347 m_stat.onUpdateSuccess();
1348 return update_flags::result_updated;
1351 template <typename Func>
1352 int try_remove_node( node_type * pParent, node_type * pNode, version_type nVersion, Func func, rcu_disposer& disp )
1354 assert( pParent != nullptr );
1355 assert( pNode != nullptr );
1357 if ( !pNode->is_valued( memory_model::memory_order_relaxed ) )
1358 return update_flags::failed;
1360 if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) {
1361 // pNode can be replaced with its child
1363 node_type * pDamaged;
1366 node_scoped_lock lp( m_Monitor, *pParent );
1367 if ( pParent->is_unlinked( memory_model::memory_order_relaxed ) || parent( pNode ) != pParent )
1368 return update_flags::retry;
1371 node_scoped_lock ln( m_Monitor, *pNode );
1372 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1373 return update_flags::retry;
1375 pOld = pNode->value( memory_model::memory_order_relaxed );
1377 return update_flags::failed;
1379 if ( !try_unlink_locked( pParent, pNode, disp ))
1380 return update_flags::retry;
1382 pDamaged = fix_height_locked( pParent );
1386 if ( func( pNode->m_key, pOld, disp )) // calls pOld disposer inside
1387 m_stat.onDisposeValue();
1389 m_stat.onExtractValue();
1392 fix_height_and_rebalance( pDamaged, disp );
1393 m_stat.onRemoveRebalanceRequired();
1397 // pNode is an internal with two children
1401 node_scoped_lock ln( m_Monitor, *pNode );
1402 pOld = pNode->value( memory_model::memory_order_relaxed );
1403 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1404 return update_flags::retry;
1406 return update_flags::failed;
1408 pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1412 if ( func( pNode->m_key, pOld, disp )) // calls pOld disposer inside
1413 m_stat.onDisposeValue();
1415 m_stat.onExtractValue();
1417 return update_flags::result_removed;
1420 bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1422 // pParent and pNode must be locked
1423 assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
1425 node_type * pParentLeft = child( pParent, left_child );
1426 node_type * pParentRight = child( pParent, right_child );
1427 if ( pNode != pParentLeft && pNode != pParentRight ) {
1428 // node is no longer a child of parent
1432 assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ) );
1433 assert( pParent == parent( pNode ));
1435 node_type * pLeft = child( pNode, left_child );
1436 node_type * pRight = child( pNode, right_child );
1437 if ( pLeft != nullptr && pRight != nullptr ) {
1438 // splicing is no longer possible
1441 node_type * pSplice = pLeft ? pLeft : pRight;
1443 if ( pParentLeft == pNode )
1444 pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
1446 pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
1449 pSplice->parent( pParent, memory_model::memory_order_relaxed );
1451 // Mark the node as unlinked
1452 pNode->version( node_type::unlinked, memory_model::memory_order_release );
1454 // The value will be disposed by calling function
1455 pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1457 disp.dispose( pNode );
1458 m_stat.onDisposeNode();
1465 private: // rotations
1467 int estimate_node_condition( node_type * pNode )
1469 node_type * pLeft = child( pNode, left_child );
1470 node_type * pRight = child( pNode, right_child );
1472 if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed ))
1473 return unlink_required;
1475 int h = height( pNode );
1476 int hL = height_null( pLeft );
1477 int hR = height_null( pRight );
1479 int hNew = 1 + std::max( hL, hR );
1480 int nBalance = hL - hR;
1482 if ( nBalance < -1 || nBalance > 1 )
1483 return rebalance_required;
1485 return h != hNew ? hNew : nothing_required;
1488 node_type * fix_height( node_type * pNode )
1490 assert( pNode != nullptr );
1491 node_scoped_lock l( m_Monitor, *pNode );
1492 return fix_height_locked( pNode );
1495 node_type * fix_height_locked( node_type * pNode )
1497 // pNode must be locked!!!
1498 int h = estimate_node_condition( pNode );
1500 case rebalance_required:
1501 case unlink_required:
1503 case nothing_required:
1506 set_height( pNode, h );
1507 return parent( pNode );
1511 void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
1513 while ( pNode && parent( pNode )) {
1514 int nCond = estimate_node_condition( pNode );
1515 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
1518 if ( nCond != unlink_required && nCond != rebalance_required )
1519 pNode = fix_height( pNode );
1521 node_type * pParent = parent( pNode );
1522 assert( pParent != nullptr );
1524 node_scoped_lock lp( m_Monitor, *pParent );
1525 if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode ) == pParent ) {
1526 node_scoped_lock ln( m_Monitor, *pNode );
1527 pNode = rebalance_locked( pParent, pNode, disp );
1534 node_type * rebalance_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1536 // pParent and pNode should be locked.
1537 // Returns a damaged node, or nullptr if no more rebalancing is necessary
1538 assert( parent( pNode ) == pParent );
1540 node_type * pLeft = child( pNode, left_child );
1541 node_type * pRight = child( pNode, right_child );
1543 if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1544 if ( try_unlink_locked( pParent, pNode, disp ))
1545 return fix_height_locked( pParent );
1547 // retry needed for pNode
1552 assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1554 int h = height( pNode );
1555 int hL = height_null( pLeft );
1556 int hR = height_null( pRight );
1557 int hNew = 1 + std::max( hL, hR );
1558 int balance = hL - hR;
1561 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
1562 else if ( balance < -1 )
1563 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
1564 else if ( hNew != h ) {
1565 set_height( pNode, hNew );
1567 // pParent is already locked
1568 return fix_height_locked( pParent );
1574 node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
1576 assert( parent( pNode ) == pParent );
1577 assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1579 // pParent and pNode is locked yet
1580 // pNode->pLeft is too large, we will rotate-right.
1581 // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
1584 assert( pLeft != nullptr );
1585 node_scoped_lock l( m_Monitor, *pLeft );
1586 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
1587 return pNode; // retry for pNode
1589 int hL = height( pLeft );
1591 return pNode; // retry
1593 node_type * pLRight = child( pLeft, right_child );
1594 int hLR = height_null( pLRight );
1595 node_type * pLLeft = child( pLeft, left_child );
1596 int hLL = height_null( pLLeft );
1600 return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1603 assert( pLRight != nullptr );
1605 node_scoped_lock lr( m_Monitor, *pLRight );
1606 if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
1607 return pNode; // retry
1609 hLR = height( pLRight );
1611 return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1613 int hLRL = height_null( child( pLRight, left_child ));
1614 int balance = hLL - hLRL;
1615 if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
1616 // nParent.child.left won't be damaged after a double rotation
1617 return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
1621 // focus on pLeft, if necessary pNode will be balanced later
1622 return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
1627 node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
1629 assert( parent( pNode ) == pParent );
1630 assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1632 // pParent and pNode is locked yet
1634 assert( pRight != nullptr );
1635 node_scoped_lock l( m_Monitor, *pRight );
1636 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
1637 return pNode; // retry for pNode
1639 int hR = height( pRight );
1640 if ( hL - hR >= -1 )
1641 return pNode; // retry
1643 node_type * pRLeft = child( pRight, left_child );
1644 int hRL = height_null( pRLeft );
1645 node_type * pRRight = child( pRight, right_child );
1646 int hRR = height_null( pRRight );
1648 return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1651 assert( pRLeft != nullptr );
1652 node_scoped_lock lrl( m_Monitor, *pRLeft );
1653 if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
1654 return pNode; // retry
1656 hRL = height( pRLeft );
1658 return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1660 node_type * pRLRight = child( pRLeft, right_child );
1661 int hRLR = height_null( pRLRight );
1662 int balance = hRR - hRLR;
1663 if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
1664 return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
1666 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
1670 static void begin_change( node_type * pNode, version_type version )
1672 assert(pNode->version(memory_model::memory_order_acquire) == version );
1673 assert( (version & node_type::shrinking) == 0 );
1674 pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
1676 static void end_change( node_type * pNode, version_type version )
1678 // Clear shrinking and unlinked flags and increment version
1679 pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
1682 node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
1684 version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1685 node_type * pParentLeft = child( pParent, left_child );
1687 begin_change( pNode, nodeVersion );
1689 pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1690 if ( pLRight != nullptr )
1691 pLRight->parent( pNode, memory_model::memory_order_relaxed );
1693 atomics::atomic_thread_fence( memory_model::memory_order_release );
1695 pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1696 pNode->parent( pLeft, memory_model::memory_order_relaxed );
1698 atomics::atomic_thread_fence( memory_model::memory_order_release );
1700 if ( pParentLeft == pNode )
1701 pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1703 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1704 pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
1706 pLeft->parent( pParent, memory_model::memory_order_relaxed );
1708 atomics::atomic_thread_fence( memory_model::memory_order_release );
1710 // fix up heights links
1711 int hNode = 1 + std::max( hLR, hR );
1712 set_height( pNode, hNode );
1713 set_height( pLeft, 1 + std::max( hLL, hNode ));
1715 end_change( pNode, nodeVersion );
1716 m_stat.onRotateRight();
1718 // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
1719 // parent.child). pNode is the deepest. Perform as many fixes as we can
1720 // with the locks we've got.
1722 // We've already fixed the height for pNode, but it might still be outside
1723 // our allowable balance range. In that case a simple fix_height_locked()
1725 int nodeBalance = hLR - hR;
1726 if ( nodeBalance < -1 || nodeBalance > 1 ) {
1727 // we need another rotation at pNode
1728 m_stat.onRotateAfterRightRotation();
1732 // we've fixed balance and height damage for pNode, now handle
1733 // extra-routing node damage
1734 if ( (pLRight == nullptr || hR == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) {
1735 // we need to remove pNode and then repair
1736 m_stat.onRemoveAfterRightRotation();
1740 // we've already fixed the height at pLeft, do we need a rotation here?
1741 int leftBalance = hLL - hNode;
1742 if ( leftBalance < -1 || leftBalance > 1 ) {
1743 m_stat.onRotateAfterRightRotation();
1747 // pLeft might also have routing node damage (if pLeft.left was null)
1748 if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_relaxed) ) {
1749 m_stat.onDamageAfterRightRotation();
1753 // try to fix the parent height while we've still got the lock
1754 return fix_height_locked( pParent );
1757 node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
1759 version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1760 node_type * pParentLeft = child( pParent, left_child );
1762 begin_change( pNode, nodeVersion );
1764 // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
1765 pNode->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1766 if ( pRLeft != nullptr )
1767 pRLeft->parent( pNode, memory_model::memory_order_relaxed );
1769 atomics::atomic_thread_fence( memory_model::memory_order_release );
1771 pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1772 pNode->parent( pRight, memory_model::memory_order_relaxed );
1774 atomics::atomic_thread_fence( memory_model::memory_order_release );
1776 if ( pParentLeft == pNode )
1777 pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
1779 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1780 pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1782 pRight->parent( pParent, memory_model::memory_order_relaxed );
1784 atomics::atomic_thread_fence( memory_model::memory_order_release );
1787 int hNode = 1 + std::max( hL, hRL );
1788 set_height( pNode, hNode );
1789 set_height( pRight, 1 + std::max( hNode, hRR ));
1791 end_change( pNode, nodeVersion );
1792 m_stat.onRotateLeft();
1794 int nodeBalance = hRL - hL;
1795 if ( nodeBalance < -1 || nodeBalance > 1 ) {
1796 m_stat.onRotateAfterLeftRotation();
1800 if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
1801 m_stat.onRemoveAfterLeftRotation();
1805 int rightBalance = hRR - hNode;
1806 if ( rightBalance < -1 || rightBalance > 1 ) {
1807 m_stat.onRotateAfterLeftRotation();
1811 if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_relaxed) ) {
1812 m_stat.onDamageAfterLeftRotation();
1816 return fix_height_locked( pParent );
1819 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 )
1821 version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1822 version_type leftVersion = pLeft->version( memory_model::memory_order_acquire );
1824 node_type * pPL = child( pParent, left_child );
1825 node_type * pLRL = child( pLRight, left_child );
1826 node_type * pLRR = child( pLRight, right_child );
1827 int hLRR = height_null( pLRR );
1829 begin_change( pNode, nodeVersion );
1830 begin_change( pLeft, leftVersion );
1832 // fix up pNode links, careful about the order!
1833 pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
1834 if ( pLRR != nullptr )
1835 pLRR->parent( pNode, memory_model::memory_order_relaxed );
1836 atomics::atomic_thread_fence( memory_model::memory_order_release );
1838 pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
1839 if ( pLRL != nullptr )
1840 pLRL->parent( pLeft, memory_model::memory_order_relaxed );
1841 atomics::atomic_thread_fence( memory_model::memory_order_release );
1843 pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
1844 pLeft->parent( pLRight, memory_model::memory_order_relaxed );
1845 atomics::atomic_thread_fence( memory_model::memory_order_release );
1847 pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
1848 pNode->parent( pLRight, memory_model::memory_order_relaxed );
1849 atomics::atomic_thread_fence( memory_model::memory_order_release );
1852 pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
1854 assert( child( pParent, right_child ) == pNode );
1855 pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
1857 pLRight->parent( pParent, memory_model::memory_order_relaxed );
1858 atomics::atomic_thread_fence( memory_model::memory_order_release );
1861 int hNode = 1 + std::max( hLRR, hR );
1862 set_height( pNode, hNode );
1863 int hLeft = 1 + std::max( hLL, hLRL );
1864 set_height( pLeft, hLeft );
1865 set_height( pLRight, 1 + std::max( hLeft, hNode ));
1867 end_change( pNode, nodeVersion );
1868 end_change( pLeft, leftVersion );
1869 m_stat.onRotateRightOverLeft();
1871 // caller should have performed only a single rotation if pLeft was going
1872 // to end up damaged
1873 assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
1874 assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_relaxed )));
1876 // We have damaged pParent, pLR (now parent.child), and pNode (now
1877 // parent.child.right). pNode is the deepest. Perform as many fixes as we
1878 // can with the locks we've got.
1880 // We've already fixed the height for pNode, but it might still be outside
1881 // our allowable balance range. In that case a simple fix_height_locked()
1883 int nodeBalance = hLRR - hR;
1884 if ( nodeBalance < -1 || nodeBalance > 1 ) {
1885 // we need another rotation at pNode
1886 m_stat.onRotateAfterRLRotation();
1890 // pNode might also be damaged by being an unnecessary routing node
1891 if ( (pLRR == nullptr || hR == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1892 // repair involves splicing out pNode and maybe more rotations
1893 m_stat.onRemoveAfterRLRotation();
1897 // we've already fixed the height at pLRight, do we need a rotation here?
1898 int balanceLR = hLeft - hNode;
1899 if ( balanceLR < -1 || balanceLR > 1 ) {
1900 m_stat.onRotateAfterRLRotation();
1904 // try to fix the parent height while we've still got the lock
1905 return fix_height_locked( pParent );
1908 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 )
1910 version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
1911 version_type rightVersion = pRight->version( memory_model::memory_order_acquire );
1913 node_type * pPL = child( pParent, left_child );
1914 node_type * pRLL = child( pRLeft, left_child );
1915 node_type * pRLR = child( pRLeft, right_child );
1916 int hRLL = height_null( pRLL );
1918 begin_change( pNode, nodeVersion );
1919 begin_change( pRight, rightVersion );
1921 // fix up pNode links, careful about the order!
1922 pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
1923 if ( pRLL != nullptr )
1924 pRLL->parent( pNode, memory_model::memory_order_relaxed );
1925 atomics::atomic_thread_fence( memory_model::memory_order_release );
1927 pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
1928 if ( pRLR != nullptr )
1929 pRLR->parent( pRight, memory_model::memory_order_relaxed );
1930 atomics::atomic_thread_fence( memory_model::memory_order_release );
1932 pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
1933 pRight->parent( pRLeft, memory_model::memory_order_relaxed );
1934 atomics::atomic_thread_fence( memory_model::memory_order_release );
1936 pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
1937 pNode->parent( pRLeft, memory_model::memory_order_relaxed );
1938 atomics::atomic_thread_fence( memory_model::memory_order_release );
1941 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
1943 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1944 pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
1946 pRLeft->parent( pParent, memory_model::memory_order_relaxed );
1947 atomics::atomic_thread_fence( memory_model::memory_order_release );
1950 int hNode = 1 + std::max( hL, hRLL );
1951 set_height( pNode, hNode );
1952 int hRight = 1 + std::max( hRLR, hRR );
1953 set_height( pRight, hRight );
1954 set_height( pRLeft, 1 + std::max( hNode, hRight ));
1956 end_change( pNode, nodeVersion );
1957 end_change( pRight, rightVersion );
1958 m_stat.onRotateLeftOverRight();
1960 assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
1962 int nodeBalance = hRLL - hL;
1963 if ( nodeBalance < -1 || nodeBalance > 1 ) {
1964 m_stat.onRotateAfterLRRotation();
1968 if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
1969 m_stat.onRemoveAfterLRRotation();
1973 int balRL = hRight - hNode;
1974 if ( balRL < -1 || balRL > 1 ) {
1975 m_stat.onRotateAfterLRRotation();
1979 return fix_height_locked( pParent );
1984 }} // namespace cds::container
1986 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H