cds/intrusive/ellen_bintree_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
   4 #define __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H
   5
   6 #include <memory>
   7 #include <cds/intrusive/details/ellen_bintree_base.h>
   8 #include <cds/opt/compare.h>
   9 #include <cds/details/binary_functor_wrapper.h>
  10 #include <cds/urcu/details/check_deadlock.h>
  11 #include <cds/urcu/exempt_ptr.h>
  12
  13 namespace cds { namespace intrusive {
  14     //@cond
  15     namespace ellen_bintree {
  16
  17         template <class RCU>
  18         struct base_node<cds::urcu::gc<RCU> >: public basic_node
  19         {
  20             typedef basic_node base_class;
  21
  22             base_node * m_pNextRetired;
  23
  24             typedef cds::urcu::gc<RCU> gc       ;   ///< Garbage collector
  25
  26             /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
  27             explicit base_node( bool bInternal )
  28                 : basic_node( bInternal ? internal : 0 )
  29                 , m_pNextRetired( nullptr )
  30             {}
  31         };
  32
  33     } // namespace ellen_bintree
  34     //@endcond
  35
  36     /// Ellen's et al binary search tree (RCU specialization)
  37     /** @ingroup cds_intrusive_map
  38         @ingroup cds_intrusive_tree
  39         @anchor cds_intrusive_EllenBinTree_rcu
  40
  41         Source:
  42             - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
  43
  44         %EllenBinTree is an unbalanced leaf-oriented binary search tree that implements the <i>set</i>
  45         abstract data type. Nodes maintains child pointers but not parent pointers.
  46         Every internal node has exactly two children, and all data of type \p T currently in
  47         the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
  48         operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
  49         may or may not be in the set. \p Key type is a subset of \p T type.
  50         There should be exactly defined a key extracting functor for converting object of type \p T to
  51         object of type \p Key.
  52
  53         Due to \p extract_min and \p extract_max member functions the \p %EllenBinTree can act as
  54         a <i>priority queue</i>. In this case you should provide unique compound key, for example,
  55         the priority value plus some uniformly distributed random value.
  56
  57         @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
  58         for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
  59
  60         @note In the current implementation we do not use helping technique described in 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 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 \ref 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 \ref cds_intrusive_EllenBinTree_rcu_extract "extract(exempt_ptr&, Q const&)"
1030             but \p pred is used for key compare.
1031             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1032             "predicate requirements".
1033             \p pred must imply the same element order as the comparator used for building the tree.
1034         */
1035         template <typename Q, typename Less>
1036         exempt_ptr extract_with( Q const& key, Less pred )
1037         {
1038             return exempt_ptr( extract_with_( key, pred ));
1039         }
1040
1041         /// Finds the key \p key
1042         /** @anchor cds_intrusive_EllenBinTree_rcu_find_val
1043             The function searches the item with key equal to \p key
1044             and returns \p true if it is found, and \p false otherwise.
1045
1046             Note the hash functor specified for class \p Traits template parameter
1047             should accept a parameter of type \p Q that can be not the same as \p value_type.
1048
1049             The function applies RCU lock internally.
1050         */
1051         template <typename Q>
1052         bool find( Q const& key ) const
1053         {
1054             rcu_lock l;
1055             search_result    res;
1056             if ( search( res, key, node_compare() )) {
1057                 m_Stat.onFindSuccess();
1058                 return true;
1059             }
1060
1061             m_Stat.onFindFailed();
1062             return false;
1063         }
1064
1065         /// Finds the key \p key with comparing functor \p pred
1066         /**
1067             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)"
1068             but \p pred is used for key compare.
1069             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1070             "Predicate requirements".
1071             \p pred must imply the same element order as the comparator used for building the tree.
1072             \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1073         */
1074         template <typename Q, typename Less>
1075         bool find_with( Q const& key, Less pred ) const
1076         {
1077             CDS_UNUSED( pred );
1078             typedef ellen_bintree::details::compare<
1079                 key_type,
1080                 value_type,
1081                 opt::details::make_comparator_from_less<Less>,
1082                 node_traits
1083             > compare_functor;
1084
1085             rcu_lock l;
1086             search_result    res;
1087             if ( search( res, key, compare_functor() )) {
1088                 m_Stat.onFindSuccess();
1089                 return true;
1090             }
1091             m_Stat.onFindFailed();
1092             return false;
1093         }
1094
1095         /// Finds the key \p key
1096         /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1097             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1098             The interface of \p Func functor is:
1099             \code
1100             struct functor {
1101                 void operator()( value_type& item, Q& key );
1102             };
1103             \endcode
1104             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1105
1106             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1107             that \p item cannot be disposed during functor is executing.
1108             The functor does not serialize simultaneous access to the tree \p item. If such access is
1109             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1110
1111             The function applies RCU lock internally.
1112
1113             The function returns \p true if \p key is found, \p false otherwise.
1114         */
1115         template <typename Q, typename Func>
1116         bool find( Q& key, Func f ) const
1117         {
1118             return find_( key, f );
1119         }
1120         //@cond
1121         template <typename Q, typename Func>
1122         bool find( Q const& key, Func f ) const
1123         {
1124             return find_( key, f );
1125         }
1126         //@endcond
1127
1128         /// Finds the key \p key with comparing functor \p pred
1129         /**
1130             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1131             but \p pred is used for key comparison.
1132             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1133             "Predicate requirements".
1134             \p pred must imply the same element order as the comparator used for building the tree.
1135         */
1136         template <typename Q, typename Less, typename Func>
1137         bool find_with( Q& key, Less pred, Func f ) const
1138         {
1139             return find_with_( key, pred, f );
1140         }
1141         //@cond
1142         template <typename Q, typename Less, typename Func>
1143         bool find_with( Q const& key, Less pred, Func f ) const
1144         {
1145             return find_with_( key, pred, f );
1146         }
1147         //@endcond
1148
1149         /// Finds \p key and return the item found
1150         /** \anchor cds_intrusive_EllenBinTree_rcu_get
1151             The function searches the item with key equal to \p key and returns the pointer to item found.
1152             If \p key is not found it returns \p nullptr.
1153
1154             RCU should be locked before call the function.
1155             Returned pointer is valid while RCU is locked.
1156         */
1157         template <typename Q>
1158         value_type * get( Q const& key ) const
1159         {
1160             return get_( key, node_compare() );
1161         }
1162
1163         /// Finds \p key with \p pred predicate and return the item found
1164         /**
1165             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1166             but \p pred is used for comparing the keys.
1167
1168             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1169             in any order.
1170             \p pred must imply the same element order as the comparator used for building the tree.
1171         */
1172         template <typename Q, typename Less>
1173         value_type * get_with( Q const& key, Less pred ) const
1174         {
1175             CDS_UNUSED( pred );
1176             typedef ellen_bintree::details::compare<
1177                 key_type,
1178                 value_type,
1179                 opt::details::make_comparator_from_less<Less>,
1180                 node_traits
1181             > compare_functor;
1182
1183             return get_( key, compare_functor());
1184         }
1185
1186         /// Checks if the tree is empty
1187         bool empty() const
1188         {
1189             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1190         }
1191
1192         /// Clears the tree (thread safe, not atomic)
1193         /**
1194             The function unlink all items from the tree.
1195             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1196             this sequence
1197             \code
1198             set.clear();
1199             assert( set.empty() );
1200             \endcode
1201             the assertion could be raised.
1202
1203             For each leaf the \ref disposer will be called after unlinking.
1204
1205             RCU \p synchronize method can be called. RCU should not be locked.
1206         */
1207         void clear()
1208         {
1209             for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min() )
1210                 ep.release();
1211         }
1212
1213         /// Clears the tree (not thread safe)
1214         /**
1215             This function is not thread safe and may be called only when no other thread deals with the tree.
1216             The function is used in the tree destructor.
1217         */
1218         void unsafe_clear()
1219         {
1220             rcu_lock l;
1221
1222             while ( true ) {
1223                 internal_node * pParent = nullptr;
1224                 internal_node * pGrandParent = nullptr;
1225                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
1226
1227                 // Get leftmost leaf
1228                 while ( pLeaf->is_internal() ) {
1229                     pGrandParent = pParent;
1230                     pParent = static_cast<internal_node *>( pLeaf );
1231                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1232                 }
1233
1234                 if ( pLeaf->infinite_key()) {
1235                     // The tree is empty
1236                     return;
1237                 }
1238
1239                 // Remove leftmost leaf and its parent node
1240                 assert( pGrandParent );
1241                 assert( pParent );
1242                 assert( pLeaf->is_leaf() );
1243
1244                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1245                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
1246                 free_internal_node( pParent );
1247             }
1248         }
1249
1250         /// Returns item count in the tree
1251         /**
1252             Only leaf nodes containing user data are counted.
1253
1254             The value returned depends on item counter type provided by \p Traits template parameter.
1255             If it is \p atomicity::empty_item_counter this function always returns 0.
1256
1257             The function is not suitable for checking the tree emptiness, use \p empty()
1258             member function for that.
1259         */
1260         size_t size() const
1261         {
1262             return m_ItemCounter;
1263         }
1264
1265         /// Returns const reference to internal statistics
1266         stat const& statistics() const
1267         {
1268             return m_Stat;
1269         }
1270
1271         /// Checks internal consistency (not atomic, not thread-safe)
1272         /**
1273             The debugging function to check internal consistency of the tree.
1274         */
1275         bool check_consistency() const
1276         {
1277             return check_consistency( &m_Root );
1278         }
1279
1280     protected:
1281         //@cond
1282
1283         bool check_consistency( internal_node const * pRoot ) const
1284         {
1285             tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1286             tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1287             assert( pLeft );
1288             assert( pRight );
1289
1290             if ( node_compare()( *pLeft, *pRoot ) < 0
1291                 && node_compare()( *pRoot, *pRight ) <= 0
1292                 && node_compare()( *pLeft, *pRight ) < 0 )
1293             {
1294                 bool bRet = true;
1295                 if ( pLeft->is_internal() )
1296                     bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
1297                 assert( bRet );
1298
1299                 if ( bRet && pRight->is_internal() )
1300                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1301                 assert( bRet );
1302
1303                 return bRet;
1304             }
1305             return false;
1306         }
1307
1308         void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
1309         {
1310             /*
1311             switch ( pUpdate.bits() ) {
1312                 case update_desc::IFlag:
1313                     help_insert( pUpdate.ptr() );
1314                     m_Stat.onHelpInsert();
1315                     break;
1316                 case update_desc::DFlag:
1317                     //help_delete( pUpdate.ptr(), rl );
1318                     //m_Stat.onHelpDelete();
1319                     break;
1320                 case update_desc::Mark:
1321                     //help_marked( pUpdate.ptr() );
1322                     //m_Stat.onHelpMark();
1323                     break;
1324             }
1325             */
1326         }
1327
1328         void help_insert( update_desc * pOp )
1329         {
1330             assert( gc::is_locked() );
1331
1332             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1333             if ( pOp->iInfo.bRightLeaf ) {
1334                 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1335                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1336             }
1337             else {
1338                 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1339                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1340             }
1341
1342             update_ptr cur( pOp, update_desc::IFlag );
1343             pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1344                       memory_model::memory_order_release, atomics::memory_order_relaxed );
1345         }
1346
1347         bool check_delete_precondition( search_result& res )
1348         {
1349             assert( res.pGrandParent != nullptr );
1350
1351             return
1352                 static_cast<internal_node *>( res.bRightParent
1353                     ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1354                     : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1355                 ) == res.pParent
1356                 &&
1357                 static_cast<leaf_node *>( res.bRightLeaf
1358                     ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1359                     : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1360                 ) == res.pLeaf;
1361         }
1362
1363         bool help_delete( update_desc * pOp, retired_list& rl )
1364         {
1365             assert( gc::is_locked() );
1366
1367             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1368             update_ptr pMark( pOp, update_desc::Mark );
1369             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1370                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1371             {
1372                 help_marked( pOp );
1373                 retire_node( pOp->dInfo.pParent, rl );
1374                 // For extract operations the leaf should NOT be disposed
1375                 if ( pOp->dInfo.bDisposeLeaf )
1376                     retire_node( pOp->dInfo.pLeaf, rl );
1377                 retire_update_desc( pOp, rl, false );
1378
1379                 return true;
1380             }
1381             else if ( pUpdate == pMark ) {
1382                 // some other thread is processing help_marked()
1383                 help_marked( pOp );
1384                 m_Stat.onHelpMark();
1385                 return true;
1386             }
1387             else {
1388                 // pUpdate has been changed by CAS
1389                 help( pUpdate, rl );
1390
1391                 // Undo grandparent dInfo
1392                 update_ptr pDel( pOp, update_desc::DFlag );
1393                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1394                     memory_model::memory_order_release, atomics::memory_order_relaxed ))
1395                 {
1396                     retire_update_desc( pOp, rl, false );
1397                 }
1398                 return false;
1399             }
1400         }
1401
1402         void help_marked( update_desc * pOp )
1403         {
1404             assert( gc::is_locked() );
1405
1406             tree_node * p = pOp->dInfo.pParent;
1407             if ( pOp->dInfo.bRightParent ) {
1408                 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1409                     pOp->dInfo.bRightLeaf
1410                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1411                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1412                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1413             }
1414             else {
1415                 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1416                     pOp->dInfo.bRightLeaf
1417                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1418                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1419                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1420             }
1421
1422             update_ptr upd( pOp, update_desc::DFlag );
1423             pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1424                 memory_model::memory_order_release, atomics::memory_order_relaxed );
1425         }
1426
1427         template <typename KeyValue, typename Compare>
1428         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1429         {
1430             assert( gc::is_locked() );
1431
1432             internal_node * pParent;
1433             internal_node * pGrandParent = nullptr;
1434             tree_node *     pLeaf;
1435             update_ptr      updParent;
1436             update_ptr      updGrandParent;
1437             bool bRightLeaf;
1438             bool bRightParent = false;
1439
1440             int nCmp = 0;
1441
1442         retry:
1443             pParent = nullptr;
1444             pLeaf = const_cast<internal_node *>( &m_Root );
1445             updParent = nullptr;
1446             bRightLeaf = false;
1447             while ( pLeaf->is_internal() ) {
1448                 pGrandParent = pParent;
1449                 pParent = static_cast<internal_node *>( pLeaf );
1450                 bRightParent = bRightLeaf;
1451                 updGrandParent = updParent;
1452                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1453
1454                 switch ( updParent.bits() ) {
1455                     case update_desc::DFlag:
1456                     case update_desc::Mark:
1457                         m_Stat.onSearchRetry();
1458                         goto retry;
1459                 }
1460
1461                 nCmp = cmp( key, *pParent );
1462                 bRightLeaf = nCmp >= 0;
1463                 pLeaf = nCmp < 0 ? pParent->m_pLeft.load( memory_model::memory_order_acquire )
1464                                  : pParent->m_pRight.load( memory_model::memory_order_acquire );
1465             }
1466
1467             assert( pLeaf->is_leaf() );
1468             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1469
1470             res.pGrandParent    = pGrandParent;
1471             res.pParent         = pParent;
1472             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1473             res.updParent       = updParent;
1474             res.updGrandParent  = updGrandParent;
1475             res.bRightParent    = bRightParent;
1476             res.bRightLeaf      = bRightLeaf;
1477
1478             return nCmp == 0;
1479         }
1480
1481         bool search_min( search_result& res ) const
1482         {
1483             assert( gc::is_locked() );
1484
1485             internal_node * pParent;
1486             internal_node * pGrandParent = nullptr;
1487             tree_node *     pLeaf;
1488             update_ptr      updParent;
1489             update_ptr      updGrandParent;
1490
1491         retry:
1492             pParent = nullptr;
1493             pLeaf = const_cast<internal_node *>( &m_Root );
1494             while ( pLeaf->is_internal() ) {
1495                 pGrandParent = pParent;
1496                 pParent = static_cast<internal_node *>( pLeaf );
1497                 updGrandParent = updParent;
1498                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1499
1500                 switch ( updParent.bits() ) {
1501                     case update_desc::DFlag:
1502                     case update_desc::Mark:
1503                         m_Stat.onSearchRetry();
1504                         goto retry;
1505                 }
1506
1507                 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1508             }
1509
1510             if ( pLeaf->infinite_key())
1511                 return false;
1512
1513             res.pGrandParent    = pGrandParent;
1514             res.pParent         = pParent;
1515             assert( pLeaf->is_leaf() );
1516             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1517             res.updParent       = updParent;
1518             res.updGrandParent  = updGrandParent;
1519             res.bRightParent    = false;
1520             res.bRightLeaf      = false;
1521
1522             return true;
1523         }
1524
1525         bool search_max( search_result& res ) const
1526         {
1527             assert( gc::is_locked() );
1528
1529             internal_node * pParent;
1530             internal_node * pGrandParent = nullptr;
1531             tree_node *     pLeaf;
1532             update_ptr      updParent;
1533             update_ptr      updGrandParent;
1534             bool bRightLeaf;
1535             bool bRightParent = false;
1536
1537         retry:
1538             pParent = nullptr;
1539             pLeaf = const_cast<internal_node *>( &m_Root );
1540             bRightLeaf = false;
1541             while ( pLeaf->is_internal() ) {
1542                 pGrandParent = pParent;
1543                 pParent = static_cast<internal_node *>( pLeaf );
1544                 bRightParent = bRightLeaf;
1545                 updGrandParent = updParent;
1546                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1547
1548                 switch ( updParent.bits() ) {
1549                     case update_desc::DFlag:
1550                     case update_desc::Mark:
1551                         m_Stat.onSearchRetry();
1552                         goto retry;
1553                 }
1554
1555                 if ( pParent->infinite_key()) {
1556                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1557                     bRightLeaf = false;
1558                 }
1559                 else {
1560                     pLeaf = pParent->m_pRight.load( memory_model::memory_order_acquire );
1561                     bRightLeaf = true;
1562                 }
1563             }
1564
1565             if ( pLeaf->infinite_key())
1566                 return false;
1567
1568             res.pGrandParent    = pGrandParent;
1569             res.pParent         = pParent;
1570             assert( pLeaf->is_leaf() );
1571             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1572             res.updParent       = updParent;
1573             res.updGrandParent  = updGrandParent;
1574             res.bRightParent    = bRightParent;
1575             res.bRightLeaf      = bRightLeaf;
1576
1577             return true;
1578         }
1579
1580         template <typename Q, typename Compare, typename Equal, typename Func>
1581         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1582         {
1583             check_deadlock_policy::check();
1584
1585             retired_list updRetire;
1586             update_desc * pOp = nullptr;
1587             search_result res;
1588             back_off bkoff;
1589
1590             {
1591                 rcu_lock l;
1592                 for ( ;; ) {
1593                     if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1594                         if ( pOp )
1595                             retire_update_desc( pOp, updRetire, false );
1596                         m_Stat.onEraseFailed();
1597                         return false;
1598                     }
1599
1600                     if ( res.updGrandParent.bits() != update_desc::Clean )
1601                         help( res.updGrandParent, updRetire );
1602                     else if ( res.updParent.bits() != update_desc::Clean )
1603                         help( res.updParent, updRetire );
1604                     else {
1605                         if ( !pOp )
1606                             pOp = alloc_update_desc();
1607                         if ( check_delete_precondition( res ) ) {
1608                             pOp->dInfo.pGrandParent = res.pGrandParent;
1609                             pOp->dInfo.pParent = res.pParent;
1610                             pOp->dInfo.pLeaf = res.pLeaf;
1611                             pOp->dInfo.bDisposeLeaf = true;
1612                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1613                             pOp->dInfo.bRightParent = res.bRightParent;
1614                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1615
1616                             update_ptr updGP( res.updGrandParent.ptr() );
1617                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1618                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1619                             {
1620                                 if ( help_delete( pOp, updRetire )) {
1621                                     // res.pLeaf is not deleted yet since RCU is blocked
1622                                     f( *node_traits::to_value_ptr( res.pLeaf ));
1623                                     break;
1624                                 }
1625                                 pOp = nullptr;
1626                             }
1627                             else {
1628                                 // updGP has been changed by CAS
1629                                 help( updGP, updRetire );
1630                             }
1631                         }
1632                     }
1633
1634                     bkoff();
1635                     m_Stat.onEraseRetry();
1636                 }
1637             }
1638
1639             --m_ItemCounter;
1640             m_Stat.onEraseSuccess();
1641             return true;
1642         }
1643
1644         template <typename Q, typename Less>
1645         value_type * extract_with_( Q const& val, Less /*pred*/ )
1646         {
1647             typedef ellen_bintree::details::compare<
1648                 key_type,
1649                 value_type,
1650                 opt::details::make_comparator_from_less<Less>,
1651                 node_traits
1652             > compare_functor;
1653
1654             return extract_( val, compare_functor() );
1655         }
1656
1657         template <typename Q, typename Compare>
1658         value_type * extract_( Q const& val, Compare cmp )
1659         {
1660             check_deadlock_policy::check();
1661
1662             retired_list updRetire;
1663             update_desc * pOp = nullptr;
1664             search_result res;
1665             back_off bkoff;
1666             value_type * pResult;
1667
1668             {
1669                 rcu_lock l;
1670                 for ( ;; ) {
1671                     if ( !search( res, val, cmp ) ) {
1672                         if ( pOp )
1673                             retire_update_desc( pOp, updRetire, false );
1674                         m_Stat.onEraseFailed();
1675                         return nullptr;
1676                     }
1677
1678                     if ( res.updGrandParent.bits() != update_desc::Clean )
1679                         help( res.updGrandParent, updRetire );
1680                     else if ( res.updParent.bits() != update_desc::Clean )
1681                         help( res.updParent, updRetire );
1682                     else {
1683                         if ( !pOp )
1684                             pOp = alloc_update_desc();
1685                         if ( check_delete_precondition( res )) {
1686                             pOp->dInfo.pGrandParent = res.pGrandParent;
1687                             pOp->dInfo.pParent = res.pParent;
1688                             pOp->dInfo.pLeaf = res.pLeaf;
1689                             pOp->dInfo.bDisposeLeaf = false;
1690                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1691                             pOp->dInfo.bRightParent = res.bRightParent;
1692                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1693
1694                             update_ptr updGP( res.updGrandParent.ptr() );
1695                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1696                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1697                             {
1698                                 if ( help_delete( pOp, updRetire )) {
1699                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1700                                     break;
1701                                 }
1702                                 pOp = nullptr;
1703                             }
1704                             else {
1705                                 // updGP has been changed by CAS
1706                                 help( updGP, updRetire );
1707                             }
1708                         }
1709                     }
1710
1711                     bkoff();
1712                     m_Stat.onEraseRetry();
1713                 }
1714             }
1715
1716             --m_ItemCounter;
1717             m_Stat.onEraseSuccess();
1718             return pResult;
1719         }
1720
1721
1722         value_type * extract_max_()
1723         {
1724             check_deadlock_policy::check();
1725
1726             retired_list updRetire;
1727             update_desc * pOp = nullptr;
1728             search_result res;
1729             back_off bkoff;
1730             value_type * pResult;
1731
1732             {
1733                 rcu_lock l;
1734                 for ( ;; ) {
1735                     if ( !search_max( res )) {
1736                         // Tree is empty
1737                         if ( pOp )
1738                             retire_update_desc( pOp, updRetire, false );
1739                         m_Stat.onExtractMaxFailed();
1740                         return nullptr;
1741                     }
1742
1743                     if ( res.updGrandParent.bits() != update_desc::Clean )
1744                         help( res.updGrandParent, updRetire );
1745                     else if ( res.updParent.bits() != update_desc::Clean )
1746                         help( res.updParent, updRetire );
1747                     else {
1748                         if ( !pOp )
1749                             pOp = alloc_update_desc();
1750                         if ( check_delete_precondition( res ) ) {
1751                             pOp->dInfo.pGrandParent = res.pGrandParent;
1752                             pOp->dInfo.pParent = res.pParent;
1753                             pOp->dInfo.pLeaf = res.pLeaf;
1754                             pOp->dInfo.bDisposeLeaf = false;
1755                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1756                             pOp->dInfo.bRightParent = res.bRightParent;
1757                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1758
1759                             update_ptr updGP( res.updGrandParent.ptr() );
1760                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1761                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1762                             {
1763                                 if ( help_delete( pOp, updRetire )) {
1764                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1765                                     break;
1766                                 }
1767                                 pOp = nullptr;
1768                             }
1769                             else {
1770                                 // updGP has been changed by CAS
1771                                 help( updGP, updRetire );
1772                             }
1773                         }
1774                     }
1775
1776                     bkoff();
1777                     m_Stat.onExtractMaxRetry();
1778                 }
1779             }
1780
1781             --m_ItemCounter;
1782             m_Stat.onExtractMaxSuccess();
1783             return pResult;
1784         }
1785
1786         value_type * extract_min_()
1787         {
1788             check_deadlock_policy::check();
1789
1790             retired_list updRetire;
1791             update_desc * pOp = nullptr;
1792             search_result res;
1793             back_off bkoff;
1794             value_type * pResult;
1795
1796             {
1797                 rcu_lock l;
1798                 for ( ;; ) {
1799                     if ( !search_min( res )) {
1800                         // Tree is empty
1801                         if ( pOp )
1802                             retire_update_desc( pOp, updRetire, false );
1803                         m_Stat.onExtractMinFailed();
1804                         return nullptr;
1805                     }
1806
1807                     if ( res.updGrandParent.bits() != update_desc::Clean )
1808                         help( res.updGrandParent, updRetire );
1809                     else if ( res.updParent.bits() != update_desc::Clean )
1810                         help( res.updParent, updRetire );
1811                     else {
1812                         if ( !pOp )
1813                             pOp = alloc_update_desc();
1814                         if ( check_delete_precondition( res ) ) {
1815                             pOp->dInfo.pGrandParent = res.pGrandParent;
1816                             pOp->dInfo.pParent = res.pParent;
1817                             pOp->dInfo.pLeaf = res.pLeaf;
1818                             pOp->dInfo.bDisposeLeaf = false;
1819                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1820                             pOp->dInfo.bRightParent = res.bRightParent;
1821                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1822
1823                             update_ptr updGP( res.updGrandParent.ptr() );
1824                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1825                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1826                             {
1827                                 if ( help_delete( pOp, updRetire )) {
1828                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1829                                     break;
1830                                 }
1831                                 pOp = nullptr;
1832                             }
1833                             else {
1834                                 // updGP has been changed by CAS
1835                                 help( updGP, updRetire );
1836                             }
1837                         }
1838                     }
1839
1840                     bkoff();
1841                     m_Stat.onExtractMinRetry();
1842                 }
1843             }
1844
1845             --m_ItemCounter;
1846             m_Stat.onExtractMinSuccess();
1847             return pResult;
1848         }
1849
1850         template <typename Q, typename Less, typename Func>
1851         bool find_with_( Q& val, Less /*pred*/, Func f ) const
1852         {
1853             typedef ellen_bintree::details::compare<
1854                 key_type,
1855                 value_type,
1856                 opt::details::make_comparator_from_less<Less>,
1857                 node_traits
1858             > compare_functor;
1859
1860             rcu_lock l;
1861             search_result    res;
1862             if ( search( res, val, compare_functor() )) {
1863                 assert( res.pLeaf );
1864                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1865
1866                 m_Stat.onFindSuccess();
1867                 return true;
1868             }
1869
1870             m_Stat.onFindFailed();
1871             return false;
1872         }
1873
1874         template <typename Q, typename Func>
1875         bool find_( Q& key, Func f ) const
1876         {
1877             rcu_lock l;
1878             search_result    res;
1879             if ( search( res, key, node_compare() )) {
1880                 assert( res.pLeaf );
1881                 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1882
1883                 m_Stat.onFindSuccess();
1884                 return true;
1885             }
1886
1887             m_Stat.onFindFailed();
1888             return false;
1889         }
1890
1891         template <typename Q, typename Compare>
1892         value_type * get_( Q const& key, Compare cmp ) const
1893         {
1894             assert( gc::is_locked());
1895
1896             search_result    res;
1897             if ( search( res, key, cmp )) {
1898                 m_Stat.onFindSuccess();
1899                 return node_traits::to_value_ptr( res.pLeaf );
1900             }
1901
1902             m_Stat.onFindFailed();
1903             return nullptr;
1904         }
1905
1906
1907         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1908         {
1909             assert( gc::is_locked() );
1910             assert( res.updParent.bits() == update_desc::Clean );
1911
1912             // check search result
1913             if ( static_cast<leaf_node *>( res.bRightLeaf
1914                 ? res.pParent->m_pRight.load( memory_model::memory_order_relaxed )
1915                 : res.pParent->m_pLeft.load( memory_model::memory_order_relaxed ) ) == res.pLeaf )
1916             {
1917                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1918
1919                 int nCmp = node_compare()( val, *res.pLeaf );
1920                 if ( nCmp < 0 ) {
1921                     if ( res.pGrandParent ) {
1922                         pNewInternal->infinite_key( 0 );
1923                         key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1924                         assert( !res.pLeaf->infinite_key() );
1925                     }
1926                     else {
1927                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1928                         pNewInternal->infinite_key( 1 );
1929                     }
1930                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1931                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1932                 }
1933                 else {
1934                     assert( !res.pLeaf->is_internal() );
1935                     pNewInternal->infinite_key( 0 );
1936
1937                     key_extractor()( pNewInternal->m_Key, val );
1938                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1939                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1940                     assert( !res.pLeaf->infinite_key());
1941                 }
1942
1943                 update_desc * pOp = alloc_update_desc();
1944
1945                 pOp->iInfo.pParent = res.pParent;
1946                 pOp->iInfo.pNew = pNewInternal;
1947                 pOp->iInfo.pLeaf = res.pLeaf;
1948                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1949
1950                 update_ptr updCur( res.updParent.ptr() );
1951                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1952                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1953                 {
1954                     // do insert
1955                     help_insert( pOp );
1956                     retire_update_desc( pOp, updRetire, false );
1957                     return true;
1958                 }
1959                 else {
1960                     // updCur has been updated by CAS
1961                     help( updCur, updRetire );
1962                     retire_update_desc( pOp, updRetire, true );
1963                 }
1964             }
1965             return false;
1966         }
1967
1968         //@endcond
1969     };
1970
1971 }} // namespace cds::intrusive
1972
1973 #endif  // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H