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