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