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