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