3 #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
4 #define __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
7 #include <cds/intrusive/details/ellen_bintree_base.h>
8 #include <cds/opt/compare.h>
9 #include <cds/details/binary_functor_wrapper.h>
10 #include <cds/urcu/details/check_deadlock.h>
11 #include <cds/gc/guarded_ptr.h>
13 namespace cds { namespace intrusive {
15 /// Ellen's et al binary search tree
16 /** @ingroup cds_intrusive_map
17 @ingroup cds_intrusive_tree
18 @anchor cds_intrusive_EllenBinTree
21 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
23 %EllenBinTree is an <i>unbalanced</i> leaf-oriented binary search tree that implements the <i>set</i>
24 abstract data type. Nodes maintains child pointers but not parent pointers.
25 Every internal node has exactly two children, and all data of type \p T currently in
26 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find()
27 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
28 may or may not be in the set. \p Key type is a subset of \p T type.
29 There should be exactly defined a key extracting functor for converting object of type \p T to
30 object of type \p Key.
32 Due to \p extract_min() and \p extract_max() member functions the \p %EllenBinTree can act as
33 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
34 the priority value plus some uniformly distributed random value.
36 @note In the current implementation we do not use helping technique described in the original paper.
37 In Hazard Pointer schema helping is too complicated and does not give any observable benefits.
38 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
39 the operation done. Such solution allows greatly simplify the implementation of tree.
41 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
42 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
44 @note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
45 There are header file for each GC type:
46 - <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC \p cds::gc::HP
47 - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Pass-the-Buck GC \p cds::gc::DHP
48 - <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
50 <b>Template arguments</b> :
51 - \p GC - garbage collector, possible types are cds::gc::HP, cds::gc::DHP.
52 - \p Key - key type, a subset of \p T
53 - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
54 (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
55 (for \p ellen_bintree::member_hook).
56 - \p Traits - tree traits, default is \p ellen_bintree::traits
57 It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
58 instead of \p Traits template argument.
60 @anchor cds_intrusive_EllenBinTree_less
61 <b>Predicate requirements</b>
63 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
64 of type \p T and \p Key in any combination.
65 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
67 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
74 bool operator()( Foo const& v1, Foo const& v2 ) const
75 { return v1.m_strKey < v2.m_strKey ; }
77 bool operator()( Foo const& v, std::string const& s ) const
78 { return v.m_strKey < s ; }
80 bool operator()( std::string const& s, Foo const& v ) const
81 { return s < v.m_strKey ; }
83 // Support comparing std::string and char const *
84 bool operator()( std::string const& s, char const * p ) const
85 { return s.compare(p) < 0 ; }
87 bool operator()( Foo const& v, char const * p ) const
88 { return v.m_strKey.compare(p) < 0 ; }
90 bool operator()( char const * p, std::string const& s ) const
91 { return s.compare(p) > 0; }
93 bool operator()( char const * p, Foo const& v ) const
94 { return v.m_strKey.compare(p) > 0; }
98 Usage examples see \ref cds_intrusive_EllenBinTree_usage "here"
103 #ifdef CDS_DOXYGEN_INVOKED
104 class Traits = ellen_bintree::traits
112 typedef GC gc; ///< Garbage collector
113 typedef Key key_type; ///< type of a key to be stored in internal nodes; key is a part of \p value_type
114 typedef T value_type; ///< type of value stored in the binary tree
115 typedef Traits traits; ///< Traits template parameter
117 typedef typename traits::hook hook; ///< hook type
118 typedef typename hook::node_type node_type; ///< node type
119 typedef typename traits::disposer disposer; ///< leaf node disposer
120 typedef typename traits::back_off back_off; ///< back-off strategy
122 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
126 typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
127 typedef node_type leaf_node; ///< Leaf node type
128 typedef ellen_bintree::node_types< gc, key_type, typename leaf_node::tag > node_factory;
129 typedef typename node_factory::internal_node_type internal_node; ///< Internal node type
130 typedef typename node_factory::update_desc_type update_desc; ///< Update descriptor
131 typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
135 # ifdef CDS_DOXYGEN_INVOKED
136 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
137 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
139 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
140 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
142 static internal_node const& to_internal_node( tree_node const& n )
144 assert( n.is_internal() );
145 return static_cast<internal_node const&>( n );
148 static leaf_node const& to_leaf_node( tree_node const& n )
150 assert( n.is_leaf() );
151 return static_cast<leaf_node const&>( n );
156 typedef typename traits::item_counter item_counter; ///< Item counting policy
157 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model
158 typedef typename traits::stat stat; ///< internal statistics type
159 typedef typename traits::key_extractor key_extractor; ///< key extracting functor
161 typedef typename traits::node_allocator node_allocator; ///< Allocator for internal node
162 typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
166 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
168 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
169 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
171 struct search_result {
176 Guard_updGrandParent,
182 // end of guard indices
186 typedef typename gc::template GuardArray< guard_count > guard_array;
189 internal_node * pGrandParent;
190 internal_node * pParent;
192 update_ptr updParent;
193 update_ptr updGrandParent;
194 bool bRightLeaf; // true if pLeaf is right child of pParent, false otherwise
195 bool bRightParent; // true if pParent is right child of pGrandParent, false otherwise
198 :pGrandParent( nullptr )
202 ,bRightParent( false )
205 void clean_help_guards()
207 guards.clear( Guard_helpLeaf );
214 internal_node m_Root; ///< Tree root node (key= Infinite2)
215 leaf_node m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
216 leaf_node m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
219 item_counter m_ItemCounter; ///< item counter
220 mutable stat m_Stat; ///< internal statistics
224 static void free_leaf_node( value_type * p )
229 internal_node * alloc_internal_node() const
231 m_Stat.onInternalNodeCreated();
232 internal_node * pNode = cxx_node_allocator().New();
236 static void free_internal_node( internal_node * pNode )
238 cxx_node_allocator().Delete( pNode );
241 struct internal_node_deleter {
242 void operator()( internal_node * p) const
244 free_internal_node( p );
248 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
250 update_desc * alloc_update_desc() const
252 m_Stat.onUpdateDescCreated();
253 return cxx_update_desc_allocator().New();
256 static void free_update_desc( update_desc * pDesc )
258 cxx_update_desc_allocator().Delete( pDesc );
261 void retire_node( tree_node * pNode ) const
263 if ( pNode->is_leaf() ) {
264 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
265 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
267 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
270 assert( static_cast<internal_node *>( pNode ) != &m_Root );
271 m_Stat.onInternalNodeDeleted();
273 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
277 void retire_update_desc( update_desc * p ) const
279 m_Stat.onUpdateDescDeleted();
280 gc::template retire( p, free_update_desc );
283 void make_empty_tree()
285 m_Root.infinite_key( 2 );
286 m_LeafInf1.infinite_key( 1 );
287 m_LeafInf2.infinite_key( 2 );
288 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
289 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
294 /// Default constructor
297 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
309 The function inserts \p val in the tree if it does not contain
310 an item with key equal to \p val.
312 Returns \p true if \p val is placed into the tree, \p false otherwise.
314 bool insert( value_type& val )
316 return insert( val, []( value_type& ) {} );
321 This function is intended for derived non-intrusive containers.
323 The function allows to split creating of new item into two part:
324 - create item with key only
325 - insert new item into the tree
326 - if inserting is success, calls \p f functor to initialize value-field of \p val.
328 The functor signature is:
330 void func( value_type& val );
332 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
333 \p val no any other changes could be made on this tree's item by concurrent threads.
334 The user-defined functor is called only if the inserting is success.
336 template <typename Func>
337 bool insert( value_type& val, Func f )
339 typename gc::Guard guardInsert;
340 guardInsert.assign( &val );
342 unique_internal_node_ptr pNewInternal;
347 if ( search( res, val, node_compare() )) {
348 if ( pNewInternal.get() )
349 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
350 m_Stat.onInsertFailed();
354 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
356 if ( !pNewInternal.get() )
357 pNewInternal.reset( alloc_internal_node() );
359 if ( try_insert( val, pNewInternal.get(), res )) {
361 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
367 m_Stat.onInsertRetry();
371 m_Stat.onInsertSuccess();
375 /// Ensures that the \p val exists in the tree
377 The operation performs inserting or changing data with lock-free manner.
379 If the item \p val is not found in the tree, then \p val is inserted into the tree.
380 Otherwise, the functor \p func is called with item found.
381 The functor signature is:
383 void func( bool bNew, value_type& item, value_type& val );
386 - \p bNew - \p true if the item has been inserted, \p false otherwise
387 - \p item - an item of the tree
388 - \p val - the argument \p val passed to the \p ensure function
389 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
390 refer to the same thing.
392 The functor can change non-key fields of the \p item; however, \p func must guarantee
393 that during changing no any other modifications could be made on this item by concurrent threads.
395 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
396 \p second is \p true if new item has been added or \p false if the item with \p key
397 already is in the tree.
399 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
401 template <typename Func>
402 std::pair<bool, bool> ensure( value_type& val, Func func )
404 typename gc::Guard guardInsert;
405 guardInsert.assign( &val );
407 unique_internal_node_ptr pNewInternal;
412 if ( search( res, val, node_compare() )) {
413 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
414 if ( pNewInternal.get() )
415 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
416 m_Stat.onEnsureExist();
417 return std::make_pair( true, false );
420 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
422 if ( !pNewInternal.get() )
423 pNewInternal.reset( alloc_internal_node() );
425 if ( try_insert( val, pNewInternal.get(), res )) {
426 func( true, val, val );
427 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
433 m_Stat.onEnsureRetry();
437 m_Stat.onEnsureNew();
438 return std::make_pair( true, true );
441 /// Unlinks the item \p val from the tree
443 The function searches the item \p val in the tree and unlink it from the tree
444 if it is found and is equal to \p val.
446 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
447 and deletes the item found. \p unlink finds an item by key and deletes it
448 only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
450 The \p disposer specified in \p Traits class template parameter is called
451 by garbage collector \p GC asynchronously.
453 The function returns \p true if success and \p false otherwise.
455 bool unlink( value_type& val )
457 return erase_( val, node_compare(),
458 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
459 [](value_type const&) {} );
462 /// Deletes the item from the tree
463 /** \anchor cds_intrusive_EllenBinTree_erase
464 The function searches an item with key equal to \p key in the tree,
465 unlinks it from the tree, and returns \p true.
466 If the item with key equal to \p key is not found the function return \p false.
468 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
470 template <typename Q>
471 bool erase( const Q& key )
473 return erase_( key, node_compare(),
474 []( Q const&, leaf_node const& ) -> bool { return true; },
475 [](value_type const&) {} );
478 /// Delete the item from the tree with comparing functor \p pred
480 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
481 but \p pred predicate is used for key comparing.
482 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
483 "Predicate requirements".
484 \p pred must imply the same element order as the comparator used for building the tree.
486 template <typename Q, typename Less>
487 bool erase_with( const Q& key, Less pred )
489 typedef ellen_bintree::details::compare<
492 opt::details::make_comparator_from_less<Less>,
496 return erase_( key, compare_functor(),
497 []( Q const&, leaf_node const& ) -> bool { return true; },
498 [](value_type const&) {} );
501 /// Deletes the item from the tree
502 /** \anchor cds_intrusive_EllenBinTree_erase_func
503 The function searches an item with key equal to \p key in the tree,
504 call \p f functor with item found, unlinks it from the tree, and returns \p true.
505 The \ref disposer specified in \p Traits class template parameter is called
506 by garbage collector \p GC asynchronously.
508 The \p Func interface is
511 void operator()( value_type const& item );
515 If the item with key equal to \p key is not found the function return \p false.
517 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
519 template <typename Q, typename Func>
520 bool erase( Q const& key, Func f )
522 return erase_( key, node_compare(),
523 []( Q const&, leaf_node const& ) -> bool { return true; },
527 /// Delete the item from the tree with comparing functor \p pred
529 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
530 but \p pred predicate is used for key comparing.
531 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
532 "Predicate requirements".
533 \p pred must imply the same element order as the comparator used for building the tree.
535 template <typename Q, typename Less, typename Func>
536 bool erase_with( Q const& key, Less pred, Func f )
538 typedef ellen_bintree::details::compare<
541 opt::details::make_comparator_from_less<Less>,
545 return erase_( key, compare_functor(),
546 []( Q const&, leaf_node const& ) -> bool { return true; },
550 /// Extracts an item with minimal key from the tree
552 The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p dest parameter.
553 If the tree is empty the function returns \p false.
555 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
556 It means that the function gets leftmost leaf of the tree and tries to unlink it.
557 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
558 So, the function returns the item with minimum key at the moment of tree traversing.
560 The guarded pointer \p dest prevents disposer invocation for returned item,
561 see cds::gc::guarded_ptr for explanation.
562 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
564 bool extract_min( guarded_ptr& dest )
566 return extract_min_( dest.guard());
569 /// Extracts an item with maximal key from the tree
571 The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p dest parameter.
572 If the tree is empty the function returns \p false.
574 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
575 It means that the function gets rightmost leaf of the tree and tries to unlink it.
576 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
577 So, the function returns the item with maximal key at the moment of tree traversing.
579 The guarded pointer \p dest prevents disposer invocation for returned item,
580 see cds::gc::guarded_ptr for explanation.
581 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
583 bool extract_max( guarded_ptr& dest )
585 return extract_max_( dest.guard() );
588 /// Extracts an item from the tree
589 /** \anchor cds_intrusive_EllenBinTree_extract
590 The function searches an item with key equal to \p key in the tree,
591 unlinks it, and returns pointer to an item found in \p dest parameter.
592 If the item is not found the function returns \p false.
594 The guarded pointer \p dest prevents disposer invocation for returned item,
595 see cds::gc::guarded_ptr for explanation.
596 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
598 template <typename Q>
599 bool extract( guarded_ptr& dest, Q const& key )
601 return extract_( dest.guard(), key );
604 /// Extracts an item from the tree using \p pred for searching
606 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(guarded_ptr& dest, Q const&)"
607 but \p pred is used for key compare.
608 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
609 "Predicate requirements".
610 \p pred must imply the same element order as the comparator used for building the tree.
612 template <typename Q, typename Less>
613 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
615 return extract_with_( dest.guard(), key, pred );
618 /// Finds the key \p key
619 /** @anchor cds_intrusive_EllenBinTree_find_val
620 The function searches the item with key equal to \p key
621 and returns \p true if it is found, and \p false otherwise.
623 Note the hash functor specified for class \p Traits template parameter
624 should accept a parameter of type \p Q that can be not the same as \p value_type.
626 template <typename Q>
627 bool find( Q const& key ) const
630 if ( search( res, key, node_compare() )) {
631 m_Stat.onFindSuccess();
635 m_Stat.onFindFailed();
639 /// Finds the key \p key with comparing functor \p pred
641 The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
642 but \p pred is used for key compare.
643 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
644 "Predicate requirements".
645 \p pred must imply the same element order as the comparator used for building the tree.
646 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
648 template <typename Q, typename Less>
649 bool find_with( Q const& key, Less pred ) const
651 typedef ellen_bintree::details::compare<
654 opt::details::make_comparator_from_less<Less>,
659 if ( search( res, key, compare_functor() )) {
660 m_Stat.onFindSuccess();
663 m_Stat.onFindFailed();
667 /// Finds the key \p key
668 /** @anchor cds_intrusive_EllenBinTree_find_func
669 The function searches the item with key equal to \p key and calls the functor \p f for item found.
670 The interface of \p Func functor is:
673 void operator()( value_type& item, Q& key );
676 where \p item is the item found, \p key is the <tt>find</tt> function argument.
678 The functor can change non-key fields of \p item. Note that the functor is only guarantee
679 that \p item cannot be disposed during functor is executing.
680 The functor does not serialize simultaneous access to the tree \p item. If such access is
681 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
683 The function returns \p true if \p key is found, \p false otherwise.
685 template <typename Q, typename Func>
686 bool find( Q& key, Func f ) const
688 return find_( key, f );
691 template <typename Q, typename Func>
692 bool find( Q const& key, Func f ) const
694 return find_( key, f );
698 /// Finds the key \p key with comparing functor \p pred
700 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
701 but \p pred is used for key comparison.
702 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
703 "Predicate requirements".
704 \p pred must imply the same element order as the comparator used for building the tree.
706 template <typename Q, typename Less, typename Func>
707 bool find_with( Q& key, Less pred, Func f ) const
709 return find_with_( key, pred, f );
712 template <typename Q, typename Less, typename Func>
713 bool find_with( Q const& key, Less pred, Func f ) const
715 return find_with_( key, pred, f );
719 /// Finds \p key and returns the item found
720 /** @anchor cds_intrusive_EllenBinTree_get
721 The function searches the item with key equal to \p key and returns the item found in \p dest parameter.
722 The function returns \p true if \p key is found, \p false otherwise.
724 The guarded pointer \p dest prevents disposer invocation for returned item,
725 see cds::gc::guarded_ptr for explanation.
726 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
728 template <typename Q>
729 bool get( guarded_ptr& dest, Q const& key ) const
731 return get_( dest.guard(), key );
734 /// Finds \p key with predicate \p pred and returns the item found
736 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(guarded_ptr&, Q const&)"
737 but \p pred is used for key comparing.
738 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
739 "Predicate requirements".
740 \p pred must imply the same element order as the comparator used for building the tree.
742 template <typename Q, typename Less>
743 bool get_with( guarded_ptr& dest, Q const& key, Less pred ) const
745 return get_with_( dest.guard(), key, pred );
748 /// Checks if the tree is empty
751 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
754 /// Clears the tree (thread safe, not atomic)
756 The function unlink all items from the tree.
757 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
761 assert( tree.empty() );
763 the assertion could be raised.
765 For each leaf the \p disposer will be called after unlinking.
770 while ( extract_min(gp));
773 /// Clears the tree (not thread safe)
775 This function is not thread safe and may be called only when no other thread deals with the tree.
776 The function is used in the tree destructor.
781 internal_node * pParent = nullptr;
782 internal_node * pGrandParent = nullptr;
783 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
786 while ( pLeaf->is_internal() ) {
787 pGrandParent = pParent;
788 pParent = static_cast<internal_node *>( pLeaf );
789 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
792 if ( pLeaf->infinite_key()) {
797 // Remove leftmost leaf and its parent node
798 assert( pGrandParent );
800 assert( pLeaf->is_leaf() );
802 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
803 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
804 free_internal_node( pParent );
808 /// Returns item count in the tree
810 Only leaf nodes containing user data are counted.
812 The value returned depends on item counter type provided by \p Traits template parameter.
813 If it is \p atomicity::empty_item_counter this function always returns 0.
814 The function is not suitable for checking the tree emptiness, use \p empty()
815 member function for this purpose.
819 return m_ItemCounter;
822 /// Returns const reference to internal statistics
823 stat const& statistics() const
828 /// Checks internal consistency (not atomic, not thread-safe)
830 The debugging function to check internal consistency of the tree.
832 bool check_consistency() const
834 return check_consistency( &m_Root );
840 bool check_consistency( internal_node const * pRoot ) const
842 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
843 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
847 if ( node_compare()( *pLeft, *pRoot ) < 0
848 && node_compare()( *pRoot, *pRight ) <= 0
849 && node_compare()( *pLeft, *pRight ) < 0 )
852 if ( pLeft->is_internal() )
853 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
856 if ( bRet && pRight->is_internal() )
857 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
865 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
868 tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
871 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
872 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
873 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
876 // child node is guarded
877 // See whether pParent->m_pUpdate has not been changed
878 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
879 // update has been changed - returns nullptr as a flag to search retry
883 if ( p && p->is_leaf() )
884 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
885 res.guards.clear( search_result::Guard_helpLeaf );
889 update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src ) const
892 update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
895 res.guards.assign( search_result::Guard_updParent, upd );
896 } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
900 template <typename KeyValue, typename Compare>
901 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
903 internal_node * pParent;
904 internal_node * pGrandParent = nullptr;
905 update_ptr updParent;
906 update_ptr updGrandParent;
908 bool bRightParent = false;
914 //pGrandParent = nullptr;
917 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
918 while ( pLeaf->is_internal() ) {
919 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
920 pGrandParent = pParent;
921 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
922 pParent = static_cast<internal_node *>( pLeaf );
923 bRightParent = bRightLeaf;
924 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
925 updGrandParent = updParent;
927 updParent = search_protect_update( res, pParent->m_pUpdate );
929 switch ( updParent.bits() ) {
930 case update_desc::DFlag:
931 case update_desc::Mark:
932 m_Stat.onSearchRetry();
936 nCmp = cmp( key, *pParent );
937 bRightLeaf = nCmp >= 0;
939 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
941 m_Stat.onSearchRetry();
946 assert( pLeaf->is_leaf() );
947 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
949 res.pGrandParent = pGrandParent;
950 res.pParent = pParent;
951 res.pLeaf = static_cast<leaf_node *>( pLeaf );
952 res.updParent = updParent;
953 res.updGrandParent = updGrandParent;
954 res.bRightParent = bRightParent;
955 res.bRightLeaf = bRightLeaf;
960 bool search_min( search_result& res ) const
962 internal_node * pParent;
963 internal_node * pGrandParent;
964 update_ptr updParent;
965 update_ptr updGrandParent;
969 pGrandParent = nullptr;
971 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
972 while ( pLeaf->is_internal() ) {
973 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
974 pGrandParent = pParent;
975 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
976 pParent = static_cast<internal_node *>( pLeaf );
977 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
978 updGrandParent = updParent;
980 updParent = search_protect_update( res, pParent->m_pUpdate );
982 switch ( updParent.bits() ) {
983 case update_desc::DFlag:
984 case update_desc::Mark:
985 m_Stat.onSearchRetry();
989 pLeaf = protect_child_node( res, pParent, false, updParent );
991 m_Stat.onSearchRetry();
996 if ( pLeaf->infinite_key())
999 res.pGrandParent = pGrandParent;
1000 res.pParent = pParent;
1001 assert( pLeaf->is_leaf() );
1002 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1003 res.updParent = updParent;
1004 res.updGrandParent = updGrandParent;
1005 res.bRightParent = false;
1006 res.bRightLeaf = false;
1011 bool search_max( search_result& res ) const
1013 internal_node * pParent;
1014 internal_node * pGrandParent;
1015 update_ptr updParent;
1016 update_ptr updGrandParent;
1018 bool bRightParent = false;
1022 pGrandParent = nullptr;
1023 updParent = nullptr;
1025 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1026 while ( pLeaf->is_internal() ) {
1027 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1028 pGrandParent = pParent;
1029 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1030 pParent = static_cast<internal_node *>( pLeaf );
1031 bRightParent = bRightLeaf;
1032 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1033 updGrandParent = updParent;
1035 updParent = search_protect_update( res, pParent->m_pUpdate );
1037 switch ( updParent.bits() ) {
1038 case update_desc::DFlag:
1039 case update_desc::Mark:
1040 m_Stat.onSearchRetry();
1044 bRightLeaf = !pParent->infinite_key();
1045 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1047 m_Stat.onSearchRetry();
1052 if ( pLeaf->infinite_key())
1055 res.pGrandParent = pGrandParent;
1056 res.pParent = pParent;
1057 assert( pLeaf->is_leaf() );
1058 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1059 res.updParent = updParent;
1060 res.updGrandParent = updGrandParent;
1061 res.bRightParent = bRightParent;
1062 res.bRightLeaf = bRightLeaf;
1068 void help( update_ptr pUpdate )
1070 // pUpdate must be guarded!
1071 switch ( pUpdate.bits() ) {
1072 case update_desc::IFlag:
1073 help_insert( pUpdate.ptr() );
1074 m_Stat.onHelpInsert();
1076 case update_desc::DFlag:
1077 help_delete( pUpdate.ptr() );
1078 m_Stat.onHelpDelete();
1080 case update_desc::Mark:
1081 //m_Stat.onHelpMark();
1082 //help_marked( pUpdate.ptr() );
1088 void help_insert( update_desc * pOp )
1090 // pOp must be guarded
1092 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1093 if ( pOp->iInfo.bRightLeaf ) {
1094 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1095 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1098 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1099 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1103 update_ptr cur( pOp, update_desc::IFlag );
1104 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1105 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1108 bool check_delete_precondition( search_result& res ) const
1110 // precondition: all member of res must be guarded
1112 assert( res.pGrandParent != nullptr );
1115 static_cast<internal_node *>(
1117 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1118 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1121 static_cast<leaf_node *>(
1123 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1124 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1128 bool help_delete( update_desc * pOp )
1130 // precondition: pOp must be guarded
1132 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1133 update_ptr pMark( pOp, update_desc::Mark );
1134 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1135 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1139 retire_node( pOp->dInfo.pParent );
1140 retire_node( pOp->dInfo.pLeaf );
1141 retire_update_desc( pOp );
1144 else if ( pUpdate == pMark ) {
1145 // some other thread is processing help_marked()
1147 m_Stat.onHelpMark();
1151 // Undo grandparent dInfo
1152 update_ptr pDel( pOp, update_desc::DFlag );
1153 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1154 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1156 retire_update_desc( pOp );
1162 tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1164 typename gc::Guard guardLeaf;
1166 tree_node * pSibling;
1167 tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1170 guard.assign( static_cast<internal_node *>(p) );
1171 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1172 } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1174 if ( pSibling->is_leaf() )
1175 guard.copy( guardLeaf );
1180 void help_marked( update_desc * pOp )
1182 // precondition: pOp must be guarded
1184 tree_node * pParent = pOp->dInfo.pParent;
1186 typename gc::Guard guard;
1187 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1189 if ( pOp->dInfo.bRightParent ) {
1190 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1191 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1194 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1195 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1198 update_ptr upd( pOp, update_desc::DFlag );
1199 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1200 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1203 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1205 assert( res.updParent.bits() == update_desc::Clean );
1206 assert( res.pLeaf->is_leaf() );
1208 // check search result
1209 if ( (res.bRightLeaf
1210 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1211 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire )) == res.pLeaf ) {
1212 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1214 int nCmp = node_compare()(val, *res.pLeaf);
1216 if ( res.pGrandParent ) {
1217 assert( !res.pLeaf->infinite_key() );
1218 pNewInternal->infinite_key( 0 );
1219 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1222 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1223 pNewInternal->infinite_key( 1 );
1225 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1226 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1229 assert( !res.pLeaf->is_internal() );
1230 pNewInternal->infinite_key( 0 );
1232 key_extractor()(pNewInternal->m_Key, val);
1233 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1234 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1235 assert( !res.pLeaf->infinite_key() );
1238 typename gc::Guard guard;
1239 update_desc * pOp = alloc_update_desc();
1240 guard.assign( pOp );
1242 pOp->iInfo.pParent = res.pParent;
1243 pOp->iInfo.pNew = pNewInternal;
1244 pOp->iInfo.pLeaf = res.pLeaf;
1245 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1247 update_ptr updCur( res.updParent.ptr() );
1248 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1249 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1252 retire_update_desc( pOp );
1256 m_Stat.onUpdateDescDeleted();
1257 free_update_desc( pOp );
1264 template <typename Q, typename Compare, typename Equal, typename Func>
1265 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1267 update_desc * pOp = nullptr;
1272 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1274 retire_update_desc( pOp );
1275 m_Stat.onEraseFailed();
1279 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1281 pOp = alloc_update_desc();
1282 if ( check_delete_precondition( res ) ) {
1283 typename gc::Guard guard;
1284 guard.assign( pOp );
1286 pOp->dInfo.pGrandParent = res.pGrandParent;
1287 pOp->dInfo.pParent = res.pParent;
1288 pOp->dInfo.pLeaf = res.pLeaf;
1289 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1290 pOp->dInfo.bRightParent = res.bRightParent;
1291 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1293 update_ptr updGP( res.updGrandParent.ptr() );
1294 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1295 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1296 if ( help_delete( pOp ) ) {
1297 // res.pLeaf is not deleted yet since it is guarded
1298 f( *node_traits::to_value_ptr( res.pLeaf ) );
1307 m_Stat.onEraseRetry();
1311 m_Stat.onEraseSuccess();
1315 template <typename Q>
1316 bool extract_( typename gc::Guard& guard, Q const& key )
1318 return erase_( key, node_compare(),
1319 []( Q const&, leaf_node const& ) -> bool { return true; },
1320 [&guard]( value_type& found ) { guard.assign( &found ); } );
1323 template <typename Q, typename Less>
1324 bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
1326 typedef ellen_bintree::details::compare<
1329 opt::details::make_comparator_from_less<Less>,
1333 return erase_( key, compare_functor(),
1334 []( Q const&, leaf_node const& ) -> bool { return true; },
1335 [&guard]( value_type& found ) { guard.assign( &found ); } );
1338 bool extract_max_( typename gc::Guard& guard )
1340 update_desc * pOp = nullptr;
1345 if ( !search_max( res )) {
1348 retire_update_desc( pOp );
1349 m_Stat.onExtractMaxFailed();
1353 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1355 pOp = alloc_update_desc();
1356 if ( check_delete_precondition( res ) ) {
1357 typename gc::Guard guard;
1358 guard.assign( pOp );
1360 pOp->dInfo.pGrandParent = res.pGrandParent;
1361 pOp->dInfo.pParent = res.pParent;
1362 pOp->dInfo.pLeaf = res.pLeaf;
1363 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1364 pOp->dInfo.bRightParent = res.bRightParent;
1365 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1367 update_ptr updGP( res.updGrandParent.ptr() );
1368 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1369 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1371 if ( help_delete( pOp ) )
1379 m_Stat.onExtractMaxRetry();
1383 m_Stat.onExtractMaxSuccess();
1384 guard.assign( node_traits::to_value_ptr( res.pLeaf ) );
1388 bool extract_min_( typename gc::Guard& guard )
1390 update_desc * pOp = nullptr;
1395 if ( !search_min( res )) {
1398 retire_update_desc( pOp );
1399 m_Stat.onExtractMinFailed();
1403 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1405 pOp = alloc_update_desc();
1406 if ( check_delete_precondition( res ) ) {
1407 typename gc::Guard guard;
1408 guard.assign( pOp );
1410 pOp->dInfo.pGrandParent = res.pGrandParent;
1411 pOp->dInfo.pParent = res.pParent;
1412 pOp->dInfo.pLeaf = res.pLeaf;
1413 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1414 pOp->dInfo.bRightParent = res.bRightParent;
1415 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1417 update_ptr updGP( res.updGrandParent.ptr() );
1418 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1419 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1421 if ( help_delete( pOp ))
1429 m_Stat.onExtractMinRetry();
1433 m_Stat.onExtractMinSuccess();
1434 guard.assign( node_traits::to_value_ptr( res.pLeaf ));
1438 template <typename Q, typename Func>
1439 bool find_( Q& val, Func f ) const
1442 if ( search( res, val, node_compare() )) {
1443 assert( res.pLeaf );
1444 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1446 m_Stat.onFindSuccess();
1450 m_Stat.onFindFailed();
1454 template <typename Q, typename Less, typename Func>
1455 bool find_with_( Q& val, Less pred, Func f ) const
1457 typedef ellen_bintree::details::compare<
1460 opt::details::make_comparator_from_less<Less>,
1465 if ( search( res, val, compare_functor() )) {
1466 assert( res.pLeaf );
1467 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1469 m_Stat.onFindSuccess();
1473 m_Stat.onFindFailed();
1477 template <typename Q>
1478 bool get_( typename gc::Guard& guard, Q const& val ) const
1480 return find_( val, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1483 template <typename Q, typename Less>
1484 bool get_with_( typename gc::Guard& guard, Q const& val, Less pred ) const
1486 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1492 }} // namespace cds::intrusive
1494 #endif // #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H