3 #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
4 #define __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
7 #include <cds/intrusive/details/ellen_bintree_base.h>
8 #include <cds/opt/compare.h>
9 #include <cds/details/binary_functor_wrapper.h>
10 #include <cds/urcu/details/check_deadlock.h>
11 #include <cds/urcu/exempt_ptr.h>
13 namespace cds { namespace intrusive {
15 namespace ellen_bintree {
18 struct base_node<cds::urcu::gc<RCU> >: public basic_node
20 typedef basic_node base_class;
22 base_node * m_pNextRetired;
24 typedef cds::urcu::gc<RCU> gc ; ///< Garbage collector
26 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
27 explicit base_node( bool bInternal )
28 : basic_node( bInternal ? internal : 0 )
29 , m_pNextRetired( nullptr )
33 } // namespace ellen_bintree
36 /// Ellen's et al binary search tree (RCU specialization)
37 /** @ingroup cds_intrusive_map
38 @ingroup cds_intrusive_tree
39 @anchor cds_intrusive_EllenBinTree_rcu
42 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
44 %EllenBinTree is an unbalanced leaf-oriented binary search tree that implements the <i>set</i>
45 abstract data type. Nodes maintains child pointers but not parent pointers.
46 Every internal node has exactly two children, and all data of type \p T currently in
47 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
48 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
49 may or may not be in the set. \p Key type is a subset of \p T type.
50 There should be exactly defined a key extracting functor for converting object of type \p T to
51 object of type \p Key.
53 Due to \p extract_min and \p extract_max member functions the \p %EllenBinTree can act as
54 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
55 the priority value plus some uniformly distributed random value.
57 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
58 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
60 @note In the current implementation we do not use helping technique described in the original paper.
61 In Hazard Pointer schema helping is too complicated and does not give any observable benefits.
62 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
63 the operation done. Such solution allows greatly simplify the implementation of tree.
65 <b>Template arguments</b> :
66 - \p RCU - one of \ref cds_urcu_gc "RCU type"
67 - \p Key - key type, a subset of \p T
68 - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
69 (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
70 (for \p ellen_bintree::member_hook).
71 - \p Traits - tree traits, default is \p ellen_bintree::traits
72 It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
73 instead of \p Traits template argument.
75 @anchor cds_intrusive_EllenBinTree_rcu_less
76 <b>Predicate requirements</b>
78 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
79 of type \p T and \p Key in any combination.
80 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
82 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
89 bool operator()( Foo const& v1, Foo const& v2 ) const
90 { return v1.m_strKey < v2.m_strKey ; }
92 bool operator()( Foo const& v, std::string const& s ) const
93 { return v.m_strKey < s ; }
95 bool operator()( std::string const& s, Foo const& v ) const
96 { return s < v.m_strKey ; }
98 // Support comparing std::string and char const *
99 bool operator()( std::string const& s, char const * p ) const
100 { return s.compare(p) < 0 ; }
102 bool operator()( Foo const& v, char const * p ) const
103 { return v.m_strKey.compare(p) < 0 ; }
105 bool operator()( char const * p, std::string const& s ) const
106 { return s.compare(p) > 0; }
108 bool operator()( char const * p, Foo const& v ) const
109 { return v.m_strKey.compare(p) > 0; }
113 @note Before including <tt><cds/intrusive/ellen_bintree_rcu.h></tt> you should include appropriate RCU header file,
114 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
116 @anchor cds_intrusive_EllenBinTree_usage
119 Suppose we have the following Foo struct with string key type:
122 std::string m_strKey ; // The key
123 //... // other non-key data
127 We want to utilize RCU-based \p %cds::intrusive::EllenBinTree set for \p Foo data.
128 We may use base hook or member hook. Consider base hook variant.
129 First, we need deriving \p Foo struct from \p cds::intrusive::ellen_bintree::node:
131 #include <cds/urcu/general_buffered.h>
132 #include <cds/intrusive/ellen_bintree_rcu.h>
135 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
137 struct Foo: public cds::intrusive:ellen_bintree::node< gpb_rcu >
139 std::string m_strKey ; // The key
140 //... // other non-key data
144 Second, we need to implement auxiliary structures and functors:
145 - key extractor functor for extracting the key from \p Foo object.
146 Such functor is necessary because the tree internal nodes store the keys.
147 - \p less predicate. We want our set should accept \p std::string
148 and <tt>char const *</tt> parameters for searching, so our \p less
149 predicate will not be trivial, see below.
150 - item counting feature: we want our set's \p size() member function
151 returns actual item count.
154 // Key extractor functor
155 struct my_key_extractor
157 void operator ()( std::string& key, Foo const& src ) const
165 bool operator()( Foo const& v1, Foo const& v2 ) const
166 { return v1.m_strKey < v2.m_strKey ; }
168 bool operator()( Foo const& v, std::string const& s ) const
169 { return v.m_strKey < s ; }
171 bool operator()( std::string const& s, Foo const& v ) const
172 { return s < v.m_strKey ; }
174 // Support comparing std::string and char const *
175 bool operator()( std::string const& s, char const * p ) const
176 { return s.compare(p) < 0 ; }
178 bool operator()( Foo const& v, char const * p ) const
179 { return v.m_strKey.compare(p) < 0 ; }
181 bool operator()( char const * p, std::string const& s ) const
182 { return s.compare(p) > 0; }
184 bool operator()( char const * p, Foo const& v ) const
185 { return v.m_strKey.compare(p) > 0; }
188 // Tree traits for our set
189 // It is necessary to specify only those typedefs that differ from
190 // cds::intrusive::ellen_bintree::traits defaults.
191 struct set_traits: public cds::intrusive::ellen_bintree::traits
193 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > > hook;
194 typedef my_key_extractor key_extractor;
195 typedef my_less less;
196 typedef cds::atomicity::item_counter item_counter;
200 Now we declare \p %EllenBinTree set and use it:
202 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, set_traits > set_type;
208 Instead of declaring \p set_traits type traits we can use option-based syntax with
209 \p ellen_bintree::make_traits metafunction, for example:
211 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo,
212 typename cds::intrusive::ellen_bintree::make_traits<
213 cds::opt::hook< cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > >
214 ,cds::intrusive::ellen_bintree::key_extractor< my_key_extractor >
215 ,cds::opt::less< my_less >
216 ,cds::opt::item_counter< cds::atomicity::item_counter >
221 Functionally, \p set_type and \p set_type2 are equivalent.
223 <b>Member-hooked tree</b>
225 Sometimes, we cannot use base hook, for example, when the \p Foo structure is external.
226 In such case we can use member hook feature.
228 #include <cds/urcu/general_buffered.h>
229 #include <cds/intrusive/ellen_bintree_rcu.h>
231 // Struct Foo is external and its declaration cannot be modified.
233 std::string m_strKey ; // The key
234 //... // other non-key data
238 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
244 cds::intrusive:ellen_bintree::node< gpb_rcu > set_hook; // member hook
247 // Key extractor functor
248 struct member_key_extractor
250 void operator ()( std::string& key, MyFoo const& src ) const
252 key = src.m_foo.m_strKey;
258 bool operator()( MyFoo const& v1, MyFoo const& v2 ) const
259 { return v1.m_foo.m_strKey < v2.m_foo.m_strKey ; }
261 bool operator()( MyFoo const& v, std::string const& s ) const
262 { return v.m_foo.m_strKey < s ; }
264 bool operator()( std::string const& s, MyFoo const& v ) const
265 { return s < v.m_foo.m_strKey ; }
267 // Support comparing std::string and char const *
268 bool operator()( std::string const& s, char const * p ) const
269 { return s.compare(p) < 0 ; }
271 bool operator()( MyFoo const& v, char const * p ) const
272 { return v.m_foo.m_strKey.compare(p) < 0 ; }
274 bool operator()( char const * p, std::string const& s ) const
275 { return s.compare(p) > 0; }
277 bool operator()( char const * p, MyFoo const& v ) const
278 { return v.m_foo.m_strKey.compare(p) > 0; }
281 // Tree traits for our member-based set
282 struct member_set_traits: public cds::intrusive::ellen_bintree::traits
284 cds::intrusive::ellen_bintree::member_hook< offsetof(MyFoo, set_hook), cds::opt::gc<gpb_rcu> > > hook;
285 typedef member_key_extractor key_extractor;
286 typedef member_less less;
287 typedef cds::atomicity::item_counter item_counter;
290 // Tree containing MyFoo objects
291 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, MyFoo, member_set_traits > member_set_type;
293 member_set_type theMemberSet;
296 <b>Multiple containers</b>
298 Sometimes we need that our \p Foo struct should be used in several different containers.
299 Suppose, \p Foo struct has two key fields:
302 std::string m_strKey ; // string key
303 int m_nKey ; // int key
304 //... // other non-key data fields
308 We want to build two intrusive \p %EllenBinTree sets: one indexed on \p Foo::m_strKey field,
309 another indexed on \p Foo::m_nKey field. To decide such case we should use a tag option for
312 #include <cds/urcu/general_buffered.h>
313 #include <cds/intrusive/ellen_bintree_rcu.h>
316 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
318 // Declare tag structs
319 struct int_tag ; // int key tag
320 struct string_tag ; // string key tag
322 // Foo struct is derived from two ellen_bintree::node class
323 // with different tags
325 : public cds::intrusive::ellen_bintree::node< gpb_rcu, cds::opt::tag< string_tag > >
326 , public cds::intrusive::ellen_bintree::node< gpb_rcu >, cds::opt::tag< int_tag >
328 std::string m_strKey ; // string key
329 int m_nKey ; // int key
330 //... // other non-key data fields
333 // String key extractor functor
334 struct string_key_extractor
336 void operator ()( std::string& key, Foo const& src ) const
342 // Int key extractor functor
343 struct int_key_extractor
345 void operator ()( int& key, Foo const& src ) const
351 // String less predicate
353 bool operator()( Foo const& v1, Foo const& v2 ) const
354 { return v1.m_strKey < v2.m_strKey ; }
356 bool operator()( Foo const& v, std::string const& s ) const
357 { return v.m_strKey < s ; }
359 bool operator()( std::string const& s, Foo const& v ) const
360 { return s < v.m_strKey ; }
362 // Support comparing std::string and char const *
363 bool operator()( std::string const& s, char const * p ) const
364 { return s.compare(p) < 0 ; }
366 bool operator()( Foo const& v, char const * p ) const
367 { return v.m_strKey.compare(p) < 0 ; }
369 bool operator()( char const * p, std::string const& s ) const
370 { return s.compare(p) > 0; }
372 bool operator()( char const * p, Foo const& v ) const
373 { return v.m_strKey.compare(p) > 0; }
376 // Int less predicate
378 bool operator()( Foo const& v1, Foo const& v2 ) const
379 { return v1.m_nKey < v2.m_nKey ; }
381 bool operator()( Foo const& v, int n ) const
382 { return v.m_nKey < n ; }
384 bool operator()( int n, Foo const& v ) const
385 { return n < v.m_nKey ; }
388 // Type traits for string-indexed set
389 struct string_set_traits: public cds::intrusive::ellen_bintree::traits
391 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< string_tag > > hook;
392 typedef string_key_extractor key_extractor;
393 typedef string_less less;
394 typedef cds::atomicity::item_counter item_counter;
397 // Type traits for int-indexed set
398 struct int_set_traits: public cds::intrusive::ellen_bintree::traits
400 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< int_tag > > hook;
401 typedef int_key_extractor key_extractor;
402 typedef int_less less;
403 typedef cds::atomicity::item_counter item_counter;
406 // Declare string-indexed set
407 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, string_set_traits > string_set_type;
408 string_set_type theStringSet;
410 // Declare int-indexed set
411 typedef cds::intrusive::EllenBinTree< gpb_rcu, int, Foo, int_set_traits > int_set_type;
412 int_set_type theIntSet;
414 // Now we can use theStringSet and theIntSet in our program
418 template < class RCU,
421 #ifdef CDS_DOXYGEN_INVOKED
422 class Traits = ellen_bintree::traits
427 class EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
430 typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
431 typedef Key key_type; ///< type of a key stored in internal nodes; key is a part of \p value_type
432 typedef T value_type; ///< type of value stored in the binary tree
433 typedef Traits traits; ///< Traits template parameter
435 typedef typename traits::hook hook; ///< hook type
436 typedef typename hook::node_type node_type; ///< node type
438 typedef typename traits::disposer disposer; ///< leaf node disposer
439 typedef typename traits::back_off back_off; ///< back-off strategy
443 typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
444 typedef node_type leaf_node; ///< Leaf node type
445 typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node; ///< Internal node type
446 typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc; ///< Update descriptor
447 typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
451 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > exempt_ptr; ///< pointer to extracted node
454 # ifdef CDS_DOXYGEN_INVOKED
455 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
456 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
458 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
459 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
461 static internal_node const& to_internal_node( tree_node const& n )
463 assert( n.is_internal() );
464 return static_cast<internal_node const&>( n );
467 static leaf_node const& to_leaf_node( tree_node const& n )
469 assert( n.is_leaf() );
470 return static_cast<leaf_node const&>( n );
475 typedef typename traits::item_counter item_counter; ///< Item counting policy used
476 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
477 typedef typename traits::stat stat; ///< internal statistics type
478 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
479 typedef typename traits::key_extractor key_extractor; ///< key extracting functor
481 typedef typename traits::node_allocator node_allocator; ///< Internal node allocator
482 typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
484 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
486 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
490 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
492 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock > check_deadlock_policy;
494 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
495 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
497 struct search_result {
498 internal_node * pGrandParent;
499 internal_node * pParent;
501 update_ptr updParent;
502 update_ptr updGrandParent;
503 bool bRightLeaf ; // true if pLeaf is right child of pParent, false otherwise
504 bool bRightParent ; // true if pParent is right child of pGrandParent, false otherwise
507 :pGrandParent( nullptr )
511 ,bRightParent( false )
518 internal_node m_Root; ///< Tree root node (key= Infinite2)
519 leaf_node m_LeafInf1;
520 leaf_node m_LeafInf2;
523 item_counter m_ItemCounter; ///< item counter
524 mutable stat m_Stat; ///< internal statistics
528 static void free_leaf_node( value_type * p )
533 internal_node * alloc_internal_node() const
535 m_Stat.onInternalNodeCreated();
536 internal_node * pNode = cxx_node_allocator().New();
541 static void free_internal_node( internal_node * pNode )
543 cxx_node_allocator().Delete( pNode );
546 struct internal_node_deleter {
547 void operator()( internal_node * p) const
549 free_internal_node( p );
553 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
555 update_desc * alloc_update_desc() const
557 m_Stat.onUpdateDescCreated();
558 return cxx_update_desc_allocator().New();
561 static void free_update_desc( update_desc * pDesc )
563 cxx_update_desc_allocator().Delete( pDesc );
568 update_desc * pUpdateHead;
569 tree_node * pNodeHead;
572 class forward_iterator
574 update_desc * m_pUpdate;
578 forward_iterator( retired_list const& l )
579 : m_pUpdate( l.pUpdateHead )
580 , m_pNode( l.pNodeHead )
584 : m_pUpdate( nullptr )
588 cds::urcu::retired_ptr operator *()
591 return cds::urcu::retired_ptr( reinterpret_cast<void *>( m_pUpdate ),
592 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
595 if ( m_pNode->is_leaf() ) {
596 return cds::urcu::retired_ptr( reinterpret_cast<void *>( node_traits::to_value_ptr( static_cast<leaf_node *>( m_pNode ))),
597 reinterpret_cast< cds::urcu::free_retired_ptr_func>( free_leaf_node ) );
600 return cds::urcu::retired_ptr( reinterpret_cast<void *>( static_cast<internal_node *>( m_pNode ) ),
601 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_internal_node ) );
604 return cds::urcu::retired_ptr( nullptr,
605 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
611 m_pUpdate = m_pUpdate->pNextRetire;
615 m_pNode = m_pNode->m_pNextRetired;
618 friend bool operator ==( forward_iterator const& i1, forward_iterator const& i2 )
620 return i1.m_pUpdate == i2.m_pUpdate && i1.m_pNode == i2.m_pNode;
622 friend bool operator !=( forward_iterator const& i1, forward_iterator const& i2 )
624 return !( i1 == i2 );
630 : pUpdateHead( nullptr )
631 , pNodeHead( nullptr )
636 gc::batch_retire( forward_iterator(*this), forward_iterator() );
639 void push( update_desc * p )
641 p->pNextRetire = pUpdateHead;
645 void push( tree_node * p )
647 p->m_pNextRetired = pNodeHead;
652 void retire_node( tree_node * pNode, retired_list& rl ) const
654 if ( pNode->is_leaf() ) {
655 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
656 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
659 assert( static_cast<internal_node *>( pNode ) != &m_Root );
660 m_Stat.onInternalNodeDeleted();
665 void retire_update_desc( update_desc * p, retired_list& rl, bool bDirect ) const
667 m_Stat.onUpdateDescDeleted();
669 free_update_desc( p );
674 void make_empty_tree()
676 m_Root.infinite_key( 2 );
677 m_LeafInf1.infinite_key( 1 );
678 m_LeafInf2.infinite_key( 2 );
679 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
680 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
685 /// Default constructor
688 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
700 The function inserts \p val in the tree if it does not contain
701 an item with key equal to \p val.
703 The function applies RCU lock internally.
705 Returns \p true if \p val is placed into the set, \p false otherwise.
707 bool insert( value_type& val )
709 return insert( val, []( value_type& ) {} );
714 This function is intended for derived non-intrusive containers.
716 The function allows to split creating of new item into two part:
717 - create item with key only
718 - insert new item into the tree
719 - if inserting is success, calls \p f functor to initialize value-field of \p val.
721 The functor signature is:
723 void func( value_type& val );
725 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
726 \p val no any other changes could be made on this tree's item by concurrent threads.
727 The user-defined functor is called only if the inserting is success.
729 RCU \p synchronize method can be called. RCU should not be locked.
731 template <typename Func>
732 bool insert( value_type& val, Func f )
734 check_deadlock_policy::check();
736 unique_internal_node_ptr pNewInternal;
737 retired_list updRetire;
745 if ( search( res, val, node_compare() )) {
746 if ( pNewInternal.get() )
747 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
748 m_Stat.onInsertFailed();
752 if ( res.updParent.bits() != update_desc::Clean )
753 help( res.updParent, updRetire );
755 if ( !pNewInternal.get() )
756 pNewInternal.reset( alloc_internal_node() );
758 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
760 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
766 m_Stat.onInsertRetry();
771 m_Stat.onInsertSuccess();
776 /// Ensures that the \p val exists in the tree
778 The operation performs inserting or changing data with lock-free manner.
780 If the item \p val is not found in the tree, then \p val is inserted into the tree.
781 Otherwise, the functor \p func is called with item found.
782 The functor signature is:
784 void func( bool bNew, value_type& item, value_type& val );
787 - \p bNew - \p true if the item has been inserted, \p false otherwise
788 - \p item - item of the tree
789 - \p val - argument \p val passed into the \p ensure function
790 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
791 refer to the same thing.
793 The functor can change non-key fields of the \p item; however, \p func must guarantee
794 that during changing no any other modifications could be made on this item by concurrent threads.
796 RCU \p synchronize method can be called. RCU should not be locked.
798 Returns <tt>std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
799 \p second is \p true if new item has been added or \p false if the item with \p key
800 already is in the tree.
802 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
804 template <typename Func>
805 std::pair<bool, bool> ensure( value_type& val, Func func )
807 check_deadlock_policy::check();
809 unique_internal_node_ptr pNewInternal;
810 retired_list updRetire;
818 if ( search( res, val, node_compare() )) {
819 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
820 if ( pNewInternal.get() )
821 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
822 m_Stat.onEnsureExist();
823 return std::make_pair( true, false );
826 if ( res.updParent.bits() != update_desc::Clean )
827 help( res.updParent, updRetire );
829 if ( !pNewInternal.get() )
830 pNewInternal.reset( alloc_internal_node() );
832 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
833 func( true, val, val );
834 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
840 m_Stat.onEnsureRetry();
845 m_Stat.onEnsureNew();
847 return std::make_pair( true, true );
850 /// Unlinks the item \p val from the tree
852 The function searches the item \p val in the tree and unlink it from the tree
853 if it is found and is equal to \p val.
855 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
856 and deletes the item found. \p unlink finds an item by key and deletes it
857 only if \p val is an item of the tree, i.e. the pointer to item found
858 is equal to <tt> &val </tt>.
860 RCU \p synchronize method can be called. RCU should not be locked.
862 The \ref disposer specified in \p Traits class template parameter is called
863 by garbage collector \p GC asynchronously.
865 The function returns \p true if success and \p false otherwise.
867 bool unlink( value_type& val )
869 return erase_( val, node_compare(),
870 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
871 [](value_type const&) {} );
874 /// Deletes the item from the tree
875 /** \anchor cds_intrusive_EllenBinTree_rcu_erase
876 The function searches an item with key equal to \p key in the tree,
877 unlinks it from the tree, and returns \p true.
878 If the item with key equal to \p key is not found the function return \p false.
880 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
882 RCU \p synchronize method can be called. RCU should not be locked.
884 template <typename Q>
885 bool erase( const Q& key )
887 return erase_( key, node_compare(),
888 []( Q const&, leaf_node const& ) -> bool { return true; },
889 [](value_type const&) {} );
892 /// Delete the item from the tree with comparing functor \p pred
894 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
895 but \p pred predicate is used for key comparing.
896 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
897 "Predicate requirements".
898 \p pred must imply the same element order as the comparator used for building the tree.
900 template <typename Q, typename Less>
901 bool erase_with( const Q& key, Less pred )
903 typedef ellen_bintree::details::compare<
906 opt::details::make_comparator_from_less<Less>,
910 return erase_( key, compare_functor(),
911 []( Q const&, leaf_node const& ) -> bool { return true; },
912 [](value_type const&) {} );
915 /// Deletes the item from the tree
916 /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
917 The function searches an item with key equal to \p key in the tree,
918 call \p f functor with item found, unlinks it from the tree, and returns \p true.
919 The \ref disposer specified in \p Traits class template parameter is called
920 by garbage collector \p GC asynchronously.
922 The \p Func interface is
925 void operator()( value_type const& item );
929 If the item with key equal to \p key is not found the function return \p false.
931 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
933 RCU \p synchronize method can be called. RCU should not be locked.
935 template <typename Q, typename Func>
936 bool erase( Q const& key, Func f )
938 return erase_( key, node_compare(),
939 []( Q const&, leaf_node const& ) -> bool { return true; },
943 /// Delete the item from the tree with comparing functor \p pred
945 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
946 but \p pred predicate is used for key comparing.
947 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
948 "Predicate requirements".
949 \p pred must imply the same element order as the comparator used for building the tree.
951 template <typename Q, typename Less, typename Func>
952 bool erase_with( Q const& key, Less pred, Func f )
954 typedef ellen_bintree::details::compare<
957 opt::details::make_comparator_from_less<Less>,
961 return erase_( key, compare_functor(),
962 []( Q const&, leaf_node const& ) -> bool { return true; },
966 /// Extracts an item with minimal key from the tree
968 The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p result parameter.
969 If the tree is empty the function returns \p false.
971 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
972 It means that the function gets leftmost leaf of the tree and tries to unlink it.
973 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
974 So, the function returns the item with minimum key at the moment of tree traversing.
976 RCU \p synchronize method can be called. RCU should NOT be locked.
977 The function does not call the disposer for the item found.
978 The disposer will be implicitly invoked when \p result object is destroyed or when
979 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
980 @note Before reusing \p result object you should call its \p release() method.
982 bool extract_min(exempt_ptr& result)
984 return extract_min_(result);
987 /// Extracts an item with maximal key from the tree
989 The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p result prameter.
990 If the tree is empty the function returns \p false.
992 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
993 It means that the function gets rightmost leaf of the tree and tries to unlink it.
994 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
995 So, the function returns the item with maximum key at the moment of tree traversing.
997 RCU \p synchronize method can be called. RCU should NOT be locked.
998 The function does not call the disposer for the item found.
999 The disposer will be implicitly invoked when \p result object is destroyed or when
1000 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1001 @note Before reusing \p result object you should call its \p release() method.
1003 bool extract_max(exempt_ptr& result)
1005 return extract_max_(result);
1008 /// Extracts an item from the tree
1009 /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1010 The function searches an item with key equal to \p key in the tree,
1011 unlinks it, and returns pointer to an item found in \p result parameter.
1012 If the item with the key equal to \p key is not found the function returns \p false.
1014 RCU \p synchronize method can be called. RCU should NOT be locked.
1015 The function does not call the disposer for the item found.
1016 The disposer will be implicitly invoked when \p result object is destroyed or when
1017 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1018 @note Before reusing \p result object you should call its \p release() method.
1020 template <typename Q>
1021 bool extract( exempt_ptr& result, Q const& key )
1023 return extract_( result, key, node_compare() );
1026 /// Extracts an item from the set using \p pred for searching
1028 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_extract "extract(exempt_ptr&, Q const&)"
1029 but \p pred is used for key compare.
1030 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1031 "predicate requirements".
1032 \p pred must imply the same element order as the comparator used for building the tree.
1034 template <typename Q, typename Less>
1035 bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
1037 return extract_with_( dest, key, pred );
1040 /// Finds the key \p key
1041 /** @anchor cds_intrusive_EllenBinTree_rcu_find_val
1042 The function searches the item with key equal to \p key
1043 and returns \p true if it is found, and \p false otherwise.
1045 Note the hash functor specified for class \p Traits template parameter
1046 should accept a parameter of type \p Q that can be not the same as \p value_type.
1048 The function applies RCU lock internally.
1050 template <typename Q>
1051 bool find( Q const& key ) const
1055 if ( search( res, key, node_compare() )) {
1056 m_Stat.onFindSuccess();
1060 m_Stat.onFindFailed();
1064 /// Finds the key \p key with comparing functor \p pred
1066 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)"
1067 but \p pred is used for key compare.
1068 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1069 "Predicate requirements".
1070 \p pred must imply the same element order as the comparator used for building the tree.
1071 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1073 template <typename Q, typename Less>
1074 bool find_with( Q const& key, Less pred ) const
1076 typedef ellen_bintree::details::compare<
1079 opt::details::make_comparator_from_less<Less>,
1085 if ( search( res, key, compare_functor() )) {
1086 m_Stat.onFindSuccess();
1089 m_Stat.onFindFailed();
1093 /// Finds the key \p key
1094 /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1095 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1096 The interface of \p Func functor is:
1099 void operator()( value_type& item, Q& key );
1102 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1104 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1105 that \p item cannot be disposed during functor is executing.
1106 The functor does not serialize simultaneous access to the tree \p item. If such access is
1107 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1109 The function applies RCU lock internally.
1111 The function returns \p true if \p key is found, \p false otherwise.
1113 template <typename Q, typename Func>
1114 bool find( Q& key, Func f ) const
1116 return find_( key, f );
1119 template <typename Q, typename Func>
1120 bool find( Q const& key, Func f ) const
1122 return find_( key, f );
1126 /// Finds the key \p key with comparing functor \p pred
1128 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1129 but \p pred is used for key comparison.
1130 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1131 "Predicate requirements".
1132 \p pred must imply the same element order as the comparator used for building the tree.
1134 template <typename Q, typename Less, typename Func>
1135 bool find_with( Q& key, Less pred, Func f ) const
1137 return find_with_( key, pred, f );
1140 template <typename Q, typename Less, typename Func>
1141 bool find_with( Q const& key, Less pred, Func f ) const
1143 return find_with_( key, pred, f );
1147 /// Finds \p key and return the item found
1148 /** \anchor cds_intrusive_EllenBinTree_rcu_get
1149 The function searches the item with key equal to \p key and returns the pointer to item found.
1150 If \p key is not found it returns \p nullptr.
1152 RCU should be locked before call the function.
1153 Returned pointer is valid while RCU is locked.
1155 template <typename Q>
1156 value_type * get( Q const& key ) const
1158 return get_( key, node_compare() );
1161 /// Finds \p key with \p pred predicate and return the item found
1163 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1164 but \p pred is used for comparing the keys.
1166 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1168 \p pred must imply the same element order as the comparator used for building the tree.
1170 template <typename Q, typename Less>
1171 value_type * get_with( Q const& key, Less pred ) const
1173 typedef ellen_bintree::details::compare<
1176 opt::details::make_comparator_from_less<Less>,
1180 return get_( key, compare_functor());
1183 /// Checks if the tree is empty
1186 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1189 /// Clears the tree (thread safe, not atomic)
1191 The function unlink all items from the tree.
1192 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1196 assert( set.empty() );
1198 the assertion could be raised.
1200 For each leaf the \ref disposer will be called after unlinking.
1202 RCU \p synchronize method can be called. RCU should not be locked.
1207 while ( extract_min(ep) )
1211 /// Clears the tree (not thread safe)
1213 This function is not thread safe and may be called only when no other thread deals with the tree.
1214 The function is used in the tree destructor.
1221 internal_node * pParent = nullptr;
1222 internal_node * pGrandParent = nullptr;
1223 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1225 // Get leftmost leaf
1226 while ( pLeaf->is_internal() ) {
1227 pGrandParent = pParent;
1228 pParent = static_cast<internal_node *>( pLeaf );
1229 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1232 if ( pLeaf->infinite_key()) {
1233 // The tree is empty
1237 // Remove leftmost leaf and its parent node
1238 assert( pGrandParent );
1240 assert( pLeaf->is_leaf() );
1242 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1243 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
1244 free_internal_node( pParent );
1248 /// Returns item count in the tree
1250 Only leaf nodes containing user data are counted.
1252 The value returned depends on item counter type provided by \p Traits template parameter.
1253 If it is \p atomicity::empty_item_counter this function always returns 0.
1255 The function is not suitable for checking the tree emptiness, use \p empty()
1256 member function for that.
1260 return m_ItemCounter;
1263 /// Returns const reference to internal statistics
1264 stat const& statistics() const
1269 /// Checks internal consistency (not atomic, not thread-safe)
1271 The debugging function to check internal consistency of the tree.
1273 bool check_consistency() const
1275 return check_consistency( &m_Root );
1281 bool check_consistency( internal_node const * pRoot ) const
1283 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1284 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1288 if ( node_compare()( *pLeft, *pRoot ) < 0
1289 && node_compare()( *pRoot, *pRight ) <= 0
1290 && node_compare()( *pLeft, *pRight ) < 0 )
1293 if ( pLeft->is_internal() )
1294 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
1297 if ( bRet && pRight->is_internal() )
1298 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1306 void help( update_ptr pUpdate, retired_list& rl )
1309 switch ( pUpdate.bits() ) {
1310 case update_desc::IFlag:
1311 help_insert( pUpdate.ptr() );
1312 m_Stat.onHelpInsert();
1314 case update_desc::DFlag:
1315 //help_delete( pUpdate.ptr(), rl );
1316 //m_Stat.onHelpDelete();
1318 case update_desc::Mark:
1319 //help_marked( pUpdate.ptr() );
1320 //m_Stat.onHelpMark();
1326 void help_insert( update_desc * pOp )
1328 assert( gc::is_locked() );
1330 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1331 if ( pOp->iInfo.bRightLeaf ) {
1332 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1333 memory_model::memory_order_release, atomics::memory_order_relaxed );
1336 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1337 memory_model::memory_order_release, atomics::memory_order_relaxed );
1340 update_ptr cur( pOp, update_desc::IFlag );
1341 pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1342 memory_model::memory_order_release, atomics::memory_order_relaxed );
1345 bool check_delete_precondition( search_result& res )
1347 assert( res.pGrandParent != nullptr );
1350 static_cast<internal_node *>( res.bRightParent
1351 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1352 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1355 static_cast<leaf_node *>( res.bRightLeaf
1356 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1357 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1361 bool help_delete( update_desc * pOp, retired_list& rl )
1363 assert( gc::is_locked() );
1365 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1366 update_ptr pMark( pOp, update_desc::Mark );
1367 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1368 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1371 retire_node( pOp->dInfo.pParent, rl );
1372 // For extract operations the leaf should NOT be disposed
1373 if ( pOp->dInfo.bDisposeLeaf )
1374 retire_node( pOp->dInfo.pLeaf, rl );
1375 retire_update_desc( pOp, rl, false );
1379 else if ( pUpdate == pMark ) {
1380 // some other thread is processing help_marked()
1382 m_Stat.onHelpMark();
1386 // pUpdate has been changed by CAS
1387 help( pUpdate, rl );
1389 // Undo grandparent dInfo
1390 update_ptr pDel( pOp, update_desc::DFlag );
1391 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1392 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1394 retire_update_desc( pOp, rl, false );
1400 void help_marked( update_desc * pOp )
1402 assert( gc::is_locked() );
1404 tree_node * p = pOp->dInfo.pParent;
1405 if ( pOp->dInfo.bRightParent ) {
1406 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1407 pOp->dInfo.bRightLeaf
1408 ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1409 : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1410 memory_model::memory_order_release, atomics::memory_order_relaxed );
1413 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1414 pOp->dInfo.bRightLeaf
1415 ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1416 : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1417 memory_model::memory_order_release, atomics::memory_order_relaxed );
1420 update_ptr upd( pOp, update_desc::DFlag );
1421 pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1422 memory_model::memory_order_release, atomics::memory_order_relaxed );
1425 template <typename KeyValue, typename Compare>
1426 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1428 assert( gc::is_locked() );
1430 internal_node * pParent;
1431 internal_node * pGrandParent = nullptr;
1433 update_ptr updParent;
1434 update_ptr updGrandParent;
1436 bool bRightParent = false;
1442 pLeaf = const_cast<internal_node *>( &m_Root );
1443 updParent = nullptr;
1445 while ( pLeaf->is_internal() ) {
1446 pGrandParent = pParent;
1447 pParent = static_cast<internal_node *>( pLeaf );
1448 bRightParent = bRightLeaf;
1449 updGrandParent = updParent;
1450 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1452 switch ( updParent.bits() ) {
1453 case update_desc::DFlag:
1454 case update_desc::Mark:
1455 m_Stat.onSearchRetry();
1459 nCmp = cmp( key, *pParent );
1460 bRightLeaf = nCmp >= 0;
1461 pLeaf = nCmp < 0 ? pParent->m_pLeft.load( memory_model::memory_order_acquire )
1462 : pParent->m_pRight.load( memory_model::memory_order_acquire );
1465 assert( pLeaf->is_leaf() );
1466 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1468 res.pGrandParent = pGrandParent;
1469 res.pParent = pParent;
1470 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1471 res.updParent = updParent;
1472 res.updGrandParent = updGrandParent;
1473 res.bRightParent = bRightParent;
1474 res.bRightLeaf = bRightLeaf;
1479 bool search_min( search_result& res ) const
1481 assert( gc::is_locked() );
1483 internal_node * pParent;
1484 internal_node * pGrandParent = nullptr;
1486 update_ptr updParent;
1487 update_ptr updGrandParent;
1491 pLeaf = const_cast<internal_node *>( &m_Root );
1492 while ( pLeaf->is_internal() ) {
1493 pGrandParent = pParent;
1494 pParent = static_cast<internal_node *>( pLeaf );
1495 updGrandParent = updParent;
1496 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1498 switch ( updParent.bits() ) {
1499 case update_desc::DFlag:
1500 case update_desc::Mark:
1501 m_Stat.onSearchRetry();
1505 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1508 if ( pLeaf->infinite_key())
1511 res.pGrandParent = pGrandParent;
1512 res.pParent = pParent;
1513 assert( pLeaf->is_leaf() );
1514 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1515 res.updParent = updParent;
1516 res.updGrandParent = updGrandParent;
1517 res.bRightParent = false;
1518 res.bRightLeaf = false;
1523 bool search_max( search_result& res ) const
1525 assert( gc::is_locked() );
1527 internal_node * pParent;
1528 internal_node * pGrandParent = nullptr;
1530 update_ptr updParent;
1531 update_ptr updGrandParent;
1533 bool bRightParent = false;
1537 pLeaf = const_cast<internal_node *>( &m_Root );
1539 while ( pLeaf->is_internal() ) {
1540 pGrandParent = pParent;
1541 pParent = static_cast<internal_node *>( pLeaf );
1542 bRightParent = bRightLeaf;
1543 updGrandParent = updParent;
1544 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1546 switch ( updParent.bits() ) {
1547 case update_desc::DFlag:
1548 case update_desc::Mark:
1549 m_Stat.onSearchRetry();
1553 if ( pParent->infinite_key()) {
1554 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1558 pLeaf = pParent->m_pRight.load( memory_model::memory_order_acquire );
1563 if ( pLeaf->infinite_key())
1566 res.pGrandParent = pGrandParent;
1567 res.pParent = pParent;
1568 assert( pLeaf->is_leaf() );
1569 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1570 res.updParent = updParent;
1571 res.updGrandParent = updGrandParent;
1572 res.bRightParent = bRightParent;
1573 res.bRightLeaf = bRightLeaf;
1578 template <typename Q, typename Compare, typename Equal, typename Func>
1579 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1581 check_deadlock_policy::check();
1583 retired_list updRetire;
1584 update_desc * pOp = nullptr;
1591 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1593 retire_update_desc( pOp, updRetire, false );
1594 m_Stat.onEraseFailed();
1598 if ( res.updGrandParent.bits() != update_desc::Clean )
1599 help( res.updGrandParent, updRetire );
1600 else if ( res.updParent.bits() != update_desc::Clean )
1601 help( res.updParent, updRetire );
1604 pOp = alloc_update_desc();
1605 if ( check_delete_precondition( res ) ) {
1606 pOp->dInfo.pGrandParent = res.pGrandParent;
1607 pOp->dInfo.pParent = res.pParent;
1608 pOp->dInfo.pLeaf = res.pLeaf;
1609 pOp->dInfo.bDisposeLeaf = true;
1610 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1611 pOp->dInfo.bRightParent = res.bRightParent;
1612 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1614 update_ptr updGP( res.updGrandParent.ptr() );
1615 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1616 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1618 if ( help_delete( pOp, updRetire )) {
1619 // res.pLeaf is not deleted yet since RCU is blocked
1620 f( *node_traits::to_value_ptr( res.pLeaf ));
1626 // updGP has been changed by CAS
1627 help( updGP, updRetire );
1633 m_Stat.onEraseRetry();
1638 m_Stat.onEraseSuccess();
1642 template <typename ExemptPtr, typename Q, typename Less>
1643 bool extract_with_( ExemptPtr& dest, Q const& val, Less pred )
1645 typedef ellen_bintree::details::compare<
1648 opt::details::make_comparator_from_less<Less>,
1652 return extract_( dest, val, compare_functor() );
1655 template <typename ExemptPtr, typename Q, typename Compare>
1656 bool extract_( ExemptPtr& ptr, Q const& val, Compare cmp )
1658 check_deadlock_policy::check();
1660 retired_list updRetire;
1661 update_desc * pOp = nullptr;
1668 if ( !search( res, val, cmp ) ) {
1670 retire_update_desc( pOp, updRetire, false );
1671 m_Stat.onEraseFailed();
1675 if ( res.updGrandParent.bits() != update_desc::Clean )
1676 help( res.updGrandParent, updRetire );
1677 else if ( res.updParent.bits() != update_desc::Clean )
1678 help( res.updParent, updRetire );
1681 pOp = alloc_update_desc();
1682 if ( check_delete_precondition( res )) {
1683 pOp->dInfo.pGrandParent = res.pGrandParent;
1684 pOp->dInfo.pParent = res.pParent;
1685 pOp->dInfo.pLeaf = res.pLeaf;
1686 pOp->dInfo.bDisposeLeaf = false;
1687 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1688 pOp->dInfo.bRightParent = res.bRightParent;
1689 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1691 update_ptr updGP( res.updGrandParent.ptr() );
1692 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1693 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1695 if ( help_delete( pOp, updRetire )) {
1696 ptr = node_traits::to_value_ptr( res.pLeaf );
1702 // updGP has been changed by CAS
1703 help( updGP, updRetire );
1709 m_Stat.onEraseRetry();
1714 m_Stat.onEraseSuccess();
1719 template <typename ExemptPtr>
1720 bool extract_max_( ExemptPtr& result )
1722 check_deadlock_policy::check();
1724 retired_list updRetire;
1725 update_desc * pOp = nullptr;
1732 if ( !search_max( res )) {
1735 retire_update_desc( pOp, updRetire, false );
1736 m_Stat.onExtractMaxFailed();
1740 if ( res.updGrandParent.bits() != update_desc::Clean )
1741 help( res.updGrandParent, updRetire );
1742 else if ( res.updParent.bits() != update_desc::Clean )
1743 help( res.updParent, updRetire );
1746 pOp = alloc_update_desc();
1747 if ( check_delete_precondition( res ) ) {
1748 pOp->dInfo.pGrandParent = res.pGrandParent;
1749 pOp->dInfo.pParent = res.pParent;
1750 pOp->dInfo.pLeaf = res.pLeaf;
1751 pOp->dInfo.bDisposeLeaf = false;
1752 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1753 pOp->dInfo.bRightParent = res.bRightParent;
1754 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1756 update_ptr updGP( res.updGrandParent.ptr() );
1757 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1758 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1760 if ( help_delete( pOp, updRetire )) {
1761 result = node_traits::to_value_ptr( res.pLeaf );
1767 // updGP has been changed by CAS
1768 help( updGP, updRetire );
1774 m_Stat.onExtractMaxRetry();
1779 m_Stat.onExtractMaxSuccess();
1783 template <typename ExemptPtr>
1784 bool extract_min_(ExemptPtr& result)
1786 check_deadlock_policy::check();
1788 retired_list updRetire;
1789 update_desc * pOp = nullptr;
1796 if ( !search_min( res )) {
1799 retire_update_desc( pOp, updRetire, false );
1800 m_Stat.onExtractMinFailed();
1804 if ( res.updGrandParent.bits() != update_desc::Clean )
1805 help( res.updGrandParent, updRetire );
1806 else if ( res.updParent.bits() != update_desc::Clean )
1807 help( res.updParent, updRetire );
1810 pOp = alloc_update_desc();
1811 if ( check_delete_precondition( res ) ) {
1812 pOp->dInfo.pGrandParent = res.pGrandParent;
1813 pOp->dInfo.pParent = res.pParent;
1814 pOp->dInfo.pLeaf = res.pLeaf;
1815 pOp->dInfo.bDisposeLeaf = false;
1816 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1817 pOp->dInfo.bRightParent = res.bRightParent;
1818 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1820 update_ptr updGP( res.updGrandParent.ptr() );
1821 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1822 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1824 if ( help_delete( pOp, updRetire )) {
1825 result = node_traits::to_value_ptr( res.pLeaf );
1831 // updGP has been changed by CAS
1832 help( updGP, updRetire );
1838 m_Stat.onExtractMinRetry();
1843 m_Stat.onExtractMinSuccess();
1847 template <typename Q, typename Less, typename Func>
1848 bool find_with_( Q& val, Less pred, Func f ) const
1850 typedef ellen_bintree::details::compare<
1853 opt::details::make_comparator_from_less<Less>,
1859 if ( search( res, val, compare_functor() )) {
1860 assert( res.pLeaf );
1861 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1863 m_Stat.onFindSuccess();
1867 m_Stat.onFindFailed();
1871 template <typename Q, typename Func>
1872 bool find_( Q& key, Func f ) const
1876 if ( search( res, key, node_compare() )) {
1877 assert( res.pLeaf );
1878 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1880 m_Stat.onFindSuccess();
1884 m_Stat.onFindFailed();
1888 template <typename Q, typename Compare>
1889 value_type * get_( Q const& key, Compare cmp ) const
1891 assert( gc::is_locked());
1894 if ( search( res, key, cmp )) {
1895 m_Stat.onFindSuccess();
1896 return node_traits::to_value_ptr( res.pLeaf );
1899 m_Stat.onFindFailed();
1904 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1906 assert( gc::is_locked() );
1907 assert( res.updParent.bits() == update_desc::Clean );
1909 // check search result
1910 if ( static_cast<leaf_node *>( res.bRightLeaf
1911 ? res.pParent->m_pRight.load( memory_model::memory_order_relaxed )
1912 : res.pParent->m_pLeft.load( memory_model::memory_order_relaxed ) ) == res.pLeaf )
1914 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1916 int nCmp = node_compare()( val, *res.pLeaf );
1918 if ( res.pGrandParent ) {
1919 pNewInternal->infinite_key( 0 );
1920 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1921 assert( !res.pLeaf->infinite_key() );
1924 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1925 pNewInternal->infinite_key( 1 );
1927 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1928 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1931 assert( !res.pLeaf->is_internal() );
1932 pNewInternal->infinite_key( 0 );
1934 key_extractor()( pNewInternal->m_Key, val );
1935 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1936 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1937 assert( !res.pLeaf->infinite_key());
1940 update_desc * pOp = alloc_update_desc();
1942 pOp->iInfo.pParent = res.pParent;
1943 pOp->iInfo.pNew = pNewInternal;
1944 pOp->iInfo.pLeaf = res.pLeaf;
1945 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1947 update_ptr updCur( res.updParent.ptr() );
1948 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1949 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1953 retire_update_desc( pOp, updRetire, false );
1957 // updCur has been updated by CAS
1958 help( updCur, updRetire );
1959 retire_update_desc( pOp, updRetire, true );
1968 }} // namespace cds::intrusive
1970 #endif // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H