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