cds/intrusive/impl/ellen_bintree.h

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