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_IMPL_ELLEN_BINTREE_H
32 #define CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_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>
40 namespace cds { namespace intrusive {
42 /// Ellen's et al binary search tree
43 /** @ingroup cds_intrusive_map
44 @ingroup cds_intrusive_tree
45 @anchor cds_intrusive_EllenBinTree
48 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
50 %EllenBinTree is an <i>unbalanced</i> leaf-oriented binary search tree that implements the <i>set</i>
51 abstract data type. Nodes maintains child pointers but not parent pointers.
52 Every internal node has exactly two children, and all data of type \p T currently in
53 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find()
54 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
55 may or may not be in the set. \p Key type is a subset of \p T type.
56 There should be exactly defined a key extracting functor for converting object of type \p T to
57 object of type \p Key.
59 Due to \p extract_min() and \p extract_max() member functions the \p %EllenBinTree can act as
60 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
61 the priority value plus some uniformly distributed random value.
63 @note In the current implementation we do not use helping technique described in the original paper.
64 In Hazard Pointer schema the helping is too complicated and does not give any observable benefits.
65 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
66 the operation done. Such solution allows greatly simplify implementation of the tree.
68 @attention Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
69 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
71 @note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
72 There are header file for each GC type:
73 - <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC \p cds::gc::HP
74 - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Dynamic Hazard Pointer GC \p cds::gc::DHP
75 - <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
77 <b>Template arguments</b> :
78 - \p GC - garbage collector, possible types are cds::gc::HP, cds::gc::DHP.
79 - \p Key - key type, a subset of \p T
80 - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
81 (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
82 (for \p ellen_bintree::member_hook).
83 - \p Traits - tree traits, default is \p ellen_bintree::traits
84 It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
85 instead of \p Traits template argument.
87 @anchor cds_intrusive_EllenBinTree_less
88 <b>Predicate requirements</b>
90 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
91 of type \p T and \p Key in any combination.
92 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
94 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
101 bool operator()( Foo const& v1, Foo const& v2 ) const
102 { return v1.m_strKey < v2.m_strKey ; }
104 bool operator()( Foo const& v, std::string const& s ) const
105 { return v.m_strKey < s ; }
107 bool operator()( std::string const& s, Foo const& v ) const
108 { return s < v.m_strKey ; }
110 // Support comparing std::string and char const *
111 bool operator()( std::string const& s, char const * p ) const
112 { return s.compare(p) < 0 ; }
114 bool operator()( Foo const& v, char const * p ) const
115 { return v.m_strKey.compare(p) < 0 ; }
117 bool operator()( char const * p, std::string const& s ) const
118 { return s.compare(p) > 0; }
120 bool operator()( char const * p, Foo const& v ) const
121 { return v.m_strKey.compare(p) > 0; }
125 Usage examples see \ref cds_intrusive_EllenBinTree_usage "here"
130 #ifdef CDS_DOXYGEN_INVOKED
131 class Traits = ellen_bintree::traits
139 typedef GC gc; ///< Garbage collector
140 typedef Key key_type; ///< type of a key to be stored in internal nodes; key is a part of \p value_type
141 typedef T value_type; ///< type of value stored in the binary tree
142 typedef Traits traits; ///< Traits template parameter
144 typedef typename traits::hook hook; ///< hook type
145 typedef typename hook::node_type node_type; ///< node type
146 typedef typename traits::disposer disposer; ///< leaf node disposer
147 typedef typename traits::back_off back_off; ///< back-off strategy
149 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
153 typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
154 typedef node_type leaf_node; ///< Leaf node type
155 typedef ellen_bintree::node_types< gc, key_type, typename leaf_node::tag > node_factory;
156 typedef typename node_factory::internal_node_type internal_node; ///< Internal node type
157 typedef typename node_factory::update_desc_type update_desc; ///< Update descriptor
158 typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
162 # ifdef CDS_DOXYGEN_INVOKED
163 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
164 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
166 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
167 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
169 static internal_node const& to_internal_node( tree_node const& n )
171 assert( n.is_internal() );
172 return static_cast<internal_node const&>( n );
175 static leaf_node const& to_leaf_node( tree_node const& n )
177 assert( n.is_leaf() );
178 return static_cast<leaf_node const&>( n );
183 typedef typename traits::item_counter item_counter; ///< Item counting policy
184 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model
185 typedef typename traits::stat stat; ///< internal statistics type
186 typedef typename traits::key_extractor key_extractor; ///< key extracting functor
188 typedef typename traits::node_allocator node_allocator; ///< Allocator for internal node
189 typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
191 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 9; ///< Count of hazard pointer required for the algorithm
195 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
197 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
198 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
200 struct search_result {
205 Guard_updGrandParent,
209 // end of guard indices
213 typedef typename gc::template GuardArray< guard_count > guard_array;
216 internal_node * pGrandParent;
217 internal_node * pParent;
219 update_ptr updParent;
220 update_ptr updGrandParent;
221 bool bRightLeaf; // true if pLeaf is right child of pParent, false otherwise
222 bool bRightParent; // true if pParent is right child of pGrandParent, false otherwise
225 :pGrandParent( nullptr )
229 ,bRightParent( false )
236 internal_node m_Root; ///< Tree root node (key= Infinite2)
237 leaf_node m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
238 leaf_node m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
241 item_counter m_ItemCounter; ///< item counter
242 mutable stat m_Stat; ///< internal statistics
246 static void free_leaf_node( value_type * p )
251 internal_node * alloc_internal_node() const
253 m_Stat.onInternalNodeCreated();
254 internal_node * pNode = cxx_node_allocator().New();
258 static void free_internal_node( internal_node * pNode )
260 cxx_node_allocator().Delete( pNode );
263 struct internal_node_deleter {
264 void operator()( internal_node * p) const
266 free_internal_node( p );
270 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
272 update_desc * alloc_update_desc() const
274 m_Stat.onUpdateDescCreated();
275 return cxx_update_desc_allocator().New();
278 static void free_update_desc( update_desc * pDesc )
280 cxx_update_desc_allocator().Delete( pDesc );
283 void retire_node( tree_node * pNode ) const
285 if ( pNode->is_leaf() ) {
286 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
287 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
289 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
292 assert( static_cast<internal_node *>( pNode ) != &m_Root );
293 m_Stat.onInternalNodeDeleted();
295 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
299 void retire_update_desc( update_desc * p ) const
301 m_Stat.onUpdateDescDeleted();
302 gc::template retire( p, free_update_desc );
305 void make_empty_tree()
307 m_Root.infinite_key( 2 );
308 m_LeafInf1.infinite_key( 1 );
309 m_LeafInf2.infinite_key( 2 );
310 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
311 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
316 /// Default constructor
319 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
331 The function inserts \p val in the tree if it does not contain
332 an item with key equal to \p val.
334 Returns \p true if \p val is placed into the tree, \p false otherwise.
336 bool insert( value_type& val )
338 return insert( val, []( value_type& ) {} );
343 This function is intended for derived non-intrusive containers.
345 The function allows to split creating of new item into two part:
346 - create item with key only
347 - insert new item into the tree
348 - if inserting is success, calls \p f functor to initialize value-field of \p val.
350 The functor signature is:
352 void func( value_type& val );
354 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
355 \p val no any other changes could be made on this tree's item by concurrent threads.
356 The user-defined functor is called only if the inserting is success.
358 template <typename Func>
359 bool insert( value_type& val, Func f )
361 typename gc::Guard guardInsert;
362 guardInsert.assign( &val );
364 unique_internal_node_ptr pNewInternal;
369 if ( search( res, val, node_compare() )) {
370 if ( pNewInternal.get() )
371 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
372 m_Stat.onInsertFailed();
376 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
378 if ( !pNewInternal.get() )
379 pNewInternal.reset( alloc_internal_node() );
381 if ( try_insert( val, pNewInternal.get(), res )) {
383 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
389 m_Stat.onInsertRetry();
393 m_Stat.onInsertSuccess();
399 The operation performs inserting or changing data with lock-free manner.
401 If the item \p val is not found in the set, then \p val is inserted into the set
402 iff \p bAllowInsert is \p true.
403 Otherwise, the functor \p func is called with item found.
404 The functor \p func signature is:
406 void func( bool bNew, value_type& item, value_type& val );
409 - \p bNew - \p true if the item has been inserted, \p false otherwise
410 - \p item - item of the set
411 - \p val - argument \p val passed into the \p %update() function
412 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
413 refer to the same thing.
415 The functor can change non-key fields of the \p item; however, \p func must guarantee
416 that during changing no any other modifications could be made on this item by concurrent threads.
418 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
419 i.e. the node has been inserted or updated,
420 \p second is \p true if new item has been added or \p false if the item with \p key
423 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
425 template <typename Func>
426 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
428 typename gc::Guard guardInsert;
429 guardInsert.assign( &val );
431 unique_internal_node_ptr pNewInternal;
436 if ( search( res, val, node_compare() )) {
437 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
438 if ( pNewInternal.get() )
439 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
440 m_Stat.onEnsureExist();
441 return std::make_pair( true, false );
444 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
446 return std::make_pair( false, false );
448 if ( !pNewInternal.get() )
449 pNewInternal.reset( alloc_internal_node() );
451 if ( try_insert( val, pNewInternal.get(), res )) {
452 func( true, val, val );
453 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
459 m_Stat.onEnsureRetry();
463 m_Stat.onEnsureNew();
464 return std::make_pair( true, true );
467 template <typename Func>
468 CDS_DEPRECATED("ensure() is deprecated, use update()")
469 std::pair<bool, bool> ensure( value_type& val, Func func )
471 return update( val, func, true );
475 /// Unlinks the item \p val from the tree
477 The function searches the item \p val in the tree and unlink it from the tree
478 if it is found and is equal to \p val.
480 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
481 and deletes the item found. \p unlink finds an item by key and deletes it
482 only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
484 The \p disposer specified in \p Traits class template parameter is called
485 by garbage collector \p GC asynchronously.
487 The function returns \p true if success and \p false otherwise.
489 bool unlink( value_type& val )
491 return erase_( val, node_compare(),
492 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
493 [](value_type const&) {} );
496 /// Deletes the item from the tree
497 /** \anchor cds_intrusive_EllenBinTree_erase
498 The function searches an item with key equal to \p key in the tree,
499 unlinks it from the tree, and returns \p true.
500 If the item with key equal to \p key is not found the function return \p false.
502 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
504 template <typename Q>
505 bool erase( const Q& key )
507 return erase_( key, node_compare(),
508 []( Q const&, leaf_node const& ) -> bool { return true; },
509 [](value_type const&) {} );
512 /// Delete the item from the tree with comparing functor \p pred
514 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
515 but \p pred predicate is used for key comparing.
516 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
517 "Predicate requirements".
518 \p pred must imply the same element order as the comparator used for building the tree.
520 template <typename Q, typename Less>
521 bool erase_with( const Q& key, Less pred )
524 typedef ellen_bintree::details::compare<
527 opt::details::make_comparator_from_less<Less>,
531 return erase_( key, compare_functor(),
532 []( Q const&, leaf_node const& ) -> bool { return true; },
533 [](value_type const&) {} );
536 /// Deletes the item from the tree
537 /** \anchor cds_intrusive_EllenBinTree_erase_func
538 The function searches an item with key equal to \p key in the tree,
539 call \p f functor with item found, unlinks it from the tree, and returns \p true.
540 The \ref disposer specified in \p Traits class template parameter is called
541 by garbage collector \p GC asynchronously.
543 The \p Func interface is
546 void operator()( value_type const& item );
550 If the item with key equal to \p key is not found the function return \p false.
552 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
554 template <typename Q, typename Func>
555 bool erase( Q const& key, Func f )
557 return erase_( key, node_compare(),
558 []( Q const&, leaf_node const& ) -> bool { return true; },
562 /// Delete the item from the tree with comparing functor \p pred
564 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
565 but \p pred predicate is used for key comparing.
566 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
567 "Predicate requirements".
568 \p pred must imply the same element order as the comparator used for building the tree.
570 template <typename Q, typename Less, typename Func>
571 bool erase_with( Q const& key, Less pred, Func f )
574 typedef ellen_bintree::details::compare<
577 opt::details::make_comparator_from_less<Less>,
581 return erase_( key, compare_functor(),
582 []( Q const&, leaf_node const& ) -> bool { return true; },
586 /// Extracts an item with minimal key from the tree
588 The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
589 If the tree is empty the function returns an empty guarded pointer.
591 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
592 It means that the function gets leftmost leaf of the tree and tries to unlink it.
593 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
594 So, the function returns the item with minimum key at the moment of tree traversing.
596 The returned \p guarded_ptr prevents disposer invocation for returned item,
597 see \p cds::gc::guarded_ptr for explanation.
598 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
600 guarded_ptr extract_min()
603 extract_min_( gp.guard() );
607 /// Extracts an item with maximal key from the tree
609 The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
610 If the tree is empty the function returns an empty \p guarded_ptr.
612 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
613 It means that the function gets rightmost leaf of the tree and tries to unlink it.
614 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
615 So, the function returns the item with maximal key at the moment of tree traversing.
617 The returned \p guarded_ptr prevents disposer invocation for returned item,
618 see cds::gc::guarded_ptr for explanation.
619 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
621 guarded_ptr extract_max()
624 extract_max_( gp.guard());
628 /// Extracts an item from the tree
629 /** \anchor cds_intrusive_EllenBinTree_extract
630 The function searches an item with key equal to \p key in the tree,
631 unlinks it, and returns a guarded pointer to an item found.
632 If the item is not found the function returns an empty \p guarded_ptr.
634 \p guarded_ptr prevents disposer invocation for returned item,
635 see cds::gc::guarded_ptr for explanation.
636 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
638 template <typename Q>
639 guarded_ptr extract( Q const& key )
642 extract_( gp.guard(), key );
646 /// Extracts an item from the tree using \p pred for searching
648 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
649 but \p pred is used for key compare.
650 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
651 "Predicate requirements".
652 \p pred must imply the same element order as the comparator used for building the tree.
654 template <typename Q, typename Less>
655 guarded_ptr extract_with( Q const& key, Less pred )
658 extract_with_( gp.guard(), key, pred );
662 /// Checks whether the set contains \p key
664 The function searches the item with key equal to \p key
665 and returns \p true if it is found, and \p false otherwise.
667 template <typename Q>
668 bool contains( Q const& key ) const
671 if ( search( res, key, node_compare() )) {
672 m_Stat.onFindSuccess();
676 m_Stat.onFindFailed();
680 template <typename Q>
681 CDS_DEPRECATED("deprecated, use contains()")
682 bool find( Q const& key ) const
684 return contains( key );
688 /// Checks whether the set contains \p key using \p pred predicate for searching
690 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
691 \p Less functor has the interface like \p std::less.
692 \p Less must imply the same element order as the comparator used for building the set.
694 template <typename Q, typename Less>
695 bool contains( Q const& key, Less pred ) const
698 typedef ellen_bintree::details::compare<
701 opt::details::make_comparator_from_less<Less>,
706 if ( search( res, key, compare_functor() )) {
707 m_Stat.onFindSuccess();
710 m_Stat.onFindFailed();
714 template <typename Q, typename Less>
715 CDS_DEPRECATED("deprecated, use contains()")
716 bool find_with( Q const& key, Less pred ) const
718 return contains( key, pred );
722 /// Finds the key \p key
723 /** @anchor cds_intrusive_EllenBinTree_find_func
724 The function searches the item with key equal to \p key and calls the functor \p f for item found.
725 The interface of \p Func functor is:
728 void operator()( value_type& item, Q& key );
731 where \p item is the item found, \p key is the <tt>find</tt> function argument.
733 The functor can change non-key fields of \p item. Note that the functor is only guarantee
734 that \p item cannot be disposed during functor is executing.
735 The functor does not serialize simultaneous access to the tree \p item. If such access is
736 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
738 The function returns \p true if \p key is found, \p false otherwise.
740 template <typename Q, typename Func>
741 bool find( Q& key, Func f ) const
743 return find_( key, f );
746 template <typename Q, typename Func>
747 bool find( Q const& key, Func f ) const
749 return find_( key, f );
753 /// Finds the key \p key with comparing functor \p pred
755 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
756 but \p pred is used for key comparison.
757 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
758 "Predicate requirements".
759 \p pred must imply the same element order as the comparator used for building the tree.
761 template <typename Q, typename Less, typename Func>
762 bool find_with( Q& key, Less pred, Func f ) const
764 return find_with_( key, pred, f );
767 template <typename Q, typename Less, typename Func>
768 bool find_with( Q const& key, Less pred, Func f ) const
770 return find_with_( key, pred, f );
774 /// Finds \p key and returns the item found
775 /** @anchor cds_intrusive_EllenBinTree_get
776 The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
777 The function returns an empty guarded pointer is \p key is not found.
779 \p guarded_ptr prevents disposer invocation for returned item,
780 see \p cds::gc::guarded_ptr for explanation.
781 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
783 template <typename Q>
784 guarded_ptr get( Q const& key ) const
787 get_( gp.guard(), key );
791 /// Finds \p key with predicate \p pred and returns the item found
793 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
794 but \p pred is used for key comparing.
795 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
796 "Predicate requirements".
797 \p pred must imply the same element order as the comparator used for building the tree.
799 template <typename Q, typename Less>
800 guarded_ptr get_with( Q const& key, Less pred ) const
803 get_with_( gp.guard(), key, pred );
807 /// Checks if the tree is empty
810 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
813 /// Clears the tree (thread safe, not atomic)
815 The function unlink all items from the tree.
816 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
820 assert( tree.empty() );
822 the assertion could be raised.
824 For each leaf the \p disposer will be called after unlinking.
834 /// Clears the tree (not thread safe)
836 This function is not thread safe and may be called only when no other thread deals with the tree.
837 The function is used in the tree destructor.
842 internal_node * pParent = nullptr;
843 internal_node * pGrandParent = nullptr;
844 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
847 while ( pLeaf->is_internal() ) {
848 pGrandParent = pParent;
849 pParent = static_cast<internal_node *>( pLeaf );
850 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
853 if ( pLeaf->infinite_key()) {
858 // Remove leftmost leaf and its parent node
859 assert( pGrandParent );
861 assert( pLeaf->is_leaf() );
863 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
864 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
865 free_internal_node( pParent );
869 /// Returns item count in the tree
871 Only leaf nodes containing user data are counted.
873 The value returned depends on item counter type provided by \p Traits template parameter.
874 If it is \p atomicity::empty_item_counter this function always returns 0.
875 The function is not suitable for checking the tree emptiness, use \p empty()
876 member function for this purpose.
880 return m_ItemCounter;
883 /// Returns const reference to internal statistics
884 stat const& statistics() const
889 /// Checks internal consistency (not atomic, not thread-safe)
891 The debugging function to check internal consistency of the tree.
893 bool check_consistency() const
895 return check_consistency( &m_Root );
901 bool check_consistency( internal_node const * pRoot ) const
903 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
904 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
908 if ( node_compare()( *pLeft, *pRoot ) < 0
909 && node_compare()( *pRoot, *pRight ) <= 0
910 && node_compare()( *pLeft, *pRight ) < 0 )
913 if ( pLeft->is_internal() )
914 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
917 if ( bRet && pRight->is_internal() )
918 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
926 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
929 tree_node * p = bRight
930 ? res.guards.protect( search_result::Guard_Leaf, pParent->m_pRight,
931 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
932 : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
933 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});
935 // If we use member hook, data node pointer != internal node pointer
936 // So, we need protect the child twice: as internal node and as data node
937 // and then analyze what kind of node we have
938 tree_node * pVal = bRight
939 ? res.guards.protect( search_result::Guard_temporary, pParent->m_pRight,
940 []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} )
941 : res.guards.protect( search_result::Guard_temporary, pParent->m_pLeft,
942 []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} );
944 // child node is guarded
945 // See whether pParent->m_pUpdate has not been changed
946 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
947 // update has been changed - returns nullptr as a flag to search retry
954 if ( p && p->is_leaf())
955 res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));
957 res.guards.clear( search_result::Guard_temporary );
962 static update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src )
964 return res.guards.protect( search_result::Guard_updParent, src, [](update_ptr p) -> update_desc* { return p.ptr(); });
967 template <typename KeyValue, typename Compare>
968 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
970 internal_node * pParent;
971 internal_node * pGrandParent = nullptr;
972 update_ptr updParent;
973 update_ptr updGrandParent;
975 bool bRightParent = false;
981 //pGrandParent = nullptr;
984 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
985 while ( pLeaf->is_internal() ) {
986 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
987 pGrandParent = pParent;
988 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
989 pParent = static_cast<internal_node *>( pLeaf );
990 bRightParent = bRightLeaf;
991 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
992 updGrandParent = updParent;
994 updParent = search_protect_update( res, pParent->m_pUpdate );
996 switch ( updParent.bits() ) {
997 case update_desc::DFlag:
998 case update_desc::Mark:
999 m_Stat.onSearchRetry();
1003 nCmp = cmp( key, *pParent );
1004 bRightLeaf = nCmp >= 0;
1006 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1008 m_Stat.onSearchRetry();
1013 assert( pLeaf->is_leaf() );
1014 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1016 res.pGrandParent = pGrandParent;
1017 res.pParent = pParent;
1018 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1019 res.updParent = updParent;
1020 res.updGrandParent = updGrandParent;
1021 res.bRightParent = bRightParent;
1022 res.bRightLeaf = bRightLeaf;
1027 bool search_min( search_result& res ) const
1029 internal_node * pParent;
1030 internal_node * pGrandParent;
1031 update_ptr updParent;
1032 update_ptr updGrandParent;
1036 pGrandParent = nullptr;
1037 updParent = nullptr;
1038 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1039 while ( pLeaf->is_internal() ) {
1040 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1041 pGrandParent = pParent;
1042 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1043 pParent = static_cast<internal_node *>( pLeaf );
1044 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1045 updGrandParent = updParent;
1047 updParent = search_protect_update( res, pParent->m_pUpdate );
1049 switch ( updParent.bits() ) {
1050 case update_desc::DFlag:
1051 case update_desc::Mark:
1052 m_Stat.onSearchRetry();
1056 pLeaf = protect_child_node( res, pParent, false, updParent );
1058 m_Stat.onSearchRetry();
1063 if ( pLeaf->infinite_key())
1066 res.pGrandParent = pGrandParent;
1067 res.pParent = pParent;
1068 assert( pLeaf->is_leaf() );
1069 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1070 res.updParent = updParent;
1071 res.updGrandParent = updGrandParent;
1072 res.bRightParent = false;
1073 res.bRightLeaf = false;
1078 bool search_max( search_result& res ) const
1080 internal_node * pParent;
1081 internal_node * pGrandParent;
1082 update_ptr updParent;
1083 update_ptr updGrandParent;
1085 bool bRightParent = false;
1089 pGrandParent = nullptr;
1090 updParent = nullptr;
1092 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1093 while ( pLeaf->is_internal() ) {
1094 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1095 pGrandParent = pParent;
1096 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1097 pParent = static_cast<internal_node *>( pLeaf );
1098 bRightParent = bRightLeaf;
1099 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1100 updGrandParent = updParent;
1102 updParent = search_protect_update( res, pParent->m_pUpdate );
1104 switch ( updParent.bits() ) {
1105 case update_desc::DFlag:
1106 case update_desc::Mark:
1107 m_Stat.onSearchRetry();
1111 bRightLeaf = !pParent->infinite_key();
1112 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1114 m_Stat.onSearchRetry();
1119 if ( pLeaf->infinite_key())
1122 res.pGrandParent = pGrandParent;
1123 res.pParent = pParent;
1124 assert( pLeaf->is_leaf() );
1125 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1126 res.updParent = updParent;
1127 res.updGrandParent = updGrandParent;
1128 res.bRightParent = bRightParent;
1129 res.bRightLeaf = bRightLeaf;
1135 void help( update_ptr pUpdate )
1137 // pUpdate must be guarded!
1138 switch ( pUpdate.bits() ) {
1139 case update_desc::IFlag:
1140 help_insert( pUpdate.ptr() );
1141 m_Stat.onHelpInsert();
1143 case update_desc::DFlag:
1144 help_delete( pUpdate.ptr() );
1145 m_Stat.onHelpDelete();
1147 case update_desc::Mark:
1148 //m_Stat.onHelpMark();
1149 //help_marked( pUpdate.ptr() );
1155 void help_insert( update_desc * pOp )
1157 // pOp must be guarded
1159 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1160 if ( pOp->iInfo.bRightLeaf ) {
1161 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1162 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1165 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1166 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1170 update_ptr cur( pOp, update_desc::IFlag );
1171 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1172 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1175 bool check_delete_precondition( search_result& res ) const
1177 // precondition: all member of res must be guarded
1179 assert( res.pGrandParent != nullptr );
1181 return static_cast<internal_node *>(res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1182 && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1185 bool help_delete( update_desc * pOp )
1187 // precondition: pOp must be guarded
1189 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1190 update_ptr pMark( pOp, update_desc::Mark );
1191 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1192 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1196 retire_node( pOp->dInfo.pParent );
1197 retire_node( pOp->dInfo.pLeaf );
1198 retire_update_desc( pOp );
1201 else if ( pUpdate == pMark ) {
1202 // some other thread is processing help_marked()
1204 m_Stat.onHelpMark();
1208 // Undo grandparent dInfo
1209 update_ptr pDel( pOp, update_desc::DFlag );
1210 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1211 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1213 retire_update_desc( pOp );
1219 static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1221 tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
1222 if ( pSibling->is_leaf() )
1223 guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
1227 void help_marked( update_desc * pOp )
1229 // precondition: pOp must be guarded
1231 tree_node * pParent = pOp->dInfo.pParent;
1233 typename gc::Guard guard;
1234 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1236 if ( pOp->dInfo.bRightParent ) {
1237 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1238 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1241 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1242 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1245 update_ptr upd( pOp, update_desc::DFlag );
1246 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1247 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1250 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1252 assert( res.updParent.bits() == update_desc::Clean );
1253 assert( res.pLeaf->is_leaf() );
1255 // check search result
1256 if ( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_acquire ) == res.pLeaf ) {
1257 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1259 int nCmp = node_compare()(val, *res.pLeaf);
1261 if ( res.pGrandParent ) {
1262 assert( !res.pLeaf->infinite_key() );
1263 pNewInternal->infinite_key( 0 );
1264 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1267 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1268 pNewInternal->infinite_key( 1 );
1270 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1271 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1274 assert( !res.pLeaf->is_internal() );
1276 pNewInternal->infinite_key( 0 );
1277 key_extractor()(pNewInternal->m_Key, val);
1278 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1279 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1280 assert( !res.pLeaf->infinite_key() );
1283 typename gc::Guard guard;
1284 update_desc * pOp = alloc_update_desc();
1285 guard.assign( pOp );
1287 pOp->iInfo.pParent = res.pParent;
1288 pOp->iInfo.pNew = pNewInternal;
1289 pOp->iInfo.pLeaf = res.pLeaf;
1290 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1292 update_ptr updCur( res.updParent.ptr() );
1293 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1294 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1297 retire_update_desc( pOp );
1301 m_Stat.onUpdateDescDeleted();
1302 free_update_desc( pOp );
1309 template <typename Q, typename Compare, typename Equal, typename Func>
1310 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1312 update_desc * pOp = nullptr;
1317 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1319 retire_update_desc( pOp );
1320 m_Stat.onEraseFailed();
1324 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1326 pOp = alloc_update_desc();
1327 if ( check_delete_precondition( res ) ) {
1328 typename gc::Guard guard;
1329 guard.assign( pOp );
1331 pOp->dInfo.pGrandParent = res.pGrandParent;
1332 pOp->dInfo.pParent = res.pParent;
1333 pOp->dInfo.pLeaf = res.pLeaf;
1334 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1335 pOp->dInfo.bRightParent = res.bRightParent;
1336 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1338 update_ptr updGP( res.updGrandParent.ptr() );
1339 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1340 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1341 if ( help_delete( pOp ) ) {
1342 // res.pLeaf is not deleted yet since it is guarded
1343 f( *node_traits::to_value_ptr( res.pLeaf ) );
1352 m_Stat.onEraseRetry();
1356 m_Stat.onEraseSuccess();
1360 template <typename Q>
1361 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
1363 return erase_( key, node_compare(),
1364 []( Q const&, leaf_node const& ) -> bool { return true; },
1365 [&guard]( value_type& found ) { guard.set( &found ); } );
1368 template <typename Q, typename Less>
1369 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
1371 typedef ellen_bintree::details::compare<
1374 opt::details::make_comparator_from_less<Less>,
1378 return erase_( key, compare_functor(),
1379 []( Q const&, leaf_node const& ) -> bool { return true; },
1380 [&guard]( value_type& found ) { guard.set( &found ); } );
1383 bool extract_max_( typename guarded_ptr::native_guard& gp )
1385 update_desc * pOp = nullptr;
1390 if ( !search_max( res )) {
1393 retire_update_desc( pOp );
1394 m_Stat.onExtractMaxFailed();
1398 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1400 pOp = alloc_update_desc();
1401 if ( check_delete_precondition( res ) ) {
1402 typename gc::Guard guard;
1403 guard.assign( pOp );
1405 pOp->dInfo.pGrandParent = res.pGrandParent;
1406 pOp->dInfo.pParent = res.pParent;
1407 pOp->dInfo.pLeaf = res.pLeaf;
1408 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1409 pOp->dInfo.bRightParent = res.bRightParent;
1410 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1412 update_ptr updGP( res.updGrandParent.ptr() );
1413 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1414 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1416 if ( help_delete( pOp ) )
1424 m_Stat.onExtractMaxRetry();
1428 m_Stat.onExtractMaxSuccess();
1429 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1433 bool extract_min_( typename guarded_ptr::native_guard& gp )
1435 update_desc * pOp = nullptr;
1440 if ( !search_min( res )) {
1443 retire_update_desc( pOp );
1444 m_Stat.onExtractMinFailed();
1448 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1450 pOp = alloc_update_desc();
1451 if ( check_delete_precondition( res ) ) {
1452 typename gc::Guard guard;
1453 guard.assign( pOp );
1455 pOp->dInfo.pGrandParent = res.pGrandParent;
1456 pOp->dInfo.pParent = res.pParent;
1457 pOp->dInfo.pLeaf = res.pLeaf;
1458 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1459 pOp->dInfo.bRightParent = res.bRightParent;
1460 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1462 update_ptr updGP( res.updGrandParent.ptr() );
1463 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1464 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1466 if ( help_delete( pOp ))
1474 m_Stat.onExtractMinRetry();
1478 m_Stat.onExtractMinSuccess();
1479 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1483 template <typename Q, typename Func>
1484 bool find_( Q& val, Func f ) const
1487 if ( search( res, val, node_compare() )) {
1488 assert( res.pLeaf );
1489 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1491 m_Stat.onFindSuccess();
1495 m_Stat.onFindFailed();
1499 template <typename Q, typename Less, typename Func>
1500 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1502 typedef ellen_bintree::details::compare<
1505 opt::details::make_comparator_from_less<Less>,
1510 if ( search( res, val, compare_functor() )) {
1511 assert( res.pLeaf );
1512 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1514 m_Stat.onFindSuccess();
1518 m_Stat.onFindFailed();
1522 template <typename Q>
1523 bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
1525 return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1528 template <typename Q, typename Less>
1529 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
1531 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1537 }} // namespace cds::intrusive
1539 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H