Removed unused vars
[libcds.git] / cds / intrusive / impl / ellen_bintree.h
1 //$$CDS-header$$
2
3 #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
4 #define __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H
5
6 #include <memory>
7 #include <cds/intrusive/details/ellen_bintree_base.h>
8 #include <cds/opt/compare.h>
9 #include <cds/details/binary_functor_wrapper.h>
10 #include <cds/urcu/details/check_deadlock.h>
11
12 namespace cds { namespace intrusive {
13
14     /// Ellen's et al binary search tree
15     /** @ingroup cds_intrusive_map
16         @ingroup cds_intrusive_tree
17         @anchor cds_intrusive_EllenBinTree
18
19         Source:
20             - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
21
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.
30
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.
34
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.
39
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>.
42
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")
48
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.
58
59         @anchor cds_intrusive_EllenBinTree_less
60         <b>Predicate requirements</b>
61
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:
65         \code
66         struct Foo: public cds::intrusive::ellen_bintree::node< ... >
67         {
68             std::string m_strKey;
69             ...
70         };
71
72         struct less {
73             bool operator()( Foo const& v1, Foo const& v2 ) const
74             { return v1.m_strKey < v2.m_strKey ; }
75
76             bool operator()( Foo const& v, std::string const& s ) const
77             { return v.m_strKey < s ; }
78
79             bool operator()( std::string const& s, Foo const& v ) const
80             { return s < v.m_strKey ; }
81
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 ; }
85
86             bool operator()( Foo const& v, char const * p ) const
87             { return v.m_strKey.compare(p) < 0 ; }
88
89             bool operator()( char const * p, std::string const& s ) const
90             { return s.compare(p) > 0; }
91
92             bool operator()( char const * p, Foo const& v ) const
93             { return v.m_strKey.compare(p) > 0; }
94         };
95         \endcode
96
97         Usage examples see \ref cds_intrusive_EllenBinTree_usage "here"
98     */
99     template < class GC,
100         typename Key,
101         typename T,
102 #ifdef CDS_DOXYGEN_INVOKED
103         class Traits = ellen_bintree::traits
104 #else
105         class Traits
106 #endif
107     >
108     class EllenBinTree
109     {
110     public:
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
115
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
120
121         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
122
123     protected:
124         //@cond
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
131         //@endcond
132
133     public:
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
137 #   else
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
140         {
141             static internal_node const& to_internal_node( tree_node const& n )
142             {
143                 assert( n.is_internal() );
144                 return static_cast<internal_node const&>( n );
145             }
146
147             static leaf_node const& to_leaf_node( tree_node const& n )
148             {
149                 assert( n.is_leaf() );
150                 return static_cast<leaf_node const&>( n );
151             }
152         };
153 #   endif
154
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
159
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
162
163     protected:
164         //@cond
165         typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
166
167         typedef cds::details::Allocator< internal_node, node_allocator >        cxx_node_allocator;
168         typedef cds::details::Allocator< update_desc, update_desc_allocator >   cxx_update_desc_allocator;
169
170         struct search_result {
171             enum guard_index {
172                 Guard_GrandParent,
173                 Guard_Parent,
174                 Guard_Leaf,
175                 Guard_updGrandParent,
176                 Guard_updParent,
177
178                 // helping
179                 Guard_helpLeaf,
180
181                 // end of guard indices
182                 guard_count
183             };
184
185             typedef typename gc::template GuardArray< guard_count > guard_array;
186             guard_array guards;
187
188             internal_node *     pGrandParent;
189             internal_node *     pParent;
190             leaf_node *         pLeaf;
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
195
196             search_result()
197                 :pGrandParent( nullptr )
198                 ,pParent( nullptr )
199                 ,pLeaf( nullptr )
200                 ,bRightLeaf( false )
201                 ,bRightParent( false )
202             {}
203
204             void clean_help_guards()
205             {
206                 guards.clear( Guard_helpLeaf );
207             }
208         };
209         //@endcond
210
211     protected:
212         //@cond
213         internal_node       m_Root;     ///< Tree root node (key= Infinite2)
214         leaf_node           m_LeafInf1; ///< Infinite leaf 1 (key= Infinite1)
215         leaf_node           m_LeafInf2; ///< Infinite leaf 2 (key= Infinite2)
216         //@endcond
217
218         item_counter        m_ItemCounter;  ///< item counter
219         mutable stat        m_Stat;         ///< internal statistics
220
221     protected:
222         //@cond
223         static void free_leaf_node( value_type * p )
224         {
225             disposer()( p );
226         }
227
228         internal_node * alloc_internal_node() const
229         {
230             m_Stat.onInternalNodeCreated();
231             internal_node * pNode = cxx_node_allocator().New();
232             return pNode;
233         }
234
235         static void free_internal_node( internal_node * pNode )
236         {
237             cxx_node_allocator().Delete( pNode );
238         }
239
240         struct internal_node_deleter {
241             void operator()( internal_node * p) const
242             {
243                 free_internal_node( p );
244             }
245         };
246
247         typedef std::unique_ptr< internal_node, internal_node_deleter>  unique_internal_node_ptr;
248
249         update_desc * alloc_update_desc() const
250         {
251             m_Stat.onUpdateDescCreated();
252             return cxx_update_desc_allocator().New();
253         }
254
255         static void free_update_desc( update_desc * pDesc )
256         {
257             cxx_update_desc_allocator().Delete( pDesc );
258         }
259
260         void retire_node( tree_node * pNode ) const
261         {
262             if ( pNode->is_leaf() ) {
263                 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
264                 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
265
266                 gc::template retire( node_traits::to_value_ptr( static_cast<leaf_node *>( pNode )), free_leaf_node );
267             }
268             else {
269                 assert( static_cast<internal_node *>( pNode ) != &m_Root );
270                 m_Stat.onInternalNodeDeleted();
271
272                 gc::template retire( static_cast<internal_node *>( pNode ), free_internal_node );
273             }
274         }
275
276         void retire_update_desc( update_desc * p ) const
277         {
278             m_Stat.onUpdateDescDeleted();
279             gc::template retire( p, free_update_desc );
280         }
281
282         void make_empty_tree()
283         {
284             m_Root.infinite_key( 2 );
285             m_LeafInf1.infinite_key( 1 );
286             m_LeafInf2.infinite_key( 2 );
287             m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
288             m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
289         }
290         //@endcond
291
292     public:
293         /// Default constructor
294         EllenBinTree()
295         {
296             static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
297             make_empty_tree();
298         }
299
300         /// Clears the tree
301         ~EllenBinTree()
302         {
303             unsafe_clear();
304         }
305
306         /// Inserts new node
307         /**
308             The function inserts \p val in the tree if it does not contain
309             an item with key equal to \p val.
310
311             Returns \p true if \p val is placed into the tree, \p false otherwise.
312         */
313         bool insert( value_type& val )
314         {
315             return insert( val, []( value_type& ) {} );
316         }
317
318         /// Inserts new node
319         /**
320             This function is intended for derived non-intrusive containers.
321
322             The function allows to split creating of new item into two part:
323             - create item with key only
324             - insert new item into the tree
325             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
326
327             The functor signature is:
328             \code
329                 void func( value_type& val );
330             \endcode
331             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
332             \p val no any other changes could be made on this tree's item by concurrent threads.
333             The user-defined functor is called only if the inserting is success.
334         */
335         template <typename Func>
336         bool insert( value_type& val, Func f )
337         {
338             typename gc::Guard guardInsert;
339             guardInsert.assign( &val );
340
341             unique_internal_node_ptr pNewInternal;
342             search_result res;
343             back_off bkoff;
344
345             for ( ;; ) {
346                 if ( search( res, val, node_compare() )) {
347                     if ( pNewInternal.get() )
348                         m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
349                     m_Stat.onInsertFailed();
350                     return false;
351                 }
352
353                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
354
355                     if ( !pNewInternal.get() )
356                         pNewInternal.reset( alloc_internal_node() );
357
358                     if ( try_insert( val, pNewInternal.get(), res )) {
359                         f( val );
360                         pNewInternal.release(); // internal node is linked into the tree and should not be deleted
361                         break;
362                     }
363                 }
364
365                 bkoff();
366                 m_Stat.onInsertRetry();
367             }
368
369             ++m_ItemCounter;
370             m_Stat.onInsertSuccess();
371             return true;
372         }
373
374         /// Ensures that the \p val exists in the tree
375         /**
376             The operation performs inserting or changing data with lock-free manner.
377
378             If the item \p val is not found in the tree, then \p val is inserted into the tree.
379             Otherwise, the functor \p func is called with item found.
380             The functor signature is:
381             \code
382                 void func( bool bNew, value_type& item, value_type& val );
383             \endcode
384             with arguments:
385             - \p bNew - \p true if the item has been inserted, \p false otherwise
386             - \p item - an item of the tree
387             - \p val - the argument \p val passed to the \p ensure function
388             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
389             refer to the same thing.
390
391             The functor can change non-key fields of the \p item; however, \p func must guarantee
392             that during changing no any other modifications could be made on this item by concurrent threads.
393
394             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
395             \p second is \p true if new item has been added or \p false if the item with \p key
396             already is in the tree.
397
398             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
399         */
400         template <typename Func>
401         std::pair<bool, bool> ensure( value_type& val, Func func )
402         {
403             typename gc::Guard guardInsert;
404             guardInsert.assign( &val );
405
406             unique_internal_node_ptr pNewInternal;
407             search_result res;
408             back_off bkoff;
409
410             for ( ;; ) {
411                 if ( search( res, val, node_compare() )) {
412                     func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
413                     if ( pNewInternal.get() )
414                         m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
415                     m_Stat.onEnsureExist();
416                     return std::make_pair( true, false );
417                 }
418
419                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean )  {
420
421                     if ( !pNewInternal.get() )
422                         pNewInternal.reset( alloc_internal_node() );
423
424                     if ( try_insert( val, pNewInternal.get(), res )) {
425                         func( true, val, val );
426                         pNewInternal.release()  ;   // internal node has been linked into the tree and should not be deleted
427                         break;
428                     }
429                 }
430
431                 bkoff();
432                 m_Stat.onEnsureRetry();
433             }
434
435             ++m_ItemCounter;
436             m_Stat.onEnsureNew();
437             return std::make_pair( true, true );
438         }
439
440         /// Unlinks the item \p val from the tree
441         /**
442             The function searches the item \p val in the tree and unlink it from the tree
443             if it is found and is equal to \p val.
444
445             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
446             and deletes the item found. \p unlink finds an item by key and deletes it
447             only if \p val is a node, i.e. the pointer to item found is equal to <tt> &val </tt>.
448
449             The \p disposer specified in \p Traits class template parameter is called
450             by garbage collector \p GC asynchronously.
451
452             The function returns \p true if success and \p false otherwise.
453         */
454         bool unlink( value_type& val )
455         {
456             return erase_( val, node_compare(),
457                 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
458                 [](value_type const&) {} );
459         }
460
461         /// Deletes the item from the tree
462         /** \anchor cds_intrusive_EllenBinTree_erase
463             The function searches an item with key equal to \p key in the tree,
464             unlinks it from the tree, and returns \p true.
465             If the item with key equal to \p key is not found the function return \p false.
466
467             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
468         */
469         template <typename Q>
470         bool erase( const Q& key )
471         {
472             return erase_( key, node_compare(),
473                 []( Q const&, leaf_node const& ) -> bool { return true; },
474                 [](value_type const&) {} );
475         }
476
477         /// Delete the item from the tree with comparing functor \p pred
478         /**
479             The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
480             but \p pred predicate is used for key comparing.
481             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
482             "Predicate requirements".
483             \p pred must imply the same element order as the comparator used for building the tree.
484         */
485         template <typename Q, typename Less>
486         bool erase_with( const Q& key, Less pred )
487         {
488             CDS_UNUSED( pred );
489             typedef ellen_bintree::details::compare<
490                 key_type,
491                 value_type,
492                 opt::details::make_comparator_from_less<Less>,
493                 node_traits
494             > compare_functor;
495
496             return erase_( key, compare_functor(),
497                 []( Q const&, leaf_node const& ) -> bool { return true; },
498                 [](value_type const&) {} );
499         }
500
501         /// Deletes the item from the tree
502         /** \anchor cds_intrusive_EllenBinTree_erase_func
503             The function searches an item with key equal to \p key in the tree,
504             call \p f functor with item found, unlinks it from the tree, and returns \p true.
505             The \ref disposer specified in \p Traits class template parameter is called
506             by garbage collector \p GC asynchronously.
507
508             The \p Func interface is
509             \code
510             struct functor {
511                 void operator()( value_type const& item );
512             };
513             \endcode
514
515             If the item with key equal to \p key is not found the function return \p false.
516
517             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
518         */
519         template <typename Q, typename Func>
520         bool erase( Q const& key, Func f )
521         {
522             return erase_( key, node_compare(),
523                 []( Q const&, leaf_node const& ) -> bool { return true; },
524                 f );
525         }
526
527         /// Delete the item from the tree with comparing functor \p pred
528         /**
529             The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
530             but \p pred predicate is used for key comparing.
531             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
532             "Predicate requirements".
533             \p pred must imply the same element order as the comparator used for building the tree.
534         */
535         template <typename Q, typename Less, typename Func>
536         bool erase_with( Q const& key, Less pred, Func f )
537         {
538             CDS_UNUSED( pred );
539             typedef ellen_bintree::details::compare<
540                 key_type,
541                 value_type,
542                 opt::details::make_comparator_from_less<Less>,
543                 node_traits
544             > compare_functor;
545
546             return erase_( key, compare_functor(),
547                 []( Q const&, leaf_node const& ) -> bool { return true; },
548                 f );
549         }
550
551         /// Extracts an item with minimal key from the tree
552         /**
553             The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
554             If the tree is empty the function returns an empty guarded pointer.
555
556             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
557             It means that the function gets leftmost leaf of the tree and tries to unlink it.
558             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
559             So, the function returns the item with minimum key at the moment of tree traversing.
560
561             The returned \p guarded_ptr prevents disposer invocation for returned item,
562             see \p cds::gc::guarded_ptr for explanation.
563             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
564         */
565         guarded_ptr extract_min()
566         {
567             guarded_ptr gp;
568             extract_min_( gp.guard() );
569             return gp;
570         }
571
572         /// Extracts an item with maximal key from the tree
573         /**
574             The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
575             If the tree is empty the function returns an empty \p guarded_ptr.
576
577             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
578             It means that the function gets rightmost leaf of the tree and tries to unlink it.
579             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
580             So, the function returns the item with maximal key at the moment of tree traversing.
581
582             The returned \p guarded_ptr prevents disposer invocation for returned item,
583             see cds::gc::guarded_ptr for explanation.
584             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
585         */
586         guarded_ptr extract_max()
587         {
588             guarded_ptr gp;
589             extract_max_( gp.guard());
590             return gp;
591         }
592
593         /// Extracts an item from the tree
594         /** \anchor cds_intrusive_EllenBinTree_extract
595             The function searches an item with key equal to \p key in the tree,
596             unlinks it, and returns a guarded pointer to an item found.
597             If the item  is not found the function returns an empty \p guarded_ptr.
598
599             \p guarded_ptr prevents disposer invocation for returned item,
600             see cds::gc::guarded_ptr for explanation.
601             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
602         */
603         template <typename Q>
604         guarded_ptr extract( Q const& key )
605         {
606             guarded_ptr gp;
607             extract_( gp.guard(), key );
608             return gp;
609         }
610
611         /// Extracts an item from the tree using \p pred for searching
612         /**
613             The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
614             but \p pred is used for key compare.
615             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
616             "Predicate requirements".
617             \p pred must imply the same element order as the comparator used for building the tree.
618         */
619         template <typename Q, typename Less>
620         guarded_ptr extract_with( Q const& key, Less pred )
621         {
622             guarded_ptr gp;
623             extract_with_( gp.guard(), key, pred );
624             return gp;
625         }
626
627         /// Finds the key \p key
628         /** @anchor cds_intrusive_EllenBinTree_find_val
629             The function searches the item with key equal to \p key
630             and returns \p true if it is found, and \p false otherwise.
631
632             Note the hash functor specified for class \p Traits template parameter
633             should accept a parameter of type \p Q that can be not the same as \p value_type.
634         */
635         template <typename Q>
636         bool find( Q const& key ) const
637         {
638             search_result    res;
639             if ( search( res, key, node_compare() )) {
640                 m_Stat.onFindSuccess();
641                 return true;
642             }
643
644             m_Stat.onFindFailed();
645             return false;
646         }
647
648         /// Finds the key \p key with comparing functor \p pred
649         /**
650             The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
651             but \p pred is used for key compare.
652             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
653             "Predicate requirements".
654             \p pred must imply the same element order as the comparator used for building the tree.
655             \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
656         */
657         template <typename Q, typename Less>
658         bool find_with( Q const& key, Less pred ) const
659         {
660             CDS_UNUSED( pred );
661             typedef ellen_bintree::details::compare<
662                 key_type,
663                 value_type,
664                 opt::details::make_comparator_from_less<Less>,
665                 node_traits
666             > compare_functor;
667
668             search_result    res;
669             if ( search( res, key, compare_functor() )) {
670                 m_Stat.onFindSuccess();
671                 return true;
672             }
673             m_Stat.onFindFailed();
674             return false;
675         }
676
677         /// Finds the key \p key
678         /** @anchor cds_intrusive_EllenBinTree_find_func
679             The function searches the item with key equal to \p key and calls the functor \p f for item found.
680             The interface of \p Func functor is:
681             \code
682             struct functor {
683                 void operator()( value_type& item, Q& key );
684             };
685             \endcode
686             where \p item is the item found, \p key is the <tt>find</tt> function argument.
687
688             The functor can change non-key fields of \p item. Note that the functor is only guarantee
689             that \p item cannot be disposed during functor is executing.
690             The functor does not serialize simultaneous access to the tree \p item. If such access is
691             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
692
693             The function returns \p true if \p key is found, \p false otherwise.
694         */
695         template <typename Q, typename Func>
696         bool find( Q& key, Func f ) const
697         {
698             return find_( key, f );
699         }
700         //@cond
701         template <typename Q, typename Func>
702         bool find( Q const& key, Func f ) const
703         {
704             return find_( key, f );
705         }
706         //@endcond
707
708         /// Finds the key \p key with comparing functor \p pred
709         /**
710             The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
711             but \p pred is used for key comparison.
712             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
713             "Predicate requirements".
714             \p pred must imply the same element order as the comparator used for building the tree.
715         */
716         template <typename Q, typename Less, typename Func>
717         bool find_with( Q& key, Less pred, Func f ) const
718         {
719             return find_with_( key, pred, f );
720         }
721         //@cond
722         template <typename Q, typename Less, typename Func>
723         bool find_with( Q const& key, Less pred, Func f ) const
724         {
725             return find_with_( key, pred, f );
726         }
727         //@endcond
728
729         /// Finds \p key and returns the item found
730         /** @anchor cds_intrusive_EllenBinTree_get
731             The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
732             The function returns an empty guarded pointer is \p key is not found.
733
734             \p guarded_ptr prevents disposer invocation for returned item,
735             see \p cds::gc::guarded_ptr for explanation.
736             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
737         */
738         template <typename Q>
739         guarded_ptr get( Q const& key ) const
740         {
741             guarded_ptr gp;
742             get_( gp.guard(), key );
743             return gp;
744         }
745
746         /// Finds \p key with predicate \p pred and returns the item found
747         /**
748             The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
749             but \p pred is used for key comparing.
750             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
751             "Predicate requirements".
752             \p pred must imply the same element order as the comparator used for building the tree.
753         */
754         template <typename Q, typename Less>
755         guarded_ptr get_with( Q const& key, Less pred ) const
756         {
757             guarded_ptr gp;
758             get_with_( gp.guard(), key, pred );
759             return gp;
760         }
761
762         /// Checks if the tree is empty
763         bool empty() const
764         {
765             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
766         }
767
768         /// Clears the tree (thread safe, not atomic)
769         /**
770             The function unlink all items from the tree.
771             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
772             this sequence
773             \code
774             tree.clear();
775             assert( tree.empty() );
776             \endcode
777             the assertion could be raised.
778
779             For each leaf the \p disposer will be called after unlinking.
780         */
781         void clear()
782         {
783             guarded_ptr gp;
784             do {
785                 gp = extract_min();
786             }  while ( gp );
787         }
788
789         /// Clears the tree (not thread safe)
790         /**
791             This function is not thread safe and may be called only when no other thread deals with the tree.
792             The function is used in the tree destructor.
793         */
794         void unsafe_clear()
795         {
796             while ( true ) {
797                 internal_node * pParent = nullptr;
798                 internal_node * pGrandParent = nullptr;
799                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
800
801                 // Get leftmost leaf
802                 while ( pLeaf->is_internal() ) {
803                     pGrandParent = pParent;
804                     pParent = static_cast<internal_node *>( pLeaf );
805                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
806                 }
807
808                 if ( pLeaf->infinite_key()) {
809                     // The tree is empty
810                     return;
811                 }
812
813                 // Remove leftmost leaf and its parent node
814                 assert( pGrandParent );
815                 assert( pParent );
816                 assert( pLeaf->is_leaf() );
817
818                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
819                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
820                 free_internal_node( pParent );
821             }
822         }
823
824         /// Returns item count in the tree
825         /**
826             Only leaf nodes containing user data are counted.
827
828             The value returned depends on item counter type provided by \p Traits template parameter.
829             If it is \p atomicity::empty_item_counter this function always returns 0.
830             The function is not suitable for checking the tree emptiness, use \p empty()
831             member function for this purpose.
832         */
833         size_t size() const
834         {
835             return m_ItemCounter;
836         }
837
838         /// Returns const reference to internal statistics
839         stat const& statistics() const
840         {
841             return m_Stat;
842         }
843
844         /// Checks internal consistency (not atomic, not thread-safe)
845         /**
846             The debugging function to check internal consistency of the tree.
847         */
848         bool check_consistency() const
849         {
850             return check_consistency( &m_Root );
851         }
852
853     protected:
854         //@cond
855
856         bool check_consistency( internal_node const * pRoot ) const
857         {
858             tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
859             tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
860             assert( pLeft );
861             assert( pRight );
862
863             if ( node_compare()( *pLeft, *pRoot ) < 0
864                 && node_compare()( *pRoot, *pRight ) <= 0
865                 && node_compare()( *pLeft, *pRight ) < 0 )
866             {
867                 bool bRet = true;
868                 if ( pLeft->is_internal() )
869                     bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
870                 assert( bRet );
871
872                 if ( bRet && pRight->is_internal() )
873                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
874                 assert( bRet );
875
876                 return bRet;
877             }
878             return false;
879         }
880
881         tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
882         {
883             tree_node * p;
884             tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
885             do {
886                 p = pn;
887                 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
888                 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
889                 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
890             } while ( p != pn );
891
892             // child node is guarded
893             // See whether pParent->m_pUpdate has not been changed
894             if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
895                 // update has been changed - returns nullptr as a flag to search retry
896                 return nullptr;
897             }
898
899             if ( p && p->is_leaf() )
900                 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
901             res.guards.clear( search_result::Guard_helpLeaf );
902             return p;
903         }
904
905         update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src ) const
906         {
907             update_ptr ret;
908             update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
909             do {
910                 ret = upd;
911                 res.guards.assign( search_result::Guard_updParent, upd );
912             } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
913             return ret;
914         }
915
916         template <typename KeyValue, typename Compare>
917         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
918         {
919             internal_node * pParent;
920             internal_node * pGrandParent = nullptr;
921             update_ptr      updParent;
922             update_ptr      updGrandParent;
923             bool bRightLeaf;
924             bool bRightParent = false;
925
926             int nCmp = 0;
927
928         retry:
929             pParent = nullptr;
930             //pGrandParent = nullptr;
931             updParent = nullptr;
932             bRightLeaf = false;
933             tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
934             while ( pLeaf->is_internal() ) {
935                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
936                 pGrandParent = pParent;
937                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
938                 pParent = static_cast<internal_node *>( pLeaf );
939                 bRightParent = bRightLeaf;
940                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
941                 updGrandParent = updParent;
942
943                 updParent = search_protect_update( res, pParent->m_pUpdate );
944
945                 switch ( updParent.bits() ) {
946                     case update_desc::DFlag:
947                     case update_desc::Mark:
948                         m_Stat.onSearchRetry();
949                         goto retry;
950                 }
951
952                 nCmp = cmp( key, *pParent );
953                 bRightLeaf = nCmp >= 0;
954
955                 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
956                 if ( !pLeaf ) {
957                     m_Stat.onSearchRetry();
958                     goto retry;
959                 }
960             }
961
962             assert( pLeaf->is_leaf() );
963             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
964
965             res.pGrandParent    = pGrandParent;
966             res.pParent         = pParent;
967             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
968             res.updParent       = updParent;
969             res.updGrandParent  = updGrandParent;
970             res.bRightParent    = bRightParent;
971             res.bRightLeaf      = bRightLeaf;
972
973             return nCmp == 0;
974         }
975
976         bool search_min( search_result& res ) const
977         {
978             internal_node * pParent;
979             internal_node * pGrandParent;
980             update_ptr      updParent;
981             update_ptr      updGrandParent;
982
983         retry:
984             pParent = nullptr;
985             pGrandParent = nullptr;
986             updParent = nullptr;
987             tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
988             while ( pLeaf->is_internal() ) {
989                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
990                 pGrandParent = pParent;
991                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
992                 pParent = static_cast<internal_node *>( pLeaf );
993                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
994                 updGrandParent = updParent;
995
996                 updParent = search_protect_update( res, pParent->m_pUpdate );
997
998                 switch ( updParent.bits() ) {
999                     case update_desc::DFlag:
1000                     case update_desc::Mark:
1001                         m_Stat.onSearchRetry();
1002                         goto retry;
1003                 }
1004
1005                 pLeaf = protect_child_node( res, pParent, false, updParent );
1006                 if ( !pLeaf ) {
1007                     m_Stat.onSearchRetry();
1008                     goto retry;
1009                 }
1010             }
1011
1012             if ( pLeaf->infinite_key())
1013                 return false;
1014
1015             res.pGrandParent    = pGrandParent;
1016             res.pParent         = pParent;
1017             assert( pLeaf->is_leaf() );
1018             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1019             res.updParent       = updParent;
1020             res.updGrandParent  = updGrandParent;
1021             res.bRightParent    = false;
1022             res.bRightLeaf      = false;
1023
1024             return true;
1025         }
1026
1027         bool search_max( search_result& res ) const
1028         {
1029             internal_node * pParent;
1030             internal_node * pGrandParent;
1031             update_ptr      updParent;
1032             update_ptr      updGrandParent;
1033             bool bRightLeaf;
1034             bool bRightParent = false;
1035
1036         retry:
1037             pParent = nullptr;
1038             pGrandParent = nullptr;
1039             updParent = nullptr;
1040             bRightLeaf = false;
1041             tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1042             while ( pLeaf->is_internal() ) {
1043                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1044                 pGrandParent = pParent;
1045                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1046                 pParent = static_cast<internal_node *>( pLeaf );
1047                 bRightParent = bRightLeaf;
1048                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1049                 updGrandParent = updParent;
1050
1051                 updParent = search_protect_update( res, pParent->m_pUpdate );
1052
1053                 switch ( updParent.bits() ) {
1054                     case update_desc::DFlag:
1055                     case update_desc::Mark:
1056                         m_Stat.onSearchRetry();
1057                         goto retry;
1058                 }
1059
1060                 bRightLeaf = !pParent->infinite_key();
1061                 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1062                 if ( !pLeaf ) {
1063                     m_Stat.onSearchRetry();
1064                     goto retry;
1065                 }
1066             }
1067
1068             if ( pLeaf->infinite_key())
1069                 return false;
1070
1071             res.pGrandParent    = pGrandParent;
1072             res.pParent         = pParent;
1073             assert( pLeaf->is_leaf() );
1074             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1075             res.updParent       = updParent;
1076             res.updGrandParent  = updGrandParent;
1077             res.bRightParent    = bRightParent;
1078             res.bRightLeaf      = bRightLeaf;
1079
1080             return true;
1081         }
1082
1083         /*
1084         void help( update_ptr pUpdate )
1085         {
1086             // pUpdate must be guarded!
1087             switch ( pUpdate.bits() ) {
1088                 case update_desc::IFlag:
1089                     help_insert( pUpdate.ptr() );
1090                     m_Stat.onHelpInsert();
1091                     break;
1092                 case update_desc::DFlag:
1093                     help_delete( pUpdate.ptr() );
1094                     m_Stat.onHelpDelete();
1095                     break;
1096                 case update_desc::Mark:
1097                     //m_Stat.onHelpMark();
1098                     //help_marked( pUpdate.ptr() );
1099                     break;
1100             }
1101         }
1102         */
1103
1104         void help_insert( update_desc * pOp )
1105         {
1106             // pOp must be guarded
1107
1108             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1109             if ( pOp->iInfo.bRightLeaf ) {
1110                 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1111                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1112             }
1113             else {
1114                 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1115                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1116             }
1117
1118             // Unflag parent
1119             update_ptr cur( pOp, update_desc::IFlag );
1120             CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1121                 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1122         }
1123
1124         bool check_delete_precondition( search_result& res ) const
1125         {
1126             // precondition: all member of res must be guarded
1127
1128             assert( res.pGrandParent != nullptr );
1129
1130             return
1131                 static_cast<internal_node *>(
1132                     res.bRightParent
1133                         ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1134                         : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1135                     ) == res.pParent
1136                 &&
1137                 static_cast<leaf_node *>(
1138                     res.bRightLeaf
1139                         ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1140                         : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1141                 ) == res.pLeaf;
1142         }
1143
1144         bool help_delete( update_desc * pOp )
1145         {
1146             // precondition: pOp must be guarded
1147
1148             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1149             update_ptr pMark( pOp, update_desc::Mark );
1150             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1151                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1152             {
1153                 help_marked( pOp );
1154
1155                 retire_node( pOp->dInfo.pParent );
1156                 retire_node( pOp->dInfo.pLeaf );
1157                 retire_update_desc( pOp );
1158                 return true;
1159             }
1160             else if ( pUpdate == pMark ) {
1161                 // some other thread is processing help_marked()
1162                 help_marked( pOp );
1163                 m_Stat.onHelpMark();
1164                 return true;
1165             }
1166             else {
1167                 // Undo grandparent dInfo
1168                 update_ptr pDel( pOp, update_desc::DFlag );
1169                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1170                     memory_model::memory_order_release, atomics::memory_order_relaxed ))
1171                 {
1172                     retire_update_desc( pOp );
1173                 }
1174                 return false;
1175             }
1176         }
1177
1178         tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1179         {
1180             typename gc::Guard guardLeaf;
1181
1182             tree_node * pSibling;
1183             tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1184             do {
1185                 pSibling = p;
1186                 guard.assign( static_cast<internal_node *>(p) );
1187                 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1188             } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1189
1190             if ( pSibling->is_leaf() )
1191                 guard.copy( guardLeaf );
1192
1193             return pSibling;
1194         }
1195
1196         void help_marked( update_desc * pOp )
1197         {
1198             // precondition: pOp must be guarded
1199
1200             tree_node * pParent = pOp->dInfo.pParent;
1201
1202             typename gc::Guard guard;
1203             tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1204
1205             if ( pOp->dInfo.bRightParent ) {
1206                 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1207                     memory_model::memory_order_release, atomics::memory_order_relaxed ));
1208             }
1209             else {
1210                 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1211                     memory_model::memory_order_release, atomics::memory_order_relaxed ));
1212             }
1213
1214             update_ptr upd( pOp, update_desc::DFlag );
1215             CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1216                 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1217         }
1218
1219         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1220         {
1221             assert( res.updParent.bits() == update_desc::Clean );
1222             assert( res.pLeaf->is_leaf() );
1223
1224             // check search result
1225             if ( (res.bRightLeaf
1226                 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1227                 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire )) == res.pLeaf ) {
1228                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1229
1230                 int nCmp = node_compare()(val, *res.pLeaf);
1231                 if ( nCmp < 0 ) {
1232                     if ( res.pGrandParent ) {
1233                         assert( !res.pLeaf->infinite_key() );
1234                         pNewInternal->infinite_key( 0 );
1235                         key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1236                     }
1237                     else {
1238                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1239                         pNewInternal->infinite_key( 1 );
1240                     }
1241                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1242                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1243                 }
1244                 else {
1245                     assert( !res.pLeaf->is_internal() );
1246                     pNewInternal->infinite_key( 0 );
1247
1248                     key_extractor()(pNewInternal->m_Key, val);
1249                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1250                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1251                     assert( !res.pLeaf->infinite_key() );
1252                 }
1253
1254                 typename gc::Guard guard;
1255                 update_desc * pOp = alloc_update_desc();
1256                 guard.assign( pOp );
1257
1258                 pOp->iInfo.pParent = res.pParent;
1259                 pOp->iInfo.pNew = pNewInternal;
1260                 pOp->iInfo.pLeaf = res.pLeaf;
1261                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1262
1263                 update_ptr updCur( res.updParent.ptr() );
1264                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1265                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1266                     // do insert
1267                     help_insert( pOp );
1268                     retire_update_desc( pOp );
1269                     return true;
1270                 }
1271                 else {
1272                     m_Stat.onUpdateDescDeleted();
1273                     free_update_desc( pOp );
1274                 }
1275             }
1276
1277             return false;
1278         }
1279
1280         template <typename Q, typename Compare, typename Equal, typename Func>
1281         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1282         {
1283             update_desc * pOp = nullptr;
1284             search_result res;
1285             back_off bkoff;
1286
1287             for ( ;; ) {
1288                 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1289                     if ( pOp )
1290                         retire_update_desc( pOp );
1291                     m_Stat.onEraseFailed();
1292                     return false;
1293                 }
1294
1295                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1296                     if ( !pOp )
1297                         pOp = alloc_update_desc();
1298                     if ( check_delete_precondition( res ) ) {
1299                         typename gc::Guard guard;
1300                         guard.assign( pOp );
1301
1302                         pOp->dInfo.pGrandParent = res.pGrandParent;
1303                         pOp->dInfo.pParent = res.pParent;
1304                         pOp->dInfo.pLeaf = res.pLeaf;
1305                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1306                         pOp->dInfo.bRightParent = res.bRightParent;
1307                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1308
1309                         update_ptr updGP( res.updGrandParent.ptr() );
1310                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1311                             memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1312                             if ( help_delete( pOp ) ) {
1313                                 // res.pLeaf is not deleted yet since it is guarded
1314                                 f( *node_traits::to_value_ptr( res.pLeaf ) );
1315                                 break;
1316                             }
1317                             pOp = nullptr;
1318                         }
1319                     }
1320                 }
1321
1322                 bkoff();
1323                 m_Stat.onEraseRetry();
1324             }
1325
1326             --m_ItemCounter;
1327             m_Stat.onEraseSuccess();
1328             return true;
1329         }
1330
1331         template <typename Q>
1332         bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
1333         {
1334             return erase_( key, node_compare(),
1335                 []( Q const&, leaf_node const& ) -> bool { return true; },
1336                 [&guard]( value_type& found ) { guard.set( &found ); } );
1337         }
1338
1339         template <typename Q, typename Less>
1340         bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
1341         {
1342             CDS_UNUSED( pred );
1343             typedef ellen_bintree::details::compare<
1344                 key_type,
1345                 value_type,
1346                 opt::details::make_comparator_from_less<Less>,
1347                 node_traits
1348             > compare_functor;
1349
1350             return erase_( key, compare_functor(),
1351                 []( Q const&, leaf_node const& ) -> bool { return true; },
1352                 [&guard]( value_type& found ) { guard.set( &found ); } );
1353         }
1354
1355         bool extract_max_( typename guarded_ptr::native_guard& gp )
1356         {
1357             update_desc * pOp = nullptr;
1358             search_result res;
1359             back_off bkoff;
1360
1361             for ( ;; ) {
1362                 if ( !search_max( res )) {
1363                     // Tree is empty
1364                     if ( pOp )
1365                         retire_update_desc( pOp );
1366                     m_Stat.onExtractMaxFailed();
1367                     return false;
1368                 }
1369
1370                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1371                     if ( !pOp )
1372                         pOp = alloc_update_desc();
1373                     if ( check_delete_precondition( res ) ) {
1374                         typename gc::Guard guard;
1375                         guard.assign( pOp );
1376
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;
1383
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 ) ) 
1387                         {
1388                             if ( help_delete( pOp ) )
1389                                 break;
1390                             pOp = nullptr;
1391                         }
1392                     }
1393                 }
1394
1395                 bkoff();
1396                 m_Stat.onExtractMaxRetry();
1397             }
1398
1399             --m_ItemCounter;
1400             m_Stat.onExtractMaxSuccess();
1401             gp.set( node_traits::to_value_ptr( res.pLeaf ));
1402             return true;
1403         }
1404
1405         bool extract_min_( typename guarded_ptr::native_guard& gp )
1406         {
1407             update_desc * pOp = nullptr;
1408             search_result res;
1409             back_off bkoff;
1410
1411             for ( ;; ) {
1412                 if ( !search_min( res )) {
1413                     // Tree is empty
1414                     if ( pOp )
1415                         retire_update_desc( pOp );
1416                     m_Stat.onExtractMinFailed();
1417                     return false;
1418                 }
1419
1420                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1421                     if ( !pOp )
1422                         pOp = alloc_update_desc();
1423                     if ( check_delete_precondition( res ) ) {
1424                         typename gc::Guard guard;
1425                         guard.assign( pOp );
1426
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;
1433
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 ))
1437                         {
1438                             if ( help_delete( pOp ))
1439                                 break;
1440                             pOp = nullptr;
1441                         }
1442                     }
1443                 }
1444
1445                 bkoff();
1446                 m_Stat.onExtractMinRetry();
1447             }
1448
1449             --m_ItemCounter;
1450             m_Stat.onExtractMinSuccess();
1451             gp.set( node_traits::to_value_ptr( res.pLeaf ));
1452             return true;
1453         }
1454
1455         template <typename Q, typename Func>
1456         bool find_( Q& val, Func f ) const
1457         {
1458             search_result    res;
1459             if ( search( res, val, node_compare() )) {
1460                 assert( res.pLeaf );
1461                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1462
1463                 m_Stat.onFindSuccess();
1464                 return true;
1465             }
1466
1467             m_Stat.onFindFailed();
1468             return false;
1469         }
1470
1471         template <typename Q, typename Less, typename Func>
1472         bool find_with_( Q& val, Less /*pred*/, Func f ) const
1473         {
1474             CDS_UNUSED( pred );
1475             typedef ellen_bintree::details::compare<
1476                 key_type,
1477                 value_type,
1478                 opt::details::make_comparator_from_less<Less>,
1479                 node_traits
1480             > compare_functor;
1481
1482             search_result    res;
1483             if ( search( res, val, compare_functor() )) {
1484                 assert( res.pLeaf );
1485                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1486
1487                 m_Stat.onFindSuccess();
1488                 return true;
1489             }
1490
1491             m_Stat.onFindFailed();
1492             return false;
1493         }
1494
1495         template <typename Q>
1496         bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
1497         {
1498             return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1499         }
1500
1501         template <typename Q, typename Less>
1502         bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
1503         {
1504             return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1505         }
1506
1507         //@endcond
1508     };
1509
1510 }} // namespace cds::intrusive
1511
1512 #endif // #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H