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 = 9; ///< 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,
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 )
208 internal_node m_Root; ///< Tree root node (key= Infinite2)
209 leaf_node m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
210 leaf_node m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
213 item_counter m_ItemCounter; ///< item counter
214 mutable stat m_Stat; ///< internal statistics
218 static void free_leaf_node( value_type * p )
223 internal_node * alloc_internal_node() const
225 m_Stat.onInternalNodeCreated();
226 internal_node * pNode = cxx_node_allocator().New();
230 static void free_internal_node( internal_node * pNode )
232 cxx_node_allocator().Delete( pNode );
235 struct internal_node_deleter {
236 void operator()( internal_node * p) const
238 free_internal_node( p );
242 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
244 update_desc * alloc_update_desc() const
246 m_Stat.onUpdateDescCreated();
247 return cxx_update_desc_allocator().New();
250 static void free_update_desc( update_desc * pDesc )
252 cxx_update_desc_allocator().Delete( pDesc );
255 void retire_node( tree_node * pNode ) const
257 if ( pNode->is_leaf() ) {
258 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
259 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
261 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
264 assert( static_cast<internal_node *>( pNode ) != &m_Root );
265 m_Stat.onInternalNodeDeleted();
267 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
271 void retire_update_desc( update_desc * p ) const
273 m_Stat.onUpdateDescDeleted();
274 gc::template retire( p, free_update_desc );
277 void make_empty_tree()
279 m_Root.infinite_key( 2 );
280 m_LeafInf1.infinite_key( 1 );
281 m_LeafInf2.infinite_key( 2 );
282 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
283 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
288 /// Default constructor
291 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
303 The function inserts \p val in the tree if it does not contain
304 an item with key equal to \p val.
306 Returns \p true if \p val is placed into the tree, \p false otherwise.
308 bool insert( value_type& val )
310 return insert( val, []( value_type& ) {} );
315 This function is intended for derived non-intrusive containers.
317 The function allows to split creating of new item into two part:
318 - create item with key only
319 - insert new item into the tree
320 - if inserting is success, calls \p f functor to initialize value-field of \p val.
322 The functor signature is:
324 void func( value_type& val );
326 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
327 \p val no any other changes could be made on this tree's item by concurrent threads.
328 The user-defined functor is called only if the inserting is success.
330 template <typename Func>
331 bool insert( value_type& val, Func f )
333 typename gc::Guard guardInsert;
334 guardInsert.assign( &val );
336 unique_internal_node_ptr pNewInternal;
341 if ( search( res, val, node_compare() )) {
342 if ( pNewInternal.get() )
343 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
344 m_Stat.onInsertFailed();
348 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
350 if ( !pNewInternal.get() )
351 pNewInternal.reset( alloc_internal_node() );
353 if ( try_insert( val, pNewInternal.get(), res )) {
355 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
361 m_Stat.onInsertRetry();
365 m_Stat.onInsertSuccess();
371 The operation performs inserting or changing data with lock-free manner.
373 If the item \p val is not found in the set, then \p val is inserted into the set
374 iff \p bAllowInsert is \p true.
375 Otherwise, the functor \p func is called with item found.
376 The functor \p func signature is:
378 void func( bool bNew, value_type& item, value_type& val );
381 - \p bNew - \p true if the item has been inserted, \p false otherwise
382 - \p item - item of the set
383 - \p val - argument \p val passed into the \p %update() function
384 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
385 refer to the same thing.
387 The functor can change non-key fields of the \p item; however, \p func must guarantee
388 that during changing no any other modifications could be made on this item by concurrent threads.
390 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
391 i.e. the node has been inserted or updated,
392 \p second is \p true if new item has been added or \p false if the item with \p key
395 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
397 template <typename Func>
398 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
400 typename gc::Guard guardInsert;
401 guardInsert.assign( &val );
403 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 return std::make_pair( false, false );
420 if ( !pNewInternal.get() )
421 pNewInternal.reset( alloc_internal_node() );
423 if ( try_insert( val, pNewInternal.get(), res )) {
424 func( true, val, val );
425 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
431 m_Stat.onEnsureRetry();
435 m_Stat.onEnsureNew();
436 return std::make_pair( true, true );
439 template <typename Func>
440 CDS_DEPRECATED("ensure() is deprecated, use update()")
441 std::pair<bool, bool> ensure( value_type& val, Func func )
443 return update( val, func, true );
447 /// Unlinks the item \p val from the tree
449 The function searches the item \p val in the tree and unlink it from the tree
450 if it is found and is equal to \p val.
452 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
453 and deletes the item found. \p unlink finds an item by key and deletes it
454 only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
456 The \p disposer specified in \p Traits class template parameter is called
457 by garbage collector \p GC asynchronously.
459 The function returns \p true if success and \p false otherwise.
461 bool unlink( value_type& val )
463 return erase_( val, node_compare(),
464 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
465 [](value_type const&) {} );
468 /// Deletes the item from the tree
469 /** \anchor cds_intrusive_EllenBinTree_erase
470 The function searches an item with key equal to \p key in the tree,
471 unlinks it from the tree, and returns \p true.
472 If the item with key equal to \p key is not found the function return \p false.
474 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
476 template <typename Q>
477 bool erase( const Q& key )
479 return erase_( key, node_compare(),
480 []( Q const&, leaf_node const& ) -> bool { return true; },
481 [](value_type const&) {} );
484 /// Delete the item from the tree with comparing functor \p pred
486 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
487 but \p pred predicate is used for key comparing.
488 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
489 "Predicate requirements".
490 \p pred must imply the same element order as the comparator used for building the tree.
492 template <typename Q, typename Less>
493 bool erase_with( const Q& key, Less pred )
496 typedef ellen_bintree::details::compare<
499 opt::details::make_comparator_from_less<Less>,
503 return erase_( key, compare_functor(),
504 []( Q const&, leaf_node const& ) -> bool { return true; },
505 [](value_type const&) {} );
508 /// Deletes the item from the tree
509 /** \anchor cds_intrusive_EllenBinTree_erase_func
510 The function searches an item with key equal to \p key in the tree,
511 call \p f functor with item found, unlinks it from the tree, and returns \p true.
512 The \ref disposer specified in \p Traits class template parameter is called
513 by garbage collector \p GC asynchronously.
515 The \p Func interface is
518 void operator()( value_type const& item );
522 If the item with key equal to \p key is not found the function return \p false.
524 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
526 template <typename Q, typename Func>
527 bool erase( Q const& key, Func f )
529 return erase_( key, node_compare(),
530 []( Q const&, leaf_node const& ) -> bool { return true; },
534 /// Delete the item from the tree with comparing functor \p pred
536 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
537 but \p pred predicate is used for key comparing.
538 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
539 "Predicate requirements".
540 \p pred must imply the same element order as the comparator used for building the tree.
542 template <typename Q, typename Less, typename Func>
543 bool erase_with( Q const& key, Less pred, Func f )
546 typedef ellen_bintree::details::compare<
549 opt::details::make_comparator_from_less<Less>,
553 return erase_( key, compare_functor(),
554 []( Q const&, leaf_node const& ) -> bool { return true; },
558 /// Extracts an item with minimal key from the tree
560 The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
561 If the tree is empty the function returns an empty guarded pointer.
563 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
564 It means that the function gets leftmost leaf of the tree and tries to unlink it.
565 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
566 So, the function returns the item with minimum key at the moment of tree traversing.
568 The returned \p guarded_ptr prevents disposer invocation for returned item,
569 see \p cds::gc::guarded_ptr for explanation.
570 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
572 guarded_ptr extract_min()
575 extract_min_( gp.guard() );
579 /// Extracts an item with maximal key from the tree
581 The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
582 If the tree is empty the function returns an empty \p guarded_ptr.
584 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
585 It means that the function gets rightmost leaf of the tree and tries to unlink it.
586 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
587 So, the function returns the item with maximal key at the moment of tree traversing.
589 The returned \p guarded_ptr 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 guarded_ptr extract_max()
596 extract_max_( gp.guard());
600 /// Extracts an item from the tree
601 /** \anchor cds_intrusive_EllenBinTree_extract
602 The function searches an item with key equal to \p key in the tree,
603 unlinks it, and returns a guarded pointer to an item found.
604 If the item is not found the function returns an empty \p guarded_ptr.
606 \p guarded_ptr prevents disposer invocation for returned item,
607 see cds::gc::guarded_ptr for explanation.
608 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
610 template <typename Q>
611 guarded_ptr extract( Q const& key )
614 extract_( gp.guard(), key );
618 /// Extracts an item from the tree using \p pred for searching
620 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
621 but \p pred is used for key compare.
622 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
623 "Predicate requirements".
624 \p pred must imply the same element order as the comparator used for building the tree.
626 template <typename Q, typename Less>
627 guarded_ptr extract_with( Q const& key, Less pred )
630 extract_with_( gp.guard(), key, pred );
634 /// Checks whether the set contains \p key
636 The function searches the item with key equal to \p key
637 and returns \p true if it is found, and \p false otherwise.
639 template <typename Q>
640 bool contains( Q const& key ) const
643 if ( search( res, key, node_compare() )) {
644 m_Stat.onFindSuccess();
648 m_Stat.onFindFailed();
652 template <typename Q>
653 CDS_DEPRECATED("deprecated, use contains()")
654 bool find( Q const& key ) const
656 return contains( key );
660 /// Checks whether the set contains \p key using \p pred predicate for searching
662 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
663 \p Less functor has the interface like \p std::less.
664 \p Less must imply the same element order as the comparator used for building the set.
666 template <typename Q, typename Less>
667 bool contains( Q const& key, Less pred ) const
670 typedef ellen_bintree::details::compare<
673 opt::details::make_comparator_from_less<Less>,
678 if ( search( res, key, compare_functor() )) {
679 m_Stat.onFindSuccess();
682 m_Stat.onFindFailed();
686 template <typename Q, typename Less>
687 CDS_DEPRECATED("deprecated, use contains()")
688 bool find_with( Q const& key, Less pred ) const
690 return contains( key, pred );
694 /// Finds the key \p key
695 /** @anchor cds_intrusive_EllenBinTree_find_func
696 The function searches the item with key equal to \p key and calls the functor \p f for item found.
697 The interface of \p Func functor is:
700 void operator()( value_type& item, Q& key );
703 where \p item is the item found, \p key is the <tt>find</tt> function argument.
705 The functor can change non-key fields of \p item. Note that the functor is only guarantee
706 that \p item cannot be disposed during functor is executing.
707 The functor does not serialize simultaneous access to the tree \p item. If such access is
708 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
710 The function returns \p true if \p key is found, \p false otherwise.
712 template <typename Q, typename Func>
713 bool find( Q& key, Func f ) const
715 return find_( key, f );
718 template <typename Q, typename Func>
719 bool find( Q const& key, Func f ) const
721 return find_( key, f );
725 /// Finds the key \p key with comparing functor \p pred
727 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
728 but \p pred is used for key comparison.
729 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
730 "Predicate requirements".
731 \p pred must imply the same element order as the comparator used for building the tree.
733 template <typename Q, typename Less, typename Func>
734 bool find_with( Q& key, Less pred, Func f ) const
736 return find_with_( key, pred, f );
739 template <typename Q, typename Less, typename Func>
740 bool find_with( Q const& key, Less pred, Func f ) const
742 return find_with_( key, pred, f );
746 /// Finds \p key and returns the item found
747 /** @anchor cds_intrusive_EllenBinTree_get
748 The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
749 The function returns an empty guarded pointer is \p key is not found.
751 \p guarded_ptr prevents disposer invocation for returned item,
752 see \p cds::gc::guarded_ptr for explanation.
753 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
755 template <typename Q>
756 guarded_ptr get( Q const& key ) const
759 get_( gp.guard(), key );
763 /// Finds \p key with predicate \p pred and returns the item found
765 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
766 but \p pred is used for key comparing.
767 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
768 "Predicate requirements".
769 \p pred must imply the same element order as the comparator used for building the tree.
771 template <typename Q, typename Less>
772 guarded_ptr get_with( Q const& key, Less pred ) const
775 get_with_( gp.guard(), key, pred );
779 /// Checks if the tree is empty
782 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
785 /// Clears the tree (thread safe, not atomic)
787 The function unlink all items from the tree.
788 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
792 assert( tree.empty() );
794 the assertion could be raised.
796 For each leaf the \p disposer will be called after unlinking.
806 /// Clears the tree (not thread safe)
808 This function is not thread safe and may be called only when no other thread deals with the tree.
809 The function is used in the tree destructor.
814 internal_node * pParent = nullptr;
815 internal_node * pGrandParent = nullptr;
816 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
819 while ( pLeaf->is_internal() ) {
820 pGrandParent = pParent;
821 pParent = static_cast<internal_node *>( pLeaf );
822 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
825 if ( pLeaf->infinite_key()) {
830 // Remove leftmost leaf and its parent node
831 assert( pGrandParent );
833 assert( pLeaf->is_leaf() );
835 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
836 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
837 free_internal_node( pParent );
841 /// Returns item count in the tree
843 Only leaf nodes containing user data are counted.
845 The value returned depends on item counter type provided by \p Traits template parameter.
846 If it is \p atomicity::empty_item_counter this function always returns 0.
847 The function is not suitable for checking the tree emptiness, use \p empty()
848 member function for this purpose.
852 return m_ItemCounter;
855 /// Returns const reference to internal statistics
856 stat const& statistics() const
861 /// Checks internal consistency (not atomic, not thread-safe)
863 The debugging function to check internal consistency of the tree.
865 bool check_consistency() const
867 return check_consistency( &m_Root );
873 bool check_consistency( internal_node const * pRoot ) const
875 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
876 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
880 if ( node_compare()( *pLeft, *pRoot ) < 0
881 && node_compare()( *pRoot, *pRight ) <= 0
882 && node_compare()( *pLeft, *pRight ) < 0 )
885 if ( pLeft->is_internal() )
886 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
889 if ( bRet && pRight->is_internal() )
890 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
898 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
901 tree_node * p = bRight
902 ? res.guards.protect( search_result::Guard_Leaf, pParent->m_pRight,
903 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
904 : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
905 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});
907 // If we use member hook, data node pointer != internal node pointer
908 // So, we need protect the child twice: as internal node and as data node
909 // and then analyze what kind of node we have
910 tree_node * pVal = bRight
911 ? res.guards.protect( search_result::Guard_temporary, pParent->m_pRight,
912 []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} )
913 : res.guards.protect( search_result::Guard_temporary, pParent->m_pLeft,
914 []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} );
916 // child node is guarded
917 // See whether pParent->m_pUpdate has not been changed
918 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
919 // update has been changed - returns nullptr as a flag to search retry
926 if ( p && p->is_leaf())
927 res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));
929 res.guards.clear( search_result::Guard_temporary );
934 static update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src )
936 return res.guards.protect( search_result::Guard_updParent, src, [](update_ptr p) -> update_desc* { return p.ptr(); });
939 template <typename KeyValue, typename Compare>
940 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
942 internal_node * pParent;
943 internal_node * pGrandParent = nullptr;
944 update_ptr updParent;
945 update_ptr updGrandParent;
947 bool bRightParent = false;
953 //pGrandParent = nullptr;
956 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
957 while ( pLeaf->is_internal() ) {
958 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
959 pGrandParent = pParent;
960 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
961 pParent = static_cast<internal_node *>( pLeaf );
962 bRightParent = bRightLeaf;
963 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
964 updGrandParent = updParent;
966 updParent = search_protect_update( res, pParent->m_pUpdate );
968 switch ( updParent.bits() ) {
969 case update_desc::DFlag:
970 case update_desc::Mark:
971 m_Stat.onSearchRetry();
975 nCmp = cmp( key, *pParent );
976 bRightLeaf = nCmp >= 0;
978 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
980 m_Stat.onSearchRetry();
985 assert( pLeaf->is_leaf() );
986 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
988 res.pGrandParent = pGrandParent;
989 res.pParent = pParent;
990 res.pLeaf = static_cast<leaf_node *>( pLeaf );
991 res.updParent = updParent;
992 res.updGrandParent = updGrandParent;
993 res.bRightParent = bRightParent;
994 res.bRightLeaf = bRightLeaf;
999 bool search_min( search_result& res ) const
1001 internal_node * pParent;
1002 internal_node * pGrandParent;
1003 update_ptr updParent;
1004 update_ptr updGrandParent;
1008 pGrandParent = nullptr;
1009 updParent = nullptr;
1010 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1011 while ( pLeaf->is_internal() ) {
1012 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1013 pGrandParent = pParent;
1014 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1015 pParent = static_cast<internal_node *>( pLeaf );
1016 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1017 updGrandParent = updParent;
1019 updParent = search_protect_update( res, pParent->m_pUpdate );
1021 switch ( updParent.bits() ) {
1022 case update_desc::DFlag:
1023 case update_desc::Mark:
1024 m_Stat.onSearchRetry();
1028 pLeaf = protect_child_node( res, pParent, false, updParent );
1030 m_Stat.onSearchRetry();
1035 if ( pLeaf->infinite_key())
1038 res.pGrandParent = pGrandParent;
1039 res.pParent = pParent;
1040 assert( pLeaf->is_leaf() );
1041 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1042 res.updParent = updParent;
1043 res.updGrandParent = updGrandParent;
1044 res.bRightParent = false;
1045 res.bRightLeaf = false;
1050 bool search_max( search_result& res ) const
1052 internal_node * pParent;
1053 internal_node * pGrandParent;
1054 update_ptr updParent;
1055 update_ptr updGrandParent;
1057 bool bRightParent = false;
1061 pGrandParent = nullptr;
1062 updParent = nullptr;
1064 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1065 while ( pLeaf->is_internal() ) {
1066 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1067 pGrandParent = pParent;
1068 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1069 pParent = static_cast<internal_node *>( pLeaf );
1070 bRightParent = bRightLeaf;
1071 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1072 updGrandParent = updParent;
1074 updParent = search_protect_update( res, pParent->m_pUpdate );
1076 switch ( updParent.bits() ) {
1077 case update_desc::DFlag:
1078 case update_desc::Mark:
1079 m_Stat.onSearchRetry();
1083 bRightLeaf = !pParent->infinite_key();
1084 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1086 m_Stat.onSearchRetry();
1091 if ( pLeaf->infinite_key())
1094 res.pGrandParent = pGrandParent;
1095 res.pParent = pParent;
1096 assert( pLeaf->is_leaf() );
1097 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1098 res.updParent = updParent;
1099 res.updGrandParent = updGrandParent;
1100 res.bRightParent = bRightParent;
1101 res.bRightLeaf = bRightLeaf;
1107 void help( update_ptr pUpdate )
1109 // pUpdate must be guarded!
1110 switch ( pUpdate.bits() ) {
1111 case update_desc::IFlag:
1112 help_insert( pUpdate.ptr() );
1113 m_Stat.onHelpInsert();
1115 case update_desc::DFlag:
1116 help_delete( pUpdate.ptr() );
1117 m_Stat.onHelpDelete();
1119 case update_desc::Mark:
1120 //m_Stat.onHelpMark();
1121 //help_marked( pUpdate.ptr() );
1127 void help_insert( update_desc * pOp )
1129 // pOp must be guarded
1131 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1132 if ( pOp->iInfo.bRightLeaf ) {
1133 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1134 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1137 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1138 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1142 update_ptr cur( pOp, update_desc::IFlag );
1143 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1144 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1147 bool check_delete_precondition( search_result& res ) const
1149 // precondition: all member of res must be guarded
1151 assert( res.pGrandParent != nullptr );
1153 return static_cast<internal_node *>(res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1154 && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1157 bool help_delete( update_desc * pOp )
1159 // precondition: pOp must be guarded
1161 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1162 update_ptr pMark( pOp, update_desc::Mark );
1163 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1164 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1168 retire_node( pOp->dInfo.pParent );
1169 retire_node( pOp->dInfo.pLeaf );
1170 retire_update_desc( pOp );
1173 else if ( pUpdate == pMark ) {
1174 // some other thread is processing help_marked()
1176 m_Stat.onHelpMark();
1180 // Undo grandparent dInfo
1181 update_ptr pDel( pOp, update_desc::DFlag );
1182 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1183 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1185 retire_update_desc( pOp );
1191 static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1193 tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
1194 if ( pSibling->is_leaf() )
1195 guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
1199 void help_marked( update_desc * pOp )
1201 // precondition: pOp must be guarded
1203 tree_node * pParent = pOp->dInfo.pParent;
1205 typename gc::Guard guard;
1206 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1208 if ( pOp->dInfo.bRightParent ) {
1209 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1210 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1213 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1214 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1217 update_ptr upd( pOp, update_desc::DFlag );
1218 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1219 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1222 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1224 assert( res.updParent.bits() == update_desc::Clean );
1225 assert( res.pLeaf->is_leaf() );
1227 // check search result
1228 if ( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_acquire ) == res.pLeaf ) {
1229 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1231 int nCmp = node_compare()(val, *res.pLeaf);
1233 if ( res.pGrandParent ) {
1234 assert( !res.pLeaf->infinite_key() );
1235 pNewInternal->infinite_key( 0 );
1236 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1239 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1240 pNewInternal->infinite_key( 1 );
1242 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1243 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1246 assert( !res.pLeaf->is_internal() );
1248 pNewInternal->infinite_key( 0 );
1249 key_extractor()(pNewInternal->m_Key, val);
1250 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1251 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1252 assert( !res.pLeaf->infinite_key() );
1255 typename gc::Guard guard;
1256 update_desc * pOp = alloc_update_desc();
1257 guard.assign( pOp );
1259 pOp->iInfo.pParent = res.pParent;
1260 pOp->iInfo.pNew = pNewInternal;
1261 pOp->iInfo.pLeaf = res.pLeaf;
1262 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1264 update_ptr updCur( res.updParent.ptr() );
1265 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1266 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1269 retire_update_desc( pOp );
1273 m_Stat.onUpdateDescDeleted();
1274 free_update_desc( pOp );
1281 template <typename Q, typename Compare, typename Equal, typename Func>
1282 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1284 update_desc * pOp = nullptr;
1289 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1291 retire_update_desc( pOp );
1292 m_Stat.onEraseFailed();
1296 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1298 pOp = alloc_update_desc();
1299 if ( check_delete_precondition( res ) ) {
1300 typename gc::Guard guard;
1301 guard.assign( pOp );
1303 pOp->dInfo.pGrandParent = res.pGrandParent;
1304 pOp->dInfo.pParent = res.pParent;
1305 pOp->dInfo.pLeaf = res.pLeaf;
1306 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1307 pOp->dInfo.bRightParent = res.bRightParent;
1308 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1310 update_ptr updGP( res.updGrandParent.ptr() );
1311 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1312 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1313 if ( help_delete( pOp ) ) {
1314 // res.pLeaf is not deleted yet since it is guarded
1315 f( *node_traits::to_value_ptr( res.pLeaf ) );
1324 m_Stat.onEraseRetry();
1328 m_Stat.onEraseSuccess();
1332 template <typename Q>
1333 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
1335 return erase_( key, node_compare(),
1336 []( Q const&, leaf_node const& ) -> bool { return true; },
1337 [&guard]( value_type& found ) { guard.set( &found ); } );
1340 template <typename Q, typename Less>
1341 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
1474 typedef ellen_bintree::details::compare<
1477 opt::details::make_comparator_from_less<Less>,
1482 if ( search( res, val, compare_functor() )) {
1483 assert( res.pLeaf );
1484 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1486 m_Stat.onFindSuccess();
1490 m_Stat.onFindFailed();
1494 template <typename Q>
1495 bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
1497 return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1500 template <typename Q, typename Less>
1501 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
1503 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1509 }} // namespace cds::intrusive
1511 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H