2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H
32 #define CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H
35 #include <cds/intrusive/details/ellen_bintree_base.h>
36 #include <cds/opt/compare.h>
37 #include <cds/details/binary_functor_wrapper.h>
38 #include <cds/urcu/details/check_deadlock.h>
39 #include <cds/urcu/exempt_ptr.h>
41 namespace cds { namespace intrusive {
43 namespace ellen_bintree {
46 struct base_node<cds::urcu::gc<RCU> >: public basic_node
48 typedef basic_node base_class;
50 base_node * m_pNextRetired;
52 typedef cds::urcu::gc<RCU> gc ; ///< Garbage collector
54 /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
55 explicit base_node( bool bInternal )
56 : basic_node( bInternal ? internal : 0 )
57 , m_pNextRetired( nullptr )
61 } // namespace ellen_bintree
64 /// Ellen's et al binary search tree (RCU specialization)
65 /** @ingroup cds_intrusive_map
66 @ingroup cds_intrusive_tree
67 @anchor cds_intrusive_EllenBinTree_rcu
70 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
72 %EllenBinTree is an unbalanced leaf-oriented binary search tree that implements the <i>set</i>
73 abstract data type. Nodes maintains child pointers but not parent pointers.
74 Every internal node has exactly two children, and all data of type \p T currently in
75 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
76 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
77 may or may not be in the set. \p Key type is a subset of \p T type.
78 There should be exactly defined a key extracting functor for converting object of type \p T to
79 object of type \p Key.
81 Due to \p extract_min and \p extract_max member functions the \p %EllenBinTree can act as
82 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
83 the priority value plus some uniformly distributed random value.
85 @attention Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
86 for uniformly distributed random keys, but in the worst case the complexity is <tt>O(N)</tt>.
88 @note In the current implementation we do not use helping technique described in the original paper.
89 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
90 the operation done. Such solution allows greatly simplify the implementation of tree.
92 <b>Template arguments</b>:
93 - \p RCU - one of \ref cds_urcu_gc "RCU type"
94 - \p Key - key type, a subset of \p T
95 - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
96 (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
97 (for \p ellen_bintree::member_hook).
98 - \p Traits - tree traits, default is \p ellen_bintree::traits
99 It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
100 instead of \p Traits template argument.
102 @note Before including <tt><cds/intrusive/ellen_bintree_rcu.h></tt> you should include appropriate RCU header file,
103 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
105 @anchor cds_intrusive_EllenBinTree_rcu_less
106 <b>Predicate requirements</b>
108 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
109 of type \p T and \p Key in any combination.
110 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
112 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
114 std::string m_strKey;
119 bool operator()( Foo const& v1, Foo const& v2 ) const
120 { return v1.m_strKey < v2.m_strKey ; }
122 bool operator()( Foo const& v, std::string const& s ) const
123 { return v.m_strKey < s ; }
125 bool operator()( std::string const& s, Foo const& v ) const
126 { return s < v.m_strKey ; }
128 // Support comparing std::string and char const *
129 bool operator()( std::string const& s, char const * p ) const
130 { return s.compare(p) < 0 ; }
132 bool operator()( Foo const& v, char const * p ) const
133 { return v.m_strKey.compare(p) < 0 ; }
135 bool operator()( char const * p, std::string const& s ) const
136 { return s.compare(p) > 0; }
138 bool operator()( char const * p, Foo const& v ) const
139 { return v.m_strKey.compare(p) > 0; }
143 @anchor cds_intrusive_EllenBinTree_usage
146 Suppose we have the following Foo struct with string key type:
149 std::string m_strKey ; // The key
150 //... // other non-key data
154 We want to utilize RCU-based \p %cds::intrusive::EllenBinTree set for \p Foo data.
155 We may use base hook or member hook. Consider base hook variant.
156 First, we need deriving \p Foo struct from \p cds::intrusive::ellen_bintree::node:
158 #include <cds/urcu/general_buffered.h>
159 #include <cds/intrusive/ellen_bintree_rcu.h>
162 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
164 struct Foo: public cds::intrusive:ellen_bintree::node< gpb_rcu >
166 std::string m_strKey ; // The key
167 //... // other non-key data
171 Second, we need to implement auxiliary structures and functors:
172 - key extractor functor for extracting the key from \p Foo object.
173 Such functor is necessary because the tree internal nodes store the keys.
174 - \p less predicate. We want our set should accept \p std::string
175 and <tt>char const *</tt> parameters for searching, so our \p less
176 predicate will not be trivial, see below.
177 - item counting feature: we want our set's \p size() member function
178 returns actual item count.
181 // Key extractor functor
182 struct my_key_extractor
184 void operator ()( std::string& key, Foo const& src ) const
192 bool operator()( Foo const& v1, Foo const& v2 ) const
193 { return v1.m_strKey < v2.m_strKey ; }
195 bool operator()( Foo const& v, std::string const& s ) const
196 { return v.m_strKey < s ; }
198 bool operator()( std::string const& s, Foo const& v ) const
199 { return s < v.m_strKey ; }
201 // Support comparing std::string and char const *
202 bool operator()( std::string const& s, char const * p ) const
203 { return s.compare(p) < 0 ; }
205 bool operator()( Foo const& v, char const * p ) const
206 { return v.m_strKey.compare(p) < 0 ; }
208 bool operator()( char const * p, std::string const& s ) const
209 { return s.compare(p) > 0; }
211 bool operator()( char const * p, Foo const& v ) const
212 { return v.m_strKey.compare(p) > 0; }
215 // Tree traits for our set
216 // It is necessary to specify only those typedefs that differ from
217 // cds::intrusive::ellen_bintree::traits defaults.
218 struct set_traits: public cds::intrusive::ellen_bintree::traits
220 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > > hook;
221 typedef my_key_extractor key_extractor;
222 typedef my_less less;
223 typedef cds::atomicity::item_counter item_counter;
227 Now we declare \p %EllenBinTree set and use it:
229 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, set_traits > set_type;
235 Instead of declaring \p set_traits type traits we can use option-based syntax with
236 \p ellen_bintree::make_traits metafunction, for example:
238 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo,
239 typename cds::intrusive::ellen_bintree::make_traits<
240 cds::opt::hook< cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > >
241 ,cds::intrusive::ellen_bintree::key_extractor< my_key_extractor >
242 ,cds::opt::less< my_less >
243 ,cds::opt::item_counter< cds::atomicity::item_counter >
248 Functionally, \p set_type and \p set_type2 are equivalent.
250 <b>Member-hooked tree</b>
252 Sometimes, we cannot use base hook, for example, when the \p Foo structure is external.
253 In such case we can use member hook feature.
255 #include <cds/urcu/general_buffered.h>
256 #include <cds/intrusive/ellen_bintree_rcu.h>
258 // Struct Foo is external and its declaration cannot be modified.
260 std::string m_strKey ; // The key
261 //... // other non-key data
265 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
271 cds::intrusive:ellen_bintree::node< gpb_rcu > set_hook; // member hook
274 // Key extractor functor
275 struct member_key_extractor
277 void operator ()( std::string& key, MyFoo const& src ) const
279 key = src.m_foo.m_strKey;
285 bool operator()( MyFoo const& v1, MyFoo const& v2 ) const
286 { return v1.m_foo.m_strKey < v2.m_foo.m_strKey ; }
288 bool operator()( MyFoo const& v, std::string const& s ) const
289 { return v.m_foo.m_strKey < s ; }
291 bool operator()( std::string const& s, MyFoo const& v ) const
292 { return s < v.m_foo.m_strKey ; }
294 // Support comparing std::string and char const *
295 bool operator()( std::string const& s, char const * p ) const
296 { return s.compare(p) < 0 ; }
298 bool operator()( MyFoo const& v, char const * p ) const
299 { return v.m_foo.m_strKey.compare(p) < 0 ; }
301 bool operator()( char const * p, std::string const& s ) const
302 { return s.compare(p) > 0; }
304 bool operator()( char const * p, MyFoo const& v ) const
305 { return v.m_foo.m_strKey.compare(p) > 0; }
308 // Tree traits for our member-based set
309 struct member_set_traits: public cds::intrusive::ellen_bintree::traits
311 cds::intrusive::ellen_bintree::member_hook< offsetof(MyFoo, set_hook), cds::opt::gc<gpb_rcu> > > hook;
312 typedef member_key_extractor key_extractor;
313 typedef member_less less;
314 typedef cds::atomicity::item_counter item_counter;
317 // Tree containing MyFoo objects
318 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, MyFoo, member_set_traits > member_set_type;
320 member_set_type theMemberSet;
323 <b>Multiple containers</b>
325 Sometimes we need that our \p Foo struct should be used in several different containers.
326 Suppose, \p Foo struct has two key fields:
329 std::string m_strKey ; // string key
330 int m_nKey ; // int key
331 //... // other non-key data fields
335 We want to build two intrusive \p %EllenBinTree sets: one indexed on \p Foo::m_strKey field,
336 another indexed on \p Foo::m_nKey field. To decide such case we should use a tag option for
339 #include <cds/urcu/general_buffered.h>
340 #include <cds/intrusive/ellen_bintree_rcu.h>
343 typedef cds::urcu::gc< cds::urcu::general_buffered<> > gpb_rcu;
345 // Declare tag structs
346 struct int_tag ; // int key tag
347 struct string_tag ; // string key tag
349 // Foo struct is derived from two ellen_bintree::node class
350 // with different tags
352 : public cds::intrusive::ellen_bintree::node< gpb_rcu, cds::opt::tag< string_tag >>
353 , public cds::intrusive::ellen_bintree::node< gpb_rcu, cds::opt::tag< int_tag >>
355 std::string m_strKey ; // string key
356 int m_nKey ; // int key
357 //... // other non-key data fields
360 // String key extractor functor
361 struct string_key_extractor
363 void operator ()( std::string& key, Foo const& src ) const
369 // Int key extractor functor
370 struct int_key_extractor
372 void operator ()( int& key, Foo const& src ) const
378 // String less predicate
380 bool operator()( Foo const& v1, Foo const& v2 ) const
381 { return v1.m_strKey < v2.m_strKey ; }
383 bool operator()( Foo const& v, std::string const& s ) const
384 { return v.m_strKey < s ; }
386 bool operator()( std::string const& s, Foo const& v ) const
387 { return s < v.m_strKey ; }
389 // Support comparing std::string and char const *
390 bool operator()( std::string const& s, char const * p ) const
391 { return s.compare(p) < 0 ; }
393 bool operator()( Foo const& v, char const * p ) const
394 { return v.m_strKey.compare(p) < 0 ; }
396 bool operator()( char const * p, std::string const& s ) const
397 { return s.compare(p) > 0; }
399 bool operator()( char const * p, Foo const& v ) const
400 { return v.m_strKey.compare(p) > 0; }
403 // Int less predicate
405 bool operator()( Foo const& v1, Foo const& v2 ) const
406 { return v1.m_nKey < v2.m_nKey ; }
408 bool operator()( Foo const& v, int n ) const
409 { return v.m_nKey < n ; }
411 bool operator()( int n, Foo const& v ) const
412 { return n < v.m_nKey ; }
415 // Type traits for string-indexed set
416 struct string_set_traits: public cds::intrusive::ellen_bintree::traits
418 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< string_tag > > hook;
419 typedef string_key_extractor key_extractor;
420 typedef string_less less;
421 typedef cds::atomicity::item_counter item_counter;
424 // Type traits for int-indexed set
425 struct int_set_traits: public cds::intrusive::ellen_bintree::traits
427 typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< int_tag > > hook;
428 typedef int_key_extractor key_extractor;
429 typedef int_less less;
430 typedef cds::atomicity::item_counter item_counter;
433 // Declare string-indexed set
434 typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, string_set_traits > string_set_type;
435 string_set_type theStringSet;
437 // Declare int-indexed set
438 typedef cds::intrusive::EllenBinTree< gpb_rcu, int, Foo, int_set_traits > int_set_type;
439 int_set_type theIntSet;
441 // Now we can use theStringSet and theIntSet in our program
445 template < class RCU,
448 #ifdef CDS_DOXYGEN_INVOKED
449 class Traits = ellen_bintree::traits
454 class EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
457 typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
458 typedef Key key_type; ///< type of a key stored in internal nodes; key is a part of \p value_type
459 typedef T value_type; ///< type of value stored in the binary tree
460 typedef Traits traits; ///< Traits template parameter
462 typedef typename traits::hook hook; ///< hook type
463 typedef typename hook::node_type node_type; ///< node type
465 typedef typename traits::disposer disposer; ///< leaf node disposer
466 typedef typename traits::back_off back_off; ///< back-off strategy
470 typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
471 typedef node_type leaf_node; ///< Leaf node type
472 typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node; ///< Internal node type
473 typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc; ///< Update descriptor
474 typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
478 using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >; ///< pointer to extracted node
481 # ifdef CDS_DOXYGEN_INVOKED
482 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
483 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
485 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
486 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
488 static internal_node const& to_internal_node( tree_node const& n )
490 assert( n.is_internal());
491 return static_cast<internal_node const&>( n );
494 static leaf_node const& to_leaf_node( tree_node const& n )
496 assert( n.is_leaf());
497 return static_cast<leaf_node const&>( n );
502 typedef typename traits::item_counter item_counter; ///< Item counting policy used
503 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
504 typedef typename traits::stat stat; ///< internal statistics type
505 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
506 typedef typename traits::key_extractor key_extractor; ///< key extracting functor
508 typedef typename traits::node_allocator node_allocator; ///< Internal node allocator
509 typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
511 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
513 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
517 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
519 typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock > check_deadlock_policy;
521 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
522 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
524 struct search_result {
525 internal_node * pGrandParent;
526 internal_node * pParent;
528 update_ptr updParent;
529 update_ptr updGrandParent;
530 bool bRightLeaf ; // true if pLeaf is right child of pParent, false otherwise
531 bool bRightParent ; // true if pParent is right child of pGrandParent, false otherwise
534 :pGrandParent( nullptr )
538 ,bRightParent( false )
545 internal_node m_Root; ///< Tree root node (key= Infinite2)
546 leaf_node m_LeafInf1;
547 leaf_node m_LeafInf2;
550 item_counter m_ItemCounter; ///< item counter
551 mutable stat m_Stat; ///< internal statistics
555 static void free_leaf_node( value_type * p )
560 internal_node * alloc_internal_node() const
562 m_Stat.onInternalNodeCreated();
563 internal_node * pNode = cxx_node_allocator().New();
568 static void free_internal_node( internal_node * pNode )
570 cxx_node_allocator().Delete( pNode );
573 struct internal_node_deleter {
574 void operator()( internal_node * p) const
576 free_internal_node( p );
580 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
582 update_desc * alloc_update_desc() const
584 m_Stat.onUpdateDescCreated();
585 return cxx_update_desc_allocator().New();
588 static void free_update_desc( update_desc * pDesc )
590 cxx_update_desc_allocator().Delete( pDesc );
595 update_desc * pUpdateHead;
596 tree_node * pNodeHead;
599 class forward_iterator
601 update_desc * m_pUpdate;
605 forward_iterator( retired_list const& l )
606 : m_pUpdate( l.pUpdateHead )
607 , m_pNode( l.pNodeHead )
611 : m_pUpdate( nullptr )
615 cds::urcu::retired_ptr operator *()
618 return cds::urcu::retired_ptr( reinterpret_cast<void *>( m_pUpdate ),
619 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ));
622 if ( m_pNode->is_leaf()) {
623 return cds::urcu::retired_ptr( reinterpret_cast<void *>( node_traits::to_value_ptr( static_cast<leaf_node *>( m_pNode ))),
624 reinterpret_cast< cds::urcu::free_retired_ptr_func>( free_leaf_node ));
627 return cds::urcu::retired_ptr( reinterpret_cast<void *>( static_cast<internal_node *>( m_pNode )),
628 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_internal_node ));
631 return cds::urcu::retired_ptr( nullptr,
632 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ));
638 m_pUpdate = m_pUpdate->pNextRetire;
642 m_pNode = m_pNode->m_pNextRetired;
645 friend bool operator ==( forward_iterator const& i1, forward_iterator const& i2 )
647 return i1.m_pUpdate == i2.m_pUpdate && i1.m_pNode == i2.m_pNode;
649 friend bool operator !=( forward_iterator const& i1, forward_iterator const& i2 )
651 return !( i1 == i2 );
657 : pUpdateHead( nullptr )
658 , pNodeHead( nullptr )
663 gc::batch_retire( forward_iterator(*this), forward_iterator());
666 void push( update_desc * p )
668 p->pNextRetire = pUpdateHead;
672 void push( tree_node * p )
674 p->m_pNextRetired = pNodeHead;
679 void retire_node( tree_node * pNode, retired_list& rl ) const
681 if ( pNode->is_leaf()) {
682 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
683 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
686 assert( static_cast<internal_node *>( pNode ) != &m_Root );
687 m_Stat.onInternalNodeDeleted();
692 void retire_update_desc( update_desc * p, retired_list& rl, bool bDirect ) const
694 m_Stat.onUpdateDescDeleted();
696 free_update_desc( p );
701 void make_empty_tree()
703 m_Root.infinite_key( 2 );
704 m_LeafInf1.infinite_key( 1 );
705 m_LeafInf2.infinite_key( 2 );
706 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
707 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
712 /// Default constructor
715 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
727 The function inserts \p val in the tree if it does not contain
728 an item with key equal to \p val.
730 The function applies RCU lock internally.
732 Returns \p true if \p val is placed into the set, \p false otherwise.
734 bool insert( value_type& val )
736 return insert( val, []( value_type& ) {} );
741 This function is intended for derived non-intrusive containers.
743 The function allows to split creating of new item into two part:
744 - create item with key only
745 - insert new item into the tree
746 - if inserting is success, calls \p f functor to initialize value-field of \p val.
748 The functor signature is:
750 void func( value_type& val );
752 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
753 \p val no any other changes could be made on this tree's item by concurrent threads.
754 The user-defined functor is called only if the inserting is success.
756 RCU \p synchronize method can be called. RCU should not be locked.
758 template <typename Func>
759 bool insert( value_type& val, Func f )
761 check_deadlock_policy::check();
763 unique_internal_node_ptr pNewInternal;
764 retired_list updRetire;
772 if ( search( res, val, node_compare())) {
773 if ( pNewInternal.get())
774 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
775 m_Stat.onInsertFailed();
779 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
780 if ( !pNewInternal.get())
781 pNewInternal.reset( alloc_internal_node());
783 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
785 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
790 help( res.updParent, updRetire );
793 m_Stat.onInsertRetry();
798 m_Stat.onInsertSuccess();
805 The operation performs inserting or changing data with lock-free manner.
807 If the item \p val is not found in the set, then \p val is inserted into the set
808 iff \p bAllowInsert is \p true.
809 Otherwise, the functor \p func is called with item found.
810 The functor \p func 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 set
817 - \p val - argument \p val passed into the \p %update() 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 RCU \p synchronize method can be called. RCU should not be locked.
826 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
827 i.e. the node has been inserted or updated,
828 \p second is \p true if new item has been added or \p false if the item with \p key
831 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
833 template <typename Func>
834 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
836 check_deadlock_policy::check();
838 unique_internal_node_ptr pNewInternal;
839 retired_list updRetire;
847 if ( search( res, val, node_compare())) {
848 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
849 if ( pNewInternal.get())
850 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
851 m_Stat.onUpdateExist();
852 return std::make_pair( true, false );
855 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
857 return std::make_pair( false, false );
859 if ( !pNewInternal.get())
860 pNewInternal.reset( alloc_internal_node());
862 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
863 func( true, val, val );
864 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
869 help( res.updParent, updRetire );
872 m_Stat.onUpdateRetry();
877 m_Stat.onUpdateNew();
879 return std::make_pair( true, true );
882 template <typename Func>
883 CDS_DEPRECATED("ensure() is deprecated, use update()")
884 std::pair<bool, bool> ensure( value_type& val, Func func )
886 return update( val, func, true );
890 /// Unlinks the item \p val from the tree
892 The function searches the item \p val in the tree and unlink it from the tree
893 if it is found and is equal to \p val.
895 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
896 and deletes the item found. \p %unlink() finds an item by key and deletes it
897 only if \p val is an item of the tree, i.e. the pointer to item found
898 is equal to <tt> &val </tt>.
900 RCU \p synchronize method can be called. RCU should not be locked.
902 The \ref disposer specified in \p Traits class template parameter is called
903 by garbage collector \p GC asynchronously.
905 The function returns \p true if success and \p false otherwise.
907 bool unlink( value_type& val )
909 return erase_( val, node_compare(),
910 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
911 [](value_type const&) {} );
914 /// Deletes the item from the tree
915 /** \anchor cds_intrusive_EllenBinTree_rcu_erase
916 The function searches an item with key equal to \p key in the tree,
917 unlinks it from the tree, and returns \p true.
918 If the item with key equal to \p key is not found the function return \p false.
920 Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
921 that can be not the same as \p value_type.
923 RCU \p synchronize method can be called. RCU should not be locked.
925 template <typename Q>
926 bool erase( const Q& key )
928 return erase_( key, node_compare(),
929 []( Q const&, leaf_node const& ) -> bool { return true; },
930 [](value_type const&) {} );
933 /// Delete the item from the tree with comparing functor \p pred
935 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
936 but \p pred predicate is used for key comparing.
937 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
938 "Predicate requirements".
939 \p pred must imply the same element order as the comparator used for building the tree.
941 template <typename Q, typename Less>
942 bool erase_with( const Q& key, Less pred )
945 typedef ellen_bintree::details::compare<
948 opt::details::make_comparator_from_less<Less>,
952 return erase_( key, compare_functor(),
953 []( Q const&, leaf_node const& ) -> bool { return true; },
954 [](value_type const&) {} );
957 /// Deletes the item from the tree
958 /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
959 The function searches an item with key equal to \p key in the tree,
960 call \p f functor with item found, unlinks it from the tree, and returns \p true.
961 The \ref disposer specified in \p Traits class template parameter is called
962 by garbage collector \p GC asynchronously.
964 The \p Func interface is
967 void operator()( value_type const& item );
971 If the item with key equal to \p key is not found the function return \p false.
973 Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
974 that can be not the same as \p value_type.
976 RCU \p synchronize method can be called. RCU should not be locked.
978 template <typename Q, typename Func>
979 bool erase( Q const& key, Func f )
981 return erase_( key, node_compare(),
982 []( Q const&, leaf_node const& ) -> bool { return true; },
986 /// Delete the item from the tree with comparing functor \p pred
988 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
989 but \p pred predicate is used for key comparing.
990 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
991 "Predicate requirements".
992 \p pred must imply the same element order as the comparator used for building the tree.
994 template <typename Q, typename Less, typename Func>
995 bool erase_with( Q const& key, Less pred, Func f )
998 typedef ellen_bintree::details::compare<
1001 opt::details::make_comparator_from_less<Less>,
1005 return erase_( key, compare_functor(),
1006 []( Q const&, leaf_node const& ) -> bool { return true; },
1010 /// Extracts an item with minimal key from the tree
1012 The function searches an item with minimal key, unlinks it, and returns
1013 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
1014 If the tree is empty the function returns empty \p exempt_ptr.
1016 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
1017 It means that the function gets leftmost leaf of the tree and tries to unlink it.
1018 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1019 So, the function returns the item with minimum key at the moment of tree traversing.
1021 RCU \p synchronize method can be called. RCU should NOT be locked.
1022 The function does not call the disposer for the item found.
1023 The disposer will be implicitly invoked when the returned object is destroyed or when
1024 its \p release() member function is called.
1026 exempt_ptr extract_min()
1028 return exempt_ptr( extract_min_());
1031 /// Extracts an item with maximal key from the tree
1033 The function searches an item with maximal key, unlinks it, and returns
1034 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
1035 If the tree is empty the function returns empty \p exempt_ptr.
1037 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
1038 It means that the function gets rightmost leaf of the tree and tries to unlink it.
1039 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
1040 So, the function returns the item with maximum key at the moment of tree traversing.
1042 RCU \p synchronize method can be called. RCU should NOT be locked.
1043 The function does not call the disposer for the item found.
1044 The disposer will be implicitly invoked when the returned object is destroyed or when
1045 its \p release() member function is called.
1047 exempt_ptr extract_max()
1049 return exempt_ptr( extract_max_());
1052 /// Extracts an item from the tree
1053 /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1054 The function searches an item with key equal to \p key in the tree,
1055 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
1056 If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr.
1058 RCU \p synchronize method can be called. RCU should NOT be locked.
1059 The function does not call the disposer for the item found.
1060 The disposer will be implicitly invoked when the returned object is destroyed or when
1061 its \p release() member function is called.
1063 template <typename Q>
1064 exempt_ptr extract( Q const& key )
1066 return exempt_ptr( extract_( key, node_compare()));
1069 /// Extracts an item from the set using \p pred for searching
1071 The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
1072 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1073 "predicate requirements".
1074 \p pred must imply the same element order as the comparator used for building the tree.
1076 template <typename Q, typename Less>
1077 exempt_ptr extract_with( Q const& key, Less pred )
1079 return exempt_ptr( extract_with_( key, pred ));
1082 /// Checks whether the set contains \p key
1084 The function searches the item with key equal to \p key
1085 and returns \p true if it is found, and \p false otherwise.
1087 The function applies RCU lock internally.
1089 template <typename Q>
1090 bool contains( Q const& key ) const
1094 if ( search( res, key, node_compare())) {
1095 m_Stat.onFindSuccess();
1099 m_Stat.onFindFailed();
1103 template <typename Q>
1104 CDS_DEPRECATED("deprecated, use contains()")
1105 bool find( Q const& key ) const
1107 return contains( key );
1111 /// Checks whether the set contains \p key using \p pred predicate for searching
1113 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1114 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1115 "Predicate requirements".
1116 \p Less must imply the same element order as the comparator used for building the set.
1117 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1119 template <typename Q, typename Less>
1120 bool contains( Q const& key, Less pred ) const
1123 typedef ellen_bintree::details::compare<
1126 opt::details::make_comparator_from_less<Less>,
1132 if ( search( res, key, compare_functor())) {
1133 m_Stat.onFindSuccess();
1136 m_Stat.onFindFailed();
1140 template <typename Q, typename Less>
1141 CDS_DEPRECATED("deprecated, use contains()")
1142 bool find_with( Q const& key, Less pred ) const
1144 return contains( key, pred );
1148 /// Finds the key \p key
1149 /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1150 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1151 The interface of \p Func functor is:
1154 void operator()( value_type& item, Q& key );
1157 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1159 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1160 that \p item cannot be disposed during functor is executing.
1161 The functor does not serialize simultaneous access to the tree \p item. If such access is
1162 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1164 The function applies RCU lock internally.
1166 The function returns \p true if \p key is found, \p false otherwise.
1168 template <typename Q, typename Func>
1169 bool find( Q& key, Func f ) const
1171 return find_( key, f );
1174 template <typename Q, typename Func>
1175 bool find( Q const& key, Func f ) const
1177 return find_( key, f );
1181 /// Finds the key \p key with comparing functor \p pred
1183 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1184 but \p pred is used for key comparison.
1185 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1186 "Predicate requirements".
1187 \p pred must imply the same element order as the comparator used for building the tree.
1189 template <typename Q, typename Less, typename Func>
1190 bool find_with( Q& key, Less pred, Func f ) const
1192 return find_with_( key, pred, f );
1195 template <typename Q, typename Less, typename Func>
1196 bool find_with( Q const& key, Less pred, Func f ) const
1198 return find_with_( key, pred, f );
1202 /// Finds \p key and return the item found
1203 /** \anchor cds_intrusive_EllenBinTree_rcu_get
1204 The function searches the item with key equal to \p key and returns the pointer to item found.
1205 If \p key is not found it returns \p nullptr.
1207 RCU should be locked before call the function.
1208 Returned pointer is valid while RCU is locked.
1210 template <typename Q>
1211 value_type * get( Q const& key ) const
1213 return get_( key, node_compare());
1216 /// Finds \p key with \p pred predicate and return the item found
1218 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1219 but \p pred is used for comparing the keys.
1221 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1223 \p pred must imply the same element order as the comparator used for building the tree.
1225 template <typename Q, typename Less>
1226 value_type * get_with( Q const& key, Less pred ) const
1229 typedef ellen_bintree::details::compare<
1232 opt::details::make_comparator_from_less<Less>,
1236 return get_( key, compare_functor());
1239 /// Checks if the tree is empty
1242 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1245 /// Clears the tree (thread safe, not atomic)
1247 The function unlink all items from the tree.
1248 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1252 assert( set.empty());
1254 the assertion could be raised.
1256 For each leaf the \ref disposer will be called after unlinking.
1258 RCU \p synchronize method can be called. RCU should not be locked.
1262 for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min())
1266 /// Clears the tree (not thread safe)
1268 This function is not thread safe and may be called only when no other thread deals with the tree.
1269 The function is used in the tree destructor.
1276 internal_node * pParent = nullptr;
1277 internal_node * pGrandParent = nullptr;
1278 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1280 // Get leftmost leaf
1281 while ( pLeaf->is_internal()) {
1282 pGrandParent = pParent;
1283 pParent = static_cast<internal_node *>( pLeaf );
1284 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1287 if ( pLeaf->infinite_key()) {
1288 // The tree is empty
1292 // Remove leftmost leaf and its parent node
1293 assert( pGrandParent );
1295 assert( pLeaf->is_leaf());
1297 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1298 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf )));
1299 free_internal_node( pParent );
1303 /// Returns item count in the tree
1305 Only leaf nodes containing user data are counted.
1307 The value returned depends on item counter type provided by \p Traits template parameter.
1308 If it is \p atomicity::empty_item_counter this function always returns 0.
1310 The function is not suitable for checking the tree emptiness, use \p empty()
1311 member function for that.
1315 return m_ItemCounter;
1318 /// Returns const reference to internal statistics
1319 stat const& statistics() const
1324 /// Checks internal consistency (not atomic, not thread-safe)
1326 The debugging function to check internal consistency of the tree.
1328 bool check_consistency() const
1330 return check_consistency( &m_Root );
1336 bool check_consistency( internal_node const * pRoot ) const
1338 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1339 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1343 if ( node_compare()( *pLeft, *pRoot ) < 0
1344 && node_compare()( *pRoot, *pRight ) <= 0
1345 && node_compare()( *pLeft, *pRight ) < 0 )
1348 if ( pLeft->is_internal())
1349 bRet = check_consistency( static_cast<internal_node *>( pLeft ));
1352 if ( bRet && pRight->is_internal())
1353 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1361 void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
1364 switch ( pUpdate.bits()) {
1365 case update_desc::IFlag:
1366 help_insert( pUpdate.ptr());
1367 m_Stat.onHelpInsert();
1369 case update_desc::DFlag:
1370 //help_delete( pUpdate.ptr(), rl );
1371 //m_Stat.onHelpDelete();
1373 case update_desc::Mark:
1374 //help_marked( pUpdate.ptr());
1375 //m_Stat.onHelpMark();
1381 void help_insert( update_desc * pOp )
1383 assert( gc::is_locked());
1385 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1386 if ( pOp->iInfo.bRightLeaf ) {
1387 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1388 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1391 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1392 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1395 update_ptr cur( pOp, update_desc::IFlag );
1396 pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1397 memory_model::memory_order_release, atomics::memory_order_relaxed );
1400 bool check_delete_precondition( search_result& res )
1402 assert( res.pGrandParent != nullptr );
1405 static_cast<internal_node *>( res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1406 && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1409 bool help_delete( update_desc * pOp, retired_list& rl )
1411 assert( gc::is_locked());
1413 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1414 update_ptr pMark( pOp, update_desc::Mark );
1415 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1416 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1419 retire_node( pOp->dInfo.pParent, rl );
1420 // For extract operations the leaf should NOT be disposed
1421 if ( pOp->dInfo.bDisposeLeaf )
1422 retire_node( pOp->dInfo.pLeaf, rl );
1423 retire_update_desc( pOp, rl, false );
1427 else if ( pUpdate == pMark ) {
1428 // some other thread is processing help_marked()
1430 m_Stat.onHelpMark();
1434 // pUpdate has been changed by CAS
1435 help( pUpdate, rl );
1437 // Undo grandparent dInfo
1438 update_ptr pDel( pOp, update_desc::DFlag );
1439 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1440 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1442 retire_update_desc( pOp, rl, false );
1448 void help_marked( update_desc * pOp )
1450 assert( gc::is_locked());
1452 tree_node * p = pOp->dInfo.pParent;
1453 if ( pOp->dInfo.bRightParent ) {
1454 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1455 pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1456 memory_model::memory_order_release, atomics::memory_order_relaxed );
1459 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1460 pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1461 memory_model::memory_order_release, atomics::memory_order_relaxed );
1464 update_ptr upd( pOp, update_desc::DFlag );
1465 pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1466 memory_model::memory_order_release, atomics::memory_order_relaxed );
1469 template <typename KeyValue, typename Compare>
1470 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1472 assert( gc::is_locked());
1474 internal_node * pParent;
1475 internal_node * pGrandParent = nullptr;
1477 update_ptr updParent;
1478 update_ptr updGrandParent;
1480 bool bRightParent = false;
1486 pLeaf = const_cast<internal_node *>( &m_Root );
1487 updParent = nullptr;
1489 while ( pLeaf->is_internal()) {
1490 pGrandParent = pParent;
1491 pParent = static_cast<internal_node *>( pLeaf );
1492 bRightParent = bRightLeaf;
1493 updGrandParent = updParent;
1494 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1496 switch ( updParent.bits()) {
1497 case update_desc::DFlag:
1498 case update_desc::Mark:
1499 m_Stat.onSearchRetry();
1503 nCmp = cmp( key, *pParent );
1504 bRightLeaf = nCmp >= 0;
1505 pLeaf = pParent->get_child( nCmp >= 0, memory_model::memory_order_acquire );
1508 assert( pLeaf->is_leaf());
1509 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf));
1511 res.pGrandParent = pGrandParent;
1512 res.pParent = pParent;
1513 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1514 res.updParent = updParent;
1515 res.updGrandParent = updGrandParent;
1516 res.bRightParent = bRightParent;
1517 res.bRightLeaf = bRightLeaf;
1522 bool search_min( search_result& res ) const
1524 assert( gc::is_locked());
1526 internal_node * pParent;
1527 internal_node * pGrandParent = nullptr;
1529 update_ptr updParent;
1530 update_ptr updGrandParent;
1534 pLeaf = const_cast<internal_node *>( &m_Root );
1535 while ( pLeaf->is_internal()) {
1536 pGrandParent = pParent;
1537 pParent = static_cast<internal_node *>( pLeaf );
1538 updGrandParent = updParent;
1539 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1541 switch ( updParent.bits()) {
1542 case update_desc::DFlag:
1543 case update_desc::Mark:
1544 m_Stat.onSearchRetry();
1548 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1551 if ( pLeaf->infinite_key())
1554 res.pGrandParent = pGrandParent;
1555 res.pParent = pParent;
1556 assert( pLeaf->is_leaf());
1557 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1558 res.updParent = updParent;
1559 res.updGrandParent = updGrandParent;
1560 res.bRightParent = false;
1561 res.bRightLeaf = false;
1566 bool search_max( search_result& res ) const
1568 assert( gc::is_locked());
1570 internal_node * pParent;
1571 internal_node * pGrandParent = nullptr;
1573 update_ptr updParent;
1574 update_ptr updGrandParent;
1576 bool bRightParent = false;
1580 pLeaf = const_cast<internal_node *>( &m_Root );
1582 while ( pLeaf->is_internal()) {
1583 pGrandParent = pParent;
1584 pParent = static_cast<internal_node *>( pLeaf );
1585 bRightParent = bRightLeaf;
1586 updGrandParent = updParent;
1587 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1589 switch ( updParent.bits()) {
1590 case update_desc::DFlag:
1591 case update_desc::Mark:
1592 m_Stat.onSearchRetry();
1596 bRightLeaf = !pParent->infinite_key();
1597 pLeaf = pParent->get_child( bRightLeaf, memory_model::memory_order_acquire );
1600 if ( pLeaf->infinite_key())
1603 res.pGrandParent = pGrandParent;
1604 res.pParent = pParent;
1605 assert( pLeaf->is_leaf());
1606 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1607 res.updParent = updParent;
1608 res.updGrandParent = updGrandParent;
1609 res.bRightParent = bRightParent;
1610 res.bRightLeaf = bRightLeaf;
1615 template <typename Q, typename Compare, typename Equal, typename Func>
1616 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1618 check_deadlock_policy::check();
1620 retired_list updRetire;
1621 update_desc * pOp = nullptr;
1628 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf )) {
1630 retire_update_desc( pOp, updRetire, false );
1631 m_Stat.onEraseFailed();
1635 if ( res.updGrandParent.bits() != update_desc::Clean )
1636 help( res.updGrandParent, updRetire );
1637 else if ( res.updParent.bits() != update_desc::Clean )
1638 help( res.updParent, updRetire );
1641 pOp = alloc_update_desc();
1642 if ( check_delete_precondition( res )) {
1643 pOp->dInfo.pGrandParent = res.pGrandParent;
1644 pOp->dInfo.pParent = res.pParent;
1645 pOp->dInfo.pLeaf = res.pLeaf;
1646 pOp->dInfo.bDisposeLeaf = true;
1647 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1648 pOp->dInfo.bRightParent = res.bRightParent;
1649 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1651 update_ptr updGP( res.updGrandParent.ptr());
1652 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1653 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1655 if ( help_delete( pOp, updRetire )) {
1656 // res.pLeaf is not deleted yet since RCU is blocked
1657 f( *node_traits::to_value_ptr( res.pLeaf ));
1663 // updGP has been changed by CAS
1664 help( updGP, updRetire );
1670 m_Stat.onEraseRetry();
1675 m_Stat.onEraseSuccess();
1679 template <typename Q, typename Less>
1680 value_type * extract_with_( Q const& val, Less /*pred*/ )
1682 typedef ellen_bintree::details::compare<
1685 opt::details::make_comparator_from_less<Less>,
1689 return extract_( val, compare_functor());
1692 template <typename Q, typename Compare>
1693 value_type * extract_( Q const& val, Compare cmp )
1695 check_deadlock_policy::check();
1697 retired_list updRetire;
1698 update_desc * pOp = nullptr;
1701 value_type * pResult;
1706 if ( !search( res, val, cmp )) {
1708 retire_update_desc( pOp, updRetire, false );
1709 m_Stat.onEraseFailed();
1713 if ( res.updGrandParent.bits() != update_desc::Clean )
1714 help( res.updGrandParent, updRetire );
1715 else if ( res.updParent.bits() != update_desc::Clean )
1716 help( res.updParent, updRetire );
1719 pOp = alloc_update_desc();
1720 if ( check_delete_precondition( res )) {
1721 pOp->dInfo.pGrandParent = res.pGrandParent;
1722 pOp->dInfo.pParent = res.pParent;
1723 pOp->dInfo.pLeaf = res.pLeaf;
1724 pOp->dInfo.bDisposeLeaf = false;
1725 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1726 pOp->dInfo.bRightParent = res.bRightParent;
1727 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1729 update_ptr updGP( res.updGrandParent.ptr());
1730 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1731 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1733 if ( help_delete( pOp, updRetire )) {
1734 pResult = node_traits::to_value_ptr( res.pLeaf );
1740 // updGP has been changed by CAS
1741 help( updGP, updRetire );
1747 m_Stat.onEraseRetry();
1752 m_Stat.onEraseSuccess();
1757 value_type * extract_max_()
1759 check_deadlock_policy::check();
1761 retired_list updRetire;
1762 update_desc * pOp = nullptr;
1765 value_type * pResult;
1770 if ( !search_max( res )) {
1773 retire_update_desc( pOp, updRetire, false );
1774 m_Stat.onExtractMaxFailed();
1778 if ( res.updGrandParent.bits() != update_desc::Clean )
1779 help( res.updGrandParent, updRetire );
1780 else if ( res.updParent.bits() != update_desc::Clean )
1781 help( res.updParent, updRetire );
1784 pOp = alloc_update_desc();
1785 if ( check_delete_precondition( res )) {
1786 pOp->dInfo.pGrandParent = res.pGrandParent;
1787 pOp->dInfo.pParent = res.pParent;
1788 pOp->dInfo.pLeaf = res.pLeaf;
1789 pOp->dInfo.bDisposeLeaf = false;
1790 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1791 pOp->dInfo.bRightParent = res.bRightParent;
1792 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1794 update_ptr updGP( res.updGrandParent.ptr());
1795 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1796 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1798 if ( help_delete( pOp, updRetire )) {
1799 pResult = node_traits::to_value_ptr( res.pLeaf );
1805 // updGP has been changed by CAS
1806 help( updGP, updRetire );
1812 m_Stat.onExtractMaxRetry();
1817 m_Stat.onExtractMaxSuccess();
1821 value_type * extract_min_()
1823 check_deadlock_policy::check();
1825 retired_list updRetire;
1826 update_desc * pOp = nullptr;
1829 value_type * pResult;
1834 if ( !search_min( res )) {
1837 retire_update_desc( pOp, updRetire, false );
1838 m_Stat.onExtractMinFailed();
1842 if ( res.updGrandParent.bits() != update_desc::Clean )
1843 help( res.updGrandParent, updRetire );
1844 else if ( res.updParent.bits() != update_desc::Clean )
1845 help( res.updParent, updRetire );
1848 pOp = alloc_update_desc();
1849 if ( check_delete_precondition( res )) {
1850 pOp->dInfo.pGrandParent = res.pGrandParent;
1851 pOp->dInfo.pParent = res.pParent;
1852 pOp->dInfo.pLeaf = res.pLeaf;
1853 pOp->dInfo.bDisposeLeaf = false;
1854 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1855 pOp->dInfo.bRightParent = res.bRightParent;
1856 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1858 update_ptr updGP( res.updGrandParent.ptr());
1859 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1860 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1862 if ( help_delete( pOp, updRetire )) {
1863 pResult = node_traits::to_value_ptr( res.pLeaf );
1869 // updGP has been changed by CAS
1870 help( updGP, updRetire );
1876 m_Stat.onExtractMinRetry();
1881 m_Stat.onExtractMinSuccess();
1885 template <typename Q, typename Less, typename Func>
1886 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1888 typedef ellen_bintree::details::compare<
1891 opt::details::make_comparator_from_less<Less>,
1897 if ( search( res, val, compare_functor())) {
1898 assert( res.pLeaf );
1899 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1901 m_Stat.onFindSuccess();
1905 m_Stat.onFindFailed();
1909 template <typename Q, typename Func>
1910 bool find_( Q& key, Func f ) const
1914 if ( search( res, key, node_compare())) {
1915 assert( res.pLeaf );
1916 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1918 m_Stat.onFindSuccess();
1922 m_Stat.onFindFailed();
1926 template <typename Q, typename Compare>
1927 value_type * get_( Q const& key, Compare cmp ) const
1929 assert( gc::is_locked());
1932 if ( search( res, key, cmp )) {
1933 m_Stat.onFindSuccess();
1934 return node_traits::to_value_ptr( res.pLeaf );
1937 m_Stat.onFindFailed();
1942 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1944 assert( gc::is_locked());
1945 assert( res.updParent.bits() == update_desc::Clean );
1947 // check search result
1948 if ( static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf ) {
1949 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1951 int nCmp = node_compare()( val, *res.pLeaf );
1953 if ( res.pGrandParent ) {
1954 pNewInternal->infinite_key( 0 );
1955 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1956 assert( !res.pLeaf->infinite_key());
1959 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1960 pNewInternal->infinite_key( 1 );
1962 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1963 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1966 assert( !res.pLeaf->is_internal());
1967 pNewInternal->infinite_key( 0 );
1969 key_extractor()( pNewInternal->m_Key, val );
1970 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1971 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1972 assert( !res.pLeaf->infinite_key());
1975 update_desc * pOp = alloc_update_desc();
1977 pOp->iInfo.pParent = res.pParent;
1978 pOp->iInfo.pNew = pNewInternal;
1979 pOp->iInfo.pLeaf = res.pLeaf;
1980 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1982 update_ptr updCur( res.updParent.ptr());
1983 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1984 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1988 retire_update_desc( pOp, updRetire, false );
1992 // updCur has been updated by CAS
1993 help( updCur, updRetire );
1994 retire_update_desc( pOp, updRetire, true );
2003 }} // namespace cds::intrusive
2005 #endif // #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H