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-2016
   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 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( value_type * p )
 247         {
 248             disposer()( 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( internal_node * pNode )
 259         {
 260             cxx_node_allocator().Delete( 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( update_desc * pDesc )
 279         {
 280             cxx_update_desc_allocator().Delete( 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 successfull,
 419             i.e. the node has been inserted or updated,
 420             \p second is \p true if new item has been added or \p false if the item with \p key
 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.onEnsureExist();
 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.onEnsureRetry();
 460             }
 461
 462             ++m_ItemCounter;
 463             m_Stat.onEnsureNew();
 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             guarded_ptr gp;
 605             extract_min_( gp.guard() );
 606             return gp;
 607         }
 608
 609         /// Extracts an item with maximal key from the tree
 610         /**
 611             The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
 612             If the tree is empty the function returns an empty \p guarded_ptr.
 613
 614             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
 615             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 616             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
 617             So, the function returns the item with maximal key at the moment of tree traversing.
 618
 619             The returned \p guarded_ptr prevents disposer invocation for returned item,
 620             see cds::gc::guarded_ptr for explanation.
 621             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 622         */
 623         guarded_ptr extract_max()
 624         {
 625             guarded_ptr gp;
 626             extract_max_( gp.guard());
 627             return gp;
 628         }
 629
 630         /// Extracts an item from the tree
 631         /** \anchor cds_intrusive_EllenBinTree_extract
 632             The function searches an item with key equal to \p key in the tree,
 633             unlinks it, and returns a guarded pointer to an item found.
 634             If the item  is not found the function returns an empty \p guarded_ptr.
 635
 636             \p guarded_ptr prevents disposer invocation for returned item,
 637             see cds::gc::guarded_ptr for explanation.
 638             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 639         */
 640         template <typename Q>
 641         guarded_ptr extract( Q const& key )
 642         {
 643             guarded_ptr gp;
 644             extract_( gp.guard(), key );
 645             return gp;
 646         }
 647
 648         /// Extracts an item from the tree using \p pred for searching
 649         /**
 650             The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
 651             but \p pred is used for key compare.
 652             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 653             "Predicate requirements".
 654             \p pred must imply the same element order as the comparator used for building the tree.
 655         */
 656         template <typename Q, typename Less>
 657         guarded_ptr extract_with( Q const& key, Less pred )
 658         {
 659             guarded_ptr gp;
 660             extract_with_( gp.guard(), key, pred );
 661             return gp;
 662         }
 663
 664         /// Checks whether the set contains \p key
 665         /**
 666             The function searches the item with key equal to \p key
 667             and returns \p true if it is found, and \p false otherwise.
 668         */
 669         template <typename Q>
 670         bool contains( Q const& key ) const
 671         {
 672             search_result    res;
 673             if ( search( res, key, node_compare() )) {
 674                 m_Stat.onFindSuccess();
 675                 return true;
 676             }
 677
 678             m_Stat.onFindFailed();
 679             return false;
 680         }
 681         //@cond
 682         template <typename Q>
 683         CDS_DEPRECATED("deprecated, use contains()")
 684         bool find( Q const& key ) const
 685         {
 686             return contains( key );
 687         }
 688         //@endcond
 689
 690         /// Checks whether the set contains \p key using \p pred predicate for searching
 691         /**
 692             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 693             \p Less functor has the interface like \p std::less.
 694             \p Less must imply the same element order as the comparator used for building the set.
 695         */
 696         template <typename Q, typename Less>
 697         bool contains( Q const& key, Less pred ) const
 698         {
 699             CDS_UNUSED( pred );
 700             typedef ellen_bintree::details::compare<
 701                 key_type,
 702                 value_type,
 703                 opt::details::make_comparator_from_less<Less>,
 704                 node_traits
 705             > compare_functor;
 706
 707             search_result    res;
 708             if ( search( res, key, compare_functor() )) {
 709                 m_Stat.onFindSuccess();
 710                 return true;
 711             }
 712             m_Stat.onFindFailed();
 713             return false;
 714         }
 715         //@cond
 716         template <typename Q, typename Less>
 717         CDS_DEPRECATED("deprecated, use contains()")
 718         bool find_with( Q const& key, Less pred ) const
 719         {
 720             return contains( key, pred );
 721         }
 722         //@endcond
 723
 724         /// Finds the key \p key
 725         /** @anchor cds_intrusive_EllenBinTree_find_func
 726             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 727             The interface of \p Func functor is:
 728             \code
 729             struct functor {
 730                 void operator()( value_type& item, Q& key );
 731             };
 732             \endcode
 733             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 734
 735             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 736             that \p item cannot be disposed during functor is executing.
 737             The functor does not serialize simultaneous access to the tree \p item. If such access is
 738             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 739
 740             The function returns \p true if \p key is found, \p false otherwise.
 741         */
 742         template <typename Q, typename Func>
 743         bool find( Q& key, Func f ) const
 744         {
 745             return find_( key, f );
 746         }
 747         //@cond
 748         template <typename Q, typename Func>
 749         bool find( Q const& key, Func f ) const
 750         {
 751             return find_( key, f );
 752         }
 753         //@endcond
 754
 755         /// Finds the key \p key with comparing functor \p pred
 756         /**
 757             The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
 758             but \p pred is used for key comparison.
 759             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 760             "Predicate requirements".
 761             \p pred must imply the same element order as the comparator used for building the tree.
 762         */
 763         template <typename Q, typename Less, typename Func>
 764         bool find_with( Q& key, Less pred, Func f ) const
 765         {
 766             return find_with_( key, pred, f );
 767         }
 768         //@cond
 769         template <typename Q, typename Less, typename Func>
 770         bool find_with( Q const& key, Less pred, Func f ) const
 771         {
 772             return find_with_( key, pred, f );
 773         }
 774         //@endcond
 775
 776         /// Finds \p key and returns the item found
 777         /** @anchor cds_intrusive_EllenBinTree_get
 778             The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
 779             The function returns an empty guarded pointer is \p key is not found.
 780
 781             \p guarded_ptr prevents disposer invocation for returned item,
 782             see \p cds::gc::guarded_ptr for explanation.
 783             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 784         */
 785         template <typename Q>
 786         guarded_ptr get( Q const& key ) const
 787         {
 788             guarded_ptr gp;
 789             get_( gp.guard(), key );
 790             return gp;
 791         }
 792
 793         /// Finds \p key with predicate \p pred and returns the item found
 794         /**
 795             The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
 796             but \p pred is used for key comparing.
 797             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 798             "Predicate requirements".
 799             \p pred must imply the same element order as the comparator used for building the tree.
 800         */
 801         template <typename Q, typename Less>
 802         guarded_ptr get_with( Q const& key, Less pred ) const
 803         {
 804             guarded_ptr gp;
 805             get_with_( gp.guard(), key, pred );
 806             return gp;
 807         }
 808
 809         /// Checks if the tree is empty
 810         bool empty() const
 811         {
 812             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
 813         }
 814
 815         /// Clears the tree (thread safe, not atomic)
 816         /**
 817             The function unlink all items from the tree.
 818             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 819             this sequence
 820             \code
 821             tree.clear();
 822             assert( tree.empty() );
 823             \endcode
 824             the assertion could be raised.
 825
 826             For each leaf the \p disposer will be called after unlinking.
 827         */
 828         void clear()
 829         {
 830             guarded_ptr gp;
 831             do {
 832                 gp = extract_min();
 833             }  while ( gp );
 834         }
 835
 836         /// Clears the tree (not thread safe)
 837         /**
 838             This function is not thread safe and may be called only when no other thread deals with the tree.
 839             The function is used in the tree destructor.
 840         */
 841         void unsafe_clear()
 842         {
 843             while ( true ) {
 844                 internal_node * pParent = nullptr;
 845                 internal_node * pGrandParent = nullptr;
 846                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
 847
 848                 // Get leftmost leaf
 849                 while ( pLeaf->is_internal() ) {
 850                     pGrandParent = pParent;
 851                     pParent = static_cast<internal_node *>( pLeaf );
 852                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
 853                 }
 854
 855                 if ( pLeaf->infinite_key()) {
 856                     // The tree is empty
 857                     return;
 858                 }
 859
 860                 // Remove leftmost leaf and its parent node
 861                 assert( pGrandParent );
 862                 assert( pParent );
 863                 assert( pLeaf->is_leaf() );
 864
 865                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
 866                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
 867                 free_internal_node( pParent );
 868             }
 869         }
 870
 871         /// Returns item count in the tree
 872         /**
 873             Only leaf nodes containing user data are counted.
 874
 875             The value returned depends on item counter type provided by \p Traits template parameter.
 876             If it is \p atomicity::empty_item_counter this function always returns 0.
 877             The function is not suitable for checking the tree emptiness, use \p empty()
 878             member function for this purpose.
 879         */
 880         size_t size() const
 881         {
 882             return m_ItemCounter;
 883         }
 884
 885         /// Returns const reference to internal statistics
 886         stat const& statistics() const
 887         {
 888             return m_Stat;
 889         }
 890
 891         /// Checks internal consistency (not atomic, not thread-safe)
 892         /**
 893             The debugging function to check internal consistency of the tree.
 894         */
 895         bool check_consistency() const
 896         {
 897             return check_consistency( &m_Root );
 898         }
 899
 900     protected:
 901         //@cond
 902
 903         bool check_consistency( internal_node const * pRoot ) const
 904         {
 905             tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
 906             tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
 907             assert( pLeft );
 908             assert( pRight );
 909
 910             if ( node_compare()( *pLeft, *pRoot ) < 0
 911                 && node_compare()( *pRoot, *pRight ) <= 0
 912                 && node_compare()( *pLeft, *pRight ) < 0 )
 913             {
 914                 bool bRet = true;
 915                 if ( pLeft->is_internal() )
 916                     bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
 917                 assert( bRet );
 918
 919                 if ( bRet && pRight->is_internal() )
 920                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
 921                 assert( bRet );
 922
 923                 return bRet;
 924             }
 925             return false;
 926         }
 927
 928         tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
 929         {
 930         retry:
 931             tree_node * p = bRight
 932                 ? res.guards.protect( search_result::Guard_Leaf, pParent->m_pRight,
 933                     []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);})
 934                 : res.guards.protect( search_result::Guard_Leaf, pParent->m_pLeft,
 935                     []( tree_node * p ) -> internal_node* { return static_cast<internal_node *>(p);});
 936
 937             // If we use member hook, data node pointer != internal node pointer
 938             // So, we need protect the child twice: as internal node and as data node
 939             // and then analyze what kind of node we have
 940             tree_node * pVal = bRight
 941                 ? res.guards.protect( search_result::Guard_temporary, pParent->m_pRight,
 942                     []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} )
 943                 : res.guards.protect( search_result::Guard_temporary, pParent->m_pLeft,
 944                     []( tree_node * p ) -> value_type* { return node_traits::to_value_ptr( static_cast<leaf_node *>(p));} );
 945
 946             // child node is guarded
 947             // See whether pParent->m_pUpdate has not been changed
 948             if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
 949                 // update has been changed - returns nullptr as a flag to search retry
 950                 return nullptr;
 951             }
 952
 953             if ( p != pVal )
 954                 goto retry;
 955
 956             if ( p && p->is_leaf())
 957                 res.guards.assign( search_result::Guard_Leaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p )));
 958
 959             res.guards.clear( search_result::Guard_temporary );
 960
 961             return p;
 962         }
 963
 964         static update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src )
 965         {
 966             return res.guards.protect( search_result::Guard_updParent, src, [](update_ptr p) -> update_desc* { return p.ptr(); });
 967         }
 968
 969         template <typename KeyValue, typename Compare>
 970         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
 971         {
 972             internal_node * pParent;
 973             internal_node * pGrandParent = nullptr;
 974             update_ptr      updParent;
 975             update_ptr      updGrandParent;
 976             bool bRightLeaf;
 977             bool bRightParent = false;
 978
 979             int nCmp = 0;
 980
 981         retry:
 982             pParent = nullptr;
 983             //pGrandParent = nullptr;
 984             updParent = nullptr;
 985             bRightLeaf = false;
 986             tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
 987             while ( pLeaf->is_internal() ) {
 988                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
 989                 pGrandParent = pParent;
 990                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
 991                 pParent = static_cast<internal_node *>( pLeaf );
 992                 bRightParent = bRightLeaf;
 993                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
 994                 updGrandParent = updParent;
 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                 nCmp = cmp( key, *pParent );
1006                 bRightLeaf = nCmp >= 0;
1007
1008                 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1009                 if ( !pLeaf ) {
1010                     m_Stat.onSearchRetry();
1011                     goto retry;
1012                 }
1013             }
1014
1015             assert( pLeaf->is_leaf() );
1016             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1017
1018             res.pGrandParent    = pGrandParent;
1019             res.pParent         = pParent;
1020             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1021             res.updParent       = updParent;
1022             res.updGrandParent  = updGrandParent;
1023             res.bRightParent    = bRightParent;
1024             res.bRightLeaf      = bRightLeaf;
1025
1026             return nCmp == 0;
1027         }
1028
1029         bool search_min( search_result& res ) const
1030         {
1031             internal_node * pParent;
1032             internal_node * pGrandParent;
1033             update_ptr      updParent;
1034             update_ptr      updGrandParent;
1035
1036         retry:
1037             pParent = nullptr;
1038             pGrandParent = nullptr;
1039             updParent = nullptr;
1040             tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
1041             while ( pLeaf->is_internal() ) {
1042                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1043                 pGrandParent = pParent;
1044                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1045                 pParent = static_cast<internal_node *>( pLeaf );
1046                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1047                 updGrandParent = updParent;
1048
1049                 updParent = search_protect_update( res, pParent->m_pUpdate );
1050
1051                 switch ( updParent.bits() ) {
1052                     case update_desc::DFlag:
1053                     case update_desc::Mark:
1054                         m_Stat.onSearchRetry();
1055                         goto retry;
1056                 }
1057
1058                 pLeaf = protect_child_node( res, pParent, false, updParent );
1059                 if ( !pLeaf ) {
1060                     m_Stat.onSearchRetry();
1061                     goto retry;
1062                 }
1063             }
1064
1065             if ( pLeaf->infinite_key())
1066                 return false;
1067
1068             res.pGrandParent    = pGrandParent;
1069             res.pParent         = pParent;
1070             assert( pLeaf->is_leaf() );
1071             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1072             res.updParent       = updParent;
1073             res.updGrandParent  = updGrandParent;
1074             res.bRightParent    = false;
1075             res.bRightLeaf      = false;
1076
1077             return true;
1078         }
1079
1080         bool search_max( search_result& res ) const
1081         {
1082             internal_node * pParent;
1083             internal_node * pGrandParent;
1084             update_ptr      updParent;
1085             update_ptr      updGrandParent;
1086             bool bRightLeaf;
1087             bool bRightParent = false;
1088
1089         retry:
1090             pParent = nullptr;
1091             pGrandParent = nullptr;
1092             updParent = nullptr;
1093             bRightLeaf = false;
1094             tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1095             while ( pLeaf->is_internal() ) {
1096                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1097                 pGrandParent = pParent;
1098                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1099                 pParent = static_cast<internal_node *>( pLeaf );
1100                 bRightParent = bRightLeaf;
1101                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1102                 updGrandParent = updParent;
1103
1104                 updParent = search_protect_update( res, pParent->m_pUpdate );
1105
1106                 switch ( updParent.bits() ) {
1107                     case update_desc::DFlag:
1108                     case update_desc::Mark:
1109                         m_Stat.onSearchRetry();
1110                         goto retry;
1111                 }
1112
1113                 bRightLeaf = !pParent->infinite_key();
1114                 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1115                 if ( !pLeaf ) {
1116                     m_Stat.onSearchRetry();
1117                     goto retry;
1118                 }
1119             }
1120
1121             if ( pLeaf->infinite_key())
1122                 return false;
1123
1124             res.pGrandParent    = pGrandParent;
1125             res.pParent         = pParent;
1126             assert( pLeaf->is_leaf() );
1127             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1128             res.updParent       = updParent;
1129             res.updGrandParent  = updGrandParent;
1130             res.bRightParent    = bRightParent;
1131             res.bRightLeaf      = bRightLeaf;
1132
1133             return true;
1134         }
1135
1136         /*
1137         void help( update_ptr pUpdate )
1138         {
1139             // pUpdate must be guarded!
1140             switch ( pUpdate.bits() ) {
1141                 case update_desc::IFlag:
1142                     help_insert( pUpdate.ptr() );
1143                     m_Stat.onHelpInsert();
1144                     break;
1145                 case update_desc::DFlag:
1146                     help_delete( pUpdate.ptr() );
1147                     m_Stat.onHelpDelete();
1148                     break;
1149                 case update_desc::Mark:
1150                     //m_Stat.onHelpMark();
1151                     //help_marked( pUpdate.ptr() );
1152                     break;
1153             }
1154         }
1155         */
1156
1157         void help_insert( update_desc * pOp )
1158         {
1159             // pOp must be guarded
1160
1161             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1162             if ( pOp->iInfo.bRightLeaf ) {
1163                 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1164                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1165             }
1166             else {
1167                 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1168                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1169             }
1170
1171             // Unflag parent
1172             update_ptr cur( pOp, update_desc::IFlag );
1173             CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1174                 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1175         }
1176
1177         bool check_delete_precondition( search_result& res ) const
1178         {
1179             // precondition: all member of res must be guarded
1180
1181             assert( res.pGrandParent != nullptr );
1182
1183             return static_cast<internal_node *>(res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1184                 && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1185         }
1186
1187         bool help_delete( update_desc * pOp )
1188         {
1189             // precondition: pOp must be guarded
1190
1191             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1192             update_ptr pMark( pOp, update_desc::Mark );
1193             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1194                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1195             {
1196                 help_marked( pOp );
1197
1198                 retire_node( pOp->dInfo.pParent );
1199                 retire_node( pOp->dInfo.pLeaf );
1200                 retire_update_desc( pOp );
1201                 return true;
1202             }
1203             else if ( pUpdate == pMark ) {
1204                 // some other thread is processing help_marked()
1205                 help_marked( pOp );
1206                 m_Stat.onHelpMark();
1207                 return true;
1208             }
1209             else {
1210                 // Undo grandparent dInfo
1211                 update_ptr pDel( pOp, update_desc::DFlag );
1212                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1213                     memory_model::memory_order_release, atomics::memory_order_relaxed ))
1214                 {
1215                     retire_update_desc( pOp );
1216                 }
1217                 return false;
1218             }
1219         }
1220
1221         static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1222         {
1223             tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
1224             if ( pSibling->is_leaf() )
1225                 guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
1226             return pSibling;
1227         }
1228
1229         void help_marked( update_desc * pOp )
1230         {
1231             // precondition: pOp must be guarded
1232
1233             tree_node * pParent = pOp->dInfo.pParent;
1234
1235             typename gc::Guard guard;
1236             tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1237
1238             if ( pOp->dInfo.bRightParent ) {
1239                 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1240                     memory_model::memory_order_release, atomics::memory_order_relaxed ));
1241             }
1242             else {
1243                 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1244                     memory_model::memory_order_release, atomics::memory_order_relaxed ));
1245             }
1246
1247             update_ptr upd( pOp, update_desc::DFlag );
1248             CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1249                 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1250         }
1251
1252         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1253         {
1254             assert( res.updParent.bits() == update_desc::Clean );
1255             assert( res.pLeaf->is_leaf() );
1256
1257             // check search result
1258             if ( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_acquire ) == res.pLeaf ) {
1259                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1260
1261                 int nCmp = node_compare()(val, *res.pLeaf);
1262                 if ( nCmp < 0 ) {
1263                     if ( res.pGrandParent ) {
1264                         assert( !res.pLeaf->infinite_key() );
1265                         pNewInternal->infinite_key( 0 );
1266                         key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1267                     }
1268                     else {
1269                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1270                         pNewInternal->infinite_key( 1 );
1271                     }
1272                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1273                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1274                 }
1275                 else {
1276                     assert( !res.pLeaf->is_internal() );
1277
1278                     pNewInternal->infinite_key( 0 );
1279                     key_extractor()(pNewInternal->m_Key, val);
1280                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1281                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1282                     assert( !res.pLeaf->infinite_key() );
1283                 }
1284
1285                 typename gc::Guard guard;
1286                 update_desc * pOp = alloc_update_desc();
1287                 guard.assign( pOp );
1288
1289                 pOp->iInfo.pParent = res.pParent;
1290                 pOp->iInfo.pNew = pNewInternal;
1291                 pOp->iInfo.pLeaf = res.pLeaf;
1292                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1293
1294                 update_ptr updCur( res.updParent.ptr() );
1295                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1296                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1297                     // do insert
1298                     help_insert( pOp );
1299                     retire_update_desc( pOp );
1300                     return true;
1301                 }
1302                 else {
1303                     m_Stat.onUpdateDescDeleted();
1304                     free_update_desc( pOp );
1305                 }
1306             }
1307
1308             return false;
1309         }
1310
1311         template <typename Q, typename Compare, typename Equal, typename Func>
1312         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1313         {
1314             update_desc * pOp = nullptr;
1315             search_result res;
1316             back_off bkoff;
1317
1318             for ( ;; ) {
1319                 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1320                     if ( pOp )
1321                         retire_update_desc( pOp );
1322                     m_Stat.onEraseFailed();
1323                     return false;
1324                 }
1325
1326                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1327                     if ( !pOp )
1328                         pOp = alloc_update_desc();
1329                     if ( check_delete_precondition( res ) ) {
1330                         typename gc::Guard guard;
1331                         guard.assign( pOp );
1332
1333                         pOp->dInfo.pGrandParent = res.pGrandParent;
1334                         pOp->dInfo.pParent = res.pParent;
1335                         pOp->dInfo.pLeaf = res.pLeaf;
1336                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1337                         pOp->dInfo.bRightParent = res.bRightParent;
1338                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1339
1340                         update_ptr updGP( res.updGrandParent.ptr() );
1341                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1342                             memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1343                             if ( help_delete( pOp ) ) {
1344                                 // res.pLeaf is not deleted yet since it is guarded
1345                                 f( *node_traits::to_value_ptr( res.pLeaf ) );
1346                                 break;
1347                             }
1348                             pOp = nullptr;
1349                         }
1350                     }
1351                 }
1352
1353                 bkoff();
1354                 m_Stat.onEraseRetry();
1355             }
1356
1357             --m_ItemCounter;
1358             m_Stat.onEraseSuccess();
1359             return true;
1360         }
1361
1362         template <typename Q>
1363         bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
1364         {
1365             return erase_( key, node_compare(),
1366                 []( Q const&, leaf_node const& ) -> bool { return true; },
1367                 [&guard]( value_type& found ) { guard.set( &found ); } );
1368         }
1369
1370         template <typename Q, typename Less>
1371         bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
1372         {
1373             typedef ellen_bintree::details::compare<
1374                 key_type,
1375                 value_type,
1376                 opt::details::make_comparator_from_less<Less>,
1377                 node_traits
1378             > compare_functor;
1379
1380             return erase_( key, compare_functor(),
1381                 []( Q const&, leaf_node const& ) -> bool { return true; },
1382                 [&guard]( value_type& found ) { guard.set( &found ); } );
1383         }
1384
1385         bool extract_max_( typename guarded_ptr::native_guard& gp )
1386         {
1387             update_desc * pOp = nullptr;
1388             search_result res;
1389             back_off bkoff;
1390
1391             for ( ;; ) {
1392                 if ( !search_max( res )) {
1393                     // Tree is empty
1394                     if ( pOp )
1395                         retire_update_desc( pOp );
1396                     m_Stat.onExtractMaxFailed();
1397                     return false;
1398                 }
1399
1400                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1401                     if ( !pOp )
1402                         pOp = alloc_update_desc();
1403                     if ( check_delete_precondition( res ) ) {
1404                         typename gc::Guard guard;
1405                         guard.assign( pOp );
1406
1407                         pOp->dInfo.pGrandParent = res.pGrandParent;
1408                         pOp->dInfo.pParent = res.pParent;
1409                         pOp->dInfo.pLeaf = res.pLeaf;
1410                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1411                         pOp->dInfo.bRightParent = res.bRightParent;
1412                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1413
1414                         update_ptr updGP( res.updGrandParent.ptr() );
1415                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1416                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1417                         {
1418                             if ( help_delete( pOp ) )
1419                                 break;
1420                             pOp = nullptr;
1421                         }
1422                     }
1423                 }
1424
1425                 bkoff();
1426                 m_Stat.onExtractMaxRetry();
1427             }
1428
1429             --m_ItemCounter;
1430             m_Stat.onExtractMaxSuccess();
1431             gp.set( node_traits::to_value_ptr( res.pLeaf ));
1432             return true;
1433         }
1434
1435         bool extract_min_( typename guarded_ptr::native_guard& gp )
1436         {
1437             update_desc * pOp = nullptr;
1438             search_result res;
1439             back_off bkoff;
1440
1441             for ( ;; ) {
1442                 if ( !search_min( res )) {
1443                     // Tree is empty
1444                     if ( pOp )
1445                         retire_update_desc( pOp );
1446                     m_Stat.onExtractMinFailed();
1447                     return false;
1448                 }
1449
1450                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1451                     if ( !pOp )
1452                         pOp = alloc_update_desc();
1453                     if ( check_delete_precondition( res ) ) {
1454                         typename gc::Guard guard;
1455                         guard.assign( pOp );
1456
1457                         pOp->dInfo.pGrandParent = res.pGrandParent;
1458                         pOp->dInfo.pParent = res.pParent;
1459                         pOp->dInfo.pLeaf = res.pLeaf;
1460                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1461                         pOp->dInfo.bRightParent = res.bRightParent;
1462                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1463
1464                         update_ptr updGP( res.updGrandParent.ptr() );
1465                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1466                             memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1467                         {
1468                             if ( help_delete( pOp ))
1469                                 break;
1470                             pOp = nullptr;
1471                         }
1472                     }
1473                 }
1474
1475                 bkoff();
1476                 m_Stat.onExtractMinRetry();
1477             }
1478
1479             --m_ItemCounter;
1480             m_Stat.onExtractMinSuccess();
1481             gp.set( node_traits::to_value_ptr( res.pLeaf ));
1482             return true;
1483         }
1484
1485         template <typename Q, typename Func>
1486         bool find_( Q& val, Func f ) const
1487         {
1488             search_result    res;
1489             if ( search( res, val, node_compare() )) {
1490                 assert( res.pLeaf );
1491                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1492
1493                 m_Stat.onFindSuccess();
1494                 return true;
1495             }
1496
1497             m_Stat.onFindFailed();
1498             return false;
1499         }
1500
1501         template <typename Q, typename Less, typename Func>
1502         bool find_with_( Q& val, Less /*pred*/, Func f ) const
1503         {
1504             typedef ellen_bintree::details::compare<
1505                 key_type,
1506                 value_type,
1507                 opt::details::make_comparator_from_less<Less>,
1508                 node_traits
1509             > compare_functor;
1510
1511             search_result    res;
1512             if ( search( res, val, compare_functor() )) {
1513                 assert( res.pLeaf );
1514                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1515
1516                 m_Stat.onFindSuccess();
1517                 return true;
1518             }
1519
1520             m_Stat.onFindFailed();
1521             return false;
1522         }
1523
1524         template <typename Q>
1525         bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
1526         {
1527             return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1528         }
1529
1530         template <typename Q, typename Less>
1531         bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
1532         {
1533             return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
1534         }
1535
1536         //@endcond
1537     };
1538
1539 }} // namespace cds::intrusive
1540
1541 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ELLEN_BINTREE_H