3 #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H
4 #define CDSLIB_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>
12 namespace cds { namespace intrusive {
14 /// Ellen's et al binary search tree
15 /** @ingroup cds_intrusive_map
16 @ingroup cds_intrusive_tree
17 @anchor cds_intrusive_EllenBinTree
20 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
22 %EllenBinTree is an <i>unbalanced</i> leaf-oriented binary search tree that implements the <i>set</i>
23 abstract data type. Nodes maintains child pointers but not parent pointers.
24 Every internal node has exactly two children, and all data of type \p T currently in
25 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find()
26 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
27 may or may not be in the set. \p Key type is a subset of \p T type.
28 There should be exactly defined a key extracting functor for converting object of type \p T to
29 object of type \p Key.
31 Due to \p extract_min() and \p extract_max() member functions the \p %EllenBinTree can act as
32 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
33 the priority value plus some uniformly distributed random value.
35 @note In the current implementation we do not use helping technique described in the original paper.
36 In Hazard Pointer schema helping is too complicated and does not give any observable benefits.
37 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
38 the operation done. Such solution allows greatly simplify the implementation of tree.
40 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
41 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
43 @note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
44 There are header file for each GC type:
45 - <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC \p cds::gc::HP
46 - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Dynamic Hazard Pointer GC \p cds::gc::DHP
47 - <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
49 <b>Template arguments</b> :
50 - \p GC - garbage collector, possible types are cds::gc::HP, cds::gc::DHP.
51 - \p Key - key type, a subset of \p T
52 - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
53 (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
54 (for \p ellen_bintree::member_hook).
55 - \p Traits - tree traits, default is \p ellen_bintree::traits
56 It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
57 instead of \p Traits template argument.
59 @anchor cds_intrusive_EllenBinTree_less
60 <b>Predicate requirements</b>
62 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
63 of type \p T and \p Key in any combination.
64 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
66 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
73 bool operator()( Foo const& v1, Foo const& v2 ) const
74 { return v1.m_strKey < v2.m_strKey ; }
76 bool operator()( Foo const& v, std::string const& s ) const
77 { return v.m_strKey < s ; }
79 bool operator()( std::string const& s, Foo const& v ) const
80 { return s < v.m_strKey ; }
82 // Support comparing std::string and char const *
83 bool operator()( std::string const& s, char const * p ) const
84 { return s.compare(p) < 0 ; }
86 bool operator()( Foo const& v, char const * p ) const
87 { return v.m_strKey.compare(p) < 0 ; }
89 bool operator()( char const * p, std::string const& s ) const
90 { return s.compare(p) > 0; }
92 bool operator()( char const * p, Foo const& v ) const
93 { return v.m_strKey.compare(p) > 0; }
97 Usage examples see \ref cds_intrusive_EllenBinTree_usage "here"
102 #ifdef CDS_DOXYGEN_INVOKED
103 class Traits = ellen_bintree::traits
111 typedef GC gc; ///< Garbage collector
112 typedef Key key_type; ///< type of a key to be stored in internal nodes; key is a part of \p value_type
113 typedef T value_type; ///< type of value stored in the binary tree
114 typedef Traits traits; ///< Traits template parameter
116 typedef typename traits::hook hook; ///< hook type
117 typedef typename hook::node_type node_type; ///< node type
118 typedef typename traits::disposer disposer; ///< leaf node disposer
119 typedef typename traits::back_off back_off; ///< back-off strategy
121 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
124 typedef cds::intrusive::ellen_bintree::implementation_tag implementation_tag;
129 typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
130 typedef node_type leaf_node; ///< Leaf node type
131 typedef ellen_bintree::node_types< gc, key_type, typename leaf_node::tag > node_factory;
132 typedef typename node_factory::internal_node_type internal_node; ///< Internal node type
133 typedef typename node_factory::update_desc_type update_desc; ///< Update descriptor
134 typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
138 # ifdef CDS_DOXYGEN_INVOKED
139 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
140 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
142 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
143 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
145 static internal_node const& to_internal_node( tree_node const& n )
147 assert( n.is_internal() );
148 return static_cast<internal_node const&>( n );
151 static leaf_node const& to_leaf_node( tree_node const& n )
153 assert( n.is_leaf() );
154 return static_cast<leaf_node const&>( n );
159 typedef typename traits::item_counter item_counter; ///< Item counting policy
160 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model
161 typedef typename traits::stat stat; ///< internal statistics type
162 typedef typename traits::key_extractor key_extractor; ///< key extracting functor
164 typedef typename traits::node_allocator node_allocator; ///< Allocator for internal node
165 typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
167 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 8; ///< Count of hazard pointer required for the algorithm
171 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
173 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
174 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
176 struct search_result {
181 Guard_updGrandParent,
184 // end of guard indices
188 typedef typename gc::template GuardArray< guard_count > guard_array;
191 internal_node * pGrandParent;
192 internal_node * pParent;
194 update_ptr updParent;
195 update_ptr updGrandParent;
196 bool bRightLeaf; // true if pLeaf is right child of pParent, false otherwise
197 bool bRightParent; // true if pParent is right child of pGrandParent, false otherwise
200 :pGrandParent( nullptr )
204 ,bRightParent( false )
211 internal_node m_Root; ///< Tree root node (key= Infinite2)
212 leaf_node m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
213 leaf_node m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
216 item_counter m_ItemCounter; ///< item counter
217 mutable stat m_Stat; ///< internal statistics
221 static void free_leaf_node( value_type * p )
226 internal_node * alloc_internal_node() const
228 m_Stat.onInternalNodeCreated();
229 internal_node * pNode = cxx_node_allocator().New();
233 static void free_internal_node( internal_node * pNode )
235 cxx_node_allocator().Delete( pNode );
238 struct internal_node_deleter {
239 void operator()( internal_node * p) const
241 free_internal_node( p );
245 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
247 update_desc * alloc_update_desc() const
249 m_Stat.onUpdateDescCreated();
250 return cxx_update_desc_allocator().New();
253 static void free_update_desc( update_desc * pDesc )
255 cxx_update_desc_allocator().Delete( pDesc );
258 void retire_node( tree_node * pNode ) const
260 if ( pNode->is_leaf() ) {
261 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
262 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
264 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
267 assert( static_cast<internal_node *>( pNode ) != &m_Root );
268 m_Stat.onInternalNodeDeleted();
270 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
274 void retire_update_desc( update_desc * p ) const
276 m_Stat.onUpdateDescDeleted();
277 gc::template retire( p, free_update_desc );
280 void make_empty_tree()
282 m_Root.infinite_key( 2 );
283 m_LeafInf1.infinite_key( 1 );
284 m_LeafInf2.infinite_key( 2 );
285 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
286 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
291 /// Default constructor
294 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
306 The function inserts \p val in the tree if it does not contain
307 an item with key equal to \p val.
309 Returns \p true if \p val is placed into the tree, \p false otherwise.
311 bool insert( value_type& val )
313 return insert( val, []( value_type& ) {} );
318 This function is intended for derived non-intrusive containers.
320 The function allows to split creating of new item into two part:
321 - create item with key only
322 - insert new item into the tree
323 - if inserting is success, calls \p f functor to initialize value-field of \p val.
325 The functor signature is:
327 void func( value_type& val );
329 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
330 \p val no any other changes could be made on this tree's item by concurrent threads.
331 The user-defined functor is called only if the inserting is success.
333 template <typename Func>
334 bool insert( value_type& val, Func f )
336 typename gc::Guard guardInsert;
337 guardInsert.assign( &val );
339 unique_internal_node_ptr pNewInternal;
344 if ( search( res, val, node_compare() )) {
345 if ( pNewInternal.get() )
346 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
347 m_Stat.onInsertFailed();
351 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
353 if ( !pNewInternal.get() )
354 pNewInternal.reset( alloc_internal_node() );
356 if ( try_insert( val, pNewInternal.get(), res )) {
358 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
364 m_Stat.onInsertRetry();
368 m_Stat.onInsertSuccess();
372 /// Ensures that the \p val exists in the tree
374 The operation performs inserting or changing data with lock-free manner.
376 If the item \p val is not found in the tree, then \p val is inserted into the tree.
377 Otherwise, the functor \p func is called with item found.
378 The functor signature is:
380 void func( bool bNew, value_type& item, value_type& val );
383 - \p bNew - \p true if the item has been inserted, \p false otherwise
384 - \p item - an item of the tree
385 - \p val - the argument \p val passed to the \p ensure function
386 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
387 refer to the same thing.
389 The functor can change non-key fields of the \p item; however, \p func must guarantee
390 that during changing no any other modifications could be made on this item by concurrent threads.
392 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
393 \p second is \p true if new item has been added or \p false if the item with \p key
394 already is in the tree.
396 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
398 template <typename Func>
399 std::pair<bool, bool> ensure( value_type& val, Func func )
401 typename gc::Guard guardInsert;
402 guardInsert.assign( &val );
404 unique_internal_node_ptr pNewInternal;
409 if ( search( res, val, node_compare() )) {
410 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
411 if ( pNewInternal.get() )
412 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
413 m_Stat.onEnsureExist();
414 return std::make_pair( true, false );
417 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
419 if ( !pNewInternal.get() )
420 pNewInternal.reset( alloc_internal_node() );
422 if ( try_insert( val, pNewInternal.get(), res )) {
423 func( true, val, val );
424 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
430 m_Stat.onEnsureRetry();
434 m_Stat.onEnsureNew();
435 return std::make_pair( true, true );
438 /// Unlinks the item \p val from the tree
440 The function searches the item \p val in the tree and unlink it from the tree
441 if it is found and is equal to \p val.
443 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
444 and deletes the item found. \p unlink finds an item by key and deletes it
445 only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
447 The \p disposer specified in \p Traits class template parameter is called
448 by garbage collector \p GC asynchronously.
450 The function returns \p true if success and \p false otherwise.
452 bool unlink( value_type& val )
454 return erase_( val, node_compare(),
455 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
456 [](value_type const&) {} );
459 /// Deletes the item from the tree
460 /** \anchor cds_intrusive_EllenBinTree_erase
461 The function searches an item with key equal to \p key in the tree,
462 unlinks it from the tree, and returns \p true.
463 If the item with key equal to \p key is not found the function return \p false.
465 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
467 template <typename Q>
468 bool erase( const Q& key )
470 return erase_( key, node_compare(),
471 []( Q const&, leaf_node const& ) -> bool { return true; },
472 [](value_type const&) {} );
475 /// Delete the item from the tree with comparing functor \p pred
477 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
478 but \p pred predicate is used for key comparing.
479 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
480 "Predicate requirements".
481 \p pred must imply the same element order as the comparator used for building the tree.
483 template <typename Q, typename Less>
484 bool erase_with( const Q& key, Less pred )
487 typedef ellen_bintree::details::compare<
490 opt::details::make_comparator_from_less<Less>,
494 return erase_( key, compare_functor(),
495 []( Q const&, leaf_node const& ) -> bool { return true; },
496 [](value_type const&) {} );
499 /// Deletes the item from the tree
500 /** \anchor cds_intrusive_EllenBinTree_erase_func
501 The function searches an item with key equal to \p key in the tree,
502 call \p f functor with item found, unlinks it from the tree, and returns \p true.
503 The \ref disposer specified in \p Traits class template parameter is called
504 by garbage collector \p GC asynchronously.
506 The \p Func interface is
509 void operator()( value_type const& item );
513 If the item with key equal to \p key is not found the function return \p false.
515 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
517 template <typename Q, typename Func>
518 bool erase( Q const& key, Func f )
520 return erase_( key, node_compare(),
521 []( Q const&, leaf_node const& ) -> bool { return true; },
525 /// Delete the item from the tree with comparing functor \p pred
527 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
528 but \p pred predicate is used for key comparing.
529 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
530 "Predicate requirements".
531 \p pred must imply the same element order as the comparator used for building the tree.
533 template <typename Q, typename Less, typename Func>
534 bool erase_with( Q const& key, Less pred, Func f )
537 typedef ellen_bintree::details::compare<
540 opt::details::make_comparator_from_less<Less>,
544 return erase_( key, compare_functor(),
545 []( Q const&, leaf_node const& ) -> bool { return true; },
549 /// Extracts an item with minimal key from the tree
551 The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
552 If the tree is empty the function returns an empty guarded pointer.
554 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
555 It means that the function gets leftmost leaf of the tree and tries to unlink it.
556 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
557 So, the function returns the item with minimum key at the moment of tree traversing.
559 The returned \p guarded_ptr prevents disposer invocation for returned item,
560 see \p cds::gc::guarded_ptr for explanation.
561 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
563 guarded_ptr extract_min()
566 extract_min_( gp.guard() );
570 /// Extracts an item with maximal key from the tree
572 The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
573 If the tree is empty the function returns an empty \p guarded_ptr.
575 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
576 It means that the function gets rightmost leaf of the tree and tries to unlink it.
577 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
578 So, the function returns the item with maximal key at the moment of tree traversing.
580 The returned \p guarded_ptr prevents disposer invocation for returned item,
581 see cds::gc::guarded_ptr for explanation.
582 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
584 guarded_ptr extract_max()
587 extract_max_( gp.guard());
591 /// Extracts an item from the tree
592 /** \anchor cds_intrusive_EllenBinTree_extract
593 The function searches an item with key equal to \p key in the tree,
594 unlinks it, and returns a guarded pointer to an item found.
595 If the item is not found the function returns an empty \p guarded_ptr.
597 \p guarded_ptr prevents disposer invocation for returned item,
598 see cds::gc::guarded_ptr for explanation.
599 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
601 template <typename Q>
602 guarded_ptr extract( Q const& key )
605 extract_( gp.guard(), key );
609 /// Extracts an item from the tree using \p pred for searching
611 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
612 but \p pred is used for key compare.
613 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
614 "Predicate requirements".
615 \p pred must imply the same element order as the comparator used for building the tree.
617 template <typename Q, typename Less>
618 guarded_ptr extract_with( Q const& key, Less pred )
621 extract_with_( gp.guard(), key, pred );
625 /// Finds the key \p key
626 /** @anchor cds_intrusive_EllenBinTree_find_val
627 The function searches the item with key equal to \p key
628 and returns \p true if it is found, and \p false otherwise.
630 Note the hash functor specified for class \p Traits template parameter
631 should accept a parameter of type \p Q that can be not the same as \p value_type.
633 template <typename Q>
634 bool find( Q const& key ) const
637 if ( search( res, key, node_compare() )) {
638 m_Stat.onFindSuccess();
642 m_Stat.onFindFailed();
646 /// Finds the key \p key with comparing functor \p pred
648 The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
649 but \p pred is used for key compare.
650 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
651 "Predicate requirements".
652 \p pred must imply the same element order as the comparator used for building the tree.
653 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
655 template <typename Q, typename Less>
656 bool find_with( Q const& key, Less pred ) const
659 typedef ellen_bintree::details::compare<
662 opt::details::make_comparator_from_less<Less>,
667 if ( search( res, key, compare_functor() )) {
668 m_Stat.onFindSuccess();
671 m_Stat.onFindFailed();
675 /// Finds the key \p key
676 /** @anchor cds_intrusive_EllenBinTree_find_func
677 The function searches the item with key equal to \p key and calls the functor \p f for item found.
678 The interface of \p Func functor is:
681 void operator()( value_type& item, Q& key );
684 where \p item is the item found, \p key is the <tt>find</tt> function argument.
686 The functor can change non-key fields of \p item. Note that the functor is only guarantee
687 that \p item cannot be disposed during functor is executing.
688 The functor does not serialize simultaneous access to the tree \p item. If such access is
689 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
691 The function returns \p true if \p key is found, \p false otherwise.
693 template <typename Q, typename Func>
694 bool find( Q& key, Func f ) const
696 return find_( key, f );
699 template <typename Q, typename Func>
700 bool find( Q const& key, Func f ) const
702 return find_( key, f );
706 /// Finds the key \p key with comparing functor \p pred
708 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
709 but \p pred is used for key comparison.
710 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
711 "Predicate requirements".
712 \p pred must imply the same element order as the comparator used for building the tree.
714 template <typename Q, typename Less, typename Func>
715 bool find_with( Q& key, Less pred, Func f ) const
717 return find_with_( key, pred, f );
720 template <typename Q, typename Less, typename Func>
721 bool find_with( Q const& key, Less pred, Func f ) const
723 return find_with_( key, pred, f );
727 /// Finds \p key and returns the item found
728 /** @anchor cds_intrusive_EllenBinTree_get
729 The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
730 The function returns an empty guarded pointer is \p key is not found.
732 \p guarded_ptr prevents disposer invocation for returned item,
733 see \p cds::gc::guarded_ptr for explanation.
734 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
736 template <typename Q>
737 guarded_ptr get( Q const& key ) const
740 get_( gp.guard(), key );
744 /// Finds \p key with predicate \p pred and returns the item found
746 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
747 but \p pred is used for key comparing.
748 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
749 "Predicate requirements".
750 \p pred must imply the same element order as the comparator used for building the tree.
752 template <typename Q, typename Less>
753 guarded_ptr get_with( Q const& key, Less pred ) const
756 get_with_( gp.guard(), key, pred );
760 /// Checks if the tree is empty
763 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
766 /// Clears the tree (thread safe, not atomic)
768 The function unlink all items from the tree.
769 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
773 assert( tree.empty() );
775 the assertion could be raised.
777 For each leaf the \p disposer will be called after unlinking.
787 /// Clears the tree (not thread safe)
789 This function is not thread safe and may be called only when no other thread deals with the tree.
790 The function is used in the tree destructor.
795 internal_node * pParent = nullptr;
796 internal_node * pGrandParent = nullptr;
797 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
800 while ( pLeaf->is_internal() ) {
801 pGrandParent = pParent;
802 pParent = static_cast<internal_node *>( pLeaf );
803 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
806 if ( pLeaf->infinite_key()) {
811 // Remove leftmost leaf and its parent node
812 assert( pGrandParent );
814 assert( pLeaf->is_leaf() );
816 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
817 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
818 free_internal_node( pParent );
822 /// Returns item count in the tree
824 Only leaf nodes containing user data are counted.
826 The value returned depends on item counter type provided by \p Traits template parameter.
827 If it is \p atomicity::empty_item_counter this function always returns 0.
828 The function is not suitable for checking the tree emptiness, use \p empty()
829 member function for this purpose.
833 return m_ItemCounter;
836 /// Returns const reference to internal statistics
837 stat const& statistics() const
842 /// Checks internal consistency (not atomic, not thread-safe)
844 The debugging function to check internal consistency of the tree.
846 bool check_consistency() const
848 return check_consistency( &m_Root );
854 bool check_consistency( internal_node const * pRoot ) const
856 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
857 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
861 if ( node_compare()( *pLeft, *pRoot ) < 0
862 && node_compare()( *pRoot, *pRight ) <= 0
863 && node_compare()( *pLeft, *pRight ) < 0 )
866 if ( pLeft->is_internal() )
867 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
870 if ( bRet && pRight->is_internal() )
871 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
879 static tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent )
881 tree_node * p = bRight
882 ? res.guards.protect( search_result::Guard_Leaf, pParent->m_pRight,
883 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
884 : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
885 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});
886 if ( p && p->is_leaf() )
887 res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));
889 // child node is guarded
890 // See whether pParent->m_pUpdate has not been changed
891 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
892 // update has been changed - returns nullptr as a flag to search retry
898 static update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src )
900 return res.guards.protect( search_result::Guard_updParent, src, [](update_ptr p) -> update_desc* { return p.ptr(); });
903 template <typename KeyValue, typename Compare>
904 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
906 internal_node * pParent;
907 internal_node * pGrandParent = nullptr;
908 update_ptr updParent;
909 update_ptr updGrandParent;
911 bool bRightParent = false;
917 //pGrandParent = nullptr;
920 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
921 while ( pLeaf->is_internal() ) {
922 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
923 pGrandParent = pParent;
924 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
925 pParent = static_cast<internal_node *>( pLeaf );
926 bRightParent = bRightLeaf;
927 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
928 updGrandParent = updParent;
930 updParent = search_protect_update( res, pParent->m_pUpdate );
932 switch ( updParent.bits() ) {
933 case update_desc::DFlag:
934 case update_desc::Mark:
935 m_Stat.onSearchRetry();
939 nCmp = cmp( key, *pParent );
940 bRightLeaf = nCmp >= 0;
942 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
944 m_Stat.onSearchRetry();
949 assert( pLeaf->is_leaf() );
950 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
952 res.pGrandParent = pGrandParent;
953 res.pParent = pParent;
954 res.pLeaf = static_cast<leaf_node *>( pLeaf );
955 res.updParent = updParent;
956 res.updGrandParent = updGrandParent;
957 res.bRightParent = bRightParent;
958 res.bRightLeaf = bRightLeaf;
963 bool search_min( search_result& res ) const
965 internal_node * pParent;
966 internal_node * pGrandParent;
967 update_ptr updParent;
968 update_ptr updGrandParent;
972 pGrandParent = nullptr;
974 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
975 while ( pLeaf->is_internal() ) {
976 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
977 pGrandParent = pParent;
978 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
979 pParent = static_cast<internal_node *>( pLeaf );
980 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
981 updGrandParent = updParent;
983 updParent = search_protect_update( res, pParent->m_pUpdate );
985 switch ( updParent.bits() ) {
986 case update_desc::DFlag:
987 case update_desc::Mark:
988 m_Stat.onSearchRetry();
992 pLeaf = protect_child_node( res, pParent, false, updParent );
994 m_Stat.onSearchRetry();
999 if ( pLeaf->infinite_key())
1002 res.pGrandParent = pGrandParent;
1003 res.pParent = pParent;
1004 assert( pLeaf->is_leaf() );
1005 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1006 res.updParent = updParent;
1007 res.updGrandParent = updGrandParent;
1008 res.bRightParent = false;
1009 res.bRightLeaf = false;
1014 bool search_max( search_result& res ) const
1016 internal_node * pParent;
1017 internal_node * pGrandParent;
1018 update_ptr updParent;
1019 update_ptr updGrandParent;
1021 bool bRightParent = false;
1025 pGrandParent = nullptr;
1026 updParent = nullptr;
1028 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1029 while ( pLeaf->is_internal() ) {
1030 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1031 pGrandParent = pParent;
1032 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1033 pParent = static_cast<internal_node *>( pLeaf );
1034 bRightParent = bRightLeaf;
1035 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1036 updGrandParent = updParent;
1038 updParent = search_protect_update( res, pParent->m_pUpdate );
1040 switch ( updParent.bits() ) {
1041 case update_desc::DFlag:
1042 case update_desc::Mark:
1043 m_Stat.onSearchRetry();
1047 bRightLeaf = !pParent->infinite_key();
1048 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1050 m_Stat.onSearchRetry();
1055 if ( pLeaf->infinite_key())
1058 res.pGrandParent = pGrandParent;
1059 res.pParent = pParent;
1060 assert( pLeaf->is_leaf() );
1061 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1062 res.updParent = updParent;
1063 res.updGrandParent = updGrandParent;
1064 res.bRightParent = bRightParent;
1065 res.bRightLeaf = bRightLeaf;
1071 void help( update_ptr pUpdate )
1073 // pUpdate must be guarded!
1074 switch ( pUpdate.bits() ) {
1075 case update_desc::IFlag:
1076 help_insert( pUpdate.ptr() );
1077 m_Stat.onHelpInsert();
1079 case update_desc::DFlag:
1080 help_delete( pUpdate.ptr() );
1081 m_Stat.onHelpDelete();
1083 case update_desc::Mark:
1084 //m_Stat.onHelpMark();
1085 //help_marked( pUpdate.ptr() );
1091 void help_insert( update_desc * pOp )
1093 // pOp must be guarded
1095 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1096 if ( pOp->iInfo.bRightLeaf ) {
1097 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1098 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1101 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1102 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1106 update_ptr cur( pOp, update_desc::IFlag );
1107 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1108 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1111 bool check_delete_precondition( search_result& res ) const
1113 // precondition: all member of res must be guarded
1115 assert( res.pGrandParent != nullptr );
1118 static_cast<internal_node *>(
1120 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1121 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1124 static_cast<leaf_node *>(
1126 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1127 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1131 bool help_delete( update_desc * pOp )
1133 // precondition: pOp must be guarded
1135 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1136 update_ptr pMark( pOp, update_desc::Mark );
1137 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1138 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1142 retire_node( pOp->dInfo.pParent );
1143 retire_node( pOp->dInfo.pLeaf );
1144 retire_update_desc( pOp );
1147 else if ( pUpdate == pMark ) {
1148 // some other thread is processing help_marked()
1150 m_Stat.onHelpMark();
1154 // Undo grandparent dInfo
1155 update_ptr pDel( pOp, update_desc::DFlag );
1156 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1157 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1159 retire_update_desc( pOp );
1165 static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1167 tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
1168 if ( pSibling->is_leaf() )
1169 guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
1173 void help_marked( update_desc * pOp )
1175 // precondition: pOp must be guarded
1177 tree_node * pParent = pOp->dInfo.pParent;
1179 typename gc::Guard guard;
1180 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1182 if ( pOp->dInfo.bRightParent ) {
1183 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1184 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1187 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1188 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1191 update_ptr upd( pOp, update_desc::DFlag );
1192 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1193 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1196 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1198 assert( res.updParent.bits() == update_desc::Clean );
1199 assert( res.pLeaf->is_leaf() );
1201 // check search result
1202 if ( (res.bRightLeaf
1203 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1204 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire )) == res.pLeaf ) {
1205 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1207 int nCmp = node_compare()(val, *res.pLeaf);
1209 if ( res.pGrandParent ) {
1210 assert( !res.pLeaf->infinite_key() );
1211 pNewInternal->infinite_key( 0 );
1212 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1215 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1216 pNewInternal->infinite_key( 1 );
1218 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1219 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1222 assert( !res.pLeaf->is_internal() );
1224 pNewInternal->infinite_key( 0 );
1225 key_extractor()(pNewInternal->m_Key, val);
1226 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1227 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1228 assert( !res.pLeaf->infinite_key() );
1231 typename gc::Guard guard;
1232 update_desc * pOp = alloc_update_desc();
1233 guard.assign( pOp );
1235 pOp->iInfo.pParent = res.pParent;
1236 pOp->iInfo.pNew = pNewInternal;
1237 pOp->iInfo.pLeaf = res.pLeaf;
1238 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1240 update_ptr updCur( res.updParent.ptr() );
1241 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1242 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1245 retire_update_desc( pOp );
1249 m_Stat.onUpdateDescDeleted();
1250 free_update_desc( pOp );
1257 template <typename Q, typename Compare, typename Equal, typename Func>
1258 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1260 update_desc * pOp = nullptr;
1265 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1267 retire_update_desc( pOp );
1268 m_Stat.onEraseFailed();
1272 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1274 pOp = alloc_update_desc();
1275 if ( check_delete_precondition( res ) ) {
1276 typename gc::Guard guard;
1277 guard.assign( pOp );
1279 pOp->dInfo.pGrandParent = res.pGrandParent;
1280 pOp->dInfo.pParent = res.pParent;
1281 pOp->dInfo.pLeaf = res.pLeaf;
1282 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1283 pOp->dInfo.bRightParent = res.bRightParent;
1284 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1286 update_ptr updGP( res.updGrandParent.ptr() );
1287 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1288 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1289 if ( help_delete( pOp ) ) {
1290 // res.pLeaf is not deleted yet since it is guarded
1291 f( *node_traits::to_value_ptr( res.pLeaf ) );
1300 m_Stat.onEraseRetry();
1304 m_Stat.onEraseSuccess();
1308 template <typename Q>
1309 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
1311 return erase_( key, node_compare(),
1312 []( Q const&, leaf_node const& ) -> bool { return true; },
1313 [&guard]( value_type& found ) { guard.set( &found ); } );
1316 template <typename Q, typename Less>
1317 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
1319 typedef ellen_bintree::details::compare<
1322 opt::details::make_comparator_from_less<Less>,
1326 return erase_( key, compare_functor(),
1327 []( Q const&, leaf_node const& ) -> bool { return true; },
1328 [&guard]( value_type& found ) { guard.set( &found ); } );
1331 bool extract_max_( typename guarded_ptr::native_guard& gp )
1333 update_desc * pOp = nullptr;
1338 if ( !search_max( res )) {
1341 retire_update_desc( pOp );
1342 m_Stat.onExtractMaxFailed();
1346 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1348 pOp = alloc_update_desc();
1349 if ( check_delete_precondition( res ) ) {
1350 typename gc::Guard guard;
1351 guard.assign( pOp );
1353 pOp->dInfo.pGrandParent = res.pGrandParent;
1354 pOp->dInfo.pParent = res.pParent;
1355 pOp->dInfo.pLeaf = res.pLeaf;
1356 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1357 pOp->dInfo.bRightParent = res.bRightParent;
1358 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1360 update_ptr updGP( res.updGrandParent.ptr() );
1361 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1362 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1364 if ( help_delete( pOp ) )
1372 m_Stat.onExtractMaxRetry();
1376 m_Stat.onExtractMaxSuccess();
1377 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1381 bool extract_min_( typename guarded_ptr::native_guard& gp )
1383 update_desc * pOp = nullptr;
1388 if ( !search_min( res )) {
1391 retire_update_desc( pOp );
1392 m_Stat.onExtractMinFailed();
1396 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1398 pOp = alloc_update_desc();
1399 if ( check_delete_precondition( res ) ) {
1400 typename gc::Guard guard;
1401 guard.assign( pOp );
1403 pOp->dInfo.pGrandParent = res.pGrandParent;
1404 pOp->dInfo.pParent = res.pParent;
1405 pOp->dInfo.pLeaf = res.pLeaf;
1406 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1407 pOp->dInfo.bRightParent = res.bRightParent;
1408 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1410 update_ptr updGP( res.updGrandParent.ptr() );
1411 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1412 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1414 if ( help_delete( pOp ))
1422 m_Stat.onExtractMinRetry();
1426 m_Stat.onExtractMinSuccess();
1427 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1431 template <typename Q, typename Func>
1432 bool find_( Q& val, Func f ) const
1435 if ( search( res, val, node_compare() )) {
1436 assert( res.pLeaf );
1437 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1439 m_Stat.onFindSuccess();
1443 m_Stat.onFindFailed();
1447 template <typename Q, typename Less, typename Func>
1448 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1450 typedef ellen_bintree::details::compare<
1453 opt::details::make_comparator_from_less<Less>,
1458 if ( search( res, val, compare_functor() )) {
1459 assert( res.pLeaf );
1460 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1462 m_Stat.onFindSuccess();
1466 m_Stat.onFindFailed();
1470 template <typename Q>
1471 bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
1473 return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1476 template <typename Q, typename Less>
1477 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
1479 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1485 }} // namespace cds::intrusive
1487 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H