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 original paper.
61 So, the current implementation is near to fine-grained lock-based tree.
62 Helping will be implemented in future release
64 <b>Template arguments</b> :
65 - \p RCU - one of \ref cds_urcu_gc "RCU type"
66 - \p Key - key type, a subset of \p T
67 - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
68 (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
69 (for \p ellen_bintree::member_hook).
70 - \p Traits - tree traits, default is \p ellen_bintree::traits
71 It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
72 instead of \p Traits template argument.
74 @anchor cds_intrusive_EllenBinTree_rcu_less
75 <b>Predicate requirements</b>
77 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
78 of type \p T and \p Key in any combination.
79 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
81 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
88 bool operator()( Foo const& v1, Foo const& v2 ) const
89 { return v1.m_strKey < v2.m_strKey ; }
91 bool operator()( Foo const& v, std::string const& s ) const
92 { return v.m_strKey < s ; }
94 bool operator()( std::string const& s, Foo const& v ) const
95 { return s < v.m_strKey ; }
97 // Support comparing std::string and char const *
98 bool operator()( std::string const& s, char const * p ) const
99 { return s.compare(p) < 0 ; }
101 bool operator()( Foo const& v, char const * p ) const
102 { return v.m_strKey.compare(p) < 0 ; }
104 bool operator()( char const * p, std::string const& s ) const
105 { return s.compare(p) > 0; }
107 bool operator()( char const * p, Foo const& v ) const
108 { return v.m_strKey.compare(p) > 0; }
112 @note Before including <tt><cds/intrusive/ellen_bintree_rcu.h></tt> you should include appropriate RCU header file,
113 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
115 @anchor cds_intrusive_EllenBinTree_usage
118 Suppose we have the following Foo struct with string key type:
121 std::string m_strKey ; // The key
122 //... // other non-key data
126 We want to utilize RCU-based \p %cds::intrusive::EllenBinTree set for \p Foo data.
127 We may use base hook or member hook. Consider base hook variant.
128 First, we need deriving \p Foo struct from \p cds::intrusive::ellen_bintree::node:
130 #include <cds/urcu/general_buffered.h>
131 #include <cds/intrusive/ellen_bintree_rcu.h>
134 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
136 struct Foo: public cds::intrusive:ellen_bintree::node< gpb_rcu >
138 std::string m_strKey ; // The key
139 //... // other non-key data
143 Second, we need to implement auxiliary structures and functors:
144 - key extractor functor for extracting the key from \p Foo object.
145 Such functor is necessary because the tree internal nodes store the keys.
146 - \p less predicate. We want our set should accept \p std::string
147 and <tt>char const *</tt> parameters for searching, so our \p less
148 predicate will not be trivial, see below.
149 - item counting feature: we want our set's \p size() member function
150 returns actual item count.
153 // Key extractor functor
154 struct my_key_extractor
156 void operator ()( std::string& key, Foo const& src ) const
164 bool operator()( Foo const& v1, Foo const& v2 ) const
165 { return v1.m_strKey < v2.m_strKey ; }
167 bool operator()( Foo const& v, std::string const& s ) const
168 { return v.m_strKey < s ; }
170 bool operator()( std::string const& s, Foo const& v ) const
171 { return s < v.m_strKey ; }
173 // Support comparing std::string and char const *
174 bool operator()( std::string const& s, char const * p ) const
175 { return s.compare(p) < 0 ; }
177 bool operator()( Foo const& v, char const * p ) const
178 { return v.m_strKey.compare(p) < 0 ; }
180 bool operator()( char const * p, std::string const& s ) const
181 { return s.compare(p) > 0; }
183 bool operator()( char const * p, Foo const& v ) const
184 { return v.m_strKey.compare(p) > 0; }
187 // Tree traits for our set
188 // It is necessary to specify only those typedefs that differ from
189 // cds::intrusive::ellen_bintree::traits defaults.
190 struct set_traits: public cds::intrusive::ellen_bintree::traits
192 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > > hook;
193 typedef my_key_extractor key_extractor;
194 typedef my_less less;
195 typedef cds::atomicity::item_counter item_counter;
199 Now we declare \p %EllenBinTree set and use it:
201 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, set_traits > set_type;
207 Instead of declaring \p set_traits type traits we can use option-based syntax with
208 \p ellen_bintree::make_traits metafunction, for example:
210 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo,
211 typename cds::intrusive::ellen_bintree::make_traits<
212 cds::opt::hook< cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > >
213 ,cds::intrusive::ellen_bintree::key_extractor< my_key_extractor >
214 ,cds::opt::less< my_less >
215 ,cds::opt::item_counter< cds::atomicity::item_counter >
220 Functionally, \p set_type and \p set_type2 are equivalent.
222 <b>Member-hooked tree</b>
224 Sometimes, we cannot use base hook, for example, when the \p Foo structure is external.
225 In such case we can use member hook feature.
227 #include <cds/urcu/general_buffered.h>
228 #include <cds/intrusive/ellen_bintree_rcu.h>
230 // Struct Foo is external and its declaration cannot be modified.
232 std::string m_strKey ; // The key
233 //... // other non-key data
237 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
243 cds::intrusive:ellen_bintree::node< gpb_rcu > set_hook; // member hook
246 // Key extractor functor
247 struct member_key_extractor
249 void operator ()( std::string& key, MyFoo const& src ) const
251 key = src.m_foo.m_strKey;
257 bool operator()( MyFoo const& v1, MyFoo const& v2 ) const
258 { return v1.m_foo.m_strKey < v2.m_foo.m_strKey ; }
260 bool operator()( MyFoo const& v, std::string const& s ) const
261 { return v.m_foo.m_strKey < s ; }
263 bool operator()( std::string const& s, MyFoo const& v ) const
264 { return s < v.m_foo.m_strKey ; }
266 // Support comparing std::string and char const *
267 bool operator()( std::string const& s, char const * p ) const
268 { return s.compare(p) < 0 ; }
270 bool operator()( MyFoo const& v, char const * p ) const
271 { return v.m_foo.m_strKey.compare(p) < 0 ; }
273 bool operator()( char const * p, std::string const& s ) const
274 { return s.compare(p) > 0; }
276 bool operator()( char const * p, MyFoo const& v ) const
277 { return v.m_foo.m_strKey.compare(p) > 0; }
280 // Tree traits for our member-based set
281 struct member_set_traits: public cds::intrusive::ellen_bintree::traits
283 cds::intrusive::ellen_bintree::member_hook< offsetof(MyFoo, set_hook), cds::opt::gc<gpb_rcu> > > hook;
284 typedef member_key_extractor key_extractor;
285 typedef member_less less;
286 typedef cds::atomicity::item_counter item_counter;
289 // Tree containing MyFoo objects
290 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, MyFoo, member_set_traits > member_set_type;
292 member_set_type theMemberSet;
295 <b>Multiple containers</b>
297 Sometimes we need that our \p Foo struct should be used in several different containers.
298 Suppose, \p Foo struct has two key fields:
301 std::string m_strKey ; // string key
302 int m_nKey ; // int key
303 //... // other non-key data fields
307 We want to build two intrusive \p %EllenBinTree sets: one indexed on \p Foo::m_strKey field,
308 another indexed on \p Foo::m_nKey field. To decide such case we should use a tag option for
311 #include <cds/urcu/general_buffered.h>
312 #include <cds/intrusive/ellen_bintree_rcu.h>
315 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
317 // Declare tag structs
318 struct int_tag ; // int key tag
319 struct string_tag ; // string key tag
321 // Foo struct is derived from two ellen_bintree::node class
322 // with different tags
324 : public cds::intrusive::ellen_bintree::node< gpb_rcu, cds::opt::tag< string_tag > >
325 , public cds::intrusive::ellen_bintree::node< gpb_rcu >, cds::opt::tag< int_tag >
327 std::string m_strKey ; // string key
328 int m_nKey ; // int key
329 //... // other non-key data fields
332 // String key extractor functor
333 struct string_key_extractor
335 void operator ()( std::string& key, Foo const& src ) const
341 // Int key extractor functor
342 struct int_key_extractor
344 void operator ()( int& key, Foo const& src ) const
350 // String less predicate
352 bool operator()( Foo const& v1, Foo const& v2 ) const
353 { return v1.m_strKey < v2.m_strKey ; }
355 bool operator()( Foo const& v, std::string const& s ) const
356 { return v.m_strKey < s ; }
358 bool operator()( std::string const& s, Foo const& v ) const
359 { return s < v.m_strKey ; }
361 // Support comparing std::string and char const *
362 bool operator()( std::string const& s, char const * p ) const
363 { return s.compare(p) < 0 ; }
365 bool operator()( Foo const& v, char const * p ) const
366 { return v.m_strKey.compare(p) < 0 ; }
368 bool operator()( char const * p, std::string const& s ) const
369 { return s.compare(p) > 0; }
371 bool operator()( char const * p, Foo const& v ) const
372 { return v.m_strKey.compare(p) > 0; }
375 // Int less predicate
377 bool operator()( Foo const& v1, Foo const& v2 ) const
378 { return v1.m_nKey < v2.m_nKey ; }
380 bool operator()( Foo const& v, int n ) const
381 { return v.m_nKey < n ; }
383 bool operator()( int n, Foo const& v ) const
384 { return n < v.m_nKey ; }
387 // Type traits for string-indexed set
388 struct string_set_traits: public cds::intrusive::ellen_bintree::traits
390 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< string_tag > > hook;
391 typedef string_key_extractor key_extractor;
392 typedef string_less less;
393 typedef cds::atomicity::item_counter item_counter;
396 // Type traits for int-indexed set
397 struct int_set_traits: public cds::intrusive::ellen_bintree::traits
399 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< int_tag > > hook;
400 typedef int_key_extractor key_extractor;
401 typedef int_less less;
402 typedef cds::atomicity::item_counter item_counter;
405 // Declare string-indexed set
406 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, string_set_traits > string_set_type;
407 string_set_type theStringSet;
409 // Declare int-indexed set
410 typedef cds::intrusive::EllenBinTree< gpb_rcu, int, Foo, int_set_traits > int_set_type;
411 int_set_type theIntSet;
413 // Now we can use theStringSet and theIntSet in our program
417 template < class RCU,
420 #ifdef CDS_DOXYGEN_INVOKED
421 class Traits = ellen_bintree::traits
426 class EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
429 typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
430 typedef Key key_type; ///< type of a key stored in internal nodes; key is a part of \p value_type
431 typedef T value_type; ///< type of value stored in the binary tree
432 typedef Traits traits; ///< Traits template parameter
434 typedef typename traits::hook hook; ///< hook type
435 typedef typename hook::node_type node_type; ///< node type
437 typedef typename traits::disposer disposer; ///< leaf node disposer
441 typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
442 typedef node_type leaf_node; ///< Leaf node type
443 typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node; ///< Internal node type
444 typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc; ///< Update descriptor
445 typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
449 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > exempt_ptr; ///< pointer to extracted node
452 # ifdef CDS_DOXYGEN_INVOKED
453 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
454 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
456 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
457 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
459 static internal_node const& to_internal_node( tree_node const& n )
461 assert( n.is_internal() );
462 return static_cast<internal_node const&>( n );
465 static leaf_node const& to_leaf_node( tree_node const& n )
467 assert( n.is_leaf() );
468 return static_cast<leaf_node const&>( n );
473 typedef typename traits::item_counter item_counter; ///< Item counting policy used
474 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
475 typedef typename traits::stat stat; ///< internal statistics type
476 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
477 typedef typename traits::key_extractor key_extractor; ///< key extracting functor
479 typedef typename traits::node_allocator node_allocator; ///< Internal node allocator
480 typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
482 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
484 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
488 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
490 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock > check_deadlock_policy;
492 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
493 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
495 struct search_result {
496 internal_node * pGrandParent;
497 internal_node * pParent;
499 update_ptr updParent;
500 update_ptr updGrandParent;
501 bool bRightLeaf ; // true if pLeaf is right child of pParent, false otherwise
502 bool bRightParent ; // true if pParent is right child of pGrandParent, false otherwise
505 :pGrandParent( nullptr )
509 ,bRightParent( false )
516 internal_node m_Root; ///< Tree root node (key= Infinite2)
517 leaf_node m_LeafInf1;
518 leaf_node m_LeafInf2;
521 item_counter m_ItemCounter; ///< item counter
522 mutable stat m_Stat; ///< internal statistics
526 static void free_leaf_node( value_type * p )
531 internal_node * alloc_internal_node() const
533 m_Stat.onInternalNodeCreated();
534 internal_node * pNode = cxx_node_allocator().New();
539 static void free_internal_node( internal_node * pNode )
541 cxx_node_allocator().Delete( pNode );
544 struct internal_node_deleter {
545 void operator()( internal_node * p) const
547 free_internal_node( p );
551 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
553 update_desc * alloc_update_desc() const
555 m_Stat.onUpdateDescCreated();
556 return cxx_update_desc_allocator().New();
559 static void free_update_desc( update_desc * pDesc )
561 cxx_update_desc_allocator().Delete( pDesc );
566 update_desc * pUpdateHead;
567 tree_node * pNodeHead;
570 class forward_iterator
572 update_desc * m_pUpdate;
576 forward_iterator( retired_list const& l )
577 : m_pUpdate( l.pUpdateHead )
578 , m_pNode( l.pNodeHead )
582 : m_pUpdate( nullptr )
586 cds::urcu::retired_ptr operator *()
589 return cds::urcu::retired_ptr( reinterpret_cast<void *>( m_pUpdate ),
590 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
593 if ( m_pNode->is_leaf() ) {
594 return cds::urcu::retired_ptr( reinterpret_cast<void *>( node_traits::to_value_ptr( static_cast<leaf_node *>( m_pNode ))),
595 reinterpret_cast< cds::urcu::free_retired_ptr_func>( free_leaf_node ) );
598 return cds::urcu::retired_ptr( reinterpret_cast<void *>( static_cast<internal_node *>( m_pNode ) ),
599 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_internal_node ) );
602 return cds::urcu::retired_ptr( nullptr,
603 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
609 m_pUpdate = m_pUpdate->pNextRetire;
613 m_pNode = m_pNode->m_pNextRetired;
616 friend bool operator ==( forward_iterator const& i1, forward_iterator const& i2 )
618 return i1.m_pUpdate == i2.m_pUpdate && i1.m_pNode == i2.m_pNode;
620 friend bool operator !=( forward_iterator const& i1, forward_iterator const& i2 )
622 return !( i1 == i2 );
628 : pUpdateHead( nullptr )
629 , pNodeHead( nullptr )
634 gc::batch_retire( forward_iterator(*this), forward_iterator() );
637 void push( update_desc * p )
639 p->pNextRetire = pUpdateHead;
643 void push( tree_node * p )
645 p->m_pNextRetired = pNodeHead;
650 void retire_node( tree_node * pNode, retired_list& rl ) const
652 if ( pNode->is_leaf() ) {
653 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
654 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
657 assert( static_cast<internal_node *>( pNode ) != &m_Root );
658 m_Stat.onInternalNodeDeleted();
663 void retire_update_desc( update_desc * p, retired_list& rl, bool bDirect ) const
665 m_Stat.onUpdateDescDeleted();
667 free_update_desc( p );
672 void make_empty_tree()
674 m_Root.infinite_key( 2 );
675 m_LeafInf1.infinite_key( 1 );
676 m_LeafInf2.infinite_key( 2 );
677 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
678 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
683 /// Default constructor
686 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
698 The function inserts \p val in the tree if it does not contain
699 an item with key equal to \p val.
701 The function applies RCU lock internally.
703 Returns \p true if \p val is placed into the set, \p false otherwise.
705 bool insert( value_type& val )
707 return insert( val, []( value_type& ) {} );
712 This function is intended for derived non-intrusive containers.
714 The function allows to split creating of new item into two part:
715 - create item with key only
716 - insert new item into the tree
717 - if inserting is success, calls \p f functor to initialize value-field of \p val.
719 The functor signature is:
721 void func( value_type& val );
723 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
724 \p val no any other changes could be made on this tree's item by concurrent threads.
725 The user-defined functor is called only if the inserting is success.
727 RCU \p synchronize method can be called. RCU should not be locked.
729 template <typename Func>
730 bool insert( value_type& val, Func f )
732 check_deadlock_policy::check();
734 unique_internal_node_ptr pNewInternal;
735 retired_list updRetire;
742 if ( search( res, val, node_compare() )) {
743 if ( pNewInternal.get() )
744 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
745 m_Stat.onInsertFailed();
749 if ( res.updParent.bits() != update_desc::Clean )
750 help( res.updParent, updRetire );
752 if ( !pNewInternal.get() )
753 pNewInternal.reset( alloc_internal_node() );
755 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
757 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
762 m_Stat.onInsertRetry();
767 m_Stat.onInsertSuccess();
772 /// Ensures that the \p val exists in the tree
774 The operation performs inserting or changing data with lock-free manner.
776 If the item \p val is not found in the tree, then \p val is inserted into the tree.
777 Otherwise, the functor \p func is called with item found.
778 The functor signature is:
780 void func( bool bNew, value_type& item, value_type& val );
783 - \p bNew - \p true if the item has been inserted, \p false otherwise
784 - \p item - item of the tree
785 - \p val - argument \p val passed into the \p ensure function
786 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
787 refer to the same thing.
789 The functor can change non-key fields of the \p item; however, \p func must guarantee
790 that during changing no any other modifications could be made on this item by concurrent threads.
792 RCU \p synchronize method can be called. RCU should not be locked.
794 Returns <tt>std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
795 \p second is \p true if new item has been added or \p false if the item with \p key
796 already is in the tree.
798 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
800 template <typename Func>
801 std::pair<bool, bool> ensure( value_type& val, Func func )
803 check_deadlock_policy::check();
805 unique_internal_node_ptr pNewInternal;
806 retired_list updRetire;
813 if ( search( res, val, node_compare() )) {
814 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
815 if ( pNewInternal.get() )
816 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
817 m_Stat.onEnsureExist();
818 return std::make_pair( true, false );
821 if ( res.updParent.bits() != update_desc::Clean )
822 help( res.updParent, updRetire );
824 if ( !pNewInternal.get() )
825 pNewInternal.reset( alloc_internal_node() );
827 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
828 func( true, val, val );
829 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
833 m_Stat.onEnsureRetry();
838 m_Stat.onEnsureNew();
840 return std::make_pair( true, true );
843 /// Unlinks the item \p val from the tree
845 The function searches the item \p val in the tree and unlink it from the tree
846 if it is found and is equal to \p val.
848 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
849 and deletes the item found. \p unlink finds an item by key and deletes it
850 only if \p val is an item of the tree, i.e. the pointer to item found
851 is equal to <tt> &val </tt>.
853 RCU \p synchronize method can be called. RCU should not be locked.
855 The \ref disposer specified in \p Traits class template parameter is called
856 by garbage collector \p GC asynchronously.
858 The function returns \p true if success and \p false otherwise.
860 bool unlink( value_type& val )
862 return erase_( val, node_compare(),
863 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
864 [](value_type const&) {} );
867 /// Deletes the item from the tree
868 /** \anchor cds_intrusive_EllenBinTree_rcu_erase
869 The function searches an item with key equal to \p key in the tree,
870 unlinks it from the tree, and returns \p true.
871 If the item with key equal to \p key is not found the function return \p false.
873 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
875 RCU \p synchronize method can be called. RCU should not be locked.
877 template <typename Q>
878 bool erase( const Q& key )
880 return erase_( key, node_compare(),
881 []( Q const&, leaf_node const& ) -> bool { return true; },
882 [](value_type const&) {} );
885 /// Delete the item from the tree with comparing functor \p pred
887 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
888 but \p pred predicate is used for key comparing.
889 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
890 "Predicate requirements".
891 \p pred must imply the same element order as the comparator used for building the tree.
893 template <typename Q, typename Less>
894 bool erase_with( const Q& key, Less pred )
896 typedef ellen_bintree::details::compare<
899 opt::details::make_comparator_from_less<Less>,
903 return erase_( key, compare_functor(),
904 []( Q const&, leaf_node const& ) -> bool { return true; },
905 [](value_type const&) {} );
908 /// Deletes the item from the tree
909 /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
910 The function searches an item with key equal to \p key in the tree,
911 call \p f functor with item found, unlinks it from the tree, and returns \p true.
912 The \ref disposer specified in \p Traits class template parameter is called
913 by garbage collector \p GC asynchronously.
915 The \p Func interface is
918 void operator()( value_type const& item );
921 The functor can be passed by reference with <tt>boost:ref</tt>
923 If the item with key equal to \p key is not found the function return \p false.
925 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
927 RCU \p synchronize method can be called. RCU should not be locked.
929 template <typename Q, typename Func>
930 bool erase( Q const& key, Func f )
932 return erase_( key, node_compare(),
933 []( Q const&, leaf_node const& ) -> bool { return true; },
937 /// Delete the item from the tree with comparing functor \p pred
939 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
940 but \p pred predicate is used for key comparing.
941 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
942 "Predicate requirements".
943 \p pred must imply the same element order as the comparator used for building the tree.
945 template <typename Q, typename Less, typename Func>
946 bool erase_with( Q const& key, Less pred, Func f )
948 typedef ellen_bintree::details::compare<
951 opt::details::make_comparator_from_less<Less>,
955 return erase_( key, compare_functor(),
956 []( Q const&, leaf_node const& ) -> bool { return true; },
960 /// Extracts an item with minimal key from the tree
962 The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p result parameter.
963 If the tree is empty the function returns \p false.
965 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
966 It means that the function gets leftmost leaf of the tree and tries to unlink it.
967 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
968 So, the function returns the item with minimum key at the moment of tree traversing.
970 RCU \p synchronize method can be called. RCU should NOT be locked.
971 The function does not call the disposer for the item found.
972 The disposer will be implicitly invoked when \p result object is destroyed or when
973 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
974 @note Before reusing \p result object you should call its \p release() method.
976 bool extract_min(exempt_ptr& result)
978 return extract_min_(result);
981 /// Extracts an item with maximal key from the tree
983 The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p result prameter.
984 If the tree is empty the function returns \p false.
986 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
987 It means that the function gets rightmost leaf of the tree and tries to unlink it.
988 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
989 So, the function returns the item with maximum key at the moment of tree traversing.
991 RCU \p synchronize method can be called. RCU should NOT be locked.
992 The function does not call the disposer for the item found.
993 The disposer will be implicitly invoked when \p result object is destroyed or when
994 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
995 @note Before reusing \p result object you should call its \p release() method.
997 bool extract_max(exempt_ptr& result)
999 return extract_max_(result);
1002 /// Extracts an item from the tree
1003 /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1004 The function searches an item with key equal to \p key in the tree,
1005 unlinks it, and returns pointer to an item found in \p result parameter.
1006 If the item with the key equal to \p key is not found the function returns \p false.
1008 RCU \p synchronize method can be called. RCU should NOT be locked.
1009 The function does not call the disposer for the item found.
1010 The disposer will be implicitly invoked when \p result object is destroyed or when
1011 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1012 @note Before reusing \p result object you should call its \p release() method.
1014 template <typename Q>
1015 bool extract( exempt_ptr& result, Q const& key )
1017 return extract_( result, key, node_compare() );
1020 /// Extracts an item from the set using \p pred for searching
1022 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_extract "extract(exempt_ptr&, Q const&)"
1023 but \p pred is used for key compare.
1024 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1025 "predicate requirements".
1026 \p pred must imply the same element order as the comparator used for building the tree.
1028 template <typename Q, typename Less>
1029 bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
1031 return extract_with_( dest, key, pred );
1034 /// Finds the key \p key
1035 /** @anchor cds_intrusive_EllenBinTree_rcu_find_val
1036 The function searches the item with key equal to \p key
1037 and returns \p true if it is found, and \p false otherwise.
1039 Note the hash functor specified for class \p Traits template parameter
1040 should accept a parameter of type \p Q that can be not the same as \p value_type.
1042 The function applies RCU lock internally.
1044 template <typename Q>
1045 bool find( Q const& key ) const
1049 if ( search( res, key, node_compare() )) {
1050 m_Stat.onFindSuccess();
1054 m_Stat.onFindFailed();
1058 /// Finds the key \p key with comparing functor \p pred
1060 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)"
1061 but \p pred is used for key compare.
1062 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1063 "Predicate requirements".
1064 \p pred must imply the same element order as the comparator used for building the tree.
1065 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1067 template <typename Q, typename Less>
1068 bool find_with( Q const& key, Less pred ) const
1070 typedef ellen_bintree::details::compare<
1073 opt::details::make_comparator_from_less<Less>,
1079 if ( search( res, key, compare_functor() )) {
1080 m_Stat.onFindSuccess();
1083 m_Stat.onFindFailed();
1087 /// Finds the key \p key
1088 /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1089 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1090 The interface of \p Func functor is:
1093 void operator()( value_type& item, Q& key );
1096 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1098 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1099 that \p item cannot be disposed during functor is executing.
1100 The functor does not serialize simultaneous access to the tree \p item. If such access is
1101 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1103 The function applies RCU lock internally.
1105 The function returns \p true if \p key is found, \p false otherwise.
1107 template <typename Q, typename Func>
1108 bool find( Q& key, Func f ) const
1110 return find_( key, f );
1113 template <typename Q, typename Func>
1114 bool find( Q const& key, Func f ) const
1116 return find_( key, f );
1120 /// Finds the key \p key with comparing functor \p pred
1122 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1123 but \p pred is used for key comparison.
1124 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1125 "Predicate requirements".
1126 \p pred must imply the same element order as the comparator used for building the tree.
1128 template <typename Q, typename Less, typename Func>
1129 bool find_with( Q& key, Less pred, Func f ) const
1131 return find_with_( key, pred, f );
1134 template <typename Q, typename Less, typename Func>
1135 bool find_with( Q const& key, Less pred, Func f ) const
1137 return find_with_( key, pred, f );
1141 /// Finds \p key and return the item found
1142 /** \anchor cds_intrusive_EllenBinTree_rcu_get
1143 The function searches the item with key equal to \p key and returns the pointer to item found.
1144 If \p key is not found it returns \p nullptr.
1146 RCU should be locked before call the function.
1147 Returned pointer is valid while RCU is locked.
1149 template <typename Q>
1150 value_type * get( Q const& key ) const
1152 return get_( key, node_compare() );
1155 /// Finds \p key with \p pred predicate and return the item found
1157 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1158 but \p pred is used for comparing the keys.
1160 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1162 \p pred must imply the same element order as the comparator used for building the tree.
1164 template <typename Q, typename Less>
1165 value_type * get_with( Q const& key, Less pred ) const
1167 typedef ellen_bintree::details::compare<
1170 opt::details::make_comparator_from_less<Less>,
1174 return get_( key, compare_functor());
1177 /// Checks if the tree is empty
1180 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1183 /// Clears the tree (thread safe, not atomic)
1185 The function unlink all items from the tree.
1186 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1190 assert( set.empty() );
1192 the assertion could be raised.
1194 For each leaf the \ref disposer will be called after unlinking.
1196 RCU \p synchronize method can be called. RCU should not be locked.
1201 while ( extract_min(ep) )
1205 /// Clears the tree (not thread safe)
1207 This function is not thread safe and may be called only when no other thread deals with the tree.
1208 The function is used in the tree destructor.
1215 internal_node * pParent = nullptr;
1216 internal_node * pGrandParent = nullptr;
1217 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1219 // Get leftmost leaf
1220 while ( pLeaf->is_internal() ) {
1221 pGrandParent = pParent;
1222 pParent = static_cast<internal_node *>( pLeaf );
1223 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1226 if ( pLeaf->infinite_key()) {
1227 // The tree is empty
1231 // Remove leftmost leaf and its parent node
1232 assert( pGrandParent );
1234 assert( pLeaf->is_leaf() );
1236 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1237 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
1238 free_internal_node( pParent );
1242 /// Returns item count in the tree
1244 Only leaf nodes containing user data are counted.
1246 The value returned depends on item counter type provided by \p Traits template parameter.
1247 If it is \p atomicity::empty_item_counter this function always returns 0.
1249 The function is not suitable for checking the tree emptiness, use \p empty()
1250 member function for that.
1254 return m_ItemCounter;
1257 /// Returns const reference to internal statistics
1258 stat const& statistics() const
1263 /// Checks internal consistency (not atomic, not thread-safe)
1265 The debugging function to check internal consistency of the tree.
1267 bool check_consistency() const
1269 return check_consistency( &m_Root );
1275 bool check_consistency( internal_node const * pRoot ) const
1277 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1278 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1282 if ( node_compare()( *pLeft, *pRoot ) < 0
1283 && node_compare()( *pRoot, *pRight ) <= 0
1284 && node_compare()( *pLeft, *pRight ) < 0 )
1287 if ( pLeft->is_internal() )
1288 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
1291 if ( bRet && pRight->is_internal() )
1292 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1300 void help( update_ptr pUpdate, retired_list& rl )
1303 switch ( pUpdate.bits() ) {
1304 case update_desc::IFlag:
1305 help_insert( pUpdate.ptr() );
1306 m_Stat.onHelpInsert();
1308 case update_desc::DFlag:
1309 //help_delete( pUpdate.ptr(), rl );
1310 //m_Stat.onHelpDelete();
1312 case update_desc::Mark:
1313 //help_marked( pUpdate.ptr() );
1314 //m_Stat.onHelpMark();
1320 void help_insert( update_desc * pOp )
1322 assert( gc::is_locked() );
1324 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1325 if ( pOp->iInfo.bRightLeaf ) {
1326 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1327 memory_model::memory_order_release, atomics::memory_order_relaxed );
1330 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1331 memory_model::memory_order_release, atomics::memory_order_relaxed );
1334 update_ptr cur( pOp, update_desc::IFlag );
1335 pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1336 memory_model::memory_order_release, atomics::memory_order_relaxed );
1339 bool check_delete_precondition( search_result& res )
1341 assert( res.pGrandParent != nullptr );
1344 static_cast<internal_node *>( res.bRightParent
1345 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1346 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1349 static_cast<leaf_node *>( res.bRightLeaf
1350 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1351 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1355 bool help_delete( update_desc * pOp, retired_list& rl )
1357 assert( gc::is_locked() );
1359 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1360 update_ptr pMark( pOp, update_desc::Mark );
1361 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1362 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1365 retire_node( pOp->dInfo.pParent, rl );
1366 // For extract operations the leaf should NOT be disposed
1367 if ( pOp->dInfo.bDisposeLeaf )
1368 retire_node( pOp->dInfo.pLeaf, rl );
1369 retire_update_desc( pOp, rl, false );
1373 else if ( pUpdate == pMark ) {
1374 // some other thread is processing help_marked()
1376 m_Stat.onHelpMark();
1380 // pUpdate has been changed by CAS
1381 help( pUpdate, rl );
1383 // Undo grandparent dInfo
1384 update_ptr pDel( pOp, update_desc::DFlag );
1385 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1386 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1388 retire_update_desc( pOp, rl, false );
1394 void help_marked( update_desc * pOp )
1396 assert( gc::is_locked() );
1398 tree_node * p = pOp->dInfo.pParent;
1399 if ( pOp->dInfo.bRightParent ) {
1400 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1401 pOp->dInfo.bRightLeaf
1402 ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1403 : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1404 memory_model::memory_order_release, atomics::memory_order_relaxed );
1407 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1408 pOp->dInfo.bRightLeaf
1409 ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1410 : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1411 memory_model::memory_order_release, atomics::memory_order_relaxed );
1414 update_ptr upd( pOp, update_desc::DFlag );
1415 pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1416 memory_model::memory_order_release, atomics::memory_order_relaxed );
1419 template <typename KeyValue, typename Compare>
1420 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1422 assert( gc::is_locked() );
1424 internal_node * pParent;
1425 internal_node * pGrandParent = nullptr;
1427 update_ptr updParent;
1428 update_ptr updGrandParent;
1430 bool bRightParent = false;
1436 pLeaf = const_cast<internal_node *>( &m_Root );
1437 updParent = nullptr;
1439 while ( pLeaf->is_internal() ) {
1440 pGrandParent = pParent;
1441 pParent = static_cast<internal_node *>( pLeaf );
1442 bRightParent = bRightLeaf;
1443 updGrandParent = updParent;
1444 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1446 switch ( updParent.bits() ) {
1447 case update_desc::DFlag:
1448 case update_desc::Mark:
1449 m_Stat.onSearchRetry();
1453 nCmp = cmp( key, *pParent );
1454 bRightLeaf = nCmp >= 0;
1455 pLeaf = nCmp < 0 ? pParent->m_pLeft.load( memory_model::memory_order_acquire )
1456 : pParent->m_pRight.load( memory_model::memory_order_acquire );
1459 assert( pLeaf->is_leaf() );
1460 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1462 res.pGrandParent = pGrandParent;
1463 res.pParent = pParent;
1464 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1465 res.updParent = updParent;
1466 res.updGrandParent = updGrandParent;
1467 res.bRightParent = bRightParent;
1468 res.bRightLeaf = bRightLeaf;
1473 bool search_min( search_result& res ) const
1475 assert( gc::is_locked() );
1477 internal_node * pParent;
1478 internal_node * pGrandParent = nullptr;
1480 update_ptr updParent;
1481 update_ptr updGrandParent;
1485 pLeaf = const_cast<internal_node *>( &m_Root );
1486 while ( pLeaf->is_internal() ) {
1487 pGrandParent = pParent;
1488 pParent = static_cast<internal_node *>( pLeaf );
1489 updGrandParent = updParent;
1490 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1492 switch ( updParent.bits() ) {
1493 case update_desc::DFlag:
1494 case update_desc::Mark:
1495 m_Stat.onSearchRetry();
1499 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1502 if ( pLeaf->infinite_key())
1505 res.pGrandParent = pGrandParent;
1506 res.pParent = pParent;
1507 assert( pLeaf->is_leaf() );
1508 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1509 res.updParent = updParent;
1510 res.updGrandParent = updGrandParent;
1511 res.bRightParent = false;
1512 res.bRightLeaf = false;
1517 bool search_max( search_result& res ) const
1519 assert( gc::is_locked() );
1521 internal_node * pParent;
1522 internal_node * pGrandParent = nullptr;
1524 update_ptr updParent;
1525 update_ptr updGrandParent;
1527 bool bRightParent = false;
1531 pLeaf = const_cast<internal_node *>( &m_Root );
1533 while ( pLeaf->is_internal() ) {
1534 pGrandParent = pParent;
1535 pParent = static_cast<internal_node *>( pLeaf );
1536 bRightParent = bRightLeaf;
1537 updGrandParent = updParent;
1538 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1540 switch ( updParent.bits() ) {
1541 case update_desc::DFlag:
1542 case update_desc::Mark:
1543 m_Stat.onSearchRetry();
1547 if ( pParent->infinite_key()) {
1548 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1552 pLeaf = pParent->m_pRight.load( memory_model::memory_order_acquire );
1557 if ( pLeaf->infinite_key())
1560 res.pGrandParent = pGrandParent;
1561 res.pParent = pParent;
1562 assert( pLeaf->is_leaf() );
1563 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1564 res.updParent = updParent;
1565 res.updGrandParent = updGrandParent;
1566 res.bRightParent = bRightParent;
1567 res.bRightLeaf = bRightLeaf;
1572 template <typename Q, typename Compare, typename Equal, typename Func>
1573 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1575 check_deadlock_policy::check();
1577 retired_list updRetire;
1578 update_desc * pOp = nullptr;
1584 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1586 retire_update_desc( pOp, updRetire, false );
1587 m_Stat.onEraseFailed();
1591 if ( res.updGrandParent.bits() != update_desc::Clean )
1592 help( res.updGrandParent, updRetire );
1593 else if ( res.updParent.bits() != update_desc::Clean )
1594 help( res.updParent, updRetire );
1597 pOp = alloc_update_desc();
1598 if ( check_delete_precondition( res ) ) {
1599 pOp->dInfo.pGrandParent = res.pGrandParent;
1600 pOp->dInfo.pParent = res.pParent;
1601 pOp->dInfo.pLeaf = res.pLeaf;
1602 pOp->dInfo.bDisposeLeaf = true;
1603 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1604 pOp->dInfo.bRightParent = res.bRightParent;
1605 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1607 update_ptr updGP( res.updGrandParent.ptr() );
1608 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1609 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1611 if ( help_delete( pOp, updRetire )) {
1612 // res.pLeaf is not deleted yet since RCU is blocked
1613 f( *node_traits::to_value_ptr( res.pLeaf ));
1619 // updGP has been changed by CAS
1620 help( updGP, updRetire );
1625 m_Stat.onEraseRetry();
1630 m_Stat.onEraseSuccess();
1634 template <typename ExemptPtr, typename Q, typename Less>
1635 bool extract_with_( ExemptPtr& dest, Q const& val, Less pred )
1637 typedef ellen_bintree::details::compare<
1640 opt::details::make_comparator_from_less<Less>,
1644 return extract_( dest, val, compare_functor() );
1647 template <typename ExemptPtr, typename Q, typename Compare>
1648 bool extract_( ExemptPtr& ptr, Q const& val, Compare cmp )
1650 check_deadlock_policy::check();
1652 retired_list updRetire;
1653 update_desc * pOp = nullptr;
1659 if ( !search( res, val, cmp ) ) {
1661 retire_update_desc( pOp, updRetire, false );
1662 m_Stat.onEraseFailed();
1666 if ( res.updGrandParent.bits() != update_desc::Clean )
1667 help( res.updGrandParent, updRetire );
1668 else if ( res.updParent.bits() != update_desc::Clean )
1669 help( res.updParent, updRetire );
1672 pOp = alloc_update_desc();
1673 if ( check_delete_precondition( res )) {
1674 pOp->dInfo.pGrandParent = res.pGrandParent;
1675 pOp->dInfo.pParent = res.pParent;
1676 pOp->dInfo.pLeaf = res.pLeaf;
1677 pOp->dInfo.bDisposeLeaf = false;
1678 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1679 pOp->dInfo.bRightParent = res.bRightParent;
1680 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1682 update_ptr updGP( res.updGrandParent.ptr() );
1683 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1684 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1686 if ( help_delete( pOp, updRetire )) {
1687 ptr = node_traits::to_value_ptr( res.pLeaf );
1693 // updGP has been changed by CAS
1694 help( updGP, updRetire );
1699 m_Stat.onEraseRetry();
1704 m_Stat.onEraseSuccess();
1709 template <typename ExemptPtr>
1710 bool extract_max_( ExemptPtr& result )
1712 check_deadlock_policy::check();
1714 retired_list updRetire;
1715 update_desc * pOp = nullptr;
1721 if ( !search_max( res )) {
1724 retire_update_desc( pOp, updRetire, false );
1725 m_Stat.onExtractMaxFailed();
1729 if ( res.updGrandParent.bits() != update_desc::Clean )
1730 help( res.updGrandParent, updRetire );
1731 else if ( res.updParent.bits() != update_desc::Clean )
1732 help( res.updParent, updRetire );
1735 pOp = alloc_update_desc();
1736 if ( check_delete_precondition( res ) ) {
1737 pOp->dInfo.pGrandParent = res.pGrandParent;
1738 pOp->dInfo.pParent = res.pParent;
1739 pOp->dInfo.pLeaf = res.pLeaf;
1740 pOp->dInfo.bDisposeLeaf = false;
1741 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1742 pOp->dInfo.bRightParent = res.bRightParent;
1743 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1745 update_ptr updGP( res.updGrandParent.ptr() );
1746 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1747 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1749 if ( help_delete( pOp, updRetire )) {
1750 result = node_traits::to_value_ptr( res.pLeaf );
1756 // updGP has been changed by CAS
1757 help( updGP, updRetire );
1761 m_Stat.onExtractMaxRetry();
1766 m_Stat.onExtractMaxSuccess();
1770 template <typename ExemptPtr>
1771 bool extract_min_(ExemptPtr& result)
1773 check_deadlock_policy::check();
1775 retired_list updRetire;
1776 update_desc * pOp = nullptr;
1782 if ( !search_min( res )) {
1785 retire_update_desc( pOp, updRetire, false );
1786 m_Stat.onExtractMinFailed();
1790 if ( res.updGrandParent.bits() != update_desc::Clean )
1791 help( res.updGrandParent, updRetire );
1792 else if ( res.updParent.bits() != update_desc::Clean )
1793 help( res.updParent, updRetire );
1796 pOp = alloc_update_desc();
1797 if ( check_delete_precondition( res ) ) {
1798 pOp->dInfo.pGrandParent = res.pGrandParent;
1799 pOp->dInfo.pParent = res.pParent;
1800 pOp->dInfo.pLeaf = res.pLeaf;
1801 pOp->dInfo.bDisposeLeaf = false;
1802 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1803 pOp->dInfo.bRightParent = res.bRightParent;
1804 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1806 update_ptr updGP( res.updGrandParent.ptr() );
1807 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1808 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1810 if ( help_delete( pOp, updRetire )) {
1811 result = node_traits::to_value_ptr( res.pLeaf );
1817 // updGP has been changed by CAS
1818 help( updGP, updRetire );
1823 m_Stat.onExtractMinRetry();
1828 m_Stat.onExtractMinSuccess();
1832 template <typename Q, typename Less, typename Func>
1833 bool find_with_( Q& val, Less pred, Func f ) const
1835 typedef ellen_bintree::details::compare<
1838 opt::details::make_comparator_from_less<Less>,
1844 if ( search( res, val, compare_functor() )) {
1845 assert( res.pLeaf );
1846 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1848 m_Stat.onFindSuccess();
1852 m_Stat.onFindFailed();
1856 template <typename Q, typename Func>
1857 bool find_( Q& key, Func f ) const
1861 if ( search( res, key, node_compare() )) {
1862 assert( res.pLeaf );
1863 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1865 m_Stat.onFindSuccess();
1869 m_Stat.onFindFailed();
1873 template <typename Q, typename Compare>
1874 value_type * get_( Q const& key, Compare cmp ) const
1876 assert( gc::is_locked());
1879 if ( search( res, key, cmp )) {
1880 m_Stat.onFindSuccess();
1881 return node_traits::to_value_ptr( res.pLeaf );
1884 m_Stat.onFindFailed();
1889 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1891 assert( gc::is_locked() );
1892 assert( res.updParent.bits() == update_desc::Clean );
1894 // check search result
1895 if ( static_cast<leaf_node *>( res.bRightLeaf
1896 ? res.pParent->m_pRight.load( memory_model::memory_order_relaxed )
1897 : res.pParent->m_pLeft.load( memory_model::memory_order_relaxed ) ) == res.pLeaf )
1899 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1901 int nCmp = node_compare()( val, *res.pLeaf );
1903 if ( res.pGrandParent ) {
1904 pNewInternal->infinite_key( 0 );
1905 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1906 assert( !res.pLeaf->infinite_key() );
1909 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1910 pNewInternal->infinite_key( 1 );
1912 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1913 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1916 assert( !res.pLeaf->is_internal() );
1917 pNewInternal->infinite_key( 0 );
1919 key_extractor()( pNewInternal->m_Key, val );
1920 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1921 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1922 assert( !res.pLeaf->infinite_key());
1925 update_desc * pOp = alloc_update_desc();
1927 pOp->iInfo.pParent = res.pParent;
1928 pOp->iInfo.pNew = pNewInternal;
1929 pOp->iInfo.pLeaf = res.pLeaf;
1930 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1932 update_ptr updCur( res.updParent.ptr() );
1933 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1934 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1938 retire_update_desc( pOp, updRetire, false );
1942 // updCur has been updated by CAS
1943 help( updCur, updRetire );
1944 retire_update_desc( pOp, updRetire, true );
1953 }} // namespace cds::intrusive
1955 #endif // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H