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