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 Dynamic Hazard Pointer 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 a guarded pointer to an item found.
553 If the tree is empty the function returns an empty guarded pointer.
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 returned \p guarded_ptr prevents disposer invocation for returned item,
561 see \p cds::gc::guarded_ptr for explanation.
562 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
564 guarded_ptr extract_min()
567 extract_min_( gp.guard() );
571 /// Extracts an item with maximal key from the tree
573 The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
574 If the tree is empty the function returns an empty \p guarded_ptr.
576 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
577 It means that the function gets rightmost leaf of the tree and tries to unlink it.
578 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
579 So, the function returns the item with maximal key at the moment of tree traversing.
581 The returned \p guarded_ptr prevents disposer invocation for returned item,
582 see cds::gc::guarded_ptr for explanation.
583 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
585 guarded_ptr extract_max()
588 extract_max_( gp.guard());
592 /// Extracts an item from the tree
593 /** \anchor cds_intrusive_EllenBinTree_extract
594 The function searches an item with key equal to \p key in the tree,
595 unlinks it, and returns a guarded pointer to an item found.
596 If the item is not found the function returns an empty \p guarded_ptr.
598 \p guarded_ptr prevents disposer invocation for returned item,
599 see cds::gc::guarded_ptr for explanation.
600 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
602 template <typename Q>
603 guarded_ptr extract( Q const& key )
606 extract_( gp.guard(), key );
610 /// Extracts an item from the tree using \p pred for searching
612 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
613 but \p pred is used for key compare.
614 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
615 "Predicate requirements".
616 \p pred must imply the same element order as the comparator used for building the tree.
618 template <typename Q, typename Less>
619 guarded_ptr extract_with( Q const& key, Less pred )
622 extract_with_( gp.guard(), key, pred );
626 /// Finds the key \p key
627 /** @anchor cds_intrusive_EllenBinTree_find_val
628 The function searches the item with key equal to \p key
629 and returns \p true if it is found, and \p false otherwise.
631 Note the hash functor specified for class \p Traits template parameter
632 should accept a parameter of type \p Q that can be not the same as \p value_type.
634 template <typename Q>
635 bool find( Q const& key ) const
638 if ( search( res, key, node_compare() )) {
639 m_Stat.onFindSuccess();
643 m_Stat.onFindFailed();
647 /// Finds the key \p key with comparing functor \p pred
649 The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
650 but \p pred is used for key compare.
651 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
652 "Predicate requirements".
653 \p pred must imply the same element order as the comparator used for building the tree.
654 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
656 template <typename Q, typename Less>
657 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 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
882 tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
885 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
886 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
887 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
890 // child node is guarded
891 // See whether pParent->m_pUpdate has not been changed
892 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
893 // update has been changed - returns nullptr as a flag to search retry
897 if ( p && p->is_leaf() )
898 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
899 res.guards.clear( search_result::Guard_helpLeaf );
903 update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src ) const
906 update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
909 res.guards.assign( search_result::Guard_updParent, upd );
910 } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
914 template <typename KeyValue, typename Compare>
915 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
917 internal_node * pParent;
918 internal_node * pGrandParent = nullptr;
919 update_ptr updParent;
920 update_ptr updGrandParent;
922 bool bRightParent = false;
928 //pGrandParent = nullptr;
931 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
932 while ( pLeaf->is_internal() ) {
933 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
934 pGrandParent = pParent;
935 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
936 pParent = static_cast<internal_node *>( pLeaf );
937 bRightParent = bRightLeaf;
938 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
939 updGrandParent = updParent;
941 updParent = search_protect_update( res, pParent->m_pUpdate );
943 switch ( updParent.bits() ) {
944 case update_desc::DFlag:
945 case update_desc::Mark:
946 m_Stat.onSearchRetry();
950 nCmp = cmp( key, *pParent );
951 bRightLeaf = nCmp >= 0;
953 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
955 m_Stat.onSearchRetry();
960 assert( pLeaf->is_leaf() );
961 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
963 res.pGrandParent = pGrandParent;
964 res.pParent = pParent;
965 res.pLeaf = static_cast<leaf_node *>( pLeaf );
966 res.updParent = updParent;
967 res.updGrandParent = updGrandParent;
968 res.bRightParent = bRightParent;
969 res.bRightLeaf = bRightLeaf;
974 bool search_min( search_result& res ) const
976 internal_node * pParent;
977 internal_node * pGrandParent;
978 update_ptr updParent;
979 update_ptr updGrandParent;
983 pGrandParent = nullptr;
985 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
986 while ( pLeaf->is_internal() ) {
987 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
988 pGrandParent = pParent;
989 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
990 pParent = static_cast<internal_node *>( pLeaf );
991 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
992 updGrandParent = updParent;
994 updParent = search_protect_update( res, pParent->m_pUpdate );
996 switch ( updParent.bits() ) {
997 case update_desc::DFlag:
998 case update_desc::Mark:
999 m_Stat.onSearchRetry();
1003 pLeaf = protect_child_node( res, pParent, false, updParent );
1005 m_Stat.onSearchRetry();
1010 if ( pLeaf->infinite_key())
1013 res.pGrandParent = pGrandParent;
1014 res.pParent = pParent;
1015 assert( pLeaf->is_leaf() );
1016 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1017 res.updParent = updParent;
1018 res.updGrandParent = updGrandParent;
1019 res.bRightParent = false;
1020 res.bRightLeaf = false;
1025 bool search_max( search_result& res ) const
1027 internal_node * pParent;
1028 internal_node * pGrandParent;
1029 update_ptr updParent;
1030 update_ptr updGrandParent;
1032 bool bRightParent = false;
1036 pGrandParent = nullptr;
1037 updParent = nullptr;
1039 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1040 while ( pLeaf->is_internal() ) {
1041 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1042 pGrandParent = pParent;
1043 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1044 pParent = static_cast<internal_node *>( pLeaf );
1045 bRightParent = bRightLeaf;
1046 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1047 updGrandParent = updParent;
1049 updParent = search_protect_update( res, pParent->m_pUpdate );
1051 switch ( updParent.bits() ) {
1052 case update_desc::DFlag:
1053 case update_desc::Mark:
1054 m_Stat.onSearchRetry();
1058 bRightLeaf = !pParent->infinite_key();
1059 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1061 m_Stat.onSearchRetry();
1066 if ( pLeaf->infinite_key())
1069 res.pGrandParent = pGrandParent;
1070 res.pParent = pParent;
1071 assert( pLeaf->is_leaf() );
1072 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1073 res.updParent = updParent;
1074 res.updGrandParent = updGrandParent;
1075 res.bRightParent = bRightParent;
1076 res.bRightLeaf = bRightLeaf;
1082 void help( update_ptr pUpdate )
1084 // pUpdate must be guarded!
1085 switch ( pUpdate.bits() ) {
1086 case update_desc::IFlag:
1087 help_insert( pUpdate.ptr() );
1088 m_Stat.onHelpInsert();
1090 case update_desc::DFlag:
1091 help_delete( pUpdate.ptr() );
1092 m_Stat.onHelpDelete();
1094 case update_desc::Mark:
1095 //m_Stat.onHelpMark();
1096 //help_marked( pUpdate.ptr() );
1102 void help_insert( update_desc * pOp )
1104 // pOp must be guarded
1106 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1107 if ( pOp->iInfo.bRightLeaf ) {
1108 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1109 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1112 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1113 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1117 update_ptr cur( pOp, update_desc::IFlag );
1118 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1119 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1122 bool check_delete_precondition( search_result& res ) const
1124 // precondition: all member of res must be guarded
1126 assert( res.pGrandParent != nullptr );
1129 static_cast<internal_node *>(
1131 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1132 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1135 static_cast<leaf_node *>(
1137 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1138 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1142 bool help_delete( update_desc * pOp )
1144 // precondition: pOp must be guarded
1146 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1147 update_ptr pMark( pOp, update_desc::Mark );
1148 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1149 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1153 retire_node( pOp->dInfo.pParent );
1154 retire_node( pOp->dInfo.pLeaf );
1155 retire_update_desc( pOp );
1158 else if ( pUpdate == pMark ) {
1159 // some other thread is processing help_marked()
1161 m_Stat.onHelpMark();
1165 // Undo grandparent dInfo
1166 update_ptr pDel( pOp, update_desc::DFlag );
1167 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1168 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1170 retire_update_desc( pOp );
1176 tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1178 typename gc::Guard guardLeaf;
1180 tree_node * pSibling;
1181 tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1184 guard.assign( static_cast<internal_node *>(p) );
1185 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1186 } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1188 if ( pSibling->is_leaf() )
1189 guard.copy( guardLeaf );
1194 void help_marked( update_desc * pOp )
1196 // precondition: pOp must be guarded
1198 tree_node * pParent = pOp->dInfo.pParent;
1200 typename gc::Guard guard;
1201 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1203 if ( pOp->dInfo.bRightParent ) {
1204 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1205 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1208 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1209 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1212 update_ptr upd( pOp, update_desc::DFlag );
1213 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1214 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1217 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1219 assert( res.updParent.bits() == update_desc::Clean );
1220 assert( res.pLeaf->is_leaf() );
1222 // check search result
1223 if ( (res.bRightLeaf
1224 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1225 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire )) == res.pLeaf ) {
1226 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1228 int nCmp = node_compare()(val, *res.pLeaf);
1230 if ( res.pGrandParent ) {
1231 assert( !res.pLeaf->infinite_key() );
1232 pNewInternal->infinite_key( 0 );
1233 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1236 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1237 pNewInternal->infinite_key( 1 );
1239 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1240 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1243 assert( !res.pLeaf->is_internal() );
1244 pNewInternal->infinite_key( 0 );
1246 key_extractor()(pNewInternal->m_Key, val);
1247 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1248 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1249 assert( !res.pLeaf->infinite_key() );
1252 typename gc::Guard guard;
1253 update_desc * pOp = alloc_update_desc();
1254 guard.assign( pOp );
1256 pOp->iInfo.pParent = res.pParent;
1257 pOp->iInfo.pNew = pNewInternal;
1258 pOp->iInfo.pLeaf = res.pLeaf;
1259 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1261 update_ptr updCur( res.updParent.ptr() );
1262 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1263 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1266 retire_update_desc( pOp );
1270 m_Stat.onUpdateDescDeleted();
1271 free_update_desc( pOp );
1278 template <typename Q, typename Compare, typename Equal, typename Func>
1279 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1281 update_desc * pOp = nullptr;
1286 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1288 retire_update_desc( pOp );
1289 m_Stat.onEraseFailed();
1293 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1295 pOp = alloc_update_desc();
1296 if ( check_delete_precondition( res ) ) {
1297 typename gc::Guard guard;
1298 guard.assign( pOp );
1300 pOp->dInfo.pGrandParent = res.pGrandParent;
1301 pOp->dInfo.pParent = res.pParent;
1302 pOp->dInfo.pLeaf = res.pLeaf;
1303 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1304 pOp->dInfo.bRightParent = res.bRightParent;
1305 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1307 update_ptr updGP( res.updGrandParent.ptr() );
1308 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1309 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1310 if ( help_delete( pOp ) ) {
1311 // res.pLeaf is not deleted yet since it is guarded
1312 f( *node_traits::to_value_ptr( res.pLeaf ) );
1321 m_Stat.onEraseRetry();
1325 m_Stat.onEraseSuccess();
1329 template <typename Q>
1330 bool extract_( typename gc::Guard& guard, Q const& key )
1333 return erase_( key, node_compare(),
1334 []( Q const&, leaf_node const& ) -> bool { return true; },
1335 [&guard]( value_type& found ) { guard.assign( &found ); } );
1338 template <typename Q, typename Less>
1339 bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
1341 typedef ellen_bintree::details::compare<
1344 opt::details::make_comparator_from_less<Less>,
1348 return erase_( key, compare_functor(),
1349 []( Q const&, leaf_node const& ) -> bool { return true; },
1350 [&guard]( value_type& found ) { guard.assign( &found ); } );
1353 bool extract_max_( typename gc::Guard& gp )
1355 update_desc * pOp = nullptr;
1360 if ( !search_max( res )) {
1363 retire_update_desc( pOp );
1364 m_Stat.onExtractMaxFailed();
1368 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1370 pOp = alloc_update_desc();
1371 if ( check_delete_precondition( res ) ) {
1372 typename gc::Guard guard;
1373 guard.assign( pOp );
1375 pOp->dInfo.pGrandParent = res.pGrandParent;
1376 pOp->dInfo.pParent = res.pParent;
1377 pOp->dInfo.pLeaf = res.pLeaf;
1378 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1379 pOp->dInfo.bRightParent = res.bRightParent;
1380 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1382 update_ptr updGP( res.updGrandParent.ptr() );
1383 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1384 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1386 if ( help_delete( pOp ) )
1394 m_Stat.onExtractMaxRetry();
1398 m_Stat.onExtractMaxSuccess();
1399 gp.assign( node_traits::to_value_ptr( res.pLeaf ));
1403 bool extract_min_( typename gc::Guard& gp )
1405 update_desc * pOp = nullptr;
1410 if ( !search_min( res )) {
1413 retire_update_desc( pOp );
1414 m_Stat.onExtractMinFailed();
1418 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1420 pOp = alloc_update_desc();
1421 if ( check_delete_precondition( res ) ) {
1422 typename gc::Guard guard;
1423 guard.assign( pOp );
1425 pOp->dInfo.pGrandParent = res.pGrandParent;
1426 pOp->dInfo.pParent = res.pParent;
1427 pOp->dInfo.pLeaf = res.pLeaf;
1428 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1429 pOp->dInfo.bRightParent = res.bRightParent;
1430 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1432 update_ptr updGP( res.updGrandParent.ptr() );
1433 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1434 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1436 if ( help_delete( pOp ))
1444 m_Stat.onExtractMinRetry();
1448 m_Stat.onExtractMinSuccess();
1449 gp.assign( node_traits::to_value_ptr( res.pLeaf ));
1453 template <typename Q, typename Func>
1454 bool find_( Q& val, Func f ) const
1457 if ( search( res, val, node_compare() )) {
1458 assert( res.pLeaf );
1459 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1461 m_Stat.onFindSuccess();
1465 m_Stat.onFindFailed();
1469 template <typename Q, typename Less, typename Func>
1470 bool find_with_( Q& val, Less pred, Func f ) const
1472 typedef ellen_bintree::details::compare<
1475 opt::details::make_comparator_from_less<Less>,
1480 if ( search( res, val, compare_functor() )) {
1481 assert( res.pLeaf );
1482 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1484 m_Stat.onFindSuccess();
1488 m_Stat.onFindFailed();
1492 template <typename Q>
1493 bool get_( typename gc::Guard& guard, Q const& val ) const
1495 return find_( val, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1498 template <typename Q, typename Less>
1499 bool get_with_( typename gc::Guard& guard, Q const& val, Less pred ) const
1501 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1507 }} // namespace cds::intrusive
1509 #endif // #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H