cds/intrusive/impl/ellen_bintree.h

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