3 #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
4 #define __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
7 #include <cds/intrusive/details/ellen_bintree_base.h>
8 #include <cds/opt/compare.h>
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 );
712 # ifndef CDS_CXX11_LAMBDA_SUPPORT
713 struct trivial_equal_functor {
714 template <typename Q>
715 bool operator()( Q const& , leaf_node const& ) const
721 struct empty_insert_functor {
722 void operator()( value_type& )
726 # if !defined(CDS_CXX11_LAMBDA_SUPPORT) || (CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
727 struct unlink_equal_functor {
728 bool operator()( value_type const& v, leaf_node const& n ) const
730 return &v == node_traits::to_value_ptr( n );
733 struct empty_erase_functor {
734 void operator()( value_type const& )
741 /// Default constructor
744 static_assert( (!std::is_same< key_extractor, opt::none >::value), "The key extractor option must be specified" );
756 The function inserts \p val in the tree if it does not contain
757 an item with key equal to \p val.
759 The function applies RCU lock internally.
761 Returns \p true if \p val is placed into the set, \p false otherwise.
763 bool insert( value_type& val )
765 # ifdef CDS_CXX11_LAMBDA_SUPPORT
766 return insert( val, []( value_type& ) {} );
768 return insert( val, empty_insert_functor() );
774 This function is intended for derived non-intrusive containers.
776 The function allows to split creating of new item into two part:
777 - create item with key only
778 - insert new item into the tree
779 - if inserting is success, calls \p f functor to initialize value-field of \p val.
781 The functor signature is:
783 void func( value_type& val );
785 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
786 \p val no any other changes could be made on this tree's item by concurrent threads.
787 The user-defined functor is called only if the inserting is success and may be passed by reference
788 using <tt>boost::ref</tt>
790 RCU \p synchronize method can be called. RCU should not be locked.
792 template <typename Func>
793 bool insert( value_type& val, Func f )
795 check_deadlock_policy::check();
797 unique_internal_node_ptr pNewInternal;
798 retired_list updRetire;
805 if ( search( res, val, node_compare() )) {
806 if ( pNewInternal.get() )
807 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
808 m_Stat.onInsertFailed();
812 if ( res.updParent.bits() != update_desc::Clean )
813 help( res.updParent, updRetire );
815 if ( !pNewInternal.get() )
816 pNewInternal.reset( alloc_internal_node() );
818 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
819 cds::unref(f)( val );
820 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
825 m_Stat.onInsertRetry();
830 m_Stat.onInsertSuccess();
835 /// Ensures that the \p val exists in the tree
837 The operation performs inserting or changing data with lock-free manner.
839 If the item \p val is not found in the tree, then \p val is inserted into the tree.
840 Otherwise, the functor \p func is called with item found.
841 The functor signature is:
843 void func( bool bNew, value_type& item, value_type& val );
846 - \p bNew - \p true if the item has been inserted, \p false otherwise
847 - \p item - item of the tree
848 - \p val - argument \p val passed into the \p ensure function
849 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
850 refer to the same thing.
852 The functor can change non-key fields of the \p item; however, \p func must guarantee
853 that during changing no any other modifications could be made on this item by concurrent threads.
855 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
857 RCU \p synchronize method can be called. RCU should not be locked.
859 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
860 \p second is \p true if new item has been added or \p false if the item with \p key
861 already is in the tree.
863 template <typename Func>
864 std::pair<bool, bool> ensure( value_type& val, Func func )
866 check_deadlock_policy::check();
868 unique_internal_node_ptr pNewInternal;
869 retired_list updRetire;
876 if ( search( res, val, node_compare() )) {
877 cds::unref(func)( false, *node_traits::to_value_ptr( res.pLeaf ), val );
878 if ( pNewInternal.get() )
879 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
880 m_Stat.onEnsureExist();
881 return std::make_pair( true, false );
884 if ( res.updParent.bits() != update_desc::Clean )
885 help( res.updParent, updRetire );
887 if ( !pNewInternal.get() )
888 pNewInternal.reset( alloc_internal_node() );
890 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
891 cds::unref(func)( true, val, val );
892 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
896 m_Stat.onEnsureRetry();
901 m_Stat.onEnsureNew();
903 return std::make_pair( true, true );
906 /// Unlinks the item \p val from the tree
908 The function searches the item \p val in the tree and unlink it from the tree
909 if it is found and is equal to \p val.
911 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
912 and deletes the item found. \p unlink finds an item by key and deletes it
913 only if \p val is an item of the tree, i.e. the pointer to item found
914 is equal to <tt> &val </tt>.
916 RCU \p synchronize method can be called. RCU should not be locked.
918 The \ref disposer specified in \p Traits class template parameter is called
919 by garbage collector \p GC asynchronously.
921 The function returns \p true if success and \p false otherwise.
923 bool unlink( value_type& val )
925 # if defined(CDS_CXX11_LAMBDA_SUPPORT) && !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
926 // vc10 generates an error for the lambda - it sees cds::intrusive::node_traits but not class-defined node_traits
927 return erase_( val, node_compare(),
928 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
929 [](value_type const&) {} );
931 return erase_( val, node_compare(), unlink_equal_functor(), empty_erase_functor() );
935 /// Deletes the item from the tree
936 /** \anchor cds_intrusive_EllenBinTree_rcu_erase
937 The function searches an item with key equal to \p val in the tree,
938 unlinks it from the tree, and returns \p true.
939 If the item with key equal to \p val is not found the function return \p false.
941 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
943 RCU \p synchronize method can be called. RCU should not be locked.
945 template <typename Q>
946 bool erase( const Q& val )
948 # ifdef CDS_CXX11_LAMBDA_SUPPORT
949 return erase_( val, node_compare(),
950 []( Q const&, leaf_node const& ) -> bool { return true; },
951 [](value_type const&) {} );
953 return erase_( val, node_compare(), trivial_equal_functor(), empty_erase_functor() );
957 /// Delete the item from the tree with comparing functor \p pred
959 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
960 but \p pred predicate is used for key comparing.
961 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
962 "Predicate requirements".
963 \p pred must imply the same element order as the comparator used for building the tree.
965 template <typename Q, typename Less>
966 bool erase_with( const Q& val, Less pred )
968 typedef ellen_bintree::details::compare<
971 opt::details::make_comparator_from_less<Less>,
975 # ifdef CDS_CXX11_LAMBDA_SUPPORT
976 return erase_( val, compare_functor(),
977 []( Q const&, leaf_node const& ) -> bool { return true; },
978 [](value_type const&) {} );
980 return erase_( val, compare_functor(), trivial_equal_functor(), empty_erase_functor() );
984 /// Deletes the item from the tree
985 /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
986 The function searches an item with key equal to \p val in the tree,
987 call \p f functor with item found, unlinks it from the tree, and returns \p true.
988 The \ref disposer specified in \p Traits class template parameter is called
989 by garbage collector \p GC asynchronously.
991 The \p Func interface is
994 void operator()( value_type const& item );
997 The functor can be passed by reference with <tt>boost:ref</tt>
999 If the item with key equal to \p val is not found the function return \p false.
1001 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1003 RCU \p synchronize method can be called. RCU should not be locked.
1005 template <typename Q, typename Func>
1006 bool erase( Q const& val, Func f )
1008 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1009 return erase_( val, node_compare(),
1010 []( Q const&, leaf_node const& ) -> bool { return true; },
1013 return erase_( val, node_compare(), trivial_equal_functor(), f );
1017 /// Delete the item from the tree with comparing functor \p pred
1019 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
1020 but \p pred predicate is used for key comparing.
1021 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1022 "Predicate requirements".
1023 \p pred must imply the same element order as the comparator used for building the tree.
1025 template <typename Q, typename Less, typename Func>
1026 bool erase_with( Q const& val, Less pred, Func f )
1028 typedef ellen_bintree::details::compare<
1031 opt::details::make_comparator_from_less<Less>,
1035 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1036 return erase_( val, compare_functor(),
1037 []( Q const&, leaf_node const& ) -> bool { return true; },
1040 return erase_( val, compare_functor(), trivial_equal_functor(), f );
1044 /// Extracts an item with minimal key from the tree
1046 The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p result parameter.
1047 If the tree is empty the function returns \p false.
1049 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
1050 It means that the function gets leftmost leaf of the tree and tries to unlink it.
1051 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1052 So, the function returns the item with minimum key at the moment of tree traversing.
1054 RCU \p synchronize method can be called. RCU should NOT be locked.
1055 The function does not call the disposer for the item found.
1056 The disposer will be implicitly invoked when \p result object is destroyed or when
1057 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1058 @note Before reusing \p result object you should call its \p release() method.
1060 bool extract_min(exempt_ptr& result)
1062 return extract_min_(result);
1065 /// Extracts an item with maximal key from the tree
1067 The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p result prameter.
1068 If the tree is empty the function returns \p false.
1070 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
1071 It means that the function gets rightmost leaf of the tree and tries to unlink it.
1072 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
1073 So, the function returns the item with maximum key at the moment of tree traversing.
1075 RCU \p synchronize method can be called. RCU should NOT be locked.
1076 The function does not call the disposer for the item found.
1077 The disposer will be implicitly invoked when \p result object is destroyed or when
1078 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1079 @note Before reusing \p result object you should call its \p release() method.
1081 bool extract_max(exempt_ptr& result)
1083 return extract_max_(result);
1086 /// Extracts an item from the tree
1087 /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1088 The function searches an item with key equal to \p key in the tree,
1089 unlinks it, and returns pointer to an item found in \p result parameter.
1090 If the item with the key equal to \p key is not found the function returns \p false.
1092 RCU \p synchronize method can be called. RCU should NOT be locked.
1093 The function does not call the disposer for the item found.
1094 The disposer will be implicitly invoked when \p result object is destroyed or when
1095 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1096 @note Before reusing \p result object you should call its \p release() method.
1098 template <typename Q>
1099 bool extract( exempt_ptr& result, Q const& key )
1101 return extract_( result, key, node_compare() );
1104 /// Extracts an item from the set using \p pred for searching
1106 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_extract "extract(exempt_ptr&, Q const&)"
1107 but \p pred is used for key compare.
1108 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1109 "predicate requirements".
1110 \p pred must imply the same element order as the comparator used for building the tree.
1112 template <typename Q, typename Less>
1113 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
1115 return extract_with_( dest, val, pred );
1118 /// Finds the key \p val
1119 /** @anchor cds_intrusive_EllenBinTree_rcu_find_val
1120 The function searches the item with key equal to \p val
1121 and returns \p true if it is found, and \p false otherwise.
1123 Note the hash functor specified for class \p Traits template parameter
1124 should accept a parameter of type \p Q that can be not the same as \p value_type.
1126 The function applies RCU lock internally.
1128 template <typename Q>
1129 bool find( Q const& val ) const
1133 if ( search( res, val, node_compare() )) {
1134 m_Stat.onFindSuccess();
1138 m_Stat.onFindFailed();
1142 /// Finds the key \p val with comparing functor \p pred
1144 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)"
1145 but \p pred is used for key compare.
1146 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1147 "Predicate requirements".
1148 \p pred must imply the same element order as the comparator used for building the tree.
1149 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1151 template <typename Q, typename Less>
1152 bool find_with( Q const& val, Less pred ) const
1154 typedef ellen_bintree::details::compare<
1157 opt::details::make_comparator_from_less<Less>,
1163 if ( search( res, val, compare_functor() )) {
1164 m_Stat.onFindSuccess();
1167 m_Stat.onFindFailed();
1171 /// Finds the key \p val
1172 /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1173 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1174 The interface of \p Func functor is:
1177 void operator()( value_type& item, Q& val );
1180 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1182 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1184 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1185 that \p item cannot be disposed during functor is executing.
1186 The functor does not serialize simultaneous access to the tree \p item. If such access is
1187 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1189 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
1190 can modify both arguments.
1192 The function applies RCU lock internally.
1194 The function returns \p true if \p val is found, \p false otherwise.
1196 template <typename Q, typename Func>
1197 bool find( Q& val, Func f ) const
1199 return find_( val, f );
1202 /// Finds the key \p val with comparing functor \p pred
1204 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1205 but \p pred is used for key comparison.
1206 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1207 "Predicate requirements".
1208 \p pred must imply the same element order as the comparator used for building the tree.
1210 template <typename Q, typename Less, typename Func>
1211 bool find_with( Q& val, Less pred, Func f ) const
1213 return find_with_( val, pred, f );
1216 /// Finds the key \p val
1217 /** @anchor cds_intrusive_EllenBinTree_rcu_find_cfunc
1218 The function searches the item with key equal to \p val and calls the functor \p f for item found.
1219 The interface of \p Func functor is:
1222 void operator()( value_type& item, Q const& val );
1225 where \p item is the item found, \p val is the <tt>find</tt> function argument.
1227 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1229 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1230 that \p item cannot be disposed during functor is executing.
1231 The functor does not serialize simultaneous access to the tree \p item. If such access is
1232 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1234 The function applies RCU lock internally.
1236 The function returns \p true if \p val is found, \p false otherwise.
1238 template <typename Q, typename Func>
1239 bool find( Q const& val, Func f ) const
1241 return find_( val, f );
1244 /// Finds the key \p val with comparing functor \p pred
1246 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_cfunc "find(Q const&, Func)"
1247 but \p pred is used for key compare.
1248 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1249 "Predicate requirements".
1250 \p pred must imply the same element order as the comparator used for building the tree.
1252 template <typename Q, typename Less, typename Func>
1253 bool find_with( Q const& val, Less pred, Func f ) const
1255 return find_with_( val, pred, f );
1258 /// Finds \p key and return the item found
1259 /** \anchor cds_intrusive_EllenBinTree_rcu_get
1260 The function searches the item with key equal to \p key and returns the pointer to item found.
1261 If \p key is not found it returns \p NULL.
1263 RCU should be locked before call the function.
1264 Returned pointer is valid while RCU is locked.
1266 template <typename Q>
1267 value_type * get( Q const& key ) const
1269 return get_( key, node_compare() );
1272 /// Finds \p key with \p pred predicate and return the item found
1274 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1275 but \p pred is used for comparing the keys.
1277 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1279 \p pred must imply the same element order as the comparator used for building the tree.
1281 template <typename Q, typename Less>
1282 value_type * get_with( Q const& key, Less pred ) const
1284 typedef ellen_bintree::details::compare<
1287 opt::details::make_comparator_from_less<Less>,
1291 return get_( key, compare_functor());
1294 /// Checks if the tree is empty
1297 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1300 /// Clears the tree (thread safe, non-atomic)
1302 The function unlink all items from the tree.
1303 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1307 assert( set.empty() );
1309 the assertion could be raised.
1311 For each leaf the \ref disposer will be called after unlinking.
1313 RCU \p synchronize method can be called. RCU should not be locked.
1318 while ( extract_min(ep) )
1322 /// Clears the tree (not thread safe)
1324 This function is not thread safe and may be called only when no other thread deals with the tree.
1325 The function is used in the tree destructor.
1332 internal_node * pParent = nullptr;
1333 internal_node * pGrandParent = nullptr;
1334 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1336 // Get leftmost leaf
1337 while ( pLeaf->is_internal() ) {
1338 pGrandParent = pParent;
1339 pParent = static_cast<internal_node *>( pLeaf );
1340 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1343 if ( pLeaf->infinite_key()) {
1344 // The tree is empty
1348 // Remove leftmost leaf and its parent node
1349 assert( pGrandParent );
1351 assert( pLeaf->is_leaf() );
1353 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1354 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
1355 free_internal_node( pParent );
1359 /// Returns item count in the tree
1361 Only leaf nodes containing user data are counted.
1363 The value returned depends on item counter type provided by \p Traits template parameter.
1364 If it is atomicity::empty_item_counter this function always returns 0.
1365 Therefore, the function is not suitable for checking the tree emptiness, use \ref empty
1366 member function for this purpose.
1370 return m_ItemCounter;
1373 /// Returns const reference to internal statistics
1374 stat const& statistics() const
1379 /// Checks internal consistency (not atomic, not thread-safe)
1381 The debugging function to check internal consistency of the tree.
1383 bool check_consistency() const
1385 return check_consistency( &m_Root );
1391 bool check_consistency( internal_node const * pRoot ) const
1393 tree_node * pLeft = pRoot->m_pLeft.load( CDS_ATOMIC::memory_order_relaxed );
1394 tree_node * pRight = pRoot->m_pRight.load( CDS_ATOMIC::memory_order_relaxed );
1398 if ( node_compare()( *pLeft, *pRoot ) < 0
1399 && node_compare()( *pRoot, *pRight ) <= 0
1400 && node_compare()( *pLeft, *pRight ) < 0 )
1403 if ( pLeft->is_internal() )
1404 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
1407 if ( bRet && pRight->is_internal() )
1408 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1416 void help( update_ptr pUpdate, retired_list& rl )
1419 switch ( pUpdate.bits() ) {
1420 case update_desc::IFlag:
1421 help_insert( pUpdate.ptr() );
1422 m_Stat.onHelpInsert();
1424 case update_desc::DFlag:
1425 //help_delete( pUpdate.ptr(), rl );
1426 //m_Stat.onHelpDelete();
1428 case update_desc::Mark:
1429 //help_marked( pUpdate.ptr() );
1430 //m_Stat.onHelpMark();
1436 void help_insert( update_desc * pOp )
1438 assert( gc::is_locked() );
1440 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1441 if ( pOp->iInfo.bRightLeaf ) {
1442 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1443 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1446 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1447 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1450 update_ptr cur( pOp, update_desc::IFlag );
1451 pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1452 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1455 bool check_delete_precondition( search_result& res )
1457 assert( res.pGrandParent != nullptr );
1460 static_cast<internal_node *>( res.bRightParent
1461 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1462 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1465 static_cast<leaf_node *>( res.bRightLeaf
1466 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1467 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1471 bool help_delete( update_desc * pOp, retired_list& rl )
1473 assert( gc::is_locked() );
1475 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1476 update_ptr pMark( pOp, update_desc::Mark );
1477 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1478 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1481 retire_node( pOp->dInfo.pParent, rl );
1482 // For extract operations the leaf should NOT be disposed
1483 if ( pOp->dInfo.bDisposeLeaf )
1484 retire_node( pOp->dInfo.pLeaf, rl );
1485 retire_update_desc( pOp, rl, false );
1489 else if ( pUpdate == pMark ) {
1490 // some other thread is processing help_marked()
1492 m_Stat.onHelpMark();
1496 // pUpdate has been changed by CAS
1497 help( pUpdate, rl );
1499 // Undo grandparent dInfo
1500 update_ptr pDel( pOp, update_desc::DFlag );
1501 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1502 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
1504 retire_update_desc( pOp, rl, false );
1510 void help_marked( update_desc * pOp )
1512 assert( gc::is_locked() );
1514 tree_node * p = pOp->dInfo.pParent;
1515 if ( pOp->dInfo.bRightParent ) {
1516 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1517 pOp->dInfo.bRightLeaf
1518 ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1519 : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1520 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1523 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1524 pOp->dInfo.bRightLeaf
1525 ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1526 : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1527 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1530 update_ptr upd( pOp, update_desc::DFlag );
1531 pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1532 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1535 template <typename KeyValue, typename Compare>
1536 bool search( search_result& res, KeyValue const& key, Compare cmp ) 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;
1552 pLeaf = const_cast<internal_node *>( &m_Root );
1553 updParent = nullptr;
1555 while ( pLeaf->is_internal() ) {
1556 pGrandParent = pParent;
1557 pParent = static_cast<internal_node *>( pLeaf );
1558 bRightParent = bRightLeaf;
1559 updGrandParent = updParent;
1560 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1562 switch ( updParent.bits() ) {
1563 case update_desc::DFlag:
1564 case update_desc::Mark:
1565 m_Stat.onSearchRetry();
1569 nCmp = cmp( key, *pParent );
1570 bRightLeaf = nCmp >= 0;
1571 pLeaf = nCmp < 0 ? pParent->m_pLeft.load( memory_model::memory_order_acquire )
1572 : pParent->m_pRight.load( memory_model::memory_order_acquire );
1575 assert( pLeaf->is_leaf() );
1576 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1578 res.pGrandParent = pGrandParent;
1579 res.pParent = pParent;
1580 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1581 res.updParent = updParent;
1582 res.updGrandParent = updGrandParent;
1583 res.bRightParent = bRightParent;
1584 res.bRightLeaf = bRightLeaf;
1589 bool search_min( search_result& res ) const
1591 assert( gc::is_locked() );
1593 internal_node * pParent;
1594 internal_node * pGrandParent = nullptr;
1596 update_ptr updParent;
1597 update_ptr updGrandParent;
1601 pLeaf = const_cast<internal_node *>( &m_Root );
1602 while ( pLeaf->is_internal() ) {
1603 pGrandParent = pParent;
1604 pParent = static_cast<internal_node *>( pLeaf );
1605 updGrandParent = updParent;
1606 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1608 switch ( updParent.bits() ) {
1609 case update_desc::DFlag:
1610 case update_desc::Mark:
1611 m_Stat.onSearchRetry();
1615 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1618 if ( pLeaf->infinite_key())
1621 res.pGrandParent = pGrandParent;
1622 res.pParent = pParent;
1623 assert( pLeaf->is_leaf() );
1624 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1625 res.updParent = updParent;
1626 res.updGrandParent = updGrandParent;
1627 res.bRightParent = false;
1628 res.bRightLeaf = false;
1633 bool search_max( search_result& res ) const
1635 assert( gc::is_locked() );
1637 internal_node * pParent;
1638 internal_node * pGrandParent = nullptr;
1640 update_ptr updParent;
1641 update_ptr updGrandParent;
1643 bool bRightParent = false;
1647 pLeaf = const_cast<internal_node *>( &m_Root );
1649 while ( pLeaf->is_internal() ) {
1650 pGrandParent = pParent;
1651 pParent = static_cast<internal_node *>( pLeaf );
1652 bRightParent = bRightLeaf;
1653 updGrandParent = updParent;
1654 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1656 switch ( updParent.bits() ) {
1657 case update_desc::DFlag:
1658 case update_desc::Mark:
1659 m_Stat.onSearchRetry();
1663 if ( pParent->infinite_key()) {
1664 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1668 pLeaf = pParent->m_pRight.load( memory_model::memory_order_acquire );
1673 if ( pLeaf->infinite_key())
1676 res.pGrandParent = pGrandParent;
1677 res.pParent = pParent;
1678 assert( pLeaf->is_leaf() );
1679 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1680 res.updParent = updParent;
1681 res.updGrandParent = updGrandParent;
1682 res.bRightParent = bRightParent;
1683 res.bRightLeaf = bRightLeaf;
1688 template <typename Q, typename Compare, typename Equal, typename Func>
1689 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1691 check_deadlock_policy::check();
1693 retired_list updRetire;
1694 update_desc * pOp = nullptr;
1700 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1702 retire_update_desc( pOp, updRetire, false );
1703 m_Stat.onEraseFailed();
1707 if ( res.updGrandParent.bits() != update_desc::Clean )
1708 help( res.updGrandParent, updRetire );
1709 else if ( res.updParent.bits() != update_desc::Clean )
1710 help( res.updParent, updRetire );
1713 pOp = alloc_update_desc();
1714 if ( check_delete_precondition( res ) ) {
1715 pOp->dInfo.pGrandParent = res.pGrandParent;
1716 pOp->dInfo.pParent = res.pParent;
1717 pOp->dInfo.pLeaf = res.pLeaf;
1718 pOp->dInfo.bDisposeLeaf = true;
1719 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1720 pOp->dInfo.bRightParent = res.bRightParent;
1721 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1723 update_ptr updGP( res.updGrandParent.ptr() );
1724 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1725 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1727 if ( help_delete( pOp, updRetire )) {
1728 // res.pLeaf is not deleted yet since RCU is blocked
1729 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ));
1735 // updGP has been changed by CAS
1736 help( updGP, updRetire );
1741 m_Stat.onEraseRetry();
1746 m_Stat.onEraseSuccess();
1750 template <typename ExemptPtr, typename Q, typename Less>
1751 bool extract_with_( ExemptPtr& dest, Q const& val, Less pred )
1753 typedef ellen_bintree::details::compare<
1756 opt::details::make_comparator_from_less<Less>,
1760 return extract_( dest, val, compare_functor() );
1763 template <typename ExemptPtr, typename Q, typename Compare>
1764 bool extract_( ExemptPtr& ptr, Q const& val, Compare cmp )
1766 check_deadlock_policy::check();
1768 retired_list updRetire;
1769 update_desc * pOp = nullptr;
1775 if ( !search( res, val, cmp ) ) {
1777 retire_update_desc( pOp, updRetire, false );
1778 m_Stat.onEraseFailed();
1782 if ( res.updGrandParent.bits() != update_desc::Clean )
1783 help( res.updGrandParent, updRetire );
1784 else if ( res.updParent.bits() != update_desc::Clean )
1785 help( res.updParent, updRetire );
1788 pOp = alloc_update_desc();
1789 if ( check_delete_precondition( res )) {
1790 pOp->dInfo.pGrandParent = res.pGrandParent;
1791 pOp->dInfo.pParent = res.pParent;
1792 pOp->dInfo.pLeaf = res.pLeaf;
1793 pOp->dInfo.bDisposeLeaf = false;
1794 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1795 pOp->dInfo.bRightParent = res.bRightParent;
1796 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1798 update_ptr updGP( res.updGrandParent.ptr() );
1799 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1800 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1802 if ( help_delete( pOp, updRetire )) {
1803 ptr = node_traits::to_value_ptr( res.pLeaf );
1809 // updGP has been changed by CAS
1810 help( updGP, updRetire );
1815 m_Stat.onEraseRetry();
1820 m_Stat.onEraseSuccess();
1825 template <typename ExemptPtr>
1826 bool extract_max_( ExemptPtr& result )
1828 check_deadlock_policy::check();
1830 retired_list updRetire;
1831 update_desc * pOp = nullptr;
1837 if ( !search_max( res )) {
1840 retire_update_desc( pOp, updRetire, false );
1841 m_Stat.onExtractMaxFailed();
1845 if ( res.updGrandParent.bits() != update_desc::Clean )
1846 help( res.updGrandParent, updRetire );
1847 else if ( res.updParent.bits() != update_desc::Clean )
1848 help( res.updParent, updRetire );
1851 pOp = alloc_update_desc();
1852 if ( check_delete_precondition( res ) ) {
1853 pOp->dInfo.pGrandParent = res.pGrandParent;
1854 pOp->dInfo.pParent = res.pParent;
1855 pOp->dInfo.pLeaf = res.pLeaf;
1856 pOp->dInfo.bDisposeLeaf = false;
1857 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1858 pOp->dInfo.bRightParent = res.bRightParent;
1859 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1861 update_ptr updGP( res.updGrandParent.ptr() );
1862 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1863 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1865 if ( help_delete( pOp, updRetire )) {
1866 result = node_traits::to_value_ptr( res.pLeaf );
1872 // updGP has been changed by CAS
1873 help( updGP, updRetire );
1877 m_Stat.onExtractMaxRetry();
1882 m_Stat.onExtractMaxSuccess();
1886 template <typename ExemptPtr>
1887 bool extract_min_(ExemptPtr& result)
1889 check_deadlock_policy::check();
1891 retired_list updRetire;
1892 update_desc * pOp = nullptr;
1898 if ( !search_min( res )) {
1901 retire_update_desc( pOp, updRetire, false );
1902 m_Stat.onExtractMinFailed();
1906 if ( res.updGrandParent.bits() != update_desc::Clean )
1907 help( res.updGrandParent, updRetire );
1908 else if ( res.updParent.bits() != update_desc::Clean )
1909 help( res.updParent, updRetire );
1912 pOp = alloc_update_desc();
1913 if ( check_delete_precondition( res ) ) {
1914 pOp->dInfo.pGrandParent = res.pGrandParent;
1915 pOp->dInfo.pParent = res.pParent;
1916 pOp->dInfo.pLeaf = res.pLeaf;
1917 pOp->dInfo.bDisposeLeaf = false;
1918 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1919 pOp->dInfo.bRightParent = res.bRightParent;
1920 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1922 update_ptr updGP( res.updGrandParent.ptr() );
1923 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1924 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1926 if ( help_delete( pOp, updRetire )) {
1927 result = node_traits::to_value_ptr( res.pLeaf );
1933 // updGP has been changed by CAS
1934 help( updGP, updRetire );
1939 m_Stat.onExtractMinRetry();
1944 m_Stat.onExtractMinSuccess();
1948 template <typename Q, typename Less, typename Func>
1949 bool find_with_( Q& val, Less pred, Func f ) const
1951 typedef ellen_bintree::details::compare<
1954 opt::details::make_comparator_from_less<Less>,
1960 if ( search( res, val, compare_functor() )) {
1961 assert( res.pLeaf );
1962 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), val );
1964 m_Stat.onFindSuccess();
1968 m_Stat.onFindFailed();
1972 template <typename Q, typename Func>
1973 bool find_( Q& key, Func f ) const
1977 if ( search( res, key, node_compare() )) {
1978 assert( res.pLeaf );
1979 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), key );
1981 m_Stat.onFindSuccess();
1985 m_Stat.onFindFailed();
1989 template <typename Q, typename Compare>
1990 value_type * get_( Q const& key, Compare cmp ) const
1992 assert( gc::is_locked());
1995 if ( search( res, key, cmp )) {
1996 m_Stat.onFindSuccess();
1997 return node_traits::to_value_ptr( res.pLeaf );
2000 m_Stat.onFindFailed();
2005 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
2007 assert( gc::is_locked() );
2008 assert( res.updParent.bits() == update_desc::Clean );
2010 // check search result
2011 if ( static_cast<leaf_node *>( res.bRightLeaf
2012 ? res.pParent->m_pRight.load( memory_model::memory_order_relaxed )
2013 : res.pParent->m_pLeft.load( memory_model::memory_order_relaxed ) ) == res.pLeaf )
2015 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
2017 int nCmp = node_compare()( val, *res.pLeaf );
2019 if ( res.pGrandParent ) {
2020 pNewInternal->infinite_key( 0 );
2021 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
2022 assert( !res.pLeaf->infinite_key() );
2025 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
2026 pNewInternal->infinite_key( 1 );
2028 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
2029 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
2032 assert( !res.pLeaf->is_internal() );
2033 pNewInternal->infinite_key( 0 );
2035 key_extractor()( pNewInternal->m_Key, val );
2036 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
2037 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
2038 assert( !res.pLeaf->infinite_key());
2041 update_desc * pOp = alloc_update_desc();
2043 pOp->iInfo.pParent = res.pParent;
2044 pOp->iInfo.pNew = pNewInternal;
2045 pOp->iInfo.pLeaf = res.pLeaf;
2046 pOp->iInfo.bRightLeaf = res.bRightLeaf;
2048 update_ptr updCur( res.updParent.ptr() );
2049 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
2050 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
2054 retire_update_desc( pOp, updRetire, false );
2058 // updCur has been updated by CAS
2059 help( updCur, updRetire );
2060 retire_update_desc( pOp, updRetire, true );
2069 }} // namespace cds::intrusive
2071 #endif // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H