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 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 successfull,
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.onEnsureExist();
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.onEnsureRetry();
877 m_Stat.onEnsureNew();
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 hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
922 RCU \p synchronize method can be called. RCU should not be locked.
924 template <typename Q>
925 bool erase( const Q& key )
927 return erase_( key, node_compare(),
928 []( Q const&, leaf_node const& ) -> bool { return true; },
929 [](value_type const&) {} );
932 /// Delete the item from the tree with comparing functor \p pred
934 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
935 but \p pred predicate is used for key comparing.
936 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
937 "Predicate requirements".
938 \p pred must imply the same element order as the comparator used for building the tree.
940 template <typename Q, typename Less>
941 bool erase_with( const Q& key, Less pred )
944 typedef ellen_bintree::details::compare<
947 opt::details::make_comparator_from_less<Less>,
951 return erase_( key, compare_functor(),
952 []( Q const&, leaf_node const& ) -> bool { return true; },
953 [](value_type const&) {} );
956 /// Deletes the item from the tree
957 /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
958 The function searches an item with key equal to \p key in the tree,
959 call \p f functor with item found, unlinks it from the tree, and returns \p true.
960 The \ref disposer specified in \p Traits class template parameter is called
961 by garbage collector \p GC asynchronously.
963 The \p Func interface is
966 void operator()( value_type const& item );
970 If the item with key equal to \p key is not found the function return \p false.
972 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
974 RCU \p synchronize method can be called. RCU should not be locked.
976 template <typename Q, typename Func>
977 bool erase( Q const& key, Func f )
979 return erase_( key, node_compare(),
980 []( Q const&, leaf_node const& ) -> bool { return true; },
984 /// Delete the item from the tree with comparing functor \p pred
986 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
987 but \p pred predicate is used for key comparing.
988 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
989 "Predicate requirements".
990 \p pred must imply the same element order as the comparator used for building the tree.
992 template <typename Q, typename Less, typename Func>
993 bool erase_with( Q const& key, Less pred, Func f )
996 typedef ellen_bintree::details::compare<
999 opt::details::make_comparator_from_less<Less>,
1003 return erase_( key, compare_functor(),
1004 []( Q const&, leaf_node const& ) -> bool { return true; },
1008 /// Extracts an item with minimal key from the tree
1010 The function searches an item with minimal key, unlinks it, and returns
1011 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
1012 If the tree is empty the function returns empty \p exempt_ptr.
1014 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
1015 It means that the function gets leftmost leaf of the tree and tries to unlink it.
1016 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1017 So, the function returns the item with minimum key at the moment of tree traversing.
1019 RCU \p synchronize method can be called. RCU should NOT be locked.
1020 The function does not call the disposer for the item found.
1021 The disposer will be implicitly invoked when the returned object is destroyed or when
1022 its \p release() member function is called.
1024 exempt_ptr extract_min()
1026 return exempt_ptr( extract_min_());
1029 /// Extracts an item with maximal key from the tree
1031 The function searches an item with maximal key, unlinks it, and returns
1032 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
1033 If the tree is empty the function returns empty \p exempt_ptr.
1035 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
1036 It means that the function gets rightmost leaf of the tree and tries to unlink it.
1037 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
1038 So, the function returns the item with maximum key at the moment of tree traversing.
1040 RCU \p synchronize method can be called. RCU should NOT be locked.
1041 The function does not call the disposer for the item found.
1042 The disposer will be implicitly invoked when the returned object is destroyed or when
1043 its \p release() member function is called.
1045 exempt_ptr extract_max()
1047 return exempt_ptr( extract_max_());
1050 /// Extracts an item from the tree
1051 /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1052 The function searches an item with key equal to \p key in the tree,
1053 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
1054 If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr.
1056 RCU \p synchronize method can be called. RCU should NOT be locked.
1057 The function does not call the disposer for the item found.
1058 The disposer will be implicitly invoked when the returned object is destroyed or when
1059 its \p release() member function is called.
1061 template <typename Q>
1062 exempt_ptr extract( Q const& key )
1064 return exempt_ptr( extract_( key, node_compare()));
1067 /// Extracts an item from the set using \p pred for searching
1069 The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
1070 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1071 "predicate requirements".
1072 \p pred must imply the same element order as the comparator used for building the tree.
1074 template <typename Q, typename Less>
1075 exempt_ptr extract_with( Q const& key, Less pred )
1077 return exempt_ptr( extract_with_( key, pred ));
1080 /// Checks whether the set contains \p key
1082 The function searches the item with key equal to \p key
1083 and returns \p true if it is found, and \p false otherwise.
1085 The function applies RCU lock internally.
1087 template <typename Q>
1088 bool contains( Q const& key ) const
1092 if ( search( res, key, node_compare())) {
1093 m_Stat.onFindSuccess();
1097 m_Stat.onFindFailed();
1101 template <typename Q>
1102 CDS_DEPRECATED("deprecated, use contains()")
1103 bool find( Q const& key ) const
1105 return contains( key );
1109 /// Checks whether the set contains \p key using \p pred predicate for searching
1111 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1112 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1113 "Predicate requirements".
1114 \p Less must imply the same element order as the comparator used for building the set.
1115 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1117 template <typename Q, typename Less>
1118 bool contains( Q const& key, Less pred ) const
1121 typedef ellen_bintree::details::compare<
1124 opt::details::make_comparator_from_less<Less>,
1130 if ( search( res, key, compare_functor())) {
1131 m_Stat.onFindSuccess();
1134 m_Stat.onFindFailed();
1138 template <typename Q, typename Less>
1139 CDS_DEPRECATED("deprecated, use contains()")
1140 bool find_with( Q const& key, Less pred ) const
1142 return contains( key, pred );
1146 /// Finds the key \p key
1147 /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1148 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1149 The interface of \p Func functor is:
1152 void operator()( value_type& item, Q& key );
1155 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1157 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1158 that \p item cannot be disposed during functor is executing.
1159 The functor does not serialize simultaneous access to the tree \p item. If such access is
1160 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1162 The function applies RCU lock internally.
1164 The function returns \p true if \p key is found, \p false otherwise.
1166 template <typename Q, typename Func>
1167 bool find( Q& key, Func f ) const
1169 return find_( key, f );
1172 template <typename Q, typename Func>
1173 bool find( Q const& key, Func f ) const
1175 return find_( key, f );
1179 /// Finds the key \p key with comparing functor \p pred
1181 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1182 but \p pred is used for key comparison.
1183 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1184 "Predicate requirements".
1185 \p pred must imply the same element order as the comparator used for building the tree.
1187 template <typename Q, typename Less, typename Func>
1188 bool find_with( Q& key, Less pred, Func f ) const
1190 return find_with_( key, pred, f );
1193 template <typename Q, typename Less, typename Func>
1194 bool find_with( Q const& key, Less pred, Func f ) const
1196 return find_with_( key, pred, f );
1200 /// Finds \p key and return the item found
1201 /** \anchor cds_intrusive_EllenBinTree_rcu_get
1202 The function searches the item with key equal to \p key and returns the pointer to item found.
1203 If \p key is not found it returns \p nullptr.
1205 RCU should be locked before call the function.
1206 Returned pointer is valid while RCU is locked.
1208 template <typename Q>
1209 value_type * get( Q const& key ) const
1211 return get_( key, node_compare());
1214 /// Finds \p key with \p pred predicate and return the item found
1216 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1217 but \p pred is used for comparing the keys.
1219 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1221 \p pred must imply the same element order as the comparator used for building the tree.
1223 template <typename Q, typename Less>
1224 value_type * get_with( Q const& key, Less pred ) const
1227 typedef ellen_bintree::details::compare<
1230 opt::details::make_comparator_from_less<Less>,
1234 return get_( key, compare_functor());
1237 /// Checks if the tree is empty
1240 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1243 /// Clears the tree (thread safe, not atomic)
1245 The function unlink all items from the tree.
1246 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1250 assert( set.empty());
1252 the assertion could be raised.
1254 For each leaf the \ref disposer will be called after unlinking.
1256 RCU \p synchronize method can be called. RCU should not be locked.
1260 for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min())
1264 /// Clears the tree (not thread safe)
1266 This function is not thread safe and may be called only when no other thread deals with the tree.
1267 The function is used in the tree destructor.
1274 internal_node * pParent = nullptr;
1275 internal_node * pGrandParent = nullptr;
1276 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1278 // Get leftmost leaf
1279 while ( pLeaf->is_internal()) {
1280 pGrandParent = pParent;
1281 pParent = static_cast<internal_node *>( pLeaf );
1282 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1285 if ( pLeaf->infinite_key()) {
1286 // The tree is empty
1290 // Remove leftmost leaf and its parent node
1291 assert( pGrandParent );
1293 assert( pLeaf->is_leaf());
1295 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1296 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf )));
1297 free_internal_node( pParent );
1301 /// Returns item count in the tree
1303 Only leaf nodes containing user data are counted.
1305 The value returned depends on item counter type provided by \p Traits template parameter.
1306 If it is \p atomicity::empty_item_counter this function always returns 0.
1308 The function is not suitable for checking the tree emptiness, use \p empty()
1309 member function for that.
1313 return m_ItemCounter;
1316 /// Returns const reference to internal statistics
1317 stat const& statistics() const
1322 /// Checks internal consistency (not atomic, not thread-safe)
1324 The debugging function to check internal consistency of the tree.
1326 bool check_consistency() const
1328 return check_consistency( &m_Root );
1334 bool check_consistency( internal_node const * pRoot ) const
1336 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1337 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1341 if ( node_compare()( *pLeft, *pRoot ) < 0
1342 && node_compare()( *pRoot, *pRight ) <= 0
1343 && node_compare()( *pLeft, *pRight ) < 0 )
1346 if ( pLeft->is_internal())
1347 bRet = check_consistency( static_cast<internal_node *>( pLeft ));
1350 if ( bRet && pRight->is_internal())
1351 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1359 void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
1362 switch ( pUpdate.bits()) {
1363 case update_desc::IFlag:
1364 help_insert( pUpdate.ptr());
1365 m_Stat.onHelpInsert();
1367 case update_desc::DFlag:
1368 //help_delete( pUpdate.ptr(), rl );
1369 //m_Stat.onHelpDelete();
1371 case update_desc::Mark:
1372 //help_marked( pUpdate.ptr());
1373 //m_Stat.onHelpMark();
1379 void help_insert( update_desc * pOp )
1381 assert( gc::is_locked());
1383 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1384 if ( pOp->iInfo.bRightLeaf ) {
1385 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1386 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1389 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1390 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1393 update_ptr cur( pOp, update_desc::IFlag );
1394 pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1395 memory_model::memory_order_release, atomics::memory_order_relaxed );
1398 bool check_delete_precondition( search_result& res )
1400 assert( res.pGrandParent != nullptr );
1403 static_cast<internal_node *>( res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1404 && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1407 bool help_delete( update_desc * pOp, retired_list& rl )
1409 assert( gc::is_locked());
1411 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1412 update_ptr pMark( pOp, update_desc::Mark );
1413 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1414 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1417 retire_node( pOp->dInfo.pParent, rl );
1418 // For extract operations the leaf should NOT be disposed
1419 if ( pOp->dInfo.bDisposeLeaf )
1420 retire_node( pOp->dInfo.pLeaf, rl );
1421 retire_update_desc( pOp, rl, false );
1425 else if ( pUpdate == pMark ) {
1426 // some other thread is processing help_marked()
1428 m_Stat.onHelpMark();
1432 // pUpdate has been changed by CAS
1433 help( pUpdate, rl );
1435 // Undo grandparent dInfo
1436 update_ptr pDel( pOp, update_desc::DFlag );
1437 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1438 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1440 retire_update_desc( pOp, rl, false );
1446 void help_marked( update_desc * pOp )
1448 assert( gc::is_locked());
1450 tree_node * p = pOp->dInfo.pParent;
1451 if ( pOp->dInfo.bRightParent ) {
1452 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1453 pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1454 memory_model::memory_order_release, atomics::memory_order_relaxed );
1457 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1458 pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1459 memory_model::memory_order_release, atomics::memory_order_relaxed );
1462 update_ptr upd( pOp, update_desc::DFlag );
1463 pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1464 memory_model::memory_order_release, atomics::memory_order_relaxed );
1467 template <typename KeyValue, typename Compare>
1468 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1470 assert( gc::is_locked());
1472 internal_node * pParent;
1473 internal_node * pGrandParent = nullptr;
1475 update_ptr updParent;
1476 update_ptr updGrandParent;
1478 bool bRightParent = false;
1484 pLeaf = const_cast<internal_node *>( &m_Root );
1485 updParent = nullptr;
1487 while ( pLeaf->is_internal()) {
1488 pGrandParent = pParent;
1489 pParent = static_cast<internal_node *>( pLeaf );
1490 bRightParent = bRightLeaf;
1491 updGrandParent = updParent;
1492 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1494 switch ( updParent.bits()) {
1495 case update_desc::DFlag:
1496 case update_desc::Mark:
1497 m_Stat.onSearchRetry();
1501 nCmp = cmp( key, *pParent );
1502 bRightLeaf = nCmp >= 0;
1503 pLeaf = pParent->get_child( nCmp >= 0, memory_model::memory_order_acquire );
1506 assert( pLeaf->is_leaf());
1507 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf));
1509 res.pGrandParent = pGrandParent;
1510 res.pParent = pParent;
1511 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1512 res.updParent = updParent;
1513 res.updGrandParent = updGrandParent;
1514 res.bRightParent = bRightParent;
1515 res.bRightLeaf = bRightLeaf;
1520 bool search_min( search_result& res ) const
1522 assert( gc::is_locked());
1524 internal_node * pParent;
1525 internal_node * pGrandParent = nullptr;
1527 update_ptr updParent;
1528 update_ptr updGrandParent;
1532 pLeaf = const_cast<internal_node *>( &m_Root );
1533 while ( pLeaf->is_internal()) {
1534 pGrandParent = pParent;
1535 pParent = static_cast<internal_node *>( pLeaf );
1536 updGrandParent = updParent;
1537 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1539 switch ( updParent.bits()) {
1540 case update_desc::DFlag:
1541 case update_desc::Mark:
1542 m_Stat.onSearchRetry();
1546 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1549 if ( pLeaf->infinite_key())
1552 res.pGrandParent = pGrandParent;
1553 res.pParent = pParent;
1554 assert( pLeaf->is_leaf());
1555 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1556 res.updParent = updParent;
1557 res.updGrandParent = updGrandParent;
1558 res.bRightParent = false;
1559 res.bRightLeaf = false;
1564 bool search_max( search_result& res ) const
1566 assert( gc::is_locked());
1568 internal_node * pParent;
1569 internal_node * pGrandParent = nullptr;
1571 update_ptr updParent;
1572 update_ptr updGrandParent;
1574 bool bRightParent = false;
1578 pLeaf = const_cast<internal_node *>( &m_Root );
1580 while ( pLeaf->is_internal()) {
1581 pGrandParent = pParent;
1582 pParent = static_cast<internal_node *>( pLeaf );
1583 bRightParent = bRightLeaf;
1584 updGrandParent = updParent;
1585 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1587 switch ( updParent.bits()) {
1588 case update_desc::DFlag:
1589 case update_desc::Mark:
1590 m_Stat.onSearchRetry();
1594 bRightLeaf = !pParent->infinite_key();
1595 pLeaf = pParent->get_child( bRightLeaf, memory_model::memory_order_acquire );
1598 if ( pLeaf->infinite_key())
1601 res.pGrandParent = pGrandParent;
1602 res.pParent = pParent;
1603 assert( pLeaf->is_leaf());
1604 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1605 res.updParent = updParent;
1606 res.updGrandParent = updGrandParent;
1607 res.bRightParent = bRightParent;
1608 res.bRightLeaf = bRightLeaf;
1613 template <typename Q, typename Compare, typename Equal, typename Func>
1614 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1616 check_deadlock_policy::check();
1618 retired_list updRetire;
1619 update_desc * pOp = nullptr;
1626 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf )) {
1628 retire_update_desc( pOp, updRetire, false );
1629 m_Stat.onEraseFailed();
1633 if ( res.updGrandParent.bits() != update_desc::Clean )
1634 help( res.updGrandParent, updRetire );
1635 else if ( res.updParent.bits() != update_desc::Clean )
1636 help( res.updParent, updRetire );
1639 pOp = alloc_update_desc();
1640 if ( check_delete_precondition( res )) {
1641 pOp->dInfo.pGrandParent = res.pGrandParent;
1642 pOp->dInfo.pParent = res.pParent;
1643 pOp->dInfo.pLeaf = res.pLeaf;
1644 pOp->dInfo.bDisposeLeaf = true;
1645 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1646 pOp->dInfo.bRightParent = res.bRightParent;
1647 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1649 update_ptr updGP( res.updGrandParent.ptr());
1650 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1651 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1653 if ( help_delete( pOp, updRetire )) {
1654 // res.pLeaf is not deleted yet since RCU is blocked
1655 f( *node_traits::to_value_ptr( res.pLeaf ));
1661 // updGP has been changed by CAS
1662 help( updGP, updRetire );
1668 m_Stat.onEraseRetry();
1673 m_Stat.onEraseSuccess();
1677 template <typename Q, typename Less>
1678 value_type * extract_with_( Q const& val, Less /*pred*/ )
1680 typedef ellen_bintree::details::compare<
1683 opt::details::make_comparator_from_less<Less>,
1687 return extract_( val, compare_functor());
1690 template <typename Q, typename Compare>
1691 value_type * extract_( Q const& val, Compare cmp )
1693 check_deadlock_policy::check();
1695 retired_list updRetire;
1696 update_desc * pOp = nullptr;
1699 value_type * pResult;
1704 if ( !search( res, val, cmp )) {
1706 retire_update_desc( pOp, updRetire, false );
1707 m_Stat.onEraseFailed();
1711 if ( res.updGrandParent.bits() != update_desc::Clean )
1712 help( res.updGrandParent, updRetire );
1713 else if ( res.updParent.bits() != update_desc::Clean )
1714 help( res.updParent, updRetire );
1717 pOp = alloc_update_desc();
1718 if ( check_delete_precondition( res )) {
1719 pOp->dInfo.pGrandParent = res.pGrandParent;
1720 pOp->dInfo.pParent = res.pParent;
1721 pOp->dInfo.pLeaf = res.pLeaf;
1722 pOp->dInfo.bDisposeLeaf = false;
1723 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1724 pOp->dInfo.bRightParent = res.bRightParent;
1725 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1727 update_ptr updGP( res.updGrandParent.ptr());
1728 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1729 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1731 if ( help_delete( pOp, updRetire )) {
1732 pResult = node_traits::to_value_ptr( res.pLeaf );
1738 // updGP has been changed by CAS
1739 help( updGP, updRetire );
1745 m_Stat.onEraseRetry();
1750 m_Stat.onEraseSuccess();
1755 value_type * extract_max_()
1757 check_deadlock_policy::check();
1759 retired_list updRetire;
1760 update_desc * pOp = nullptr;
1763 value_type * pResult;
1768 if ( !search_max( res )) {
1771 retire_update_desc( pOp, updRetire, false );
1772 m_Stat.onExtractMaxFailed();
1776 if ( res.updGrandParent.bits() != update_desc::Clean )
1777 help( res.updGrandParent, updRetire );
1778 else if ( res.updParent.bits() != update_desc::Clean )
1779 help( res.updParent, updRetire );
1782 pOp = alloc_update_desc();
1783 if ( check_delete_precondition( res )) {
1784 pOp->dInfo.pGrandParent = res.pGrandParent;
1785 pOp->dInfo.pParent = res.pParent;
1786 pOp->dInfo.pLeaf = res.pLeaf;
1787 pOp->dInfo.bDisposeLeaf = false;
1788 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1789 pOp->dInfo.bRightParent = res.bRightParent;
1790 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1792 update_ptr updGP( res.updGrandParent.ptr());
1793 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1794 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1796 if ( help_delete( pOp, updRetire )) {
1797 pResult = node_traits::to_value_ptr( res.pLeaf );
1803 // updGP has been changed by CAS
1804 help( updGP, updRetire );
1810 m_Stat.onExtractMaxRetry();
1815 m_Stat.onExtractMaxSuccess();
1819 value_type * extract_min_()
1821 check_deadlock_policy::check();
1823 retired_list updRetire;
1824 update_desc * pOp = nullptr;
1827 value_type * pResult;
1832 if ( !search_min( res )) {
1835 retire_update_desc( pOp, updRetire, false );
1836 m_Stat.onExtractMinFailed();
1840 if ( res.updGrandParent.bits() != update_desc::Clean )
1841 help( res.updGrandParent, updRetire );
1842 else if ( res.updParent.bits() != update_desc::Clean )
1843 help( res.updParent, updRetire );
1846 pOp = alloc_update_desc();
1847 if ( check_delete_precondition( res )) {
1848 pOp->dInfo.pGrandParent = res.pGrandParent;
1849 pOp->dInfo.pParent = res.pParent;
1850 pOp->dInfo.pLeaf = res.pLeaf;
1851 pOp->dInfo.bDisposeLeaf = false;
1852 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1853 pOp->dInfo.bRightParent = res.bRightParent;
1854 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1856 update_ptr updGP( res.updGrandParent.ptr());
1857 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1858 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1860 if ( help_delete( pOp, updRetire )) {
1861 pResult = node_traits::to_value_ptr( res.pLeaf );
1867 // updGP has been changed by CAS
1868 help( updGP, updRetire );
1874 m_Stat.onExtractMinRetry();
1879 m_Stat.onExtractMinSuccess();
1883 template <typename Q, typename Less, typename Func>
1884 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1886 typedef ellen_bintree::details::compare<
1889 opt::details::make_comparator_from_less<Less>,
1895 if ( search( res, val, compare_functor())) {
1896 assert( res.pLeaf );
1897 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1899 m_Stat.onFindSuccess();
1903 m_Stat.onFindFailed();
1907 template <typename Q, typename Func>
1908 bool find_( Q& key, Func f ) const
1912 if ( search( res, key, node_compare())) {
1913 assert( res.pLeaf );
1914 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1916 m_Stat.onFindSuccess();
1920 m_Stat.onFindFailed();
1924 template <typename Q, typename Compare>
1925 value_type * get_( Q const& key, Compare cmp ) const
1927 assert( gc::is_locked());
1930 if ( search( res, key, cmp )) {
1931 m_Stat.onFindSuccess();
1932 return node_traits::to_value_ptr( res.pLeaf );
1935 m_Stat.onFindFailed();
1940 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1942 assert( gc::is_locked());
1943 assert( res.updParent.bits() == update_desc::Clean );
1945 // check search result
1946 if ( static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf ) {
1947 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1949 int nCmp = node_compare()( val, *res.pLeaf );
1951 if ( res.pGrandParent ) {
1952 pNewInternal->infinite_key( 0 );
1953 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1954 assert( !res.pLeaf->infinite_key());
1957 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1958 pNewInternal->infinite_key( 1 );
1960 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1961 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1964 assert( !res.pLeaf->is_internal());
1965 pNewInternal->infinite_key( 0 );
1967 key_extractor()( pNewInternal->m_Key, val );
1968 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1969 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1970 assert( !res.pLeaf->infinite_key());
1973 update_desc * pOp = alloc_update_desc();
1975 pOp->iInfo.pParent = res.pParent;
1976 pOp->iInfo.pNew = pNewInternal;
1977 pOp->iInfo.pLeaf = res.pLeaf;
1978 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1980 update_ptr updCur( res.updParent.ptr());
1981 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1982 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1986 retire_update_desc( pOp, updRetire, false );
1990 // updCur has been updated by CAS
1991 help( updCur, updRetire );
1992 retire_update_desc( pOp, updRetire, true );
2001 }} // namespace cds::intrusive
2003 #endif // #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H