cds/intrusive/impl/ellen_bintree.h

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