cds/intrusive/ellen_bintree_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
   4 #define __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
   5
   6 #include <memory>
   7 #include <cds/intrusive/details/ellen_bintree_base.h>
   8 #include <cds/opt/compare.h>
   9 #include <cds/details/binary_functor_wrapper.h>
  10 #include <cds/urcu/details/check_deadlock.h>
  11 #include <cds/urcu/exempt_ptr.h>
  12
  13 namespace cds { namespace intrusive {
  14     //@cond
  15     namespace ellen_bintree {
  16
  17         template <class RCU>
  18         struct base_node<cds::urcu::gc<RCU> >: public basic_node
  19         {
  20             typedef basic_node base_class;
  21
  22             base_node * m_pNextRetired;
  23
  24             typedef cds::urcu::gc<RCU> gc       ;   ///< Garbage collector
  25
  26             /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
  27             explicit base_node( bool bInternal )
  28                 : basic_node( bInternal ? internal : 0 )
  29                 , m_pNextRetired( nullptr )
  30             {}
  31         };
  32
  33     } // namespace ellen_bintree
  34     //@endcond
  35
  36     /// Ellen's et al binary search tree (RCU specialization)
  37     /** @ingroup cds_intrusive_map
  38         @ingroup cds_intrusive_tree
  39         @anchor cds_intrusive_EllenBinTree_rcu
  40
  41         Source:
  42             - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
  43
  44         %EllenBinTree is an unbalanced leaf-oriented binary search tree that implements the <i>set</i>
  45         abstract data type. Nodes maintains child pointers but not parent pointers.
  46         Every internal node has exactly two children, and all data of type \p T currently in
  47         the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
  48         operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
  49         may or may not be in the set. \p Key type is a subset of \p T type.
  50         There should be exactly defined a key extracting functor for converting object of type \p T to
  51         object of type \p Key.
  52
  53         Due to \p extract_min and \p extract_max member functions the \p %EllenBinTree can act as
  54         a <i>priority queue</i>. In this case you should provide unique compound key, for example,
  55         the priority value plus some uniformly distributed random value.
  56
  57         @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
  58         for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
  59
  60         @note In the current implementation we do not use helping technique described in original paper.
  61         So, the current implementation is near to fine-grained lock-based tree.
  62         Helping will be implemented in future release
  63
  64         <b>Template arguments</b> :
  65         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  66         - \p Key - key type, a subset of \p T
  67         - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
  68             (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
  69             (for \p ellen_bintree::member_hook).
  70         - \p Traits - tree traits, default is \p ellen_bintree::traits
  71             It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
  72             instead of \p Traits template argument.
  73
  74         @anchor cds_intrusive_EllenBinTree_rcu_less
  75         <b>Predicate requirements</b>
  76
  77         \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
  78         of type \p T and \p Key in any combination.
  79         For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
  80         \code
  81         struct Foo: public cds::intrusive::ellen_bintree::node< ... >
  82         {
  83             std::string m_strKey;
  84             ...
  85         };
  86
  87         struct less {
  88             bool operator()( Foo const& v1, Foo const& v2 ) const
  89             { return v1.m_strKey < v2.m_strKey ; }
  90
  91             bool operator()( Foo const& v, std::string const& s ) const
  92             { return v.m_strKey < s ; }
  93
  94             bool operator()( std::string const& s, Foo const& v ) const
  95             { return s < v.m_strKey ; }
  96
  97             // Support comparing std::string and char const *
  98             bool operator()( std::string const& s, char const * p ) const
  99             { return s.compare(p) < 0 ; }
 100
 101             bool operator()( Foo const& v, char const * p ) const
 102             { return v.m_strKey.compare(p) < 0 ; }
 103
 104             bool operator()( char const * p, std::string const& s ) const
 105             { return s.compare(p) > 0; }
 106
 107             bool operator()( char const * p, Foo const& v ) const
 108             { return v.m_strKey.compare(p) > 0; }
 109         };
 110         \endcode
 111
 112         @note Before including <tt><cds/intrusive/ellen_bintree_rcu.h></tt> you should include appropriate RCU header file,
 113         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
 114
 115         @anchor cds_intrusive_EllenBinTree_usage
 116         <b>Usage</b>
 117
 118         Suppose we have the following Foo struct with string key type:
 119         \code
 120         struct Foo {
 121             std::string     m_strKey    ;   // The key
 122             //...                           // other non-key data
 123         };
 124         \endcode
 125
 126         We want to utilize RCU-based \p %cds::intrusive::EllenBinTree set for \p Foo data.
 127         We may use base hook or member hook. Consider base hook variant.
 128         First, we need deriving \p Foo struct from \p cds::intrusive::ellen_bintree::node:
 129         \code
 130         #include <cds/urcu/general_buffered.h>
 131         #include <cds/intrusive/ellen_bintree_rcu.h>
 132
 133         // RCU type we use
 134         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  gpb_rcu;
 135
 136         struct Foo: public cds::intrusive:ellen_bintree::node< gpb_rcu >
 137         {
 138             std::string     m_strKey    ;   // The key
 139             //...                           // other non-key data
 140         };
 141         \endcode
 142
 143         Second, we need to implement auxiliary structures and functors:
 144         - key extractor functor for extracting the key from \p Foo object.
 145             Such functor is necessary because the tree internal nodes store the keys.
 146         - \p less predicate. We want our set should accept \p std::string
 147             and <tt>char const *</tt> parameters for searching, so our \p less
 148             predicate will not be trivial, see below.
 149         - item counting feature: we want our set's \p size() member function
 150             returns actual item count.
 151
 152         \code
 153         // Key extractor functor
 154         struct my_key_extractor
 155         {
 156             void operator ()( std::string& key, Foo const& src ) const
 157             {
 158                 key = src.m_strKey;
 159             }
 160         };
 161
 162         // Less predicate
 163         struct my_less {
 164             bool operator()( Foo const& v1, Foo const& v2 ) const
 165             { return v1.m_strKey < v2.m_strKey ; }
 166
 167             bool operator()( Foo const& v, std::string const& s ) const
 168             { return v.m_strKey < s ; }
 169
 170             bool operator()( std::string const& s, Foo const& v ) const
 171             { return s < v.m_strKey ; }
 172
 173             // Support comparing std::string and char const *
 174             bool operator()( std::string const& s, char const * p ) const
 175             { return s.compare(p) < 0 ; }
 176
 177             bool operator()( Foo const& v, char const * p ) const
 178             { return v.m_strKey.compare(p) < 0 ; }
 179
 180             bool operator()( char const * p, std::string const& s ) const
 181             { return s.compare(p) > 0; }
 182
 183             bool operator()( char const * p, Foo const& v ) const
 184             { return v.m_strKey.compare(p) > 0; }
 185         };
 186
 187         // Tree traits for our set
 188         // It is necessary to specify only those typedefs that differ from
 189         // cds::intrusive::ellen_bintree::traits defaults.
 190         struct set_traits: public cds::intrusive::ellen_bintree::traits
 191         {
 192             typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > > hook;
 193             typedef my_key_extractor    key_extractor;
 194             typedef my_less             less;
 195             typedef cds::atomicity::item_counter item_counter;
 196         };
 197         \endcode
 198
 199         Now we declare \p %EllenBinTree set and use it:
 200         \code
 201         typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, set_traits >   set_type;
 202
 203         set_type    theSet;
 204         // ...
 205         \endcode
 206
 207         Instead of declaring \p set_traits type traits we can use option-based syntax with
 208         \p ellen_bintree::make_traits metafunction, for example:
 209         \code
 210         typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo,
 211             typename cds::intrusive::ellen_bintree::make_traits<
 212                 cds::opt::hook< cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > >
 213                 ,cds::intrusive::ellen_bintree::key_extractor< my_key_extractor >
 214                 ,cds::opt::less< my_less >
 215                 ,cds::opt::item_counter< cds::atomicity::item_counter >
 216             >::type
 217         >   set_type2;
 218         \endcode
 219
 220         Functionally, \p set_type and \p set_type2 are equivalent.
 221
 222         <b>Member-hooked tree</b>
 223
 224         Sometimes, we cannot use base hook, for example, when the \p Foo structure is external.
 225         In such case we can use member hook feature.
 226         \code
 227         #include <cds/urcu/general_buffered.h>
 228         #include <cds/intrusive/ellen_bintree_rcu.h>
 229
 230         // Struct Foo is external and its declaration cannot be modified.
 231         struct Foo {
 232             std::string     m_strKey    ;   // The key
 233             //...                           // other non-key data
 234         };
 235
 236         // RCU type we use
 237         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  gpb_rcu;
 238
 239         // Foo wrapper
 240         struct MyFoo
 241         {
 242             Foo     m_foo;
 243             cds::intrusive:ellen_bintree::node< gpb_rcu >   set_hook;   // member hook
 244         };
 245
 246         // Key extractor functor
 247         struct member_key_extractor
 248         {
 249             void operator ()( std::string& key, MyFoo const& src ) const
 250             {
 251                 key = src.m_foo.m_strKey;
 252             }
 253         };
 254
 255         // Less predicate
 256         struct member_less {
 257             bool operator()( MyFoo const& v1, MyFoo const& v2 ) const
 258             { return v1.m_foo.m_strKey < v2.m_foo.m_strKey ; }
 259
 260             bool operator()( MyFoo const& v, std::string const& s ) const
 261             { return v.m_foo.m_strKey < s ; }
 262
 263             bool operator()( std::string const& s, MyFoo const& v ) const
 264             { return s < v.m_foo.m_strKey ; }
 265
 266             // Support comparing std::string and char const *
 267             bool operator()( std::string const& s, char const * p ) const
 268             { return s.compare(p) < 0 ; }
 269
 270             bool operator()( MyFoo const& v, char const * p ) const
 271             { return v.m_foo.m_strKey.compare(p) < 0 ; }
 272
 273             bool operator()( char const * p, std::string const& s ) const
 274             { return s.compare(p) > 0; }
 275
 276             bool operator()( char const * p, MyFoo const& v ) const
 277             { return v.m_foo.m_strKey.compare(p) > 0; }
 278         };
 279
 280         // Tree traits for our member-based set
 281         struct member_set_traits: public cds::intrusive::ellen_bintree::traits
 282         {
 283             cds::intrusive::ellen_bintree::member_hook< offsetof(MyFoo, set_hook), cds::opt::gc<gpb_rcu> > > hook;
 284             typedef member_key_extractor    key_extractor;
 285             typedef member_less             less;
 286             typedef cds::atomicity::item_counter item_counter;
 287         };
 288
 289         // Tree containing MyFoo objects
 290         typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, MyFoo, member_set_traits >   member_set_type;
 291
 292         member_set_type    theMemberSet;
 293         \endcode
 294
 295         <b>Multiple containers</b>
 296
 297         Sometimes we need that our \p Foo struct should be used in several different containers.
 298         Suppose, \p Foo struct has two key fields:
 299         \code
 300         struct Foo {
 301             std::string m_strKey    ;   // string key
 302             int         m_nKey      ;   // int key
 303             //...                       // other non-key data fields
 304         };
 305         \endcode
 306
 307         We want to build two intrusive \p %EllenBinTree sets: one indexed on \p Foo::m_strKey field,
 308         another indexed on \p Foo::m_nKey field. To decide such case we should use a tag option for
 309         tree's hook:
 310         \code
 311         #include <cds/urcu/general_buffered.h>
 312         #include <cds/intrusive/ellen_bintree_rcu.h>
 313
 314         // RCU type we use
 315         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  gpb_rcu;
 316
 317         // Declare tag structs
 318         struct int_tag      ;   // int key tag
 319         struct string_tag   ;   // string key tag
 320
 321         // Foo struct is derived from two ellen_bintree::node class
 322         // with different tags
 323         struct Foo
 324             : public cds::intrusive::ellen_bintree::node< gpb_rcu, cds::opt::tag< string_tag > >
 325             , public cds::intrusive::ellen_bintree::node< gpb_rcu >, cds::opt::tag< int_tag >
 326         {
 327             std::string m_strKey    ;   // string key
 328             int         m_nKey      ;   // int key
 329             //...                       // other non-key data fields
 330         };
 331
 332         // String key extractor functor
 333         struct string_key_extractor
 334         {
 335             void operator ()( std::string& key, Foo const& src ) const
 336             {
 337                 key = src.m_strKey;
 338             }
 339         };
 340
 341         // Int key extractor functor
 342         struct int_key_extractor
 343         {
 344             void operator ()( int& key, Foo const& src ) const
 345             {
 346                 key = src.m_nKey;
 347             }
 348         };
 349
 350         // String less predicate
 351         struct string_less {
 352             bool operator()( Foo const& v1, Foo const& v2 ) const
 353             { return v1.m_strKey < v2.m_strKey ; }
 354
 355             bool operator()( Foo const& v, std::string const& s ) const
 356             { return v.m_strKey < s ; }
 357
 358             bool operator()( std::string const& s, Foo const& v ) const
 359             { return s < v.m_strKey ; }
 360
 361             // Support comparing std::string and char const *
 362             bool operator()( std::string const& s, char const * p ) const
 363             { return s.compare(p) < 0 ; }
 364
 365             bool operator()( Foo const& v, char const * p ) const
 366             { return v.m_strKey.compare(p) < 0 ; }
 367
 368             bool operator()( char const * p, std::string const& s ) const
 369             { return s.compare(p) > 0; }
 370
 371             bool operator()( char const * p, Foo const& v ) const
 372             { return v.m_strKey.compare(p) > 0; }
 373         };
 374
 375         // Int less predicate
 376         struct int_less {
 377             bool operator()( Foo const& v1, Foo const& v2 ) const
 378             { return v1.m_nKey < v2.m_nKey ; }
 379
 380             bool operator()( Foo const& v, int n ) const
 381             { return v.m_nKey < n ; }
 382
 383             bool operator()( int n, Foo const& v ) const
 384             { return n < v.m_nKey ; }
 385         };
 386
 387         // Type traits for string-indexed set
 388         struct string_set_traits: public cds::intrusive::ellen_bintree::traits
 389         {
 390             typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< string_tag > > hook;
 391             typedef string_key_extractor    key_extractor;
 392             typedef string_less             less;
 393             typedef cds::atomicity::item_counter item_counter;
 394         };
 395
 396         // Type traits for int-indexed set
 397         struct int_set_traits: public cds::intrusive::ellen_bintree::traits
 398         {
 399             typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< int_tag > > hook;
 400             typedef int_key_extractor    key_extractor;
 401             typedef int_less             less;
 402             typedef cds::atomicity::item_counter item_counter;
 403         };
 404
 405         // Declare string-indexed set
 406         typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, string_set_traits >   string_set_type;
 407         string_set_type theStringSet;
 408
 409         // Declare int-indexed set
 410         typedef cds::intrusive::EllenBinTree< gpb_rcu, int, Foo, int_set_traits >   int_set_type;
 411         int_set_type    theIntSet;
 412
 413         // Now we can use theStringSet and theIntSet in our program
 414         // ...
 415         \endcode
 416     */
 417     template < class RCU,
 418         typename Key,
 419         typename T,
 420 #ifdef CDS_DOXYGEN_INVOKED
 421         class Traits = ellen_bintree::traits
 422 #else
 423         class Traits
 424 #endif
 425     >
 426     class EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
 427     {
 428     public:
 429         typedef cds::urcu::gc<RCU>  gc;   ///< RCU Garbage collector
 430         typedef Key     key_type;         ///< type of a key stored in internal nodes; key is a part of \p value_type
 431         typedef T       value_type;       ///< type of value stored in the binary tree
 432         typedef Traits  traits;           ///< Traits template parameter
 433
 434         typedef typename traits::hook    hook;      ///< hook type
 435         typedef typename hook::node_type node_type; ///< node type
 436
 437         typedef typename traits::disposer disposer;   ///< leaf node disposer
 438
 439     protected:
 440         //@cond
 441         typedef ellen_bintree::base_node< gc >                      tree_node; ///< Base type of tree node
 442         typedef node_type                                           leaf_node; ///< Leaf node type
 443         typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node; ///< Internal node type
 444         typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc; ///< Update descriptor
 445         typedef typename update_desc::update_ptr                    update_ptr; ///< Marked pointer to update descriptor
 446         //@endcond
 447
 448     public:
 449         typedef cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > exempt_ptr; ///< pointer to extracted node
 450
 451     public:
 452 #   ifdef CDS_DOXYGEN_INVOKED
 453         typedef implementation_defined key_comparator;    ///< key compare functor based on \p Traits::compare and \p Traits::less
 454         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
 455 #   else
 456         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
 457         struct node_traits: public get_node_traits< value_type, node_type, hook>::type
 458         {
 459             static internal_node const& to_internal_node( tree_node const& n )
 460             {
 461                 assert( n.is_internal() );
 462                 return static_cast<internal_node const&>( n );
 463             }
 464
 465             static leaf_node const& to_leaf_node( tree_node const& n )
 466             {
 467                 assert( n.is_leaf() );
 468                 return static_cast<leaf_node const&>( n );
 469             }
 470         };
 471 #   endif
 472
 473         typedef typename traits::item_counter  item_counter;   ///< Item counting policy used
 474         typedef typename traits::memory_model  memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 475         typedef typename traits::stat          stat;           ///< internal statistics type
 476         typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
 477         typedef typename traits::key_extractor      key_extractor;      ///< key extracting functor
 478
 479         typedef typename traits::node_allocator        node_allocator;  ///< Internal node allocator
 480         typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
 481
 482         typedef typename gc::scoped_lock    rcu_lock;   ///< RCU scoped lock
 483
 484         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
 485
 486     protected:
 487         //@cond
 488         typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
 489
 490         typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock >   check_deadlock_policy;
 491
 492         typedef cds::details::Allocator< internal_node, node_allocator >        cxx_node_allocator;
 493         typedef cds::details::Allocator< update_desc, update_desc_allocator >   cxx_update_desc_allocator;
 494
 495         struct search_result {
 496             internal_node *     pGrandParent;
 497             internal_node *     pParent;
 498             leaf_node *         pLeaf;
 499             update_ptr          updParent;
 500             update_ptr          updGrandParent;
 501             bool                bRightLeaf      ; // true if pLeaf is right child of pParent, false otherwise
 502             bool                bRightParent    ; // true if pParent is right child of pGrandParent, false otherwise
 503
 504             search_result()
 505                 :pGrandParent( nullptr )
 506                 , pParent( nullptr )
 507                 , pLeaf( nullptr )
 508                 ,bRightLeaf( false )
 509                 ,bRightParent( false )
 510             {}
 511         };
 512         //@endcond
 513
 514     protected:
 515         //@cond
 516         internal_node       m_Root;     ///< Tree root node (key= Infinite2)
 517         leaf_node           m_LeafInf1;
 518         leaf_node           m_LeafInf2;
 519         //@endcond
 520
 521         item_counter        m_ItemCounter;  ///< item counter
 522         mutable stat        m_Stat;         ///< internal statistics
 523
 524     protected:
 525         //@cond
 526         static void free_leaf_node( value_type * p )
 527         {
 528             disposer()( p );
 529         }
 530
 531         internal_node * alloc_internal_node() const
 532         {
 533             m_Stat.onInternalNodeCreated();
 534             internal_node * pNode = cxx_node_allocator().New();
 535             //pNode->clean();
 536             return pNode;
 537         }
 538
 539         static void free_internal_node( internal_node * pNode )
 540         {
 541             cxx_node_allocator().Delete( pNode );
 542         }
 543
 544         struct internal_node_deleter {
 545             void operator()( internal_node * p) const
 546             {
 547                 free_internal_node( p );
 548             }
 549         };
 550
 551         typedef std::unique_ptr< internal_node, internal_node_deleter>  unique_internal_node_ptr;
 552
 553         update_desc * alloc_update_desc() const
 554         {
 555             m_Stat.onUpdateDescCreated();
 556             return cxx_update_desc_allocator().New();
 557         }
 558
 559         static void free_update_desc( update_desc * pDesc )
 560         {
 561             cxx_update_desc_allocator().Delete( pDesc );
 562         }
 563
 564         class retired_list
 565         {
 566             update_desc *   pUpdateHead;
 567             tree_node *     pNodeHead;
 568
 569         private:
 570             class forward_iterator
 571             {
 572                 update_desc *   m_pUpdate;
 573                 tree_node *     m_pNode;
 574
 575             public:
 576                 forward_iterator( retired_list const& l )
 577                     : m_pUpdate( l.pUpdateHead )
 578                     , m_pNode( l.pNodeHead )
 579                 {}
 580
 581                 forward_iterator()
 582                     : m_pUpdate( nullptr )
 583                     , m_pNode( nullptr )
 584                 {}
 585
 586                 cds::urcu::retired_ptr operator *()
 587                 {
 588                     if ( m_pUpdate ) {
 589                         return cds::urcu::retired_ptr( reinterpret_cast<void *>( m_pUpdate ),
 590                             reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
 591                     }
 592                     if ( m_pNode ) {
 593                         if ( m_pNode->is_leaf() ) {
 594                             return cds::urcu::retired_ptr( reinterpret_cast<void *>( node_traits::to_value_ptr( static_cast<leaf_node *>( m_pNode ))),
 595                                 reinterpret_cast< cds::urcu::free_retired_ptr_func>( free_leaf_node ) );
 596                         }
 597                         else {
 598                             return cds::urcu::retired_ptr( reinterpret_cast<void *>( static_cast<internal_node *>( m_pNode ) ),
 599                                 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_internal_node ) );
 600                         }
 601                     }
 602                     return cds::urcu::retired_ptr( nullptr,
 603                         reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
 604                 }
 605
 606                 void operator ++()
 607                 {
 608                     if ( m_pUpdate ) {
 609                         m_pUpdate = m_pUpdate->pNextRetire;
 610                         return;
 611                     }
 612                     if ( m_pNode )
 613                         m_pNode = m_pNode->m_pNextRetired;
 614                 }
 615
 616                 friend bool operator ==( forward_iterator const& i1, forward_iterator const& i2 )
 617                 {
 618                     return i1.m_pUpdate == i2.m_pUpdate && i1.m_pNode == i2.m_pNode;
 619                 }
 620                 friend bool operator !=( forward_iterator const& i1, forward_iterator const& i2 )
 621                 {
 622                     return !( i1 == i2 );
 623                 }
 624             };
 625
 626         public:
 627             retired_list()
 628                 : pUpdateHead( nullptr )
 629                 , pNodeHead( nullptr )
 630             {}
 631
 632             ~retired_list()
 633             {
 634                 gc::batch_retire( forward_iterator(*this), forward_iterator() );
 635             }
 636
 637             void push( update_desc * p )
 638             {
 639                 p->pNextRetire = pUpdateHead;
 640                 pUpdateHead = p;
 641             }
 642
 643             void push( tree_node * p )
 644             {
 645                 p->m_pNextRetired = pNodeHead;
 646                 pNodeHead = p;
 647             }
 648         };
 649
 650         void retire_node( tree_node * pNode, retired_list& rl ) const
 651         {
 652             if ( pNode->is_leaf() ) {
 653                 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
 654                 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
 655             }
 656             else {
 657                 assert( static_cast<internal_node *>( pNode ) != &m_Root );
 658                 m_Stat.onInternalNodeDeleted();
 659             }
 660             rl.push( pNode );
 661         }
 662
 663         void retire_update_desc( update_desc * p, retired_list& rl, bool bDirect ) const
 664         {
 665             m_Stat.onUpdateDescDeleted();
 666             if ( bDirect )
 667                 free_update_desc( p );
 668             else
 669                 rl.push( p );
 670         }
 671
 672         void make_empty_tree()
 673         {
 674             m_Root.infinite_key( 2 );
 675             m_LeafInf1.infinite_key( 1 );
 676             m_LeafInf2.infinite_key( 2 );
 677             m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
 678             m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
 679         }
 680         //@endcond
 681
 682     public:
 683         /// Default constructor
 684         EllenBinTree()
 685         {
 686             static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
 687             make_empty_tree();
 688         }
 689
 690         /// Clears the tree
 691         ~EllenBinTree()
 692         {
 693             unsafe_clear();
 694         }
 695
 696         /// Inserts new node
 697         /**
 698             The function inserts \p val in the tree if it does not contain
 699             an item with key equal to \p val.
 700
 701             The function applies RCU lock internally.
 702
 703             Returns \p true if \p val is placed into the set, \p false otherwise.
 704         */
 705         bool insert( value_type& val )
 706         {
 707             return insert( val, []( value_type& ) {} );
 708         }
 709
 710         /// Inserts new node
 711         /**
 712             This function is intended for derived non-intrusive containers.
 713
 714             The function allows to split creating of new item into two part:
 715             - create item with key only
 716             - insert new item into the tree
 717             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 718
 719             The functor signature is:
 720             \code
 721                 void func( value_type& val );
 722             \endcode
 723             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 724             \p val no any other changes could be made on this tree's item by concurrent threads.
 725             The user-defined functor is called only if the inserting is success.
 726
 727             RCU \p synchronize method can be called. RCU should not be locked.
 728         */
 729         template <typename Func>
 730         bool insert( value_type& val, Func f )
 731         {
 732             check_deadlock_policy::check();
 733
 734             unique_internal_node_ptr pNewInternal;
 735             retired_list updRetire;
 736
 737             {
 738                 rcu_lock l;
 739
 740                 search_result res;
 741                 for ( ;; ) {
 742                     if ( search( res, val, node_compare() )) {
 743                         if ( pNewInternal.get() )
 744                             m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 745                         m_Stat.onInsertFailed();
 746                         return false;
 747                     }
 748
 749                     if ( res.updParent.bits() != update_desc::Clean )
 750                         help( res.updParent, updRetire );
 751                     else {
 752                         if ( !pNewInternal.get() )
 753                             pNewInternal.reset( alloc_internal_node() );
 754
 755                         if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
 756                             f( val );
 757                             pNewInternal.release()  ;   // internal node is linked into the tree and should not be deleted
 758                             break;
 759                         }
 760                     }
 761
 762                     m_Stat.onInsertRetry();
 763                 }
 764             }
 765
 766             ++m_ItemCounter;
 767             m_Stat.onInsertSuccess();
 768
 769             return true;
 770         }
 771
 772         /// Ensures that the \p val exists in the tree
 773         /**
 774             The operation performs inserting or changing data with lock-free manner.
 775
 776             If the item \p val is not found in the tree, then \p val is inserted into the tree.
 777             Otherwise, the functor \p func is called with item found.
 778             The functor signature is:
 779             \code
 780                 void func( bool bNew, value_type& item, value_type& val );
 781             \endcode
 782             with arguments:
 783             - \p bNew - \p true if the item has been inserted, \p false otherwise
 784             - \p item - item of the tree
 785             - \p val - argument \p val passed into the \p ensure function
 786             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 787             refer to the same thing.
 788
 789             The functor can change non-key fields of the \p item; however, \p func must guarantee
 790             that during changing no any other modifications could be made on this item by concurrent threads.
 791
 792             RCU \p synchronize method can be called. RCU should not be locked.
 793
 794             Returns <tt>std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 795             \p second is \p true if new item has been added or \p false if the item with \p key
 796             already is in the tree.
 797
 798             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 799         */
 800         template <typename Func>
 801         std::pair<bool, bool> ensure( value_type& val, Func func )
 802         {
 803             check_deadlock_policy::check();
 804
 805             unique_internal_node_ptr pNewInternal;
 806             retired_list updRetire;
 807
 808             {
 809                 rcu_lock l;
 810
 811                 search_result res;
 812                 for ( ;; ) {
 813                     if ( search( res, val, node_compare() )) {
 814                         func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
 815                         if ( pNewInternal.get() )
 816                             m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 817                         m_Stat.onEnsureExist();
 818                         return std::make_pair( true, false );
 819                     }
 820
 821                     if ( res.updParent.bits() != update_desc::Clean )
 822                         help( res.updParent, updRetire );
 823                     else {
 824                         if ( !pNewInternal.get() )
 825                             pNewInternal.reset( alloc_internal_node() );
 826
 827                         if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
 828                             func( true, val, val );
 829                             pNewInternal.release()  ;   // internal node is linked into the tree and should not be deleted
 830                             break;
 831                         }
 832                     }
 833                     m_Stat.onEnsureRetry();
 834                 }
 835             }
 836
 837             ++m_ItemCounter;
 838             m_Stat.onEnsureNew();
 839
 840             return std::make_pair( true, true );
 841         }
 842
 843         /// Unlinks the item \p val from the tree
 844         /**
 845             The function searches the item \p val in the tree and unlink it from the tree
 846             if it is found and is equal to \p val.
 847
 848             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 849             and deletes the item found. \p unlink finds an item by key and deletes it
 850             only if \p val is an item of the tree, i.e. the pointer to item found
 851             is equal to <tt> &val </tt>.
 852
 853             RCU \p synchronize method can be called. RCU should not be locked.
 854
 855             The \ref disposer specified in \p Traits class template parameter is called
 856             by garbage collector \p GC asynchronously.
 857
 858             The function returns \p true if success and \p false otherwise.
 859         */
 860         bool unlink( value_type& val )
 861         {
 862             return erase_( val, node_compare(),
 863                 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
 864                 [](value_type const&) {} );
 865         }
 866
 867         /// Deletes the item from the tree
 868         /** \anchor cds_intrusive_EllenBinTree_rcu_erase
 869             The function searches an item with key equal to \p key in the tree,
 870             unlinks it from the tree, and returns \p true.
 871             If the item with key equal to \p key is not found the function return \p false.
 872
 873             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 874
 875             RCU \p synchronize method can be called. RCU should not be locked.
 876         */
 877         template <typename Q>
 878         bool erase( const Q& key )
 879         {
 880             return erase_( key, node_compare(),
 881                 []( Q const&, leaf_node const& ) -> bool { return true; },
 882                 [](value_type const&) {} );
 883         }
 884
 885         /// Delete the item from the tree with comparing functor \p pred
 886         /**
 887             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
 888             but \p pred predicate is used for key comparing.
 889             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 890             "Predicate requirements".
 891             \p pred must imply the same element order as the comparator used for building the tree.
 892         */
 893         template <typename Q, typename Less>
 894         bool erase_with( const Q& key, Less pred )
 895         {
 896             typedef ellen_bintree::details::compare<
 897                 key_type,
 898                 value_type,
 899                 opt::details::make_comparator_from_less<Less>,
 900                 node_traits
 901             > compare_functor;
 902
 903             return erase_( key, compare_functor(),
 904                 []( Q const&, leaf_node const& ) -> bool { return true; },
 905                 [](value_type const&) {} );
 906         }
 907
 908         /// Deletes the item from the tree
 909         /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
 910             The function searches an item with key equal to \p key in the tree,
 911             call \p f functor with item found, unlinks it from the tree, and returns \p true.
 912             The \ref disposer specified in \p Traits class template parameter is called
 913             by garbage collector \p GC asynchronously.
 914
 915             The \p Func interface is
 916             \code
 917             struct functor {
 918                 void operator()( value_type const& item );
 919             };
 920             \endcode
 921             The functor can be passed by reference with <tt>boost:ref</tt>
 922
 923             If the item with key equal to \p key is not found the function return \p false.
 924
 925             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 926
 927             RCU \p synchronize method can be called. RCU should not be locked.
 928         */
 929         template <typename Q, typename Func>
 930         bool erase( Q const& key, Func f )
 931         {
 932             return erase_( key, node_compare(),
 933                 []( Q const&, leaf_node const& ) -> bool { return true; },
 934                 f );
 935         }
 936
 937         /// Delete the item from the tree with comparing functor \p pred
 938         /**
 939             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
 940             but \p pred predicate is used for key comparing.
 941             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 942             "Predicate requirements".
 943             \p pred must imply the same element order as the comparator used for building the tree.
 944         */
 945         template <typename Q, typename Less, typename Func>
 946         bool erase_with( Q const& key, Less pred, Func f )
 947         {
 948             typedef ellen_bintree::details::compare<
 949                 key_type,
 950                 value_type,
 951                 opt::details::make_comparator_from_less<Less>,
 952                 node_traits
 953             > compare_functor;
 954
 955             return erase_( key, compare_functor(),
 956                 []( Q const&, leaf_node const& ) -> bool { return true; },
 957                 f );
 958         }
 959
 960         /// Extracts an item with minimal key from the tree
 961         /**
 962             The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p result parameter.
 963             If the tree is empty the function returns \p false.
 964
 965             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
 966             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 967             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 968             So, the function returns the item with minimum key at the moment of tree traversing.
 969
 970             RCU \p synchronize method can be called. RCU should NOT be locked.
 971             The function does not call the disposer for the item found.
 972             The disposer will be implicitly invoked when \p result object is destroyed or when
 973             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 974             @note Before reusing \p result object you should call its \p release() method.
 975         */
 976         bool extract_min(exempt_ptr& result)
 977         {
 978             return extract_min_(result);
 979         }
 980
 981         /// Extracts an item with maximal key from the tree
 982         /**
 983             The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p result prameter.
 984             If the tree is empty the function returns \p false.
 985
 986             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
 987             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 988             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
 989             So, the function returns the item with maximum key at the moment of tree traversing.
 990
 991             RCU \p synchronize method can be called. RCU should NOT be locked.
 992             The function does not call the disposer for the item found.
 993             The disposer will be implicitly invoked when \p result object is destroyed or when
 994             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 995             @note Before reusing \p result object you should call its \p release() method.
 996         */
 997         bool extract_max(exempt_ptr& result)
 998         {
 999             return extract_max_(result);
1000         }
1001
1002         /// Extracts an item from the tree
1003         /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1004             The function searches an item with key equal to \p key in the tree,
1005             unlinks it, and returns pointer to an item found in \p result parameter.
1006             If the item with the key equal to \p key is not found the function returns \p false.
1007
1008             RCU \p synchronize method can be called. RCU should NOT be locked.
1009             The function does not call the disposer for the item found.
1010             The disposer will be implicitly invoked when \p result object is destroyed or when
1011             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1012             @note Before reusing \p result object you should call its \p release() method.
1013         */
1014         template <typename Q>
1015         bool extract( exempt_ptr& result, Q const& key )
1016         {
1017             return extract_( result, key, node_compare() );
1018         }
1019
1020         /// Extracts an item from the set using \p pred for searching
1021         /**
1022             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_extract "extract(exempt_ptr&, Q const&)"
1023             but \p pred is used for key compare.
1024             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1025             "predicate requirements".
1026             \p pred must imply the same element order as the comparator used for building the tree.
1027         */
1028         template <typename Q, typename Less>
1029         bool extract_with( exempt_ptr& dest,  Q const& key, Less pred )
1030         {
1031             return extract_with_( dest, key, pred );
1032         }
1033
1034         /// Finds the key \p key
1035         /** @anchor cds_intrusive_EllenBinTree_rcu_find_val
1036             The function searches the item with key equal to \p key
1037             and returns \p true if it is found, and \p false otherwise.
1038
1039             Note the hash functor specified for class \p Traits template parameter
1040             should accept a parameter of type \p Q that can be not the same as \p value_type.
1041
1042             The function applies RCU lock internally.
1043         */
1044         template <typename Q>
1045         bool find( Q const& key ) const
1046         {
1047             rcu_lock l;
1048             search_result    res;
1049             if ( search( res, key, node_compare() )) {
1050                 m_Stat.onFindSuccess();
1051                 return true;
1052             }
1053
1054             m_Stat.onFindFailed();
1055             return false;
1056         }
1057
1058         /// Finds the key \p key with comparing functor \p pred
1059         /**
1060             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)"
1061             but \p pred is used for key compare.
1062             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1063             "Predicate requirements".
1064             \p pred must imply the same element order as the comparator used for building the tree.
1065             \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1066         */
1067         template <typename Q, typename Less>
1068         bool find_with( Q const& key, Less pred ) const
1069         {
1070             typedef ellen_bintree::details::compare<
1071                 key_type,
1072                 value_type,
1073                 opt::details::make_comparator_from_less<Less>,
1074                 node_traits
1075             > compare_functor;
1076
1077             rcu_lock l;
1078             search_result    res;
1079             if ( search( res, key, compare_functor() )) {
1080                 m_Stat.onFindSuccess();
1081                 return true;
1082             }
1083             m_Stat.onFindFailed();
1084             return false;
1085         }
1086
1087         /// Finds the key \p key
1088         /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1089             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1090             The interface of \p Func functor is:
1091             \code
1092             struct functor {
1093                 void operator()( value_type& item, Q& key );
1094             };
1095             \endcode
1096             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1097
1098             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1099             that \p item cannot be disposed during functor is executing.
1100             The functor does not serialize simultaneous access to the tree \p item. If such access is
1101             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1102
1103             The function applies RCU lock internally.
1104
1105             The function returns \p true if \p key is found, \p false otherwise.
1106         */
1107         template <typename Q, typename Func>
1108         bool find( Q& key, Func f ) const
1109         {
1110             return find_( key, f );
1111         }
1112
1113         /// Finds the key \p key with comparing functor \p pred
1114         /**
1115             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1116             but \p pred is used for key comparison.
1117             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1118             "Predicate requirements".
1119             \p pred must imply the same element order as the comparator used for building the tree.
1120         */
1121         template <typename Q, typename Less, typename Func>
1122         bool find_with( Q& key, Less pred, Func f ) const
1123         {
1124             return find_with_( key, pred, f );
1125         }
1126
1127         /// Finds \p key and return the item found
1128         /** \anchor cds_intrusive_EllenBinTree_rcu_get
1129             The function searches the item with key equal to \p key and returns the pointer to item found.
1130             If \p key is not found it returns \p nullptr.
1131
1132             RCU should be locked before call the function.
1133             Returned pointer is valid while RCU is locked.
1134         */
1135         template <typename Q>
1136         value_type * get( Q const& key ) const
1137         {
1138             return get_( key, node_compare() );
1139         }
1140
1141         /// Finds \p key with \p pred predicate and return the item found
1142         /**
1143             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1144             but \p pred is used for comparing the keys.
1145
1146             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1147             in any order.
1148             \p pred must imply the same element order as the comparator used for building the tree.
1149         */
1150         template <typename Q, typename Less>
1151         value_type * get_with( Q const& key, Less pred ) const
1152         {
1153             typedef ellen_bintree::details::compare<
1154                 key_type,
1155                 value_type,
1156                 opt::details::make_comparator_from_less<Less>,
1157                 node_traits
1158             > compare_functor;
1159
1160             return get_( key, compare_functor());
1161         }
1162
1163         /// Checks if the tree is empty
1164         bool empty() const
1165         {
1166             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1167         }
1168
1169         /// Clears the tree (thread safe, not atomic)
1170         /**
1171             The function unlink all items from the tree.
1172             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1173             this sequence
1174             \code
1175             set.clear();
1176             assert( set.empty() );
1177             \endcode
1178             the assertion could be raised.
1179
1180             For each leaf the \ref disposer will be called after unlinking.
1181
1182             RCU \p synchronize method can be called. RCU should not be locked.
1183         */
1184         void clear()
1185         {
1186             exempt_ptr ep;
1187             while ( extract_min(ep) )
1188                 ep.release();
1189         }
1190
1191         /// Clears the tree (not thread safe)
1192         /**
1193             This function is not thread safe and may be called only when no other thread deals with the tree.
1194             The function is used in the tree destructor.
1195         */
1196         void unsafe_clear()
1197         {
1198             rcu_lock l;
1199
1200             while ( true ) {
1201                 internal_node * pParent = nullptr;
1202                 internal_node * pGrandParent = nullptr;
1203                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
1204
1205                 // Get leftmost leaf
1206                 while ( pLeaf->is_internal() ) {
1207                     pGrandParent = pParent;
1208                     pParent = static_cast<internal_node *>( pLeaf );
1209                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1210                 }
1211
1212                 if ( pLeaf->infinite_key()) {
1213                     // The tree is empty
1214                     return;
1215                 }
1216
1217                 // Remove leftmost leaf and its parent node
1218                 assert( pGrandParent );
1219                 assert( pParent );
1220                 assert( pLeaf->is_leaf() );
1221
1222                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1223                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
1224                 free_internal_node( pParent );
1225             }
1226         }
1227
1228         /// Returns item count in the tree
1229         /**
1230             Only leaf nodes containing user data are counted.
1231
1232             The value returned depends on item counter type provided by \p Traits template parameter.
1233             If it is \p atomicity::empty_item_counter this function always returns 0.
1234
1235             The function is not suitable for checking the tree emptiness, use \p empty()
1236             member function for that.
1237         */
1238         size_t size() const
1239         {
1240             return m_ItemCounter;
1241         }
1242
1243         /// Returns const reference to internal statistics
1244         stat const& statistics() const
1245         {
1246             return m_Stat;
1247         }
1248
1249         /// Checks internal consistency (not atomic, not thread-safe)
1250         /**
1251             The debugging function to check internal consistency of the tree.
1252         */
1253         bool check_consistency() const
1254         {
1255             return check_consistency( &m_Root );
1256         }
1257
1258     protected:
1259         //@cond
1260
1261         bool check_consistency( internal_node const * pRoot ) const
1262         {
1263             tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1264             tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1265             assert( pLeft );
1266             assert( pRight );
1267
1268             if ( node_compare()( *pLeft, *pRoot ) < 0
1269                 && node_compare()( *pRoot, *pRight ) <= 0
1270                 && node_compare()( *pLeft, *pRight ) < 0 )
1271             {
1272                 bool bRet = true;
1273                 if ( pLeft->is_internal() )
1274                     bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
1275                 assert( bRet );
1276
1277                 if ( bRet && pRight->is_internal() )
1278                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1279                 assert( bRet );
1280
1281                 return bRet;
1282             }
1283             return false;
1284         }
1285
1286         void help( update_ptr pUpdate, retired_list& rl )
1287         {
1288             /*
1289             switch ( pUpdate.bits() ) {
1290                 case update_desc::IFlag:
1291                     help_insert( pUpdate.ptr() );
1292                     m_Stat.onHelpInsert();
1293                     break;
1294                 case update_desc::DFlag:
1295                     //help_delete( pUpdate.ptr(), rl );
1296                     //m_Stat.onHelpDelete();
1297                     break;
1298                 case update_desc::Mark:
1299                     //help_marked( pUpdate.ptr() );
1300                     //m_Stat.onHelpMark();
1301                     break;
1302             }
1303             */
1304         }
1305
1306         void help_insert( update_desc * pOp )
1307         {
1308             assert( gc::is_locked() );
1309
1310             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1311             if ( pOp->iInfo.bRightLeaf ) {
1312                 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1313                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1314             }
1315             else {
1316                 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1317                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1318             }
1319
1320             update_ptr cur( pOp, update_desc::IFlag );
1321             pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1322                       memory_model::memory_order_release, atomics::memory_order_relaxed );
1323         }
1324
1325         bool check_delete_precondition( search_result& res )
1326         {
1327             assert( res.pGrandParent != nullptr );
1328
1329             return
1330                 static_cast<internal_node *>( res.bRightParent
1331                     ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1332                     : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1333                 ) == res.pParent
1334                 &&
1335                 static_cast<leaf_node *>( res.bRightLeaf
1336                     ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1337                     : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1338                 ) == res.pLeaf;
1339         }
1340
1341         bool help_delete( update_desc * pOp, retired_list& rl )
1342         {
1343             assert( gc::is_locked() );
1344
1345             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1346             update_ptr pMark( pOp, update_desc::Mark );
1347             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1348                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1349             {
1350                 help_marked( pOp );
1351                 retire_node( pOp->dInfo.pParent, rl );
1352                 // For extract operations the leaf should NOT be disposed
1353                 if ( pOp->dInfo.bDisposeLeaf )
1354                     retire_node( pOp->dInfo.pLeaf, rl );
1355                 retire_update_desc( pOp, rl, false );
1356
1357                 return true;
1358             }
1359             else if ( pUpdate == pMark ) {
1360                 // some other thread is processing help_marked()
1361                 help_marked( pOp );
1362                 m_Stat.onHelpMark();
1363                 return true;
1364             }
1365             else {
1366                 // pUpdate has been changed by CAS
1367                 help( pUpdate, rl );
1368
1369                 // Undo grandparent dInfo
1370                 update_ptr pDel( pOp, update_desc::DFlag );
1371                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1372                     memory_model::memory_order_release, atomics::memory_order_relaxed ))
1373                 {
1374                     retire_update_desc( pOp, rl, false );
1375                 }
1376                 return false;
1377             }
1378         }
1379
1380         void help_marked( update_desc * pOp )
1381         {
1382             assert( gc::is_locked() );
1383
1384             tree_node * p = pOp->dInfo.pParent;
1385             if ( pOp->dInfo.bRightParent ) {
1386                 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1387                     pOp->dInfo.bRightLeaf
1388                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1389                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1390                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1391             }
1392             else {
1393                 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1394                     pOp->dInfo.bRightLeaf
1395                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1396                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1397                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1398             }
1399
1400             update_ptr upd( pOp, update_desc::DFlag );
1401             pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1402                 memory_model::memory_order_release, atomics::memory_order_relaxed );
1403         }
1404
1405         template <typename KeyValue, typename Compare>
1406         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1407         {
1408             assert( gc::is_locked() );
1409
1410             internal_node * pParent;
1411             internal_node * pGrandParent = nullptr;
1412             tree_node *     pLeaf;
1413             update_ptr      updParent;
1414             update_ptr      updGrandParent;
1415             bool bRightLeaf;
1416             bool bRightParent = false;
1417
1418             int nCmp = 0;
1419
1420         retry:
1421             pParent = nullptr;
1422             pLeaf = const_cast<internal_node *>( &m_Root );
1423             updParent = nullptr;
1424             bRightLeaf = false;
1425             while ( pLeaf->is_internal() ) {
1426                 pGrandParent = pParent;
1427                 pParent = static_cast<internal_node *>( pLeaf );
1428                 bRightParent = bRightLeaf;
1429                 updGrandParent = updParent;
1430                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1431
1432                 switch ( updParent.bits() ) {
1433                     case update_desc::DFlag:
1434                     case update_desc::Mark:
1435                         m_Stat.onSearchRetry();
1436                         goto retry;
1437                 }
1438
1439                 nCmp = cmp( key, *pParent );
1440                 bRightLeaf = nCmp >= 0;
1441                 pLeaf = nCmp < 0 ? pParent->m_pLeft.load( memory_model::memory_order_acquire )
1442                                  : pParent->m_pRight.load( memory_model::memory_order_acquire );
1443             }
1444
1445             assert( pLeaf->is_leaf() );
1446             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1447
1448             res.pGrandParent    = pGrandParent;
1449             res.pParent         = pParent;
1450             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1451             res.updParent       = updParent;
1452             res.updGrandParent  = updGrandParent;
1453             res.bRightParent    = bRightParent;
1454             res.bRightLeaf      = bRightLeaf;
1455
1456             return nCmp == 0;
1457         }
1458
1459         bool search_min( search_result& res ) const
1460         {
1461             assert( gc::is_locked() );
1462
1463             internal_node * pParent;
1464             internal_node * pGrandParent = nullptr;
1465             tree_node *     pLeaf;
1466             update_ptr      updParent;
1467             update_ptr      updGrandParent;
1468
1469         retry:
1470             pParent = nullptr;
1471             pLeaf = const_cast<internal_node *>( &m_Root );
1472             while ( pLeaf->is_internal() ) {
1473                 pGrandParent = pParent;
1474                 pParent = static_cast<internal_node *>( pLeaf );
1475                 updGrandParent = updParent;
1476                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1477
1478                 switch ( updParent.bits() ) {
1479                     case update_desc::DFlag:
1480                     case update_desc::Mark:
1481                         m_Stat.onSearchRetry();
1482                         goto retry;
1483                 }
1484
1485                 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1486             }
1487
1488             if ( pLeaf->infinite_key())
1489                 return false;
1490
1491             res.pGrandParent    = pGrandParent;
1492             res.pParent         = pParent;
1493             assert( pLeaf->is_leaf() );
1494             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1495             res.updParent       = updParent;
1496             res.updGrandParent  = updGrandParent;
1497             res.bRightParent    = false;
1498             res.bRightLeaf      = false;
1499
1500             return true;
1501         }
1502
1503         bool search_max( search_result& res ) const
1504         {
1505             assert( gc::is_locked() );
1506
1507             internal_node * pParent;
1508             internal_node * pGrandParent = nullptr;
1509             tree_node *     pLeaf;
1510             update_ptr      updParent;
1511             update_ptr      updGrandParent;
1512             bool bRightLeaf;
1513             bool bRightParent = false;
1514
1515         retry:
1516             pParent = nullptr;
1517             pLeaf = const_cast<internal_node *>( &m_Root );
1518             bRightLeaf = false;
1519             while ( pLeaf->is_internal() ) {
1520                 pGrandParent = pParent;
1521                 pParent = static_cast<internal_node *>( pLeaf );
1522                 bRightParent = bRightLeaf;
1523                 updGrandParent = updParent;
1524                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1525
1526                 switch ( updParent.bits() ) {
1527                     case update_desc::DFlag:
1528                     case update_desc::Mark:
1529                         m_Stat.onSearchRetry();
1530                         goto retry;
1531                 }
1532
1533                 if ( pParent->infinite_key()) {
1534                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1535                     bRightLeaf = false;
1536                 }
1537                 else {
1538                     pLeaf = pParent->m_pRight.load( memory_model::memory_order_acquire );
1539                     bRightLeaf = true;
1540                 }
1541             }
1542
1543             if ( pLeaf->infinite_key())
1544                 return false;
1545
1546             res.pGrandParent    = pGrandParent;
1547             res.pParent         = pParent;
1548             assert( pLeaf->is_leaf() );
1549             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1550             res.updParent       = updParent;
1551             res.updGrandParent  = updGrandParent;
1552             res.bRightParent    = bRightParent;
1553             res.bRightLeaf      = bRightLeaf;
1554
1555             return true;
1556         }
1557
1558         template <typename Q, typename Compare, typename Equal, typename Func>
1559         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1560         {
1561             check_deadlock_policy::check();
1562
1563             retired_list updRetire;
1564             update_desc * pOp = nullptr;
1565             search_result res;
1566
1567             {
1568                 rcu_lock l;
1569                 for ( ;; ) {
1570                     if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1571                         if ( pOp )
1572                             retire_update_desc( pOp, updRetire, false );
1573                         m_Stat.onEraseFailed();
1574                         return false;
1575                     }
1576
1577                     if ( res.updGrandParent.bits() != update_desc::Clean )
1578                         help( res.updGrandParent, updRetire );
1579                     else if ( res.updParent.bits() != update_desc::Clean )
1580                         help( res.updParent, updRetire );
1581                     else {
1582                         if ( !pOp )
1583                             pOp = alloc_update_desc();
1584                         if ( check_delete_precondition( res ) ) {
1585                             pOp->dInfo.pGrandParent = res.pGrandParent;
1586                             pOp->dInfo.pParent = res.pParent;
1587                             pOp->dInfo.pLeaf = res.pLeaf;
1588                             pOp->dInfo.bDisposeLeaf = true;
1589                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1590                             pOp->dInfo.bRightParent = res.bRightParent;
1591                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1592
1593                             update_ptr updGP( res.updGrandParent.ptr() );
1594                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1595                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1596                             {
1597                                 if ( help_delete( pOp, updRetire )) {
1598                                     // res.pLeaf is not deleted yet since RCU is blocked
1599                                     f( *node_traits::to_value_ptr( res.pLeaf ));
1600                                     break;
1601                                 }
1602                                 pOp = nullptr;
1603                             }
1604                             else {
1605                                 // updGP has been changed by CAS
1606                                 help( updGP, updRetire );
1607                             }
1608                         }
1609                     }
1610
1611                     m_Stat.onEraseRetry();
1612                 }
1613             }
1614
1615             --m_ItemCounter;
1616             m_Stat.onEraseSuccess();
1617             return true;
1618         }
1619
1620         template <typename ExemptPtr, typename Q, typename Less>
1621         bool extract_with_( ExemptPtr& dest,  Q const& val, Less pred )
1622         {
1623             typedef ellen_bintree::details::compare<
1624                 key_type,
1625                 value_type,
1626                 opt::details::make_comparator_from_less<Less>,
1627                 node_traits
1628             > compare_functor;
1629
1630             return extract_( dest, val, compare_functor() );
1631         }
1632
1633         template <typename ExemptPtr, typename Q, typename Compare>
1634         bool extract_( ExemptPtr& ptr, Q const& val, Compare cmp )
1635         {
1636             check_deadlock_policy::check();
1637
1638             retired_list updRetire;
1639             update_desc * pOp = nullptr;
1640             search_result res;
1641
1642             {
1643                 rcu_lock l;
1644                 for ( ;; ) {
1645                     if ( !search( res, val, cmp ) ) {
1646                         if ( pOp )
1647                             retire_update_desc( pOp, updRetire, false );
1648                         m_Stat.onEraseFailed();
1649                         return false;
1650                     }
1651
1652                     if ( res.updGrandParent.bits() != update_desc::Clean )
1653                         help( res.updGrandParent, updRetire );
1654                     else if ( res.updParent.bits() != update_desc::Clean )
1655                         help( res.updParent, updRetire );
1656                     else {
1657                         if ( !pOp )
1658                             pOp = alloc_update_desc();
1659                         if ( check_delete_precondition( res )) {
1660                             pOp->dInfo.pGrandParent = res.pGrandParent;
1661                             pOp->dInfo.pParent = res.pParent;
1662                             pOp->dInfo.pLeaf = res.pLeaf;
1663                             pOp->dInfo.bDisposeLeaf = false;
1664                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1665                             pOp->dInfo.bRightParent = res.bRightParent;
1666                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1667
1668                             update_ptr updGP( res.updGrandParent.ptr() );
1669                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1670                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1671                             {
1672                                 if ( help_delete( pOp, updRetire )) {
1673                                     ptr = node_traits::to_value_ptr( res.pLeaf );
1674                                     break;
1675                                 }
1676                                 pOp = nullptr;
1677                             }
1678                             else {
1679                                 // updGP has been changed by CAS
1680                                 help( updGP, updRetire );
1681                             }
1682                         }
1683                     }
1684
1685                     m_Stat.onEraseRetry();
1686                 }
1687             }
1688
1689             --m_ItemCounter;
1690             m_Stat.onEraseSuccess();
1691             return true;
1692         }
1693
1694
1695         template <typename ExemptPtr>
1696         bool extract_max_( ExemptPtr& result )
1697         {
1698             check_deadlock_policy::check();
1699
1700             retired_list updRetire;
1701             update_desc * pOp = nullptr;
1702             search_result res;
1703
1704             {
1705                 rcu_lock l;
1706                 for ( ;; ) {
1707                     if ( !search_max( res )) {
1708                         // Tree is empty
1709                         if ( pOp )
1710                             retire_update_desc( pOp, updRetire, false );
1711                         m_Stat.onExtractMaxFailed();
1712                         return false;
1713                     }
1714
1715                     if ( res.updGrandParent.bits() != update_desc::Clean )
1716                         help( res.updGrandParent, updRetire );
1717                     else if ( res.updParent.bits() != update_desc::Clean )
1718                         help( res.updParent, updRetire );
1719                     else {
1720                         if ( !pOp )
1721                             pOp = alloc_update_desc();
1722                         if ( check_delete_precondition( res ) ) {
1723                             pOp->dInfo.pGrandParent = res.pGrandParent;
1724                             pOp->dInfo.pParent = res.pParent;
1725                             pOp->dInfo.pLeaf = res.pLeaf;
1726                             pOp->dInfo.bDisposeLeaf = false;
1727                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1728                             pOp->dInfo.bRightParent = res.bRightParent;
1729                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1730
1731                             update_ptr updGP( res.updGrandParent.ptr() );
1732                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1733                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1734                             {
1735                                 if ( help_delete( pOp, updRetire )) {
1736                                     result = node_traits::to_value_ptr( res.pLeaf );
1737                                     break;
1738                                 }
1739                                 pOp = nullptr;
1740                             }
1741                             else {
1742                                 // updGP has been changed by CAS
1743                                 help( updGP, updRetire );
1744                             }
1745                         }
1746                     }
1747                     m_Stat.onExtractMaxRetry();
1748                 }
1749             }
1750
1751             --m_ItemCounter;
1752             m_Stat.onExtractMaxSuccess();
1753             return true;
1754         }
1755
1756         template <typename ExemptPtr>
1757         bool extract_min_(ExemptPtr& result)
1758         {
1759             check_deadlock_policy::check();
1760
1761             retired_list updRetire;
1762             update_desc * pOp = nullptr;
1763             search_result res;
1764
1765             {
1766                 rcu_lock l;
1767                 for ( ;; ) {
1768                     if ( !search_min( res )) {
1769                         // Tree is empty
1770                         if ( pOp )
1771                             retire_update_desc( pOp, updRetire, false );
1772                         m_Stat.onExtractMinFailed();
1773                         return false;
1774                     }
1775
1776                     if ( res.updGrandParent.bits() != update_desc::Clean )
1777                         help( res.updGrandParent, updRetire );
1778                     else if ( res.updParent.bits() != update_desc::Clean )
1779                         help( res.updParent, updRetire );
1780                     else {
1781                         if ( !pOp )
1782                             pOp = alloc_update_desc();
1783                         if ( check_delete_precondition( res ) ) {
1784                             pOp->dInfo.pGrandParent = res.pGrandParent;
1785                             pOp->dInfo.pParent = res.pParent;
1786                             pOp->dInfo.pLeaf = res.pLeaf;
1787                             pOp->dInfo.bDisposeLeaf = false;
1788                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1789                             pOp->dInfo.bRightParent = res.bRightParent;
1790                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1791
1792                             update_ptr updGP( res.updGrandParent.ptr() );
1793                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1794                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1795                             {
1796                                 if ( help_delete( pOp, updRetire )) {
1797                                     result = node_traits::to_value_ptr( res.pLeaf );
1798                                     break;
1799                                 }
1800                                 pOp = nullptr;
1801                             }
1802                             else {
1803                                 // updGP has been changed by CAS
1804                                 help( updGP, updRetire );
1805                             }
1806                         }
1807                     }
1808
1809                     m_Stat.onExtractMinRetry();
1810                 }
1811             }
1812
1813             --m_ItemCounter;
1814             m_Stat.onExtractMinSuccess();
1815             return true;
1816         }
1817
1818         template <typename Q, typename Less, typename Func>
1819         bool find_with_( Q& val, Less pred, Func f ) const
1820         {
1821             typedef ellen_bintree::details::compare<
1822                 key_type,
1823                 value_type,
1824                 opt::details::make_comparator_from_less<Less>,
1825                 node_traits
1826             > compare_functor;
1827
1828             rcu_lock l;
1829             search_result    res;
1830             if ( search( res, val, compare_functor() )) {
1831                 assert( res.pLeaf );
1832                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1833
1834                 m_Stat.onFindSuccess();
1835                 return true;
1836             }
1837
1838             m_Stat.onFindFailed();
1839             return false;
1840         }
1841
1842         template <typename Q, typename Func>
1843         bool find_( Q& key, Func f ) const
1844         {
1845             rcu_lock l;
1846             search_result    res;
1847             if ( search( res, key, node_compare() )) {
1848                 assert( res.pLeaf );
1849                 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1850
1851                 m_Stat.onFindSuccess();
1852                 return true;
1853             }
1854
1855             m_Stat.onFindFailed();
1856             return false;
1857         }
1858
1859         template <typename Q, typename Compare>
1860         value_type * get_( Q const& key, Compare cmp ) const
1861         {
1862             assert( gc::is_locked());
1863
1864             search_result    res;
1865             if ( search( res, key, cmp )) {
1866                 m_Stat.onFindSuccess();
1867                 return node_traits::to_value_ptr( res.pLeaf );
1868             }
1869
1870             m_Stat.onFindFailed();
1871             return nullptr;
1872         }
1873
1874
1875         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1876         {
1877             assert( gc::is_locked() );
1878             assert( res.updParent.bits() == update_desc::Clean );
1879
1880             // check search result
1881             if ( static_cast<leaf_node *>( res.bRightLeaf
1882                 ? res.pParent->m_pRight.load( memory_model::memory_order_relaxed )
1883                 : res.pParent->m_pLeft.load( memory_model::memory_order_relaxed ) ) == res.pLeaf )
1884             {
1885                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1886
1887                 int nCmp = node_compare()( val, *res.pLeaf );
1888                 if ( nCmp < 0 ) {
1889                     if ( res.pGrandParent ) {
1890                         pNewInternal->infinite_key( 0 );
1891                         key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1892                         assert( !res.pLeaf->infinite_key() );
1893                     }
1894                     else {
1895                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1896                         pNewInternal->infinite_key( 1 );
1897                     }
1898                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1899                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1900                 }
1901                 else {
1902                     assert( !res.pLeaf->is_internal() );
1903                     pNewInternal->infinite_key( 0 );
1904
1905                     key_extractor()( pNewInternal->m_Key, val );
1906                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1907                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1908                     assert( !res.pLeaf->infinite_key());
1909                 }
1910
1911                 update_desc * pOp = alloc_update_desc();
1912
1913                 pOp->iInfo.pParent = res.pParent;
1914                 pOp->iInfo.pNew = pNewInternal;
1915                 pOp->iInfo.pLeaf = res.pLeaf;
1916                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1917
1918                 update_ptr updCur( res.updParent.ptr() );
1919                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1920                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1921                 {
1922                     // do insert
1923                     help_insert( pOp );
1924                     retire_update_desc( pOp, updRetire, false );
1925                     return true;
1926                 }
1927                 else {
1928                     // updCur has been updated by CAS
1929                     help( updCur, updRetire );
1930                     retire_update_desc( pOp, updRetire, true );
1931                 }
1932             }
1933             return false;
1934         }
1935
1936         //@endcond
1937     };
1938
1939 }} // namespace cds::intrusive
1940
1941 #endif  // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H