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