3 #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
4 #define __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
7 #include <cds/intrusive/details/ellen_bintree_base.h>
8 #include <cds/opt/compare.h>
9 #include <cds/details/binary_functor_wrapper.h>
10 #include <cds/urcu/details/check_deadlock.h>
11 #include <cds/gc/guarded_ptr.h>
13 namespace cds { namespace intrusive {
15 /// Ellen's et al binary search tree
16 /** @ingroup cds_intrusive_map
17 @ingroup cds_intrusive_tree
18 @anchor cds_intrusive_EllenBinTree
21 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
23 %EllenBinTree is an <i>unbalanced</i> leaf-oriented binary search tree that implements the <i>set</i>
24 abstract data type. Nodes maintains child pointers but not parent pointers.
25 Every internal node has exactly two children, and all data of type \p T currently in
26 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find()
27 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
28 may or may not be in the set. \p Key type is a subset of \p T type.
29 There should be exactly defined a key extracting functor for converting object of type \p T to
30 object of type \p Key.
32 Due to \p extract_min() and \p extract_max() member functions the \p %EllenBinTree can act as
33 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
34 the priority value plus some uniformly distributed random value.
36 @note In the current implementation we do not use helping technique described in the original paper.
37 In Hazard Pointer schema helping is too complicated and does not give any observable benefits.
38 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
39 the operation done. Such solution allows greatly simplify the implementation of tree.
41 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
42 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
44 @note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
45 There are header file for each GC type:
46 - <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC \p cds::gc::HP
47 - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Pass-the-Buck GC \p cds::gc::DHP
48 - <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
50 <b>Template arguments</b> :
51 - \p GC - garbage collector, possible types are cds::gc::HP, cds::gc::DHP.
52 - \p Key - key type, a subset of \p T
53 - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
54 (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
55 (for \p ellen_bintree::member_hook).
56 - \p Traits - tree traits, default is \p ellen_bintree::traits
57 It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
58 instead of \p Traits template argument.
60 @anchor cds_intrusive_EllenBinTree_less
61 <b>Predicate requirements</b>
63 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
64 of type \p T and \p Key in any combination.
65 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
67 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
74 bool operator()( Foo const& v1, Foo const& v2 ) const
75 { return v1.m_strKey < v2.m_strKey ; }
77 bool operator()( Foo const& v, std::string const& s ) const
78 { return v.m_strKey < s ; }
80 bool operator()( std::string const& s, Foo const& v ) const
81 { return s < v.m_strKey ; }
83 // Support comparing std::string and char const *
84 bool operator()( std::string const& s, char const * p ) const
85 { return s.compare(p) < 0 ; }
87 bool operator()( Foo const& v, char const * p ) const
88 { return v.m_strKey.compare(p) < 0 ; }
90 bool operator()( char const * p, std::string const& s ) const
91 { return s.compare(p) > 0; }
93 bool operator()( char const * p, Foo const& v ) const
94 { return v.m_strKey.compare(p) > 0; }
98 Usage examples see \ref cds_intrusive_EllenBinTree_usage "here"
103 #ifdef CDS_DOXYGEN_INVOKED
104 class Traits = ellen_bintree::traits
112 typedef GC gc; ///< Garbage collector
113 typedef Key key_type; ///< type of a key to be stored in internal nodes; key is a part of \p value_type
114 typedef T value_type; ///< type of value stored in the binary tree
115 typedef Traits traits; ///< Traits template parameter
117 typedef typename traits::hook hook; ///< hook type
118 typedef typename hook::node_type node_type; ///< node type
119 typedef typename traits::disposer disposer; ///< leaf node disposer
121 typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
125 typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
126 typedef node_type leaf_node; ///< Leaf node type
127 typedef ellen_bintree::node_types< gc, key_type, typename leaf_node::tag > node_factory;
128 typedef typename node_factory::internal_node_type internal_node; ///< Internal node type
129 typedef typename node_factory::update_desc_type update_desc; ///< Update descriptor
130 typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
134 # ifdef CDS_DOXYGEN_INVOKED
135 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
136 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
138 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
139 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
141 static internal_node const& to_internal_node( tree_node const& n )
143 assert( n.is_internal() );
144 return static_cast<internal_node const&>( n );
147 static leaf_node const& to_leaf_node( tree_node const& n )
149 assert( n.is_leaf() );
150 return static_cast<leaf_node const&>( n );
155 typedef typename traits::item_counter item_counter; ///< Item counting policy
156 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model
157 typedef typename traits::stat stat; ///< internal statistics type
158 typedef typename traits::key_extractor key_extractor; ///< key extracting functor
160 typedef typename traits::node_allocator node_allocator; ///< Allocator for internal node
161 typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
165 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
167 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
168 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
170 struct search_result {
175 Guard_updGrandParent,
181 // end of guard indices
185 typedef typename gc::template GuardArray< guard_count > guard_array;
188 internal_node * pGrandParent;
189 internal_node * pParent;
191 update_ptr updParent;
192 update_ptr updGrandParent;
193 bool bRightLeaf; // true if pLeaf is right child of pParent, false otherwise
194 bool bRightParent; // true if pParent is right child of pGrandParent, false otherwise
197 :pGrandParent( nullptr )
201 ,bRightParent( false )
204 void clean_help_guards()
206 guards.clear( Guard_helpLeaf );
213 internal_node m_Root; ///< Tree root node (key= Infinite2)
214 leaf_node m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
215 leaf_node m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
218 item_counter m_ItemCounter; ///< item counter
219 mutable stat m_Stat; ///< internal statistics
223 static void free_leaf_node( value_type * p )
228 internal_node * alloc_internal_node() const
230 m_Stat.onInternalNodeCreated();
231 internal_node * pNode = cxx_node_allocator().New();
235 static void free_internal_node( internal_node * pNode )
237 cxx_node_allocator().Delete( pNode );
240 struct internal_node_deleter {
241 void operator()( internal_node * p) const
243 free_internal_node( p );
247 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
249 update_desc * alloc_update_desc() const
251 m_Stat.onUpdateDescCreated();
252 return cxx_update_desc_allocator().New();
255 static void free_update_desc( update_desc * pDesc )
257 cxx_update_desc_allocator().Delete( pDesc );
260 void retire_node( tree_node * pNode ) const
262 if ( pNode->is_leaf() ) {
263 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
264 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
266 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
269 assert( static_cast<internal_node *>( pNode ) != &m_Root );
270 m_Stat.onInternalNodeDeleted();
272 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
276 void retire_update_desc( update_desc * p ) const
278 m_Stat.onUpdateDescDeleted();
279 gc::template retire( p, free_update_desc );
282 void make_empty_tree()
284 m_Root.infinite_key( 2 );
285 m_LeafInf1.infinite_key( 1 );
286 m_LeafInf2.infinite_key( 2 );
287 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
288 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
293 /// Default constructor
296 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
308 The function inserts \p val in the tree if it does not contain
309 an item with key equal to \p val.
311 Returns \p true if \p val is placed into the tree, \p false otherwise.
313 bool insert( value_type& val )
315 return insert( val, []( value_type& ) {} );
320 This function is intended for derived non-intrusive containers.
322 The function allows to split creating of new item into two part:
323 - create item with key only
324 - insert new item into the tree
325 - if inserting is success, calls \p f functor to initialize value-field of \p val.
327 The functor signature is:
329 void func( value_type& val );
331 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
332 \p val no any other changes could be made on this tree's item by concurrent threads.
333 The user-defined functor is called only if the inserting is success.
335 template <typename Func>
336 bool insert( value_type& val, Func f )
338 typename gc::Guard guardInsert;
339 guardInsert.assign( &val );
341 unique_internal_node_ptr pNewInternal;
345 if ( search( res, val, node_compare() )) {
346 if ( pNewInternal.get() )
347 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
348 m_Stat.onInsertFailed();
352 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
354 if ( !pNewInternal.get() )
355 pNewInternal.reset( alloc_internal_node() );
357 if ( try_insert( val, pNewInternal.get(), res )) {
359 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;
408 if ( search( res, val, node_compare() )) {
409 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
410 if ( pNewInternal.get() )
411 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
412 m_Stat.onEnsureExist();
413 return std::make_pair( true, false );
416 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
418 if ( !pNewInternal.get() )
419 pNewInternal.reset( alloc_internal_node() );
421 if ( try_insert( val, pNewInternal.get(), res )) {
422 func( true, val, val );
423 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
427 m_Stat.onEnsureRetry();
431 m_Stat.onEnsureNew();
432 return std::make_pair( true, true );
435 /// Unlinks the item \p val from the tree
437 The function searches the item \p val in the tree and unlink it from the tree
438 if it is found and is equal to \p val.
440 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
441 and deletes the item found. \p unlink finds an item by key and deletes it
442 only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
444 The \p disposer specified in \p Traits class template parameter is called
445 by garbage collector \p GC asynchronously.
447 The function returns \p true if success and \p false otherwise.
449 bool unlink( value_type& val )
451 return erase_( val, node_compare(),
452 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
453 [](value_type const&) {} );
456 /// Deletes the item from the tree
457 /** \anchor cds_intrusive_EllenBinTree_erase
458 The function searches an item with key equal to \p key in the tree,
459 unlinks it from the tree, and returns \p true.
460 If the item with key equal to \p key is not found the function return \p false.
462 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
464 template <typename Q>
465 bool erase( const Q& key )
467 return erase_( key, node_compare(),
468 []( Q const&, leaf_node const& ) -> bool { return true; },
469 [](value_type const&) {} );
472 /// Delete the item from the tree with comparing functor \p pred
474 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
475 but \p pred predicate is used for key comparing.
476 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
477 "Predicate requirements".
478 \p pred must imply the same element order as the comparator used for building the tree.
480 template <typename Q, typename Less>
481 bool erase_with( const Q& key, Less pred )
483 typedef ellen_bintree::details::compare<
486 opt::details::make_comparator_from_less<Less>,
490 return erase_( key, compare_functor(),
491 []( Q const&, leaf_node const& ) -> bool { return true; },
492 [](value_type const&) {} );
495 /// Deletes the item from the tree
496 /** \anchor cds_intrusive_EllenBinTree_erase_func
497 The function searches an item with key equal to \p key in the tree,
498 call \p f functor with item found, unlinks it from the tree, and returns \p true.
499 The \ref disposer specified in \p Traits class template parameter is called
500 by garbage collector \p GC asynchronously.
502 The \p Func interface is
505 void operator()( value_type const& item );
508 The functor can be passed by reference with <tt>boost:ref</tt>
510 If the item with key equal to \p key is not found the function return \p false.
512 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
514 template <typename Q, typename Func>
515 bool erase( Q const& key, Func f )
517 return erase_( key, node_compare(),
518 []( Q const&, leaf_node const& ) -> bool { return true; },
522 /// Delete the item from the tree with comparing functor \p pred
524 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
525 but \p pred predicate is used for key comparing.
526 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
527 "Predicate requirements".
528 \p pred must imply the same element order as the comparator used for building the tree.
530 template <typename Q, typename Less, typename Func>
531 bool erase_with( Q const& key, Less pred, Func f )
533 typedef ellen_bintree::details::compare<
536 opt::details::make_comparator_from_less<Less>,
540 return erase_( key, compare_functor(),
541 []( Q const&, leaf_node const& ) -> bool { return true; },
545 /// Extracts an item with minimal key from the tree
547 The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p dest parameter.
548 If the tree is empty the function returns \p false.
550 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
551 It means that the function gets leftmost leaf of the tree and tries to unlink it.
552 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
553 So, the function returns the item with minimum key at the moment of tree traversing.
555 The guarded pointer \p dest prevents disposer invocation for returned item,
556 see cds::gc::guarded_ptr for explanation.
557 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
559 bool extract_min( guarded_ptr& dest )
561 return extract_min_( dest.guard());
564 /// Extracts an item with maximal key from the tree
566 The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p dest parameter.
567 If the tree is empty the function returns \p false.
569 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
570 It means that the function gets rightmost leaf of the tree and tries to unlink it.
571 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
572 So, the function returns the item with maximal key at the moment of tree traversing.
574 The guarded pointer \p dest prevents disposer invocation for returned item,
575 see cds::gc::guarded_ptr for explanation.
576 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
578 bool extract_max( guarded_ptr& dest )
580 return extract_max_( dest.guard() );
583 /// Extracts an item from the tree
584 /** \anchor cds_intrusive_EllenBinTree_extract
585 The function searches an item with key equal to \p key in the tree,
586 unlinks it, and returns pointer to an item found in \p dest parameter.
587 If the item is not found the function returns \p false.
589 The guarded pointer \p dest prevents disposer invocation for returned item,
590 see cds::gc::guarded_ptr for explanation.
591 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
593 template <typename Q>
594 bool extract( guarded_ptr& dest, Q const& key )
596 return extract_( dest.guard(), key );
599 /// Extracts an item from the tree using \p pred for searching
601 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(guarded_ptr& dest, Q const&)"
602 but \p pred is used for key compare.
603 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
604 "Predicate requirements".
605 \p pred must imply the same element order as the comparator used for building the tree.
607 template <typename Q, typename Less>
608 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
610 return extract_with_( dest.guard(), key, pred );
613 /// Finds the key \p key
614 /** @anchor cds_intrusive_EllenBinTree_find_val
615 The function searches the item with key equal to \p key
616 and returns \p true if it is found, and \p false otherwise.
618 Note the hash functor specified for class \p Traits template parameter
619 should accept a parameter of type \p Q that can be not the same as \p value_type.
621 template <typename Q>
622 bool find( Q const& key ) const
625 if ( search( res, key, node_compare() )) {
626 m_Stat.onFindSuccess();
630 m_Stat.onFindFailed();
634 /// Finds the key \p key with comparing functor \p pred
636 The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
637 but \p pred is used for key compare.
638 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
639 "Predicate requirements".
640 \p pred must imply the same element order as the comparator used for building the tree.
641 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
643 template <typename Q, typename Less>
644 bool find_with( Q const& key, Less pred ) const
646 typedef ellen_bintree::details::compare<
649 opt::details::make_comparator_from_less<Less>,
654 if ( search( res, key, compare_functor() )) {
655 m_Stat.onFindSuccess();
658 m_Stat.onFindFailed();
662 /// Finds the key \p key
663 /** @anchor cds_intrusive_EllenBinTree_find_func
664 The function searches the item with key equal to \p key and calls the functor \p f for item found.
665 The interface of \p Func functor is:
668 void operator()( value_type& item, Q& key );
671 where \p item is the item found, \p key is the <tt>find</tt> function argument.
673 You can pass \p f argument by value or by reference using \p std::ref.
675 The functor can change non-key fields of \p item. Note that the functor is only guarantee
676 that \p item cannot be disposed during functor is executing.
677 The functor does not serialize simultaneous access to the tree \p item. If such access is
678 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
680 The function returns \p true if \p key is found, \p false otherwise.
682 template <typename Q, typename Func>
683 bool find( Q& key, Func f ) const
685 return find_( key, f );
688 template <typename Q, typename Func>
689 bool find( Q const& key, Func f ) const
691 return find_( key, f );
695 /// Finds the key \p key with comparing functor \p pred
697 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
698 but \p pred is used for key comparison.
699 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
700 "Predicate requirements".
701 \p pred must imply the same element order as the comparator used for building the tree.
703 template <typename Q, typename Less, typename Func>
704 bool find_with( Q& key, Less pred, Func f ) const
706 return find_with_( key, pred, f );
709 template <typename Q, typename Less, typename Func>
710 bool find_with( Q const& key, Less pred, Func f ) const
712 return find_with_( key, pred, f );
716 /// Finds \p key and returns the item found
717 /** @anchor cds_intrusive_EllenBinTree_get
718 The function searches the item with key equal to \p key and returns the item found in \p dest parameter.
719 The function returns \p true if \p key is found, \p false otherwise.
721 The guarded pointer \p dest prevents disposer invocation for returned item,
722 see cds::gc::guarded_ptr for explanation.
723 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
725 template <typename Q>
726 bool get( guarded_ptr& dest, Q const& key ) const
728 return get_( dest.guard(), key );
731 /// Finds \p key with predicate \p pred and returns the item found
733 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(guarded_ptr&, Q const&)"
734 but \p pred is used for key comparing.
735 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
736 "Predicate requirements".
737 \p pred must imply the same element order as the comparator used for building the tree.
739 template <typename Q, typename Less>
740 bool get_with( guarded_ptr& dest, Q const& key, Less pred ) const
742 return get_with_( dest.guard(), key, pred );
745 /// Checks if the tree is empty
748 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
751 /// Clears the tree (thread safe, not atomic)
753 The function unlink all items from the tree.
754 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
758 assert( tree.empty() );
760 the assertion could be raised.
762 For each leaf the \p disposer will be called after unlinking.
767 while ( extract_min(gp));
770 /// Clears the tree (not thread safe)
772 This function is not thread safe and may be called only when no other thread deals with the tree.
773 The function is used in the tree destructor.
778 internal_node * pParent = nullptr;
779 internal_node * pGrandParent = nullptr;
780 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
783 while ( pLeaf->is_internal() ) {
784 pGrandParent = pParent;
785 pParent = static_cast<internal_node *>( pLeaf );
786 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
789 if ( pLeaf->infinite_key()) {
794 // Remove leftmost leaf and its parent node
795 assert( pGrandParent );
797 assert( pLeaf->is_leaf() );
799 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
800 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
801 free_internal_node( pParent );
805 /// Returns item count in the tree
807 Only leaf nodes containing user data are counted.
809 The value returned depends on item counter type provided by \p Traits template parameter.
810 If it is \p atomicity::empty_item_counter this function always returns 0.
811 The function is not suitable for checking the tree emptiness, use \p empty()
812 member function for this purpose.
816 return m_ItemCounter;
819 /// Returns const reference to internal statistics
820 stat const& statistics() const
825 /// Checks internal consistency (not atomic, not thread-safe)
827 The debugging function to check internal consistency of the tree.
829 bool check_consistency() const
831 return check_consistency( &m_Root );
837 bool check_consistency( internal_node const * pRoot ) const
839 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
840 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
844 if ( node_compare()( *pLeft, *pRoot ) < 0
845 && node_compare()( *pRoot, *pRight ) <= 0
846 && node_compare()( *pLeft, *pRight ) < 0 )
849 if ( pLeft->is_internal() )
850 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
853 if ( bRet && pRight->is_internal() )
854 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
862 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
865 tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
868 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
869 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
870 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
873 // child node is guarded
874 // See whether pParent->m_pUpdate has not been changed
875 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
876 // update has been changed - returns nullptr as a flag to search retry
880 if ( p && p->is_leaf() )
881 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
882 res.guards.clear( search_result::Guard_helpLeaf );
886 update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src ) const
889 update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
892 res.guards.assign( search_result::Guard_updParent, upd );
893 } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
897 template <typename KeyValue, typename Compare>
898 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
900 internal_node * pParent;
901 internal_node * pGrandParent = nullptr;
902 update_ptr updParent;
903 update_ptr updGrandParent;
905 bool bRightParent = false;
911 //pGrandParent = nullptr;
914 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
915 while ( pLeaf->is_internal() ) {
916 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
917 pGrandParent = pParent;
918 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
919 pParent = static_cast<internal_node *>( pLeaf );
920 bRightParent = bRightLeaf;
921 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
922 updGrandParent = updParent;
924 updParent = search_protect_update( res, pParent->m_pUpdate );
926 switch ( updParent.bits() ) {
927 case update_desc::DFlag:
928 case update_desc::Mark:
929 m_Stat.onSearchRetry();
933 nCmp = cmp( key, *pParent );
934 bRightLeaf = nCmp >= 0;
936 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
938 m_Stat.onSearchRetry();
943 assert( pLeaf->is_leaf() );
944 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
946 res.pGrandParent = pGrandParent;
947 res.pParent = pParent;
948 res.pLeaf = static_cast<leaf_node *>( pLeaf );
949 res.updParent = updParent;
950 res.updGrandParent = updGrandParent;
951 res.bRightParent = bRightParent;
952 res.bRightLeaf = bRightLeaf;
957 bool search_min( search_result& res ) const
959 internal_node * pParent;
960 internal_node * pGrandParent;
961 update_ptr updParent;
962 update_ptr updGrandParent;
966 pGrandParent = nullptr;
968 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
969 while ( pLeaf->is_internal() ) {
970 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
971 pGrandParent = pParent;
972 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
973 pParent = static_cast<internal_node *>( pLeaf );
974 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
975 updGrandParent = updParent;
977 updParent = search_protect_update( res, pParent->m_pUpdate );
979 switch ( updParent.bits() ) {
980 case update_desc::DFlag:
981 case update_desc::Mark:
982 m_Stat.onSearchRetry();
986 pLeaf = protect_child_node( res, pParent, false, updParent );
988 m_Stat.onSearchRetry();
993 if ( pLeaf->infinite_key())
996 res.pGrandParent = pGrandParent;
997 res.pParent = pParent;
998 assert( pLeaf->is_leaf() );
999 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1000 res.updParent = updParent;
1001 res.updGrandParent = updGrandParent;
1002 res.bRightParent = false;
1003 res.bRightLeaf = false;
1008 bool search_max( search_result& res ) const
1010 internal_node * pParent;
1011 internal_node * pGrandParent;
1012 update_ptr updParent;
1013 update_ptr updGrandParent;
1015 bool bRightParent = false;
1019 pGrandParent = nullptr;
1020 updParent = nullptr;
1022 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1023 while ( pLeaf->is_internal() ) {
1024 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1025 pGrandParent = pParent;
1026 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1027 pParent = static_cast<internal_node *>( pLeaf );
1028 bRightParent = bRightLeaf;
1029 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1030 updGrandParent = updParent;
1032 updParent = search_protect_update( res, pParent->m_pUpdate );
1034 switch ( updParent.bits() ) {
1035 case update_desc::DFlag:
1036 case update_desc::Mark:
1037 m_Stat.onSearchRetry();
1041 bRightLeaf = !pParent->infinite_key();
1042 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1044 m_Stat.onSearchRetry();
1049 if ( pLeaf->infinite_key())
1052 res.pGrandParent = pGrandParent;
1053 res.pParent = pParent;
1054 assert( pLeaf->is_leaf() );
1055 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1056 res.updParent = updParent;
1057 res.updGrandParent = updGrandParent;
1058 res.bRightParent = bRightParent;
1059 res.bRightLeaf = bRightLeaf;
1064 void help( update_ptr pUpdate )
1066 // pUpdate must be guarded!
1067 switch ( pUpdate.bits() ) {
1068 case update_desc::IFlag:
1069 help_insert( pUpdate.ptr() );
1070 m_Stat.onHelpInsert();
1072 case update_desc::DFlag:
1073 help_delete( pUpdate.ptr() );
1074 m_Stat.onHelpDelete();
1076 case update_desc::Mark:
1077 //m_Stat.onHelpMark();
1078 //help_marked( pUpdate.ptr() );
1083 void help_insert( update_desc * pOp )
1085 // pOp must be guarded
1087 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1088 if ( pOp->iInfo.bRightLeaf ) {
1089 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1090 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1093 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1094 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1098 update_ptr cur( pOp, update_desc::IFlag );
1099 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1100 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1103 bool check_delete_precondition( search_result& res ) const
1105 // precondition: all member of res must be guarded
1107 assert( res.pGrandParent != nullptr );
1110 static_cast<internal_node *>(
1112 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1113 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1116 static_cast<leaf_node *>(
1118 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1119 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1123 bool help_delete( update_desc * pOp )
1125 // precondition: pOp must be guarded
1127 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1128 update_ptr pMark( pOp, update_desc::Mark );
1129 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1130 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1134 retire_node( pOp->dInfo.pParent );
1135 retire_node( pOp->dInfo.pLeaf );
1136 retire_update_desc( pOp );
1139 else if ( pUpdate == pMark ) {
1140 // some other thread is processing help_marked()
1142 m_Stat.onHelpMark();
1146 // Undo grandparent dInfo
1147 update_ptr pDel( pOp, update_desc::DFlag );
1148 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1149 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1151 retire_update_desc( pOp );
1157 tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1159 typename gc::Guard guardLeaf;
1161 tree_node * pSibling;
1162 tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1165 guard.assign( static_cast<internal_node *>(p) );
1166 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1167 } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1169 if ( pSibling->is_leaf() )
1170 guard.copy( guardLeaf );
1175 void help_marked( update_desc * pOp )
1177 // precondition: pOp must be guarded
1179 tree_node * pParent = pOp->dInfo.pParent;
1181 typename gc::Guard guard;
1182 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1184 if ( pOp->dInfo.bRightParent ) {
1185 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1186 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1189 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1190 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1193 update_ptr upd( pOp, update_desc::DFlag );
1194 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1195 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1198 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1200 assert( res.updParent.bits() == update_desc::Clean );
1201 assert( res.pLeaf->is_leaf() );
1203 // check search result
1204 if ( ( res.bRightLeaf
1205 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1206 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire ) ) == res.pLeaf )
1208 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1210 int nCmp = node_compare()( val, *res.pLeaf );
1212 if ( res.pGrandParent ) {
1213 assert( !res.pLeaf->infinite_key() );
1214 pNewInternal->infinite_key( 0 );
1215 key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1218 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1219 pNewInternal->infinite_key( 1 );
1221 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1222 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1225 assert( !res.pLeaf->is_internal() );
1226 pNewInternal->infinite_key( 0 );
1228 key_extractor()( pNewInternal->m_Key, val );
1229 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1230 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1231 assert( !res.pLeaf->infinite_key());
1234 typename gc::Guard guard;
1235 update_desc * pOp = alloc_update_desc();
1236 guard.assign( pOp );
1238 pOp->iInfo.pParent = res.pParent;
1239 pOp->iInfo.pNew = pNewInternal;
1240 pOp->iInfo.pLeaf = res.pLeaf;
1241 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1243 update_ptr updCur( res.updParent.ptr() );
1244 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1245 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1249 retire_update_desc( pOp );
1253 m_Stat.onUpdateDescDeleted();
1254 free_update_desc( pOp );
1260 template <typename Q, typename Compare, typename Equal, typename Func>
1261 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1263 update_desc * pOp = nullptr;
1267 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1269 retire_update_desc( pOp );
1270 m_Stat.onEraseFailed();
1274 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1276 pOp = alloc_update_desc();
1277 if ( check_delete_precondition( res ) ) {
1278 typename gc::Guard guard;
1279 guard.assign( pOp );
1281 pOp->dInfo.pGrandParent = res.pGrandParent;
1282 pOp->dInfo.pParent = res.pParent;
1283 pOp->dInfo.pLeaf = res.pLeaf;
1284 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1285 pOp->dInfo.bRightParent = res.bRightParent;
1286 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1288 update_ptr updGP( res.updGrandParent.ptr() );
1289 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1290 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1292 if ( help_delete( pOp )) {
1293 // res.pLeaf is not deleted yet since it is guarded
1294 f( *node_traits::to_value_ptr( res.pLeaf ));
1302 m_Stat.onEraseRetry();
1306 m_Stat.onEraseSuccess();
1310 template <typename Q>
1311 bool extract_( typename gc::Guard& guard, Q const& key )
1313 return erase_( key, node_compare(),
1314 []( Q const&, leaf_node const& ) -> bool { return true; },
1315 [&guard]( value_type& found ) { guard.assign( &found ); } );
1318 template <typename Q, typename Less>
1319 bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
1321 typedef ellen_bintree::details::compare<
1324 opt::details::make_comparator_from_less<Less>,
1328 return erase_( key, compare_functor(),
1329 []( Q const&, leaf_node const& ) -> bool { return true; },
1330 [&guard]( value_type& found ) { guard.assign( &found ); } );
1333 bool extract_max_( typename gc::Guard& guard )
1335 update_desc * pOp = nullptr;
1339 if ( !search_max( res )) {
1342 retire_update_desc( pOp );
1343 m_Stat.onExtractMaxFailed();
1347 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1349 pOp = alloc_update_desc();
1350 if ( check_delete_precondition( res ) ) {
1351 typename gc::Guard guard;
1352 guard.assign( pOp );
1354 pOp->dInfo.pGrandParent = res.pGrandParent;
1355 pOp->dInfo.pParent = res.pParent;
1356 pOp->dInfo.pLeaf = res.pLeaf;
1357 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1358 pOp->dInfo.bRightParent = res.bRightParent;
1359 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1361 update_ptr updGP( res.updGrandParent.ptr() );
1362 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1363 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1365 if ( help_delete( pOp ))
1372 m_Stat.onExtractMaxRetry();
1376 m_Stat.onExtractMaxSuccess();
1377 guard.assign( node_traits::to_value_ptr( res.pLeaf ) );
1381 bool extract_min_( typename gc::Guard& guard )
1383 update_desc * pOp = nullptr;
1387 if ( !search_min( res )) {
1390 retire_update_desc( pOp );
1391 m_Stat.onExtractMinFailed();
1395 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1397 pOp = alloc_update_desc();
1398 if ( check_delete_precondition( res ) ) {
1399 typename gc::Guard guard;
1400 guard.assign( pOp );
1402 pOp->dInfo.pGrandParent = res.pGrandParent;
1403 pOp->dInfo.pParent = res.pParent;
1404 pOp->dInfo.pLeaf = res.pLeaf;
1405 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1406 pOp->dInfo.bRightParent = res.bRightParent;
1407 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1409 update_ptr updGP( res.updGrandParent.ptr() );
1410 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1411 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1413 if ( help_delete( pOp ))
1420 m_Stat.onExtractMinRetry();
1424 m_Stat.onExtractMinSuccess();
1425 guard.assign( node_traits::to_value_ptr( res.pLeaf ));
1429 template <typename Q, typename Func>
1430 bool find_( Q& val, Func f ) const
1433 if ( search( res, val, node_compare() )) {
1434 assert( res.pLeaf );
1435 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1437 m_Stat.onFindSuccess();
1441 m_Stat.onFindFailed();
1445 template <typename Q, typename Less, typename Func>
1446 bool find_with_( Q& val, Less pred, Func f ) const
1448 typedef ellen_bintree::details::compare<
1451 opt::details::make_comparator_from_less<Less>,
1456 if ( search( res, val, compare_functor() )) {
1457 assert( res.pLeaf );
1458 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1460 m_Stat.onFindSuccess();
1464 m_Stat.onFindFailed();
1468 template <typename Q>
1469 bool get_( typename gc::Guard& guard, Q const& val ) const
1471 return find_( val, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1474 template <typename Q, typename Less>
1475 bool get_with_( typename gc::Guard& guard, Q const& val, Less pred ) const
1477 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1483 }} // namespace cds::intrusive
1485 #endif // #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H