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     protected:
 442         //@cond
 443         typedef ellen_bintree::base_node< gc >                      tree_node; ///< Base type of tree node
 444         typedef node_type                                           leaf_node; ///< Leaf node type
 445         typedef ellen_bintree::internal_node< key_type, leaf_node > internal_node; ///< Internal node type
 446         typedef ellen_bintree::update_desc< leaf_node, internal_node> update_desc; ///< Update descriptor
 447         typedef typename update_desc::update_ptr                    update_ptr; ///< Marked pointer to update descriptor
 448         //@endcond
 449
 450     public:
 451         using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >; ///< pointer to extracted node
 452
 453     public:
 454 #   ifdef CDS_DOXYGEN_INVOKED
 455         typedef implementation_defined key_comparator;    ///< key compare functor based on \p Traits::compare and \p Traits::less
 456         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< Node traits
 457 #   else
 458         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
 459         struct node_traits: public get_node_traits< value_type, node_type, hook>::type
 460         {
 461             static internal_node const& to_internal_node( tree_node const& n )
 462             {
 463                 assert( n.is_internal() );
 464                 return static_cast<internal_node const&>( n );
 465             }
 466
 467             static leaf_node const& to_leaf_node( tree_node const& n )
 468             {
 469                 assert( n.is_leaf() );
 470                 return static_cast<leaf_node const&>( n );
 471             }
 472         };
 473 #   endif
 474
 475         typedef typename traits::item_counter  item_counter;   ///< Item counting policy used
 476         typedef typename traits::memory_model  memory_model;   ///< Memory ordering. See \p cds::opt::memory_model option
 477         typedef typename traits::stat          stat;           ///< internal statistics type
 478         typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
 479         typedef typename traits::key_extractor      key_extractor;      ///< key extracting functor
 480
 481         typedef typename traits::node_allocator        node_allocator;  ///< Internal node allocator
 482         typedef typename traits::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
 483
 484         typedef typename gc::scoped_lock    rcu_lock;   ///< RCU scoped lock
 485
 486         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
 487
 488     protected:
 489         //@cond
 490         typedef ellen_bintree::details::compare< key_type, value_type, key_comparator, node_traits > node_compare;
 491
 492         typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock >   check_deadlock_policy;
 493
 494         typedef cds::details::Allocator< internal_node, node_allocator >        cxx_node_allocator;
 495         typedef cds::details::Allocator< update_desc, update_desc_allocator >   cxx_update_desc_allocator;
 496
 497         struct search_result {
 498             internal_node *     pGrandParent;
 499             internal_node *     pParent;
 500             leaf_node *         pLeaf;
 501             update_ptr          updParent;
 502             update_ptr          updGrandParent;
 503             bool                bRightLeaf      ; // true if pLeaf is right child of pParent, false otherwise
 504             bool                bRightParent    ; // true if pParent is right child of pGrandParent, false otherwise
 505
 506             search_result()
 507                 :pGrandParent( nullptr )
 508                 , pParent( nullptr )
 509                 , pLeaf( nullptr )
 510                 ,bRightLeaf( false )
 511                 ,bRightParent( false )
 512             {}
 513         };
 514         //@endcond
 515
 516     protected:
 517         //@cond
 518         internal_node       m_Root;     ///< Tree root node (key= Infinite2)
 519         leaf_node           m_LeafInf1;
 520         leaf_node           m_LeafInf2;
 521         //@endcond
 522
 523         item_counter        m_ItemCounter;  ///< item counter
 524         mutable stat        m_Stat;         ///< internal statistics
 525
 526     protected:
 527         //@cond
 528         static void free_leaf_node( value_type * p )
 529         {
 530             disposer()( p );
 531         }
 532
 533         internal_node * alloc_internal_node() const
 534         {
 535             m_Stat.onInternalNodeCreated();
 536             internal_node * pNode = cxx_node_allocator().New();
 537             //pNode->clean();
 538             return pNode;
 539         }
 540
 541         static void free_internal_node( internal_node * pNode )
 542         {
 543             cxx_node_allocator().Delete( pNode );
 544         }
 545
 546         struct internal_node_deleter {
 547             void operator()( internal_node * p) const
 548             {
 549                 free_internal_node( p );
 550             }
 551         };
 552
 553         typedef std::unique_ptr< internal_node, internal_node_deleter>  unique_internal_node_ptr;
 554
 555         update_desc * alloc_update_desc() const
 556         {
 557             m_Stat.onUpdateDescCreated();
 558             return cxx_update_desc_allocator().New();
 559         }
 560
 561         static void free_update_desc( update_desc * pDesc )
 562         {
 563             cxx_update_desc_allocator().Delete( pDesc );
 564         }
 565
 566         class retired_list
 567         {
 568             update_desc *   pUpdateHead;
 569             tree_node *     pNodeHead;
 570
 571         private:
 572             class forward_iterator
 573             {
 574                 update_desc *   m_pUpdate;
 575                 tree_node *     m_pNode;
 576
 577             public:
 578                 forward_iterator( retired_list const& l )
 579                     : m_pUpdate( l.pUpdateHead )
 580                     , m_pNode( l.pNodeHead )
 581                 {}
 582
 583                 forward_iterator()
 584                     : m_pUpdate( nullptr )
 585                     , m_pNode( nullptr )
 586                 {}
 587
 588                 cds::urcu::retired_ptr operator *()
 589                 {
 590                     if ( m_pUpdate ) {
 591                         return cds::urcu::retired_ptr( reinterpret_cast<void *>( m_pUpdate ),
 592                             reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
 593                     }
 594                     if ( m_pNode ) {
 595                         if ( m_pNode->is_leaf() ) {
 596                             return cds::urcu::retired_ptr( reinterpret_cast<void *>( node_traits::to_value_ptr( static_cast<leaf_node *>( m_pNode ))),
 597                                 reinterpret_cast< cds::urcu::free_retired_ptr_func>( free_leaf_node ) );
 598                         }
 599                         else {
 600                             return cds::urcu::retired_ptr( reinterpret_cast<void *>( static_cast<internal_node *>( m_pNode ) ),
 601                                 reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_internal_node ) );
 602                         }
 603                     }
 604                     return cds::urcu::retired_ptr( nullptr,
 605                         reinterpret_cast<cds::urcu::free_retired_ptr_func>( free_update_desc ) );
 606                 }
 607
 608                 void operator ++()
 609                 {
 610                     if ( m_pUpdate ) {
 611                         m_pUpdate = m_pUpdate->pNextRetire;
 612                         return;
 613                     }
 614                     if ( m_pNode )
 615                         m_pNode = m_pNode->m_pNextRetired;
 616                 }
 617
 618                 friend bool operator ==( forward_iterator const& i1, forward_iterator const& i2 )
 619                 {
 620                     return i1.m_pUpdate == i2.m_pUpdate && i1.m_pNode == i2.m_pNode;
 621                 }
 622                 friend bool operator !=( forward_iterator const& i1, forward_iterator const& i2 )
 623                 {
 624                     return !( i1 == i2 );
 625                 }
 626             };
 627
 628         public:
 629             retired_list()
 630                 : pUpdateHead( nullptr )
 631                 , pNodeHead( nullptr )
 632             {}
 633
 634             ~retired_list()
 635             {
 636                 gc::batch_retire( forward_iterator(*this), forward_iterator() );
 637             }
 638
 639             void push( update_desc * p )
 640             {
 641                 p->pNextRetire = pUpdateHead;
 642                 pUpdateHead = p;
 643             }
 644
 645             void push( tree_node * p )
 646             {
 647                 p->m_pNextRetired = pNodeHead;
 648                 pNodeHead = p;
 649             }
 650         };
 651
 652         void retire_node( tree_node * pNode, retired_list& rl ) const
 653         {
 654             if ( pNode->is_leaf() ) {
 655                 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
 656                 assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
 657             }
 658             else {
 659                 assert( static_cast<internal_node *>( pNode ) != &m_Root );
 660                 m_Stat.onInternalNodeDeleted();
 661             }
 662             rl.push( pNode );
 663         }
 664
 665         void retire_update_desc( update_desc * p, retired_list& rl, bool bDirect ) const
 666         {
 667             m_Stat.onUpdateDescDeleted();
 668             if ( bDirect )
 669                 free_update_desc( p );
 670             else
 671                 rl.push( p );
 672         }
 673
 674         void make_empty_tree()
 675         {
 676             m_Root.infinite_key( 2 );
 677             m_LeafInf1.infinite_key( 1 );
 678             m_LeafInf2.infinite_key( 2 );
 679             m_Root.m_pLeft.store( &m_LeafInf1, memory_model::memory_order_relaxed );
 680             m_Root.m_pRight.store( &m_LeafInf2, memory_model::memory_order_release );
 681         }
 682         //@endcond
 683
 684     public:
 685         /// Default constructor
 686         EllenBinTree()
 687         {
 688             static_assert( !std::is_same< key_extractor, opt::none >::value, "The key extractor option must be specified" );
 689             make_empty_tree();
 690         }
 691
 692         /// Clears the tree
 693         ~EllenBinTree()
 694         {
 695             unsafe_clear();
 696         }
 697
 698         /// Inserts new node
 699         /**
 700             The function inserts \p val in the tree if it does not contain
 701             an item with key equal to \p val.
 702
 703             The function applies RCU lock internally.
 704
 705             Returns \p true if \p val is placed into the set, \p false otherwise.
 706         */
 707         bool insert( value_type& val )
 708         {
 709             return insert( val, []( value_type& ) {} );
 710         }
 711
 712         /// Inserts new node
 713         /**
 714             This function is intended for derived non-intrusive containers.
 715
 716             The function allows to split creating of new item into two part:
 717             - create item with key only
 718             - insert new item into the tree
 719             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 720
 721             The functor signature is:
 722             \code
 723                 void func( value_type& val );
 724             \endcode
 725             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 726             \p val no any other changes could be made on this tree's item by concurrent threads.
 727             The user-defined functor is called only if the inserting is success.
 728
 729             RCU \p synchronize method can be called. RCU should not be locked.
 730         */
 731         template <typename Func>
 732         bool insert( value_type& val, Func f )
 733         {
 734             check_deadlock_policy::check();
 735
 736             unique_internal_node_ptr pNewInternal;
 737             retired_list updRetire;
 738             back_off bkoff;
 739
 740             {
 741                 rcu_lock l;
 742
 743                 search_result res;
 744                 for ( ;; ) {
 745                     if ( search( res, val, node_compare() )) {
 746                         if ( pNewInternal.get() )
 747                             m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 748                         m_Stat.onInsertFailed();
 749                         return false;
 750                     }
 751
 752                     if ( res.updParent.bits() != update_desc::Clean )
 753                         help( res.updParent, updRetire );
 754                     else {
 755                         if ( !pNewInternal.get() )
 756                             pNewInternal.reset( alloc_internal_node() );
 757
 758                         if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
 759                             f( val );
 760                             pNewInternal.release()  ;   // internal node is linked into the tree and should not be deleted
 761                             break;
 762                         }
 763                     }
 764
 765                     bkoff();
 766                     m_Stat.onInsertRetry();
 767                 }
 768             }
 769
 770             ++m_ItemCounter;
 771             m_Stat.onInsertSuccess();
 772
 773             return true;
 774         }
 775
 776         /// Ensures that the \p val exists in the tree
 777         /**
 778             The operation performs inserting or changing data with lock-free manner.
 779
 780             If the item \p val is not found in the tree, then \p val is inserted into the tree.
 781             Otherwise, the functor \p func is called with item found.
 782             The functor signature is:
 783             \code
 784                 void func( bool bNew, value_type& item, value_type& val );
 785             \endcode
 786             with arguments:
 787             - \p bNew - \p true if the item has been inserted, \p false otherwise
 788             - \p item - item of the tree
 789             - \p val - argument \p val passed into the \p ensure function
 790             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 791             refer to the same thing.
 792
 793             The functor can change non-key fields of the \p item; however, \p func must guarantee
 794             that during changing no any other modifications could be made on this item by concurrent threads.
 795
 796             RCU \p synchronize method can be called. RCU should not be locked.
 797
 798             Returns <tt>std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 799             \p second is \p true if new item has been added or \p false if the item with \p key
 800             already is in the tree.
 801
 802             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 803         */
 804         template <typename Func>
 805         std::pair<bool, bool> ensure( value_type& val, Func func )
 806         {
 807             check_deadlock_policy::check();
 808
 809             unique_internal_node_ptr pNewInternal;
 810             retired_list updRetire;
 811             back_off bkoff;
 812
 813             {
 814                 rcu_lock l;
 815
 816                 search_result res;
 817                 for ( ;; ) {
 818                     if ( search( res, val, node_compare() )) {
 819                         func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
 820                         if ( pNewInternal.get() )
 821                             m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 822                         m_Stat.onEnsureExist();
 823                         return std::make_pair( true, false );
 824                     }
 825
 826                     if ( res.updParent.bits() != update_desc::Clean )
 827                         help( res.updParent, updRetire );
 828                     else {
 829                         if ( !pNewInternal.get() )
 830                             pNewInternal.reset( alloc_internal_node() );
 831
 832                         if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
 833                             func( true, val, val );
 834                             pNewInternal.release()  ;   // internal node is linked into the tree and should not be deleted
 835                             break;
 836                         }
 837                     }
 838
 839                     bkoff();
 840                     m_Stat.onEnsureRetry();
 841                 }
 842             }
 843
 844             ++m_ItemCounter;
 845             m_Stat.onEnsureNew();
 846
 847             return std::make_pair( true, true );
 848         }
 849
 850         /// Unlinks the item \p val from the tree
 851         /**
 852             The function searches the item \p val in the tree and unlink it from the tree
 853             if it is found and is equal to \p val.
 854
 855             Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
 856             and deletes the item found. \p %unlink() finds an item by key and deletes it
 857             only if \p val is an item of the tree, i.e. the pointer to item found
 858             is equal to <tt> &val </tt>.
 859
 860             RCU \p synchronize method can be called. RCU should not be locked.
 861
 862             The \ref disposer specified in \p Traits class template parameter is called
 863             by garbage collector \p GC asynchronously.
 864
 865             The function returns \p true if success and \p false otherwise.
 866         */
 867         bool unlink( value_type& val )
 868         {
 869             return erase_( val, node_compare(),
 870                 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
 871                 [](value_type const&) {} );
 872         }
 873
 874         /// Deletes the item from the tree
 875         /** \anchor cds_intrusive_EllenBinTree_rcu_erase
 876             The function searches an item with key equal to \p key in the tree,
 877             unlinks it from the tree, and returns \p true.
 878             If the item with key equal to \p key is not found the function return \p false.
 879
 880             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 881
 882             RCU \p synchronize method can be called. RCU should not be locked.
 883         */
 884         template <typename Q>
 885         bool erase( const Q& key )
 886         {
 887             return erase_( key, node_compare(),
 888                 []( Q const&, leaf_node const& ) -> bool { return true; },
 889                 [](value_type const&) {} );
 890         }
 891
 892         /// Delete the item from the tree with comparing functor \p pred
 893         /**
 894             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
 895             but \p pred predicate is used for key comparing.
 896             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 897             "Predicate requirements".
 898             \p pred must imply the same element order as the comparator used for building the tree.
 899         */
 900         template <typename Q, typename Less>
 901         bool erase_with( const Q& key, Less pred )
 902         {
 903             CDS_UNUSED( pred );
 904             typedef ellen_bintree::details::compare<
 905                 key_type,
 906                 value_type,
 907                 opt::details::make_comparator_from_less<Less>,
 908                 node_traits
 909             > compare_functor;
 910
 911             return erase_( key, compare_functor(),
 912                 []( Q const&, leaf_node const& ) -> bool { return true; },
 913                 [](value_type const&) {} );
 914         }
 915
 916         /// Deletes the item from the tree
 917         /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
 918             The function searches an item with key equal to \p key in the tree,
 919             call \p f functor with item found, unlinks it from the tree, and returns \p true.
 920             The \ref disposer specified in \p Traits class template parameter is called
 921             by garbage collector \p GC asynchronously.
 922
 923             The \p Func interface is
 924             \code
 925             struct functor {
 926                 void operator()( value_type const& item );
 927             };
 928             \endcode
 929
 930             If the item with key equal to \p key is not found the function return \p false.
 931
 932             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 933
 934             RCU \p synchronize method can be called. RCU should not be locked.
 935         */
 936         template <typename Q, typename Func>
 937         bool erase( Q const& key, Func f )
 938         {
 939             return erase_( key, node_compare(),
 940                 []( Q const&, leaf_node const& ) -> bool { return true; },
 941                 f );
 942         }
 943
 944         /// Delete the item from the tree with comparing functor \p pred
 945         /**
 946             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
 947             but \p pred predicate is used for key comparing.
 948             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 949             "Predicate requirements".
 950             \p pred must imply the same element order as the comparator used for building the tree.
 951         */
 952         template <typename Q, typename Less, typename Func>
 953         bool erase_with( Q const& key, Less pred, Func f )
 954         {
 955             CDS_UNUSED( pred );
 956             typedef ellen_bintree::details::compare<
 957                 key_type,
 958                 value_type,
 959                 opt::details::make_comparator_from_less<Less>,
 960                 node_traits
 961             > compare_functor;
 962
 963             return erase_( key, compare_functor(),
 964                 []( Q const&, leaf_node const& ) -> bool { return true; },
 965                 f );
 966         }
 967
 968         /// Extracts an item with minimal key from the tree
 969         /**
 970             The function searches an item with minimal key, unlinks it, and returns
 971             \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
 972             If the tree is empty the function returns empty \p exempt_ptr.
 973
 974             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
 975             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 976             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 977             So, the function returns the item with minimum key at the moment of tree traversing.
 978
 979             RCU \p synchronize method can be called. RCU should NOT be locked.
 980             The function does not call the disposer for the item found.
 981             The disposer will be implicitly invoked when the returned object is destroyed or when
 982             its \p release() member function is called.
 983         */
 984         exempt_ptr extract_min()
 985         {
 986             return exempt_ptr( extract_min_() );
 987         }
 988
 989         /// Extracts an item with maximal key from the tree
 990         /**
 991             The function searches an item with maximal key, unlinks it, and returns
 992             \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
 993             If the tree is empty the function returns empty \p exempt_ptr.
 994
 995             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
 996             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 997             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
 998             So, the function returns the item with maximum key at the moment of tree traversing.
 999
1000             RCU \p synchronize method can be called. RCU should NOT be locked.
1001             The function does not call the disposer for the item found.
1002             The disposer will be implicitly invoked when the returned object is destroyed or when
1003             its \p release() member function is called.
1004         */
1005         exempt_ptr extract_max()
1006         {
1007             return exempt_ptr( extract_max_() );
1008         }
1009
1010         /// Extracts an item from the tree
1011         /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1012             The function searches an item with key equal to \p key in the tree,
1013             unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
1014             If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr.
1015
1016             RCU \p synchronize method can be called. RCU should NOT be locked.
1017             The function does not call the disposer for the item found.
1018             The disposer will be implicitly invoked when the returned object is destroyed or when
1019             its \p release() member function is called.
1020         */
1021         template <typename Q>
1022         exempt_ptr extract( Q const& key )
1023         {
1024             return exempt_ptr( extract_( key, node_compare() ));
1025         }
1026
1027         /// Extracts an item from the set using \p pred for searching
1028         /**
1029             The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
1030             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1031             "predicate requirements".
1032             \p pred must imply the same element order as the comparator used for building the tree.
1033         */
1034         template <typename Q, typename Less>
1035         exempt_ptr extract_with( Q const& key, Less pred )
1036         {
1037             return exempt_ptr( extract_with_( key, pred ));
1038         }
1039
1040         /// Finds the key \p key
1041         /** @anchor cds_intrusive_EllenBinTree_rcu_find_val
1042             The function searches the item with key equal to \p key
1043             and returns \p true if it is found, and \p false otherwise.
1044
1045             Note the hash functor specified for class \p Traits template parameter
1046             should accept a parameter of type \p Q that can be not the same as \p value_type.
1047
1048             The function applies RCU lock internally.
1049         */
1050         template <typename Q>
1051         bool find( Q const& key ) const
1052         {
1053             rcu_lock l;
1054             search_result    res;
1055             if ( search( res, key, node_compare() )) {
1056                 m_Stat.onFindSuccess();
1057                 return true;
1058             }
1059
1060             m_Stat.onFindFailed();
1061             return false;
1062         }
1063
1064         /// Finds the key \p key with comparing functor \p pred
1065         /**
1066             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)"
1067             but \p pred is used for key compare.
1068             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1069             "Predicate requirements".
1070             \p pred must imply the same element order as the comparator used for building the tree.
1071             \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1072         */
1073         template <typename Q, typename Less>
1074         bool find_with( Q const& key, Less pred ) const
1075         {
1076             CDS_UNUSED( pred );
1077             typedef ellen_bintree::details::compare<
1078                 key_type,
1079                 value_type,
1080                 opt::details::make_comparator_from_less<Less>,
1081                 node_traits
1082             > compare_functor;
1083
1084             rcu_lock l;
1085             search_result    res;
1086             if ( search( res, key, compare_functor() )) {
1087                 m_Stat.onFindSuccess();
1088                 return true;
1089             }
1090             m_Stat.onFindFailed();
1091             return false;
1092         }
1093
1094         /// Finds the key \p key
1095         /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1096             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1097             The interface of \p Func functor is:
1098             \code
1099             struct functor {
1100                 void operator()( value_type& item, Q& key );
1101             };
1102             \endcode
1103             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1104
1105             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1106             that \p item cannot be disposed during functor is executing.
1107             The functor does not serialize simultaneous access to the tree \p item. If such access is
1108             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1109
1110             The function applies RCU lock internally.
1111
1112             The function returns \p true if \p key is found, \p false otherwise.
1113         */
1114         template <typename Q, typename Func>
1115         bool find( Q& key, Func f ) const
1116         {
1117             return find_( key, f );
1118         }
1119         //@cond
1120         template <typename Q, typename Func>
1121         bool find( Q const& key, Func f ) const
1122         {
1123             return find_( key, f );
1124         }
1125         //@endcond
1126
1127         /// Finds the key \p key with comparing functor \p pred
1128         /**
1129             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1130             but \p pred is used for key comparison.
1131             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1132             "Predicate requirements".
1133             \p pred must imply the same element order as the comparator used for building the tree.
1134         */
1135         template <typename Q, typename Less, typename Func>
1136         bool find_with( Q& key, Less pred, Func f ) const
1137         {
1138             return find_with_( key, pred, f );
1139         }
1140         //@cond
1141         template <typename Q, typename Less, typename Func>
1142         bool find_with( Q const& key, Less pred, Func f ) const
1143         {
1144             return find_with_( key, pred, f );
1145         }
1146         //@endcond
1147
1148         /// Finds \p key and return the item found
1149         /** \anchor cds_intrusive_EllenBinTree_rcu_get
1150             The function searches the item with key equal to \p key and returns the pointer to item found.
1151             If \p key is not found it returns \p nullptr.
1152
1153             RCU should be locked before call the function.
1154             Returned pointer is valid while RCU is locked.
1155         */
1156         template <typename Q>
1157         value_type * get( Q const& key ) const
1158         {
1159             return get_( key, node_compare() );
1160         }
1161
1162         /// Finds \p key with \p pred predicate and return the item found
1163         /**
1164             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1165             but \p pred is used for comparing the keys.
1166
1167             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1168             in any order.
1169             \p pred must imply the same element order as the comparator used for building the tree.
1170         */
1171         template <typename Q, typename Less>
1172         value_type * get_with( Q const& key, Less pred ) const
1173         {
1174             CDS_UNUSED( pred );
1175             typedef ellen_bintree::details::compare<
1176                 key_type,
1177                 value_type,
1178                 opt::details::make_comparator_from_less<Less>,
1179                 node_traits
1180             > compare_functor;
1181
1182             return get_( key, compare_functor());
1183         }
1184
1185         /// Checks if the tree is empty
1186         bool empty() const
1187         {
1188             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1189         }
1190
1191         /// Clears the tree (thread safe, not atomic)
1192         /**
1193             The function unlink all items from the tree.
1194             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1195             this sequence
1196             \code
1197             set.clear();
1198             assert( set.empty() );
1199             \endcode
1200             the assertion could be raised.
1201
1202             For each leaf the \ref disposer will be called after unlinking.
1203
1204             RCU \p synchronize method can be called. RCU should not be locked.
1205         */
1206         void clear()
1207         {
1208             for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() )
1209                 ep.release();
1210         }
1211
1212         /// Clears the tree (not thread safe)
1213         /**
1214             This function is not thread safe and may be called only when no other thread deals with the tree.
1215             The function is used in the tree destructor.
1216         */
1217         void unsafe_clear()
1218         {
1219             rcu_lock l;
1220
1221             while ( true ) {
1222                 internal_node * pParent = nullptr;
1223                 internal_node * pGrandParent = nullptr;
1224                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
1225
1226                 // Get leftmost leaf
1227                 while ( pLeaf->is_internal() ) {
1228                     pGrandParent = pParent;
1229                     pParent = static_cast<internal_node *>( pLeaf );
1230                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1231                 }
1232
1233                 if ( pLeaf->infinite_key()) {
1234                     // The tree is empty
1235                     return;
1236                 }
1237
1238                 // Remove leftmost leaf and its parent node
1239                 assert( pGrandParent );
1240                 assert( pParent );
1241                 assert( pLeaf->is_leaf() );
1242
1243                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1244                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
1245                 free_internal_node( pParent );
1246             }
1247         }
1248
1249         /// Returns item count in the tree
1250         /**
1251             Only leaf nodes containing user data are counted.
1252
1253             The value returned depends on item counter type provided by \p Traits template parameter.
1254             If it is \p atomicity::empty_item_counter this function always returns 0.
1255
1256             The function is not suitable for checking the tree emptiness, use \p empty()
1257             member function for that.
1258         */
1259         size_t size() const
1260         {
1261             return m_ItemCounter;
1262         }
1263
1264         /// Returns const reference to internal statistics
1265         stat const& statistics() const
1266         {
1267             return m_Stat;
1268         }
1269
1270         /// Checks internal consistency (not atomic, not thread-safe)
1271         /**
1272             The debugging function to check internal consistency of the tree.
1273         */
1274         bool check_consistency() const
1275         {
1276             return check_consistency( &m_Root );
1277         }
1278
1279     protected:
1280         //@cond
1281
1282         bool check_consistency( internal_node const * pRoot ) const
1283         {
1284             tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1285             tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1286             assert( pLeft );
1287             assert( pRight );
1288
1289             if ( node_compare()( *pLeft, *pRoot ) < 0
1290                 && node_compare()( *pRoot, *pRight ) <= 0
1291                 && node_compare()( *pLeft, *pRight ) < 0 )
1292             {
1293                 bool bRet = true;
1294                 if ( pLeft->is_internal() )
1295                     bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
1296                 assert( bRet );
1297
1298                 if ( bRet && pRight->is_internal() )
1299                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1300                 assert( bRet );
1301
1302                 return bRet;
1303             }
1304             return false;
1305         }
1306
1307         void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
1308         {
1309             /*
1310             switch ( pUpdate.bits() ) {
1311                 case update_desc::IFlag:
1312                     help_insert( pUpdate.ptr() );
1313                     m_Stat.onHelpInsert();
1314                     break;
1315                 case update_desc::DFlag:
1316                     //help_delete( pUpdate.ptr(), rl );
1317                     //m_Stat.onHelpDelete();
1318                     break;
1319                 case update_desc::Mark:
1320                     //help_marked( pUpdate.ptr() );
1321                     //m_Stat.onHelpMark();
1322                     break;
1323             }
1324             */
1325         }
1326
1327         void help_insert( update_desc * pOp )
1328         {
1329             assert( gc::is_locked() );
1330
1331             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1332             if ( pOp->iInfo.bRightLeaf ) {
1333                 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1334                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1335             }
1336             else {
1337                 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1338                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1339             }
1340
1341             update_ptr cur( pOp, update_desc::IFlag );
1342             pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1343                       memory_model::memory_order_release, atomics::memory_order_relaxed );
1344         }
1345
1346         bool check_delete_precondition( search_result& res )
1347         {
1348             assert( res.pGrandParent != nullptr );
1349
1350             return
1351                 static_cast<internal_node *>( res.bRightParent
1352                     ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1353                     : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1354                 ) == res.pParent
1355                 &&
1356                 static_cast<leaf_node *>( res.bRightLeaf
1357                     ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1358                     : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1359                 ) == res.pLeaf;
1360         }
1361
1362         bool help_delete( update_desc * pOp, retired_list& rl )
1363         {
1364             assert( gc::is_locked() );
1365
1366             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1367             update_ptr pMark( pOp, update_desc::Mark );
1368             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1369                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1370             {
1371                 help_marked( pOp );
1372                 retire_node( pOp->dInfo.pParent, rl );
1373                 // For extract operations the leaf should NOT be disposed
1374                 if ( pOp->dInfo.bDisposeLeaf )
1375                     retire_node( pOp->dInfo.pLeaf, rl );
1376                 retire_update_desc( pOp, rl, false );
1377
1378                 return true;
1379             }
1380             else if ( pUpdate == pMark ) {
1381                 // some other thread is processing help_marked()
1382                 help_marked( pOp );
1383                 m_Stat.onHelpMark();
1384                 return true;
1385             }
1386             else {
1387                 // pUpdate has been changed by CAS
1388                 help( pUpdate, rl );
1389
1390                 // Undo grandparent dInfo
1391                 update_ptr pDel( pOp, update_desc::DFlag );
1392                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1393                     memory_model::memory_order_release, atomics::memory_order_relaxed ))
1394                 {
1395                     retire_update_desc( pOp, rl, false );
1396                 }
1397                 return false;
1398             }
1399         }
1400
1401         void help_marked( update_desc * pOp )
1402         {
1403             assert( gc::is_locked() );
1404
1405             tree_node * p = pOp->dInfo.pParent;
1406             if ( pOp->dInfo.bRightParent ) {
1407                 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1408                     pOp->dInfo.bRightLeaf
1409                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1410                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1411                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1412             }
1413             else {
1414                 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1415                     pOp->dInfo.bRightLeaf
1416                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1417                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1418                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1419             }
1420
1421             update_ptr upd( pOp, update_desc::DFlag );
1422             pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1423                 memory_model::memory_order_release, atomics::memory_order_relaxed );
1424         }
1425
1426         template <typename KeyValue, typename Compare>
1427         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1428         {
1429             assert( gc::is_locked() );
1430
1431             internal_node * pParent;
1432             internal_node * pGrandParent = nullptr;
1433             tree_node *     pLeaf;
1434             update_ptr      updParent;
1435             update_ptr      updGrandParent;
1436             bool bRightLeaf;
1437             bool bRightParent = false;
1438
1439             int nCmp = 0;
1440
1441         retry:
1442             pParent = nullptr;
1443             pLeaf = const_cast<internal_node *>( &m_Root );
1444             updParent = nullptr;
1445             bRightLeaf = false;
1446             while ( pLeaf->is_internal() ) {
1447                 pGrandParent = pParent;
1448                 pParent = static_cast<internal_node *>( pLeaf );
1449                 bRightParent = bRightLeaf;
1450                 updGrandParent = updParent;
1451                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1452
1453                 switch ( updParent.bits() ) {
1454                     case update_desc::DFlag:
1455                     case update_desc::Mark:
1456                         m_Stat.onSearchRetry();
1457                         goto retry;
1458                 }
1459
1460                 nCmp = cmp( key, *pParent );
1461                 bRightLeaf = nCmp >= 0;
1462                 pLeaf = nCmp < 0 ? pParent->m_pLeft.load( memory_model::memory_order_acquire )
1463                                  : pParent->m_pRight.load( memory_model::memory_order_acquire );
1464             }
1465
1466             assert( pLeaf->is_leaf() );
1467             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1468
1469             res.pGrandParent    = pGrandParent;
1470             res.pParent         = pParent;
1471             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1472             res.updParent       = updParent;
1473             res.updGrandParent  = updGrandParent;
1474             res.bRightParent    = bRightParent;
1475             res.bRightLeaf      = bRightLeaf;
1476
1477             return nCmp == 0;
1478         }
1479
1480         bool search_min( search_result& res ) const
1481         {
1482             assert( gc::is_locked() );
1483
1484             internal_node * pParent;
1485             internal_node * pGrandParent = nullptr;
1486             tree_node *     pLeaf;
1487             update_ptr      updParent;
1488             update_ptr      updGrandParent;
1489
1490         retry:
1491             pParent = nullptr;
1492             pLeaf = const_cast<internal_node *>( &m_Root );
1493             while ( pLeaf->is_internal() ) {
1494                 pGrandParent = pParent;
1495                 pParent = static_cast<internal_node *>( pLeaf );
1496                 updGrandParent = updParent;
1497                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1498
1499                 switch ( updParent.bits() ) {
1500                     case update_desc::DFlag:
1501                     case update_desc::Mark:
1502                         m_Stat.onSearchRetry();
1503                         goto retry;
1504                 }
1505
1506                 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1507             }
1508
1509             if ( pLeaf->infinite_key())
1510                 return false;
1511
1512             res.pGrandParent    = pGrandParent;
1513             res.pParent         = pParent;
1514             assert( pLeaf->is_leaf() );
1515             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1516             res.updParent       = updParent;
1517             res.updGrandParent  = updGrandParent;
1518             res.bRightParent    = false;
1519             res.bRightLeaf      = false;
1520
1521             return true;
1522         }
1523
1524         bool search_max( search_result& res ) const
1525         {
1526             assert( gc::is_locked() );
1527
1528             internal_node * pParent;
1529             internal_node * pGrandParent = nullptr;
1530             tree_node *     pLeaf;
1531             update_ptr      updParent;
1532             update_ptr      updGrandParent;
1533             bool bRightLeaf;
1534             bool bRightParent = false;
1535
1536         retry:
1537             pParent = nullptr;
1538             pLeaf = const_cast<internal_node *>( &m_Root );
1539             bRightLeaf = false;
1540             while ( pLeaf->is_internal() ) {
1541                 pGrandParent = pParent;
1542                 pParent = static_cast<internal_node *>( pLeaf );
1543                 bRightParent = bRightLeaf;
1544                 updGrandParent = updParent;
1545                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1546
1547                 switch ( updParent.bits() ) {
1548                     case update_desc::DFlag:
1549                     case update_desc::Mark:
1550                         m_Stat.onSearchRetry();
1551                         goto retry;
1552                 }
1553
1554                 if ( pParent->infinite_key()) {
1555                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1556                     bRightLeaf = false;
1557                 }
1558                 else {
1559                     pLeaf = pParent->m_pRight.load( memory_model::memory_order_acquire );
1560                     bRightLeaf = true;
1561                 }
1562             }
1563
1564             if ( pLeaf->infinite_key())
1565                 return false;
1566
1567             res.pGrandParent    = pGrandParent;
1568             res.pParent         = pParent;
1569             assert( pLeaf->is_leaf() );
1570             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1571             res.updParent       = updParent;
1572             res.updGrandParent  = updGrandParent;
1573             res.bRightParent    = bRightParent;
1574             res.bRightLeaf      = bRightLeaf;
1575
1576             return true;
1577         }
1578
1579         template <typename Q, typename Compare, typename Equal, typename Func>
1580         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1581         {
1582             check_deadlock_policy::check();
1583
1584             retired_list updRetire;
1585             update_desc * pOp = nullptr;
1586             search_result res;
1587             back_off bkoff;
1588
1589             {
1590                 rcu_lock l;
1591                 for ( ;; ) {
1592                     if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1593                         if ( pOp )
1594                             retire_update_desc( pOp, updRetire, false );
1595                         m_Stat.onEraseFailed();
1596                         return false;
1597                     }
1598
1599                     if ( res.updGrandParent.bits() != update_desc::Clean )
1600                         help( res.updGrandParent, updRetire );
1601                     else if ( res.updParent.bits() != update_desc::Clean )
1602                         help( res.updParent, updRetire );
1603                     else {
1604                         if ( !pOp )
1605                             pOp = alloc_update_desc();
1606                         if ( check_delete_precondition( res ) ) {
1607                             pOp->dInfo.pGrandParent = res.pGrandParent;
1608                             pOp->dInfo.pParent = res.pParent;
1609                             pOp->dInfo.pLeaf = res.pLeaf;
1610                             pOp->dInfo.bDisposeLeaf = true;
1611                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1612                             pOp->dInfo.bRightParent = res.bRightParent;
1613                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1614
1615                             update_ptr updGP( res.updGrandParent.ptr() );
1616                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1617                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1618                             {
1619                                 if ( help_delete( pOp, updRetire )) {
1620                                     // res.pLeaf is not deleted yet since RCU is blocked
1621                                     f( *node_traits::to_value_ptr( res.pLeaf ));
1622                                     break;
1623                                 }
1624                                 pOp = nullptr;
1625                             }
1626                             else {
1627                                 // updGP has been changed by CAS
1628                                 help( updGP, updRetire );
1629                             }
1630                         }
1631                     }
1632
1633                     bkoff();
1634                     m_Stat.onEraseRetry();
1635                 }
1636             }
1637
1638             --m_ItemCounter;
1639             m_Stat.onEraseSuccess();
1640             return true;
1641         }
1642
1643         template <typename Q, typename Less>
1644         value_type * extract_with_( Q const& val, Less /*pred*/ )
1645         {
1646             typedef ellen_bintree::details::compare<
1647                 key_type,
1648                 value_type,
1649                 opt::details::make_comparator_from_less<Less>,
1650                 node_traits
1651             > compare_functor;
1652
1653             return extract_( val, compare_functor() );
1654         }
1655
1656         template <typename Q, typename Compare>
1657         value_type * extract_( Q const& val, Compare cmp )
1658         {
1659             check_deadlock_policy::check();
1660
1661             retired_list updRetire;
1662             update_desc * pOp = nullptr;
1663             search_result res;
1664             back_off bkoff;
1665             value_type * pResult;
1666
1667             {
1668                 rcu_lock l;
1669                 for ( ;; ) {
1670                     if ( !search( res, val, cmp ) ) {
1671                         if ( pOp )
1672                             retire_update_desc( pOp, updRetire, false );
1673                         m_Stat.onEraseFailed();
1674                         return nullptr;
1675                     }
1676
1677                     if ( res.updGrandParent.bits() != update_desc::Clean )
1678                         help( res.updGrandParent, updRetire );
1679                     else if ( res.updParent.bits() != update_desc::Clean )
1680                         help( res.updParent, updRetire );
1681                     else {
1682                         if ( !pOp )
1683                             pOp = alloc_update_desc();
1684                         if ( check_delete_precondition( res )) {
1685                             pOp->dInfo.pGrandParent = res.pGrandParent;
1686                             pOp->dInfo.pParent = res.pParent;
1687                             pOp->dInfo.pLeaf = res.pLeaf;
1688                             pOp->dInfo.bDisposeLeaf = false;
1689                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1690                             pOp->dInfo.bRightParent = res.bRightParent;
1691                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1692
1693                             update_ptr updGP( res.updGrandParent.ptr() );
1694                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1695                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1696                             {
1697                                 if ( help_delete( pOp, updRetire )) {
1698                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1699                                     break;
1700                                 }
1701                                 pOp = nullptr;
1702                             }
1703                             else {
1704                                 // updGP has been changed by CAS
1705                                 help( updGP, updRetire );
1706                             }
1707                         }
1708                     }
1709
1710                     bkoff();
1711                     m_Stat.onEraseRetry();
1712                 }
1713             }
1714
1715             --m_ItemCounter;
1716             m_Stat.onEraseSuccess();
1717             return pResult;
1718         }
1719
1720
1721         value_type * extract_max_()
1722         {
1723             check_deadlock_policy::check();
1724
1725             retired_list updRetire;
1726             update_desc * pOp = nullptr;
1727             search_result res;
1728             back_off bkoff;
1729             value_type * pResult;
1730
1731             {
1732                 rcu_lock l;
1733                 for ( ;; ) {
1734                     if ( !search_max( res )) {
1735                         // Tree is empty
1736                         if ( pOp )
1737                             retire_update_desc( pOp, updRetire, false );
1738                         m_Stat.onExtractMaxFailed();
1739                         return nullptr;
1740                     }
1741
1742                     if ( res.updGrandParent.bits() != update_desc::Clean )
1743                         help( res.updGrandParent, updRetire );
1744                     else if ( res.updParent.bits() != update_desc::Clean )
1745                         help( res.updParent, updRetire );
1746                     else {
1747                         if ( !pOp )
1748                             pOp = alloc_update_desc();
1749                         if ( check_delete_precondition( res ) ) {
1750                             pOp->dInfo.pGrandParent = res.pGrandParent;
1751                             pOp->dInfo.pParent = res.pParent;
1752                             pOp->dInfo.pLeaf = res.pLeaf;
1753                             pOp->dInfo.bDisposeLeaf = false;
1754                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1755                             pOp->dInfo.bRightParent = res.bRightParent;
1756                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1757
1758                             update_ptr updGP( res.updGrandParent.ptr() );
1759                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1760                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1761                             {
1762                                 if ( help_delete( pOp, updRetire )) {
1763                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1764                                     break;
1765                                 }
1766                                 pOp = nullptr;
1767                             }
1768                             else {
1769                                 // updGP has been changed by CAS
1770                                 help( updGP, updRetire );
1771                             }
1772                         }
1773                     }
1774
1775                     bkoff();
1776                     m_Stat.onExtractMaxRetry();
1777                 }
1778             }
1779
1780             --m_ItemCounter;
1781             m_Stat.onExtractMaxSuccess();
1782             return pResult;
1783         }
1784
1785         value_type * extract_min_()
1786         {
1787             check_deadlock_policy::check();
1788
1789             retired_list updRetire;
1790             update_desc * pOp = nullptr;
1791             search_result res;
1792             back_off bkoff;
1793             value_type * pResult;
1794
1795             {
1796                 rcu_lock l;
1797                 for ( ;; ) {
1798                     if ( !search_min( res )) {
1799                         // Tree is empty
1800                         if ( pOp )
1801                             retire_update_desc( pOp, updRetire, false );
1802                         m_Stat.onExtractMinFailed();
1803                         return nullptr;
1804                     }
1805
1806                     if ( res.updGrandParent.bits() != update_desc::Clean )
1807                         help( res.updGrandParent, updRetire );
1808                     else if ( res.updParent.bits() != update_desc::Clean )
1809                         help( res.updParent, updRetire );
1810                     else {
1811                         if ( !pOp )
1812                             pOp = alloc_update_desc();
1813                         if ( check_delete_precondition( res ) ) {
1814                             pOp->dInfo.pGrandParent = res.pGrandParent;
1815                             pOp->dInfo.pParent = res.pParent;
1816                             pOp->dInfo.pLeaf = res.pLeaf;
1817                             pOp->dInfo.bDisposeLeaf = false;
1818                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1819                             pOp->dInfo.bRightParent = res.bRightParent;
1820                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1821
1822                             update_ptr updGP( res.updGrandParent.ptr() );
1823                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1824                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1825                             {
1826                                 if ( help_delete( pOp, updRetire )) {
1827                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1828                                     break;
1829                                 }
1830                                 pOp = nullptr;
1831                             }
1832                             else {
1833                                 // updGP has been changed by CAS
1834                                 help( updGP, updRetire );
1835                             }
1836                         }
1837                     }
1838
1839                     bkoff();
1840                     m_Stat.onExtractMinRetry();
1841                 }
1842             }
1843
1844             --m_ItemCounter;
1845             m_Stat.onExtractMinSuccess();
1846             return pResult;
1847         }
1848
1849         template <typename Q, typename Less, typename Func>
1850         bool find_with_( Q& val, Less /*pred*/, Func f ) const
1851         {
1852             typedef ellen_bintree::details::compare<
1853                 key_type,
1854                 value_type,
1855                 opt::details::make_comparator_from_less<Less>,
1856                 node_traits
1857             > compare_functor;
1858
1859             rcu_lock l;
1860             search_result    res;
1861             if ( search( res, val, compare_functor() )) {
1862                 assert( res.pLeaf );
1863                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1864
1865                 m_Stat.onFindSuccess();
1866                 return true;
1867             }
1868
1869             m_Stat.onFindFailed();
1870             return false;
1871         }
1872
1873         template <typename Q, typename Func>
1874         bool find_( Q& key, Func f ) const
1875         {
1876             rcu_lock l;
1877             search_result    res;
1878             if ( search( res, key, node_compare() )) {
1879                 assert( res.pLeaf );
1880                 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1881
1882                 m_Stat.onFindSuccess();
1883                 return true;
1884             }
1885
1886             m_Stat.onFindFailed();
1887             return false;
1888         }
1889
1890         template <typename Q, typename Compare>
1891         value_type * get_( Q const& key, Compare cmp ) const
1892         {
1893             assert( gc::is_locked());
1894
1895             search_result    res;
1896             if ( search( res, key, cmp )) {
1897                 m_Stat.onFindSuccess();
1898                 return node_traits::to_value_ptr( res.pLeaf );
1899             }
1900
1901             m_Stat.onFindFailed();
1902             return nullptr;
1903         }
1904
1905
1906         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1907         {
1908             assert( gc::is_locked() );
1909             assert( res.updParent.bits() == update_desc::Clean );
1910
1911             // check search result
1912             if ( static_cast<leaf_node *>( res.bRightLeaf
1913                 ? res.pParent->m_pRight.load( memory_model::memory_order_relaxed )
1914                 : res.pParent->m_pLeft.load( memory_model::memory_order_relaxed ) ) == res.pLeaf )
1915             {
1916                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1917
1918                 int nCmp = node_compare()( val, *res.pLeaf );
1919                 if ( nCmp < 0 ) {
1920                     if ( res.pGrandParent ) {
1921                         pNewInternal->infinite_key( 0 );
1922                         key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1923                         assert( !res.pLeaf->infinite_key() );
1924                     }
1925                     else {
1926                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1927                         pNewInternal->infinite_key( 1 );
1928                     }
1929                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1930                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1931                 }
1932                 else {
1933                     assert( !res.pLeaf->is_internal() );
1934                     pNewInternal->infinite_key( 0 );
1935
1936                     key_extractor()( pNewInternal->m_Key, val );
1937                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1938                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1939                     assert( !res.pLeaf->infinite_key());
1940                 }
1941
1942                 update_desc * pOp = alloc_update_desc();
1943
1944                 pOp->iInfo.pParent = res.pParent;
1945                 pOp->iInfo.pNew = pNewInternal;
1946                 pOp->iInfo.pLeaf = res.pLeaf;
1947                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1948
1949                 update_ptr updCur( res.updParent.ptr() );
1950                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1951                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1952                 {
1953                     // do insert
1954                     help_insert( pOp );
1955                     retire_update_desc( pOp, updRetire, false );
1956                     return true;
1957                 }
1958                 else {
1959                     // updCur has been updated by CAS
1960                     help( updCur, updRetire );
1961                     retire_update_desc( pOp, updRetire, true );
1962                 }
1963             }
1964             return false;
1965         }
1966
1967         //@endcond
1968     };
1969
1970 }} // namespace cds::intrusive
1971
1972 #endif  // #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H