cds/intrusive/ellen_bintree_rcu.h

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