cds/intrusive/ellen_bintree_impl.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_IMPL_H
   4 #define __CDS_INTRUSIVE_ELLEN_BINTREE_IMPL_H
   5
   6 #include <cds/intrusive/details/ellen_bintree_base.h>
   7 #include <cds/opt/compare.h>
   8 #include <cds/ref.h>
   9 #include <cds/details/binary_functor_wrapper.h>
  10 #include <cds/urcu/details/check_deadlock.h>
  11 #include <cds/details/std/memory.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/ellen_bintree_impl.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( null_ptr<internal_node *>() )
 229                 ,pParent( null_ptr<internal_node *>() )
 230                 ,pLeaf( null_ptr<leaf_node *>() )
 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
 322 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 323         struct trivial_equal_functor {
 324             template <typename Q>
 325             bool operator()( Q const& , leaf_node const& ) const
 326             {
 327                 return true;
 328             }
 329         };
 330
 331         struct empty_insert_functor {
 332             void operator()( value_type& )
 333             {}
 334         };
 335
 336         struct assign_guard_functor {
 337             typename gc::Guard&    m_guard;
 338             assign_guard_functor( typename gc::Guard& guard )
 339                 : m_guard(guard)
 340             {}
 341
 342             template <typename Q>
 343             void operator()( value_type& val, Q& )
 344             {
 345                 m_guard.assign( &val );
 346             }
 347
 348             void operator()( value_type& val )
 349             {
 350                 m_guard.assign( &val );
 351             }
 352         };
 353
 354 #   endif
 355
 356 #   if !defined(CDS_CXX11_LAMBDA_SUPPORT) || (CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
 357         struct unlink_equal_functor {
 358             bool operator()( value_type const& v, leaf_node const& n ) const
 359             {
 360                 return &v == node_traits::to_value_ptr( n );
 361             }
 362         };
 363         struct empty_erase_functor  {
 364             void operator()( value_type const& )
 365             {}
 366         };
 367 #   endif
 368         //@endcond
 369
 370     public:
 371         /// Default constructor
 372         EllenBinTree()
 373         {
 374             static_assert( (!std::is_same< key_extractor, opt::none >::value), "The key extractor option must be specified" );
 375             make_empty_tree();
 376         }
 377
 378         /// Clears the tree
 379         ~EllenBinTree()
 380         {
 381             unsafe_clear();
 382         }
 383
 384         /// Inserts new node
 385         /**
 386             The function inserts \p val in the tree if it does not contain
 387             an item with key equal to \p val.
 388
 389             Returns \p true if \p val is placed into the tree, \p false otherwise.
 390         */
 391         bool insert( value_type& val )
 392         {
 393 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 394             return insert( val, []( value_type& ) {} );
 395 #   else
 396             return insert( val, empty_insert_functor() );
 397 #   endif
 398         }
 399
 400         /// Inserts new node
 401         /**
 402             This function is intended for derived non-intrusive containers.
 403
 404             The function allows to split creating of new item into two part:
 405             - create item with key only
 406             - insert new item into the tree
 407             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 408
 409             The functor signature is:
 410             \code
 411                 void func( value_type& val );
 412             \endcode
 413             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 414             \p val no any other changes could be made on this tree's item by concurrent threads.
 415             The user-defined functor is called only if the inserting is success and may be passed by reference
 416             using <tt>boost::ref</tt>
 417         */
 418         template <typename Func>
 419         bool insert( value_type& val, Func f )
 420         {
 421             typename gc::Guard guardInsert;
 422             guardInsert.assign( &val );
 423
 424             unique_internal_node_ptr pNewInternal;
 425
 426             search_result res;
 427             for ( ;; ) {
 428                 if ( search( res, val, node_compare() )) {
 429                     if ( pNewInternal.get() )
 430                         m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 431                     m_Stat.onInsertFailed();
 432                     return false;
 433                 }
 434
 435                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
 436
 437                     if ( !pNewInternal.get() )
 438                         pNewInternal.reset( alloc_internal_node() );
 439
 440                     if ( try_insert( val, pNewInternal.get(), res )) {
 441                         cds::unref(f)( val );
 442                         pNewInternal.release(); // internal node is linked into the tree and should not be deleted
 443                         break;
 444                     }
 445                 }
 446
 447                 m_Stat.onInsertRetry();
 448             }
 449
 450             ++m_ItemCounter;
 451             m_Stat.onInsertSuccess();
 452             return true;
 453         }
 454
 455         /// Ensures that the \p val exists in the tree
 456         /**
 457             The operation performs inserting or changing data with lock-free manner.
 458
 459             If the item \p val is not found in the tree, then \p val is inserted into the tree.
 460             Otherwise, the functor \p func is called with item found.
 461             The functor signature is:
 462             \code
 463                 void func( bool bNew, value_type& item, value_type& val );
 464             \endcode
 465             with arguments:
 466             - \p bNew - \p true if the item has been inserted, \p false otherwise
 467             - \p item - item of the tree
 468             - \p val - argument \p val passed into the \p ensure function
 469             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 470             refer to the same thing.
 471
 472             The functor can change non-key fields of the \p item; however, \p func must guarantee
 473             that during changing no any other modifications could be made on this item by concurrent threads.
 474
 475             You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 476
 477             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 478             \p second is \p true if new item has been added or \p false if the item with \p key
 479             already is in the tree.
 480         */
 481         template <typename Func>
 482         std::pair<bool, bool> ensure( value_type& val, Func func )
 483         {
 484             typename gc::Guard guardInsert;
 485             guardInsert.assign( &val );
 486
 487             unique_internal_node_ptr pNewInternal;
 488
 489             search_result res;
 490             for ( ;; ) {
 491                 if ( search( res, val, node_compare() )) {
 492                     cds::unref(func)( false, *node_traits::to_value_ptr( res.pLeaf ), val );
 493                     if ( pNewInternal.get() )
 494                         m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 495                     m_Stat.onEnsureExist();
 496                     return std::make_pair( true, false );
 497                 }
 498
 499                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean )  {
 500
 501                     if ( !pNewInternal.get() )
 502                         pNewInternal.reset( alloc_internal_node() );
 503
 504                     if ( try_insert( val, pNewInternal.get(), res )) {
 505                         cds::unref(func)( true, val, val );
 506                         pNewInternal.release()  ;   // internal node has been linked into the tree and should not be deleted
 507                         break;
 508                     }
 509                 }
 510                 m_Stat.onEnsureRetry();
 511             }
 512
 513             ++m_ItemCounter;
 514             m_Stat.onEnsureNew();
 515             return std::make_pair( true, true );
 516         }
 517
 518         /// Unlinks the item \p val from the tree
 519         /**
 520             The function searches the item \p val in the tree and unlink it from the tree
 521             if it is found and is equal to \p val.
 522
 523             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 524             and deletes the item found. \p unlink finds an item by key and deletes it
 525             only if \p val is an item of the tree, i.e. the pointer to item found
 526             is equal to <tt> &val </tt>.
 527
 528             The \ref disposer specified in \p Traits class template parameter is called
 529             by garbage collector \p GC asynchronously.
 530
 531             The function returns \p true if success and \p false otherwise.
 532         */
 533         bool unlink( value_type& val )
 534         {
 535 #       if defined(CDS_CXX11_LAMBDA_SUPPORT) && !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
 536             // vc10 generates an error for the lambda - it sees cds::intrusive::node_traits but not class-defined node_traits
 537             return erase_( val, node_compare(),
 538                 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
 539                 [](value_type const&) {} );
 540 #       else
 541             return erase_( val, node_compare(), unlink_equal_functor(), empty_erase_functor() );
 542 #       endif
 543         }
 544
 545         /// Deletes the item from the tree
 546         /** \anchor cds_intrusive_EllenBinTree_erase
 547             The function searches an item with key equal to \p val in the tree,
 548             unlinks it from the tree, and returns \p true.
 549             If the item with key equal to \p val is not found the function return \p false.
 550
 551             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 552         */
 553         template <typename Q>
 554         bool erase( const Q& val )
 555         {
 556 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 557             return erase_( val, node_compare(),
 558                 []( Q const&, leaf_node const& ) -> bool { return true; },
 559                 [](value_type const&) {} );
 560 #       else
 561             return erase_( val, node_compare(), trivial_equal_functor(), empty_erase_functor() );
 562 #       endif
 563         }
 564
 565         /// Delete the item from the tree with comparing functor \p pred
 566         /**
 567             The function is an analog of \ref cds_intrusive_EllenBinTree_erase "erase(Q const&)"
 568             but \p pred predicate is used for key comparing.
 569             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 570             "Predicate requirements".
 571             \p pred must imply the same element order as the comparator used for building the tree.
 572         */
 573         template <typename Q, typename Less>
 574         bool erase_with( const Q& val, Less pred )
 575         {
 576             typedef ellen_bintree::details::compare<
 577                 key_type,
 578                 value_type,
 579                 opt::details::make_comparator_from_less<Less>,
 580                 node_traits
 581             > compare_functor;
 582
 583 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 584             return erase_( val, compare_functor(),
 585                 []( Q const&, leaf_node const& ) -> bool { return true; },
 586                 [](value_type const&) {} );
 587 #       else
 588             return erase_( val, compare_functor(), trivial_equal_functor(), empty_erase_functor() );
 589 #       endif
 590         }
 591
 592         /// Deletes the item from the tree
 593         /** \anchor cds_intrusive_EllenBinTree_erase_func
 594             The function searches an item with key equal to \p val in the tree,
 595             call \p f functor with item found, unlinks it from the tree, and returns \p true.
 596             The \ref disposer specified in \p Traits class template parameter is called
 597             by garbage collector \p GC asynchronously.
 598
 599             The \p Func interface is
 600             \code
 601             struct functor {
 602                 void operator()( value_type const& item );
 603             };
 604             \endcode
 605             The functor can be passed by reference with <tt>boost:ref</tt>
 606
 607             If the item with key equal to \p val is not found the function return \p false.
 608
 609             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 610         */
 611         template <typename Q, typename Func>
 612         bool erase( Q const& val, Func f )
 613         {
 614 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 615             return erase_( val, node_compare(),
 616                 []( Q const&, leaf_node const& ) -> bool { return true; },
 617                 f );
 618 #       else
 619             return erase_( val, node_compare(), trivial_equal_functor(), f );
 620 #       endif
 621         }
 622
 623         /// Delete the item from the tree with comparing functor \p pred
 624         /**
 625             The function is an analog of \ref cds_intrusive_EllenBinTree_erase_func "erase(Q const&, Func)"
 626             but \p pred predicate is used for key comparing.
 627             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 628             "Predicate requirements".
 629             \p pred must imply the same element order as the comparator used for building the tree.
 630         */
 631         template <typename Q, typename Less, typename Func>
 632         bool erase_with( Q const& val, Less pred, Func f )
 633         {
 634             typedef ellen_bintree::details::compare<
 635                 key_type,
 636                 value_type,
 637                 opt::details::make_comparator_from_less<Less>,
 638                 node_traits
 639             > compare_functor;
 640
 641 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 642             return erase_( val, compare_functor(),
 643                 []( Q const&, leaf_node const& ) -> bool { return true; },
 644                 f );
 645 #       else
 646             return erase_( val, compare_functor(), trivial_equal_functor(), f );
 647 #       endif
 648         }
 649
 650         /// Extracts an item with minimal key from the tree
 651         /**
 652             The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p dest parameter.
 653             If the tree is empty the function returns \p false.
 654
 655             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
 656             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 657             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 658             So, the function returns the item with minimum key at the moment of tree traversing.
 659
 660             The guarded pointer \p dest prevents disposer invocation for returned item,
 661             see cds::gc::guarded_ptr for explanation.
 662             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 663         */
 664         bool extract_min( guarded_ptr& dest )
 665         {
 666             return extract_min_( dest.guard());
 667         }
 668
 669         /// Extracts an item with maximal key from the tree
 670         /**
 671             The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p dest parameter.
 672             If the tree is empty the function returns \p false.
 673
 674             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
 675             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 676             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
 677             So, the function returns the item with maximal key at the moment of tree traversing.
 678
 679             The guarded pointer \p dest prevents disposer invocation for returned item,
 680             see cds::gc::guarded_ptr for explanation.
 681             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 682         */
 683         bool extract_max( guarded_ptr& dest )
 684         {
 685             return extract_max_( dest.guard() );
 686         }
 687
 688         /// Extracts an item from the tree
 689         /** \anchor cds_intrusive_EllenBinTree_extract
 690             The function searches an item with key equal to \p key in the tree,
 691             unlinks it, and returns pointer to an item found in \p dest parameter.
 692             If the item  is not found the function returns \p false.
 693
 694             The guarded pointer \p dest prevents disposer invocation for returned item,
 695             see cds::gc::guarded_ptr for explanation.
 696             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 697         */
 698         template <typename Q>
 699         bool extract( guarded_ptr& dest, Q const& key )
 700         {
 701             return extract_( dest.guard(), key );
 702         }
 703
 704         /// Extracts an item from the tree using \p pred for searching
 705         /**
 706             The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(guarded_ptr& dest, Q const&)"
 707             but \p pred is used for key compare.
 708             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 709             "Predicate requirements".
 710             \p pred must imply the same element order as the comparator used for building the tree.
 711         */
 712         template <typename Q, typename Less>
 713         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
 714         {
 715             return extract_with_( dest.guard(), key, pred );
 716         }
 717
 718         /// Finds the key \p val
 719         /** @anchor cds_intrusive_EllenBinTree_find_val
 720             The function searches the item with key equal to \p val
 721             and returns \p true if it is found, and \p false otherwise.
 722
 723             Note the hash functor specified for class \p Traits template parameter
 724             should accept a parameter of type \p Q that can be not the same as \p value_type.
 725         */
 726         template <typename Q>
 727         bool find( Q const& val ) const
 728         {
 729             search_result    res;
 730             if ( search( res, val, node_compare() )) {
 731                 m_Stat.onFindSuccess();
 732                 return true;
 733             }
 734
 735             m_Stat.onFindFailed();
 736             return false;
 737         }
 738
 739         /// Finds the key \p val with comparing functor \p pred
 740         /**
 741             The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
 742             but \p pred is used for key compare.
 743             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 744             "Predicate requirements".
 745             \p pred must imply the same element order as the comparator used for building the tree.
 746             \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
 747         */
 748         template <typename Q, typename Less>
 749         bool find_with( Q const& val, Less pred ) const
 750         {
 751             typedef ellen_bintree::details::compare<
 752                 key_type,
 753                 value_type,
 754                 opt::details::make_comparator_from_less<Less>,
 755                 node_traits
 756             > compare_functor;
 757
 758             search_result    res;
 759             if ( search( res, val, compare_functor() )) {
 760                 m_Stat.onFindSuccess();
 761                 return true;
 762             }
 763             m_Stat.onFindFailed();
 764             return false;
 765         }
 766
 767         /// Finds the key \p val
 768         /** @anchor cds_intrusive_EllenBinTree_find_func
 769             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 770             The interface of \p Func functor is:
 771             \code
 772             struct functor {
 773                 void operator()( value_type& item, Q& val );
 774             };
 775             \endcode
 776             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 777
 778             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 779
 780             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 781             that \p item cannot be disposed during functor is executing.
 782             The functor does not serialize simultaneous access to the tree \p item. If such access is
 783             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 784
 785             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 786             can modify both arguments.
 787
 788             The function returns \p true if \p val is found, \p false otherwise.
 789         */
 790         template <typename Q, typename Func>
 791         bool find( Q& val, Func f ) const
 792         {
 793             return find_( val, f );
 794         }
 795
 796         /// Finds the key \p val with comparing functor \p pred
 797         /**
 798             The function is an analog of \ref cds_intrusive_EllenBinTree_find_func "find(Q&, Func)"
 799             but \p pred is used for key comparison.
 800             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 801             "Predicate requirements".
 802             \p pred must imply the same element order as the comparator used for building the tree.
 803         */
 804         template <typename Q, typename Less, typename Func>
 805         bool find_with( Q& val, Less pred, Func f ) const
 806         {
 807             return find_with_( val, pred, f );
 808         }
 809
 810         /// Finds the key \p val
 811         /** @anchor cds_intrusive_EllenBinTree_find_cfunc
 812             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 813             The interface of \p Func functor is:
 814             \code
 815             struct functor {
 816                 void operator()( value_type& item, Q const& val );
 817             };
 818             \endcode
 819             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 820
 821             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 822
 823             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 824             that \p item cannot be disposed during functor is executing.
 825             The functor does not serialize simultaneous access to the tree \p item. If such access is
 826             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 827
 828             The function returns \p true if \p val is found, \p false otherwise.
 829         */
 830         template <typename Q, typename Func>
 831         bool find( Q const& val, Func f ) const
 832         {
 833             return find_( val, f );
 834         }
 835
 836         /// Finds the key \p val with comparing functor \p pred
 837         /**
 838             The function is an analog of \ref cds_intrusive_EllenBinTree_find_cfunc "find(Q const&, Func)"
 839             but \p pred is used for key compare.
 840             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 841             "Predicate requirements".
 842             \p pred must imply the same element order as the comparator used for building the tree.
 843         */
 844         template <typename Q, typename Less, typename Func>
 845         bool find_with( Q const& val, Less pred, Func f ) const
 846         {
 847             return find_with_( val, pred, f );
 848         }
 849
 850         /// Finds \p key and returns the item found
 851         /** @anchor cds_intrusive_EllenBinTree_get
 852             The function searches the item with key equal to \p key and returns the item found in \p dest parameter.
 853             The function returns \p true if \p key is found, \p false otherwise.
 854
 855             The guarded pointer \p dest prevents disposer invocation for returned item,
 856             see cds::gc::guarded_ptr for explanation.
 857             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 858         */
 859         template <typename Q>
 860         bool get( guarded_ptr& dest, Q const& key ) const
 861         {
 862             return get_( dest.guard(), key );
 863         }
 864
 865         /// Finds \p key with predicate \p pred and returns the item found
 866         /**
 867             The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(guarded_ptr&, Q const&)"
 868             but \p pred is used for key comparing.
 869             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
 870             "Predicate requirements".
 871             \p pred must imply the same element order as the comparator used for building the tree.
 872         */
 873         template <typename Q, typename Less>
 874         bool get_with( guarded_ptr& dest, Q const& key, Less pred ) const
 875         {
 876             return get_with_( dest.guard(), key, pred );
 877         }
 878
 879         /// Checks if the tree is empty
 880         bool empty() const
 881         {
 882             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
 883         }
 884
 885         /// Clears the tree (thread safe, non-atomic)
 886         /**
 887             The function unlink all items from the tree.
 888             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 889             this sequence
 890             \code
 891             tree.clear();
 892             assert( tree.empty() );
 893             \endcode
 894             the assertion could be raised.
 895
 896             For each leaf the \ref disposer will be called after unlinking.
 897         */
 898         void clear()
 899         {
 900             guarded_ptr gp;
 901             while ( extract_min(gp));
 902         }
 903
 904         /// Clears the tree (not thread safe)
 905         /**
 906             This function is not thread safe and may be called only when no other thread deals with the tree.
 907             The function is used in the tree destructor.
 908         */
 909         void unsafe_clear()
 910         {
 911             while ( true ) {
 912                 internal_node * pParent = null_ptr< internal_node *>();
 913                 internal_node * pGrandParent = null_ptr<internal_node *>();
 914                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
 915
 916                 // Get leftmost leaf
 917                 while ( pLeaf->is_internal() ) {
 918                     pGrandParent = pParent;
 919                     pParent = static_cast<internal_node *>( pLeaf );
 920                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
 921                 }
 922
 923                 if ( pLeaf->infinite_key()) {
 924                     // The tree is empty
 925                     return;
 926                 }
 927
 928                 // Remove leftmost leaf and its parent node
 929                 assert( pGrandParent );
 930                 assert( pParent );
 931                 assert( pLeaf->is_leaf() );
 932
 933                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
 934                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
 935                 free_internal_node( pParent );
 936             }
 937         }
 938
 939         /// Returns item count in the tree
 940         /**
 941             Only leaf nodes containing user data are counted.
 942
 943             The value returned depends on item counter type provided by \p Traits template parameter.
 944             If it is atomicity::empty_item_counter this function always returns 0.
 945             Therefore, the function is not suitable for checking the tree emptiness, use \ref empty
 946             member function for this purpose.
 947         */
 948         size_t size() const
 949         {
 950             return m_ItemCounter;
 951         }
 952
 953         /// Returns const reference to internal statistics
 954         stat const& statistics() const
 955         {
 956             return m_Stat;
 957         }
 958
 959         /// Checks internal consistency (not atomic, not thread-safe)
 960         /**
 961             The debugging function to check internal consistency of the tree.
 962         */
 963         bool check_consistency() const
 964         {
 965             return check_consistency( &m_Root );
 966         }
 967
 968     protected:
 969         //@cond
 970
 971         bool check_consistency( internal_node const * pRoot ) const
 972         {
 973             tree_node * pLeft  = pRoot->m_pLeft.load( CDS_ATOMIC::memory_order_relaxed );
 974             tree_node * pRight = pRoot->m_pRight.load( CDS_ATOMIC::memory_order_relaxed );
 975             assert( pLeft );
 976             assert( pRight );
 977
 978             if ( node_compare()( *pLeft, *pRoot ) < 0
 979                 && node_compare()( *pRoot, *pRight ) <= 0
 980                 && node_compare()( *pLeft, *pRight ) < 0 )
 981             {
 982                 bool bRet = true;
 983                 if ( pLeft->is_internal() )
 984                     bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
 985                 assert( bRet );
 986
 987                 if ( bRet && pRight->is_internal() )
 988                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
 989                 assert( bRet );
 990
 991                 return bRet;
 992             }
 993             return false;
 994         }
 995
 996         tree_node * protect_child_node( search_result& res, internal_node * pParent, bool bRight, update_ptr updParent ) const
 997         {
 998             tree_node * p;
 999             tree_node * pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_relaxed ) : pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1000             do {
1001                 p = pn;
1002                 res.guards.assign( search_result::Guard_Leaf, static_cast<internal_node *>( p ));
1003                 res.guards.assign( search_result::Guard_helpLeaf, node_traits::to_value_ptr( static_cast<leaf_node *>( p ) ));
1004                 pn = bRight ? pParent->m_pRight.load( memory_model::memory_order_acquire ) : pParent->m_pLeft.load( memory_model::memory_order_acquire );
1005             } while ( p != pn );
1006
1007             // child node is guarded
1008             // See whether pParent->m_pUpdate has not been changed
1009             if ( pParent->m_pUpdate.load( memory_model::memory_order_acquire ) != updParent ) {
1010                 // update has been changed - returns nullptr as a flag to search retry
1011                 return null_ptr<tree_node *>();
1012             }
1013
1014             if ( p && p->is_leaf() )
1015                 res.guards.copy( search_result::Guard_Leaf, search_result::Guard_helpLeaf );
1016             res.guards.clear( search_result::Guard_helpLeaf );
1017             return p;
1018         }
1019
1020         update_ptr search_protect_update( search_result& res, CDS_ATOMIC::atomic<update_ptr> const& src ) const
1021         {
1022             update_ptr ret;
1023             update_ptr upd( src.load( memory_model::memory_order_relaxed ) );
1024             do {
1025                 ret = upd;
1026                 res.guards.assign( search_result::Guard_updParent, upd );
1027             } while ( ret != (upd = src.load( memory_model::memory_order_acquire )) );
1028             return ret;
1029         }
1030
1031         template <typename KeyValue, typename Compare>
1032         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1033         {
1034             internal_node * pParent;
1035             internal_node * pGrandParent = null_ptr<internal_node *>();
1036             update_ptr      updParent;
1037             update_ptr      updGrandParent;
1038             bool bRightLeaf;
1039             bool bRightParent = false;
1040
1041             int nCmp = 0;
1042
1043         retry:
1044             pParent = null_ptr< internal_node *>();
1045             //pGrandParent = null_ptr<internal_node *>();
1046             updParent = null_ptr<update_desc *>();
1047             bRightLeaf = false;
1048             tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1049             while ( pLeaf->is_internal() ) {
1050                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1051                 pGrandParent = pParent;
1052                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1053                 pParent = static_cast<internal_node *>( pLeaf );
1054                 bRightParent = bRightLeaf;
1055                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1056                 updGrandParent = updParent;
1057
1058                 updParent = search_protect_update( res, pParent->m_pUpdate );
1059
1060                 switch ( updParent.bits() ) {
1061                     case update_desc::DFlag:
1062                     case update_desc::Mark:
1063                         m_Stat.onSearchRetry();
1064                         goto retry;
1065                 }
1066
1067                 nCmp = cmp( key, *pParent );
1068                 bRightLeaf = nCmp >= 0;
1069
1070                 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1071                 if ( !pLeaf ) {
1072                     m_Stat.onSearchRetry();
1073                     goto retry;
1074                 }
1075             }
1076
1077             assert( pLeaf->is_leaf() );
1078             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1079
1080             res.pGrandParent    = pGrandParent;
1081             res.pParent         = pParent;
1082             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1083             res.updParent       = updParent;
1084             res.updGrandParent  = updGrandParent;
1085             res.bRightParent    = bRightParent;
1086             res.bRightLeaf      = bRightLeaf;
1087
1088             return nCmp == 0;
1089         }
1090
1091         bool search_min( search_result& res ) const
1092         {
1093             internal_node * pParent;
1094             internal_node * pGrandParent;
1095             update_ptr      updParent;
1096             update_ptr      updGrandParent;
1097
1098         retry:
1099             pParent = null_ptr< internal_node *>();
1100             pGrandParent = null_ptr<internal_node *>();
1101             updParent = null_ptr<update_desc *>();
1102             tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
1103             while ( pLeaf->is_internal() ) {
1104                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1105                 pGrandParent = pParent;
1106                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1107                 pParent = static_cast<internal_node *>( pLeaf );
1108                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1109                 updGrandParent = updParent;
1110
1111                 updParent = search_protect_update( res, pParent->m_pUpdate );
1112
1113                 switch ( updParent.bits() ) {
1114                     case update_desc::DFlag:
1115                     case update_desc::Mark:
1116                         m_Stat.onSearchRetry();
1117                         goto retry;
1118                 }
1119
1120                 pLeaf = protect_child_node( res, pParent, false, updParent );
1121                 if ( !pLeaf ) {
1122                     m_Stat.onSearchRetry();
1123                     goto retry;
1124                 }
1125             }
1126
1127             if ( pLeaf->infinite_key())
1128                 return false;
1129
1130             res.pGrandParent    = pGrandParent;
1131             res.pParent         = pParent;
1132             assert( pLeaf->is_leaf() );
1133             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1134             res.updParent       = updParent;
1135             res.updGrandParent  = updGrandParent;
1136             res.bRightParent    = false;
1137             res.bRightLeaf      = false;
1138
1139             return true;
1140         }
1141
1142         bool search_max( search_result& res ) const
1143         {
1144             internal_node * pParent;
1145             internal_node * pGrandParent;
1146             update_ptr      updParent;
1147             update_ptr      updGrandParent;
1148             bool bRightLeaf;
1149             bool bRightParent = false;
1150
1151         retry:
1152             pParent = null_ptr< internal_node *>();
1153             pGrandParent = null_ptr<internal_node *>();
1154             updParent = null_ptr<update_desc *>();
1155             bRightLeaf = false;
1156             tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
1157             while ( pLeaf->is_internal() ) {
1158                 res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
1159                 pGrandParent = pParent;
1160                 res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
1161                 pParent = static_cast<internal_node *>( pLeaf );
1162                 bRightParent = bRightLeaf;
1163                 res.guards.copy( search_result::Guard_updGrandParent, search_result::Guard_updParent );
1164                 updGrandParent = updParent;
1165
1166                 updParent = search_protect_update( res, pParent->m_pUpdate );
1167
1168                 switch ( updParent.bits() ) {
1169                     case update_desc::DFlag:
1170                     case update_desc::Mark:
1171                         m_Stat.onSearchRetry();
1172                         goto retry;
1173                 }
1174
1175                 bRightLeaf = !pParent->infinite_key();
1176                 pLeaf = protect_child_node( res, pParent, bRightLeaf, updParent );
1177                 if ( !pLeaf ) {
1178                     m_Stat.onSearchRetry();
1179                     goto retry;
1180                 }
1181             }
1182
1183             if ( pLeaf->infinite_key())
1184                 return false;
1185
1186             res.pGrandParent    = pGrandParent;
1187             res.pParent         = pParent;
1188             assert( pLeaf->is_leaf() );
1189             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1190             res.updParent       = updParent;
1191             res.updGrandParent  = updGrandParent;
1192             res.bRightParent    = bRightParent;
1193             res.bRightLeaf      = bRightLeaf;
1194
1195             return true;
1196         }
1197
1198         void help( update_ptr pUpdate )
1199         {
1200             // pUpdate must be guarded!
1201             switch ( pUpdate.bits() ) {
1202                 case update_desc::IFlag:
1203                     help_insert( pUpdate.ptr() );
1204                     m_Stat.onHelpInsert();
1205                     break;
1206                 case update_desc::DFlag:
1207                     help_delete( pUpdate.ptr() );
1208                     m_Stat.onHelpDelete();
1209                     break;
1210                 case update_desc::Mark:
1211                     //m_Stat.onHelpMark();
1212                     //help_marked( pUpdate.ptr() );
1213                     break;
1214             }
1215         }
1216
1217         void help_insert( update_desc * pOp )
1218         {
1219             // pOp must be guarded
1220
1221             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1222             if ( pOp->iInfo.bRightLeaf ) {
1223                 CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1224                     memory_model::memory_order_relaxed, CDS_ATOMIC::memory_order_relaxed ));
1225             }
1226             else {
1227                 CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1228                     memory_model::memory_order_relaxed, CDS_ATOMIC::memory_order_relaxed ));
1229             }
1230
1231             // Unflag parent
1232             update_ptr cur( pOp, update_desc::IFlag );
1233             CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1234                 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ));
1235         }
1236
1237         bool check_delete_precondition( search_result& res ) const
1238         {
1239             // precondition: all member of res must be guarded
1240
1241             assert( res.pGrandParent != null_ptr<internal_node *>() );
1242
1243             return
1244                 static_cast<internal_node *>(
1245                     res.bRightParent
1246                         ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1247                         : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1248                     ) == res.pParent
1249                 &&
1250                 static_cast<leaf_node *>(
1251                     res.bRightLeaf
1252                         ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1253                         : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1254                 ) == res.pLeaf;
1255         }
1256
1257         bool help_delete( update_desc * pOp )
1258         {
1259             // precondition: pOp must be guarded
1260
1261             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1262             update_ptr pMark( pOp, update_desc::Mark );
1263             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // *
1264                 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1265             {
1266                 help_marked( pOp );
1267
1268                 retire_node( pOp->dInfo.pParent );
1269                 retire_node( pOp->dInfo.pLeaf );
1270                 retire_update_desc( pOp );
1271                 return true;
1272             }
1273             else if ( pUpdate == pMark ) {
1274                 // some other thread is processing help_marked()
1275                 help_marked( pOp );
1276                 m_Stat.onHelpMark();
1277                 return true;
1278             }
1279             else {
1280                 // Undo grandparent dInfo
1281                 update_ptr pDel( pOp, update_desc::DFlag );
1282                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1283                     memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
1284                 {
1285                     retire_update_desc( pOp );
1286                 }
1287                 return false;
1288             }
1289         }
1290
1291         tree_node * protect_sibling( typename gc::Guard& guard, CDS_ATOMIC::atomic<tree_node *>& sibling )
1292         {
1293             typename gc::Guard guardLeaf;
1294
1295             tree_node * pSibling;
1296             tree_node * p = sibling.load( memory_model::memory_order_relaxed );
1297             do {
1298                 pSibling = p;
1299                 guard.assign( static_cast<internal_node *>(p) );
1300                 guardLeaf.assign( node_traits::to_value_ptr( static_cast<leaf_node *>(p)));
1301             } while ( pSibling != ( p = sibling.load( memory_model::memory_order_acquire )) );
1302
1303             if ( pSibling->is_leaf() )
1304                 guard.copy( guardLeaf );
1305
1306             return pSibling;
1307         }
1308
1309         void help_marked( update_desc * pOp )
1310         {
1311             // precondition: pOp must be guarded
1312
1313             tree_node * pParent = pOp->dInfo.pParent;
1314
1315             typename gc::Guard guard;
1316             tree_node * pOpposite = protect_sibling( guard, pOp->dInfo.bRightLeaf ? pOp->dInfo.pParent->m_pLeft : pOp->dInfo.pParent->m_pRight );
1317
1318             if ( pOp->dInfo.bRightParent ) {
1319                 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( pParent, pOpposite,
1320                     memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ));
1321             }
1322             else {
1323                 CDS_VERIFY( pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( pParent, pOpposite,
1324                     memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ));
1325             }
1326
1327             update_ptr upd( pOp, update_desc::DFlag );
1328             CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1329                 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ));
1330         }
1331
1332         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
1333         {
1334             assert( res.updParent.bits() == update_desc::Clean );
1335             assert( res.pLeaf->is_leaf() );
1336
1337             // check search result
1338             if ( ( res.bRightLeaf
1339                 ? res.pParent->m_pRight.load( memory_model::memory_order_acquire )
1340                 : res.pParent->m_pLeft.load( memory_model::memory_order_acquire ) ) == res.pLeaf )
1341             {
1342                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1343
1344                 int nCmp = node_compare()( val, *res.pLeaf );
1345                 if ( nCmp < 0 ) {
1346                     if ( res.pGrandParent ) {
1347                         assert( !res.pLeaf->infinite_key() );
1348                         pNewInternal->infinite_key( 0 );
1349                         key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1350                     }
1351                     else {
1352                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1353                         pNewInternal->infinite_key( 1 );
1354                     }
1355                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1356                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1357                 }
1358                 else {
1359                     assert( !res.pLeaf->is_internal() );
1360                     pNewInternal->infinite_key( 0 );
1361
1362                     key_extractor()( pNewInternal->m_Key, val );
1363                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1364                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1365                     assert( !res.pLeaf->infinite_key());
1366                 }
1367
1368                 typename gc::Guard guard;
1369                 update_desc * pOp = alloc_update_desc();
1370                 guard.assign( pOp );
1371
1372                 pOp->iInfo.pParent = res.pParent;
1373                 pOp->iInfo.pNew = pNewInternal;
1374                 pOp->iInfo.pLeaf = res.pLeaf;
1375                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1376
1377                 update_ptr updCur( res.updParent.ptr() );
1378                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1379                     memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1380                 {
1381                     // do insert
1382                     help_insert( pOp );
1383                     retire_update_desc( pOp );
1384                     return true;
1385                 }
1386                 else {
1387                     m_Stat.onUpdateDescDeleted();
1388                     free_update_desc( pOp );
1389                 }
1390             }
1391             return false;
1392         }
1393
1394         template <typename Q, typename Compare, typename Equal, typename Func>
1395         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1396         {
1397             update_desc * pOp = null_ptr<update_desc *>();
1398             search_result res;
1399
1400             for ( ;; ) {
1401                 if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1402                     if ( pOp )
1403                         retire_update_desc( pOp );
1404                     m_Stat.onEraseFailed();
1405                     return false;
1406                 }
1407
1408                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1409                     if ( !pOp )
1410                         pOp = alloc_update_desc();
1411                     if ( check_delete_precondition( res ) ) {
1412                         typename gc::Guard guard;
1413                         guard.assign( pOp );
1414
1415                         pOp->dInfo.pGrandParent = res.pGrandParent;
1416                         pOp->dInfo.pParent = res.pParent;
1417                         pOp->dInfo.pLeaf = res.pLeaf;
1418                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1419                         pOp->dInfo.bRightParent = res.bRightParent;
1420                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1421
1422                         update_ptr updGP( res.updGrandParent.ptr() );
1423                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1424                             memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1425                         {
1426                             if ( help_delete( pOp )) {
1427                                 // res.pLeaf is not deleted yet since it is guarded
1428                                 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ));
1429                                 break;
1430                             }
1431                             pOp = null_ptr<update_desc *>();
1432                         }
1433                     }
1434                 }
1435
1436                 m_Stat.onEraseRetry();
1437             }
1438
1439             --m_ItemCounter;
1440             m_Stat.onEraseSuccess();
1441             return true;
1442         }
1443
1444         template <typename Q>
1445         bool extract_( typename gc::Guard& guard, Q const& key )
1446         {
1447 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1448             return erase_( key, node_compare(),
1449                 []( Q const&, leaf_node const& ) -> bool { return true; },
1450                 [&guard]( value_type& found ) { guard.assign( &found ); } );
1451 #       else
1452             assign_guard_functor f( guard );
1453             return erase_( key, node_compare(), trivial_equal_functor(), cds::ref(f) );
1454 #       endif
1455         }
1456
1457         template <typename Q, typename Less>
1458         bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
1459         {
1460             typedef ellen_bintree::details::compare<
1461                 key_type,
1462                 value_type,
1463                 opt::details::make_comparator_from_less<Less>,
1464                 node_traits
1465             > compare_functor;
1466
1467 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1468             return erase_( key, compare_functor(),
1469                 []( Q const&, leaf_node const& ) -> bool { return true; },
1470                 [&guard]( value_type& found ) { guard.assign( &found ); } );
1471 #       else
1472             assign_guard_functor f( guard );
1473             return erase_( key, compare_functor(), trivial_equal_functor(), cds::ref(f) );
1474 #       endif
1475         }
1476
1477         bool extract_max_( typename gc::Guard& guard )
1478         {
1479             update_desc * pOp = null_ptr<update_desc *>();
1480             search_result res;
1481
1482             for ( ;; ) {
1483                 if ( !search_max( res )) {
1484                     // Tree is empty
1485                     if ( pOp )
1486                         retire_update_desc( pOp );
1487                     m_Stat.onExtractMaxFailed();
1488                     return false;
1489                 }
1490
1491                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean )  {
1492                     if ( !pOp )
1493                         pOp = alloc_update_desc();
1494                     if ( check_delete_precondition( res ) ) {
1495                         typename gc::Guard guard;
1496                         guard.assign( pOp );
1497
1498                         pOp->dInfo.pGrandParent = res.pGrandParent;
1499                         pOp->dInfo.pParent = res.pParent;
1500                         pOp->dInfo.pLeaf = res.pLeaf;
1501                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1502                         pOp->dInfo.bRightParent = res.bRightParent;
1503                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1504
1505                         update_ptr updGP( res.updGrandParent.ptr() );
1506                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1507                             memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1508                         {
1509                             if ( help_delete( pOp ))
1510                                 break;
1511                             pOp = null_ptr<update_desc *>();
1512                         }
1513                     }
1514                 }
1515
1516                 m_Stat.onExtractMaxRetry();
1517             }
1518
1519             --m_ItemCounter;
1520             m_Stat.onExtractMaxSuccess();
1521             guard.assign( node_traits::to_value_ptr( res.pLeaf ) );
1522             return true;
1523         }
1524
1525         bool extract_min_( typename gc::Guard& guard )
1526         {
1527             update_desc * pOp = null_ptr<update_desc *>();
1528             search_result res;
1529
1530             for ( ;; ) {
1531                 if ( !search_min( res )) {
1532                     // Tree is empty
1533                     if ( pOp )
1534                         retire_update_desc( pOp );
1535                     m_Stat.onExtractMinFailed();
1536                     return false;
1537                 }
1538
1539                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
1540                     if ( !pOp )
1541                         pOp = alloc_update_desc();
1542                     if ( check_delete_precondition( res ) ) {
1543                         typename gc::Guard guard;
1544                         guard.assign( pOp );
1545
1546                         pOp->dInfo.pGrandParent = res.pGrandParent;
1547                         pOp->dInfo.pParent = res.pParent;
1548                         pOp->dInfo.pLeaf = res.pLeaf;
1549                         pOp->dInfo.pUpdateParent = res.updParent.ptr();
1550                         pOp->dInfo.bRightParent = res.bRightParent;
1551                         pOp->dInfo.bRightLeaf = res.bRightLeaf;
1552
1553                         update_ptr updGP( res.updGrandParent.ptr() );
1554                         if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1555                             memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1556                         {
1557                             if ( help_delete( pOp ))
1558                                 break;
1559                             pOp = null_ptr<update_desc *>();
1560                         }
1561                     }
1562                 }
1563
1564                 m_Stat.onExtractMinRetry();
1565             }
1566
1567             --m_ItemCounter;
1568             m_Stat.onExtractMinSuccess();
1569             guard.assign( node_traits::to_value_ptr( res.pLeaf ));
1570             return true;
1571         }
1572
1573         template <typename Q, typename Func>
1574         bool find_( Q& val, Func f ) const
1575         {
1576             search_result    res;
1577             if ( search( res, val, node_compare() )) {
1578                 assert( res.pLeaf );
1579                 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), val );
1580
1581                 m_Stat.onFindSuccess();
1582                 return true;
1583             }
1584
1585             m_Stat.onFindFailed();
1586             return false;
1587         }
1588
1589         template <typename Q, typename Less, typename Func>
1590         bool find_with_( Q& val, Less pred, Func f ) const
1591         {
1592             typedef ellen_bintree::details::compare<
1593                 key_type,
1594                 value_type,
1595                 opt::details::make_comparator_from_less<Less>,
1596                 node_traits
1597             > compare_functor;
1598
1599             search_result    res;
1600             if ( search( res, val, compare_functor() )) {
1601                 assert( res.pLeaf );
1602                 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), val );
1603
1604                 m_Stat.onFindSuccess();
1605                 return true;
1606             }
1607
1608             m_Stat.onFindFailed();
1609             return false;
1610         }
1611
1612         template <typename Q>
1613         bool get_( typename gc::Guard& guard, Q const& val ) const
1614         {
1615 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1616             return find_( val, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1617 #       else
1618             assign_guard_functor f(guard);
1619             return find_( val, cds::ref(f) );
1620 #       endif
1621         }
1622
1623         template <typename Q, typename Less>
1624         bool get_with_( typename gc::Guard& guard, Q const& val, Less pred ) const
1625         {
1626 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1627             return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.assign( &found ); } );
1628 #       else
1629             assign_guard_functor f(guard);
1630             return find_with_( val, pred, cds::ref(f) );
1631 #       endif
1632         }
1633
1634         //@endcond
1635     };
1636
1637 }} // namespace cds::intrusive
1638
1639 #endif // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_IMPL_H