3 #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H
4 #define CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H
7 #include <cds/intrusive/details/ellen_bintree_base.h>
8 #include <cds/opt/compare.h>
9 #include <cds/details/binary_functor_wrapper.h>
10 #include <cds/urcu/details/check_deadlock.h>
12 namespace cds { namespace intrusive {
14 /// Ellen's et al binary search tree
15 /** @ingroup cds_intrusive_map
16 @ingroup cds_intrusive_tree
17 @anchor cds_intrusive_EllenBinTree
20 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
22 %EllenBinTree is an <i>unbalanced</i> leaf-oriented binary search tree that implements the <i>set</i>
23 abstract data type. Nodes maintains child pointers but not parent pointers.
24 Every internal node has exactly two children, and all data of type \p T currently in
25 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find()
26 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
27 may or may not be in the set. \p Key type is a subset of \p T type.
28 There should be exactly defined a key extracting functor for converting object of type \p T to
29 object of type \p Key.
31 Due to \p extract_min() and \p extract_max() member functions the \p %EllenBinTree can act as
32 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
33 the priority value plus some uniformly distributed random value.
35 @note In the current implementation we do not use helping technique described in the original paper.
36 In Hazard Pointer schema helping is too complicated and does not give any observable benefits.
37 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
38 the operation done. Such solution allows greatly simplify the implementation of tree.
40 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
41 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
43 @note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
44 There are header file for each GC type:
45 - <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC \p cds::gc::HP
46 - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Dynamic Hazard Pointer GC \p cds::gc::DHP
47 - <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
49 <b>Template arguments</b> :
50 - \p GC - garbage collector, possible types are cds::gc::HP, cds::gc::DHP.
51 - \p Key - key type, a subset of \p T
52 - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
53 (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
54 (for \p ellen_bintree::member_hook).
55 - \p Traits - tree traits, default is \p ellen_bintree::traits
56 It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
57 instead of \p Traits template argument.
59 @anchor cds_intrusive_EllenBinTree_less
60 <b>Predicate requirements</b>
62 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
63 of type \p T and \p Key in any combination.
64 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
66 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
73 bool operator()( Foo const& v1, Foo const& v2 ) const
74 { return v1.m_strKey < v2.m_strKey ; }
76 bool operator()( Foo const& v, std::string const& s ) const
77 { return v.m_strKey < s ; }
79 bool operator()( std::string const& s, Foo const& v ) const
80 { return s < v.m_strKey ; }
82 // Support comparing std::string and char const *
83 bool operator()( std::string const& s, char const * p ) const
84 { return s.compare(p) < 0 ; }
86 bool operator()( Foo const& v, char const * p ) const
87 { return v.m_strKey.compare(p) < 0 ; }
89 bool operator()( char const * p, std::string const& s ) const
90 { return s.compare(p) > 0; }
92 bool operator()( char const * p, Foo const& v ) const
93 { return v.m_strKey.compare(p) > 0; }
97 Usage examples see \ref cds_intrusive_EllenBinTree_usage "here"
102 #ifdef CDS_DOXYGEN_INVOKED
103 class Traits = ellen_bintree::traits
111 typedef GC gc; ///< Garbage collector
112 typedef Key key_type; ///< type of a key to be stored in internal nodes; key is a part of \p value_type
113 typedef T value_type; ///< type of value stored in the binary tree
114 typedef Traits traits; ///< Traits template parameter
116 typedef typename traits::hook hook; ///< hook type
117 typedef typename hook::node_type node_type; ///< node type
118 typedef typename traits::disposer disposer; ///< leaf node disposer
119 typedef typename traits::back_off back_off; ///< back-off strategy
121 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
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
163 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 8; ///< Count of hazard pointer required for the algorithm
167 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
169 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
170 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
172 struct search_result {
177 Guard_updGrandParent,
180 // end of guard indices
184 typedef typename gc::template GuardArray< guard_count > guard_array;
187 internal_node * pGrandParent;
188 internal_node * pParent;
190 update_ptr updParent;
191 update_ptr updGrandParent;
192 bool bRightLeaf; // true if pLeaf is right child of pParent, false otherwise
193 bool bRightParent; // true if pParent is right child of pGrandParent, false otherwise
196 :pGrandParent( nullptr )
200 ,bRightParent( false )
207 internal_node m_Root; ///< Tree root node (key= Infinite2)
208 leaf_node m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
209 leaf_node m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
212 item_counter m_ItemCounter; ///< item counter
213 mutable stat m_Stat; ///< internal statistics
217 static void free_leaf_node( value_type * p )
222 internal_node * alloc_internal_node() const
224 m_Stat.onInternalNodeCreated();
225 internal_node * pNode = cxx_node_allocator().New();
229 static void free_internal_node( internal_node * pNode )
231 cxx_node_allocator().Delete( pNode );
234 struct internal_node_deleter {
235 void operator()( internal_node * p) const
237 free_internal_node( p );
241 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
243 update_desc * alloc_update_desc() const
245 m_Stat.onUpdateDescCreated();
246 return cxx_update_desc_allocator().New();
249 static void free_update_desc( update_desc * pDesc )
251 cxx_update_desc_allocator().Delete( pDesc );
254 void retire_node( tree_node * pNode ) const
256 if ( pNode->is_leaf() ) {
257 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
258 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
260 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
263 assert( static_cast<internal_node *>( pNode ) != &m_Root );
264 m_Stat.onInternalNodeDeleted();
266 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
270 void retire_update_desc( update_desc * p ) const
272 m_Stat.onUpdateDescDeleted();
273 gc::template retire( p, free_update_desc );
276 void make_empty_tree()
278 m_Root.infinite_key( 2 );
279 m_LeafInf1.infinite_key( 1 );
280 m_LeafInf2.infinite_key( 2 );
281 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
282 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
287 /// Default constructor
290 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
302 The function inserts \p val in the tree if it does not contain
303 an item with key equal to \p val.
305 Returns \p true if \p val is placed into the tree, \p false otherwise.
307 bool insert( value_type& val )
309 return insert( val, []( value_type& ) {} );
314 This function is intended for derived non-intrusive containers.
316 The function allows to split creating of new item into two part:
317 - create item with key only
318 - insert new item into the tree
319 - if inserting is success, calls \p f functor to initialize value-field of \p val.
321 The functor signature is:
323 void func( value_type& val );
325 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
326 \p val no any other changes could be made on this tree's item by concurrent threads.
327 The user-defined functor is called only if the inserting is success.
329 template <typename Func>
330 bool insert( value_type& val, Func f )
332 typename gc::Guard guardInsert;
333 guardInsert.assign( &val );
335 unique_internal_node_ptr pNewInternal;
340 if ( search( res, val, node_compare() )) {
341 if ( pNewInternal.get() )
342 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
343 m_Stat.onInsertFailed();
347 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
349 if ( !pNewInternal.get() )
350 pNewInternal.reset( alloc_internal_node() );
352 if ( try_insert( val, pNewInternal.get(), res )) {
354 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
360 m_Stat.onInsertRetry();
364 m_Stat.onInsertSuccess();
370 The operation performs inserting or changing data with lock-free manner.
372 If the item \p val is not found in the set, then \p val is inserted into the set
373 iff \p bAllowInsert is \p true.
374 Otherwise, the functor \p func is called with item found.
375 The functor \p func signature is:
377 void func( bool bNew, value_type& item, value_type& val );
380 - \p bNew - \p true if the item has been inserted, \p false otherwise
381 - \p item - item of the set
382 - \p val - argument \p val passed into the \p %update() function
383 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
384 refer to the same thing.
386 The functor can change non-key fields of the \p item; however, \p func must guarantee
387 that during changing no any other modifications could be made on this item by concurrent threads.
389 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
390 i.e. the node has been inserted or updated,
391 \p second is \p true if new item has been added or \p false if the item with \p key
394 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
396 template <typename Func>
397 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
399 typename gc::Guard guardInsert;
400 guardInsert.assign( &val );
402 unique_internal_node_ptr pNewInternal;
407 if ( search( res, val, node_compare() )) {
408 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
409 if ( pNewInternal.get() )
410 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
411 m_Stat.onEnsureExist();
412 return std::make_pair( true, false );
415 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
417 return std::make_pair( false, false );
419 if ( !pNewInternal.get() )
420 pNewInternal.reset( alloc_internal_node() );
422 if ( try_insert( val, pNewInternal.get(), res )) {
423 func( true, val, val );
424 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
430 m_Stat.onEnsureRetry();
434 m_Stat.onEnsureNew();
435 return std::make_pair( true, true );
438 template <typename Func>
439 CDS_DEPRECATED("ensure() is deprecated, use update()")
440 std::pair<bool, bool> ensure( value_type& val, Func func )
442 return update( val, func, true );
446 /// Unlinks the item \p val from the tree
448 The function searches the item \p val in the tree and unlink it from the tree
449 if it is found and is equal to \p val.
451 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
452 and deletes the item found. \p unlink finds an item by key and deletes it
453 only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
455 The \p disposer specified in \p Traits class template parameter is called
456 by garbage collector \p GC asynchronously.
458 The function returns \p true if success and \p false otherwise.
460 bool unlink( value_type& val )
462 return erase_( val, node_compare(),
463 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
464 [](value_type const&) {} );
467 /// Deletes the item from the tree
468 /** \anchor cds_intrusive_EllenBinTree_erase
469 The function searches an item with key equal to \p key in the tree,
470 unlinks it from the tree, and returns \p true.
471 If the item with key equal to \p key is not found the function return \p false.
473 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
475 template <typename Q>
476 bool erase( const Q& key )
478 return erase_( key, node_compare(),
479 []( Q const&, leaf_node const& ) -> bool { return true; },
480 [](value_type const&) {} );
483 /// Delete the item from the tree with comparing functor \p pred
485 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
486 but \p pred predicate is used for key comparing.
487 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
488 "Predicate requirements".
489 \p pred must imply the same element order as the comparator used for building the tree.
491 template <typename Q, typename Less>
492 bool erase_with( const Q& key, Less pred )
495 typedef ellen_bintree::details::compare<
498 opt::details::make_comparator_from_less<Less>,
502 return erase_( key, compare_functor(),
503 []( Q const&, leaf_node const& ) -> bool { return true; },
504 [](value_type const&) {} );
507 /// Deletes the item from the tree
508 /** \anchor cds_intrusive_EllenBinTree_erase_func
509 The function searches an item with key equal to \p key in the tree,
510 call \p f functor with item found, unlinks it from the tree, and returns \p true.
511 The \ref disposer specified in \p Traits class template parameter is called
512 by garbage collector \p GC asynchronously.
514 The \p Func interface is
517 void operator()( value_type const& item );
521 If the item with key equal to \p key is not found the function return \p false.
523 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
525 template <typename Q, typename Func>
526 bool erase( Q const& key, Func f )
528 return erase_( key, node_compare(),
529 []( Q const&, leaf_node const& ) -> bool { return true; },
533 /// Delete the item from the tree with comparing functor \p pred
535 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
536 but \p pred predicate is used for key comparing.
537 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
538 "Predicate requirements".
539 \p pred must imply the same element order as the comparator used for building the tree.
541 template <typename Q, typename Less, typename Func>
542 bool erase_with( Q const& key, Less pred, Func f )
545 typedef ellen_bintree::details::compare<
548 opt::details::make_comparator_from_less<Less>,
552 return erase_( key, compare_functor(),
553 []( Q const&, leaf_node const& ) -> bool { return true; },
557 /// Extracts an item with minimal key from the tree
559 The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
560 If the tree is empty the function returns an empty guarded pointer.
562 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
563 It means that the function gets leftmost leaf of the tree and tries to unlink it.
564 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
565 So, the function returns the item with minimum key at the moment of tree traversing.
567 The returned \p guarded_ptr prevents disposer invocation for returned item,
568 see \p cds::gc::guarded_ptr for explanation.
569 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
571 guarded_ptr extract_min()
574 extract_min_( gp.guard() );
578 /// Extracts an item with maximal key from the tree
580 The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
581 If the tree is empty the function returns an empty \p guarded_ptr.
583 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
584 It means that the function gets rightmost leaf of the tree and tries to unlink it.
585 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
586 So, the function returns the item with maximal key at the moment of tree traversing.
588 The returned \p guarded_ptr prevents disposer invocation for returned item,
589 see cds::gc::guarded_ptr for explanation.
590 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
592 guarded_ptr extract_max()
595 extract_max_( gp.guard());
599 /// Extracts an item from the tree
600 /** \anchor cds_intrusive_EllenBinTree_extract
601 The function searches an item with key equal to \p key in the tree,
602 unlinks it, and returns a guarded pointer to an item found.
603 If the item is not found the function returns an empty \p guarded_ptr.
605 \p guarded_ptr prevents disposer invocation for returned item,
606 see cds::gc::guarded_ptr for explanation.
607 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
609 template <typename Q>
610 guarded_ptr extract( Q const& key )
613 extract_( gp.guard(), key );
617 /// Extracts an item from the tree using \p pred for searching
619 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
620 but \p pred is used for key compare.
621 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
622 "Predicate requirements".
623 \p pred must imply the same element order as the comparator used for building the tree.
625 template <typename Q, typename Less>
626 guarded_ptr extract_with( Q const& key, Less pred )
629 extract_with_( gp.guard(), key, pred );
633 /// Checks whether the set contains \p key
635 The function searches the item with key equal to \p key
636 and returns \p true if it is found, and \p false otherwise.
638 template <typename Q>
639 bool contains( Q const& key ) const
642 if ( search( res, key, node_compare() )) {
643 m_Stat.onFindSuccess();
647 m_Stat.onFindFailed();
651 template <typename Q>
652 CDS_DEPRECATED("deprecated, use contains()")
653 bool find( Q const& key ) const
655 return contains( key );
659 /// Checks whether the set contains \p key using \p pred predicate for searching
661 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
662 \p Less functor has the interface like \p std::less.
663 \p Less must imply the same element order as the comparator used for building the set.
665 template <typename Q, typename Less>
666 bool contains( Q const& key, Less pred ) const
669 typedef ellen_bintree::details::compare<
672 opt::details::make_comparator_from_less<Less>,
677 if ( search( res, key, compare_functor() )) {
678 m_Stat.onFindSuccess();
681 m_Stat.onFindFailed();
685 template <typename Q, typename Less>
686 CDS_DEPRECATED("deprecated, use contains()")
687 bool find_with( Q const& key, Less pred ) const
689 return contains( key, pred );
693 /// Finds the key \p key
694 /** @anchor cds_intrusive_EllenBinTree_find_func
695 The function searches the item with key equal to \p key and calls the functor \p f for item found.
696 The interface of \p Func functor is:
699 void operator()( value_type& item, Q& key );
702 where \p item is the item found, \p key is the <tt>find</tt> function argument.
704 The functor can change non-key fields of \p item. Note that the functor is only guarantee
705 that \p item cannot be disposed during functor is executing.
706 The functor does not serialize simultaneous access to the tree \p item. If such access is
707 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
709 The function returns \p true if \p key is found, \p false otherwise.
711 template <typename Q, typename Func>
712 bool find( Q& key, Func f ) const
714 return find_( key, f );
717 template <typename Q, typename Func>
718 bool find( Q const& key, Func f ) const
720 return find_( key, f );
724 /// Finds the key \p key with comparing functor \p pred
726 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
727 but \p pred is used for key comparison.
728 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
729 "Predicate requirements".
730 \p pred must imply the same element order as the comparator used for building the tree.
732 template <typename Q, typename Less, typename Func>
733 bool find_with( Q& key, Less pred, Func f ) const
735 return find_with_( key, pred, f );
738 template <typename Q, typename Less, typename Func>
739 bool find_with( Q const& key, Less pred, Func f ) const
741 return find_with_( key, pred, f );
745 /// Finds \p key and returns the item found
746 /** @anchor cds_intrusive_EllenBinTree_get
747 The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
748 The function returns an empty guarded pointer is \p key is not found.
750 \p guarded_ptr prevents disposer invocation for returned item,
751 see \p cds::gc::guarded_ptr for explanation.
752 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
754 template <typename Q>
755 guarded_ptr get( Q const& key ) const
758 get_( gp.guard(), key );
762 /// Finds \p key with predicate \p pred and returns the item found
764 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
765 but \p pred is used for key comparing.
766 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
767 "Predicate requirements".
768 \p pred must imply the same element order as the comparator used for building the tree.
770 template <typename Q, typename Less>
771 guarded_ptr get_with( Q const& key, Less pred ) const
774 get_with_( gp.guard(), key, pred );
778 /// Checks if the tree is empty
781 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
784 /// Clears the tree (thread safe, not atomic)
786 The function unlink all items from the tree.
787 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
791 assert( tree.empty() );
793 the assertion could be raised.
795 For each leaf the \p disposer will be called after unlinking.
805 /// Clears the tree (not thread safe)
807 This function is not thread safe and may be called only when no other thread deals with the tree.
808 The function is used in the tree destructor.
813 internal_node * pParent = nullptr;
814 internal_node * pGrandParent = nullptr;
815 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
818 while ( pLeaf->is_internal() ) {
819 pGrandParent = pParent;
820 pParent = static_cast<internal_node *>( pLeaf );
821 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
824 if ( pLeaf->infinite_key()) {
829 // Remove leftmost leaf and its parent node
830 assert( pGrandParent );
832 assert( pLeaf->is_leaf() );
834 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
835 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
836 free_internal_node( pParent );
840 /// Returns item count in the tree
842 Only leaf nodes containing user data are counted.
844 The value returned depends on item counter type provided by \p Traits template parameter.
845 If it is \p atomicity::empty_item_counter this function always returns 0.
846 The function is not suitable for checking the tree emptiness, use \p empty()
847 member function for this purpose.
851 return m_ItemCounter;
854 /// Returns const reference to internal statistics
855 stat const& statistics() const
860 /// Checks internal consistency (not atomic, not thread-safe)
862 The debugging function to check internal consistency of the tree.
864 bool check_consistency() const
866 return check_consistency( &m_Root );
872 bool check_consistency( internal_node const * pRoot ) const
874 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
875 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
879 if ( node_compare()( *pLeft, *pRoot ) < 0
880 && node_compare()( *pRoot, *pRight ) <= 0
881 && node_compare()( *pLeft, *pRight ) < 0 )
884 if ( pLeft->is_internal() )
885 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
888 if ( bRet && pRight->is_internal() )
889 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
897 static tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent )
899 tree_node * p = bRight
900 ? res.guards.protect( search_result::Guard_Leaf, pParent->m_pRight,
901 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
902 : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
903 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});
904 if ( p && p->is_leaf() )
905 res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));
907 // child node is guarded
908 // See whether pParent->m_pUpdate has not been changed
909 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
910 // update has been changed - returns nullptr as a flag to search retry
916 static update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src )
918 return res.guards.protect( search_result::Guard_updParent, src, [](update_ptr p) -> update_desc* { return p.ptr(); });
921 template <typename KeyValue, typename Compare>
922 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
924 internal_node * pParent;
925 internal_node * pGrandParent = nullptr;
926 update_ptr updParent;
927 update_ptr updGrandParent;
929 bool bRightParent = false;
935 //pGrandParent = nullptr;
938 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
939 while ( pLeaf->is_internal() ) {
940 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
941 pGrandParent = pParent;
942 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
943 pParent = static_cast<internal_node *>( pLeaf );
944 bRightParent = bRightLeaf;
945 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
946 updGrandParent = updParent;
948 updParent = search_protect_update( res, pParent->m_pUpdate );
950 switch ( updParent.bits() ) {
951 case update_desc::DFlag:
952 case update_desc::Mark:
953 m_Stat.onSearchRetry();
957 nCmp = cmp( key, *pParent );
958 bRightLeaf = nCmp >= 0;
960 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
962 m_Stat.onSearchRetry();
967 assert( pLeaf->is_leaf() );
968 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
970 res.pGrandParent = pGrandParent;
971 res.pParent = pParent;
972 res.pLeaf = static_cast<leaf_node *>( pLeaf );
973 res.updParent = updParent;
974 res.updGrandParent = updGrandParent;
975 res.bRightParent = bRightParent;
976 res.bRightLeaf = bRightLeaf;
981 bool search_min( search_result& res ) const
983 internal_node * pParent;
984 internal_node * pGrandParent;
985 update_ptr updParent;
986 update_ptr updGrandParent;
990 pGrandParent = nullptr;
992 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
993 while ( pLeaf->is_internal() ) {
994 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
995 pGrandParent = pParent;
996 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
997 pParent = static_cast<internal_node *>( pLeaf );
998 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
999 updGrandParent = updParent;
1001 updParent = search_protect_update( res, pParent->m_pUpdate );
1003 switch ( updParent.bits() ) {
1004 case update_desc::DFlag:
1005 case update_desc::Mark:
1006 m_Stat.onSearchRetry();
1010 pLeaf = protect_child_node( res, pParent, false, updParent );
1012 m_Stat.onSearchRetry();
1017 if ( pLeaf->infinite_key())
1020 res.pGrandParent = pGrandParent;
1021 res.pParent = pParent;
1022 assert( pLeaf->is_leaf() );
1023 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1024 res.updParent = updParent;
1025 res.updGrandParent = updGrandParent;
1026 res.bRightParent = false;
1027 res.bRightLeaf = false;
1032 bool search_max( search_result& res ) const
1034 internal_node * pParent;
1035 internal_node * pGrandParent;
1036 update_ptr updParent;
1037 update_ptr updGrandParent;
1039 bool bRightParent = false;
1043 pGrandParent = nullptr;
1044 updParent = nullptr;
1046 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1047 while ( pLeaf->is_internal() ) {
1048 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1049 pGrandParent = pParent;
1050 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1051 pParent = static_cast<internal_node *>( pLeaf );
1052 bRightParent = bRightLeaf;
1053 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1054 updGrandParent = updParent;
1056 updParent = search_protect_update( res, pParent->m_pUpdate );
1058 switch ( updParent.bits() ) {
1059 case update_desc::DFlag:
1060 case update_desc::Mark:
1061 m_Stat.onSearchRetry();
1065 bRightLeaf = !pParent->infinite_key();
1066 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1068 m_Stat.onSearchRetry();
1073 if ( pLeaf->infinite_key())
1076 res.pGrandParent = pGrandParent;
1077 res.pParent = pParent;
1078 assert( pLeaf->is_leaf() );
1079 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1080 res.updParent = updParent;
1081 res.updGrandParent = updGrandParent;
1082 res.bRightParent = bRightParent;
1083 res.bRightLeaf = bRightLeaf;
1089 void help( update_ptr pUpdate )
1091 // pUpdate must be guarded!
1092 switch ( pUpdate.bits() ) {
1093 case update_desc::IFlag:
1094 help_insert( pUpdate.ptr() );
1095 m_Stat.onHelpInsert();
1097 case update_desc::DFlag:
1098 help_delete( pUpdate.ptr() );
1099 m_Stat.onHelpDelete();
1101 case update_desc::Mark:
1102 //m_Stat.onHelpMark();
1103 //help_marked( pUpdate.ptr() );
1109 void help_insert( update_desc * pOp )
1111 // pOp must be guarded
1113 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1114 if ( pOp->iInfo.bRightLeaf ) {
1115 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1116 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1119 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1120 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1124 update_ptr cur( pOp, update_desc::IFlag );
1125 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1126 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1129 bool check_delete_precondition( search_result& res ) const
1131 // precondition: all member of res must be guarded
1133 assert( res.pGrandParent != nullptr );
1136 static_cast<internal_node *>(
1138 ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1139 : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1142 static_cast<leaf_node *>(
1144 ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1145 : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1149 bool help_delete( update_desc * pOp )
1151 // precondition: pOp must be guarded
1153 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1154 update_ptr pMark( pOp, update_desc::Mark );
1155 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1156 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1160 retire_node( pOp->dInfo.pParent );
1161 retire_node( pOp->dInfo.pLeaf );
1162 retire_update_desc( pOp );
1165 else if ( pUpdate == pMark ) {
1166 // some other thread is processing help_marked()
1168 m_Stat.onHelpMark();
1172 // Undo grandparent dInfo
1173 update_ptr pDel( pOp, update_desc::DFlag );
1174 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1175 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1177 retire_update_desc( pOp );
1183 static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1185 tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
1186 if ( pSibling->is_leaf() )
1187 guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
1191 void help_marked( update_desc * pOp )
1193 // precondition: pOp must be guarded
1195 tree_node * pParent = pOp->dInfo.pParent;
1197 typename gc::Guard guard;
1198 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1200 if ( pOp->dInfo.bRightParent ) {
1201 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1202 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1205 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1206 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1209 update_ptr upd( pOp, update_desc::DFlag );
1210 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1211 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1214 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1216 assert( res.updParent.bits() == update_desc::Clean );
1217 assert( res.pLeaf->is_leaf() );
1219 // check search result
1220 if ( (res.bRightLeaf
1221 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1222 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire )) == res.pLeaf ) {
1223 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1225 int nCmp = node_compare()(val, *res.pLeaf);
1227 if ( res.pGrandParent ) {
1228 assert( !res.pLeaf->infinite_key() );
1229 pNewInternal->infinite_key( 0 );
1230 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1233 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1234 pNewInternal->infinite_key( 1 );
1236 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1237 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1240 assert( !res.pLeaf->is_internal() );
1242 pNewInternal->infinite_key( 0 );
1243 key_extractor()(pNewInternal->m_Key, val);
1244 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1245 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1246 assert( !res.pLeaf->infinite_key() );
1249 typename gc::Guard guard;
1250 update_desc * pOp = alloc_update_desc();
1251 guard.assign( pOp );
1253 pOp->iInfo.pParent = res.pParent;
1254 pOp->iInfo.pNew = pNewInternal;
1255 pOp->iInfo.pLeaf = res.pLeaf;
1256 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1258 update_ptr updCur( res.updParent.ptr() );
1259 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1260 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1263 retire_update_desc( pOp );
1267 m_Stat.onUpdateDescDeleted();
1268 free_update_desc( pOp );
1275 template <typename Q, typename Compare, typename Equal, typename Func>
1276 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1278 update_desc * pOp = nullptr;
1283 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1285 retire_update_desc( pOp );
1286 m_Stat.onEraseFailed();
1290 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1292 pOp = alloc_update_desc();
1293 if ( check_delete_precondition( res ) ) {
1294 typename gc::Guard guard;
1295 guard.assign( pOp );
1297 pOp->dInfo.pGrandParent = res.pGrandParent;
1298 pOp->dInfo.pParent = res.pParent;
1299 pOp->dInfo.pLeaf = res.pLeaf;
1300 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1301 pOp->dInfo.bRightParent = res.bRightParent;
1302 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1304 update_ptr updGP( res.updGrandParent.ptr() );
1305 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1306 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1307 if ( help_delete( pOp ) ) {
1308 // res.pLeaf is not deleted yet since it is guarded
1309 f( *node_traits::to_value_ptr( res.pLeaf ) );
1318 m_Stat.onEraseRetry();
1322 m_Stat.onEraseSuccess();
1326 template <typename Q>
1327 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
1329 return erase_( key, node_compare(),
1330 []( Q const&, leaf_node const& ) -> bool { return true; },
1331 [&guard]( value_type& found ) { guard.set( &found ); } );
1334 template <typename Q, typename Less>
1335 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
1337 typedef ellen_bintree::details::compare<
1340 opt::details::make_comparator_from_less<Less>,
1344 return erase_( key, compare_functor(),
1345 []( Q const&, leaf_node const& ) -> bool { return true; },
1346 [&guard]( value_type& found ) { guard.set( &found ); } );
1349 bool extract_max_( typename guarded_ptr::native_guard& gp )
1351 update_desc * pOp = nullptr;
1356 if ( !search_max( res )) {
1359 retire_update_desc( pOp );
1360 m_Stat.onExtractMaxFailed();
1364 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1366 pOp = alloc_update_desc();
1367 if ( check_delete_precondition( res ) ) {
1368 typename gc::Guard guard;
1369 guard.assign( pOp );
1371 pOp->dInfo.pGrandParent = res.pGrandParent;
1372 pOp->dInfo.pParent = res.pParent;
1373 pOp->dInfo.pLeaf = res.pLeaf;
1374 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1375 pOp->dInfo.bRightParent = res.bRightParent;
1376 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1378 update_ptr updGP( res.updGrandParent.ptr() );
1379 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1380 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1382 if ( help_delete( pOp ) )
1390 m_Stat.onExtractMaxRetry();
1394 m_Stat.onExtractMaxSuccess();
1395 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1399 bool extract_min_( typename guarded_ptr::native_guard& gp )
1401 update_desc * pOp = nullptr;
1406 if ( !search_min( res )) {
1409 retire_update_desc( pOp );
1410 m_Stat.onExtractMinFailed();
1414 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1416 pOp = alloc_update_desc();
1417 if ( check_delete_precondition( res ) ) {
1418 typename gc::Guard guard;
1419 guard.assign( pOp );
1421 pOp->dInfo.pGrandParent = res.pGrandParent;
1422 pOp->dInfo.pParent = res.pParent;
1423 pOp->dInfo.pLeaf = res.pLeaf;
1424 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1425 pOp->dInfo.bRightParent = res.bRightParent;
1426 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1428 update_ptr updGP( res.updGrandParent.ptr() );
1429 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1430 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1432 if ( help_delete( pOp ))
1440 m_Stat.onExtractMinRetry();
1444 m_Stat.onExtractMinSuccess();
1445 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1449 template <typename Q, typename Func>
1450 bool find_( Q& val, Func f ) const
1453 if ( search( res, val, node_compare() )) {
1454 assert( res.pLeaf );
1455 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1457 m_Stat.onFindSuccess();
1461 m_Stat.onFindFailed();
1465 template <typename Q, typename Less, typename Func>
1466 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1468 typedef ellen_bintree::details::compare<
1471 opt::details::make_comparator_from_less<Less>,
1476 if ( search( res, val, compare_functor() )) {
1477 assert( res.pLeaf );
1478 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1480 m_Stat.onFindSuccess();
1484 m_Stat.onFindFailed();
1488 template <typename Q>
1489 bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
1491 return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1494 template <typename Q, typename Less>
1495 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
1497 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1503 }} // namespace cds::intrusive
1505 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H