cds/intrusive/impl/ellen_bintree.h

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