cds/intrusive/impl/ellen_bintree.h

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