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