2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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 )
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 )
559 static void free_leaf_node_void( void* p )
561 free_leaf_node( reinterpret_cast<value_type*>( p ));
564 internal_node * alloc_internal_node() const
566 m_Stat.onInternalNodeCreated();
567 internal_node * pNode = cxx_node_allocator().New();
572 static void free_internal_node( internal_node* pNode )
574 cxx_node_allocator().Delete( pNode );
576 static void free_internal_node_void( void* pNode )
578 free_internal_node( reinterpret_cast<internal_node*>( pNode ));
581 struct internal_node_deleter {
582 void operator()( internal_node * p) const
584 free_internal_node( p );
588 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
590 update_desc * alloc_update_desc() const
592 m_Stat.onUpdateDescCreated();
593 return cxx_update_desc_allocator().New();
596 static void free_update_desc( update_desc* pDesc )
598 cxx_update_desc_allocator().Delete( pDesc );
600 static void free_update_desc_void( void* pDesc )
602 free_update_desc( reinterpret_cast<update_desc*>( pDesc ));
607 update_desc * pUpdateHead;
608 tree_node * pNodeHead;
611 class forward_iterator
613 update_desc * m_pUpdate;
617 forward_iterator( retired_list const& l )
618 : m_pUpdate( l.pUpdateHead )
619 , m_pNode( l.pNodeHead )
623 : m_pUpdate( nullptr )
627 cds::urcu::retired_ptr operator *()
630 return cds::urcu::retired_ptr( reinterpret_cast<void *>( m_pUpdate ), free_update_desc_void );
633 if ( m_pNode->is_leaf()) {
634 return cds::urcu::retired_ptr( reinterpret_cast<void *>( node_traits::to_value_ptr( static_cast<leaf_node *>( m_pNode ))),
635 free_leaf_node_void );
638 return cds::urcu::retired_ptr( reinterpret_cast<void *>( static_cast<internal_node *>( m_pNode )),
639 free_internal_node_void );
642 return cds::urcu::retired_ptr( nullptr, free_update_desc_void );
648 m_pUpdate = m_pUpdate->pNextRetire;
652 m_pNode = m_pNode->m_pNextRetired;
655 friend bool operator ==( forward_iterator const& i1, forward_iterator const& i2 )
657 return i1.m_pUpdate == i2.m_pUpdate && i1.m_pNode == i2.m_pNode;
659 friend bool operator !=( forward_iterator const& i1, forward_iterator const& i2 )
661 return !( i1 == i2 );
667 : pUpdateHead( nullptr )
668 , pNodeHead( nullptr )
673 gc::batch_retire( forward_iterator(*this), forward_iterator());
676 void push( update_desc * p )
678 p->pNextRetire = pUpdateHead;
682 void push( tree_node * p )
684 p->m_pNextRetired = pNodeHead;
689 void retire_node( tree_node * pNode, retired_list& rl ) const
691 if ( pNode->is_leaf()) {
692 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
693 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
696 assert( static_cast<internal_node *>( pNode ) != &m_Root );
697 m_Stat.onInternalNodeDeleted();
702 void retire_update_desc( update_desc * p, retired_list& rl, bool bDirect ) const
704 m_Stat.onUpdateDescDeleted();
706 free_update_desc( p );
711 void make_empty_tree()
713 m_Root.infinite_key( 2 );
714 m_LeafInf1.infinite_key( 1 );
715 m_LeafInf2.infinite_key( 2 );
716 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
717 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
722 /// Default constructor
725 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
737 The function inserts \p val in the tree if it does not contain
738 an item with key equal to \p val.
740 The function applies RCU lock internally.
742 Returns \p true if \p val is placed into the set, \p false otherwise.
744 bool insert( value_type& val )
746 return insert( val, []( value_type& ) {} );
751 This function is intended for derived non-intrusive containers.
753 The function allows to split creating of new item into two part:
754 - create item with key only
755 - insert new item into the tree
756 - if inserting is success, calls \p f functor to initialize value-field of \p val.
758 The functor signature is:
760 void func( value_type& val );
762 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
763 \p val no any other changes could be made on this tree's item by concurrent threads.
764 The user-defined functor is called only if the inserting is success.
766 RCU \p synchronize method can be called. RCU should not be locked.
768 template <typename Func>
769 bool insert( value_type& val, Func f )
771 check_deadlock_policy::check();
773 unique_internal_node_ptr pNewInternal;
774 retired_list updRetire;
782 if ( search( res, val, node_compare())) {
783 if ( pNewInternal.get())
784 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
785 m_Stat.onInsertFailed();
789 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
790 if ( !pNewInternal.get())
791 pNewInternal.reset( alloc_internal_node());
793 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
795 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
800 help( res.updParent, updRetire );
803 m_Stat.onInsertRetry();
808 m_Stat.onInsertSuccess();
815 The operation performs inserting or changing data with lock-free manner.
817 If the item \p val is not found in the set, then \p val is inserted into the set
818 iff \p bAllowInsert is \p true.
819 Otherwise, the functor \p func is called with item found.
820 The functor \p func signature is:
822 void func( bool bNew, value_type& item, value_type& val );
825 - \p bNew - \p true if the item has been inserted, \p false otherwise
826 - \p item - item of the set
827 - \p val - argument \p val passed into the \p %update() function
828 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
829 refer to the same thing.
831 The functor can change non-key fields of the \p item; however, \p func must guarantee
832 that during changing no any other modifications could be made on this item by concurrent threads.
834 RCU \p synchronize method can be called. RCU should not be locked.
836 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
837 i.e. the node has been inserted or updated,
838 \p second is \p true if new item has been added or \p false if the item with \p key
841 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
843 template <typename Func>
844 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
846 check_deadlock_policy::check();
848 unique_internal_node_ptr pNewInternal;
849 retired_list updRetire;
857 if ( search( res, val, node_compare())) {
858 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
859 if ( pNewInternal.get())
860 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
861 m_Stat.onUpdateExist();
862 return std::make_pair( true, false );
865 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
867 return std::make_pair( false, false );
869 if ( !pNewInternal.get())
870 pNewInternal.reset( alloc_internal_node());
872 if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
873 func( true, val, val );
874 pNewInternal.release() ; // internal node is linked into the tree and should not be deleted
879 help( res.updParent, updRetire );
882 m_Stat.onUpdateRetry();
887 m_Stat.onUpdateNew();
889 return std::make_pair( true, true );
892 template <typename Func>
893 CDS_DEPRECATED("ensure() is deprecated, use update()")
894 std::pair<bool, bool> ensure( value_type& val, Func func )
896 return update( val, func, true );
900 /// Unlinks the item \p val from the tree
902 The function searches the item \p val in the tree and unlink it from the tree
903 if it is found and is equal to \p val.
905 Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
906 and deletes the item found. \p %unlink() finds an item by key and deletes it
907 only if \p val is an item of the tree, i.e. the pointer to item found
908 is equal to <tt> &val </tt>.
910 RCU \p synchronize method can be called. RCU should not be locked.
912 The \ref disposer specified in \p Traits class template parameter is called
913 by garbage collector \p GC asynchronously.
915 The function returns \p true if success and \p false otherwise.
917 bool unlink( value_type& val )
919 return erase_( val, node_compare(),
920 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
921 [](value_type const&) {} );
924 /// Deletes the item from the tree
925 /** \anchor cds_intrusive_EllenBinTree_rcu_erase
926 The function searches an item with key equal to \p key in the tree,
927 unlinks it from the tree, and returns \p true.
928 If the item with key equal to \p key is not found the function return \p false.
930 Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
931 that can be not the same as \p value_type.
933 RCU \p synchronize method can be called. RCU should not be locked.
935 template <typename Q>
936 bool erase( const Q& key )
938 return erase_( key, node_compare(),
939 []( Q const&, leaf_node const& ) -> bool { return true; },
940 [](value_type const&) {} );
943 /// Delete the item from the tree with comparing functor \p pred
945 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
946 but \p pred predicate is used for key comparing.
947 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
948 "Predicate requirements".
949 \p pred must imply the same element order as the comparator used for building the tree.
951 template <typename Q, typename Less>
952 bool erase_with( const Q& key, Less pred )
955 typedef ellen_bintree::details::compare<
958 opt::details::make_comparator_from_less<Less>,
962 return erase_( key, compare_functor(),
963 []( Q const&, leaf_node const& ) -> bool { return true; },
964 [](value_type const&) {} );
967 /// Deletes the item from the tree
968 /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
969 The function searches an item with key equal to \p key in the tree,
970 call \p f functor with item found, unlinks it from the tree, and returns \p true.
971 The \ref disposer specified in \p Traits class template parameter is called
972 by garbage collector \p GC asynchronously.
974 The \p Func interface is
977 void operator()( value_type const& item );
981 If the item with key equal to \p key is not found the function return \p false.
983 Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
984 that can be not the same as \p value_type.
986 RCU \p synchronize method can be called. RCU should not be locked.
988 template <typename Q, typename Func>
989 bool erase( Q const& key, Func f )
991 return erase_( key, node_compare(),
992 []( Q const&, leaf_node const& ) -> bool { return true; },
996 /// Delete the item from the tree with comparing functor \p pred
998 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
999 but \p pred predicate is used for key comparing.
1000 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1001 "Predicate requirements".
1002 \p pred must imply the same element order as the comparator used for building the tree.
1004 template <typename Q, typename Less, typename Func>
1005 bool erase_with( Q const& key, Less pred, Func f )
1008 typedef ellen_bintree::details::compare<
1011 opt::details::make_comparator_from_less<Less>,
1015 return erase_( key, compare_functor(),
1016 []( Q const&, leaf_node const& ) -> bool { return true; },
1020 /// Extracts an item with minimal key from the tree
1022 The function searches an item with minimal key, unlinks it, and returns
1023 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
1024 If the tree is empty the function returns empty \p exempt_ptr.
1026 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
1027 It means that the function gets leftmost leaf of the tree and tries to unlink it.
1028 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1029 So, the function returns the item with minimum key at the moment of tree traversing.
1031 RCU \p synchronize method can be called. RCU should NOT be locked.
1032 The function does not call the disposer for the item found.
1033 The disposer will be implicitly invoked when the returned object is destroyed or when
1034 its \p release() member function is called.
1036 exempt_ptr extract_min()
1038 return exempt_ptr( extract_min_());
1041 /// Extracts an item with maximal key from the tree
1043 The function searches an item with maximal key, unlinks it, and returns
1044 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
1045 If the tree is empty the function returns empty \p exempt_ptr.
1047 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
1048 It means that the function gets rightmost leaf of the tree and tries to unlink it.
1049 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
1050 So, the function returns the item with maximum key at the moment of tree traversing.
1052 RCU \p synchronize method can be called. RCU should NOT be locked.
1053 The function does not call the disposer for the item found.
1054 The disposer will be implicitly invoked when the returned object is destroyed or when
1055 its \p release() member function is called.
1057 exempt_ptr extract_max()
1059 return exempt_ptr( extract_max_());
1062 /// Extracts an item from the tree
1063 /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1064 The function searches an item with key equal to \p key in the tree,
1065 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
1066 If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr.
1068 RCU \p synchronize method can be called. RCU should NOT be locked.
1069 The function does not call the disposer for the item found.
1070 The disposer will be implicitly invoked when the returned object is destroyed or when
1071 its \p release() member function is called.
1073 template <typename Q>
1074 exempt_ptr extract( Q const& key )
1076 return exempt_ptr( extract_( key, node_compare()));
1079 /// Extracts an item from the set using \p pred for searching
1081 The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
1082 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1083 "predicate requirements".
1084 \p pred must imply the same element order as the comparator used for building the tree.
1086 template <typename Q, typename Less>
1087 exempt_ptr extract_with( Q const& key, Less pred )
1089 return exempt_ptr( extract_with_( key, pred ));
1092 /// Checks whether the set contains \p key
1094 The function searches the item with key equal to \p key
1095 and returns \p true if it is found, and \p false otherwise.
1097 The function applies RCU lock internally.
1099 template <typename Q>
1100 bool contains( Q const& key ) const
1104 if ( search( res, key, node_compare())) {
1105 m_Stat.onFindSuccess();
1109 m_Stat.onFindFailed();
1113 template <typename Q>
1114 CDS_DEPRECATED("deprecated, use contains()")
1115 bool find( Q const& key ) const
1117 return contains( key );
1121 /// Checks whether the set contains \p key using \p pred predicate for searching
1123 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1124 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1125 "Predicate requirements".
1126 \p Less must imply the same element order as the comparator used for building the set.
1127 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1129 template <typename Q, typename Less>
1130 bool contains( Q const& key, Less pred ) const
1133 typedef ellen_bintree::details::compare<
1136 opt::details::make_comparator_from_less<Less>,
1142 if ( search( res, key, compare_functor())) {
1143 m_Stat.onFindSuccess();
1146 m_Stat.onFindFailed();
1150 template <typename Q, typename Less>
1151 CDS_DEPRECATED("deprecated, use contains()")
1152 bool find_with( Q const& key, Less pred ) const
1154 return contains( key, pred );
1158 /// Finds the key \p key
1159 /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1160 The function searches the item with key equal to \p key and calls the functor \p f for item found.
1161 The interface of \p Func functor is:
1164 void operator()( value_type& item, Q& key );
1167 where \p item is the item found, \p key is the <tt>find</tt> function argument.
1169 The functor can change non-key fields of \p item. Note that the functor is only guarantee
1170 that \p item cannot be disposed during functor is executing.
1171 The functor does not serialize simultaneous access to the tree \p item. If such access is
1172 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1174 The function applies RCU lock internally.
1176 The function returns \p true if \p key is found, \p false otherwise.
1178 template <typename Q, typename Func>
1179 bool find( Q& key, Func f ) const
1181 return find_( key, f );
1184 template <typename Q, typename Func>
1185 bool find( Q const& key, Func f ) const
1187 return find_( key, f );
1191 /// Finds the key \p key with comparing functor \p pred
1193 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1194 but \p pred is used for key comparison.
1195 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1196 "Predicate requirements".
1197 \p pred must imply the same element order as the comparator used for building the tree.
1199 template <typename Q, typename Less, typename Func>
1200 bool find_with( Q& key, Less pred, Func f ) const
1202 return find_with_( key, pred, f );
1205 template <typename Q, typename Less, typename Func>
1206 bool find_with( Q const& key, Less pred, Func f ) const
1208 return find_with_( key, pred, f );
1212 /// Finds \p key and return the item found
1213 /** \anchor cds_intrusive_EllenBinTree_rcu_get
1214 The function searches the item with key equal to \p key and returns the pointer to item found.
1215 If \p key is not found it returns \p nullptr.
1217 RCU should be locked before call the function.
1218 Returned pointer is valid while RCU is locked.
1220 template <typename Q>
1221 value_type * get( Q const& key ) const
1223 return get_( key, node_compare());
1226 /// Finds \p key with \p pred predicate and return the item found
1228 The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1229 but \p pred is used for comparing the keys.
1231 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1233 \p pred must imply the same element order as the comparator used for building the tree.
1235 template <typename Q, typename Less>
1236 value_type * get_with( Q const& key, Less pred ) const
1239 typedef ellen_bintree::details::compare<
1242 opt::details::make_comparator_from_less<Less>,
1246 return get_( key, compare_functor());
1249 /// Checks if the tree is empty
1252 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1255 /// Clears the tree (thread safe, not atomic)
1257 The function unlink all items from the tree.
1258 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1262 assert( set.empty());
1264 the assertion could be raised.
1266 For each leaf the \ref disposer will be called after unlinking.
1268 RCU \p synchronize method can be called. RCU should not be locked.
1272 for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min())
1276 /// Clears the tree (not thread safe)
1278 This function is not thread safe and may be called only when no other thread deals with the tree.
1279 The function is used in the tree destructor.
1286 internal_node * pParent = nullptr;
1287 internal_node * pGrandParent = nullptr;
1288 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1290 // Get leftmost leaf
1291 while ( pLeaf->is_internal()) {
1292 pGrandParent = pParent;
1293 pParent = static_cast<internal_node *>( pLeaf );
1294 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1297 if ( pLeaf->infinite_key()) {
1298 // The tree is empty
1302 // Remove leftmost leaf and its parent node
1303 assert( pGrandParent );
1305 assert( pLeaf->is_leaf());
1307 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1308 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf )));
1309 free_internal_node( pParent );
1313 /// Returns item count in the tree
1315 Only leaf nodes containing user data are counted.
1317 The value returned depends on item counter type provided by \p Traits template parameter.
1318 If it is \p atomicity::empty_item_counter this function always returns 0.
1320 The function is not suitable for checking the tree emptiness, use \p empty()
1321 member function for that.
1325 return m_ItemCounter;
1328 /// Returns const reference to internal statistics
1329 stat const& statistics() const
1334 /// Checks internal consistency (not atomic, not thread-safe)
1336 The debugging function to check internal consistency of the tree.
1338 bool check_consistency() const
1340 return check_consistency( &m_Root );
1346 bool check_consistency( internal_node const * pRoot ) const
1348 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1349 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1353 if ( node_compare()( *pLeft, *pRoot ) < 0
1354 && node_compare()( *pRoot, *pRight ) <= 0
1355 && node_compare()( *pLeft, *pRight ) < 0 )
1358 if ( pLeft->is_internal())
1359 bRet = check_consistency( static_cast<internal_node *>( pLeft ));
1362 if ( bRet && pRight->is_internal())
1363 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1371 void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
1374 switch ( pUpdate.bits()) {
1375 case update_desc::IFlag:
1376 help_insert( pUpdate.ptr());
1377 m_Stat.onHelpInsert();
1379 case update_desc::DFlag:
1380 //help_delete( pUpdate.ptr(), rl );
1381 //m_Stat.onHelpDelete();
1383 case update_desc::Mark:
1384 //help_marked( pUpdate.ptr());
1385 //m_Stat.onHelpMark();
1391 void help_insert( update_desc * pOp )
1393 assert( gc::is_locked());
1395 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1396 if ( pOp->iInfo.bRightLeaf ) {
1397 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1398 memory_model::memory_order_release, atomics::memory_order_relaxed );
1401 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1402 memory_model::memory_order_release, atomics::memory_order_relaxed );
1405 update_ptr cur( pOp, update_desc::IFlag );
1406 pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1407 memory_model::memory_order_release, atomics::memory_order_relaxed );
1410 bool check_delete_precondition( search_result& res )
1412 assert( res.pGrandParent != nullptr );
1415 static_cast<internal_node *>( res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1416 && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1419 bool help_delete( update_desc * pOp, retired_list& rl )
1421 assert( gc::is_locked());
1423 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1424 update_ptr pMark( pOp, update_desc::Mark );
1425 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1426 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1429 retire_node( pOp->dInfo.pParent, rl );
1430 // For extract operations the leaf should NOT be disposed
1431 if ( pOp->dInfo.bDisposeLeaf )
1432 retire_node( pOp->dInfo.pLeaf, rl );
1433 retire_update_desc( pOp, rl, false );
1437 else if ( pUpdate == pMark ) {
1438 // some other thread is processing help_marked()
1440 m_Stat.onHelpMark();
1444 // pUpdate has been changed by CAS
1445 help( pUpdate, rl );
1447 // Undo grandparent dInfo
1448 update_ptr pDel( pOp, update_desc::DFlag );
1449 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1450 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1452 retire_update_desc( pOp, rl, false );
1458 void help_marked( update_desc * pOp )
1460 assert( gc::is_locked());
1462 tree_node * p = pOp->dInfo.pParent;
1463 if ( pOp->dInfo.bRightParent ) {
1464 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1465 pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1466 memory_model::memory_order_release, atomics::memory_order_relaxed );
1469 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1470 pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1471 memory_model::memory_order_release, atomics::memory_order_relaxed );
1474 update_ptr upd( pOp, update_desc::DFlag );
1475 pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1476 memory_model::memory_order_release, atomics::memory_order_relaxed );
1479 template <typename KeyValue, typename Compare>
1480 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1482 assert( gc::is_locked());
1484 internal_node * pParent;
1485 internal_node * pGrandParent = nullptr;
1487 update_ptr updParent;
1488 update_ptr updGrandParent;
1490 bool bRightParent = false;
1496 pLeaf = const_cast<internal_node *>( &m_Root );
1497 updParent = nullptr;
1499 while ( pLeaf->is_internal()) {
1500 pGrandParent = pParent;
1501 pParent = static_cast<internal_node *>( pLeaf );
1502 bRightParent = bRightLeaf;
1503 updGrandParent = updParent;
1504 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1506 switch ( updParent.bits()) {
1507 case update_desc::DFlag:
1508 case update_desc::Mark:
1509 m_Stat.onSearchRetry();
1513 nCmp = cmp( key, *pParent );
1514 bRightLeaf = nCmp >= 0;
1515 pLeaf = pParent->get_child( nCmp >= 0, memory_model::memory_order_acquire );
1518 assert( pLeaf->is_leaf());
1519 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf));
1521 res.pGrandParent = pGrandParent;
1522 res.pParent = pParent;
1523 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1524 res.updParent = updParent;
1525 res.updGrandParent = updGrandParent;
1526 res.bRightParent = bRightParent;
1527 res.bRightLeaf = bRightLeaf;
1532 bool search_min( search_result& res ) const
1534 assert( gc::is_locked());
1536 internal_node * pParent;
1537 internal_node * pGrandParent = nullptr;
1539 update_ptr updParent;
1540 update_ptr updGrandParent;
1544 pLeaf = const_cast<internal_node *>( &m_Root );
1545 while ( pLeaf->is_internal()) {
1546 pGrandParent = pParent;
1547 pParent = static_cast<internal_node *>( pLeaf );
1548 updGrandParent = updParent;
1549 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1551 switch ( updParent.bits()) {
1552 case update_desc::DFlag:
1553 case update_desc::Mark:
1554 m_Stat.onSearchRetry();
1558 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1561 if ( pLeaf->infinite_key())
1564 res.pGrandParent = pGrandParent;
1565 res.pParent = pParent;
1566 assert( pLeaf->is_leaf());
1567 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1568 res.updParent = updParent;
1569 res.updGrandParent = updGrandParent;
1570 res.bRightParent = false;
1571 res.bRightLeaf = false;
1576 bool search_max( search_result& res ) const
1578 assert( gc::is_locked());
1580 internal_node * pParent;
1581 internal_node * pGrandParent = nullptr;
1583 update_ptr updParent;
1584 update_ptr updGrandParent;
1586 bool bRightParent = false;
1590 pLeaf = const_cast<internal_node *>( &m_Root );
1592 while ( pLeaf->is_internal()) {
1593 pGrandParent = pParent;
1594 pParent = static_cast<internal_node *>( pLeaf );
1595 bRightParent = bRightLeaf;
1596 updGrandParent = updParent;
1597 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1599 switch ( updParent.bits()) {
1600 case update_desc::DFlag:
1601 case update_desc::Mark:
1602 m_Stat.onSearchRetry();
1606 bRightLeaf = !pParent->infinite_key();
1607 pLeaf = pParent->get_child( bRightLeaf, memory_model::memory_order_acquire );
1610 if ( pLeaf->infinite_key())
1613 res.pGrandParent = pGrandParent;
1614 res.pParent = pParent;
1615 assert( pLeaf->is_leaf());
1616 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1617 res.updParent = updParent;
1618 res.updGrandParent = updGrandParent;
1619 res.bRightParent = bRightParent;
1620 res.bRightLeaf = bRightLeaf;
1625 template <typename Q, typename Compare, typename Equal, typename Func>
1626 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1628 check_deadlock_policy::check();
1630 retired_list updRetire;
1631 update_desc * pOp = nullptr;
1638 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf )) {
1640 retire_update_desc( pOp, updRetire, false );
1641 m_Stat.onEraseFailed();
1645 if ( res.updGrandParent.bits() != update_desc::Clean )
1646 help( res.updGrandParent, updRetire );
1647 else if ( res.updParent.bits() != update_desc::Clean )
1648 help( res.updParent, updRetire );
1651 pOp = alloc_update_desc();
1652 if ( check_delete_precondition( res )) {
1653 pOp->dInfo.pGrandParent = res.pGrandParent;
1654 pOp->dInfo.pParent = res.pParent;
1655 pOp->dInfo.pLeaf = res.pLeaf;
1656 pOp->dInfo.bDisposeLeaf = true;
1657 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1658 pOp->dInfo.bRightParent = res.bRightParent;
1659 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1661 update_ptr updGP( res.updGrandParent.ptr());
1662 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1663 memory_model::memory_order_acq_rel, atomics::memory_order_acquire ))
1665 if ( help_delete( pOp, updRetire )) {
1666 // res.pLeaf is not deleted yet since RCU is blocked
1667 f( *node_traits::to_value_ptr( res.pLeaf ));
1673 // updGP has been changed by CAS
1674 help( updGP, updRetire );
1680 m_Stat.onEraseRetry();
1685 m_Stat.onEraseSuccess();
1689 template <typename Q, typename Less>
1690 value_type * extract_with_( Q const& val, Less /*pred*/ )
1692 typedef ellen_bintree::details::compare<
1695 opt::details::make_comparator_from_less<Less>,
1699 return extract_( val, compare_functor());
1702 template <typename Q, typename Compare>
1703 value_type * extract_( Q const& val, Compare cmp )
1705 check_deadlock_policy::check();
1707 retired_list updRetire;
1708 update_desc * pOp = nullptr;
1711 value_type * pResult;
1716 if ( !search( res, val, cmp )) {
1718 retire_update_desc( pOp, updRetire, false );
1719 m_Stat.onEraseFailed();
1723 if ( res.updGrandParent.bits() != update_desc::Clean )
1724 help( res.updGrandParent, updRetire );
1725 else if ( res.updParent.bits() != update_desc::Clean )
1726 help( res.updParent, updRetire );
1729 pOp = alloc_update_desc();
1730 if ( check_delete_precondition( res )) {
1731 pOp->dInfo.pGrandParent = res.pGrandParent;
1732 pOp->dInfo.pParent = res.pParent;
1733 pOp->dInfo.pLeaf = res.pLeaf;
1734 pOp->dInfo.bDisposeLeaf = false;
1735 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1736 pOp->dInfo.bRightParent = res.bRightParent;
1737 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1739 update_ptr updGP( res.updGrandParent.ptr());
1740 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1741 memory_model::memory_order_acq_rel, atomics::memory_order_acquire ))
1743 if ( help_delete( pOp, updRetire )) {
1744 pResult = node_traits::to_value_ptr( res.pLeaf );
1750 // updGP has been changed by CAS
1751 help( updGP, updRetire );
1757 m_Stat.onEraseRetry();
1762 m_Stat.onEraseSuccess();
1767 value_type * extract_max_()
1769 check_deadlock_policy::check();
1771 retired_list updRetire;
1772 update_desc * pOp = nullptr;
1775 value_type * pResult;
1780 if ( !search_max( res )) {
1783 retire_update_desc( pOp, updRetire, false );
1784 m_Stat.onExtractMaxFailed();
1788 if ( res.updGrandParent.bits() != update_desc::Clean )
1789 help( res.updGrandParent, updRetire );
1790 else if ( res.updParent.bits() != update_desc::Clean )
1791 help( res.updParent, updRetire );
1794 pOp = alloc_update_desc();
1795 if ( check_delete_precondition( res )) {
1796 pOp->dInfo.pGrandParent = res.pGrandParent;
1797 pOp->dInfo.pParent = res.pParent;
1798 pOp->dInfo.pLeaf = res.pLeaf;
1799 pOp->dInfo.bDisposeLeaf = false;
1800 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1801 pOp->dInfo.bRightParent = res.bRightParent;
1802 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1804 update_ptr updGP( res.updGrandParent.ptr());
1805 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1806 memory_model::memory_order_acq_rel, atomics::memory_order_acquire ))
1808 if ( help_delete( pOp, updRetire )) {
1809 pResult = node_traits::to_value_ptr( res.pLeaf );
1815 // updGP has been changed by CAS
1816 help( updGP, updRetire );
1822 m_Stat.onExtractMaxRetry();
1827 m_Stat.onExtractMaxSuccess();
1831 value_type * extract_min_()
1833 check_deadlock_policy::check();
1835 retired_list updRetire;
1836 update_desc * pOp = nullptr;
1839 value_type * pResult;
1844 if ( !search_min( res )) {
1847 retire_update_desc( pOp, updRetire, false );
1848 m_Stat.onExtractMinFailed();
1852 if ( res.updGrandParent.bits() != update_desc::Clean )
1853 help( res.updGrandParent, updRetire );
1854 else if ( res.updParent.bits() != update_desc::Clean )
1855 help( res.updParent, updRetire );
1858 pOp = alloc_update_desc();
1859 if ( check_delete_precondition( res )) {
1860 pOp->dInfo.pGrandParent = res.pGrandParent;
1861 pOp->dInfo.pParent = res.pParent;
1862 pOp->dInfo.pLeaf = res.pLeaf;
1863 pOp->dInfo.bDisposeLeaf = false;
1864 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1865 pOp->dInfo.bRightParent = res.bRightParent;
1866 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1868 update_ptr updGP( res.updGrandParent.ptr());
1869 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1870 memory_model::memory_order_acq_rel, atomics::memory_order_acquire ))
1872 if ( help_delete( pOp, updRetire )) {
1873 pResult = node_traits::to_value_ptr( res.pLeaf );
1879 // updGP has been changed by CAS
1880 help( updGP, updRetire );
1886 m_Stat.onExtractMinRetry();
1891 m_Stat.onExtractMinSuccess();
1895 template <typename Q, typename Less, typename Func>
1896 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1898 typedef ellen_bintree::details::compare<
1901 opt::details::make_comparator_from_less<Less>,
1907 if ( search( res, val, compare_functor())) {
1908 assert( res.pLeaf );
1909 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1911 m_Stat.onFindSuccess();
1915 m_Stat.onFindFailed();
1919 template <typename Q, typename Func>
1920 bool find_( Q& key, Func f ) const
1924 if ( search( res, key, node_compare())) {
1925 assert( res.pLeaf );
1926 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1928 m_Stat.onFindSuccess();
1932 m_Stat.onFindFailed();
1936 template <typename Q, typename Compare>
1937 value_type * get_( Q const& key, Compare cmp ) const
1939 assert( gc::is_locked());
1942 if ( search( res, key, cmp )) {
1943 m_Stat.onFindSuccess();
1944 return node_traits::to_value_ptr( res.pLeaf );
1947 m_Stat.onFindFailed();
1952 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1954 assert( gc::is_locked());
1955 assert( res.updParent.bits() == update_desc::Clean );
1957 // check search result
1958 if ( static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf ) {
1959 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1961 int nCmp = node_compare()( val, *res.pLeaf );
1963 if ( res.pGrandParent ) {
1964 pNewInternal->infinite_key( 0 );
1965 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1966 assert( !res.pLeaf->infinite_key());
1969 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1970 pNewInternal->infinite_key( 1 );
1972 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1973 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1976 assert( !res.pLeaf->is_internal());
1977 pNewInternal->infinite_key( 0 );
1979 key_extractor()( pNewInternal->m_Key, val );
1980 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1981 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1982 assert( !res.pLeaf->infinite_key());
1985 update_desc * pOp = alloc_update_desc();
1987 pOp->iInfo.pParent = res.pParent;
1988 pOp->iInfo.pNew = pNewInternal;
1989 pOp->iInfo.pLeaf = res.pLeaf;
1990 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1992 update_ptr updCur( res.updParent.ptr());
1993 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1994 memory_model::memory_order_acq_rel, atomics::memory_order_acquire ))
1998 retire_update_desc( pOp, updRetire, false );
2002 // updCur has been updated by CAS
2003 help( updCur, updRetire );
2004 retire_update_desc( pOp, updRetire, true );
2013 }} // namespace cds::intrusive
2015 #endif // #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H