3 #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
4 #define __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
7 #include <functional> // ref
8 #include <cds/intrusive/details/ellen_bintree_base.h>
9 #include <cds/opt/compare.h>
10 #include <cds/details/binary_functor_wrapper.h>
11 #include <cds/urcu/details/check_deadlock.h>
12 #include <cds/urcu/exempt_ptr.h>
14 namespace cds { namespace intrusive {
16 namespace ellen_bintree {
19 struct base_node<cds::urcu::gc<RCU> >: public basic_node
21 typedef basic_node base_class;
23 base_node * m_pNextRetired;
25 typedef cds::urcu::gc<RCU> gc ; ///< Garbage collector
27 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
28 explicit base_node( bool bInternal )
29 : basic_node( bInternal ? internal : 0 )
30 , m_pNextRetired( nullptr )
34 } // namespace ellen_bintree
37 /// Ellen's et al binary search tree (RCU specialization)
38 /** @ingroup cds_intrusive_map
39 @ingroup cds_intrusive_tree
40 @anchor cds_intrusive_EllenBinTree_rcu
43 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
45 %EllenBinTree is an unbalanced leaf-oriented binary search tree that implements the <i>set</i>
46 abstract data type. Nodes maintains child pointers but not parent pointers.
47 Every internal node has exactly two children, and all data of type \p T currently in
48 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
49 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
50 may or may not be in the set. \p Key type is a subset of \p T type.
51 There should be exactly defined a key extracting functor for converting object of type \p T to
52 object of type \p Key.
54 Due to \p extract_min and \p extract_max member functions the \p %EllenBinTree can act as
55 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
56 the priority value plus some uniformly distributed random value.
58 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
59 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
61 @note In the current implementation we do not use helping technique described in original paper.
62 So, the current implementation is near to fine-grained lock-based tree.
63 Helping will be implemented in future release
65 <b>Template arguments</b> :
66 - \p RCU - one of \ref cds_urcu_gc "RCU type"
67 - \p Key - key type, a subset of \p T
68 - \p T - type to be stored in tree's leaf nodes. The type must be based on ellen_bintree::node
69 (for ellen_bintree::base_hook) or it must have a member of type ellen_bintree::node
70 (for ellen_bintree::member_hook).
71 - \p Traits - type traits. See ellen_bintree::type_traits for explanation.
73 It is possible to declare option-based tree with cds::intrusive::ellen_bintree::make_traits metafunction
74 instead of \p Traits template argument.
75 Template argument list \p Options of cds::intrusive::ellen_bintree::make_traits metafunction are:
76 - opt::hook - hook used. Possible values are: ellen_bintree::base_hook, ellen_bintree::member_hook, ellen_bintree::traits_hook.
77 If the option is not specified, <tt>ellen_bintree::base_hook<></tt> is used.
78 - ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
80 struct key_extractor {
81 void operator ()( Key& dest, T const& src );
84 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
85 - opt::compare - key compare functor. No default functor is provided.
86 If the option is not specified, \p %opt::less is used.
87 - opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
88 - opt::disposer - the functor used for dispose removed nodes. Default is opt::v::empty_disposer. Due the nature
89 of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
90 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
91 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
92 or opt::v::sequential_consistent (sequentially consisnent memory model).
93 - ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
94 default is CDS_DEFAULT_ALLOCATOR.
95 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
96 The number of simultaneously existing descriptors is bounded and depends on the number of threads
97 working with the tree and RCU buffer size (if RCU is buffered).
98 Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good candidate
99 for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
100 Also notice that size of update descriptor is constant and not dependent on the type of data
101 stored in the tree so single free-list object can be used for all \p %EllenBinTree objects.
102 - opt::node_allocator - the allocator used for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
103 - opt::stat - internal statistics. Available types: ellen_bintree::stat, ellen_bintree::empty_stat (the default)
104 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
106 @anchor cds_intrusive_EllenBinTree_rcu_less
107 <b>Predicate requirements</b>
109 opt::less, opt::compare and other predicates using with member fuctions should accept at least parameters
110 of type \p T and \p Key in any combination.
111 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
113 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
115 std::string m_strKey;
120 bool operator()( Foo const& v1, Foo const& v2 ) const
121 { return v1.m_strKey < v2.m_strKey ; }
123 bool operator()( Foo const& v, std::string const& s ) const
124 { return v.m_strKey < s ; }
126 bool operator()( std::string const& s, Foo const& v ) const
127 { return s < v.m_strKey ; }
129 // Support comparing std::string and char const *
130 bool operator()( std::string const& s, char const * p ) const
131 { return s.compare(p) < 0 ; }
133 bool operator()( Foo const& v, char const * p ) const
134 { return v.m_strKey.compare(p) < 0 ; }
136 bool operator()( char const * p, std::string const& s ) const
137 { return s.compare(p) > 0; }
139 bool operator()( char const * p, Foo const& v ) const
140 { return v.m_strKey.compare(p) > 0; }
144 @note Before including <tt><cds/intrusive/ellen_bintree_rcu.h></tt> you should include appropriate RCU header file,
145 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
149 Suppose we have the following Foo struct with string key type:
152 std::string m_strKey ; // The key
153 //... // other non-key data
157 We want to utilize RCU-based \p %cds::intrusive::EllenBinTree set for \p Foo data.
158 We may use base hook or member hook. Consider base hook variant.
159 First, we need deriving \p Foo struct from \p cds::intrusive::ellen_bintree::node:
161 #include <cds/urcu/general_buffered.h>
162 #include <cds/intrusive/ellen_bintree_rcu.h>
165 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
167 struct Foo: public cds::intrusive:ellen_bintree::node< gpb_rcu >
169 std::string m_strKey ; // The key
170 //... // other non-key data
174 Second, we need to implement auxiliary structures and functors:
175 - key extractor functor for extracting the key from \p Foo object.
176 Such functor is necessary because the tree internal nodes store the keys.
177 - \p less predicate. We want our set should accept \p std::string
178 and <tt>char const *</tt> parameters for searching, so our \p less
179 predicate should be non-trivial, see below.
180 - item counting feature: we want our set's \p size() member function
181 returns actual item count.
184 // Key extractor functor
185 struct my_key_extractor
187 void operator ()( std::string& key, Foo const& src ) const
195 bool operator()( Foo const& v1, Foo const& v2 ) const
196 { return v1.m_strKey < v2.m_strKey ; }
198 bool operator()( Foo const& v, std::string const& s ) const
199 { return v.m_strKey < s ; }
201 bool operator()( std::string const& s, Foo const& v ) const
202 { return s < v.m_strKey ; }
204 // Support comparing std::string and char const *
205 bool operator()( std::string const& s, char const * p ) const
206 { return s.compare(p) < 0 ; }
208 bool operator()( Foo const& v, char const * p ) const
209 { return v.m_strKey.compare(p) < 0 ; }
211 bool operator()( char const * p, std::string const& s ) const
212 { return s.compare(p) > 0; }
214 bool operator()( char const * p, Foo const& v ) const
215 { return v.m_strKey.compare(p) > 0; }
218 // Type traits for our set
219 // It is necessary to specify only those typedefs that differ from
220 // cds::intrusive::ellen_bintree::type_traits defaults.
221 struct set_traits: public cds::intrusive::ellen_bintree::type_traits
223 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > > hook;
224 typedef my_key_extractor key_extractor;
225 typedef my_less less;
226 typedef cds::atomicity::item_counter item_counter;
230 Now we declare \p %EllenBinTree set and use it:
232 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, set_traits > set_type;
238 Instead of declaring \p set_traits type traits we can use option-based syntax with \p %make_traits metafunction,
241 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo,
242 typename cds::intrusive::ellen_bintree::make_traits<
243 cds::opt::hook< cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > >
244 ,cds::intrusive::ellen_bintree::key_extractor< my_key_extractor >
245 ,cds::opt::less< my_less >
246 ,cds::opt::item_counter< cds::atomicity::item_counter >
251 Functionally, \p set_type and \p set_type2 are equivalent.
253 <b>Member-hooked tree</b>
255 Sometimes, we cannot use base hook, for example, when the \p Foo structure is external.
256 In such case we can use member hook feature.
258 #include <cds/urcu/general_buffered.h>
259 #include <cds/intrusive/ellen_bintree_rcu.h>
261 // Struct Foo is external and its declaration cannot be modified.
263 std::string m_strKey ; // The key
264 //... // other non-key data
268 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
274 cds::intrusive:ellen_bintree::node< gpb_rcu > set_hook ; // member hook
277 // Key extractor functor
278 struct member_key_extractor
280 void operator ()( std::string& key, MyFoo const& src ) const
282 key = src.m_foo.m_strKey;
288 bool operator()( MyFoo const& v1, MyFoo const& v2 ) const
289 { return v1.m_foo.m_strKey < v2.m_foo.m_strKey ; }
291 bool operator()( MyFoo const& v, std::string const& s ) const
292 { return v.m_foo.m_strKey < s ; }
294 bool operator()( std::string const& s, MyFoo const& v ) const
295 { return s < v.m_foo.m_strKey ; }
297 // Support comparing std::string and char const *
298 bool operator()( std::string const& s, char const * p ) const
299 { return s.compare(p) < 0 ; }
301 bool operator()( MyFoo const& v, char const * p ) const
302 { return v.m_foo.m_strKey.compare(p) < 0 ; }
304 bool operator()( char const * p, std::string const& s ) const
305 { return s.compare(p) > 0; }
307 bool operator()( char const * p, MyFoo const& v ) const
308 { return v.m_foo.m_strKey.compare(p) > 0; }
311 // Type traits for our member-based set
312 struct member_set_traits: public cds::intrusive::ellen_bintree::type_traits
314 cds::intrusive::ellen_bintree::member_hook< offsetof(MyFoo, set_hook), cds::opt::gc<gpb_rcu> > > hook;
315 typedef member_key_extractor key_extractor;
316 typedef member_less less;
317 typedef cds::atomicity::item_counter item_counter;
320 // Tree containing MyFoo objects
321 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, MyFoo, member_set_traits > member_set_type;
323 member_set_type theMemberSet;
326 <b>Multiple containers</b>
328 Sometimes we need that our \p Foo struct should be used in several different containers.
329 Suppose, \p Foo struct has two key fields:
332 std::string m_strKey ; // string key
333 int m_nKey ; // int key
334 //... // other non-key data fields
338 We want to build two intrusive \p %EllenBinTree sets: one indexed on \p Foo::m_strKey field,
339 another indexed on \p Foo::m_nKey field. To decide such case we should use a tag option for
342 #include <cds/urcu/general_buffered.h>
343 #include <cds/intrusive/ellen_bintree_rcu.h>
346 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
348 // Declare tag structs
349 struct int_tag ; // in key tag
350 struct string_tag ; // string key tag
352 // Foo struct is derived from two ellen_bintree::node class
353 // with different tags
355 : public cds::intrusive::ellen_bintree::node< gpb_rcu, cds::opt::tag< string_tag > >
356 , public cds::intrusive::ellen_bintree::node< gpb_rcu >, cds::opt::tag< int_tag >
358 std::string m_strKey ; // string key
359 int m_nKey ; // int key
360 //... // other non-key data fields
363 // String key extractor functor
364 struct string_key_extractor
366 void operator ()( std::string& key, Foo const& src ) const
372 // Int key extractor functor
373 struct int_key_extractor
375 void operator ()( int& key, Foo const& src ) const
381 // String less predicate
383 bool operator()( Foo const& v1, Foo const& v2 ) const
384 { return v1.m_strKey < v2.m_strKey ; }
386 bool operator()( Foo const& v, std::string const& s ) const
387 { return v.m_strKey < s ; }
389 bool operator()( std::string const& s, Foo const& v ) const
390 { return s < v.m_strKey ; }
392 // Support comparing std::string and char const *
393 bool operator()( std::string const& s, char const * p ) const
394 { return s.compare(p) < 0 ; }
396 bool operator()( Foo const& v, char const * p ) const
397 { return v.m_strKey.compare(p) < 0 ; }
399 bool operator()( char const * p, std::string const& s ) const
400 { return s.compare(p) > 0; }
402 bool operator()( char const * p, Foo const& v ) const
403 { return v.m_strKey.compare(p) > 0; }
406 // Int less predicate
408 bool operator()( Foo const& v1, Foo const& v2 ) const
409 { return v1.m_nKey < v2.m_nKey ; }
411 bool operator()( Foo const& v, int n ) const
412 { return v.m_nKey < n ; }
414 bool operator()( int n, Foo const& v ) const
415 { return n < v.m_nKey ; }
418 // Type traits for string-indexed set
419 struct string_set_traits: public cds::intrusive::ellen_bintree::type_traits
421 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< string_tag > > hook;
422 typedef string_key_extractor key_extractor;
423 typedef string_less less;
424 typedef cds::atomicity::item_counter item_counter;
427 // Type traits for int-indexed set
428 struct int_set_traits: public cds::intrusive::ellen_bintree::type_traits
430 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< int_tag > > hook;
431 typedef int_key_extractor key_extractor;
432 typedef int_less less;
433 typedef cds::atomicity::item_counter item_counter;
436 // Declare string-indexed set
437 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, string_set_traits > string_set_type;
438 string_set_type theStringSet;
440 // Declare int-indexed set
441 typedef cds::intrusive::EllenBinTree< gpb_rcu, int, Foo, int_set_traits > int_set_type;
442 int_set_type theIntSet;
444 // Now we can use theStringSet and theIntSet in our program
448 template < class RCU,
451 #ifdef CDS_DOXYGEN_INVOKED
452 class Traits = ellen_bintree::type_traits
457 class EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
460 typedef cds::urcu::gc<RCU> gc ; ///< RCU Garbage collector
461 typedef Key key_type ; ///< type of a key stored in internal nodes; key is a part of \p value_type
462 typedef T value_type ; ///< type of value stored in the binary tree
463 typedef Traits options ; ///< Traits template parameter
465 typedef typename options::hook hook ; ///< hook type
466 typedef typename hook::node_type node_type ; ///< node type
468 typedef typename options::disposer disposer ; ///< leaf node disposer
472 typedef ellen_bintree::base_node< gc > tree_node ; ///< Base type of tree node
473 typedef node_type leaf_node ; ///< Leaf node type
474 typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node ; ///< Internal node type
475 typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc ; ///< Update descriptor
476 typedef typename update_desc::update_ptr update_ptr ; ///< Marked pointer to update descriptor
480 typedef cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > exempt_ptr ; ///< pointer to extracted node
483 # ifdef CDS_DOXYGEN_INVOKED
484 typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
485 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< Node traits
487 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
488 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
490 static internal_node const& to_internal_node( tree_node const& n )
492 assert( n.is_internal() );
493 return static_cast<internal_node const&>( n );
496 static leaf_node const& to_leaf_node( tree_node const& n )
498 assert( n.is_leaf() );
499 return static_cast<leaf_node const&>( n );
504 typedef typename options::item_counter item_counter; ///< Item counting policy used
505 typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
506 typedef typename options::stat stat ; ///< internal statistics type
507 typedef typename options::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy
508 typedef typename options::key_extractor key_extractor ; ///< key extracting functor
510 typedef typename options::node_allocator node_allocator ; ///< Internal node allocator
511 typedef typename options::update_desc_allocator update_desc_allocator ; ///< Update descriptor allocator
513 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
515 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
519 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
521 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock > check_deadlock_policy;
523 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
524 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
526 struct search_result {
527 internal_node * pGrandParent;
528 internal_node * pParent;
530 update_ptr updParent;
531 update_ptr updGrandParent;
532 bool bRightLeaf ; // true if pLeaf is right child of pParent, false otherwise
533 bool bRightParent ; // true if pParent is right child of pGrandParent, false otherwise
536 :pGrandParent( nullptr )
540 ,bRightParent( false )
547 internal_node m_Root ; ///< Tree root node (key= Infinite2)
548 leaf_node m_LeafInf1;
549 leaf_node m_LeafInf2;
552 item_counter m_ItemCounter ; ///< item counter
553 mutable stat m_Stat ; ///< internal statistics
557 static void free_leaf_node( value_type * p )
562 internal_node * alloc_internal_node() const
564 m_Stat.onInternalNodeCreated();
565 internal_node * pNode = cxx_node_allocator().New();
570 static void free_internal_node( internal_node * pNode )
572 cxx_node_allocator().Delete( pNode );
575 struct internal_node_deleter {
576 void operator()( internal_node * p) const
578 free_internal_node( p );
582 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
584 update_desc * alloc_update_desc() const
586 m_Stat.onUpdateDescCreated();
587 return cxx_update_desc_allocator().New();
590 static void free_update_desc( update_desc * pDesc )
592 cxx_update_desc_allocator().Delete( pDesc );
597 update_desc * pUpdateHead;
598 tree_node * pNodeHead;
601 class forward_iterator
603 update_desc * m_pUpdate;
607 forward_iterator( retired_list const& l )
608 : m_pUpdate( l.pUpdateHead )
609 , m_pNode( l.pNodeHead )
613 : m_pUpdate( nullptr )
617 cds::urcu::retired_ptr operator *()
620 return cds::urcu::retired_ptr( reinterpret_cast<void *>( m_pUpdate ),
621 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
624 if ( m_pNode->is_leaf() ) {
625 return cds::urcu::retired_ptr( reinterpret_cast<void *>( node_traits::to_value_ptr( static_cast<leaf_node *>( m_pNode ))),
626 reinterpret_cast< cds::urcu::free_retired_ptr_func>( free_leaf_node ) );
629 return cds::urcu::retired_ptr( reinterpret_cast<void *>( static_cast<internal_node *>( m_pNode ) ),
630 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_internal_node ) );
633 return cds::urcu::retired_ptr( nullptr,
634 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
640 m_pUpdate = m_pUpdate->pNextRetire;
644 m_pNode = m_pNode->m_pNextRetired;
647 friend bool operator ==( forward_iterator const& i1, forward_iterator const& i2 )
649 return i1.m_pUpdate == i2.m_pUpdate && i1.m_pNode == i2.m_pNode;
651 friend bool operator !=( forward_iterator const& i1, forward_iterator const& i2 )
653 return !( i1 == i2 );
659 : pUpdateHead( nullptr )
660 , pNodeHead( nullptr )
665 gc::batch_retire( forward_iterator(*this), forward_iterator() );
668 void push( update_desc * p )
670 p->pNextRetire = pUpdateHead;
674 void push( tree_node * p )
676 p->m_pNextRetired = pNodeHead;
681 void retire_node( tree_node * pNode, retired_list& rl ) const
683 if ( pNode->is_leaf() ) {
684 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
685 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
688 assert( static_cast<internal_node *>( pNode ) != &m_Root );
689 m_Stat.onInternalNodeDeleted();
694 void retire_update_desc( update_desc * p, retired_list& rl, bool bDirect ) const
696 m_Stat.onUpdateDescDeleted();
698 free_update_desc( p );
703 void make_empty_tree()
705 m_Root.infinite_key( 2 );
706 m_LeafInf1.infinite_key( 1 );
707 m_LeafInf2.infinite_key( 2 );
708 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
709 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
714 /// Default constructor
717 static_assert( (!std::is_same< key_extractor, opt::none >::value), "The key extractor option must be specified" );
729 The function inserts \p val in the tree if it does not contain
730 an item with key equal to \p val.
732 The function applies RCU lock internally.
734 Returns \p true if \p val is placed into the set, \p false otherwise.
736 bool insert( value_type& val )
738 return insert( val, []( value_type& ) {} );
743 This function is intended for derived non-intrusive containers.
745 The function allows to split creating of new item into two part:
746 - create item with key only
747 - insert new item into the tree
748 - if inserting is success, calls \p f functor to initialize value-field of \p val.
750 The functor signature is:
752 void func( value_type& val );
754 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
755 \p val no any other changes could be made on this tree's item by concurrent threads.
756 The user-defined functor is called only if the inserting is success and may be passed by reference
759 RCU \p synchronize method can be called. RCU should not be locked.
761 template <typename Func>
762 bool insert( value_type& val, Func f )
764 check_deadlock_policy::check();
766 unique_internal_node_ptr pNewInternal;
767 retired_list updRetire;
774 if ( search( res, val, node_compare() )) {
775 if ( pNewInternal.get() )
776 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
777 m_Stat.onInsertFailed();
781 if ( res.updParent.bits() != update_desc::Clean )
782 help( res.updParent, updRetire );
784 if ( !pNewInternal.get() )
785 pNewInternal.reset( alloc_internal_node() );
787 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
789 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
794 m_Stat.onInsertRetry();
799 m_Stat.onInsertSuccess();
804 /// Ensures that the \p val exists in the tree
806 The operation performs inserting or changing data with lock-free manner.
808 If the item \p val is not found in the tree, then \p val is inserted into the tree.
809 Otherwise, the functor \p func is called with item found.
810 The functor signature is:
812 void func( bool bNew, value_type& item, value_type& val );
815 - \p bNew - \p true if the item has been inserted, \p false otherwise
816 - \p item - item of the tree
817 - \p val - argument \p val passed into the \p ensure function
818 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
819 refer to the same thing.
821 The functor can change non-key fields of the \p item; however, \p func must guarantee
822 that during changing no any other modifications could be made on this item by concurrent threads.
824 You can pass \p func argument by value or by reference using \p std::ref.
826 RCU \p synchronize method can be called. RCU should not be locked.
828 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
829 \p second is \p true if new item has been added or \p false if the item with \p key
830 already is in the tree.
832 template <typename Func>
833 std::pair<bool, bool> ensure( value_type& val, Func func )
835 check_deadlock_policy::check();
837 unique_internal_node_ptr pNewInternal;
838 retired_list updRetire;
845 if ( search( res, val, node_compare() )) {
846 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
847 if ( pNewInternal.get() )
848 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
849 m_Stat.onEnsureExist();
850 return std::make_pair( true, false );
853 if ( res.updParent.bits() != update_desc::Clean )
854 help( res.updParent, updRetire );
856 if ( !pNewInternal.get() )
857 pNewInternal.reset( alloc_internal_node() );
859 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
860 func( true, val, val );
861 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
865 m_Stat.onEnsureRetry();
870 m_Stat.onEnsureNew();
872 return std::make_pair( true, true );
875 /// Unlinks the item \p val from the tree
877 The function searches the item \p val in the tree and unlink it from the tree
878 if it is found and is equal to \p val.
880 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
881 and deletes the item found. \p unlink finds an item by key and deletes it
882 only if \p val is an item of the tree, i.e. the pointer to item found
883 is equal to <tt> &val </tt>.
885 RCU \p synchronize method can be called. RCU should not be locked.
887 The \ref disposer specified in \p Traits class template parameter is called
888 by garbage collector \p GC asynchronously.
890 The function returns \p true if success and \p false otherwise.
892 bool unlink( value_type& val )
894 return erase_( val, node_compare(),
895 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
896 [](value_type const&) {} );
899 /// Deletes the item from the tree
900 /** \anchor cds_intrusive_EllenBinTree_rcu_erase
901 The function searches an item with key equal to \p val in the tree,
902 unlinks it from the tree, and returns \p true.
903 If the item with key equal to \p val is not found the function return \p false.
905 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
907 RCU \p synchronize method can be called. RCU should not be locked.
909 template <typename Q>
910 bool erase( const Q& val )
912 return erase_( val, node_compare(),
913 []( Q const&, leaf_node const& ) -> bool { return true; },
914 [](value_type const&) {} );
917 /// Delete the item from the tree with comparing functor \p pred
919 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
920 but \p pred predicate is used for key comparing.
921 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
922 "Predicate requirements".
923 \p pred must imply the same element order as the comparator used for building the tree.
925 template <typename Q, typename Less>
926 bool erase_with( const Q& val, Less pred )
928 typedef ellen_bintree::details::compare<
931 opt::details::make_comparator_from_less<Less>,
935 return erase_( val, compare_functor(),
936 []( Q const&, leaf_node const& ) -> bool { return true; },
937 [](value_type const&) {} );
940 /// Deletes the item from the tree
941 /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
942 The function searches an item with key equal to \p val in the tree,
943 call \p f functor with item found, unlinks it from the tree, and returns \p true.
944 The \ref disposer specified in \p Traits class template parameter is called
945 by garbage collector \p GC asynchronously.
947 The \p Func interface is
950 void operator()( value_type const& item );
953 The functor can be passed by reference with <tt>boost:ref</tt>
955 If the item with key equal to \p val is not found the function return \p false.
957 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
959 RCU \p synchronize method can be called. RCU should not be locked.
961 template <typename Q, typename Func>
962 bool erase( Q const& val, Func f )
964 return erase_( val, node_compare(),
965 []( Q const&, leaf_node const& ) -> bool { return true; },
969 /// Delete the item from the tree with comparing functor \p pred
971 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
972 but \p pred predicate is used for key comparing.
973 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
974 "Predicate requirements".
975 \p pred must imply the same element order as the comparator used for building the tree.
977 template <typename Q, typename Less, typename Func>
978 bool erase_with( Q const& val, Less pred, Func f )
980 typedef ellen_bintree::details::compare<
983 opt::details::make_comparator_from_less<Less>,
987 return erase_( val, compare_functor(),
988 []( Q const&, leaf_node const& ) -> bool { return true; },
992 /// Extracts an item with minimal key from the tree
994 The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p result parameter.
995 If the tree is empty the function returns \p false.
997 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
998 It means that the function gets leftmost leaf of the tree and tries to unlink it.
999 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1000 So, the function returns the item with minimum key at the moment of tree traversing.
1002 RCU \p synchronize method can be called. RCU should NOT be locked.
1003 The function does not call the disposer for the item found.
1004 The disposer will be implicitly invoked when \p result object is destroyed or when
1005 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1006 @note Before reusing \p result object you should call its \p release() method.
1008 bool extract_min(exempt_ptr& result)
1010 return extract_min_(result);
1013 /// Extracts an item with maximal key from the tree
1015 The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p result prameter.
1016 If the tree is empty the function returns \p false.
1018 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
1019 It means that the function gets rightmost leaf of the tree and tries to unlink it.
1020 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
1021 So, the function returns the item with maximum key at the moment of tree traversing.
1023 RCU \p synchronize method can be called. RCU should NOT be locked.
1024 The function does not call the disposer for the item found.
1025 The disposer will be implicitly invoked when \p result object is destroyed or when
1026 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1027 @note Before reusing \p result object you should call its \p release() method.
1029 bool extract_max(exempt_ptr& result)
1031 return extract_max_(result);
1034 /// Extracts an item from the tree
1035 /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1036 The function searches an item with key equal to \p key in the tree,
1037 unlinks it, and returns pointer to an item found in \p result parameter.
1038 If the item with the key equal to \p key is not found the function returns \p false.
1040 RCU \p synchronize method can be called. RCU should NOT be locked.
1041 The function does not call the disposer for the item found.
1042 The disposer will be implicitly invoked when \p result object is destroyed or when
1043 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1044 @note Before reusing \p result object you should call its \p release() method.
1046 template <typename Q>
1047 bool extract( exempt_ptr& result, Q const& key )
1049 return extract_( result, key, node_compare() );
1052 /// Extracts an item from the set using \p pred for searching
1054 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_extract "extract(exempt_ptr&, Q const&)"
1055 but \p pred is used for key compare.
1056 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1057 "predicate requirements".
1058 \p pred must imply the same element order as the comparator used for building the tree.
1060 template <typename Q, typename Less>
1061 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
1063 return extract_with_( dest, val, pred );
1066 /// Finds the key \p val
1067 /** @anchor cds_intrusive_EllenBinTree_rcu_find_val
1068 The function searches the item with key equal to \p val
1069 and returns \p true if it is found, and \p false otherwise.
1071 Note the hash functor specified for class \p Traits template parameter
1072 should accept a parameter of type \p Q that can be not the same as \p value_type.
1074 The function applies RCU lock internally.
1076 template <typename Q>
1077 bool find( Q const& val ) const
1081 if ( search( res, val, node_compare() )) {
1082 m_Stat.onFindSuccess();
1086 m_Stat.onFindFailed();
1090 /// Finds the key \p val with comparing functor \p pred
1092 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)"
1093 but \p pred is used for key compare.
1094 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1095 "Predicate requirements".
1096 \p pred must imply the same element order as the comparator used for building the tree.
1097 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1099 template <typename Q, typename Less>
1100 bool find_with( Q const& val, Less pred ) const
1102 typedef ellen_bintree::details::compare<
1105 opt::details::make_comparator_from_less<Less>,
1111 if ( search( res, val, compare_functor() )) {
1112 m_Stat.onFindSuccess();
1115 m_Stat.onFindFailed();
1119 /// Finds the key \p val
1120 /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1121 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1122 The interface of \p Func functor is:
1125 void operator()( value_type& item, Q& val );
1128 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1130 You can pass \p f argument by value or by reference using \p std::ref.
1132 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1133 that \p item cannot be disposed during functor is executing.
1134 The functor does not serialize simultaneous access to the tree \p item. If such access is
1135 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1137 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
1138 can modify both arguments.
1140 The function applies RCU lock internally.
1142 The function returns \p true if \p val is found, \p false otherwise.
1144 template <typename Q, typename Func>
1145 bool find( Q& val, Func f ) const
1147 return find_( val, f );
1150 /// Finds the key \p val with comparing functor \p pred
1152 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1153 but \p pred is used for key comparison.
1154 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1155 "Predicate requirements".
1156 \p pred must imply the same element order as the comparator used for building the tree.
1158 template <typename Q, typename Less, typename Func>
1159 bool find_with( Q& val, Less pred, Func f ) const
1161 return find_with_( val, pred, f );
1164 /// Finds the key \p val
1165 /** @anchor cds_intrusive_EllenBinTree_rcu_find_cfunc
1166 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1167 The interface of \p Func functor is:
1170 void operator()( value_type& item, Q const& val );
1173 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1175 You can pass \p f argument by value or by reference using \p std::ref.
1177 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1178 that \p item cannot be disposed during functor is executing.
1179 The functor does not serialize simultaneous access to the tree \p item. If such access is
1180 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1182 The function applies RCU lock internally.
1184 The function returns \p true if \p val is found, \p false otherwise.
1186 template <typename Q, typename Func>
1187 bool find( Q const& val, Func f ) const
1189 return find_( val, f );
1192 /// Finds the key \p val with comparing functor \p pred
1194 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_cfunc "find(Q const&, Func)"
1195 but \p pred is used for key compare.
1196 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1197 "Predicate requirements".
1198 \p pred must imply the same element order as the comparator used for building the tree.
1200 template <typename Q, typename Less, typename Func>
1201 bool find_with( Q const& val, Less pred, Func f ) const
1203 return find_with_( val, pred, f );
1206 /// Finds \p key and return the item found
1207 /** \anchor cds_intrusive_EllenBinTree_rcu_get
1208 The function searches the item with key equal to \p key and returns the pointer to item found.
1209 If \p key is not found it returns \p nullptr.
1211 RCU should be locked before call the function.
1212 Returned pointer is valid while RCU is locked.
1214 template <typename Q>
1215 value_type * get( Q const& key ) const
1217 return get_( key, node_compare() );
1220 /// Finds \p key with \p pred predicate and return the item found
1222 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1223 but \p pred is used for comparing the keys.
1225 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1227 \p pred must imply the same element order as the comparator used for building the tree.
1229 template <typename Q, typename Less>
1230 value_type * get_with( Q const& key, Less pred ) const
1232 typedef ellen_bintree::details::compare<
1235 opt::details::make_comparator_from_less<Less>,
1239 return get_( key, compare_functor());
1242 /// Checks if the tree is empty
1245 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1248 /// Clears the tree (thread safe, non-atomic)
1250 The function unlink all items from the tree.
1251 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1255 assert( set.empty() );
1257 the assertion could be raised.
1259 For each leaf the \ref disposer will be called after unlinking.
1261 RCU \p synchronize method can be called. RCU should not be locked.
1266 while ( extract_min(ep) )
1270 /// Clears the tree (not thread safe)
1272 This function is not thread safe and may be called only when no other thread deals with the tree.
1273 The function is used in the tree destructor.
1280 internal_node * pParent = nullptr;
1281 internal_node * pGrandParent = nullptr;
1282 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1284 // Get leftmost leaf
1285 while ( pLeaf->is_internal() ) {
1286 pGrandParent = pParent;
1287 pParent = static_cast<internal_node *>( pLeaf );
1288 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1291 if ( pLeaf->infinite_key()) {
1292 // The tree is empty
1296 // Remove leftmost leaf and its parent node
1297 assert( pGrandParent );
1299 assert( pLeaf->is_leaf() );
1301 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1302 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
1303 free_internal_node( pParent );
1307 /// Returns item count in the tree
1309 Only leaf nodes containing user data are counted.
1311 The value returned depends on item counter type provided by \p Traits template parameter.
1312 If it is atomicity::empty_item_counter this function always returns 0.
1313 Therefore, the function is not suitable for checking the tree emptiness, use \ref empty
1314 member function for this purpose.
1318 return m_ItemCounter;
1321 /// Returns const reference to internal statistics
1322 stat const& statistics() const
1327 /// Checks internal consistency (not atomic, not thread-safe)
1329 The debugging function to check internal consistency of the tree.
1331 bool check_consistency() const
1333 return check_consistency( &m_Root );
1339 bool check_consistency( internal_node const * pRoot ) const
1341 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1342 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1346 if ( node_compare()( *pLeft, *pRoot ) < 0
1347 && node_compare()( *pRoot, *pRight ) <= 0
1348 && node_compare()( *pLeft, *pRight ) < 0 )
1351 if ( pLeft->is_internal() )
1352 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
1355 if ( bRet && pRight->is_internal() )
1356 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1364 void help( update_ptr pUpdate, retired_list& rl )
1367 switch ( pUpdate.bits() ) {
1368 case update_desc::IFlag:
1369 help_insert( pUpdate.ptr() );
1370 m_Stat.onHelpInsert();
1372 case update_desc::DFlag:
1373 //help_delete( pUpdate.ptr(), rl );
1374 //m_Stat.onHelpDelete();
1376 case update_desc::Mark:
1377 //help_marked( pUpdate.ptr() );
1378 //m_Stat.onHelpMark();
1384 void help_insert( update_desc * pOp )
1386 assert( gc::is_locked() );
1388 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1389 if ( pOp->iInfo.bRightLeaf ) {
1390 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1391 memory_model::memory_order_release, atomics::memory_order_relaxed );
1394 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1395 memory_model::memory_order_release, atomics::memory_order_relaxed );
1398 update_ptr cur( pOp, update_desc::IFlag );
1399 pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1400 memory_model::memory_order_release, atomics::memory_order_relaxed );
1403 bool check_delete_precondition( search_result& res )
1405 assert( res.pGrandParent != nullptr );
1408 static_cast<internal_node *>( res.bRightParent
1409 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1410 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1413 static_cast<leaf_node *>( res.bRightLeaf
1414 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1415 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1419 bool help_delete( update_desc * pOp, retired_list& rl )
1421 assert( gc::is_locked() );
1423 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1424 update_ptr pMark( pOp, update_desc::Mark );
1425 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1426 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1429 retire_node( pOp->dInfo.pParent, rl );
1430 // For extract operations the leaf should NOT be disposed
1431 if ( pOp->dInfo.bDisposeLeaf )
1432 retire_node( pOp->dInfo.pLeaf, rl );
1433 retire_update_desc( pOp, rl, false );
1437 else if ( pUpdate == pMark ) {
1438 // some other thread is processing help_marked()
1440 m_Stat.onHelpMark();
1444 // pUpdate has been changed by CAS
1445 help( pUpdate, rl );
1447 // Undo grandparent dInfo
1448 update_ptr pDel( pOp, update_desc::DFlag );
1449 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1450 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1452 retire_update_desc( pOp, rl, false );
1458 void help_marked( update_desc * pOp )
1460 assert( gc::is_locked() );
1462 tree_node * p = pOp->dInfo.pParent;
1463 if ( pOp->dInfo.bRightParent ) {
1464 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1465 pOp->dInfo.bRightLeaf
1466 ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1467 : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1468 memory_model::memory_order_release, atomics::memory_order_relaxed );
1471 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1472 pOp->dInfo.bRightLeaf
1473 ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1474 : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1475 memory_model::memory_order_release, atomics::memory_order_relaxed );
1478 update_ptr upd( pOp, update_desc::DFlag );
1479 pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1480 memory_model::memory_order_release, atomics::memory_order_relaxed );
1483 template <typename KeyValue, typename Compare>
1484 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1486 assert( gc::is_locked() );
1488 internal_node * pParent;
1489 internal_node * pGrandParent = nullptr;
1491 update_ptr updParent;
1492 update_ptr updGrandParent;
1494 bool bRightParent = false;
1500 pLeaf = const_cast<internal_node *>( &m_Root );
1501 updParent = nullptr;
1503 while ( pLeaf->is_internal() ) {
1504 pGrandParent = pParent;
1505 pParent = static_cast<internal_node *>( pLeaf );
1506 bRightParent = bRightLeaf;
1507 updGrandParent = updParent;
1508 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1510 switch ( updParent.bits() ) {
1511 case update_desc::DFlag:
1512 case update_desc::Mark:
1513 m_Stat.onSearchRetry();
1517 nCmp = cmp( key, *pParent );
1518 bRightLeaf = nCmp >= 0;
1519 pLeaf = nCmp < 0 ? pParent->m_pLeft.load( memory_model::memory_order_acquire )
1520 : pParent->m_pRight.load( memory_model::memory_order_acquire );
1523 assert( pLeaf->is_leaf() );
1524 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1526 res.pGrandParent = pGrandParent;
1527 res.pParent = pParent;
1528 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1529 res.updParent = updParent;
1530 res.updGrandParent = updGrandParent;
1531 res.bRightParent = bRightParent;
1532 res.bRightLeaf = bRightLeaf;
1537 bool search_min( search_result& res ) const
1539 assert( gc::is_locked() );
1541 internal_node * pParent;
1542 internal_node * pGrandParent = nullptr;
1544 update_ptr updParent;
1545 update_ptr updGrandParent;
1549 pLeaf = const_cast<internal_node *>( &m_Root );
1550 while ( pLeaf->is_internal() ) {
1551 pGrandParent = pParent;
1552 pParent = static_cast<internal_node *>( pLeaf );
1553 updGrandParent = updParent;
1554 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1556 switch ( updParent.bits() ) {
1557 case update_desc::DFlag:
1558 case update_desc::Mark:
1559 m_Stat.onSearchRetry();
1563 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1566 if ( pLeaf->infinite_key())
1569 res.pGrandParent = pGrandParent;
1570 res.pParent = pParent;
1571 assert( pLeaf->is_leaf() );
1572 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1573 res.updParent = updParent;
1574 res.updGrandParent = updGrandParent;
1575 res.bRightParent = false;
1576 res.bRightLeaf = false;
1581 bool search_max( search_result& res ) const
1583 assert( gc::is_locked() );
1585 internal_node * pParent;
1586 internal_node * pGrandParent = nullptr;
1588 update_ptr updParent;
1589 update_ptr updGrandParent;
1591 bool bRightParent = false;
1595 pLeaf = const_cast<internal_node *>( &m_Root );
1597 while ( pLeaf->is_internal() ) {
1598 pGrandParent = pParent;
1599 pParent = static_cast<internal_node *>( pLeaf );
1600 bRightParent = bRightLeaf;
1601 updGrandParent = updParent;
1602 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1604 switch ( updParent.bits() ) {
1605 case update_desc::DFlag:
1606 case update_desc::Mark:
1607 m_Stat.onSearchRetry();
1611 if ( pParent->infinite_key()) {
1612 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1616 pLeaf = pParent->m_pRight.load( memory_model::memory_order_acquire );
1621 if ( pLeaf->infinite_key())
1624 res.pGrandParent = pGrandParent;
1625 res.pParent = pParent;
1626 assert( pLeaf->is_leaf() );
1627 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1628 res.updParent = updParent;
1629 res.updGrandParent = updGrandParent;
1630 res.bRightParent = bRightParent;
1631 res.bRightLeaf = bRightLeaf;
1636 template <typename Q, typename Compare, typename Equal, typename Func>
1637 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1639 check_deadlock_policy::check();
1641 retired_list updRetire;
1642 update_desc * pOp = nullptr;
1648 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1650 retire_update_desc( pOp, updRetire, false );
1651 m_Stat.onEraseFailed();
1655 if ( res.updGrandParent.bits() != update_desc::Clean )
1656 help( res.updGrandParent, updRetire );
1657 else if ( res.updParent.bits() != update_desc::Clean )
1658 help( res.updParent, updRetire );
1661 pOp = alloc_update_desc();
1662 if ( check_delete_precondition( res ) ) {
1663 pOp->dInfo.pGrandParent = res.pGrandParent;
1664 pOp->dInfo.pParent = res.pParent;
1665 pOp->dInfo.pLeaf = res.pLeaf;
1666 pOp->dInfo.bDisposeLeaf = true;
1667 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1668 pOp->dInfo.bRightParent = res.bRightParent;
1669 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1671 update_ptr updGP( res.updGrandParent.ptr() );
1672 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1673 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1675 if ( help_delete( pOp, updRetire )) {
1676 // res.pLeaf is not deleted yet since RCU is blocked
1677 f( *node_traits::to_value_ptr( res.pLeaf ));
1683 // updGP has been changed by CAS
1684 help( updGP, updRetire );
1689 m_Stat.onEraseRetry();
1694 m_Stat.onEraseSuccess();
1698 template <typename ExemptPtr, typename Q, typename Less>
1699 bool extract_with_( ExemptPtr& dest, Q const& val, Less pred )
1701 typedef ellen_bintree::details::compare<
1704 opt::details::make_comparator_from_less<Less>,
1708 return extract_( dest, val, compare_functor() );
1711 template <typename ExemptPtr, typename Q, typename Compare>
1712 bool extract_( ExemptPtr& ptr, Q const& val, Compare cmp )
1714 check_deadlock_policy::check();
1716 retired_list updRetire;
1717 update_desc * pOp = nullptr;
1723 if ( !search( res, val, cmp ) ) {
1725 retire_update_desc( pOp, updRetire, false );
1726 m_Stat.onEraseFailed();
1730 if ( res.updGrandParent.bits() != update_desc::Clean )
1731 help( res.updGrandParent, updRetire );
1732 else if ( res.updParent.bits() != update_desc::Clean )
1733 help( res.updParent, updRetire );
1736 pOp = alloc_update_desc();
1737 if ( check_delete_precondition( res )) {
1738 pOp->dInfo.pGrandParent = res.pGrandParent;
1739 pOp->dInfo.pParent = res.pParent;
1740 pOp->dInfo.pLeaf = res.pLeaf;
1741 pOp->dInfo.bDisposeLeaf = false;
1742 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1743 pOp->dInfo.bRightParent = res.bRightParent;
1744 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1746 update_ptr updGP( res.updGrandParent.ptr() );
1747 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1748 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1750 if ( help_delete( pOp, updRetire )) {
1751 ptr = node_traits::to_value_ptr( res.pLeaf );
1757 // updGP has been changed by CAS
1758 help( updGP, updRetire );
1763 m_Stat.onEraseRetry();
1768 m_Stat.onEraseSuccess();
1773 template <typename ExemptPtr>
1774 bool extract_max_( ExemptPtr& result )
1776 check_deadlock_policy::check();
1778 retired_list updRetire;
1779 update_desc * pOp = nullptr;
1785 if ( !search_max( res )) {
1788 retire_update_desc( pOp, updRetire, false );
1789 m_Stat.onExtractMaxFailed();
1793 if ( res.updGrandParent.bits() != update_desc::Clean )
1794 help( res.updGrandParent, updRetire );
1795 else if ( res.updParent.bits() != update_desc::Clean )
1796 help( res.updParent, updRetire );
1799 pOp = alloc_update_desc();
1800 if ( check_delete_precondition( res ) ) {
1801 pOp->dInfo.pGrandParent = res.pGrandParent;
1802 pOp->dInfo.pParent = res.pParent;
1803 pOp->dInfo.pLeaf = res.pLeaf;
1804 pOp->dInfo.bDisposeLeaf = false;
1805 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1806 pOp->dInfo.bRightParent = res.bRightParent;
1807 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1809 update_ptr updGP( res.updGrandParent.ptr() );
1810 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1811 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1813 if ( help_delete( pOp, updRetire )) {
1814 result = node_traits::to_value_ptr( res.pLeaf );
1820 // updGP has been changed by CAS
1821 help( updGP, updRetire );
1825 m_Stat.onExtractMaxRetry();
1830 m_Stat.onExtractMaxSuccess();
1834 template <typename ExemptPtr>
1835 bool extract_min_(ExemptPtr& result)
1837 check_deadlock_policy::check();
1839 retired_list updRetire;
1840 update_desc * pOp = nullptr;
1846 if ( !search_min( res )) {
1849 retire_update_desc( pOp, updRetire, false );
1850 m_Stat.onExtractMinFailed();
1854 if ( res.updGrandParent.bits() != update_desc::Clean )
1855 help( res.updGrandParent, updRetire );
1856 else if ( res.updParent.bits() != update_desc::Clean )
1857 help( res.updParent, updRetire );
1860 pOp = alloc_update_desc();
1861 if ( check_delete_precondition( res ) ) {
1862 pOp->dInfo.pGrandParent = res.pGrandParent;
1863 pOp->dInfo.pParent = res.pParent;
1864 pOp->dInfo.pLeaf = res.pLeaf;
1865 pOp->dInfo.bDisposeLeaf = false;
1866 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1867 pOp->dInfo.bRightParent = res.bRightParent;
1868 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1870 update_ptr updGP( res.updGrandParent.ptr() );
1871 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1872 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1874 if ( help_delete( pOp, updRetire )) {
1875 result = node_traits::to_value_ptr( res.pLeaf );
1881 // updGP has been changed by CAS
1882 help( updGP, updRetire );
1887 m_Stat.onExtractMinRetry();
1892 m_Stat.onExtractMinSuccess();
1896 template <typename Q, typename Less, typename Func>
1897 bool find_with_( Q& val, Less pred, Func f ) const
1899 typedef ellen_bintree::details::compare<
1902 opt::details::make_comparator_from_less<Less>,
1908 if ( search( res, val, compare_functor() )) {
1909 assert( res.pLeaf );
1910 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1912 m_Stat.onFindSuccess();
1916 m_Stat.onFindFailed();
1920 template <typename Q, typename Func>
1921 bool find_( Q& key, Func f ) const
1925 if ( search( res, key, node_compare() )) {
1926 assert( res.pLeaf );
1927 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1929 m_Stat.onFindSuccess();
1933 m_Stat.onFindFailed();
1937 template <typename Q, typename Compare>
1938 value_type * get_( Q const& key, Compare cmp ) const
1940 assert( gc::is_locked());
1943 if ( search( res, key, cmp )) {
1944 m_Stat.onFindSuccess();
1945 return node_traits::to_value_ptr( res.pLeaf );
1948 m_Stat.onFindFailed();
1953 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1955 assert( gc::is_locked() );
1956 assert( res.updParent.bits() == update_desc::Clean );
1958 // check search result
1959 if ( static_cast<leaf_node *>( res.bRightLeaf
1960 ? res.pParent->m_pRight.load( memory_model::memory_order_relaxed )
1961 : res.pParent->m_pLeft.load( memory_model::memory_order_relaxed ) ) == res.pLeaf )
1963 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1965 int nCmp = node_compare()( val, *res.pLeaf );
1967 if ( res.pGrandParent ) {
1968 pNewInternal->infinite_key( 0 );
1969 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1970 assert( !res.pLeaf->infinite_key() );
1973 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1974 pNewInternal->infinite_key( 1 );
1976 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1977 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1980 assert( !res.pLeaf->is_internal() );
1981 pNewInternal->infinite_key( 0 );
1983 key_extractor()( pNewInternal->m_Key, val );
1984 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1985 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1986 assert( !res.pLeaf->infinite_key());
1989 update_desc * pOp = alloc_update_desc();
1991 pOp->iInfo.pParent = res.pParent;
1992 pOp->iInfo.pNew = pNewInternal;
1993 pOp->iInfo.pLeaf = res.pLeaf;
1994 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1996 update_ptr updCur( res.updParent.ptr() );
1997 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1998 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
2002 retire_update_desc( pOp, updRetire, false );
2006 // updCur has been updated by CAS
2007 help( updCur, updRetire );
2008 retire_update_desc( pOp, updRetire, true );
2017 }} // namespace cds::intrusive
2019 #endif // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H