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