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
 688         /// Finds the key \p key with comparing functor \p pred
 689         /**
 690             The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
 691             but \p pred is used for key comparison.
 692             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 693             "Predicate requirements".
 694             \p pred must imply the same element order as the comparator used for building the tree.
 695         */
 696         template <typename Q, typename Less, typename Func>
 697         bool find_with( Q& key, Less pred, Func f ) const
 698         {
 699             return find_with_( key, pred, f );
 700         }
 701
 702         /// Finds \p key and returns the item found
 703         /** @anchor cds_intrusive_EllenBinTree_get
 704             The function searches the item with key equal to \p key and returns the item found in \p dest parameter.
 705             The function returns \p true if \p key is found, \p false otherwise.
 706
 707             The guarded pointer \p dest prevents disposer invocation for returned item,
 708             see cds::gc::guarded_ptr for explanation.
 709             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 710         */
 711         template <typename Q>
 712         bool get( guarded_ptr& dest, Q const& key ) const
 713         {
 714             return get_( dest.guard(), key );
 715         }
 716
 717         /// Finds \p key with predicate \p pred and returns the item found
 718         /**
 719             The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(guarded_ptr&, Q const&)"
 720             but \p pred is used for key comparing.
 721             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 722             "Predicate requirements".
 723             \p pred must imply the same element order as the comparator used for building the tree.
 724         */
 725         template <typename Q, typename Less>
 726         bool get_with( guarded_ptr& dest, Q const& key, Less pred ) const
 727         {
 728             return get_with_( dest.guard(), key, pred );
 729         }
 730
 731         /// Checks if the tree is empty
 732         bool empty() const
 733         {
 734             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
 735         }
 736
 737         /// Clears the tree (thread safe, not atomic)
 738         /**
 739             The function unlink all items from the tree.
 740             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 741             this sequence
 742             \code
 743             tree.clear();
 744             assert( tree.empty() );
 745             \endcode
 746             the assertion could be raised.
 747
 748             For each leaf the \p disposer will be called after unlinking.
 749         */
 750         void clear()
 751         {
 752             guarded_ptr gp;
 753             while ( extract_min(gp));
 754         }
 755
 756         /// Clears the tree (not thread safe)
 757         /**
 758             This function is not thread safe and may be called only when no other thread deals with the tree.
 759             The function is used in the tree destructor.
 760         */
 761         void unsafe_clear()
 762         {
 763             while ( true ) {
 764                 internal_node * pParent = nullptr;
 765                 internal_node * pGrandParent = nullptr;
 766                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
 767
 768                 // Get leftmost leaf
 769                 while ( pLeaf->is_internal() ) {
 770                     pGrandParent = pParent;
 771                     pParent = static_cast<internal_node *>( pLeaf );
 772                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
 773                 }
 774
 775                 if ( pLeaf->infinite_key()) {
 776                     // The tree is empty
 777                     return;
 778                 }
 779
 780                 // Remove leftmost leaf and its parent node
 781                 assert( pGrandParent );
 782                 assert( pParent );
 783                 assert( pLeaf->is_leaf() );
 784
 785                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
 786                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
 787                 free_internal_node( pParent );
 788             }
 789         }
 790
 791         /// Returns item count in the tree
 792         /**
 793             Only leaf nodes containing user data are counted.
 794
 795             The value returned depends on item counter type provided by \p Traits template parameter.
 796             If it is \p atomicity::empty_item_counter this function always returns 0.
 797             The function is not suitable for checking the tree emptiness, use \p empty()
 798             member function for this purpose.
 799         */
 800         size_t size() const
 801         {
 802             return m_ItemCounter;
 803         }
 804
 805         /// Returns const reference to internal statistics
 806         stat const& statistics() const
 807         {
 808             return m_Stat;
 809         }
 810
 811         /// Checks internal consistency (not atomic, not thread-safe)
 812         /**
 813             The debugging function to check internal consistency of the tree.
 814         */
 815         bool check_consistency() const
 816         {
 817             return check_consistency( &m_Root );
 818         }
 819
 820     protected:
 821         //@cond
 822
 823         bool check_consistency( internal_node const * pRoot ) const
 824         {
 825             tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
 826             tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
 827             assert( pLeft );
 828             assert( pRight );
 829
 830             if ( node_compare()( *pLeft, *pRoot ) < 0
 831                 && node_compare()( *pRoot, *pRight ) <= 0
 832                 && node_compare()( *pLeft, *pRight ) < 0 )
 833             {
 834                 bool bRet = true;
 835                 if ( pLeft->is_internal() )
 836                     bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
 837                 assert( bRet );
 838
 839                 if ( bRet && pRight->is_internal() )
 840                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
 841                 assert( bRet );
 842
 843                 return bRet;
 844             }
 845             return false;
 846         }
 847
 848         tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
 849         {
 850             tree_node * p;
 851             tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
 852             do {
 853                 p = pn;
 854                 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
 855                 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
 856                 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
 857             } while ( p != pn );
 858
 859             // child node is guarded
 860             // See whether pParent->m_pUpdate has not been changed
 861             if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
 862                 // update has been changed - returns nullptr as a flag to search retry
 863                 return nullptr;
 864             }
 865
 866             if ( p && p->is_leaf() )
 867                 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
 868             res.guards.clear( search_result::Guard_helpLeaf );
 869             return p;
 870         }
 871
 872         update_ptr search_protect_update( search_result& res, atomics::atomic<update_ptr> const& src ) const
 873         {
 874             update_ptr ret;
 875             update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
 876             do {
 877                 ret = upd;
 878                 res.guards.assign( search_result::Guard_updParent, upd );
 879             } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
 880             return ret;
 881         }
 882
 883         template <typename KeyValue, typename Compare>
 884         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
 885         {
 886             internal_node * pParent;
 887             internal_node * pGrandParent = nullptr;
 888             update_ptr      updParent;
 889             update_ptr      updGrandParent;
 890             bool bRightLeaf;
 891             bool bRightParent = false;
 892
 893             int nCmp = 0;
 894
 895         retry:
 896             pParent = nullptr;
 897             //pGrandParent = nullptr;
 898             updParent = nullptr;
 899             bRightLeaf = false;
 900             tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
 901             while ( pLeaf->is_internal() ) {
 902                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
 903                 pGrandParent = pParent;
 904                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
 905                 pParent = static_cast<internal_node *>( pLeaf );
 906                 bRightParent = bRightLeaf;
 907                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
 908                 updGrandParent = updParent;
 909
 910                 updParent = search_protect_update( res, pParent->m_pUpdate );
 911
 912                 switch ( updParent.bits() ) {
 913                     case update_desc::DFlag:
 914                     case update_desc::Mark:
 915                         m_Stat.onSearchRetry();
 916                         goto retry;
 917                 }
 918
 919                 nCmp = cmp( key, *pParent );
 920                 bRightLeaf = nCmp >= 0;
 921
 922                 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
 923                 if ( !pLeaf ) {
 924                     m_Stat.onSearchRetry();
 925                     goto retry;
 926                 }
 927             }
 928
 929             assert( pLeaf->is_leaf() );
 930             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
 931
 932             res.pGrandParent    = pGrandParent;
 933             res.pParent         = pParent;
 934             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
 935             res.updParent       = updParent;
 936             res.updGrandParent  = updGrandParent;
 937             res.bRightParent    = bRightParent;
 938             res.bRightLeaf      = bRightLeaf;
 939
 940             return nCmp == 0;
 941         }
 942
 943         bool search_min( search_result& res ) const
 944         {
 945             internal_node * pParent;
 946             internal_node * pGrandParent;
 947             update_ptr      updParent;
 948             update_ptr      updGrandParent;
 949
 950         retry:
 951             pParent = nullptr;
 952             pGrandParent = nullptr;
 953             updParent = nullptr;
 954             tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
 955             while ( pLeaf->is_internal() ) {
 956                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
 957                 pGrandParent = pParent;
 958                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
 959                 pParent = static_cast<internal_node *>( pLeaf );
 960                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
 961                 updGrandParent = updParent;
 962
 963                 updParent = search_protect_update( res, pParent->m_pUpdate );
 964
 965                 switch ( updParent.bits() ) {
 966                     case update_desc::DFlag:
 967                     case update_desc::Mark:
 968                         m_Stat.onSearchRetry();
 969                         goto retry;
 970                 }
 971
 972                 pLeaf = protect_child_node( res, pParent, false, updParent );
 973                 if ( !pLeaf ) {
 974                     m_Stat.onSearchRetry();
 975                     goto retry;
 976                 }
 977             }
 978
 979             if ( pLeaf->infinite_key())
 980                 return false;
 981
 982             res.pGrandParent    = pGrandParent;
 983             res.pParent         = pParent;
 984             assert( pLeaf->is_leaf() );
 985             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
 986             res.updParent       = updParent;
 987             res.updGrandParent  = updGrandParent;
 988             res.bRightParent    = false;
 989             res.bRightLeaf      = false;
 990
 991             return true;
 992         }
 993
 994         bool search_max( search_result& res ) const
 995         {
 996             internal_node * pParent;
 997             internal_node * pGrandParent;
 998             update_ptr      updParent;
 999             update_ptr      updGrandParent;
1000             bool bRightLeaf;
1001             bool bRightParent = false;
1002
1003         retry:
1004             pParent = nullptr;
1005             pGrandParent = nullptr;
1006             updParent = nullptr;
1007             bRightLeaf = false;
1008             tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1009             while ( pLeaf->is_internal() ) {
1010                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1011                 pGrandParent = pParent;
1012                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1013                 pParent = static_cast<internal_node *>( pLeaf );
1014                 bRightParent = bRightLeaf;
1015                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1016                 updGrandParent = updParent;
1017
1018                 updParent = search_protect_update( res, pParent->m_pUpdate );
1019
1020                 switch ( updParent.bits() ) {
1021                     case update_desc::DFlag:
1022                     case update_desc::Mark:
1023                         m_Stat.onSearchRetry();
1024                         goto retry;
1025                 }
1026
1027                 bRightLeaf = !pParent->infinite_key();
1028                 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1029                 if ( !pLeaf ) {
1030                     m_Stat.onSearchRetry();
1031                     goto retry;
1032                 }
1033             }
1034
1035             if ( pLeaf->infinite_key())
1036                 return false;
1037
1038             res.pGrandParent    = pGrandParent;
1039             res.pParent         = pParent;
1040             assert( pLeaf->is_leaf() );
1041             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1042             res.updParent       = updParent;
1043             res.updGrandParent  = updGrandParent;
1044             res.bRightParent    = bRightParent;
1045             res.bRightLeaf      = bRightLeaf;
1046
1047             return true;
1048         }
1049
1050         void help( update_ptr pUpdate )
1051         {
1052             // pUpdate must be guarded!
1053             switch ( pUpdate.bits() ) {
1054                 case update_desc::IFlag:
1055                     help_insert( pUpdate.ptr() );
1056                     m_Stat.onHelpInsert();
1057                     break;
1058                 case update_desc::DFlag:
1059                     help_delete( pUpdate.ptr() );
1060                     m_Stat.onHelpDelete();
1061                     break;
1062                 case update_desc::Mark:
1063                     //m_Stat.onHelpMark();
1064                     //help_marked( pUpdate.ptr() );
1065                     break;
1066             }
1067         }
1068
1069         void help_insert( update_desc * pOp )
1070         {
1071             // pOp must be guarded
1072
1073             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1074             if ( pOp->iInfo.bRightLeaf ) {
1075                 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1076                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1077             }
1078             else {
1079                 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1080                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
1081             }
1082
1083             // Unflag parent
1084             update_ptr cur( pOp, update_desc::IFlag );
1085             CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1086                 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1087         }
1088
1089         bool check_delete_precondition( search_result& res ) const
1090         {
1091             // precondition: all member of res must be guarded
1092
1093             assert( res.pGrandParent != nullptr );
1094
1095             return
1096                 static_cast<internal_node *>(
1097                     res.bRightParent
1098                         ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1099                         : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1100                     ) == res.pParent
1101                 &&
1102                 static_cast<leaf_node *>(
1103                     res.bRightLeaf
1104                         ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1105                         : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1106                 ) == res.pLeaf;
1107         }
1108
1109         bool help_delete( update_desc * pOp )
1110         {
1111             // precondition: pOp must be guarded
1112
1113             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1114             update_ptr pMark( pOp, update_desc::Mark );
1115             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1116                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1117             {
1118                 help_marked( pOp );
1119
1120                 retire_node( pOp->dInfo.pParent );
1121                 retire_node( pOp->dInfo.pLeaf );
1122                 retire_update_desc( pOp );
1123                 return true;
1124             }
1125             else if ( pUpdate == pMark ) {
1126                 // some other thread is processing help_marked()
1127                 help_marked( pOp );
1128                 m_Stat.onHelpMark();
1129                 return true;
1130             }
1131             else {
1132                 // Undo grandparent dInfo
1133                 update_ptr pDel( pOp, update_desc::DFlag );
1134                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1135                     memory_model::memory_order_release, atomics::memory_order_relaxed ))
1136                 {
1137                     retire_update_desc( pOp );
1138                 }
1139                 return false;
1140             }
1141         }
1142
1143         tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
1144         {
1145             typename gc::Guard guardLeaf;
1146
1147             tree_node * pSibling;
1148             tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1149             do {
1150                 pSibling = p;
1151                 guard.assign( static_cast<internal_node *>(p) );
1152                 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1153             } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1154
1155             if ( pSibling->is_leaf() )
1156                 guard.copy( guardLeaf );
1157
1158             return pSibling;
1159         }
1160
1161         void help_marked( update_desc * pOp )
1162         {
1163             // precondition: pOp must be guarded
1164
1165             tree_node * pParent = pOp->dInfo.pParent;
1166
1167             typename gc::Guard guard;
1168             tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1169
1170             if ( pOp->dInfo.bRightParent ) {
1171                 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1172                     memory_model::memory_order_release, atomics::memory_order_relaxed ));
1173             }
1174             else {
1175                 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1176                     memory_model::memory_order_release, atomics::memory_order_relaxed ));
1177             }
1178
1179             update_ptr upd( pOp, update_desc::DFlag );
1180             CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1181                 memory_model::memory_order_release, atomics::memory_order_relaxed ));
1182         }
1183
1184         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1185         {
1186             assert( res.updParent.bits() == update_desc::Clean );
1187             assert( res.pLeaf->is_leaf() );
1188
1189             // check search result
1190             if ( ( res.bRightLeaf
1191                 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1192                 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire ) ) == res.pLeaf )
1193             {
1194                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1195
1196                 int nCmp = node_compare()( val, *res.pLeaf );
1197                 if ( nCmp < 0 ) {
1198                     if ( res.pGrandParent ) {
1199                         assert( !res.pLeaf->infinite_key() );
1200                         pNewInternal->infinite_key( 0 );
1201                         key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1202                     }
1203                     else {
1204                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1205                         pNewInternal->infinite_key( 1 );
1206                     }
1207                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1208                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1209                 }
1210                 else {
1211                     assert( !res.pLeaf->is_internal() );
1212                     pNewInternal->infinite_key( 0 );
1213
1214                     key_extractor()( pNewInternal->m_Key, val );
1215                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1216                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1217                     assert( !res.pLeaf->infinite_key());
1218                 }
1219
1220                 typename gc::Guard guard;
1221                 update_desc * pOp = alloc_update_desc();
1222                 guard.assign( pOp );
1223
1224                 pOp->iInfo.pParent = res.pParent;
1225                 pOp->iInfo.pNew = pNewInternal;
1226                 pOp->iInfo.pLeaf = res.pLeaf;
1227                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1228
1229                 update_ptr updCur( res.updParent.ptr() );
1230                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1231                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1232                 {
1233                     // do insert
1234                     help_insert( pOp );
1235                     retire_update_desc( pOp );
1236                     return true;
1237                 }
1238                 else {
1239                     m_Stat.onUpdateDescDeleted();
1240                     free_update_desc( pOp );
1241                 }
1242             }
1243             return false;
1244         }
1245
1246         template <typename Q, typename Compare, typename Equal, typename Func>
1247         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1248         {
1249             update_desc * pOp = nullptr;
1250             search_result res;
1251
1252             for ( ;; ) {
1253                 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1254                     if ( pOp )
1255                         retire_update_desc( pOp );
1256                     m_Stat.onEraseFailed();
1257                     return false;
1258                 }
1259
1260                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1261                     if ( !pOp )
1262                         pOp = alloc_update_desc();
1263                     if ( check_delete_precondition( res ) ) {
1264                         typename gc::Guard guard;
1265                         guard.assign( pOp );
1266
1267                         pOp->dInfo.pGrandParent = res.pGrandParent;
1268                         pOp->dInfo.pParent = res.pParent;
1269                         pOp->dInfo.pLeaf = res.pLeaf;
1270                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1271                         pOp->dInfo.bRightParent = res.bRightParent;
1272                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1273
1274                         update_ptr updGP( res.updGrandParent.ptr() );
1275                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1276                             memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1277                         {
1278                             if ( help_delete( pOp )) {
1279                                 // res.pLeaf is not deleted yet since it is guarded
1280                                 f( *node_traits::to_value_ptr( res.pLeaf ));
1281                                 break;
1282                             }
1283                             pOp = nullptr;
1284                         }
1285                     }
1286                 }
1287
1288                 m_Stat.onEraseRetry();
1289             }
1290
1291             --m_ItemCounter;
1292             m_Stat.onEraseSuccess();
1293             return true;
1294         }
1295
1296         template <typename Q>
1297         bool extract_( typename gc::Guard& guard, Q const& key )
1298         {
1299             return erase_( key, node_compare(),
1300                 []( Q const&, leaf_node const& ) -> bool { return true; },
1301                 [&guard]( value_type& found ) { guard.assign( &found ); } );
1302         }
1303
1304         template <typename Q, typename Less>
1305         bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
1306         {
1307             typedef ellen_bintree::details::compare<
1308                 key_type,
1309                 value_type,
1310                 opt::details::make_comparator_from_less<Less>,
1311                 node_traits
1312             > compare_functor;
1313
1314             return erase_( key, compare_functor(),
1315                 []( Q const&, leaf_node const& ) -> bool { return true; },
1316                 [&guard]( value_type& found ) { guard.assign( &found ); } );
1317         }
1318
1319         bool extract_max_( typename gc::Guard& guard )
1320         {
1321             update_desc * pOp = nullptr;
1322             search_result res;
1323
1324             for ( ;; ) {
1325                 if ( !search_max( res )) {
1326                     // Tree is empty
1327                     if ( pOp )
1328                         retire_update_desc( pOp );
1329                     m_Stat.onExtractMaxFailed();
1330                     return false;
1331                 }
1332
1333                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean )  {
1334                     if ( !pOp )
1335                         pOp = alloc_update_desc();
1336                     if ( check_delete_precondition( res ) ) {
1337                         typename gc::Guard guard;
1338                         guard.assign( pOp );
1339
1340                         pOp->dInfo.pGrandParent = res.pGrandParent;
1341                         pOp->dInfo.pParent = res.pParent;
1342                         pOp->dInfo.pLeaf = res.pLeaf;
1343                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1344                         pOp->dInfo.bRightParent = res.bRightParent;
1345                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1346
1347                         update_ptr updGP( res.updGrandParent.ptr() );
1348                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1349                             memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1350                         {
1351                             if ( help_delete( pOp ))
1352                                 break;
1353                             pOp = nullptr;
1354                         }
1355                     }
1356                 }
1357
1358                 m_Stat.onExtractMaxRetry();
1359             }
1360
1361             --m_ItemCounter;
1362             m_Stat.onExtractMaxSuccess();
1363             guard.assign( node_traits::to_value_ptr( res.pLeaf ) );
1364             return true;
1365         }
1366
1367         bool extract_min_( typename gc::Guard& guard )
1368         {
1369             update_desc * pOp = nullptr;
1370             search_result res;
1371
1372             for ( ;; ) {
1373                 if ( !search_min( res )) {
1374                     // Tree is empty
1375                     if ( pOp )
1376                         retire_update_desc( pOp );
1377                     m_Stat.onExtractMinFailed();
1378                     return false;
1379                 }
1380
1381                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1382                     if ( !pOp )
1383                         pOp = alloc_update_desc();
1384                     if ( check_delete_precondition( res ) ) {
1385                         typename gc::Guard guard;
1386                         guard.assign( pOp );
1387
1388                         pOp->dInfo.pGrandParent = res.pGrandParent;
1389                         pOp->dInfo.pParent = res.pParent;
1390                         pOp->dInfo.pLeaf = res.pLeaf;
1391                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1392                         pOp->dInfo.bRightParent = res.bRightParent;
1393                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1394
1395                         update_ptr updGP( res.updGrandParent.ptr() );
1396                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1397                             memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1398                         {
1399                             if ( help_delete( pOp ))
1400                                 break;
1401                             pOp = nullptr;
1402                         }
1403                     }
1404                 }
1405
1406                 m_Stat.onExtractMinRetry();
1407             }
1408
1409             --m_ItemCounter;
1410             m_Stat.onExtractMinSuccess();
1411             guard.assign( node_traits::to_value_ptr( res.pLeaf ));
1412             return true;
1413         }
1414
1415         template <typename Q, typename Func>
1416         bool find_( Q& val, Func f ) const
1417         {
1418             search_result    res;
1419             if ( search( res, val, node_compare() )) {
1420                 assert( res.pLeaf );
1421                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1422
1423                 m_Stat.onFindSuccess();
1424                 return true;
1425             }
1426
1427             m_Stat.onFindFailed();
1428             return false;
1429         }
1430
1431         template <typename Q, typename Less, typename Func>
1432         bool find_with_( Q& val, Less pred, Func f ) const
1433         {
1434             typedef ellen_bintree::details::compare<
1435                 key_type,
1436                 value_type,
1437                 opt::details::make_comparator_from_less<Less>,
1438                 node_traits
1439             > compare_functor;
1440
1441             search_result    res;
1442             if ( search( res, val, compare_functor() )) {
1443                 assert( res.pLeaf );
1444                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1445
1446                 m_Stat.onFindSuccess();
1447                 return true;
1448             }
1449
1450             m_Stat.onFindFailed();
1451             return false;
1452         }
1453
1454         template <typename Q>
1455         bool get_( typename gc::Guard& guard, Q const& val ) const
1456         {
1457             return find_( val, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1458         }
1459
1460         template <typename Q, typename Less>
1461         bool get_with_( typename gc::Guard& guard, Q const& val, Less pred ) const
1462         {
1463             return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1464         }
1465
1466         //@endcond
1467     };
1468
1469 }} // namespace cds::intrusive
1470
1471 #endif // #ifndef __CDS_INTRUSIVE_IMPL_ELLEN_BINTREE_H