3 #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H
4 #define CDSLIB_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 @attention 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 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
62 the operation done. Such solution allows greatly simplify the implementation of tree.
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 @note Before including <tt><cds/intrusive/ellen_bintree_rcu.h></tt> you should include appropriate RCU header file,
75 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
77 @anchor cds_intrusive_EllenBinTree_rcu_less
78 <b>Predicate requirements</b>
80 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
81 of type \p T and \p Key in any combination.
82 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
84 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
91 bool operator()( Foo const& v1, Foo const& v2 ) const
92 { return v1.m_strKey < v2.m_strKey ; }
94 bool operator()( Foo const& v, std::string const& s ) const
95 { return v.m_strKey < s ; }
97 bool operator()( std::string const& s, Foo const& v ) const
98 { return s < v.m_strKey ; }
100 // Support comparing std::string and char const *
101 bool operator()( std::string const& s, char const * p ) const
102 { return s.compare(p) < 0 ; }
104 bool operator()( Foo const& v, char const * p ) const
105 { return v.m_strKey.compare(p) < 0 ; }
107 bool operator()( char const * p, std::string const& s ) const
108 { return s.compare(p) > 0; }
110 bool operator()( char const * p, Foo const& v ) const
111 { return v.m_strKey.compare(p) > 0; }
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
438 typedef typename traits::back_off back_off; ///< back-off strategy
442 typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
443 typedef node_type leaf_node; ///< Leaf node type
444 typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node; ///< Internal node type
445 typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc; ///< Update descriptor
446 typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
450 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >; ///< pointer to extracted node
453 # ifdef CDS_DOXYGEN_INVOKED
454 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
455 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
457 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
458 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
460 static internal_node const& to_internal_node( tree_node const& n )
462 assert( n.is_internal());
463 return static_cast<internal_node const&>( n );
466 static leaf_node const& to_leaf_node( tree_node const& n )
468 assert( n.is_leaf());
469 return static_cast<leaf_node const&>( n );
474 typedef typename traits::item_counter item_counter; ///< Item counting policy used
475 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
476 typedef typename traits::stat stat; ///< internal statistics type
477 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
478 typedef typename traits::key_extractor key_extractor; ///< key extracting functor
480 typedef typename traits::node_allocator node_allocator; ///< Internal node allocator
481 typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
483 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
485 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
489 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
491 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock > check_deadlock_policy;
493 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
494 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
496 struct search_result {
497 internal_node * pGrandParent;
498 internal_node * pParent;
500 update_ptr updParent;
501 update_ptr updGrandParent;
502 bool bRightLeaf ; // true if pLeaf is right child of pParent, false otherwise
503 bool bRightParent ; // true if pParent is right child of pGrandParent, false otherwise
506 :pGrandParent( nullptr )
510 ,bRightParent( false )
517 internal_node m_Root; ///< Tree root node (key= Infinite2)
518 leaf_node m_LeafInf1;
519 leaf_node m_LeafInf2;
522 item_counter m_ItemCounter; ///< item counter
523 mutable stat m_Stat; ///< internal statistics
527 static void free_leaf_node( value_type * p )
532 internal_node * alloc_internal_node() const
534 m_Stat.onInternalNodeCreated();
535 internal_node * pNode = cxx_node_allocator().New();
540 static void free_internal_node( internal_node * pNode )
542 cxx_node_allocator().Delete( pNode );
545 struct internal_node_deleter {
546 void operator()( internal_node * p) const
548 free_internal_node( p );
552 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
554 update_desc * alloc_update_desc() const
556 m_Stat.onUpdateDescCreated();
557 return cxx_update_desc_allocator().New();
560 static void free_update_desc( update_desc * pDesc )
562 cxx_update_desc_allocator().Delete( pDesc );
567 update_desc * pUpdateHead;
568 tree_node * pNodeHead;
571 class forward_iterator
573 update_desc * m_pUpdate;
577 forward_iterator( retired_list const& l )
578 : m_pUpdate( l.pUpdateHead )
579 , m_pNode( l.pNodeHead )
583 : m_pUpdate( nullptr )
587 cds::urcu::retired_ptr operator *()
590 return cds::urcu::retired_ptr( reinterpret_cast<void *>( m_pUpdate ),
591 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ));
594 if ( m_pNode->is_leaf()) {
595 return cds::urcu::retired_ptr( reinterpret_cast<void *>( node_traits::to_value_ptr( static_cast<leaf_node *>( m_pNode ))),
596 reinterpret_cast< cds::urcu::free_retired_ptr_func>( free_leaf_node ));
599 return cds::urcu::retired_ptr( reinterpret_cast<void *>( static_cast<internal_node *>( m_pNode )),
600 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_internal_node ));
603 return cds::urcu::retired_ptr( nullptr,
604 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ));
610 m_pUpdate = m_pUpdate->pNextRetire;
614 m_pNode = m_pNode->m_pNextRetired;
617 friend bool operator ==( forward_iterator const& i1, forward_iterator const& i2 )
619 return i1.m_pUpdate == i2.m_pUpdate && i1.m_pNode == i2.m_pNode;
621 friend bool operator !=( forward_iterator const& i1, forward_iterator const& i2 )
623 return !( i1 == i2 );
629 : pUpdateHead( nullptr )
630 , pNodeHead( nullptr )
635 gc::batch_retire( forward_iterator(*this), forward_iterator());
638 void push( update_desc * p )
640 p->pNextRetire = pUpdateHead;
644 void push( tree_node * p )
646 p->m_pNextRetired = pNodeHead;
651 void retire_node( tree_node * pNode, retired_list& rl ) const
653 if ( pNode->is_leaf()) {
654 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
655 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
658 assert( static_cast<internal_node *>( pNode ) != &m_Root );
659 m_Stat.onInternalNodeDeleted();
664 void retire_update_desc( update_desc * p, retired_list& rl, bool bDirect ) const
666 m_Stat.onUpdateDescDeleted();
668 free_update_desc( p );
673 void make_empty_tree()
675 m_Root.infinite_key( 2 );
676 m_LeafInf1.infinite_key( 1 );
677 m_LeafInf2.infinite_key( 2 );
678 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
679 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
684 /// Default constructor
687 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
699 The function inserts \p val in the tree if it does not contain
700 an item with key equal to \p val.
702 The function applies RCU lock internally.
704 Returns \p true if \p val is placed into the set, \p false otherwise.
706 bool insert( value_type& val )
708 return insert( val, []( value_type& ) {} );
713 This function is intended for derived non-intrusive containers.
715 The function allows to split creating of new item into two part:
716 - create item with key only
717 - insert new item into the tree
718 - if inserting is success, calls \p f functor to initialize value-field of \p val.
720 The functor signature is:
722 void func( value_type& val );
724 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
725 \p val no any other changes could be made on this tree's item by concurrent threads.
726 The user-defined functor is called only if the inserting is success.
728 RCU \p synchronize method can be called. RCU should not be locked.
730 template <typename Func>
731 bool insert( value_type& val, Func f )
733 check_deadlock_policy::check();
735 unique_internal_node_ptr pNewInternal;
736 retired_list updRetire;
744 if ( search( res, val, node_compare())) {
745 if ( pNewInternal.get())
746 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
747 m_Stat.onInsertFailed();
751 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
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 help( res.updParent, updRetire );
765 m_Stat.onInsertRetry();
770 m_Stat.onInsertSuccess();
777 The operation performs inserting or changing data with lock-free manner.
779 If the item \p val is not found in the set, then \p val is inserted into the set
780 iff \p bAllowInsert is \p true.
781 Otherwise, the functor \p func is called with item found.
782 The functor \p func 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 set
789 - \p val - argument \p val passed into the \p %update() 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 std::pair<bool, bool> where \p first is \p true if operation is successfull,
799 i.e. the node has been inserted or updated,
800 \p second is \p true if new item has been added or \p false if the item with \p key
803 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
805 template <typename Func>
806 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
808 check_deadlock_policy::check();
810 unique_internal_node_ptr pNewInternal;
811 retired_list updRetire;
819 if ( search( res, val, node_compare())) {
820 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
821 if ( pNewInternal.get())
822 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
823 m_Stat.onEnsureExist();
824 return std::make_pair( true, false );
827 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
829 return std::make_pair( false, false );
831 if ( !pNewInternal.get())
832 pNewInternal.reset( alloc_internal_node());
834 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
835 func( true, val, val );
836 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
841 help( res.updParent, updRetire );
844 m_Stat.onEnsureRetry();
849 m_Stat.onEnsureNew();
851 return std::make_pair( true, true );
854 template <typename Func>
855 CDS_DEPRECATED("ensure() is deprecated, use update()")
856 std::pair<bool, bool> ensure( value_type& val, Func func )
858 return update( val, func, true );
862 /// Unlinks the item \p val from the tree
864 The function searches the item \p val in the tree and unlink it from the tree
865 if it is found and is equal to \p val.
867 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
868 and deletes the item found. \p %unlink() finds an item by key and deletes it
869 only if \p val is an item of the tree, i.e. the pointer to item found
870 is equal to <tt> &val </tt>.
872 RCU \p synchronize method can be called. RCU should not be locked.
874 The \ref disposer specified in \p Traits class template parameter is called
875 by garbage collector \p GC asynchronously.
877 The function returns \p true if success and \p false otherwise.
879 bool unlink( value_type& val )
881 return erase_( val, node_compare(),
882 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
883 [](value_type const&) {} );
886 /// Deletes the item from the tree
887 /** \anchor cds_intrusive_EllenBinTree_rcu_erase
888 The function searches an item with key equal to \p key in the tree,
889 unlinks it from the tree, and returns \p true.
890 If the item with key equal to \p key is not found the function return \p false.
892 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
894 RCU \p synchronize method can be called. RCU should not be locked.
896 template <typename Q>
897 bool erase( const Q& key )
899 return erase_( key, node_compare(),
900 []( Q const&, leaf_node const& ) -> bool { return true; },
901 [](value_type const&) {} );
904 /// Delete the item from the tree with comparing functor \p pred
906 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
907 but \p pred predicate is used for key comparing.
908 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
909 "Predicate requirements".
910 \p pred must imply the same element order as the comparator used for building the tree.
912 template <typename Q, typename Less>
913 bool erase_with( const Q& key, Less pred )
916 typedef ellen_bintree::details::compare<
919 opt::details::make_comparator_from_less<Less>,
923 return erase_( key, compare_functor(),
924 []( Q const&, leaf_node const& ) -> bool { return true; },
925 [](value_type const&) {} );
928 /// Deletes the item from the tree
929 /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
930 The function searches an item with key equal to \p key in the tree,
931 call \p f functor with item found, unlinks it from the tree, and returns \p true.
932 The \ref disposer specified in \p Traits class template parameter is called
933 by garbage collector \p GC asynchronously.
935 The \p Func interface is
938 void operator()( value_type const& item );
942 If the item with key equal to \p key is not found the function return \p false.
944 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
946 RCU \p synchronize method can be called. RCU should not be locked.
948 template <typename Q, typename Func>
949 bool erase( Q const& key, Func f )
951 return erase_( key, node_compare(),
952 []( Q const&, leaf_node const& ) -> bool { return true; },
956 /// Delete the item from the tree with comparing functor \p pred
958 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
959 but \p pred predicate is used for key comparing.
960 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
961 "Predicate requirements".
962 \p pred must imply the same element order as the comparator used for building the tree.
964 template <typename Q, typename Less, typename Func>
965 bool erase_with( Q const& key, Less pred, Func f )
968 typedef ellen_bintree::details::compare<
971 opt::details::make_comparator_from_less<Less>,
975 return erase_( key, compare_functor(),
976 []( Q const&, leaf_node const& ) -> bool { return true; },
980 /// Extracts an item with minimal key from the tree
982 The function searches an item with minimal key, unlinks it, and returns
983 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
984 If the tree is empty the function returns empty \p exempt_ptr.
986 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
987 It means that the function gets leftmost leaf of the tree and tries to unlink it.
988 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
989 So, the function returns the item with minimum 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 the returned object is destroyed or when
994 its \p release() member function is called.
996 exempt_ptr extract_min()
998 return exempt_ptr( extract_min_());
1001 /// Extracts an item with maximal key from the tree
1003 The function searches an item with maximal key, unlinks it, and returns
1004 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
1005 If the tree is empty the function returns empty \p exempt_ptr.
1007 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
1008 It means that the function gets rightmost leaf of the tree and tries to unlink it.
1009 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
1010 So, the function returns the item with maximum key at the moment of tree traversing.
1012 RCU \p synchronize method can be called. RCU should NOT be locked.
1013 The function does not call the disposer for the item found.
1014 The disposer will be implicitly invoked when the returned object is destroyed or when
1015 its \p release() member function is called.
1017 exempt_ptr extract_max()
1019 return exempt_ptr( extract_max_());
1022 /// Extracts an item from the tree
1023 /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1024 The function searches an item with key equal to \p key in the tree,
1025 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
1026 If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr.
1028 RCU \p synchronize method can be called. RCU should NOT be locked.
1029 The function does not call the disposer for the item found.
1030 The disposer will be implicitly invoked when the returned object is destroyed or when
1031 its \p release() member function is called.
1033 template <typename Q>
1034 exempt_ptr extract( Q const& key )
1036 return exempt_ptr( extract_( key, node_compare()));
1039 /// Extracts an item from the set using \p pred for searching
1041 The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
1042 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1043 "predicate requirements".
1044 \p pred must imply the same element order as the comparator used for building the tree.
1046 template <typename Q, typename Less>
1047 exempt_ptr extract_with( Q const& key, Less pred )
1049 return exempt_ptr( extract_with_( key, pred ));
1052 /// Checks whether the set contains \p key
1054 The function searches the item with key equal to \p key
1055 and returns \p true if it is found, and \p false otherwise.
1057 The function applies RCU lock internally.
1059 template <typename Q>
1060 bool contains( Q const& key ) const
1064 if ( search( res, key, node_compare())) {
1065 m_Stat.onFindSuccess();
1069 m_Stat.onFindFailed();
1073 template <typename Q>
1074 CDS_DEPRECATED("deprecated, use contains()")
1075 bool find( Q const& key ) const
1077 return contains( key );
1081 /// Checks whether the set contains \p key using \p pred predicate for searching
1083 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1084 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1085 "Predicate requirements".
1086 \p Less must imply the same element order as the comparator used for building the set.
1087 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1089 template <typename Q, typename Less>
1090 bool contains( Q const& key, Less pred ) const
1093 typedef ellen_bintree::details::compare<
1096 opt::details::make_comparator_from_less<Less>,
1102 if ( search( res, key, compare_functor())) {
1103 m_Stat.onFindSuccess();
1106 m_Stat.onFindFailed();
1110 template <typename Q, typename Less>
1111 CDS_DEPRECATED("deprecated, use contains()")
1112 bool find_with( Q const& key, Less pred ) const
1114 return contains( key, pred );
1118 /// Finds the key \p key
1119 /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1120 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1121 The interface of \p Func functor is:
1124 void operator()( value_type& item, Q& key );
1127 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1129 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1130 that \p item cannot be disposed during functor is executing.
1131 The functor does not serialize simultaneous access to the tree \p item. If such access is
1132 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1134 The function applies RCU lock internally.
1136 The function returns \p true if \p key is found, \p false otherwise.
1138 template <typename Q, typename Func>
1139 bool find( Q& key, Func f ) const
1141 return find_( key, f );
1144 template <typename Q, typename Func>
1145 bool find( Q const& key, Func f ) const
1147 return find_( key, f );
1151 /// Finds the key \p key with comparing functor \p pred
1153 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1154 but \p pred is used for key comparison.
1155 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1156 "Predicate requirements".
1157 \p pred must imply the same element order as the comparator used for building the tree.
1159 template <typename Q, typename Less, typename Func>
1160 bool find_with( Q& key, Less pred, Func f ) const
1162 return find_with_( key, pred, f );
1165 template <typename Q, typename Less, typename Func>
1166 bool find_with( Q const& key, Less pred, Func f ) const
1168 return find_with_( key, pred, f );
1172 /// Finds \p key and return the item found
1173 /** \anchor cds_intrusive_EllenBinTree_rcu_get
1174 The function searches the item with key equal to \p key and returns the pointer to item found.
1175 If \p key is not found it returns \p nullptr.
1177 RCU should be locked before call the function.
1178 Returned pointer is valid while RCU is locked.
1180 template <typename Q>
1181 value_type * get( Q const& key ) const
1183 return get_( key, node_compare());
1186 /// Finds \p key with \p pred predicate and return the item found
1188 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1189 but \p pred is used for comparing the keys.
1191 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1193 \p pred must imply the same element order as the comparator used for building the tree.
1195 template <typename Q, typename Less>
1196 value_type * get_with( Q const& key, Less pred ) const
1199 typedef ellen_bintree::details::compare<
1202 opt::details::make_comparator_from_less<Less>,
1206 return get_( key, compare_functor());
1209 /// Checks if the tree is empty
1212 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1215 /// Clears the tree (thread safe, not atomic)
1217 The function unlink all items from the tree.
1218 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1222 assert( set.empty());
1224 the assertion could be raised.
1226 For each leaf the \ref disposer will be called after unlinking.
1228 RCU \p synchronize method can be called. RCU should not be locked.
1232 for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min())
1236 /// Clears the tree (not thread safe)
1238 This function is not thread safe and may be called only when no other thread deals with the tree.
1239 The function is used in the tree destructor.
1246 internal_node * pParent = nullptr;
1247 internal_node * pGrandParent = nullptr;
1248 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1250 // Get leftmost leaf
1251 while ( pLeaf->is_internal()) {
1252 pGrandParent = pParent;
1253 pParent = static_cast<internal_node *>( pLeaf );
1254 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1257 if ( pLeaf->infinite_key()) {
1258 // The tree is empty
1262 // Remove leftmost leaf and its parent node
1263 assert( pGrandParent );
1265 assert( pLeaf->is_leaf());
1267 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1268 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf )));
1269 free_internal_node( pParent );
1273 /// Returns item count in the tree
1275 Only leaf nodes containing user data are counted.
1277 The value returned depends on item counter type provided by \p Traits template parameter.
1278 If it is \p atomicity::empty_item_counter this function always returns 0.
1280 The function is not suitable for checking the tree emptiness, use \p empty()
1281 member function for that.
1285 return m_ItemCounter;
1288 /// Returns const reference to internal statistics
1289 stat const& statistics() const
1294 /// Checks internal consistency (not atomic, not thread-safe)
1296 The debugging function to check internal consistency of the tree.
1298 bool check_consistency() const
1300 return check_consistency( &m_Root );
1306 bool check_consistency( internal_node const * pRoot ) const
1308 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1309 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1313 if ( node_compare()( *pLeft, *pRoot ) < 0
1314 && node_compare()( *pRoot, *pRight ) <= 0
1315 && node_compare()( *pLeft, *pRight ) < 0 )
1318 if ( pLeft->is_internal())
1319 bRet = check_consistency( static_cast<internal_node *>( pLeft ));
1322 if ( bRet && pRight->is_internal())
1323 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1331 void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
1334 switch ( pUpdate.bits()) {
1335 case update_desc::IFlag:
1336 help_insert( pUpdate.ptr());
1337 m_Stat.onHelpInsert();
1339 case update_desc::DFlag:
1340 //help_delete( pUpdate.ptr(), rl );
1341 //m_Stat.onHelpDelete();
1343 case update_desc::Mark:
1344 //help_marked( pUpdate.ptr());
1345 //m_Stat.onHelpMark();
1351 void help_insert( update_desc * pOp )
1353 assert( gc::is_locked());
1355 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1356 if ( pOp->iInfo.bRightLeaf ) {
1357 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1358 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1361 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1362 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1365 update_ptr cur( pOp, update_desc::IFlag );
1366 pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1367 memory_model::memory_order_release, atomics::memory_order_relaxed );
1370 bool check_delete_precondition( search_result& res )
1372 assert( res.pGrandParent != nullptr );
1375 static_cast<internal_node *>( res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1376 && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1379 bool help_delete( update_desc * pOp, retired_list& rl )
1381 assert( gc::is_locked());
1383 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1384 update_ptr pMark( pOp, update_desc::Mark );
1385 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1386 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1389 retire_node( pOp->dInfo.pParent, rl );
1390 // For extract operations the leaf should NOT be disposed
1391 if ( pOp->dInfo.bDisposeLeaf )
1392 retire_node( pOp->dInfo.pLeaf, rl );
1393 retire_update_desc( pOp, rl, false );
1397 else if ( pUpdate == pMark ) {
1398 // some other thread is processing help_marked()
1400 m_Stat.onHelpMark();
1404 // pUpdate has been changed by CAS
1405 help( pUpdate, rl );
1407 // Undo grandparent dInfo
1408 update_ptr pDel( pOp, update_desc::DFlag );
1409 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1410 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1412 retire_update_desc( pOp, rl, false );
1418 void help_marked( update_desc * pOp )
1420 assert( gc::is_locked());
1422 tree_node * p = pOp->dInfo.pParent;
1423 if ( pOp->dInfo.bRightParent ) {
1424 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1425 pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1426 memory_model::memory_order_release, atomics::memory_order_relaxed );
1429 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1430 pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1431 memory_model::memory_order_release, atomics::memory_order_relaxed );
1434 update_ptr upd( pOp, update_desc::DFlag );
1435 pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1436 memory_model::memory_order_release, atomics::memory_order_relaxed );
1439 template <typename KeyValue, typename Compare>
1440 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1442 assert( gc::is_locked());
1444 internal_node * pParent;
1445 internal_node * pGrandParent = nullptr;
1447 update_ptr updParent;
1448 update_ptr updGrandParent;
1450 bool bRightParent = false;
1456 pLeaf = const_cast<internal_node *>( &m_Root );
1457 updParent = nullptr;
1459 while ( pLeaf->is_internal()) {
1460 pGrandParent = pParent;
1461 pParent = static_cast<internal_node *>( pLeaf );
1462 bRightParent = bRightLeaf;
1463 updGrandParent = updParent;
1464 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1466 switch ( updParent.bits()) {
1467 case update_desc::DFlag:
1468 case update_desc::Mark:
1469 m_Stat.onSearchRetry();
1473 nCmp = cmp( key, *pParent );
1474 bRightLeaf = nCmp >= 0;
1475 pLeaf = pParent->get_child( nCmp >= 0, memory_model::memory_order_acquire );
1478 assert( pLeaf->is_leaf());
1479 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf));
1481 res.pGrandParent = pGrandParent;
1482 res.pParent = pParent;
1483 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1484 res.updParent = updParent;
1485 res.updGrandParent = updGrandParent;
1486 res.bRightParent = bRightParent;
1487 res.bRightLeaf = bRightLeaf;
1492 bool search_min( search_result& res ) const
1494 assert( gc::is_locked());
1496 internal_node * pParent;
1497 internal_node * pGrandParent = nullptr;
1499 update_ptr updParent;
1500 update_ptr updGrandParent;
1504 pLeaf = const_cast<internal_node *>( &m_Root );
1505 while ( pLeaf->is_internal()) {
1506 pGrandParent = pParent;
1507 pParent = static_cast<internal_node *>( pLeaf );
1508 updGrandParent = updParent;
1509 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1511 switch ( updParent.bits()) {
1512 case update_desc::DFlag:
1513 case update_desc::Mark:
1514 m_Stat.onSearchRetry();
1518 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1521 if ( pLeaf->infinite_key())
1524 res.pGrandParent = pGrandParent;
1525 res.pParent = pParent;
1526 assert( pLeaf->is_leaf());
1527 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1528 res.updParent = updParent;
1529 res.updGrandParent = updGrandParent;
1530 res.bRightParent = false;
1531 res.bRightLeaf = false;
1536 bool search_max( search_result& res ) const
1538 assert( gc::is_locked());
1540 internal_node * pParent;
1541 internal_node * pGrandParent = nullptr;
1543 update_ptr updParent;
1544 update_ptr updGrandParent;
1546 bool bRightParent = false;
1550 pLeaf = const_cast<internal_node *>( &m_Root );
1552 while ( pLeaf->is_internal()) {
1553 pGrandParent = pParent;
1554 pParent = static_cast<internal_node *>( pLeaf );
1555 bRightParent = bRightLeaf;
1556 updGrandParent = updParent;
1557 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1559 switch ( updParent.bits()) {
1560 case update_desc::DFlag:
1561 case update_desc::Mark:
1562 m_Stat.onSearchRetry();
1566 bRightLeaf = !pParent->infinite_key();
1567 pLeaf = pParent->get_child( bRightLeaf, memory_model::memory_order_acquire );
1570 if ( pLeaf->infinite_key())
1573 res.pGrandParent = pGrandParent;
1574 res.pParent = pParent;
1575 assert( pLeaf->is_leaf());
1576 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1577 res.updParent = updParent;
1578 res.updGrandParent = updGrandParent;
1579 res.bRightParent = bRightParent;
1580 res.bRightLeaf = bRightLeaf;
1585 template <typename Q, typename Compare, typename Equal, typename Func>
1586 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1588 check_deadlock_policy::check();
1590 retired_list updRetire;
1591 update_desc * pOp = nullptr;
1598 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf )) {
1600 retire_update_desc( pOp, updRetire, false );
1601 m_Stat.onEraseFailed();
1605 if ( res.updGrandParent.bits() != update_desc::Clean )
1606 help( res.updGrandParent, updRetire );
1607 else if ( res.updParent.bits() != update_desc::Clean )
1608 help( res.updParent, updRetire );
1611 pOp = alloc_update_desc();
1612 if ( check_delete_precondition( res )) {
1613 pOp->dInfo.pGrandParent = res.pGrandParent;
1614 pOp->dInfo.pParent = res.pParent;
1615 pOp->dInfo.pLeaf = res.pLeaf;
1616 pOp->dInfo.bDisposeLeaf = true;
1617 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1618 pOp->dInfo.bRightParent = res.bRightParent;
1619 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1621 update_ptr updGP( res.updGrandParent.ptr());
1622 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1623 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1625 if ( help_delete( pOp, updRetire )) {
1626 // res.pLeaf is not deleted yet since RCU is blocked
1627 f( *node_traits::to_value_ptr( res.pLeaf ));
1633 // updGP has been changed by CAS
1634 help( updGP, updRetire );
1640 m_Stat.onEraseRetry();
1645 m_Stat.onEraseSuccess();
1649 template <typename Q, typename Less>
1650 value_type * extract_with_( Q const& val, Less /*pred*/ )
1652 typedef ellen_bintree::details::compare<
1655 opt::details::make_comparator_from_less<Less>,
1659 return extract_( val, compare_functor());
1662 template <typename Q, typename Compare>
1663 value_type * extract_( Q const& val, Compare cmp )
1665 check_deadlock_policy::check();
1667 retired_list updRetire;
1668 update_desc * pOp = nullptr;
1671 value_type * pResult;
1676 if ( !search( res, val, cmp )) {
1678 retire_update_desc( pOp, updRetire, false );
1679 m_Stat.onEraseFailed();
1683 if ( res.updGrandParent.bits() != update_desc::Clean )
1684 help( res.updGrandParent, updRetire );
1685 else if ( res.updParent.bits() != update_desc::Clean )
1686 help( res.updParent, updRetire );
1689 pOp = alloc_update_desc();
1690 if ( check_delete_precondition( res )) {
1691 pOp->dInfo.pGrandParent = res.pGrandParent;
1692 pOp->dInfo.pParent = res.pParent;
1693 pOp->dInfo.pLeaf = res.pLeaf;
1694 pOp->dInfo.bDisposeLeaf = false;
1695 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1696 pOp->dInfo.bRightParent = res.bRightParent;
1697 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1699 update_ptr updGP( res.updGrandParent.ptr());
1700 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1701 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1703 if ( help_delete( pOp, updRetire )) {
1704 pResult = node_traits::to_value_ptr( res.pLeaf );
1710 // updGP has been changed by CAS
1711 help( updGP, updRetire );
1717 m_Stat.onEraseRetry();
1722 m_Stat.onEraseSuccess();
1727 value_type * extract_max_()
1729 check_deadlock_policy::check();
1731 retired_list updRetire;
1732 update_desc * pOp = nullptr;
1735 value_type * pResult;
1740 if ( !search_max( res )) {
1743 retire_update_desc( pOp, updRetire, false );
1744 m_Stat.onExtractMaxFailed();
1748 if ( res.updGrandParent.bits() != update_desc::Clean )
1749 help( res.updGrandParent, updRetire );
1750 else if ( res.updParent.bits() != update_desc::Clean )
1751 help( res.updParent, updRetire );
1754 pOp = alloc_update_desc();
1755 if ( check_delete_precondition( res )) {
1756 pOp->dInfo.pGrandParent = res.pGrandParent;
1757 pOp->dInfo.pParent = res.pParent;
1758 pOp->dInfo.pLeaf = res.pLeaf;
1759 pOp->dInfo.bDisposeLeaf = false;
1760 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1761 pOp->dInfo.bRightParent = res.bRightParent;
1762 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1764 update_ptr updGP( res.updGrandParent.ptr());
1765 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1766 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1768 if ( help_delete( pOp, updRetire )) {
1769 pResult = node_traits::to_value_ptr( res.pLeaf );
1775 // updGP has been changed by CAS
1776 help( updGP, updRetire );
1782 m_Stat.onExtractMaxRetry();
1787 m_Stat.onExtractMaxSuccess();
1791 value_type * extract_min_()
1793 check_deadlock_policy::check();
1795 retired_list updRetire;
1796 update_desc * pOp = nullptr;
1799 value_type * pResult;
1804 if ( !search_min( res )) {
1807 retire_update_desc( pOp, updRetire, false );
1808 m_Stat.onExtractMinFailed();
1812 if ( res.updGrandParent.bits() != update_desc::Clean )
1813 help( res.updGrandParent, updRetire );
1814 else if ( res.updParent.bits() != update_desc::Clean )
1815 help( res.updParent, updRetire );
1818 pOp = alloc_update_desc();
1819 if ( check_delete_precondition( res )) {
1820 pOp->dInfo.pGrandParent = res.pGrandParent;
1821 pOp->dInfo.pParent = res.pParent;
1822 pOp->dInfo.pLeaf = res.pLeaf;
1823 pOp->dInfo.bDisposeLeaf = false;
1824 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1825 pOp->dInfo.bRightParent = res.bRightParent;
1826 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1828 update_ptr updGP( res.updGrandParent.ptr());
1829 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1830 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1832 if ( help_delete( pOp, updRetire )) {
1833 pResult = node_traits::to_value_ptr( res.pLeaf );
1839 // updGP has been changed by CAS
1840 help( updGP, updRetire );
1846 m_Stat.onExtractMinRetry();
1851 m_Stat.onExtractMinSuccess();
1855 template <typename Q, typename Less, typename Func>
1856 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1858 typedef ellen_bintree::details::compare<
1861 opt::details::make_comparator_from_less<Less>,
1867 if ( search( res, val, compare_functor())) {
1868 assert( res.pLeaf );
1869 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1871 m_Stat.onFindSuccess();
1875 m_Stat.onFindFailed();
1879 template <typename Q, typename Func>
1880 bool find_( Q& key, Func f ) const
1884 if ( search( res, key, node_compare())) {
1885 assert( res.pLeaf );
1886 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1888 m_Stat.onFindSuccess();
1892 m_Stat.onFindFailed();
1896 template <typename Q, typename Compare>
1897 value_type * get_( Q const& key, Compare cmp ) const
1899 assert( gc::is_locked());
1902 if ( search( res, key, cmp )) {
1903 m_Stat.onFindSuccess();
1904 return node_traits::to_value_ptr( res.pLeaf );
1907 m_Stat.onFindFailed();
1912 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1914 assert( gc::is_locked());
1915 assert( res.updParent.bits() == update_desc::Clean );
1917 // check search result
1918 if ( static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf ) {
1919 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1921 int nCmp = node_compare()( val, *res.pLeaf );
1923 if ( res.pGrandParent ) {
1924 pNewInternal->infinite_key( 0 );
1925 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1926 assert( !res.pLeaf->infinite_key());
1929 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1930 pNewInternal->infinite_key( 1 );
1932 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1933 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1936 assert( !res.pLeaf->is_internal());
1937 pNewInternal->infinite_key( 0 );
1939 key_extractor()( pNewInternal->m_Key, val );
1940 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1941 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1942 assert( !res.pLeaf->infinite_key());
1945 update_desc * pOp = alloc_update_desc();
1947 pOp->iInfo.pParent = res.pParent;
1948 pOp->iInfo.pNew = pNewInternal;
1949 pOp->iInfo.pLeaf = res.pLeaf;
1950 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1952 update_ptr updCur( res.updParent.ptr());
1953 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1954 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1958 retire_update_desc( pOp, updRetire, false );
1962 // updCur has been updated by CAS
1963 help( updCur, updRetire );
1964 retire_update_desc( pOp, updRetire, true );
1973 }} // namespace cds::intrusive
1975 #endif // #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H