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
169 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
171 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
172 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
174 struct search_result {
179 Guard_updGrandParent,
185 // end of guard indices
189 typedef typename gc::template GuardArray< guard_count > guard_array;
192 internal_node * pGrandParent;
193 internal_node * pParent;
195 update_ptr updParent;
196 update_ptr updGrandParent;
197 bool bRightLeaf; // true if pLeaf is right child of pParent, false otherwise
198 bool bRightParent; // true if pParent is right child of pGrandParent, false otherwise
201 :pGrandParent( nullptr )
205 ,bRightParent( false )
208 void clean_help_guards()
210 guards.clear( Guard_helpLeaf );
217 internal_node m_Root; ///< Tree root node (key= Infinite2)
218 leaf_node m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
219 leaf_node m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
222 item_counter m_ItemCounter; ///< item counter
223 mutable stat m_Stat; ///< internal statistics
227 static void free_leaf_node( value_type * p )
232 internal_node * alloc_internal_node() const
234 m_Stat.onInternalNodeCreated();
235 internal_node * pNode = cxx_node_allocator().New();
239 static void free_internal_node( internal_node * pNode )
241 cxx_node_allocator().Delete( pNode );
244 struct internal_node_deleter {
245 void operator()( internal_node * p) const
247 free_internal_node( p );
251 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
253 update_desc * alloc_update_desc() const
255 m_Stat.onUpdateDescCreated();
256 return cxx_update_desc_allocator().New();
259 static void free_update_desc( update_desc * pDesc )
261 cxx_update_desc_allocator().Delete( pDesc );
264 void retire_node( tree_node * pNode ) const
266 if ( pNode->is_leaf() ) {
267 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
268 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
270 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
273 assert( static_cast<internal_node *>( pNode ) != &m_Root );
274 m_Stat.onInternalNodeDeleted();
276 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
280 void retire_update_desc( update_desc * p ) const
282 m_Stat.onUpdateDescDeleted();
283 gc::template retire( p, free_update_desc );
286 void make_empty_tree()
288 m_Root.infinite_key( 2 );
289 m_LeafInf1.infinite_key( 1 );
290 m_LeafInf2.infinite_key( 2 );
291 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
292 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
297 /// Default constructor
300 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
312 The function inserts \p val in the tree if it does not contain
313 an item with key equal to \p val.
315 Returns \p true if \p val is placed into the tree, \p false otherwise.
317 bool insert( value_type& val )
319 return insert( val, []( value_type& ) {} );
324 This function is intended for derived non-intrusive containers.
326 The function allows to split creating of new item into two part:
327 - create item with key only
328 - insert new item into the tree
329 - if inserting is success, calls \p f functor to initialize value-field of \p val.
331 The functor signature is:
333 void func( value_type& val );
335 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
336 \p val no any other changes could be made on this tree's item by concurrent threads.
337 The user-defined functor is called only if the inserting is success.
339 template <typename Func>
340 bool insert( value_type& val, Func f )
342 typename gc::Guard guardInsert;
343 guardInsert.assign( &val );
345 unique_internal_node_ptr pNewInternal;
350 if ( search( res, val, node_compare() )) {
351 if ( pNewInternal.get() )
352 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
353 m_Stat.onInsertFailed();
357 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
359 if ( !pNewInternal.get() )
360 pNewInternal.reset( alloc_internal_node() );
362 if ( try_insert( val, pNewInternal.get(), res )) {
364 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
370 m_Stat.onInsertRetry();
374 m_Stat.onInsertSuccess();
378 /// Ensures that the \p val exists in the tree
380 The operation performs inserting or changing data with lock-free manner.
382 If the item \p val is not found in the tree, then \p val is inserted into the tree.
383 Otherwise, the functor \p func is called with item found.
384 The functor signature is:
386 void func( bool bNew, value_type& item, value_type& val );
389 - \p bNew - \p true if the item has been inserted, \p false otherwise
390 - \p item - an item of the tree
391 - \p val - the argument \p val passed to the \p ensure function
392 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
393 refer to the same thing.
395 The functor can change non-key fields of the \p item; however, \p func must guarantee
396 that during changing no any other modifications could be made on this item by concurrent threads.
398 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
399 \p second is \p true if new item has been added or \p false if the item with \p key
400 already is in the tree.
402 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
404 template <typename Func>
405 std::pair<bool, bool> ensure( value_type& val, Func func )
407 typename gc::Guard guardInsert;
408 guardInsert.assign( &val );
410 unique_internal_node_ptr pNewInternal;
415 if ( search( res, val, node_compare() )) {
416 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
417 if ( pNewInternal.get() )
418 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
419 m_Stat.onEnsureExist();
420 return std::make_pair( true, false );
423 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
425 if ( !pNewInternal.get() )
426 pNewInternal.reset( alloc_internal_node() );
428 if ( try_insert( val, pNewInternal.get(), res )) {
429 func( true, val, val );
430 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
436 m_Stat.onEnsureRetry();
440 m_Stat.onEnsureNew();
441 return std::make_pair( true, true );
444 /// Unlinks the item \p val from the tree
446 The function searches the item \p val in the tree and unlink it from the tree
447 if it is found and is equal to \p val.
449 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
450 and deletes the item found. \p unlink finds an item by key and deletes it
451 only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
453 The \p disposer specified in \p Traits class template parameter is called
454 by garbage collector \p GC asynchronously.
456 The function returns \p true if success and \p false otherwise.
458 bool unlink( value_type& val )
460 return erase_( val, node_compare(),
461 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
462 [](value_type const&) {} );
465 /// Deletes the item from the tree
466 /** \anchor cds_intrusive_EllenBinTree_erase
467 The function searches an item with key equal to \p key in the tree,
468 unlinks it from the tree, and returns \p true.
469 If the item with key equal to \p key is not found the function return \p false.
471 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
473 template <typename Q>
474 bool erase( const Q& key )
476 return erase_( key, node_compare(),
477 []( Q const&, leaf_node const& ) -> bool { return true; },
478 [](value_type const&) {} );
481 /// Delete the item from the tree with comparing functor \p pred
483 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
484 but \p pred predicate is used for key comparing.
485 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
486 "Predicate requirements".
487 \p pred must imply the same element order as the comparator used for building the tree.
489 template <typename Q, typename Less>
490 bool erase_with( const Q& key, Less pred )
493 typedef ellen_bintree::details::compare<
496 opt::details::make_comparator_from_less<Less>,
500 return erase_( key, compare_functor(),
501 []( Q const&, leaf_node const& ) -> bool { return true; },
502 [](value_type const&) {} );
505 /// Deletes the item from the tree
506 /** \anchor cds_intrusive_EllenBinTree_erase_func
507 The function searches an item with key equal to \p key in the tree,
508 call \p f functor with item found, unlinks it from the tree, and returns \p true.
509 The \ref disposer specified in \p Traits class template parameter is called
510 by garbage collector \p GC asynchronously.
512 The \p Func interface is
515 void operator()( value_type const& item );
519 If the item with key equal to \p key is not found the function return \p false.
521 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
523 template <typename Q, typename Func>
524 bool erase( Q const& key, Func f )
526 return erase_( key, node_compare(),
527 []( Q const&, leaf_node const& ) -> bool { return true; },
531 /// Delete the item from the tree with comparing functor \p pred
533 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
534 but \p pred predicate is used for key comparing.
535 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
536 "Predicate requirements".
537 \p pred must imply the same element order as the comparator used for building the tree.
539 template <typename Q, typename Less, typename Func>
540 bool erase_with( Q const& key, Less pred, Func f )
543 typedef ellen_bintree::details::compare<
546 opt::details::make_comparator_from_less<Less>,
550 return erase_( key, compare_functor(),
551 []( Q const&, leaf_node const& ) -> bool { return true; },
555 /// Extracts an item with minimal key from the tree
557 The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
558 If the tree is empty the function returns an empty guarded pointer.
560 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
561 It means that the function gets leftmost leaf of the tree and tries to unlink it.
562 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
563 So, the function returns the item with minimum key at the moment of tree traversing.
565 The returned \p guarded_ptr prevents disposer invocation for returned item,
566 see \p cds::gc::guarded_ptr for explanation.
567 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
569 guarded_ptr extract_min()
572 extract_min_( gp.guard() );
576 /// Extracts an item with maximal key from the tree
578 The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
579 If the tree is empty the function returns an empty \p guarded_ptr.
581 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
582 It means that the function gets rightmost leaf of the tree and tries to unlink it.
583 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
584 So, the function returns the item with maximal key at the moment of tree traversing.
586 The returned \p guarded_ptr prevents disposer invocation for returned item,
587 see cds::gc::guarded_ptr for explanation.
588 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
590 guarded_ptr extract_max()
593 extract_max_( gp.guard());
597 /// Extracts an item from the tree
598 /** \anchor cds_intrusive_EllenBinTree_extract
599 The function searches an item with key equal to \p key in the tree,
600 unlinks it, and returns a guarded pointer to an item found.
601 If the item is not found the function returns an empty \p guarded_ptr.
603 \p guarded_ptr prevents disposer invocation for returned item,
604 see cds::gc::guarded_ptr for explanation.
605 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
607 template <typename Q>
608 guarded_ptr extract( Q const& key )
611 extract_( gp.guard(), key );
615 /// Extracts an item from the tree using \p pred for searching
617 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
618 but \p pred is used for key compare.
619 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
620 "Predicate requirements".
621 \p pred must imply the same element order as the comparator used for building the tree.
623 template <typename Q, typename Less>
624 guarded_ptr extract_with( Q const& key, Less pred )
627 extract_with_( gp.guard(), key, pred );
631 /// Finds the key \p key
632 /** @anchor cds_intrusive_EllenBinTree_find_val
633 The function searches the item with key equal to \p key
634 and returns \p true if it is found, and \p false otherwise.
636 Note the hash functor specified for class \p Traits template parameter
637 should accept a parameter of type \p Q that can be not the same as \p value_type.
639 template <typename Q>
640 bool find( Q const& key ) const
643 if ( search( res, key, node_compare() )) {
644 m_Stat.onFindSuccess();
648 m_Stat.onFindFailed();
652 /// Finds the key \p key with comparing functor \p pred
654 The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
655 but \p pred is used for key compare.
656 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
657 "Predicate requirements".
658 \p pred must imply the same element order as the comparator used for building the tree.
659 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
661 template <typename Q, typename Less>
662 bool find_with( Q const& key, Less pred ) const
665 typedef ellen_bintree::details::compare<
668 opt::details::make_comparator_from_less<Less>,
673 if ( search( res, key, compare_functor() )) {
674 m_Stat.onFindSuccess();
677 m_Stat.onFindFailed();
681 /// Finds the key \p key
682 /** @anchor cds_intrusive_EllenBinTree_find_func
683 The function searches the item with key equal to \p key and calls the functor \p f for item found.
684 The interface of \p Func functor is:
687 void operator()( value_type& item, Q& key );
690 where \p item is the item found, \p key is the <tt>find</tt> function argument.
692 The functor can change non-key fields of \p item. Note that the functor is only guarantee
693 that \p item cannot be disposed during functor is executing.
694 The functor does not serialize simultaneous access to the tree \p item. If such access is
695 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
697 The function returns \p true if \p key is found, \p false otherwise.
699 template <typename Q, typename Func>
700 bool find( Q& key, Func f ) const
702 return find_( key, f );
705 template <typename Q, typename Func>
706 bool find( Q const& key, Func f ) const
708 return find_( key, f );
712 /// Finds the key \p key with comparing functor \p pred
714 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
715 but \p pred is used for key comparison.
716 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
717 "Predicate requirements".
718 \p pred must imply the same element order as the comparator used for building the tree.
720 template <typename Q, typename Less, typename Func>
721 bool find_with( Q& key, Less pred, Func f ) const
723 return find_with_( key, pred, f );
726 template <typename Q, typename Less, typename Func>
727 bool find_with( Q const& key, Less pred, Func f ) const
729 return find_with_( key, pred, f );
733 /// Finds \p key and returns the item found
734 /** @anchor cds_intrusive_EllenBinTree_get
735 The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
736 The function returns an empty guarded pointer is \p key is not found.
738 \p guarded_ptr prevents disposer invocation for returned item,
739 see \p cds::gc::guarded_ptr for explanation.
740 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
742 template <typename Q>
743 guarded_ptr get( Q const& key ) const
746 get_( gp.guard(), key );
750 /// Finds \p key with predicate \p pred and returns the item found
752 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
753 but \p pred is used for key comparing.
754 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
755 "Predicate requirements".
756 \p pred must imply the same element order as the comparator used for building the tree.
758 template <typename Q, typename Less>
759 guarded_ptr get_with( Q const& key, Less pred ) const
762 get_with_( gp.guard(), key, pred );
766 /// Checks if the tree is empty
769 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
772 /// Clears the tree (thread safe, not atomic)
774 The function unlink all items from the tree.
775 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
779 assert( tree.empty() );
781 the assertion could be raised.
783 For each leaf the \p disposer will be called after unlinking.
793 /// Clears the tree (not thread safe)
795 This function is not thread safe and may be called only when no other thread deals with the tree.
796 The function is used in the tree destructor.
801 internal_node * pParent = nullptr;
802 internal_node * pGrandParent = nullptr;
803 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
806 while ( pLeaf->is_internal() ) {
807 pGrandParent = pParent;
808 pParent = static_cast<internal_node *>( pLeaf );
809 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
812 if ( pLeaf->infinite_key()) {
817 // Remove leftmost leaf and its parent node
818 assert( pGrandParent );
820 assert( pLeaf->is_leaf() );
822 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
823 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
824 free_internal_node( pParent );
828 /// Returns item count in the tree
830 Only leaf nodes containing user data are counted.
832 The value returned depends on item counter type provided by \p Traits template parameter.
833 If it is \p atomicity::empty_item_counter this function always returns 0.
834 The function is not suitable for checking the tree emptiness, use \p empty()
835 member function for this purpose.
839 return m_ItemCounter;
842 /// Returns const reference to internal statistics
843 stat const& statistics() const
848 /// Checks internal consistency (not atomic, not thread-safe)
850 The debugging function to check internal consistency of the tree.
852 bool check_consistency() const
854 return check_consistency( &m_Root );
860 bool check_consistency( internal_node const * pRoot ) const
862 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
863 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
867 if ( node_compare()( *pLeft, *pRoot ) < 0
868 && node_compare()( *pRoot, *pRight ) <= 0
869 && node_compare()( *pLeft, *pRight ) < 0 )
872 if ( pLeft->is_internal() )
873 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
876 if ( bRet && pRight->is_internal() )
877 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
885 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
888 tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
891 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
892 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
893 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
896 // child node is guarded
897 // See whether pParent->m_pUpdate has not been changed
898 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
899 // update has been changed - returns nullptr as a flag to search retry
903 if ( p && p->is_leaf() )
904 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
905 res.guards.clear( search_result::Guard_helpLeaf );
909 update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src ) const
912 update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
915 res.guards.assign( search_result::Guard_updParent, upd );
916 } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
920 template <typename KeyValue, typename Compare>
921 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
923 internal_node * pParent;
924 internal_node * pGrandParent = nullptr;
925 update_ptr updParent;
926 update_ptr updGrandParent;
928 bool bRightParent = false;
934 //pGrandParent = nullptr;
937 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
938 while ( pLeaf->is_internal() ) {
939 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
940 pGrandParent = pParent;
941 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
942 pParent = static_cast<internal_node *>( pLeaf );
943 bRightParent = bRightLeaf;
944 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
945 updGrandParent = updParent;
947 updParent = search_protect_update( res, pParent->m_pUpdate );
949 switch ( updParent.bits() ) {
950 case update_desc::DFlag:
951 case update_desc::Mark:
952 m_Stat.onSearchRetry();
956 nCmp = cmp( key, *pParent );
957 bRightLeaf = nCmp >= 0;
959 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
961 m_Stat.onSearchRetry();
966 assert( pLeaf->is_leaf() );
967 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
969 res.pGrandParent = pGrandParent;
970 res.pParent = pParent;
971 res.pLeaf = static_cast<leaf_node *>( pLeaf );
972 res.updParent = updParent;
973 res.updGrandParent = updGrandParent;
974 res.bRightParent = bRightParent;
975 res.bRightLeaf = bRightLeaf;
980 bool search_min( search_result& res ) const
982 internal_node * pParent;
983 internal_node * pGrandParent;
984 update_ptr updParent;
985 update_ptr updGrandParent;
989 pGrandParent = nullptr;
991 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
992 while ( pLeaf->is_internal() ) {
993 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
994 pGrandParent = pParent;
995 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
996 pParent = static_cast<internal_node *>( pLeaf );
997 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
998 updGrandParent = updParent;
1000 updParent = search_protect_update( res, pParent->m_pUpdate );
1002 switch ( updParent.bits() ) {
1003 case update_desc::DFlag:
1004 case update_desc::Mark:
1005 m_Stat.onSearchRetry();
1009 pLeaf = protect_child_node( res, pParent, false, updParent );
1011 m_Stat.onSearchRetry();
1016 if ( pLeaf->infinite_key())
1019 res.pGrandParent = pGrandParent;
1020 res.pParent = pParent;
1021 assert( pLeaf->is_leaf() );
1022 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1023 res.updParent = updParent;
1024 res.updGrandParent = updGrandParent;
1025 res.bRightParent = false;
1026 res.bRightLeaf = false;
1031 bool search_max( search_result& res ) const
1033 internal_node * pParent;
1034 internal_node * pGrandParent;
1035 update_ptr updParent;
1036 update_ptr updGrandParent;
1038 bool bRightParent = false;
1042 pGrandParent = nullptr;
1043 updParent = nullptr;
1045 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1046 while ( pLeaf->is_internal() ) {
1047 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1048 pGrandParent = pParent;
1049 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1050 pParent = static_cast<internal_node *>( pLeaf );
1051 bRightParent = bRightLeaf;
1052 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1053 updGrandParent = updParent;
1055 updParent = search_protect_update( res, pParent->m_pUpdate );
1057 switch ( updParent.bits() ) {
1058 case update_desc::DFlag:
1059 case update_desc::Mark:
1060 m_Stat.onSearchRetry();
1064 bRightLeaf = !pParent->infinite_key();
1065 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1067 m_Stat.onSearchRetry();
1072 if ( pLeaf->infinite_key())
1075 res.pGrandParent = pGrandParent;
1076 res.pParent = pParent;
1077 assert( pLeaf->is_leaf() );
1078 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1079 res.updParent = updParent;
1080 res.updGrandParent = updGrandParent;
1081 res.bRightParent = bRightParent;
1082 res.bRightLeaf = bRightLeaf;
1088 void help( update_ptr pUpdate )
1090 // pUpdate must be guarded!
1091 switch ( pUpdate.bits() ) {
1092 case update_desc::IFlag:
1093 help_insert( pUpdate.ptr() );
1094 m_Stat.onHelpInsert();
1096 case update_desc::DFlag:
1097 help_delete( pUpdate.ptr() );
1098 m_Stat.onHelpDelete();
1100 case update_desc::Mark:
1101 //m_Stat.onHelpMark();
1102 //help_marked( pUpdate.ptr() );
1108 void help_insert( update_desc * pOp )
1110 // pOp must be guarded
1112 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1113 if ( pOp->iInfo.bRightLeaf ) {
1114 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1115 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1118 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1119 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1123 update_ptr cur( pOp, update_desc::IFlag );
1124 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1125 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1128 bool check_delete_precondition( search_result& res ) const
1130 // precondition: all member of res must be guarded
1132 assert( res.pGrandParent != nullptr );
1135 static_cast<internal_node *>(
1137 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1138 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1141 static_cast<leaf_node *>(
1143 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1144 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1148 bool help_delete( update_desc * pOp )
1150 // precondition: pOp must be guarded
1152 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1153 update_ptr pMark( pOp, update_desc::Mark );
1154 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1155 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1159 retire_node( pOp->dInfo.pParent );
1160 retire_node( pOp->dInfo.pLeaf );
1161 retire_update_desc( pOp );
1164 else if ( pUpdate == pMark ) {
1165 // some other thread is processing help_marked()
1167 m_Stat.onHelpMark();
1171 // Undo grandparent dInfo
1172 update_ptr pDel( pOp, update_desc::DFlag );
1173 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1174 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1176 retire_update_desc( pOp );
1182 tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1184 typename gc::Guard guardLeaf;
1186 tree_node * pSibling;
1187 tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1190 guard.assign( static_cast<internal_node *>(p) );
1191 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1192 } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1194 if ( pSibling->is_leaf() )
1195 guard.copy( guardLeaf );
1200 void help_marked( update_desc * pOp )
1202 // precondition: pOp must be guarded
1204 tree_node * pParent = pOp->dInfo.pParent;
1206 typename gc::Guard guard;
1207 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1209 if ( pOp->dInfo.bRightParent ) {
1210 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1211 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1214 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1215 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1218 update_ptr upd( pOp, update_desc::DFlag );
1219 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1220 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1223 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1225 assert( res.updParent.bits() == update_desc::Clean );
1226 assert( res.pLeaf->is_leaf() );
1228 // check search result
1229 if ( (res.bRightLeaf
1230 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1231 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire )) == res.pLeaf ) {
1232 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1234 int nCmp = node_compare()(val, *res.pLeaf);
1236 if ( res.pGrandParent ) {
1237 assert( !res.pLeaf->infinite_key() );
1238 pNewInternal->infinite_key( 0 );
1239 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1242 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1243 pNewInternal->infinite_key( 1 );
1245 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1246 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1249 assert( !res.pLeaf->is_internal() );
1250 pNewInternal->infinite_key( 0 );
1252 key_extractor()(pNewInternal->m_Key, val);
1253 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1254 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1255 assert( !res.pLeaf->infinite_key() );
1258 typename gc::Guard guard;
1259 update_desc * pOp = alloc_update_desc();
1260 guard.assign( pOp );
1262 pOp->iInfo.pParent = res.pParent;
1263 pOp->iInfo.pNew = pNewInternal;
1264 pOp->iInfo.pLeaf = res.pLeaf;
1265 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1267 update_ptr updCur( res.updParent.ptr() );
1268 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1269 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1272 retire_update_desc( pOp );
1276 m_Stat.onUpdateDescDeleted();
1277 free_update_desc( pOp );
1284 template <typename Q, typename Compare, typename Equal, typename Func>
1285 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1287 update_desc * pOp = nullptr;
1292 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1294 retire_update_desc( pOp );
1295 m_Stat.onEraseFailed();
1299 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1301 pOp = alloc_update_desc();
1302 if ( check_delete_precondition( res ) ) {
1303 typename gc::Guard guard;
1304 guard.assign( pOp );
1306 pOp->dInfo.pGrandParent = res.pGrandParent;
1307 pOp->dInfo.pParent = res.pParent;
1308 pOp->dInfo.pLeaf = res.pLeaf;
1309 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1310 pOp->dInfo.bRightParent = res.bRightParent;
1311 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1313 update_ptr updGP( res.updGrandParent.ptr() );
1314 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1315 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1316 if ( help_delete( pOp ) ) {
1317 // res.pLeaf is not deleted yet since it is guarded
1318 f( *node_traits::to_value_ptr( res.pLeaf ) );
1327 m_Stat.onEraseRetry();
1331 m_Stat.onEraseSuccess();
1335 template <typename Q>
1336 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
1338 return erase_( key, node_compare(),
1339 []( Q const&, leaf_node const& ) -> bool { return true; },
1340 [&guard]( value_type& found ) { guard.set( &found ); } );
1343 template <typename Q, typename Less>
1344 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
1346 typedef ellen_bintree::details::compare<
1349 opt::details::make_comparator_from_less<Less>,
1353 return erase_( key, compare_functor(),
1354 []( Q const&, leaf_node const& ) -> bool { return true; },
1355 [&guard]( value_type& found ) { guard.set( &found ); } );
1358 bool extract_max_( typename guarded_ptr::native_guard& gp )
1360 update_desc * pOp = nullptr;
1365 if ( !search_max( res )) {
1368 retire_update_desc( pOp );
1369 m_Stat.onExtractMaxFailed();
1373 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1375 pOp = alloc_update_desc();
1376 if ( check_delete_precondition( res ) ) {
1377 typename gc::Guard guard;
1378 guard.assign( pOp );
1380 pOp->dInfo.pGrandParent = res.pGrandParent;
1381 pOp->dInfo.pParent = res.pParent;
1382 pOp->dInfo.pLeaf = res.pLeaf;
1383 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1384 pOp->dInfo.bRightParent = res.bRightParent;
1385 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1387 update_ptr updGP( res.updGrandParent.ptr() );
1388 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1389 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1391 if ( help_delete( pOp ) )
1399 m_Stat.onExtractMaxRetry();
1403 m_Stat.onExtractMaxSuccess();
1404 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1408 bool extract_min_( typename guarded_ptr::native_guard& gp )
1410 update_desc * pOp = nullptr;
1415 if ( !search_min( res )) {
1418 retire_update_desc( pOp );
1419 m_Stat.onExtractMinFailed();
1423 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1425 pOp = alloc_update_desc();
1426 if ( check_delete_precondition( res ) ) {
1427 typename gc::Guard guard;
1428 guard.assign( pOp );
1430 pOp->dInfo.pGrandParent = res.pGrandParent;
1431 pOp->dInfo.pParent = res.pParent;
1432 pOp->dInfo.pLeaf = res.pLeaf;
1433 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1434 pOp->dInfo.bRightParent = res.bRightParent;
1435 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1437 update_ptr updGP( res.updGrandParent.ptr() );
1438 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1439 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1441 if ( help_delete( pOp ))
1449 m_Stat.onExtractMinRetry();
1453 m_Stat.onExtractMinSuccess();
1454 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1458 template <typename Q, typename Func>
1459 bool find_( Q& val, Func f ) const
1462 if ( search( res, val, node_compare() )) {
1463 assert( res.pLeaf );
1464 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1466 m_Stat.onFindSuccess();
1470 m_Stat.onFindFailed();
1474 template <typename Q, typename Less, typename Func>
1475 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1477 typedef ellen_bintree::details::compare<
1480 opt::details::make_comparator_from_less<Less>,
1485 if ( search( res, val, compare_functor() )) {
1486 assert( res.pLeaf );
1487 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1489 m_Stat.onFindSuccess();
1493 m_Stat.onFindFailed();
1497 template <typename Q>
1498 bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
1500 return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1503 template <typename Q, typename Less>
1504 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
1506 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1512 }} // namespace cds::intrusive
1514 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H