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>
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
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;
346 if ( search( res, val, node_compare() )) {
347 if ( pNewInternal.get() )
348 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
349 m_Stat.onInsertFailed();
353 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
355 if ( !pNewInternal.get() )
356 pNewInternal.reset( alloc_internal_node() );
358 if ( try_insert( val, pNewInternal.get(), res )) {
360 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
366 m_Stat.onInsertRetry();
370 m_Stat.onInsertSuccess();
374 /// Ensures that the \p val exists in the tree
376 The operation performs inserting or changing data with lock-free manner.
378 If the item \p val is not found in the tree, then \p val is inserted into the tree.
379 Otherwise, the functor \p func is called with item found.
380 The functor signature is:
382 void func( bool bNew, value_type& item, value_type& val );
385 - \p bNew - \p true if the item has been inserted, \p false otherwise
386 - \p item - an item of the tree
387 - \p val - the argument \p val passed to the \p ensure function
388 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
389 refer to the same thing.
391 The functor can change non-key fields of the \p item; however, \p func must guarantee
392 that during changing no any other modifications could be made on this item by concurrent threads.
394 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
395 \p second is \p true if new item has been added or \p false if the item with \p key
396 already is in the tree.
398 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
400 template <typename Func>
401 std::pair<bool, bool> ensure( value_type& val, Func func )
403 typename gc::Guard guardInsert;
404 guardInsert.assign( &val );
406 unique_internal_node_ptr pNewInternal;
411 if ( search( res, val, node_compare() )) {
412 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
413 if ( pNewInternal.get() )
414 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
415 m_Stat.onEnsureExist();
416 return std::make_pair( true, false );
419 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
421 if ( !pNewInternal.get() )
422 pNewInternal.reset( alloc_internal_node() );
424 if ( try_insert( val, pNewInternal.get(), res )) {
425 func( true, val, val );
426 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
432 m_Stat.onEnsureRetry();
436 m_Stat.onEnsureNew();
437 return std::make_pair( true, true );
440 /// Unlinks the item \p val from the tree
442 The function searches the item \p val in the tree and unlink it from the tree
443 if it is found and is equal to \p val.
445 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
446 and deletes the item found. \p unlink finds an item by key and deletes it
447 only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
449 The \p disposer specified in \p Traits class template parameter is called
450 by garbage collector \p GC asynchronously.
452 The function returns \p true if success and \p false otherwise.
454 bool unlink( value_type& val )
456 return erase_( val, node_compare(),
457 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
458 [](value_type const&) {} );
461 /// Deletes the item from the tree
462 /** \anchor cds_intrusive_EllenBinTree_erase
463 The function searches an item with key equal to \p key in the tree,
464 unlinks it from the tree, and returns \p true.
465 If the item with key equal to \p key is not found the function return \p false.
467 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
469 template <typename Q>
470 bool erase( const Q& key )
472 return erase_( key, node_compare(),
473 []( Q const&, leaf_node const& ) -> bool { return true; },
474 [](value_type const&) {} );
477 /// Delete the item from the tree with comparing functor \p pred
479 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
480 but \p pred predicate is used for key comparing.
481 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
482 "Predicate requirements".
483 \p pred must imply the same element order as the comparator used for building the tree.
485 template <typename Q, typename Less>
486 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 )
539 typedef ellen_bintree::details::compare<
542 opt::details::make_comparator_from_less<Less>,
546 return erase_( key, compare_functor(),
547 []( Q const&, leaf_node const& ) -> bool { return true; },
551 /// Extracts an item with minimal key from the tree
553 The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
554 If the tree is empty the function returns an empty guarded pointer.
556 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
557 It means that the function gets leftmost leaf of the tree and tries to unlink it.
558 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
559 So, the function returns the item with minimum key at the moment of tree traversing.
561 The returned \p guarded_ptr prevents disposer invocation for returned item,
562 see \p cds::gc::guarded_ptr for explanation.
563 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
565 guarded_ptr extract_min()
568 extract_min_( gp.guard() );
572 /// Extracts an item with maximal key from the tree
574 The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
575 If the tree is empty the function returns an empty \p guarded_ptr.
577 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
578 It means that the function gets rightmost leaf of the tree and tries to unlink it.
579 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
580 So, the function returns the item with maximal key at the moment of tree traversing.
582 The returned \p guarded_ptr prevents disposer invocation for returned item,
583 see cds::gc::guarded_ptr for explanation.
584 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
586 guarded_ptr extract_max()
589 extract_max_( gp.guard());
593 /// Extracts an item from the tree
594 /** \anchor cds_intrusive_EllenBinTree_extract
595 The function searches an item with key equal to \p key in the tree,
596 unlinks it, and returns a guarded pointer to an item found.
597 If the item is not found the function returns an empty \p guarded_ptr.
599 \p guarded_ptr prevents disposer invocation for returned item,
600 see cds::gc::guarded_ptr for explanation.
601 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
603 template <typename Q>
604 guarded_ptr extract( Q const& key )
607 extract_( gp.guard(), key );
611 /// Extracts an item from the tree using \p pred for searching
613 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
614 but \p pred is used for key compare.
615 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
616 "Predicate requirements".
617 \p pred must imply the same element order as the comparator used for building the tree.
619 template <typename Q, typename Less>
620 guarded_ptr extract_with( Q const& key, Less pred )
623 extract_with_( gp.guard(), key, pred );
627 /// Finds the key \p key
628 /** @anchor cds_intrusive_EllenBinTree_find_val
629 The function searches the item with key equal to \p key
630 and returns \p true if it is found, and \p false otherwise.
632 Note the hash functor specified for class \p Traits template parameter
633 should accept a parameter of type \p Q that can be not the same as \p value_type.
635 template <typename Q>
636 bool find( Q const& key ) const
639 if ( search( res, key, node_compare() )) {
640 m_Stat.onFindSuccess();
644 m_Stat.onFindFailed();
648 /// Finds the key \p key with comparing functor \p pred
650 The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
651 but \p pred is used for key compare.
652 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
653 "Predicate requirements".
654 \p pred must imply the same element order as the comparator used for building the tree.
655 \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
657 template <typename Q, typename Less>
658 bool find_with( Q const& key, Less pred ) const
661 typedef ellen_bintree::details::compare<
664 opt::details::make_comparator_from_less<Less>,
669 if ( search( res, key, compare_functor() )) {
670 m_Stat.onFindSuccess();
673 m_Stat.onFindFailed();
677 /// Finds the key \p key
678 /** @anchor cds_intrusive_EllenBinTree_find_func
679 The function searches the item with key equal to \p key and calls the functor \p f for item found.
680 The interface of \p Func functor is:
683 void operator()( value_type& item, Q& key );
686 where \p item is the item found, \p key is the <tt>find</tt> function argument.
688 The functor can change non-key fields of \p item. Note that the functor is only guarantee
689 that \p item cannot be disposed during functor is executing.
690 The functor does not serialize simultaneous access to the tree \p item. If such access is
691 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
693 The function returns \p true if \p key is found, \p false otherwise.
695 template <typename Q, typename Func>
696 bool find( Q& key, Func f ) const
698 return find_( key, f );
701 template <typename Q, typename Func>
702 bool find( Q const& key, Func f ) const
704 return find_( key, f );
708 /// Finds the key \p key with comparing functor \p pred
710 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
711 but \p pred is used for key comparison.
712 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
713 "Predicate requirements".
714 \p pred must imply the same element order as the comparator used for building the tree.
716 template <typename Q, typename Less, typename Func>
717 bool find_with( Q& key, Less pred, Func f ) const
719 return find_with_( key, pred, f );
722 template <typename Q, typename Less, typename Func>
723 bool find_with( Q const& key, Less pred, Func f ) const
725 return find_with_( key, pred, f );
729 /// Finds \p key and returns the item found
730 /** @anchor cds_intrusive_EllenBinTree_get
731 The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
732 The function returns an empty guarded pointer is \p key is not found.
734 \p guarded_ptr prevents disposer invocation for returned item,
735 see \p cds::gc::guarded_ptr for explanation.
736 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
738 template <typename Q>
739 guarded_ptr get( Q const& key ) const
742 get_( gp.guard(), key );
746 /// Finds \p key with predicate \p pred and returns the item found
748 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
749 but \p pred is used for key comparing.
750 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
751 "Predicate requirements".
752 \p pred must imply the same element order as the comparator used for building the tree.
754 template <typename Q, typename Less>
755 guarded_ptr get_with( Q const& key, Less pred ) const
758 get_with_( gp.guard(), key, pred );
762 /// Checks if the tree is empty
765 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
768 /// Clears the tree (thread safe, not atomic)
770 The function unlink all items from the tree.
771 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
775 assert( tree.empty() );
777 the assertion could be raised.
779 For each leaf the \p disposer will be called after unlinking.
789 /// Clears the tree (not thread safe)
791 This function is not thread safe and may be called only when no other thread deals with the tree.
792 The function is used in the tree destructor.
797 internal_node * pParent = nullptr;
798 internal_node * pGrandParent = nullptr;
799 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
802 while ( pLeaf->is_internal() ) {
803 pGrandParent = pParent;
804 pParent = static_cast<internal_node *>( pLeaf );
805 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
808 if ( pLeaf->infinite_key()) {
813 // Remove leftmost leaf and its parent node
814 assert( pGrandParent );
816 assert( pLeaf->is_leaf() );
818 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
819 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
820 free_internal_node( pParent );
824 /// Returns item count in the tree
826 Only leaf nodes containing user data are counted.
828 The value returned depends on item counter type provided by \p Traits template parameter.
829 If it is \p atomicity::empty_item_counter this function always returns 0.
830 The function is not suitable for checking the tree emptiness, use \p empty()
831 member function for this purpose.
835 return m_ItemCounter;
838 /// Returns const reference to internal statistics
839 stat const& statistics() const
844 /// Checks internal consistency (not atomic, not thread-safe)
846 The debugging function to check internal consistency of the tree.
848 bool check_consistency() const
850 return check_consistency( &m_Root );
856 bool check_consistency( internal_node const * pRoot ) const
858 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
859 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
863 if ( node_compare()( *pLeft, *pRoot ) < 0
864 && node_compare()( *pRoot, *pRight ) <= 0
865 && node_compare()( *pLeft, *pRight ) < 0 )
868 if ( pLeft->is_internal() )
869 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
872 if ( bRet && pRight->is_internal() )
873 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
881 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
884 tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
887 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
888 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
889 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
892 // child node is guarded
893 // See whether pParent->m_pUpdate has not been changed
894 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
895 // update has been changed - returns nullptr as a flag to search retry
899 if ( p && p->is_leaf() )
900 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
901 res.guards.clear( search_result::Guard_helpLeaf );
905 update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src ) const
908 update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
911 res.guards.assign( search_result::Guard_updParent, upd );
912 } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
916 template <typename KeyValue, typename Compare>
917 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
919 internal_node * pParent;
920 internal_node * pGrandParent = nullptr;
921 update_ptr updParent;
922 update_ptr updGrandParent;
924 bool bRightParent = false;
930 //pGrandParent = nullptr;
933 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
934 while ( pLeaf->is_internal() ) {
935 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
936 pGrandParent = pParent;
937 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
938 pParent = static_cast<internal_node *>( pLeaf );
939 bRightParent = bRightLeaf;
940 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
941 updGrandParent = updParent;
943 updParent = search_protect_update( res, pParent->m_pUpdate );
945 switch ( updParent.bits() ) {
946 case update_desc::DFlag:
947 case update_desc::Mark:
948 m_Stat.onSearchRetry();
952 nCmp = cmp( key, *pParent );
953 bRightLeaf = nCmp >= 0;
955 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
957 m_Stat.onSearchRetry();
962 assert( pLeaf->is_leaf() );
963 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
965 res.pGrandParent = pGrandParent;
966 res.pParent = pParent;
967 res.pLeaf = static_cast<leaf_node *>( pLeaf );
968 res.updParent = updParent;
969 res.updGrandParent = updGrandParent;
970 res.bRightParent = bRightParent;
971 res.bRightLeaf = bRightLeaf;
976 bool search_min( search_result& res ) const
978 internal_node * pParent;
979 internal_node * pGrandParent;
980 update_ptr updParent;
981 update_ptr updGrandParent;
985 pGrandParent = nullptr;
987 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
988 while ( pLeaf->is_internal() ) {
989 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
990 pGrandParent = pParent;
991 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
992 pParent = static_cast<internal_node *>( pLeaf );
993 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
994 updGrandParent = updParent;
996 updParent = search_protect_update( res, pParent->m_pUpdate );
998 switch ( updParent.bits() ) {
999 case update_desc::DFlag:
1000 case update_desc::Mark:
1001 m_Stat.onSearchRetry();
1005 pLeaf = protect_child_node( res, pParent, false, updParent );
1007 m_Stat.onSearchRetry();
1012 if ( pLeaf->infinite_key())
1015 res.pGrandParent = pGrandParent;
1016 res.pParent = pParent;
1017 assert( pLeaf->is_leaf() );
1018 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1019 res.updParent = updParent;
1020 res.updGrandParent = updGrandParent;
1021 res.bRightParent = false;
1022 res.bRightLeaf = false;
1027 bool search_max( search_result& res ) const
1029 internal_node * pParent;
1030 internal_node * pGrandParent;
1031 update_ptr updParent;
1032 update_ptr updGrandParent;
1034 bool bRightParent = false;
1038 pGrandParent = nullptr;
1039 updParent = nullptr;
1041 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1042 while ( pLeaf->is_internal() ) {
1043 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1044 pGrandParent = pParent;
1045 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1046 pParent = static_cast<internal_node *>( pLeaf );
1047 bRightParent = bRightLeaf;
1048 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1049 updGrandParent = updParent;
1051 updParent = search_protect_update( res, pParent->m_pUpdate );
1053 switch ( updParent.bits() ) {
1054 case update_desc::DFlag:
1055 case update_desc::Mark:
1056 m_Stat.onSearchRetry();
1060 bRightLeaf = !pParent->infinite_key();
1061 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1063 m_Stat.onSearchRetry();
1068 if ( pLeaf->infinite_key())
1071 res.pGrandParent = pGrandParent;
1072 res.pParent = pParent;
1073 assert( pLeaf->is_leaf() );
1074 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1075 res.updParent = updParent;
1076 res.updGrandParent = updGrandParent;
1077 res.bRightParent = bRightParent;
1078 res.bRightLeaf = bRightLeaf;
1084 void help( update_ptr pUpdate )
1086 // pUpdate must be guarded!
1087 switch ( pUpdate.bits() ) {
1088 case update_desc::IFlag:
1089 help_insert( pUpdate.ptr() );
1090 m_Stat.onHelpInsert();
1092 case update_desc::DFlag:
1093 help_delete( pUpdate.ptr() );
1094 m_Stat.onHelpDelete();
1096 case update_desc::Mark:
1097 //m_Stat.onHelpMark();
1098 //help_marked( pUpdate.ptr() );
1104 void help_insert( update_desc * pOp )
1106 // pOp must be guarded
1108 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1109 if ( pOp->iInfo.bRightLeaf ) {
1110 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1111 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1114 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1115 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1119 update_ptr cur( pOp, update_desc::IFlag );
1120 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1121 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1124 bool check_delete_precondition( search_result& res ) const
1126 // precondition: all member of res must be guarded
1128 assert( res.pGrandParent != nullptr );
1131 static_cast<internal_node *>(
1133 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1134 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1137 static_cast<leaf_node *>(
1139 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1140 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1144 bool help_delete( update_desc * pOp )
1146 // precondition: pOp must be guarded
1148 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1149 update_ptr pMark( pOp, update_desc::Mark );
1150 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1151 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1155 retire_node( pOp->dInfo.pParent );
1156 retire_node( pOp->dInfo.pLeaf );
1157 retire_update_desc( pOp );
1160 else if ( pUpdate == pMark ) {
1161 // some other thread is processing help_marked()
1163 m_Stat.onHelpMark();
1167 // Undo grandparent dInfo
1168 update_ptr pDel( pOp, update_desc::DFlag );
1169 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1170 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1172 retire_update_desc( pOp );
1178 tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1180 typename gc::Guard guardLeaf;
1182 tree_node * pSibling;
1183 tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1186 guard.assign( static_cast<internal_node *>(p) );
1187 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1188 } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1190 if ( pSibling->is_leaf() )
1191 guard.copy( guardLeaf );
1196 void help_marked( update_desc * pOp )
1198 // precondition: pOp must be guarded
1200 tree_node * pParent = pOp->dInfo.pParent;
1202 typename gc::Guard guard;
1203 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1205 if ( pOp->dInfo.bRightParent ) {
1206 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1207 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1210 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1211 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1214 update_ptr upd( pOp, update_desc::DFlag );
1215 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1216 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1219 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1221 assert( res.updParent.bits() == update_desc::Clean );
1222 assert( res.pLeaf->is_leaf() );
1224 // check search result
1225 if ( (res.bRightLeaf
1226 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1227 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire )) == res.pLeaf ) {
1228 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1230 int nCmp = node_compare()(val, *res.pLeaf);
1232 if ( res.pGrandParent ) {
1233 assert( !res.pLeaf->infinite_key() );
1234 pNewInternal->infinite_key( 0 );
1235 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1238 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1239 pNewInternal->infinite_key( 1 );
1241 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1242 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1245 assert( !res.pLeaf->is_internal() );
1246 pNewInternal->infinite_key( 0 );
1248 key_extractor()(pNewInternal->m_Key, val);
1249 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1250 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1251 assert( !res.pLeaf->infinite_key() );
1254 typename gc::Guard guard;
1255 update_desc * pOp = alloc_update_desc();
1256 guard.assign( pOp );
1258 pOp->iInfo.pParent = res.pParent;
1259 pOp->iInfo.pNew = pNewInternal;
1260 pOp->iInfo.pLeaf = res.pLeaf;
1261 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1263 update_ptr updCur( res.updParent.ptr() );
1264 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1265 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1268 retire_update_desc( pOp );
1272 m_Stat.onUpdateDescDeleted();
1273 free_update_desc( pOp );
1280 template <typename Q, typename Compare, typename Equal, typename Func>
1281 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1283 update_desc * pOp = nullptr;
1288 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1290 retire_update_desc( pOp );
1291 m_Stat.onEraseFailed();
1295 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1297 pOp = alloc_update_desc();
1298 if ( check_delete_precondition( res ) ) {
1299 typename gc::Guard guard;
1300 guard.assign( pOp );
1302 pOp->dInfo.pGrandParent = res.pGrandParent;
1303 pOp->dInfo.pParent = res.pParent;
1304 pOp->dInfo.pLeaf = res.pLeaf;
1305 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1306 pOp->dInfo.bRightParent = res.bRightParent;
1307 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1309 update_ptr updGP( res.updGrandParent.ptr() );
1310 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1311 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1312 if ( help_delete( pOp ) ) {
1313 // res.pLeaf is not deleted yet since it is guarded
1314 f( *node_traits::to_value_ptr( res.pLeaf ) );
1323 m_Stat.onEraseRetry();
1327 m_Stat.onEraseSuccess();
1331 template <typename Q>
1332 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
1334 return erase_( key, node_compare(),
1335 []( Q const&, leaf_node const& ) -> bool { return true; },
1336 [&guard]( value_type& found ) { guard.set( &found ); } );
1339 template <typename Q, typename Less>
1340 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less pred )
1343 typedef ellen_bintree::details::compare<
1346 opt::details::make_comparator_from_less<Less>,
1350 return erase_( key, compare_functor(),
1351 []( Q const&, leaf_node const& ) -> bool { return true; },
1352 [&guard]( value_type& found ) { guard.set( &found ); } );
1355 bool extract_max_( typename guarded_ptr::native_guard& gp )
1357 update_desc * pOp = nullptr;
1362 if ( !search_max( res )) {
1365 retire_update_desc( pOp );
1366 m_Stat.onExtractMaxFailed();
1370 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1372 pOp = alloc_update_desc();
1373 if ( check_delete_precondition( res ) ) {
1374 typename gc::Guard guard;
1375 guard.assign( pOp );
1377 pOp->dInfo.pGrandParent = res.pGrandParent;
1378 pOp->dInfo.pParent = res.pParent;
1379 pOp->dInfo.pLeaf = res.pLeaf;
1380 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1381 pOp->dInfo.bRightParent = res.bRightParent;
1382 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1384 update_ptr updGP( res.updGrandParent.ptr() );
1385 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1386 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1388 if ( help_delete( pOp ) )
1396 m_Stat.onExtractMaxRetry();
1400 m_Stat.onExtractMaxSuccess();
1401 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1405 bool extract_min_( typename guarded_ptr::native_guard& gp )
1407 update_desc * pOp = nullptr;
1412 if ( !search_min( res )) {
1415 retire_update_desc( pOp );
1416 m_Stat.onExtractMinFailed();
1420 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1422 pOp = alloc_update_desc();
1423 if ( check_delete_precondition( res ) ) {
1424 typename gc::Guard guard;
1425 guard.assign( pOp );
1427 pOp->dInfo.pGrandParent = res.pGrandParent;
1428 pOp->dInfo.pParent = res.pParent;
1429 pOp->dInfo.pLeaf = res.pLeaf;
1430 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1431 pOp->dInfo.bRightParent = res.bRightParent;
1432 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1434 update_ptr updGP( res.updGrandParent.ptr() );
1435 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1436 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1438 if ( help_delete( pOp ))
1446 m_Stat.onExtractMinRetry();
1450 m_Stat.onExtractMinSuccess();
1451 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1455 template <typename Q, typename Func>
1456 bool find_( Q& val, Func f ) const
1459 if ( search( res, val, node_compare() )) {
1460 assert( res.pLeaf );
1461 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1463 m_Stat.onFindSuccess();
1467 m_Stat.onFindFailed();
1471 template <typename Q, typename Less, typename Func>
1472 bool find_with_( Q& val, Less pred, Func f ) const
1475 typedef ellen_bintree::details::compare<
1478 opt::details::make_comparator_from_less<Less>,
1483 if ( search( res, val, compare_functor() )) {
1484 assert( res.pLeaf );
1485 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1487 m_Stat.onFindSuccess();
1491 m_Stat.onFindFailed();
1495 template <typename Q>
1496 bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
1498 return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1501 template <typename Q, typename Less>
1502 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
1504 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1510 }} // namespace cds::intrusive
1512 #endif // #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H