3 #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
4 #define __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
7 #include <functional> // ref
8 #include <cds/intrusive/details/ellen_bintree_base.h>
9 #include <cds/opt/compare.h>
10 #include <cds/details/binary_functor_wrapper.h>
11 #include <cds/urcu/details/check_deadlock.h>
12 #include <cds/gc/guarded_ptr.h>
14 namespace cds { namespace intrusive {
16 /// Ellen's et al binary search tree
17 /** @ingroup cds_intrusive_map
18 @ingroup cds_intrusive_tree
19 @anchor cds_intrusive_EllenBinTree
22 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
24 %EllenBinTree is an unbalanced leaf-oriented binary search tree that implements the <i>set</i>
25 abstract data type. Nodes maintains child pointers but not parent pointers.
26 Every internal node has exactly two children, and all data of type \p T currently in
27 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
28 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
29 may or may not be in the set. \p Key type is a subset of \p T type.
30 There should be exactly defined a key extracting functor for converting object of type \p T to
31 object of type \p Key.
33 Due to \p extract_min and \p extract_max member functions the \p %EllenBinTree can act as
34 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
35 the priority value plus some uniformly distributed random value.
37 @note In the current implementation we do not use helping technique described in the original paper.
38 In Hazard Pointer schema helping is too complicated and does not give any observable benefits.
39 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
40 the operation done. Such solution allows greatly simplify the implementation of tree.
42 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
43 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
45 @note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
46 There are header file for each GC type:
47 - <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC cds::gc::HP
48 - <tt><cds/intrusive/ellen_bintree_ptb.h></tt> - for Pass-the-Buck GC cds::gc::PTB
49 - <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU GC
50 (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
52 <b>Template arguments</b> :
53 - \p GC - garbage collector used, possible types are cds::gc::HP, cds::gc::PTB.
54 Note that cds::gc::HRC is not supported.
55 - \p Key - key type, a subset of \p T
56 - \p T - type to be stored in tree's leaf nodes. The type must be based on ellen_bintree::node
57 (for ellen_bintree::base_hook) or it must have a member of type ellen_bintree::node
58 (for ellen_bintree::member_hook).
59 - \p Traits - type traits. See ellen_bintree::type_traits for explanation.
61 It is possible to declare option-based tree with cds::intrusive::ellen_bintree::make_traits metafunction
62 instead of \p Traits template argument.
63 Template argument list \p Options of cds::intrusive::ellen_bintree::make_traits metafunction are:
64 - opt::hook - hook used. Possible values are: ellen_bintree::base_hook, ellen_bintree::member_hook, ellen_bintree::traits_hook.
65 If the option is not specified, <tt>ellen_bintree::base_hook<></tt> is used.
66 - ellen_bintree::key_extractor - key extracting functor, mandatory option. The functor has the following prototype:
68 struct key_extractor {
69 void operator ()( Key& dest, T const& src );
72 It should initialize \p dest key from \p src data. The functor is used to initialize internal nodes.
73 - opt::compare - key compare functor. No default functor is provided.
74 If the option is not specified, \p %opt::less is used.
75 - opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
76 - opt::disposer - the functor used for dispose removed nodes. Default is opt::v::empty_disposer. Due the nature
77 of GC schema the disposer may be called asynchronously. The disposer is used only for leaf nodes.
78 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that means no item counting.
79 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
80 or opt::v::sequential_consistent (sequentially consisnent memory model).
81 - ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
82 default is CDS_DEFAULT_ALLOCATOR.
83 Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
84 The number of simultaneously existing descriptors is bounded and depends on the number of threads
85 working with the tree and GC internals.
86 A bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good candidate
87 for the free-list of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
88 Also notice that size of update descriptor is constant and not dependent on the type of data
89 stored in the tree so single free-list object can be used for all \p %EllenBinTree objects.
90 - opt::node_allocator - the allocator used for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
91 - opt::stat - internal statistics. Available types: ellen_bintree::stat, ellen_bintree::empty_stat (the default)
93 @anchor cds_intrusive_EllenBinTree_less
94 <b>Predicate requirements</b>
96 opt::less, opt::compare and other predicates using with member fuctions should accept at least parameters
97 of type \p T and \p Key in any combination.
98 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
100 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
102 std::string m_strKey;
107 bool operator()( Foo const& v1, Foo const& v2 ) const
108 { return v1.m_strKey < v2.m_strKey ; }
110 bool operator()( Foo const& v, std::string const& s ) const
111 { return v.m_strKey < s ; }
113 bool operator()( std::string const& s, Foo const& v ) const
114 { return s < v.m_strKey ; }
116 // Support comparing std::string and char const *
117 bool operator()( std::string const& s, char const * p ) const
118 { return s.compare(p) < 0 ; }
120 bool operator()( Foo const& v, char const * p ) const
121 { return v.m_strKey.compare(p) < 0 ; }
123 bool operator()( char const * p, std::string const& s ) const
124 { return s.compare(p) > 0; }
126 bool operator()( char const * p, Foo const& v ) const
127 { return v.m_strKey.compare(p) > 0; }
134 #ifdef CDS_DOXYGEN_INVOKED
135 class Traits = ellen_bintree::type_traits
143 typedef GC gc ; ///< Garbage collector used
144 typedef Key key_type ; ///< type of a key stored in internal nodes; key is a part of \p value_type
145 typedef T value_type ; ///< type of value stored in the binary tree
146 typedef Traits options ; ///< Traits template parameter
148 typedef typename options::hook hook ; ///< hook type
149 typedef typename hook::node_type node_type ; ///< node type
150 typedef typename options::disposer disposer ; ///< leaf node disposer
152 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
156 typedef ellen_bintree::base_node< gc > tree_node ; ///< Base type of tree node
157 typedef node_type leaf_node ; ///< Leaf node type
158 typedef ellen_bintree::node_types< gc, key_type, typename leaf_node::tag > node_factory;
159 typedef typename node_factory::internal_node_type internal_node ; ///< Internal node type
160 typedef typename node_factory::update_desc_type update_desc ; ///< Update descriptor
161 typedef typename update_desc::update_ptr update_ptr ; ///< Marked pointer to update descriptor
165 # ifdef CDS_DOXYGEN_INVOKED
166 typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
167 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< Node traits
169 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
170 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
172 static internal_node const& to_internal_node( tree_node const& n )
174 assert( n.is_internal() );
175 return static_cast<internal_node const&>( n );
178 static leaf_node const& to_leaf_node( tree_node const& n )
180 assert( n.is_leaf() );
181 return static_cast<leaf_node const&>( n );
186 typedef typename options::item_counter item_counter; ///< Item counting policy used
187 typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
188 typedef typename options::stat stat ; ///< internal statistics type
189 typedef typename options::key_extractor key_extractor ; ///< key extracting functor
191 typedef typename options::node_allocator node_allocator ; ///< Internal node allocator
192 typedef typename options::update_desc_allocator update_desc_allocator ; ///< Update descriptor allocator
196 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
198 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
199 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
201 struct search_result {
206 Guard_updGrandParent,
212 // end of guard indices
216 typedef typename gc::template GuardArray< guard_count > guard_array;
219 internal_node * pGrandParent;
220 internal_node * pParent;
222 update_ptr updParent;
223 update_ptr updGrandParent;
224 bool bRightLeaf ; // true if pLeaf is right child of pParent, false otherwise
225 bool bRightParent ; // true if pParent is right child of pGrandParent, false otherwise
228 :pGrandParent( nullptr )
232 ,bRightParent( false )
235 void clean_help_guards()
237 guards.clear( Guard_helpLeaf );
244 internal_node m_Root ; ///< Tree root node (key= Infinite2)
245 leaf_node m_LeafInf1 ; ///< Infinite leaf 1 (key= Infinite1)
246 leaf_node m_LeafInf2 ; ///< Infinite leaf 2 (key= Infinite2)
249 item_counter m_ItemCounter ; ///< item counter
250 mutable stat m_Stat ; ///< internal statistics
254 static void free_leaf_node( value_type * p )
259 internal_node * alloc_internal_node() const
261 m_Stat.onInternalNodeCreated();
262 internal_node * pNode = cxx_node_allocator().New();
266 static void free_internal_node( internal_node * pNode )
268 cxx_node_allocator().Delete( pNode );
271 struct internal_node_deleter {
272 void operator()( internal_node * p) const
274 free_internal_node( p );
278 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
280 update_desc * alloc_update_desc() const
282 m_Stat.onUpdateDescCreated();
283 return cxx_update_desc_allocator().New();
286 static void free_update_desc( update_desc * pDesc )
288 cxx_update_desc_allocator().Delete( pDesc );
291 void retire_node( tree_node * pNode ) const
293 if ( pNode->is_leaf() ) {
294 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
295 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
297 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
300 assert( static_cast<internal_node *>( pNode ) != &m_Root );
301 m_Stat.onInternalNodeDeleted();
303 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
307 void retire_update_desc( update_desc * p ) const
309 m_Stat.onUpdateDescDeleted();
310 gc::template retire( p, free_update_desc );
313 void make_empty_tree()
315 m_Root.infinite_key( 2 );
316 m_LeafInf1.infinite_key( 1 );
317 m_LeafInf2.infinite_key( 2 );
318 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
319 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
324 /// Default constructor
327 static_assert( (!std::is_same< key_extractor, opt::none >::value), "The key extractor option must be specified" );
339 The function inserts \p val in the tree if it does not contain
340 an item with key equal to \p val.
342 Returns \p true if \p val is placed into the tree, \p false otherwise.
344 bool insert( value_type& val )
346 return insert( val, []( value_type& ) {} );
351 This function is intended for derived non-intrusive containers.
353 The function allows to split creating of new item into two part:
354 - create item with key only
355 - insert new item into the tree
356 - if inserting is success, calls \p f functor to initialize value-field of \p val.
358 The functor signature is:
360 void func( value_type& val );
362 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
363 \p val no any other changes could be made on this tree's item by concurrent threads.
364 The user-defined functor is called only if the inserting is success and may be passed by reference
367 template <typename Func>
368 bool insert( value_type& val, Func f )
370 typename gc::Guard guardInsert;
371 guardInsert.assign( &val );
373 unique_internal_node_ptr pNewInternal;
377 if ( search( res, val, node_compare() )) {
378 if ( pNewInternal.get() )
379 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
380 m_Stat.onInsertFailed();
384 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
386 if ( !pNewInternal.get() )
387 pNewInternal.reset( alloc_internal_node() );
389 if ( try_insert( val, pNewInternal.get(), res )) {
391 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
396 m_Stat.onInsertRetry();
400 m_Stat.onInsertSuccess();
404 /// Ensures that the \p val exists in the tree
406 The operation performs inserting or changing data with lock-free manner.
408 If the item \p val is not found in the tree, then \p val is inserted into the tree.
409 Otherwise, the functor \p func is called with item found.
410 The functor signature is:
412 void func( bool bNew, value_type& item, value_type& val );
415 - \p bNew - \p true if the item has been inserted, \p false otherwise
416 - \p item - item of the tree
417 - \p val - argument \p val passed into the \p ensure function
418 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
419 refer to the same thing.
421 The functor can change non-key fields of the \p item; however, \p func must guarantee
422 that during changing no any other modifications could be made on this item by concurrent threads.
424 You can pass \p func argument by value or by reference using \p std::ref.
426 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
427 \p second is \p true if new item has been added or \p false if the item with \p key
428 already is in the tree.
430 template <typename Func>
431 std::pair<bool, bool> ensure( value_type& val, Func func )
433 typename gc::Guard guardInsert;
434 guardInsert.assign( &val );
436 unique_internal_node_ptr pNewInternal;
440 if ( search( res, val, node_compare() )) {
441 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
442 if ( pNewInternal.get() )
443 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
444 m_Stat.onEnsureExist();
445 return std::make_pair( true, false );
448 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
450 if ( !pNewInternal.get() )
451 pNewInternal.reset( alloc_internal_node() );
453 if ( try_insert( val, pNewInternal.get(), res )) {
454 func( true, val, val );
455 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 /// Unlinks the item \p val from the tree
469 The function searches the item \p val in the tree and unlink it from the tree
470 if it is found and is equal to \p val.
472 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
473 and deletes the item found. \p unlink finds an item by key and deletes it
474 only if \p val is an item of the tree, i.e. the pointer to item found
475 is equal to <tt> &val </tt>.
477 The \ref disposer specified in \p Traits class template parameter is called
478 by garbage collector \p GC asynchronously.
480 The function returns \p true if success and \p false otherwise.
482 bool unlink( value_type& val )
484 return erase_( val, node_compare(),
485 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
486 [](value_type const&) {} );
489 /// Deletes the item from the tree
490 /** \anchor cds_intrusive_EllenBinTree_erase
491 The function searches an item with key equal to \p val in the tree,
492 unlinks it from the tree, and returns \p true.
493 If the item with key equal to \p val is not found the function return \p false.
495 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
497 template <typename Q>
498 bool erase( const Q& val )
500 return erase_( val, node_compare(),
501 []( Q const&, leaf_node const& ) -> bool { return true; },
502 [](value_type const&) {} );
505 /// Delete the item from the tree with comparing functor \p pred
507 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
508 but \p pred predicate is used for key comparing.
509 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
510 "Predicate requirements".
511 \p pred must imply the same element order as the comparator used for building the tree.
513 template <typename Q, typename Less>
514 bool erase_with( const Q& val, Less pred )
516 typedef ellen_bintree::details::compare<
519 opt::details::make_comparator_from_less<Less>,
523 return erase_( val, compare_functor(),
524 []( Q const&, leaf_node const& ) -> bool { return true; },
525 [](value_type const&) {} );
528 /// Deletes the item from the tree
529 /** \anchor cds_intrusive_EllenBinTree_erase_func
530 The function searches an item with key equal to \p val in the tree,
531 call \p f functor with item found, unlinks it from the tree, and returns \p true.
532 The \ref disposer specified in \p Traits class template parameter is called
533 by garbage collector \p GC asynchronously.
535 The \p Func interface is
538 void operator()( value_type const& item );
541 The functor can be passed by reference with <tt>boost:ref</tt>
543 If the item with key equal to \p val is not found the function return \p false.
545 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
547 template <typename Q, typename Func>
548 bool erase( Q const& val, Func f )
550 return erase_( val, node_compare(),
551 []( Q const&, leaf_node const& ) -> bool { return true; },
555 /// Delete the item from the tree with comparing functor \p pred
557 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
558 but \p pred predicate is used for key comparing.
559 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
560 "Predicate requirements".
561 \p pred must imply the same element order as the comparator used for building the tree.
563 template <typename Q, typename Less, typename Func>
564 bool erase_with( Q const& val, Less pred, Func f )
566 typedef ellen_bintree::details::compare<
569 opt::details::make_comparator_from_less<Less>,
573 return erase_( val, compare_functor(),
574 []( Q const&, leaf_node const& ) -> bool { return true; },
578 /// Extracts an item with minimal key from the tree
580 The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p dest parameter.
581 If the tree is empty the function returns \p false.
583 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
584 It means that the function gets leftmost leaf of the tree and tries to unlink it.
585 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
586 So, the function returns the item with minimum key at the moment of tree traversing.
588 The guarded pointer \p dest prevents disposer invocation for returned item,
589 see cds::gc::guarded_ptr for explanation.
590 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
592 bool extract_min( guarded_ptr& dest )
594 return extract_min_( dest.guard());
597 /// Extracts an item with maximal key from the tree
599 The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p dest parameter.
600 If the tree is empty the function returns \p false.
602 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
603 It means that the function gets rightmost leaf of the tree and tries to unlink it.
604 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
605 So, the function returns the item with maximal key at the moment of tree traversing.
607 The guarded pointer \p dest prevents disposer invocation for returned item,
608 see cds::gc::guarded_ptr for explanation.
609 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
611 bool extract_max( guarded_ptr& dest )
613 return extract_max_( dest.guard() );
616 /// Extracts an item from the tree
617 /** \anchor cds_intrusive_EllenBinTree_extract
618 The function searches an item with key equal to \p key in the tree,
619 unlinks it, and returns pointer to an item found in \p dest parameter.
620 If the item is not found the function returns \p false.
622 The guarded pointer \p dest prevents disposer invocation for returned item,
623 see cds::gc::guarded_ptr for explanation.
624 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
626 template <typename Q>
627 bool extract( guarded_ptr& dest, Q const& key )
629 return extract_( dest.guard(), key );
632 /// Extracts an item from the tree using \p pred for searching
634 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(guarded_ptr& dest, Q const&)"
635 but \p pred is used for key compare.
636 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
637 "Predicate requirements".
638 \p pred must imply the same element order as the comparator used for building the tree.
640 template <typename Q, typename Less>
641 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
643 return extract_with_( dest.guard(), key, pred );
646 /// Finds the key \p val
647 /** @anchor cds_intrusive_EllenBinTree_find_val
648 The function searches the item with key equal to \p val
649 and returns \p true if it is found, and \p false otherwise.
651 Note the hash functor specified for class \p Traits template parameter
652 should accept a parameter of type \p Q that can be not the same as \p value_type.
654 template <typename Q>
655 bool find( Q const& val ) const
658 if ( search( res, val, node_compare() )) {
659 m_Stat.onFindSuccess();
663 m_Stat.onFindFailed();
667 /// Finds the key \p val with comparing functor \p pred
669 The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
670 but \p pred is used for key compare.
671 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
672 "Predicate requirements".
673 \p pred must imply the same element order as the comparator used for building the tree.
674 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
676 template <typename Q, typename Less>
677 bool find_with( Q const& val, Less pred ) const
679 typedef ellen_bintree::details::compare<
682 opt::details::make_comparator_from_less<Less>,
687 if ( search( res, val, compare_functor() )) {
688 m_Stat.onFindSuccess();
691 m_Stat.onFindFailed();
695 /// Finds the key \p val
696 /** @anchor cds_intrusive_EllenBinTree_find_func
697 The function searches the item with key equal to \p val and calls the functor \p f for item found.
698 The interface of \p Func functor is:
701 void operator()( value_type& item, Q& val );
704 where \p item is the item found, \p val is the <tt>find</tt> function argument.
706 You can pass \p f argument by value or by reference using \p std::ref.
708 The functor can change non-key fields of \p item. Note that the functor is only guarantee
709 that \p item cannot be disposed during functor is executing.
710 The functor does not serialize simultaneous access to the tree \p item. If such access is
711 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
713 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
714 can modify both arguments.
716 The function returns \p true if \p val is found, \p false otherwise.
718 template <typename Q, typename Func>
719 bool find( Q& val, Func f ) const
721 return find_( val, f );
724 /// Finds the key \p val with comparing functor \p pred
726 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
727 but \p pred is used for key comparison.
728 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
729 "Predicate requirements".
730 \p pred must imply the same element order as the comparator used for building the tree.
732 template <typename Q, typename Less, typename Func>
733 bool find_with( Q& val, Less pred, Func f ) const
735 return find_with_( val, pred, f );
738 /// Finds the key \p val
739 /** @anchor cds_intrusive_EllenBinTree_find_cfunc
740 The function searches the item with key equal to \p val and calls the functor \p f for item found.
741 The interface of \p Func functor is:
744 void operator()( value_type& item, Q const& val );
747 where \p item is the item found, \p val is the <tt>find</tt> function argument.
749 You can pass \p f argument by value or by reference using \p std::ref.
751 The functor can change non-key fields of \p item. Note that the functor is only guarantee
752 that \p item cannot be disposed during functor is executing.
753 The functor does not serialize simultaneous access to the tree \p item. If such access is
754 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
756 The function returns \p true if \p val is found, \p false otherwise.
758 template <typename Q, typename Func>
759 bool find( Q const& val, Func f ) const
761 return find_( val, f );
764 /// Finds the key \p val with comparing functor \p pred
766 The function is an analog of \ref cds_intrusive_EllenBinTree_find_cfunc "find(Q const&, Func)"
767 but \p pred is used for key compare.
768 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
769 "Predicate requirements".
770 \p pred must imply the same element order as the comparator used for building the tree.
772 template <typename Q, typename Less, typename Func>
773 bool find_with( Q const& val, Less pred, Func f ) const
775 return find_with_( val, pred, f );
778 /// Finds \p key and returns the item found
779 /** @anchor cds_intrusive_EllenBinTree_get
780 The function searches the item with key equal to \p key and returns the item found in \p dest parameter.
781 The function returns \p true if \p key is found, \p false otherwise.
783 The guarded pointer \p dest prevents disposer invocation for returned item,
784 see cds::gc::guarded_ptr for explanation.
785 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
787 template <typename Q>
788 bool get( guarded_ptr& dest, Q const& key ) const
790 return get_( dest.guard(), key );
793 /// Finds \p key with predicate \p pred and returns the item found
795 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(guarded_ptr&, Q const&)"
796 but \p pred is used for key comparing.
797 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
798 "Predicate requirements".
799 \p pred must imply the same element order as the comparator used for building the tree.
801 template <typename Q, typename Less>
802 bool get_with( guarded_ptr& dest, Q const& key, Less pred ) const
804 return get_with_( dest.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, non-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 \ref disposer will be called after unlinking.
829 while ( extract_min(gp));
832 /// Clears the tree (not thread safe)
834 This function is not thread safe and may be called only when no other thread deals with the tree.
835 The function is used in the tree destructor.
840 internal_node * pParent = nullptr;
841 internal_node * pGrandParent = nullptr;
842 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
845 while ( pLeaf->is_internal() ) {
846 pGrandParent = pParent;
847 pParent = static_cast<internal_node *>( pLeaf );
848 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
851 if ( pLeaf->infinite_key()) {
856 // Remove leftmost leaf and its parent node
857 assert( pGrandParent );
859 assert( pLeaf->is_leaf() );
861 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
862 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
863 free_internal_node( pParent );
867 /// Returns item count in the tree
869 Only leaf nodes containing user data are counted.
871 The value returned depends on item counter type provided by \p Traits template parameter.
872 If it is atomicity::empty_item_counter this function always returns 0.
873 Therefore, the function is not suitable for checking the tree emptiness, use \ref empty
874 member function for this purpose.
878 return m_ItemCounter;
881 /// Returns const reference to internal statistics
882 stat const& statistics() const
887 /// Checks internal consistency (not atomic, not thread-safe)
889 The debugging function to check internal consistency of the tree.
891 bool check_consistency() const
893 return check_consistency( &m_Root );
899 bool check_consistency( internal_node const * pRoot ) const
901 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
902 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
906 if ( node_compare()( *pLeft, *pRoot ) < 0
907 && node_compare()( *pRoot, *pRight ) <= 0
908 && node_compare()( *pLeft, *pRight ) < 0 )
911 if ( pLeft->is_internal() )
912 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
915 if ( bRet && pRight->is_internal() )
916 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
924 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
927 tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
930 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
931 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
932 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
935 // child node is guarded
936 // See whether pParent->m_pUpdate has not been changed
937 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
938 // update has been changed - returns nullptr as a flag to search retry
942 if ( p && p->is_leaf() )
943 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
944 res.guards.clear( search_result::Guard_helpLeaf );
948 update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src ) const
951 update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
954 res.guards.assign( search_result::Guard_updParent, upd );
955 } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
959 template <typename KeyValue, typename Compare>
960 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
962 internal_node * pParent;
963 internal_node * pGrandParent = nullptr;
964 update_ptr updParent;
965 update_ptr updGrandParent;
967 bool bRightParent = false;
973 //pGrandParent = nullptr;
976 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
977 while ( pLeaf->is_internal() ) {
978 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
979 pGrandParent = pParent;
980 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
981 pParent = static_cast<internal_node *>( pLeaf );
982 bRightParent = bRightLeaf;
983 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
984 updGrandParent = updParent;
986 updParent = search_protect_update( res, pParent->m_pUpdate );
988 switch ( updParent.bits() ) {
989 case update_desc::DFlag:
990 case update_desc::Mark:
991 m_Stat.onSearchRetry();
995 nCmp = cmp( key, *pParent );
996 bRightLeaf = nCmp >= 0;
998 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1000 m_Stat.onSearchRetry();
1005 assert( pLeaf->is_leaf() );
1006 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1008 res.pGrandParent = pGrandParent;
1009 res.pParent = pParent;
1010 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1011 res.updParent = updParent;
1012 res.updGrandParent = updGrandParent;
1013 res.bRightParent = bRightParent;
1014 res.bRightLeaf = bRightLeaf;
1019 bool search_min( search_result& res ) const
1021 internal_node * pParent;
1022 internal_node * pGrandParent;
1023 update_ptr updParent;
1024 update_ptr updGrandParent;
1028 pGrandParent = nullptr;
1029 updParent = nullptr;
1030 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1031 while ( pLeaf->is_internal() ) {
1032 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1033 pGrandParent = pParent;
1034 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1035 pParent = static_cast<internal_node *>( pLeaf );
1036 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1037 updGrandParent = updParent;
1039 updParent = search_protect_update( res, pParent->m_pUpdate );
1041 switch ( updParent.bits() ) {
1042 case update_desc::DFlag:
1043 case update_desc::Mark:
1044 m_Stat.onSearchRetry();
1048 pLeaf = protect_child_node( res, pParent, false, updParent );
1050 m_Stat.onSearchRetry();
1055 if ( pLeaf->infinite_key())
1058 res.pGrandParent = pGrandParent;
1059 res.pParent = pParent;
1060 assert( pLeaf->is_leaf() );
1061 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1062 res.updParent = updParent;
1063 res.updGrandParent = updGrandParent;
1064 res.bRightParent = false;
1065 res.bRightLeaf = false;
1070 bool search_max( search_result& res ) const
1072 internal_node * pParent;
1073 internal_node * pGrandParent;
1074 update_ptr updParent;
1075 update_ptr updGrandParent;
1077 bool bRightParent = false;
1081 pGrandParent = nullptr;
1082 updParent = nullptr;
1084 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1085 while ( pLeaf->is_internal() ) {
1086 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1087 pGrandParent = pParent;
1088 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1089 pParent = static_cast<internal_node *>( pLeaf );
1090 bRightParent = bRightLeaf;
1091 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1092 updGrandParent = updParent;
1094 updParent = search_protect_update( res, pParent->m_pUpdate );
1096 switch ( updParent.bits() ) {
1097 case update_desc::DFlag:
1098 case update_desc::Mark:
1099 m_Stat.onSearchRetry();
1103 bRightLeaf = !pParent->infinite_key();
1104 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1106 m_Stat.onSearchRetry();
1111 if ( pLeaf->infinite_key())
1114 res.pGrandParent = pGrandParent;
1115 res.pParent = pParent;
1116 assert( pLeaf->is_leaf() );
1117 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1118 res.updParent = updParent;
1119 res.updGrandParent = updGrandParent;
1120 res.bRightParent = bRightParent;
1121 res.bRightLeaf = bRightLeaf;
1126 void help( update_ptr pUpdate )
1128 // pUpdate must be guarded!
1129 switch ( pUpdate.bits() ) {
1130 case update_desc::IFlag:
1131 help_insert( pUpdate.ptr() );
1132 m_Stat.onHelpInsert();
1134 case update_desc::DFlag:
1135 help_delete( pUpdate.ptr() );
1136 m_Stat.onHelpDelete();
1138 case update_desc::Mark:
1139 //m_Stat.onHelpMark();
1140 //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_relaxed, 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_relaxed, 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 );
1172 static_cast<internal_node *>(
1174 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1175 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1178 static_cast<leaf_node *>(
1180 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1181 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
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 tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1221 typename gc::Guard guardLeaf;
1223 tree_node * pSibling;
1224 tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1227 guard.assign( static_cast<internal_node *>(p) );
1228 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1229 } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1231 if ( pSibling->is_leaf() )
1232 guard.copy( guardLeaf );
1237 void help_marked( update_desc * pOp )
1239 // precondition: pOp must be guarded
1241 tree_node * pParent = pOp->dInfo.pParent;
1243 typename gc::Guard guard;
1244 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1246 if ( pOp->dInfo.bRightParent ) {
1247 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1248 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1251 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1252 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1255 update_ptr upd( pOp, update_desc::DFlag );
1256 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1257 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1260 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1262 assert( res.updParent.bits() == update_desc::Clean );
1263 assert( res.pLeaf->is_leaf() );
1265 // check search result
1266 if ( ( res.bRightLeaf
1267 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1268 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire ) ) == res.pLeaf )
1270 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1272 int nCmp = node_compare()( val, *res.pLeaf );
1274 if ( res.pGrandParent ) {
1275 assert( !res.pLeaf->infinite_key() );
1276 pNewInternal->infinite_key( 0 );
1277 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1280 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1281 pNewInternal->infinite_key( 1 );
1283 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1284 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1287 assert( !res.pLeaf->is_internal() );
1288 pNewInternal->infinite_key( 0 );
1290 key_extractor()( pNewInternal->m_Key, val );
1291 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1292 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1293 assert( !res.pLeaf->infinite_key());
1296 typename gc::Guard guard;
1297 update_desc * pOp = alloc_update_desc();
1298 guard.assign( pOp );
1300 pOp->iInfo.pParent = res.pParent;
1301 pOp->iInfo.pNew = pNewInternal;
1302 pOp->iInfo.pLeaf = res.pLeaf;
1303 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1305 update_ptr updCur( res.updParent.ptr() );
1306 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1307 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1311 retire_update_desc( pOp );
1315 m_Stat.onUpdateDescDeleted();
1316 free_update_desc( pOp );
1322 template <typename Q, typename Compare, typename Equal, typename Func>
1323 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1325 update_desc * pOp = nullptr;
1329 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1331 retire_update_desc( pOp );
1332 m_Stat.onEraseFailed();
1336 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1338 pOp = alloc_update_desc();
1339 if ( check_delete_precondition( res ) ) {
1340 typename gc::Guard guard;
1341 guard.assign( pOp );
1343 pOp->dInfo.pGrandParent = res.pGrandParent;
1344 pOp->dInfo.pParent = res.pParent;
1345 pOp->dInfo.pLeaf = res.pLeaf;
1346 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1347 pOp->dInfo.bRightParent = res.bRightParent;
1348 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1350 update_ptr updGP( res.updGrandParent.ptr() );
1351 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1352 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1354 if ( help_delete( pOp )) {
1355 // res.pLeaf is not deleted yet since it is guarded
1356 f( *node_traits::to_value_ptr( res.pLeaf ));
1364 m_Stat.onEraseRetry();
1368 m_Stat.onEraseSuccess();
1372 template <typename Q>
1373 bool extract_( typename gc::Guard& guard, Q const& key )
1375 return erase_( key, node_compare(),
1376 []( Q const&, leaf_node const& ) -> bool { return true; },
1377 [&guard]( value_type& found ) { guard.assign( &found ); } );
1380 template <typename Q, typename Less>
1381 bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
1383 typedef ellen_bintree::details::compare<
1386 opt::details::make_comparator_from_less<Less>,
1390 return erase_( key, compare_functor(),
1391 []( Q const&, leaf_node const& ) -> bool { return true; },
1392 [&guard]( value_type& found ) { guard.assign( &found ); } );
1395 bool extract_max_( typename gc::Guard& guard )
1397 update_desc * pOp = nullptr;
1401 if ( !search_max( res )) {
1404 retire_update_desc( pOp );
1405 m_Stat.onExtractMaxFailed();
1409 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1411 pOp = alloc_update_desc();
1412 if ( check_delete_precondition( res ) ) {
1413 typename gc::Guard guard;
1414 guard.assign( pOp );
1416 pOp->dInfo.pGrandParent = res.pGrandParent;
1417 pOp->dInfo.pParent = res.pParent;
1418 pOp->dInfo.pLeaf = res.pLeaf;
1419 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1420 pOp->dInfo.bRightParent = res.bRightParent;
1421 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1423 update_ptr updGP( res.updGrandParent.ptr() );
1424 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1425 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1427 if ( help_delete( pOp ))
1434 m_Stat.onExtractMaxRetry();
1438 m_Stat.onExtractMaxSuccess();
1439 guard.assign( node_traits::to_value_ptr( res.pLeaf ) );
1443 bool extract_min_( typename gc::Guard& guard )
1445 update_desc * pOp = nullptr;
1449 if ( !search_min( res )) {
1452 retire_update_desc( pOp );
1453 m_Stat.onExtractMinFailed();
1457 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1459 pOp = alloc_update_desc();
1460 if ( check_delete_precondition( res ) ) {
1461 typename gc::Guard guard;
1462 guard.assign( pOp );
1464 pOp->dInfo.pGrandParent = res.pGrandParent;
1465 pOp->dInfo.pParent = res.pParent;
1466 pOp->dInfo.pLeaf = res.pLeaf;
1467 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1468 pOp->dInfo.bRightParent = res.bRightParent;
1469 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1471 update_ptr updGP( res.updGrandParent.ptr() );
1472 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1473 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1475 if ( help_delete( pOp ))
1482 m_Stat.onExtractMinRetry();
1486 m_Stat.onExtractMinSuccess();
1487 guard.assign( node_traits::to_value_ptr( res.pLeaf ));
1491 template <typename Q, typename Func>
1492 bool find_( Q& val, Func f ) const
1495 if ( search( res, val, node_compare() )) {
1496 assert( res.pLeaf );
1497 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1499 m_Stat.onFindSuccess();
1503 m_Stat.onFindFailed();
1507 template <typename Q, typename Less, typename Func>
1508 bool find_with_( Q& val, Less pred, Func f ) const
1510 typedef ellen_bintree::details::compare<
1513 opt::details::make_comparator_from_less<Less>,
1518 if ( search( res, val, compare_functor() )) {
1519 assert( res.pLeaf );
1520 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1522 m_Stat.onFindSuccess();
1526 m_Stat.onFindFailed();
1530 template <typename Q>
1531 bool get_( typename gc::Guard& guard, Q const& val ) const
1533 return find_( val, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1536 template <typename Q, typename Less>
1537 bool get_with_( typename gc::Guard& guard, Q const& val, Less pred ) const
1539 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1545 }} // namespace cds::intrusive
1547 #endif // #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H