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_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 the 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( void* p )
248 disposer()( reinterpret_cast<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( void* pNode )
260 cxx_node_allocator().Delete( reinterpret_cast<internal_node*>( pNode ));
263 struct internal_node_deleter {
264 void operator()( internal_node* p) const
266 cxx_node_allocator().Delete( 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( void* pDesc )
280 cxx_update_desc_allocator().Delete( reinterpret_cast<update_desc*>( 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 successful,
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.onUpdateExist();
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.onUpdateRetry();
463 m_Stat.onUpdateNew();
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 \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
503 that can be not the same as \p value_type.
505 template <typename Q>
506 bool erase( const Q& key )
508 return erase_( key, node_compare(),
509 []( Q const&, leaf_node const& ) -> bool { return true; },
510 [](value_type const&) {} );
513 /// Delete the item from the tree with comparing functor \p pred
515 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
516 but \p pred predicate is used for key comparing.
517 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
518 "Predicate requirements".
519 \p pred must imply the same element order as the comparator used for building the tree.
521 template <typename Q, typename Less>
522 bool erase_with( const Q& key, Less pred )
525 typedef ellen_bintree::details::compare<
528 opt::details::make_comparator_from_less<Less>,
532 return erase_( key, compare_functor(),
533 []( Q const&, leaf_node const& ) -> bool { return true; },
534 [](value_type const&) {} );
537 /// Deletes the item from the tree
538 /** \anchor cds_intrusive_EllenBinTree_erase_func
539 The function searches an item with key equal to \p key in the tree,
540 call \p f functor with item found, unlinks it from the tree, and returns \p true.
541 The \ref disposer specified in \p Traits class template parameter is called
542 by garbage collector \p GC asynchronously.
544 The \p Func interface is
547 void operator()( value_type const& item );
551 If the item with key equal to \p key is not found the function return \p false.
553 Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
554 that can be not the same as \p value_type.
556 template <typename Q, typename Func>
557 bool erase( Q const& key, Func f )
559 return erase_( key, node_compare(),
560 []( Q const&, leaf_node const& ) -> bool { return true; },
564 /// Delete the item from the tree with comparing functor \p pred
566 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
567 but \p pred predicate is used for key comparing.
568 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
569 "Predicate requirements".
570 \p pred must imply the same element order as the comparator used for building the tree.
572 template <typename Q, typename Less, typename Func>
573 bool erase_with( Q const& key, Less pred, Func f )
576 typedef ellen_bintree::details::compare<
579 opt::details::make_comparator_from_less<Less>,
583 return erase_( key, compare_functor(),
584 []( Q const&, leaf_node const& ) -> bool { return true; },
588 /// Extracts an item with minimal key from the tree
590 The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
591 If the tree is empty the function returns an empty guarded pointer.
593 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
594 It means that the function gets leftmost leaf of the tree and tries to unlink it.
595 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
596 So, the function returns the item with minimum key at the moment of tree traversing.
598 The returned \p guarded_ptr prevents disposer invocation for returned item,
599 see \p cds::gc::guarded_ptr for explanation.
600 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
602 guarded_ptr extract_min()
604 return extract_min_();
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()
623 return extract_max_();
626 /// Extracts an item from the tree
627 /** \anchor cds_intrusive_EllenBinTree_extract
628 The function searches an item with key equal to \p key in the tree,
629 unlinks it, and returns a guarded pointer to an item found.
630 If the item is not found the function returns an empty \p guarded_ptr.
632 \p guarded_ptr prevents disposer invocation for returned item,
633 see cds::gc::guarded_ptr for explanation.
634 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
636 template <typename Q>
637 guarded_ptr extract( Q const& key )
639 return extract_( key );
642 /// Extracts an item from the tree using \p pred for searching
644 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
645 but \p pred is used for key compare.
646 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
647 "Predicate requirements".
648 \p pred must imply the same element order as the comparator used for building the tree.
650 template <typename Q, typename Less>
651 guarded_ptr extract_with( Q const& key, Less pred )
653 return extract_with_( key, pred );
656 /// Checks whether the set contains \p key
658 The function searches the item with key equal to \p key
659 and returns \p true if it is found, and \p false otherwise.
661 template <typename Q>
662 bool contains( Q const& key ) const
665 if ( search( res, key, node_compare())) {
666 m_Stat.onFindSuccess();
670 m_Stat.onFindFailed();
674 template <typename Q>
675 CDS_DEPRECATED("deprecated, use contains()")
676 bool find( Q const& key ) const
678 return contains( key );
682 /// Checks whether the set contains \p key using \p pred predicate for searching
684 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
685 \p Less functor has the interface like \p std::less.
686 \p Less must imply the same element order as the comparator used for building the set.
688 template <typename Q, typename Less>
689 bool contains( Q const& key, Less pred ) const
692 typedef ellen_bintree::details::compare<
695 opt::details::make_comparator_from_less<Less>,
700 if ( search( res, key, compare_functor())) {
701 m_Stat.onFindSuccess();
704 m_Stat.onFindFailed();
708 template <typename Q, typename Less>
709 CDS_DEPRECATED("deprecated, use contains()")
710 bool find_with( Q const& key, Less pred ) const
712 return contains( key, pred );
716 /// Finds the key \p key
717 /** @anchor cds_intrusive_EllenBinTree_find_func
718 The function searches the item with key equal to \p key and calls the functor \p f for item found.
719 The interface of \p Func functor is:
722 void operator()( value_type& item, Q& key );
725 where \p item is the item found, \p key is the <tt>find</tt> function argument.
727 The functor can change non-key fields of \p item. Note that the functor is only guarantee
728 that \p item cannot be disposed during functor is executing.
729 The functor does not serialize simultaneous access to the tree \p item. If such access is
730 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
732 The function returns \p true if \p key is found, \p false otherwise.
734 template <typename Q, typename Func>
735 bool find( Q& key, Func f ) const
737 return find_( key, f );
740 template <typename Q, typename Func>
741 bool find( Q const& key, Func f ) const
743 return find_( key, f );
747 /// Finds the key \p key with comparing functor \p pred
749 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
750 but \p pred is used for key comparison.
751 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
752 "Predicate requirements".
753 \p pred must imply the same element order as the comparator used for building the tree.
755 template <typename Q, typename Less, typename Func>
756 bool find_with( Q& key, Less pred, Func f ) const
758 return find_with_( key, pred, f );
761 template <typename Q, typename Less, typename Func>
762 bool find_with( Q const& key, Less pred, Func f ) const
764 return find_with_( key, pred, f );
768 /// Finds \p key and returns the item found
769 /** @anchor cds_intrusive_EllenBinTree_get
770 The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
771 The function returns an empty guarded pointer is \p key is not found.
773 \p guarded_ptr prevents disposer invocation for returned item,
774 see \p cds::gc::guarded_ptr for explanation.
775 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
777 template <typename Q>
778 guarded_ptr get( Q const& key ) const
783 /// Finds \p key with predicate \p pred and returns the item found
785 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
786 but \p pred is used for key comparing.
787 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
788 "Predicate requirements".
789 \p pred must imply the same element order as the comparator used for building the tree.
791 template <typename Q, typename Less>
792 guarded_ptr get_with( Q const& key, Less pred ) const
794 return get_with_( key, pred );
797 /// Checks if the tree is empty
800 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
803 /// Clears the tree (thread safe, not atomic)
805 The function unlink all items from the tree.
806 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
810 assert( tree.empty());
812 the assertion could be raised.
814 For each leaf the \p disposer will be called after unlinking.
824 /// Clears the tree (not thread safe)
826 This function is not thread safe and may be called only when no other thread deals with the tree.
827 The function is used in the tree destructor.
832 internal_node * pParent = nullptr;
833 internal_node * pGrandParent = nullptr;
834 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
837 while ( pLeaf->is_internal()) {
838 pGrandParent = pParent;
839 pParent = static_cast<internal_node *>( pLeaf );
840 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
843 if ( pLeaf->infinite_key()) {
848 // Remove leftmost leaf and its parent node
849 assert( pGrandParent );
851 assert( pLeaf->is_leaf());
853 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
854 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf )));
855 free_internal_node( pParent );
859 /// Returns item count in the tree
861 Only leaf nodes containing user data are counted.
863 The value returned depends on item counter type provided by \p Traits template parameter.
864 If it is \p atomicity::empty_item_counter this function always returns 0.
865 The function is not suitable for checking the tree emptiness, use \p empty()
866 member function for this purpose.
870 return m_ItemCounter;
873 /// Returns const reference to internal statistics
874 stat const& statistics() const
879 /// Checks internal consistency (not atomic, not thread-safe)
881 The debugging function to check internal consistency of the tree.
883 bool check_consistency() const
885 return check_consistency( &m_Root );
891 bool check_consistency( internal_node const * pRoot ) const
893 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
894 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
898 if ( node_compare()( *pLeft, *pRoot ) < 0
899 && node_compare()( *pRoot, *pRight ) <= 0
900 && node_compare()( *pLeft, *pRight ) < 0 )
903 if ( pLeft->is_internal())
904 bRet = check_consistency( static_cast<internal_node *>( pLeft ));
907 if ( bRet && pRight->is_internal())
908 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
916 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
919 tree_node * p = bRight
920 ? res.guards.protect( search_result::Guard_Leaf, pParent->m_pRight,
921 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
922 : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
923 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});
925 // If we use member hook, data node pointer != internal node pointer
926 // So, we need protect the child twice: as internal node and as data node
927 // and then analyze what kind of node we have
928 tree_node * pVal = bRight
929 ? res.guards.protect( search_result::Guard_temporary, pParent->m_pRight,
930 []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} )
931 : res.guards.protect( search_result::Guard_temporary, pParent->m_pLeft,
932 []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} );
934 // child node is guarded
935 // See whether pParent->m_pUpdate has not been changed
936 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
937 // update has been changed - returns nullptr as a flag to search retry
944 if ( p && p->is_leaf())
945 res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));
947 res.guards.clear( search_result::Guard_temporary );
952 static update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src )
954 return res.guards.protect( search_result::Guard_updParent, src, [](update_ptr p) -> update_desc* { return p.ptr(); });
957 template <typename KeyValue, typename Compare>
958 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
960 internal_node * pParent;
961 internal_node * pGrandParent = nullptr;
962 update_ptr updParent;
963 update_ptr updGrandParent;
965 bool bRightParent = false;
971 //pGrandParent = nullptr;
974 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
975 while ( pLeaf->is_internal()) {
976 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
977 pGrandParent = pParent;
978 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
979 pParent = static_cast<internal_node *>( pLeaf );
980 bRightParent = bRightLeaf;
981 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
982 updGrandParent = updParent;
984 updParent = search_protect_update( res, pParent->m_pUpdate );
986 switch ( updParent.bits()) {
987 case update_desc::DFlag:
988 case update_desc::Mark:
989 m_Stat.onSearchRetry();
993 nCmp = cmp( key, *pParent );
994 bRightLeaf = nCmp >= 0;
996 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
998 m_Stat.onSearchRetry();
1003 assert( pLeaf->is_leaf());
1004 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf));
1006 res.pGrandParent = pGrandParent;
1007 res.pParent = pParent;
1008 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1009 res.updParent = updParent;
1010 res.updGrandParent = updGrandParent;
1011 res.bRightParent = bRightParent;
1012 res.bRightLeaf = bRightLeaf;
1017 bool search_min( search_result& res ) const
1019 internal_node * pParent;
1020 internal_node * pGrandParent;
1021 update_ptr updParent;
1022 update_ptr updGrandParent;
1026 pGrandParent = nullptr;
1027 updParent = nullptr;
1028 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1029 while ( pLeaf->is_internal()) {
1030 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1031 pGrandParent = pParent;
1032 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1033 pParent = static_cast<internal_node *>( pLeaf );
1034 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1035 updGrandParent = updParent;
1037 updParent = search_protect_update( res, pParent->m_pUpdate );
1039 switch ( updParent.bits()) {
1040 case update_desc::DFlag:
1041 case update_desc::Mark:
1042 m_Stat.onSearchRetry();
1046 pLeaf = protect_child_node( res, pParent, false, updParent );
1048 m_Stat.onSearchRetry();
1053 if ( pLeaf->infinite_key())
1056 res.pGrandParent = pGrandParent;
1057 res.pParent = pParent;
1058 assert( pLeaf->is_leaf());
1059 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1060 res.updParent = updParent;
1061 res.updGrandParent = updGrandParent;
1062 res.bRightParent = false;
1063 res.bRightLeaf = false;
1068 bool search_max( search_result& res ) const
1070 internal_node * pParent;
1071 internal_node * pGrandParent;
1072 update_ptr updParent;
1073 update_ptr updGrandParent;
1075 bool bRightParent = false;
1079 pGrandParent = nullptr;
1080 updParent = nullptr;
1082 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1083 while ( pLeaf->is_internal()) {
1084 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1085 pGrandParent = pParent;
1086 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1087 pParent = static_cast<internal_node *>( pLeaf );
1088 bRightParent = bRightLeaf;
1089 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1090 updGrandParent = updParent;
1092 updParent = search_protect_update( res, pParent->m_pUpdate );
1094 switch ( updParent.bits()) {
1095 case update_desc::DFlag:
1096 case update_desc::Mark:
1097 m_Stat.onSearchRetry();
1101 bRightLeaf = !pParent->infinite_key();
1102 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1104 m_Stat.onSearchRetry();
1109 if ( pLeaf->infinite_key())
1112 res.pGrandParent = pGrandParent;
1113 res.pParent = pParent;
1114 assert( pLeaf->is_leaf());
1115 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1116 res.updParent = updParent;
1117 res.updGrandParent = updGrandParent;
1118 res.bRightParent = bRightParent;
1119 res.bRightLeaf = bRightLeaf;
1125 void help( update_ptr pUpdate )
1127 // pUpdate must be guarded!
1128 switch ( pUpdate.bits()) {
1129 case update_desc::IFlag:
1130 help_insert( pUpdate.ptr());
1131 m_Stat.onHelpInsert();
1133 case update_desc::DFlag:
1134 help_delete( pUpdate.ptr());
1135 m_Stat.onHelpDelete();
1137 case update_desc::Mark:
1138 //m_Stat.onHelpMark();
1139 //help_marked( pUpdate.ptr());
1145 void help_insert( update_desc * pOp )
1147 // pOp must be guarded
1149 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1150 if ( pOp->iInfo.bRightLeaf ) {
1151 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1152 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1155 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1156 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1160 update_ptr cur( pOp, update_desc::IFlag );
1161 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1162 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1165 bool check_delete_precondition( search_result& res ) const
1167 // precondition: all member of res must be guarded
1169 assert( res.pGrandParent != nullptr );
1171 return static_cast<internal_node *>(res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1172 && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1175 bool help_delete( update_desc * pOp )
1177 // precondition: pOp must be guarded
1179 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1180 update_ptr pMark( pOp, update_desc::Mark );
1181 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1182 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1186 retire_node( pOp->dInfo.pParent );
1187 retire_node( pOp->dInfo.pLeaf );
1188 retire_update_desc( pOp );
1191 else if ( pUpdate == pMark ) {
1192 // some other thread is processing help_marked()
1194 m_Stat.onHelpMark();
1198 // Undo grandparent dInfo
1199 update_ptr pDel( pOp, update_desc::DFlag );
1200 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1201 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1203 retire_update_desc( pOp );
1209 static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1211 tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
1212 if ( pSibling->is_leaf())
1213 guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
1217 void help_marked( update_desc * pOp )
1219 // precondition: pOp must be guarded
1221 tree_node * pParent = pOp->dInfo.pParent;
1223 typename gc::Guard guard;
1224 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1226 if ( pOp->dInfo.bRightParent ) {
1227 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1228 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1231 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1232 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1235 update_ptr upd( pOp, update_desc::DFlag );
1236 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1237 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1240 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1242 assert( res.updParent.bits() == update_desc::Clean );
1243 assert( res.pLeaf->is_leaf());
1245 // check search result
1246 if ( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_acquire ) == res.pLeaf ) {
1247 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1249 int nCmp = node_compare()(val, *res.pLeaf);
1251 if ( res.pGrandParent ) {
1252 assert( !res.pLeaf->infinite_key());
1253 pNewInternal->infinite_key( 0 );
1254 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1257 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1258 pNewInternal->infinite_key( 1 );
1260 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1261 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1264 assert( !res.pLeaf->is_internal());
1266 pNewInternal->infinite_key( 0 );
1267 key_extractor()(pNewInternal->m_Key, val);
1268 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1269 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1270 assert( !res.pLeaf->infinite_key());
1273 typename gc::Guard guard;
1274 update_desc * pOp = alloc_update_desc();
1275 guard.assign( pOp );
1277 pOp->iInfo.pParent = res.pParent;
1278 pOp->iInfo.pNew = pNewInternal;
1279 pOp->iInfo.pLeaf = res.pLeaf;
1280 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1282 update_ptr updCur( res.updParent.ptr());
1283 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1284 memory_model::memory_order_acq_rel, atomics::memory_order_relaxed )) {
1287 retire_update_desc( pOp );
1291 m_Stat.onUpdateDescDeleted();
1292 free_update_desc( pOp );
1299 template <typename Q, typename Compare, typename Equal, typename Func>
1300 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1302 update_desc * pOp = nullptr;
1307 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf )) {
1309 retire_update_desc( pOp );
1310 m_Stat.onEraseFailed();
1314 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1316 pOp = alloc_update_desc();
1317 if ( check_delete_precondition( res )) {
1318 typename gc::Guard guard;
1319 guard.assign( pOp );
1321 pOp->dInfo.pGrandParent = res.pGrandParent;
1322 pOp->dInfo.pParent = res.pParent;
1323 pOp->dInfo.pLeaf = res.pLeaf;
1324 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1325 pOp->dInfo.bRightParent = res.bRightParent;
1326 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1328 update_ptr updGP( res.updGrandParent.ptr());
1329 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1330 memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1331 if ( help_delete( pOp )) {
1332 // res.pLeaf is not deleted yet since it is guarded
1333 f( *node_traits::to_value_ptr( res.pLeaf ));
1342 m_Stat.onEraseRetry();
1346 m_Stat.onEraseSuccess();
1350 template <typename Q, typename Compare>
1351 guarded_ptr extract_item( Q const& key, Compare cmp )
1353 update_desc * pOp = nullptr;
1358 if ( !search( res, key, cmp )) {
1360 retire_update_desc( pOp );
1361 m_Stat.onEraseFailed();
1362 return guarded_ptr();
1365 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1367 pOp = alloc_update_desc();
1368 if ( check_delete_precondition( res )) {
1369 typename gc::Guard guard;
1370 guard.assign( pOp );
1372 pOp->dInfo.pGrandParent = res.pGrandParent;
1373 pOp->dInfo.pParent = res.pParent;
1374 pOp->dInfo.pLeaf = res.pLeaf;
1375 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1376 pOp->dInfo.bRightParent = res.bRightParent;
1377 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1379 update_ptr updGP( res.updGrandParent.ptr());
1380 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1381 memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1382 if ( help_delete( pOp ))
1390 m_Stat.onEraseRetry();
1394 m_Stat.onEraseSuccess();
1395 return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
1398 template <typename Q>
1399 guarded_ptr extract_( Q const& key )
1401 return extract_item( key, node_compare());
1404 template <typename Q, typename Less>
1405 guarded_ptr extract_with_( Q const& key, Less /*pred*/ )
1407 typedef ellen_bintree::details::compare<
1410 opt::details::make_comparator_from_less<Less>,
1414 return extract_item( key, compare_functor());
1417 guarded_ptr extract_max_()
1419 update_desc * pOp = nullptr;
1424 if ( !search_max( res )) {
1427 retire_update_desc( pOp );
1428 m_Stat.onExtractMaxFailed();
1429 return guarded_ptr();
1432 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1434 pOp = alloc_update_desc();
1435 if ( check_delete_precondition( res )) {
1436 typename gc::Guard guard;
1437 guard.assign( pOp );
1439 pOp->dInfo.pGrandParent = res.pGrandParent;
1440 pOp->dInfo.pParent = res.pParent;
1441 pOp->dInfo.pLeaf = res.pLeaf;
1442 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1443 pOp->dInfo.bRightParent = res.bRightParent;
1444 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1446 update_ptr updGP( res.updGrandParent.ptr());
1447 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1448 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1450 if ( help_delete( pOp ))
1458 m_Stat.onExtractMaxRetry();
1462 m_Stat.onExtractMaxSuccess();
1463 return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
1466 guarded_ptr extract_min_()
1468 update_desc * pOp = nullptr;
1473 if ( !search_min( res )) {
1476 retire_update_desc( pOp );
1477 m_Stat.onExtractMinFailed();
1478 return guarded_ptr();
1481 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1483 pOp = alloc_update_desc();
1484 if ( check_delete_precondition( res )) {
1485 typename gc::Guard guard;
1486 guard.assign( pOp );
1488 pOp->dInfo.pGrandParent = res.pGrandParent;
1489 pOp->dInfo.pParent = res.pParent;
1490 pOp->dInfo.pLeaf = res.pLeaf;
1491 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1492 pOp->dInfo.bRightParent = res.bRightParent;
1493 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1495 update_ptr updGP( res.updGrandParent.ptr());
1496 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1497 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1499 if ( help_delete( pOp ))
1507 m_Stat.onExtractMinRetry();
1511 m_Stat.onExtractMinSuccess();
1512 return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
1515 template <typename Q, typename Func>
1516 bool find_( Q& val, Func f ) const
1519 if ( search( res, val, node_compare())) {
1520 assert( res.pLeaf );
1521 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1523 m_Stat.onFindSuccess();
1527 m_Stat.onFindFailed();
1531 template <typename Q, typename Less, typename Func>
1532 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1534 typedef ellen_bintree::details::compare<
1537 opt::details::make_comparator_from_less<Less>,
1542 if ( search( res, val, compare_functor())) {
1543 assert( res.pLeaf );
1544 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1546 m_Stat.onFindSuccess();
1550 m_Stat.onFindFailed();
1554 template <typename Q>
1555 guarded_ptr get_( Q const& val ) const
1558 if ( search( res, val, node_compare())) {
1559 assert( res.pLeaf );
1560 m_Stat.onFindSuccess();
1561 return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
1564 m_Stat.onFindFailed();
1565 return guarded_ptr();
1568 template <typename Q, typename Less>
1569 guarded_ptr get_with_( Q const& val, Less pred ) const
1573 typedef ellen_bintree::details::compare<
1576 opt::details::make_comparator_from_less<Less>,
1581 if ( search( res, val, compare_functor())) {
1582 assert( res.pLeaf );
1583 m_Stat.onFindSuccess();
1584 return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
1587 m_Stat.onFindFailed();
1588 return guarded_ptr();
1595 }} // namespace cds::intrusive
1597 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H