2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H
32 #define CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H
35 #include <cds/intrusive/details/ellen_bintree_base.h>
36 #include <cds/opt/compare.h>
37 #include <cds/details/binary_functor_wrapper.h>
38 #include <cds/urcu/details/check_deadlock.h>
40 namespace cds { namespace intrusive {
42 /// Ellen's et al binary search tree
43 /** @ingroup cds_intrusive_map
44 @ingroup cds_intrusive_tree
45 @anchor cds_intrusive_EllenBinTree
48 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
50 %EllenBinTree is an <i>unbalanced</i> leaf-oriented binary search tree that implements the <i>set</i>
51 abstract data type. Nodes maintains child pointers but not parent pointers.
52 Every internal node has exactly two children, and all data of type \p T currently in
53 the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find()
54 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
55 may or may not be in the set. \p Key type is a subset of \p T type.
56 There should be exactly defined a key extracting functor for converting object of type \p T to
57 object of type \p Key.
59 Due to \p extract_min() and \p extract_max() member functions the \p %EllenBinTree can act as
60 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
61 the priority value plus some uniformly distributed random value.
63 @note In the current implementation we do not use helping technique described in the original paper.
64 In Hazard Pointer schema the helping is too complicated and does not give any observable benefits.
65 Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
66 the operation done. Such solution allows greatly simplify implementation of the tree.
68 @attention Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
69 for uniformly distributed random keys, but in the worst case the complexity is <tt>O(N)</tt>.
71 @note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
72 There are header file for each GC type:
73 - <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC \p cds::gc::HP
74 - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Dynamic Hazard Pointer GC \p cds::gc::DHP
75 - <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
77 <b>Template arguments</b> :
78 - \p GC - garbage collector, possible types are cds::gc::HP, cds::gc::DHP.
79 - \p Key - key type, a subset of \p T
80 - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
81 (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
82 (for \p ellen_bintree::member_hook).
83 - \p Traits - tree traits, default is \p ellen_bintree::traits
84 It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
85 instead of \p Traits template argument.
87 @anchor cds_intrusive_EllenBinTree_less
88 <b>Predicate requirements</b>
90 \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
91 of type \p T and \p Key in any combination.
92 For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
94 struct Foo: public cds::intrusive::ellen_bintree::node< ... >
101 bool operator()( Foo const& v1, Foo const& v2 ) const
102 { return v1.m_strKey < v2.m_strKey ; }
104 bool operator()( Foo const& v, std::string const& s ) const
105 { return v.m_strKey < s ; }
107 bool operator()( std::string const& s, Foo const& v ) const
108 { return s < v.m_strKey ; }
110 // Support comparing std::string and char const *
111 bool operator()( std::string const& s, char const * p ) const
112 { return s.compare(p) < 0 ; }
114 bool operator()( Foo const& v, char const * p ) const
115 { return v.m_strKey.compare(p) < 0 ; }
117 bool operator()( char const * p, std::string const& s ) const
118 { return s.compare(p) > 0; }
120 bool operator()( char const * p, Foo const& v ) const
121 { return v.m_strKey.compare(p) > 0; }
125 Usage examples see \ref cds_intrusive_EllenBinTree_usage "here"
130 #ifdef CDS_DOXYGEN_INVOKED
131 class Traits = ellen_bintree::traits
139 typedef GC gc; ///< Garbage collector
140 typedef Key key_type; ///< type of a key to be stored in internal nodes; key is a part of \p value_type
141 typedef T value_type; ///< type of value stored in the binary tree
142 typedef Traits traits; ///< Traits template parameter
144 typedef typename traits::hook hook; ///< hook type
145 typedef typename hook::node_type node_type; ///< node type
146 typedef typename traits::disposer disposer; ///< leaf node disposer
147 typedef typename traits::back_off back_off; ///< back-off strategy
149 typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
153 typedef ellen_bintree::base_node< gc > tree_node; ///< Base type of tree node
154 typedef node_type leaf_node; ///< Leaf node type
155 typedef ellen_bintree::node_types< gc, key_type, typename leaf_node::tag > node_factory;
156 typedef typename node_factory::internal_node_type internal_node; ///< Internal node type
157 typedef typename node_factory::update_desc_type update_desc; ///< Update descriptor
158 typedef typename update_desc::update_ptr update_ptr; ///< Marked pointer to update descriptor
162 # ifdef CDS_DOXYGEN_INVOKED
163 typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
164 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
166 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
167 struct node_traits: public get_node_traits< value_type, node_type, hook>::type
169 static internal_node const& to_internal_node( tree_node const& n )
171 assert( n.is_internal() );
172 return static_cast<internal_node const&>( n );
175 static leaf_node const& to_leaf_node( tree_node const& n )
177 assert( n.is_leaf() );
178 return static_cast<leaf_node const&>( n );
183 typedef typename traits::item_counter item_counter; ///< Item counting policy
184 typedef typename traits::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model
185 typedef typename traits::stat stat; ///< internal statistics type
186 typedef typename traits::key_extractor key_extractor; ///< key extracting functor
188 typedef typename traits::node_allocator node_allocator; ///< Allocator for internal node
189 typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
191 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 9; ///< Count of hazard pointer required for the algorithm
195 typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
197 typedef cds::details::Allocator< internal_node, node_allocator > cxx_node_allocator;
198 typedef cds::details::Allocator< update_desc, update_desc_allocator > cxx_update_desc_allocator;
200 struct search_result {
205 Guard_updGrandParent,
209 // end of guard indices
213 typedef typename gc::template GuardArray< guard_count > guard_array;
216 internal_node * pGrandParent;
217 internal_node * pParent;
219 update_ptr updParent;
220 update_ptr updGrandParent;
221 bool bRightLeaf; // true if pLeaf is right child of pParent, false otherwise
222 bool bRightParent; // true if pParent is right child of pGrandParent, false otherwise
225 :pGrandParent( nullptr )
229 ,bRightParent( false )
236 internal_node m_Root; ///< Tree root node (key= Infinite2)
237 leaf_node m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
238 leaf_node m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
241 item_counter m_ItemCounter; ///< item counter
242 mutable stat m_Stat; ///< internal statistics
246 static void free_leaf_node( value_type * p )
251 internal_node * alloc_internal_node() const
253 m_Stat.onInternalNodeCreated();
254 internal_node * pNode = cxx_node_allocator().New();
258 static void free_internal_node( internal_node * pNode )
260 cxx_node_allocator().Delete( pNode );
263 struct internal_node_deleter {
264 void operator()( internal_node * p) const
266 free_internal_node( p );
270 typedef std::unique_ptr< internal_node, internal_node_deleter> unique_internal_node_ptr;
272 update_desc * alloc_update_desc() const
274 m_Stat.onUpdateDescCreated();
275 return cxx_update_desc_allocator().New();
278 static void free_update_desc( update_desc * pDesc )
280 cxx_update_desc_allocator().Delete( pDesc );
283 void retire_node( tree_node * pNode ) const
285 if ( pNode->is_leaf() ) {
286 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
287 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
289 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
292 assert( static_cast<internal_node *>( pNode ) != &m_Root );
293 m_Stat.onInternalNodeDeleted();
295 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
299 void retire_update_desc( update_desc * p ) const
301 m_Stat.onUpdateDescDeleted();
302 gc::template retire( p, free_update_desc );
305 void make_empty_tree()
307 m_Root.infinite_key( 2 );
308 m_LeafInf1.infinite_key( 1 );
309 m_LeafInf2.infinite_key( 2 );
310 m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
311 m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
316 /// Default constructor
319 static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
331 The function inserts \p val in the tree if it does not contain
332 an item with key equal to \p val.
334 Returns \p true if \p val is placed into the tree, \p false otherwise.
336 bool insert( value_type& val )
338 return insert( val, []( value_type& ) {} );
343 This function is intended for derived non-intrusive containers.
345 The function allows to split creating of new item into two part:
346 - create item with key only
347 - insert new item into the tree
348 - if inserting is success, calls \p f functor to initialize value-field of \p val.
350 The functor signature is:
352 void func( value_type& val );
354 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
355 \p val no any other changes could be made on this tree's item by concurrent threads.
356 The user-defined functor is called only if the inserting is success.
358 template <typename Func>
359 bool insert( value_type& val, Func f )
361 typename gc::Guard guardInsert;
362 guardInsert.assign( &val );
364 unique_internal_node_ptr pNewInternal;
369 if ( search( res, val, node_compare() )) {
370 if ( pNewInternal.get() )
371 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
372 m_Stat.onInsertFailed();
376 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
378 if ( !pNewInternal.get() )
379 pNewInternal.reset( alloc_internal_node() );
381 if ( try_insert( val, pNewInternal.get(), res )) {
383 pNewInternal.release(); // internal node is linked into the tree and should not be deleted
389 m_Stat.onInsertRetry();
393 m_Stat.onInsertSuccess();
399 The operation performs inserting or changing data with lock-free manner.
401 If the item \p val is not found in the set, then \p val is inserted into the set
402 iff \p bAllowInsert is \p true.
403 Otherwise, the functor \p func is called with item found.
404 The functor \p func signature is:
406 void func( bool bNew, value_type& item, value_type& val );
409 - \p bNew - \p true if the item has been inserted, \p false otherwise
410 - \p item - item of the set
411 - \p val - argument \p val passed into the \p %update() function
412 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
413 refer to the same thing.
415 The functor can change non-key fields of the \p item; however, \p func must guarantee
416 that during changing no any other modifications could be made on this item by concurrent threads.
418 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
419 i.e. the node has been inserted or updated,
420 \p second is \p true if new item has been added or \p false if the item with \p key
423 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
425 template <typename Func>
426 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
428 typename gc::Guard guardInsert;
429 guardInsert.assign( &val );
431 unique_internal_node_ptr pNewInternal;
436 if ( search( res, val, node_compare() )) {
437 func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
438 if ( pNewInternal.get() )
439 m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
440 m_Stat.onEnsureExist();
441 return std::make_pair( true, false );
444 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
446 return std::make_pair( false, false );
448 if ( !pNewInternal.get() )
449 pNewInternal.reset( alloc_internal_node() );
451 if ( try_insert( val, pNewInternal.get(), res )) {
452 func( true, val, val );
453 pNewInternal.release() ; // internal node has been linked into the tree and should not be deleted
459 m_Stat.onEnsureRetry();
463 m_Stat.onEnsureNew();
464 return std::make_pair( true, true );
467 template <typename Func>
468 CDS_DEPRECATED("ensure() is deprecated, use update()")
469 std::pair<bool, bool> ensure( value_type& val, Func func )
471 return update( val, func, true );
475 /// Unlinks the item \p val from the tree
477 The function searches the item \p val in the tree and unlink it from the tree
478 if it is found and is equal to \p val.
480 Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
481 and deletes the item found. \p unlink finds an item by key and deletes it
482 only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
484 The \p disposer specified in \p Traits class template parameter is called
485 by garbage collector \p GC asynchronously.
487 The function returns \p true if success and \p false otherwise.
489 bool unlink( value_type& val )
491 return erase_( val, node_compare(),
492 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
493 [](value_type const&) {} );
496 /// Deletes the item from the tree
497 /** \anchor cds_intrusive_EllenBinTree_erase
498 The function searches an item with key equal to \p key in the tree,
499 unlinks it from the tree, and returns \p true.
500 If the item with key equal to \p key is not found the function return \p false.
502 Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
503 that can be not the same as \p value_type.
505 template <typename Q>
506 bool erase( const Q& key )
508 return erase_( key, node_compare(),
509 []( Q const&, leaf_node const& ) -> bool { return true; },
510 [](value_type const&) {} );
513 /// Delete the item from the tree with comparing functor \p pred
515 The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
516 but \p pred predicate is used for key comparing.
517 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
518 "Predicate requirements".
519 \p pred must imply the same element order as the comparator used for building the tree.
521 template <typename Q, typename Less>
522 bool erase_with( const Q& key, Less pred )
525 typedef ellen_bintree::details::compare<
528 opt::details::make_comparator_from_less<Less>,
532 return erase_( key, compare_functor(),
533 []( Q const&, leaf_node const& ) -> bool { return true; },
534 [](value_type const&) {} );
537 /// Deletes the item from the tree
538 /** \anchor cds_intrusive_EllenBinTree_erase_func
539 The function searches an item with key equal to \p key in the tree,
540 call \p f functor with item found, unlinks it from the tree, and returns \p true.
541 The \ref disposer specified in \p Traits class template parameter is called
542 by garbage collector \p GC asynchronously.
544 The \p Func interface is
547 void operator()( value_type const& item );
551 If the item with key equal to \p key is not found the function return \p false.
553 Note the \p Traits::less and/or \p Traits::compare predicate should accept a parameter of type \p Q
554 that can be not the same as \p value_type.
556 template <typename Q, typename Func>
557 bool erase( Q const& key, Func f )
559 return erase_( key, node_compare(),
560 []( Q const&, leaf_node const& ) -> bool { return true; },
564 /// Delete the item from the tree with comparing functor \p pred
566 The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
567 but \p pred predicate is used for key comparing.
568 \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
569 "Predicate requirements".
570 \p pred must imply the same element order as the comparator used for building the tree.
572 template <typename Q, typename Less, typename Func>
573 bool erase_with( Q const& key, Less pred, Func f )
576 typedef ellen_bintree::details::compare<
579 opt::details::make_comparator_from_less<Less>,
583 return erase_( key, compare_functor(),
584 []( Q const&, leaf_node const& ) -> bool { return true; },
588 /// Extracts an item with minimal key from the tree
590 The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
591 If the tree is empty the function returns an empty guarded pointer.
593 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
594 It means that the function gets leftmost leaf of the tree and tries to unlink it.
595 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
596 So, the function returns the item with minimum key at the moment of tree traversing.
598 The returned \p guarded_ptr prevents disposer invocation for returned item,
599 see \p cds::gc::guarded_ptr for explanation.
600 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
602 guarded_ptr extract_min()
605 extract_min_( gp.guard() );
609 /// Extracts an item with maximal key from the tree
611 The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
612 If the tree is empty the function returns an empty \p guarded_ptr.
614 @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
615 It means that the function gets rightmost leaf of the tree and tries to unlink it.
616 During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
617 So, the function returns the item with maximal key at the moment of tree traversing.
619 The returned \p guarded_ptr prevents disposer invocation for returned item,
620 see cds::gc::guarded_ptr for explanation.
621 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
623 guarded_ptr extract_max()
626 extract_max_( gp.guard());
630 /// Extracts an item from the tree
631 /** \anchor cds_intrusive_EllenBinTree_extract
632 The function searches an item with key equal to \p key in the tree,
633 unlinks it, and returns a guarded pointer to an item found.
634 If the item is not found the function returns an empty \p guarded_ptr.
636 \p guarded_ptr prevents disposer invocation for returned item,
637 see cds::gc::guarded_ptr for explanation.
638 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
640 template <typename Q>
641 guarded_ptr extract( Q const& key )
644 extract_( gp.guard(), key );
648 /// Extracts an item from the tree using \p pred for searching
650 The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
651 but \p pred is used for key compare.
652 \p Less 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.
656 template <typename Q, typename Less>
657 guarded_ptr extract_with( Q const& key, Less pred )
660 extract_with_( gp.guard(), key, pred );
664 /// Checks whether the set contains \p key
666 The function searches the item with key equal to \p key
667 and returns \p true if it is found, and \p false otherwise.
669 template <typename Q>
670 bool contains( Q const& key ) const
673 if ( search( res, key, node_compare() )) {
674 m_Stat.onFindSuccess();
678 m_Stat.onFindFailed();
682 template <typename Q>
683 CDS_DEPRECATED("deprecated, use contains()")
684 bool find( Q const& key ) const
686 return contains( key );
690 /// Checks whether the set contains \p key using \p pred predicate for searching
692 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
693 \p Less functor has the interface like \p std::less.
694 \p Less must imply the same element order as the comparator used for building the set.
696 template <typename Q, typename Less>
697 bool contains( Q const& key, Less pred ) const
700 typedef ellen_bintree::details::compare<
703 opt::details::make_comparator_from_less<Less>,
708 if ( search( res, key, compare_functor() )) {
709 m_Stat.onFindSuccess();
712 m_Stat.onFindFailed();
716 template <typename Q, typename Less>
717 CDS_DEPRECATED("deprecated, use contains()")
718 bool find_with( Q const& key, Less pred ) const
720 return contains( key, pred );
724 /// Finds the key \p key
725 /** @anchor cds_intrusive_EllenBinTree_find_func
726 The function searches the item with key equal to \p key and calls the functor \p f for item found.
727 The interface of \p Func functor is:
730 void operator()( value_type& item, Q& key );
733 where \p item is the item found, \p key is the <tt>find</tt> function argument.
735 The functor can change non-key fields of \p item. Note that the functor is only guarantee
736 that \p item cannot be disposed during functor is executing.
737 The functor does not serialize simultaneous access to the tree \p item. If such access is
738 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
740 The function returns \p true if \p key is found, \p false otherwise.
742 template <typename Q, typename Func>
743 bool find( Q& key, Func f ) const
745 return find_( key, f );
748 template <typename Q, typename Func>
749 bool find( Q const& key, Func f ) const
751 return find_( key, f );
755 /// Finds the key \p key with comparing functor \p pred
757 The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
758 but \p pred is used for key comparison.
759 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
760 "Predicate requirements".
761 \p pred must imply the same element order as the comparator used for building the tree.
763 template <typename Q, typename Less, typename Func>
764 bool find_with( Q& key, Less pred, Func f ) const
766 return find_with_( key, pred, f );
769 template <typename Q, typename Less, typename Func>
770 bool find_with( Q const& key, Less pred, Func f ) const
772 return find_with_( key, pred, f );
776 /// Finds \p key and returns the item found
777 /** @anchor cds_intrusive_EllenBinTree_get
778 The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
779 The function returns an empty guarded pointer is \p key is not found.
781 \p guarded_ptr prevents disposer invocation for returned item,
782 see \p cds::gc::guarded_ptr for explanation.
783 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
785 template <typename Q>
786 guarded_ptr get( Q const& key ) const
789 get_( gp.guard(), key );
793 /// Finds \p key with predicate \p pred and returns the item found
795 The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
796 but \p pred is used for key comparing.
797 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
798 "Predicate requirements".
799 \p pred must imply the same element order as the comparator used for building the tree.
801 template <typename Q, typename Less>
802 guarded_ptr get_with( Q const& key, Less pred ) const
805 get_with_( gp.guard(), key, pred );
809 /// Checks if the tree is empty
812 return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
815 /// Clears the tree (thread safe, not atomic)
817 The function unlink all items from the tree.
818 The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
822 assert( tree.empty() );
824 the assertion could be raised.
826 For each leaf the \p disposer will be called after unlinking.
836 /// Clears the tree (not thread safe)
838 This function is not thread safe and may be called only when no other thread deals with the tree.
839 The function is used in the tree destructor.
844 internal_node * pParent = nullptr;
845 internal_node * pGrandParent = nullptr;
846 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
849 while ( pLeaf->is_internal() ) {
850 pGrandParent = pParent;
851 pParent = static_cast<internal_node *>( pLeaf );
852 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
855 if ( pLeaf->infinite_key()) {
860 // Remove leftmost leaf and its parent node
861 assert( pGrandParent );
863 assert( pLeaf->is_leaf() );
865 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
866 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
867 free_internal_node( pParent );
871 /// Returns item count in the tree
873 Only leaf nodes containing user data are counted.
875 The value returned depends on item counter type provided by \p Traits template parameter.
876 If it is \p atomicity::empty_item_counter this function always returns 0.
877 The function is not suitable for checking the tree emptiness, use \p empty()
878 member function for this purpose.
882 return m_ItemCounter;
885 /// Returns const reference to internal statistics
886 stat const& statistics() const
891 /// Checks internal consistency (not atomic, not thread-safe)
893 The debugging function to check internal consistency of the tree.
895 bool check_consistency() const
897 return check_consistency( &m_Root );
903 bool check_consistency( internal_node const * pRoot ) const
905 tree_node * pLeft = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
906 tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
910 if ( node_compare()( *pLeft, *pRoot ) < 0
911 && node_compare()( *pRoot, *pRight ) <= 0
912 && node_compare()( *pLeft, *pRight ) < 0 )
915 if ( pLeft->is_internal() )
916 bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
919 if ( bRet && pRight->is_internal() )
920 bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
928 tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
931 tree_node * p = bRight
932 ? res.guards.protect( search_result::Guard_Leaf, pParent->m_pRight,
933 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
934 : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
935 []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});
937 // If we use member hook, data node pointer != internal node pointer
938 // So, we need protect the child twice: as internal node and as data node
939 // and then analyze what kind of node we have
940 tree_node * pVal = bRight
941 ? res.guards.protect( search_result::Guard_temporary, pParent->m_pRight,
942 []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} )
943 : res.guards.protect( search_result::Guard_temporary, pParent->m_pLeft,
944 []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} );
946 // child node is guarded
947 // See whether pParent->m_pUpdate has not been changed
948 if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
949 // update has been changed - returns nullptr as a flag to search retry
956 if ( p && p->is_leaf())
957 res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));
959 res.guards.clear( search_result::Guard_temporary );
964 static update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src )
966 return res.guards.protect( search_result::Guard_updParent, src, [](update_ptr p) -> update_desc* { return p.ptr(); });
969 template <typename KeyValue, typename Compare>
970 bool search( search_result& res, KeyValue const& key, Compare cmp ) const
972 internal_node * pParent;
973 internal_node * pGrandParent = nullptr;
974 update_ptr updParent;
975 update_ptr updGrandParent;
977 bool bRightParent = false;
983 //pGrandParent = nullptr;
986 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
987 while ( pLeaf->is_internal() ) {
988 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
989 pGrandParent = pParent;
990 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
991 pParent = static_cast<internal_node *>( pLeaf );
992 bRightParent = bRightLeaf;
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 nCmp = cmp( key, *pParent );
1006 bRightLeaf = nCmp >= 0;
1008 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1010 m_Stat.onSearchRetry();
1015 assert( pLeaf->is_leaf() );
1016 nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1018 res.pGrandParent = pGrandParent;
1019 res.pParent = pParent;
1020 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1021 res.updParent = updParent;
1022 res.updGrandParent = updGrandParent;
1023 res.bRightParent = bRightParent;
1024 res.bRightLeaf = bRightLeaf;
1029 bool search_min( search_result& res ) const
1031 internal_node * pParent;
1032 internal_node * pGrandParent;
1033 update_ptr updParent;
1034 update_ptr updGrandParent;
1038 pGrandParent = nullptr;
1039 updParent = nullptr;
1040 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1041 while ( pLeaf->is_internal() ) {
1042 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1043 pGrandParent = pParent;
1044 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1045 pParent = static_cast<internal_node *>( pLeaf );
1046 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1047 updGrandParent = updParent;
1049 updParent = search_protect_update( res, pParent->m_pUpdate );
1051 switch ( updParent.bits() ) {
1052 case update_desc::DFlag:
1053 case update_desc::Mark:
1054 m_Stat.onSearchRetry();
1058 pLeaf = protect_child_node( res, pParent, false, updParent );
1060 m_Stat.onSearchRetry();
1065 if ( pLeaf->infinite_key())
1068 res.pGrandParent = pGrandParent;
1069 res.pParent = pParent;
1070 assert( pLeaf->is_leaf() );
1071 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1072 res.updParent = updParent;
1073 res.updGrandParent = updGrandParent;
1074 res.bRightParent = false;
1075 res.bRightLeaf = false;
1080 bool search_max( search_result& res ) const
1082 internal_node * pParent;
1083 internal_node * pGrandParent;
1084 update_ptr updParent;
1085 update_ptr updGrandParent;
1087 bool bRightParent = false;
1091 pGrandParent = nullptr;
1092 updParent = nullptr;
1094 tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1095 while ( pLeaf->is_internal() ) {
1096 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1097 pGrandParent = pParent;
1098 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1099 pParent = static_cast<internal_node *>( pLeaf );
1100 bRightParent = bRightLeaf;
1101 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1102 updGrandParent = updParent;
1104 updParent = search_protect_update( res, pParent->m_pUpdate );
1106 switch ( updParent.bits() ) {
1107 case update_desc::DFlag:
1108 case update_desc::Mark:
1109 m_Stat.onSearchRetry();
1113 bRightLeaf = !pParent->infinite_key();
1114 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1116 m_Stat.onSearchRetry();
1121 if ( pLeaf->infinite_key())
1124 res.pGrandParent = pGrandParent;
1125 res.pParent = pParent;
1126 assert( pLeaf->is_leaf() );
1127 res.pLeaf = static_cast<leaf_node *>( pLeaf );
1128 res.updParent = updParent;
1129 res.updGrandParent = updGrandParent;
1130 res.bRightParent = bRightParent;
1131 res.bRightLeaf = bRightLeaf;
1137 void help( update_ptr pUpdate )
1139 // pUpdate must be guarded!
1140 switch ( pUpdate.bits() ) {
1141 case update_desc::IFlag:
1142 help_insert( pUpdate.ptr() );
1143 m_Stat.onHelpInsert();
1145 case update_desc::DFlag:
1146 help_delete( pUpdate.ptr() );
1147 m_Stat.onHelpDelete();
1149 case update_desc::Mark:
1150 //m_Stat.onHelpMark();
1151 //help_marked( pUpdate.ptr() );
1157 void help_insert( update_desc * pOp )
1159 // pOp must be guarded
1161 tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1162 if ( pOp->iInfo.bRightLeaf ) {
1163 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1164 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1167 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1168 memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1172 update_ptr cur( pOp, update_desc::IFlag );
1173 CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1174 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1177 bool check_delete_precondition( search_result& res ) const
1179 // precondition: all member of res must be guarded
1181 assert( res.pGrandParent != nullptr );
1183 return static_cast<internal_node *>(res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1184 && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1187 bool help_delete( update_desc * pOp )
1189 // precondition: pOp must be guarded
1191 update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1192 update_ptr pMark( pOp, update_desc::Mark );
1193 if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1194 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1198 retire_node( pOp->dInfo.pParent );
1199 retire_node( pOp->dInfo.pLeaf );
1200 retire_update_desc( pOp );
1203 else if ( pUpdate == pMark ) {
1204 // some other thread is processing help_marked()
1206 m_Stat.onHelpMark();
1210 // Undo grandparent dInfo
1211 update_ptr pDel( pOp, update_desc::DFlag );
1212 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1213 memory_model::memory_order_release, atomics::memory_order_relaxed ))
1215 retire_update_desc( pOp );
1221 static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1223 tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
1224 if ( pSibling->is_leaf() )
1225 guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
1229 void help_marked( update_desc * pOp )
1231 // precondition: pOp must be guarded
1233 tree_node * pParent = pOp->dInfo.pParent;
1235 typename gc::Guard guard;
1236 tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1238 if ( pOp->dInfo.bRightParent ) {
1239 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1240 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1243 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1244 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1247 update_ptr upd( pOp, update_desc::DFlag );
1248 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1249 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1252 bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1254 assert( res.updParent.bits() == update_desc::Clean );
1255 assert( res.pLeaf->is_leaf() );
1257 // check search result
1258 if ( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_acquire ) == res.pLeaf ) {
1259 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1261 int nCmp = node_compare()(val, *res.pLeaf);
1263 if ( res.pGrandParent ) {
1264 assert( !res.pLeaf->infinite_key() );
1265 pNewInternal->infinite_key( 0 );
1266 key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1269 assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1270 pNewInternal->infinite_key( 1 );
1272 pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1273 pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1276 assert( !res.pLeaf->is_internal() );
1278 pNewInternal->infinite_key( 0 );
1279 key_extractor()(pNewInternal->m_Key, val);
1280 pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1281 pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1282 assert( !res.pLeaf->infinite_key() );
1285 typename gc::Guard guard;
1286 update_desc * pOp = alloc_update_desc();
1287 guard.assign( pOp );
1289 pOp->iInfo.pParent = res.pParent;
1290 pOp->iInfo.pNew = pNewInternal;
1291 pOp->iInfo.pLeaf = res.pLeaf;
1292 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1294 update_ptr updCur( res.updParent.ptr() );
1295 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1296 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1299 retire_update_desc( pOp );
1303 m_Stat.onUpdateDescDeleted();
1304 free_update_desc( pOp );
1311 template <typename Q, typename Compare, typename Equal, typename Func>
1312 bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1314 update_desc * pOp = nullptr;
1319 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1321 retire_update_desc( pOp );
1322 m_Stat.onEraseFailed();
1326 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1328 pOp = alloc_update_desc();
1329 if ( check_delete_precondition( res ) ) {
1330 typename gc::Guard guard;
1331 guard.assign( pOp );
1333 pOp->dInfo.pGrandParent = res.pGrandParent;
1334 pOp->dInfo.pParent = res.pParent;
1335 pOp->dInfo.pLeaf = res.pLeaf;
1336 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1337 pOp->dInfo.bRightParent = res.bRightParent;
1338 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1340 update_ptr updGP( res.updGrandParent.ptr() );
1341 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1342 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1343 if ( help_delete( pOp ) ) {
1344 // res.pLeaf is not deleted yet since it is guarded
1345 f( *node_traits::to_value_ptr( res.pLeaf ) );
1354 m_Stat.onEraseRetry();
1358 m_Stat.onEraseSuccess();
1362 template <typename Q>
1363 bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
1365 return erase_( key, node_compare(),
1366 []( Q const&, leaf_node const& ) -> bool { return true; },
1367 [&guard]( value_type& found ) { guard.set( &found ); } );
1370 template <typename Q, typename Less>
1371 bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
1373 typedef ellen_bintree::details::compare<
1376 opt::details::make_comparator_from_less<Less>,
1380 return erase_( key, compare_functor(),
1381 []( Q const&, leaf_node const& ) -> bool { return true; },
1382 [&guard]( value_type& found ) { guard.set( &found ); } );
1385 bool extract_max_( typename guarded_ptr::native_guard& gp )
1387 update_desc * pOp = nullptr;
1392 if ( !search_max( res )) {
1395 retire_update_desc( pOp );
1396 m_Stat.onExtractMaxFailed();
1400 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1402 pOp = alloc_update_desc();
1403 if ( check_delete_precondition( res ) ) {
1404 typename gc::Guard guard;
1405 guard.assign( pOp );
1407 pOp->dInfo.pGrandParent = res.pGrandParent;
1408 pOp->dInfo.pParent = res.pParent;
1409 pOp->dInfo.pLeaf = res.pLeaf;
1410 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1411 pOp->dInfo.bRightParent = res.bRightParent;
1412 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1414 update_ptr updGP( res.updGrandParent.ptr() );
1415 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1416 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1418 if ( help_delete( pOp ) )
1426 m_Stat.onExtractMaxRetry();
1430 m_Stat.onExtractMaxSuccess();
1431 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1435 bool extract_min_( typename guarded_ptr::native_guard& gp )
1437 update_desc * pOp = nullptr;
1442 if ( !search_min( res )) {
1445 retire_update_desc( pOp );
1446 m_Stat.onExtractMinFailed();
1450 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1452 pOp = alloc_update_desc();
1453 if ( check_delete_precondition( res ) ) {
1454 typename gc::Guard guard;
1455 guard.assign( pOp );
1457 pOp->dInfo.pGrandParent = res.pGrandParent;
1458 pOp->dInfo.pParent = res.pParent;
1459 pOp->dInfo.pLeaf = res.pLeaf;
1460 pOp->dInfo.pUpdateParent = res.updParent.ptr();
1461 pOp->dInfo.bRightParent = res.bRightParent;
1462 pOp->dInfo.bRightLeaf = res.bRightLeaf;
1464 update_ptr updGP( res.updGrandParent.ptr() );
1465 if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1466 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1468 if ( help_delete( pOp ))
1476 m_Stat.onExtractMinRetry();
1480 m_Stat.onExtractMinSuccess();
1481 gp.set( node_traits::to_value_ptr( res.pLeaf ));
1485 template <typename Q, typename Func>
1486 bool find_( Q& val, Func f ) const
1489 if ( search( res, val, node_compare() )) {
1490 assert( res.pLeaf );
1491 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1493 m_Stat.onFindSuccess();
1497 m_Stat.onFindFailed();
1501 template <typename Q, typename Less, typename Func>
1502 bool find_with_( Q& val, Less /*pred*/, Func f ) const
1504 typedef ellen_bintree::details::compare<
1507 opt::details::make_comparator_from_less<Less>,
1512 if ( search( res, val, compare_functor() )) {
1513 assert( res.pLeaf );
1514 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1516 m_Stat.onFindSuccess();
1520 m_Stat.onFindFailed();
1524 template <typename Q>
1525 bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
1527 return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1530 template <typename Q, typename Less>
1531 bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
1533 return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1539 }} // namespace cds::intrusive
1541 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H