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