3 #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_IMPL_H
4 #define __CDS_INTRUSIVE_ELLEN_BINTREE_IMPL_H
6 #include <cds/intrusive/details/ellen_bintree_base.h>
7 #include <cds/opt/compare.h>
9 #include <cds/details/binary_functor_wrapper.h>
10 #include <cds/urcu/details/check_deadlock.h>
11 #include <cds/details/std/memory.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/ellen_bintree_impl.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 );
322 # ifndef CDS_CXX11_LAMBDA_SUPPORT
323 struct trivial_equal_functor {
324 template <typename Q>
325 bool operator()( Q const& , leaf_node const& ) const
331 struct empty_insert_functor {
332 void operator()( value_type& )
336 struct assign_guard_functor {
337 typename gc::Guard& m_guard;
338 assign_guard_functor( typename gc::Guard& guard )
342 template <typename Q>
343 void operator()( value_type& val, Q& )
345 m_guard.assign( &val );
348 void operator()( value_type& val )
350 m_guard.assign( &val );
356 # if !defined(CDS_CXX11_LAMBDA_SUPPORT) || (CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
357 struct unlink_equal_functor {
358 bool operator()( value_type const& v, leaf_node const& n ) const
360 return &v == node_traits::to_value_ptr( n );
363 struct empty_erase_functor {
364 void operator()( value_type const& )
371 /// Default constructor
374 static_assert( (!std::is_same< key_extractor, opt::none >::value), "The key extractor option must be specified" );
386 The function inserts \p val in the tree if it does not contain
387 an item with key equal to \p val.
389 Returns \p true if \p val is placed into the tree, \p false otherwise.
391 bool insert( value_type& val )
393 # ifdef CDS_CXX11_LAMBDA_SUPPORT
394 return insert( val, []( value_type& ) {} );
396 return insert( val, empty_insert_functor() );
402 This function is intended for derived non-intrusive containers.
404 The function allows to split creating of new item into two part:
405 - create item with key only
406 - insert new item into the tree
407 - if inserting is success, calls \p f functor to initialize value-field of \p val.
409 The functor signature is:
411 void func( value_type& val );
413 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
414 \p val no any other changes could be made on this tree's item by concurrent threads.
415 The user-defined functor is called only if the inserting is success and may be passed by reference
416 using <tt>boost::ref</tt>
418 template <typename Func>
419 bool insert( value_type& val, Func f )
421 typename gc::Guard guardInsert;
422 guardInsert.assign( &val );
424 unique_internal_node_ptr pNewInternal;
428 if ( search( res, val, node_compare() )) {
429 if ( pNewInternal.get() )
430 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
431 m_Stat.onInsertFailed();
435 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
437 if ( !pNewInternal.get() )
438 pNewInternal.reset( alloc_internal_node() );
440 if ( try_insert( val, pNewInternal.get(), res )) {
441 cds::unref(f)( val );
442 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
447 m_Stat.onInsertRetry();
451 m_Stat.onInsertSuccess();
455 /// Ensures that the \p val exists in the tree
457 The operation performs inserting or changing data with lock-free manner.
459 If the item \p val is not found in the tree, then \p val is inserted into the tree.
460 Otherwise, the functor \p func is called with item found.
461 The functor signature is:
463 void func( bool bNew, value_type& item, value_type& val );
466 - \p bNew - \p true if the item has been inserted, \p false otherwise
467 - \p item - item of the tree
468 - \p val - argument \p val passed into the \p ensure function
469 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
470 refer to the same thing.
472 The functor can change non-key fields of the \p item; however, \p func must guarantee
473 that during changing no any other modifications could be made on this item by concurrent threads.
475 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
477 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
478 \p second is \p true if new item has been added or \p false if the item with \p key
479 already is in the tree.
481 template <typename Func>
482 std::pair<bool, bool> ensure( value_type& val, Func func )
484 typename gc::Guard guardInsert;
485 guardInsert.assign( &val );
487 unique_internal_node_ptr pNewInternal;
491 if ( search( res, val, node_compare() )) {
492 cds::unref(func)( false, *node_traits::to_value_ptr( res.pLeaf ), val );
493 if ( pNewInternal.get() )
494 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
495 m_Stat.onEnsureExist();
496 return std::make_pair( true, false );
499 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
501 if ( !pNewInternal.get() )
502 pNewInternal.reset( alloc_internal_node() );
504 if ( try_insert( val, pNewInternal.get(), res )) {
505 cds::unref(func)( true, val, val );
506 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
510 m_Stat.onEnsureRetry();
514 m_Stat.onEnsureNew();
515 return std::make_pair( true, true );
518 /// Unlinks the item \p val from the tree
520 The function searches the item \p val in the tree and unlink it from the tree
521 if it is found and is equal to \p val.
523 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
524 and deletes the item found. \p unlink finds an item by key and deletes it
525 only if \p val is an item of the tree, i.e. the pointer to item found
526 is equal to <tt> &val </tt>.
528 The \ref disposer specified in \p Traits class template parameter is called
529 by garbage collector \p GC asynchronously.
531 The function returns \p true if success and \p false otherwise.
533 bool unlink( value_type& val )
535 # if defined(CDS_CXX11_LAMBDA_SUPPORT) && !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
536 // vc10 generates an error for the lambda - it sees cds::intrusive::node_traits but not class-defined node_traits
537 return erase_( val, node_compare(),
538 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
539 [](value_type const&) {} );
541 return erase_( val, node_compare(), unlink_equal_functor(), empty_erase_functor() );
545 /// Deletes the item from the tree
546 /** \anchor cds_intrusive_EllenBinTree_erase
547 The function searches an item with key equal to \p val in the tree,
548 unlinks it from the tree, and returns \p true.
549 If the item with key equal to \p val is not found the function return \p false.
551 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
553 template <typename Q>
554 bool erase( const Q& val )
556 # ifdef CDS_CXX11_LAMBDA_SUPPORT
557 return erase_( val, node_compare(),
558 []( Q const&, leaf_node const& ) -> bool { return true; },
559 [](value_type const&) {} );
561 return erase_( val, node_compare(), trivial_equal_functor(), empty_erase_functor() );
565 /// Delete the item from the tree with comparing functor \p pred
567 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
568 but \p pred predicate is used for key comparing.
569 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
570 "Predicate requirements".
571 \p pred must imply the same element order as the comparator used for building the tree.
573 template <typename Q, typename Less>
574 bool erase_with( const Q& val, Less pred )
576 typedef ellen_bintree::details::compare<
579 opt::details::make_comparator_from_less<Less>,
583 # ifdef CDS_CXX11_LAMBDA_SUPPORT
584 return erase_( val, compare_functor(),
585 []( Q const&, leaf_node const& ) -> bool { return true; },
586 [](value_type const&) {} );
588 return erase_( val, compare_functor(), trivial_equal_functor(), empty_erase_functor() );
592 /// Deletes the item from the tree
593 /** \anchor cds_intrusive_EllenBinTree_erase_func
594 The function searches an item with key equal to \p val in the tree,
595 call \p f functor with item found, unlinks it from the tree, and returns \p true.
596 The \ref disposer specified in \p Traits class template parameter is called
597 by garbage collector \p GC asynchronously.
599 The \p Func interface is
602 void operator()( value_type const& item );
605 The functor can be passed by reference with <tt>boost:ref</tt>
607 If the item with key equal to \p val is not found the function return \p false.
609 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
611 template <typename Q, typename Func>
612 bool erase( Q const& val, Func f )
614 # ifdef CDS_CXX11_LAMBDA_SUPPORT
615 return erase_( val, node_compare(),
616 []( Q const&, leaf_node const& ) -> bool { return true; },
619 return erase_( val, node_compare(), trivial_equal_functor(), f );
623 /// Delete the item from the tree with comparing functor \p pred
625 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
626 but \p pred predicate is used for key comparing.
627 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
628 "Predicate requirements".
629 \p pred must imply the same element order as the comparator used for building the tree.
631 template <typename Q, typename Less, typename Func>
632 bool erase_with( Q const& val, Less pred, Func f )
634 typedef ellen_bintree::details::compare<
637 opt::details::make_comparator_from_less<Less>,
641 # ifdef CDS_CXX11_LAMBDA_SUPPORT
642 return erase_( val, compare_functor(),
643 []( Q const&, leaf_node const& ) -> bool { return true; },
646 return erase_( val, compare_functor(), trivial_equal_functor(), f );
650 /// Extracts an item with minimal key from the tree
652 The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p dest parameter.
653 If the tree is empty the function returns \p false.
655 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
656 It means that the function gets leftmost leaf of the tree and tries to unlink it.
657 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
658 So, the function returns the item with minimum key at the moment of tree traversing.
660 The guarded pointer \p dest prevents disposer invocation for returned item,
661 see cds::gc::guarded_ptr for explanation.
662 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
664 bool extract_min( guarded_ptr& dest )
666 return extract_min_( dest.guard());
669 /// Extracts an item with maximal key from the tree
671 The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p dest parameter.
672 If the tree is empty the function returns \p false.
674 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
675 It means that the function gets rightmost leaf of the tree and tries to unlink it.
676 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
677 So, the function returns the item with maximal key at the moment of tree traversing.
679 The guarded pointer \p dest prevents disposer invocation for returned item,
680 see cds::gc::guarded_ptr for explanation.
681 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
683 bool extract_max( guarded_ptr& dest )
685 return extract_max_( dest.guard() );
688 /// Extracts an item from the tree
689 /** \anchor cds_intrusive_EllenBinTree_extract
690 The function searches an item with key equal to \p key in the tree,
691 unlinks it, and returns pointer to an item found in \p dest parameter.
692 If the item is not found the function returns \p false.
694 The guarded pointer \p dest prevents disposer invocation for returned item,
695 see cds::gc::guarded_ptr for explanation.
696 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
698 template <typename Q>
699 bool extract( guarded_ptr& dest, Q const& key )
701 return extract_( dest.guard(), key );
704 /// Extracts an item from the tree using \p pred for searching
706 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(guarded_ptr& dest, Q const&)"
707 but \p pred is used for key compare.
708 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
709 "Predicate requirements".
710 \p pred must imply the same element order as the comparator used for building the tree.
712 template <typename Q, typename Less>
713 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
715 return extract_with_( dest.guard(), key, pred );
718 /// Finds the key \p val
719 /** @anchor cds_intrusive_EllenBinTree_find_val
720 The function searches the item with key equal to \p val
721 and returns \p true if it is found, and \p false otherwise.
723 Note the hash functor specified for class \p Traits template parameter
724 should accept a parameter of type \p Q that can be not the same as \p value_type.
726 template <typename Q>
727 bool find( Q const& val ) const
730 if ( search( res, val, node_compare() )) {
731 m_Stat.onFindSuccess();
735 m_Stat.onFindFailed();
739 /// Finds the key \p val with comparing functor \p pred
741 The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
742 but \p pred is used for key compare.
743 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
744 "Predicate requirements".
745 \p pred must imply the same element order as the comparator used for building the tree.
746 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
748 template <typename Q, typename Less>
749 bool find_with( Q const& val, Less pred ) const
751 typedef ellen_bintree::details::compare<
754 opt::details::make_comparator_from_less<Less>,
759 if ( search( res, val, compare_functor() )) {
760 m_Stat.onFindSuccess();
763 m_Stat.onFindFailed();
767 /// Finds the key \p val
768 /** @anchor cds_intrusive_EllenBinTree_find_func
769 The function searches the item with key equal to \p val and calls the functor \p f for item found.
770 The interface of \p Func functor is:
773 void operator()( value_type& item, Q& val );
776 where \p item is the item found, \p val is the <tt>find</tt> function argument.
778 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
780 The functor can change non-key fields of \p item. Note that the functor is only guarantee
781 that \p item cannot be disposed during functor is executing.
782 The functor does not serialize simultaneous access to the tree \p item. If such access is
783 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
785 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
786 can modify both arguments.
788 The function returns \p true if \p val is found, \p false otherwise.
790 template <typename Q, typename Func>
791 bool find( Q& val, Func f ) const
793 return find_( val, f );
796 /// Finds the key \p val with comparing functor \p pred
798 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
799 but \p pred is used for key comparison.
800 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
801 "Predicate requirements".
802 \p pred must imply the same element order as the comparator used for building the tree.
804 template <typename Q, typename Less, typename Func>
805 bool find_with( Q& val, Less pred, Func f ) const
807 return find_with_( val, pred, f );
810 /// Finds the key \p val
811 /** @anchor cds_intrusive_EllenBinTree_find_cfunc
812 The function searches the item with key equal to \p val and calls the functor \p f for item found.
813 The interface of \p Func functor is:
816 void operator()( value_type& item, Q const& val );
819 where \p item is the item found, \p val is the <tt>find</tt> function argument.
821 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
823 The functor can change non-key fields of \p item. Note that the functor is only guarantee
824 that \p item cannot be disposed during functor is executing.
825 The functor does not serialize simultaneous access to the tree \p item. If such access is
826 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
828 The function returns \p true if \p val is found, \p false otherwise.
830 template <typename Q, typename Func>
831 bool find( Q const& val, Func f ) const
833 return find_( val, f );
836 /// Finds the key \p val with comparing functor \p pred
838 The function is an analog of \ref cds_intrusive_EllenBinTree_find_cfunc "find(Q const&, Func)"
839 but \p pred is used for key compare.
840 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
841 "Predicate requirements".
842 \p pred must imply the same element order as the comparator used for building the tree.
844 template <typename Q, typename Less, typename Func>
845 bool find_with( Q const& val, Less pred, Func f ) const
847 return find_with_( val, pred, f );
850 /// Finds \p key and returns the item found
851 /** @anchor cds_intrusive_EllenBinTree_get
852 The function searches the item with key equal to \p key and returns the item found in \p dest parameter.
853 The function returns \p true if \p key is found, \p false otherwise.
855 The guarded pointer \p dest prevents disposer invocation for returned item,
856 see cds::gc::guarded_ptr for explanation.
857 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
859 template <typename Q>
860 bool get( guarded_ptr& dest, Q const& key ) const
862 return get_( dest.guard(), key );
865 /// Finds \p key with predicate \p pred and returns the item found
867 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(guarded_ptr&, Q const&)"
868 but \p pred is used for key comparing.
869 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
870 "Predicate requirements".
871 \p pred must imply the same element order as the comparator used for building the tree.
873 template <typename Q, typename Less>
874 bool get_with( guarded_ptr& dest, Q const& key, Less pred ) const
876 return get_with_( dest.guard(), key, pred );
879 /// Checks if the tree is empty
882 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
885 /// Clears the tree (thread safe, non-atomic)
887 The function unlink all items from the tree.
888 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
892 assert( tree.empty() );
894 the assertion could be raised.
896 For each leaf the \ref disposer will be called after unlinking.
901 while ( extract_min(gp));
904 /// Clears the tree (not thread safe)
906 This function is not thread safe and may be called only when no other thread deals with the tree.
907 The function is used in the tree destructor.
912 internal_node * pParent = nullptr;
913 internal_node * pGrandParent = nullptr;
914 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
917 while ( pLeaf->is_internal() ) {
918 pGrandParent = pParent;
919 pParent = static_cast<internal_node *>( pLeaf );
920 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
923 if ( pLeaf->infinite_key()) {
928 // Remove leftmost leaf and its parent node
929 assert( pGrandParent );
931 assert( pLeaf->is_leaf() );
933 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
934 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
935 free_internal_node( pParent );
939 /// Returns item count in the tree
941 Only leaf nodes containing user data are counted.
943 The value returned depends on item counter type provided by \p Traits template parameter.
944 If it is atomicity::empty_item_counter this function always returns 0.
945 Therefore, the function is not suitable for checking the tree emptiness, use \ref empty
946 member function for this purpose.
950 return m_ItemCounter;
953 /// Returns const reference to internal statistics
954 stat const& statistics() const
959 /// Checks internal consistency (not atomic, not thread-safe)
961 The debugging function to check internal consistency of the tree.
963 bool check_consistency() const
965 return check_consistency( &m_Root );
971 bool check_consistency( internal_node const * pRoot ) const
973 tree_node * pLeft = pRoot->m_pLeft.load( CDS_ATOMIC::memory_order_relaxed );
974 tree_node * pRight = pRoot->m_pRight.load( CDS_ATOMIC::memory_order_relaxed );
978 if ( node_compare()( *pLeft, *pRoot ) < 0
979 && node_compare()( *pRoot, *pRight ) <= 0
980 && node_compare()( *pLeft, *pRight ) < 0 )
983 if ( pLeft->is_internal() )
984 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
987 if ( bRet && pRight->is_internal() )
988 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
996 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
999 tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1002 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
1003 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
1004 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
1005 } while ( p != pn );
1007 // child node is guarded
1008 // See whether pParent->m_pUpdate has not been changed
1009 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
1010 // update has been changed - returns nullptr as a flag to search retry
1014 if ( p && p->is_leaf() )
1015 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
1016 res.guards.clear( search_result::Guard_helpLeaf );
1020 update_ptr search_protect_update( search_result& res, CDS_ATOMIC::atomic<update_ptr> const& src ) const
1023 update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
1026 res.guards.assign( search_result::Guard_updParent, upd );
1027 } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
1031 template <typename KeyValue, typename Compare>
1032 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1034 internal_node * pParent;
1035 internal_node * pGrandParent = nullptr;
1036 update_ptr updParent;
1037 update_ptr updGrandParent;
1039 bool bRightParent = false;
1045 //pGrandParent = nullptr;
1046 updParent = nullptr;
1048 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1049 while ( pLeaf->is_internal() ) {
1050 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1051 pGrandParent = pParent;
1052 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1053 pParent = static_cast<internal_node *>( pLeaf );
1054 bRightParent = bRightLeaf;
1055 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1056 updGrandParent = updParent;
1058 updParent = search_protect_update( res, pParent->m_pUpdate );
1060 switch ( updParent.bits() ) {
1061 case update_desc::DFlag:
1062 case update_desc::Mark:
1063 m_Stat.onSearchRetry();
1067 nCmp = cmp( key, *pParent );
1068 bRightLeaf = nCmp >= 0;
1070 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1072 m_Stat.onSearchRetry();
1077 assert( pLeaf->is_leaf() );
1078 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1080 res.pGrandParent = pGrandParent;
1081 res.pParent = pParent;
1082 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1083 res.updParent = updParent;
1084 res.updGrandParent = updGrandParent;
1085 res.bRightParent = bRightParent;
1086 res.bRightLeaf = bRightLeaf;
1091 bool search_min( search_result& res ) const
1093 internal_node * pParent;
1094 internal_node * pGrandParent;
1095 update_ptr updParent;
1096 update_ptr updGrandParent;
1100 pGrandParent = nullptr;
1101 updParent = nullptr;
1102 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1103 while ( pLeaf->is_internal() ) {
1104 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1105 pGrandParent = pParent;
1106 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1107 pParent = static_cast<internal_node *>( pLeaf );
1108 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1109 updGrandParent = updParent;
1111 updParent = search_protect_update( res, pParent->m_pUpdate );
1113 switch ( updParent.bits() ) {
1114 case update_desc::DFlag:
1115 case update_desc::Mark:
1116 m_Stat.onSearchRetry();
1120 pLeaf = protect_child_node( res, pParent, false, updParent );
1122 m_Stat.onSearchRetry();
1127 if ( pLeaf->infinite_key())
1130 res.pGrandParent = pGrandParent;
1131 res.pParent = pParent;
1132 assert( pLeaf->is_leaf() );
1133 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1134 res.updParent = updParent;
1135 res.updGrandParent = updGrandParent;
1136 res.bRightParent = false;
1137 res.bRightLeaf = false;
1142 bool search_max( search_result& res ) const
1144 internal_node * pParent;
1145 internal_node * pGrandParent;
1146 update_ptr updParent;
1147 update_ptr updGrandParent;
1149 bool bRightParent = false;
1153 pGrandParent = nullptr;
1154 updParent = nullptr;
1156 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1157 while ( pLeaf->is_internal() ) {
1158 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1159 pGrandParent = pParent;
1160 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1161 pParent = static_cast<internal_node *>( pLeaf );
1162 bRightParent = bRightLeaf;
1163 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1164 updGrandParent = updParent;
1166 updParent = search_protect_update( res, pParent->m_pUpdate );
1168 switch ( updParent.bits() ) {
1169 case update_desc::DFlag:
1170 case update_desc::Mark:
1171 m_Stat.onSearchRetry();
1175 bRightLeaf = !pParent->infinite_key();
1176 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1178 m_Stat.onSearchRetry();
1183 if ( pLeaf->infinite_key())
1186 res.pGrandParent = pGrandParent;
1187 res.pParent = pParent;
1188 assert( pLeaf->is_leaf() );
1189 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1190 res.updParent = updParent;
1191 res.updGrandParent = updGrandParent;
1192 res.bRightParent = bRightParent;
1193 res.bRightLeaf = bRightLeaf;
1198 void help( update_ptr pUpdate )
1200 // pUpdate must be guarded!
1201 switch ( pUpdate.bits() ) {
1202 case update_desc::IFlag:
1203 help_insert( pUpdate.ptr() );
1204 m_Stat.onHelpInsert();
1206 case update_desc::DFlag:
1207 help_delete( pUpdate.ptr() );
1208 m_Stat.onHelpDelete();
1210 case update_desc::Mark:
1211 //m_Stat.onHelpMark();
1212 //help_marked( pUpdate.ptr() );
1217 void help_insert( update_desc * pOp )
1219 // pOp must be guarded
1221 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1222 if ( pOp->iInfo.bRightLeaf ) {
1223 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1224 memory_model::memory_order_relaxed, CDS_ATOMIC::memory_order_relaxed ));
1227 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1228 memory_model::memory_order_relaxed, CDS_ATOMIC::memory_order_relaxed ));
1232 update_ptr cur( pOp, update_desc::IFlag );
1233 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1234 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ));
1237 bool check_delete_precondition( search_result& res ) const
1239 // precondition: all member of res must be guarded
1241 assert( res.pGrandParent != nullptr );
1244 static_cast<internal_node *>(
1246 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1247 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1250 static_cast<leaf_node *>(
1252 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1253 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1257 bool help_delete( update_desc * pOp )
1259 // precondition: pOp must be guarded
1261 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1262 update_ptr pMark( pOp, update_desc::Mark );
1263 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1264 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1268 retire_node( pOp->dInfo.pParent );
1269 retire_node( pOp->dInfo.pLeaf );
1270 retire_update_desc( pOp );
1273 else if ( pUpdate == pMark ) {
1274 // some other thread is processing help_marked()
1276 m_Stat.onHelpMark();
1280 // Undo grandparent dInfo
1281 update_ptr pDel( pOp, update_desc::DFlag );
1282 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1283 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
1285 retire_update_desc( pOp );
1291 tree_node * protect_sibling( typename gc::Guard& guard, CDS_ATOMIC::atomic<tree_node *>& sibling )
1293 typename gc::Guard guardLeaf;
1295 tree_node * pSibling;
1296 tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1299 guard.assign( static_cast<internal_node *>(p) );
1300 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1301 } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1303 if ( pSibling->is_leaf() )
1304 guard.copy( guardLeaf );
1309 void help_marked( update_desc * pOp )
1311 // precondition: pOp must be guarded
1313 tree_node * pParent = pOp->dInfo.pParent;
1315 typename gc::Guard guard;
1316 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1318 if ( pOp->dInfo.bRightParent ) {
1319 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1320 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ));
1323 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1324 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ));
1327 update_ptr upd( pOp, update_desc::DFlag );
1328 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1329 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ));
1332 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1334 assert( res.updParent.bits() == update_desc::Clean );
1335 assert( res.pLeaf->is_leaf() );
1337 // check search result
1338 if ( ( res.bRightLeaf
1339 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1340 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire ) ) == res.pLeaf )
1342 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1344 int nCmp = node_compare()( val, *res.pLeaf );
1346 if ( res.pGrandParent ) {
1347 assert( !res.pLeaf->infinite_key() );
1348 pNewInternal->infinite_key( 0 );
1349 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1352 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1353 pNewInternal->infinite_key( 1 );
1355 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1356 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1359 assert( !res.pLeaf->is_internal() );
1360 pNewInternal->infinite_key( 0 );
1362 key_extractor()( pNewInternal->m_Key, val );
1363 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1364 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1365 assert( !res.pLeaf->infinite_key());
1368 typename gc::Guard guard;
1369 update_desc * pOp = alloc_update_desc();
1370 guard.assign( pOp );
1372 pOp->iInfo.pParent = res.pParent;
1373 pOp->iInfo.pNew = pNewInternal;
1374 pOp->iInfo.pLeaf = res.pLeaf;
1375 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1377 update_ptr updCur( res.updParent.ptr() );
1378 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1379 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1383 retire_update_desc( pOp );
1387 m_Stat.onUpdateDescDeleted();
1388 free_update_desc( pOp );
1394 template <typename Q, typename Compare, typename Equal, typename Func>
1395 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1397 update_desc * pOp = nullptr;
1401 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1403 retire_update_desc( pOp );
1404 m_Stat.onEraseFailed();
1408 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1410 pOp = alloc_update_desc();
1411 if ( check_delete_precondition( res ) ) {
1412 typename gc::Guard guard;
1413 guard.assign( pOp );
1415 pOp->dInfo.pGrandParent = res.pGrandParent;
1416 pOp->dInfo.pParent = res.pParent;
1417 pOp->dInfo.pLeaf = res.pLeaf;
1418 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1419 pOp->dInfo.bRightParent = res.bRightParent;
1420 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1422 update_ptr updGP( res.updGrandParent.ptr() );
1423 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1424 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1426 if ( help_delete( pOp )) {
1427 // res.pLeaf is not deleted yet since it is guarded
1428 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ));
1436 m_Stat.onEraseRetry();
1440 m_Stat.onEraseSuccess();
1444 template <typename Q>
1445 bool extract_( typename gc::Guard& guard, Q const& key )
1447 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1448 return erase_( key, node_compare(),
1449 []( Q const&, leaf_node const& ) -> bool { return true; },
1450 [&guard]( value_type& found ) { guard.assign( &found ); } );
1452 assign_guard_functor f( guard );
1453 return erase_( key, node_compare(), trivial_equal_functor(), cds::ref(f) );
1457 template <typename Q, typename Less>
1458 bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
1460 typedef ellen_bintree::details::compare<
1463 opt::details::make_comparator_from_less<Less>,
1467 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1468 return erase_( key, compare_functor(),
1469 []( Q const&, leaf_node const& ) -> bool { return true; },
1470 [&guard]( value_type& found ) { guard.assign( &found ); } );
1472 assign_guard_functor f( guard );
1473 return erase_( key, compare_functor(), trivial_equal_functor(), cds::ref(f) );
1477 bool extract_max_( typename gc::Guard& guard )
1479 update_desc * pOp = nullptr;
1483 if ( !search_max( res )) {
1486 retire_update_desc( pOp );
1487 m_Stat.onExtractMaxFailed();
1491 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1493 pOp = alloc_update_desc();
1494 if ( check_delete_precondition( res ) ) {
1495 typename gc::Guard guard;
1496 guard.assign( pOp );
1498 pOp->dInfo.pGrandParent = res.pGrandParent;
1499 pOp->dInfo.pParent = res.pParent;
1500 pOp->dInfo.pLeaf = res.pLeaf;
1501 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1502 pOp->dInfo.bRightParent = res.bRightParent;
1503 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1505 update_ptr updGP( res.updGrandParent.ptr() );
1506 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1507 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1509 if ( help_delete( pOp ))
1516 m_Stat.onExtractMaxRetry();
1520 m_Stat.onExtractMaxSuccess();
1521 guard.assign( node_traits::to_value_ptr( res.pLeaf ) );
1525 bool extract_min_( typename gc::Guard& guard )
1527 update_desc * pOp = nullptr;
1531 if ( !search_min( res )) {
1534 retire_update_desc( pOp );
1535 m_Stat.onExtractMinFailed();
1539 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1541 pOp = alloc_update_desc();
1542 if ( check_delete_precondition( res ) ) {
1543 typename gc::Guard guard;
1544 guard.assign( pOp );
1546 pOp->dInfo.pGrandParent = res.pGrandParent;
1547 pOp->dInfo.pParent = res.pParent;
1548 pOp->dInfo.pLeaf = res.pLeaf;
1549 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1550 pOp->dInfo.bRightParent = res.bRightParent;
1551 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1553 update_ptr updGP( res.updGrandParent.ptr() );
1554 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1555 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1557 if ( help_delete( pOp ))
1564 m_Stat.onExtractMinRetry();
1568 m_Stat.onExtractMinSuccess();
1569 guard.assign( node_traits::to_value_ptr( res.pLeaf ));
1573 template <typename Q, typename Func>
1574 bool find_( Q& val, Func f ) const
1577 if ( search( res, val, node_compare() )) {
1578 assert( res.pLeaf );
1579 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), val );
1581 m_Stat.onFindSuccess();
1585 m_Stat.onFindFailed();
1589 template <typename Q, typename Less, typename Func>
1590 bool find_with_( Q& val, Less pred, Func f ) const
1592 typedef ellen_bintree::details::compare<
1595 opt::details::make_comparator_from_less<Less>,
1600 if ( search( res, val, compare_functor() )) {
1601 assert( res.pLeaf );
1602 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), val );
1604 m_Stat.onFindSuccess();
1608 m_Stat.onFindFailed();
1612 template <typename Q>
1613 bool get_( typename gc::Guard& guard, Q const& val ) const
1615 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1616 return find_( val, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1618 assign_guard_functor f(guard);
1619 return find_( val, cds::ref(f) );
1623 template <typename Q, typename Less>
1624 bool get_with_( typename gc::Guard& guard, Q const& val, Less pred ) const
1626 # ifdef CDS_CXX11_LAMBDA_SUPPORT
1627 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1629 assign_guard_functor f(guard);
1630 return find_with_( val, pred, cds::ref(f) );
1637 }} // namespace cds::intrusive
1639 #endif // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_IMPL_H