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         typedef cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > exempt_ptr; ///< 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             typedef ellen_bintree::details::compare<
 904                 key_type,
 905                 value_type,
 906                 opt::details::make_comparator_from_less<Less>,
 907                 node_traits
 908             > compare_functor;
 909
 910             return erase_( key, compare_functor(),
 911                 []( Q const&, leaf_node const& ) -> bool { return true; },
 912                 [](value_type const&) {} );
 913         }
 914
 915         /// Deletes the item from the tree
 916         /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
 917             The function searches an item with key equal to \p key in the tree,
 918             call \p f functor with item found, unlinks it from the tree, and returns \p true.
 919             The \ref disposer specified in \p Traits class template parameter is called
 920             by garbage collector \p GC asynchronously.
 921
 922             The \p Func interface is
 923             \code
 924             struct functor {
 925                 void operator()( value_type const& item );
 926             };
 927             \endcode
 928
 929             If the item with key equal to \p key is not found the function return \p false.
 930
 931             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 932
 933             RCU \p synchronize method can be called. RCU should not be locked.
 934         */
 935         template <typename Q, typename Func>
 936         bool erase( Q const& key, Func f )
 937         {
 938             return erase_( key, node_compare(),
 939                 []( Q const&, leaf_node const& ) -> bool { return true; },
 940                 f );
 941         }
 942
 943         /// Delete the item from the tree with comparing functor \p pred
 944         /**
 945             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
 946             but \p pred predicate is used for key comparing.
 947             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 948             "Predicate requirements".
 949             \p pred must imply the same element order as the comparator used for building the tree.
 950         */
 951         template <typename Q, typename Less, typename Func>
 952         bool erase_with( Q const& key, Less pred, Func f )
 953         {
 954             typedef ellen_bintree::details::compare<
 955                 key_type,
 956                 value_type,
 957                 opt::details::make_comparator_from_less<Less>,
 958                 node_traits
 959             > compare_functor;
 960
 961             return erase_( key, compare_functor(),
 962                 []( Q const&, leaf_node const& ) -> bool { return true; },
 963                 f );
 964         }
 965
 966         /// Extracts an item with minimal key from the tree
 967         /**
 968             The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p result parameter.
 969             If the tree is empty the function returns \p false.
 970
 971             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
 972             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 973             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 974             So, the function returns the item with minimum key at the moment of tree traversing.
 975
 976             RCU \p synchronize method can be called. RCU should NOT be locked.
 977             The function does not call the disposer for the item found.
 978             The disposer will be implicitly invoked when \p result object is destroyed or when
 979             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 980             @note Before reusing \p result object you should call its \p release() method.
 981         */
 982         bool extract_min(exempt_ptr& result)
 983         {
 984             return extract_min_(result);
 985         }
 986
 987         /// Extracts an item with maximal key from the tree
 988         /**
 989             The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p result prameter.
 990             If the tree is empty the function returns \p false.
 991
 992             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
 993             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 994             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
 995             So, the function returns the item with maximum key at the moment of tree traversing.
 996
 997             RCU \p synchronize method can be called. RCU should NOT be locked.
 998             The function does not call the disposer for the item found.
 999             The disposer will be implicitly invoked when \p result object is destroyed or when
1000             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1001             @note Before reusing \p result object you should call its \p release() method.
1002         */
1003         bool extract_max(exempt_ptr& result)
1004         {
1005             return extract_max_(result);
1006         }
1007
1008         /// Extracts an item from the tree
1009         /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1010             The function searches an item with key equal to \p key in the tree,
1011             unlinks it, and returns pointer to an item found in \p result parameter.
1012             If the item with the key equal to \p key is not found the function returns \p false.
1013
1014             RCU \p synchronize method can be called. RCU should NOT be locked.
1015             The function does not call the disposer for the item found.
1016             The disposer will be implicitly invoked when \p result object is destroyed or when
1017             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1018             @note Before reusing \p result object you should call its \p release() method.
1019         */
1020         template <typename Q>
1021         bool extract( exempt_ptr& result, Q const& key )
1022         {
1023             return extract_( result, key, node_compare() );
1024         }
1025
1026         /// Extracts an item from the set using \p pred for searching
1027         /**
1028             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_extract "extract(exempt_ptr&, Q const&)"
1029             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         bool extract_with( exempt_ptr& dest,  Q const& key, Less pred )
1036         {
1037             return extract_with_( dest, 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             typedef ellen_bintree::details::compare<
1077                 key_type,
1078                 value_type,
1079                 opt::details::make_comparator_from_less<Less>,
1080                 node_traits
1081             > compare_functor;
1082
1083             rcu_lock l;
1084             search_result    res;
1085             if ( search( res, key, compare_functor() )) {
1086                 m_Stat.onFindSuccess();
1087                 return true;
1088             }
1089             m_Stat.onFindFailed();
1090             return false;
1091         }
1092
1093         /// Finds the key \p key
1094         /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1095             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1096             The interface of \p Func functor is:
1097             \code
1098             struct functor {
1099                 void operator()( value_type& item, Q& key );
1100             };
1101             \endcode
1102             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1103
1104             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1105             that \p item cannot be disposed during functor is executing.
1106             The functor does not serialize simultaneous access to the tree \p item. If such access is
1107             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1108
1109             The function applies RCU lock internally.
1110
1111             The function returns \p true if \p key is found, \p false otherwise.
1112         */
1113         template <typename Q, typename Func>
1114         bool find( Q& key, Func f ) const
1115         {
1116             return find_( key, f );
1117         }
1118         //@cond
1119         template <typename Q, typename Func>
1120         bool find( Q const& key, Func f ) const
1121         {
1122             return find_( key, f );
1123         }
1124         //@endcond
1125
1126         /// Finds the key \p key with comparing functor \p pred
1127         /**
1128             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1129             but \p pred is used for key comparison.
1130             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1131             "Predicate requirements".
1132             \p pred must imply the same element order as the comparator used for building the tree.
1133         */
1134         template <typename Q, typename Less, typename Func>
1135         bool find_with( Q& key, Less pred, Func f ) const
1136         {
1137             return find_with_( key, pred, f );
1138         }
1139         //@cond
1140         template <typename Q, typename Less, typename Func>
1141         bool find_with( Q const& key, Less pred, Func f ) const
1142         {
1143             return find_with_( key, pred, f );
1144         }
1145         //@endcond
1146
1147         /// Finds \p key and return the item found
1148         /** \anchor cds_intrusive_EllenBinTree_rcu_get
1149             The function searches the item with key equal to \p key and returns the pointer to item found.
1150             If \p key is not found it returns \p nullptr.
1151
1152             RCU should be locked before call the function.
1153             Returned pointer is valid while RCU is locked.
1154         */
1155         template <typename Q>
1156         value_type * get( Q const& key ) const
1157         {
1158             return get_( key, node_compare() );
1159         }
1160
1161         /// Finds \p key with \p pred predicate and return the item found
1162         /**
1163             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1164             but \p pred is used for comparing the keys.
1165
1166             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1167             in any order.
1168             \p pred must imply the same element order as the comparator used for building the tree.
1169         */
1170         template <typename Q, typename Less>
1171         value_type * get_with( Q const& key, Less pred ) const
1172         {
1173             typedef ellen_bintree::details::compare<
1174                 key_type,
1175                 value_type,
1176                 opt::details::make_comparator_from_less<Less>,
1177                 node_traits
1178             > compare_functor;
1179
1180             return get_( key, compare_functor());
1181         }
1182
1183         /// Checks if the tree is empty
1184         bool empty() const
1185         {
1186             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1187         }
1188
1189         /// Clears the tree (thread safe, not atomic)
1190         /**
1191             The function unlink all items from the tree.
1192             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1193             this sequence
1194             \code
1195             set.clear();
1196             assert( set.empty() );
1197             \endcode
1198             the assertion could be raised.
1199
1200             For each leaf the \ref disposer will be called after unlinking.
1201
1202             RCU \p synchronize method can be called. RCU should not be locked.
1203         */
1204         void clear()
1205         {
1206             exempt_ptr ep;
1207             while ( extract_min(ep) )
1208                 ep.release();
1209         }
1210
1211         /// Clears the tree (not thread safe)
1212         /**
1213             This function is not thread safe and may be called only when no other thread deals with the tree.
1214             The function is used in the tree destructor.
1215         */
1216         void unsafe_clear()
1217         {
1218             rcu_lock l;
1219
1220             while ( true ) {
1221                 internal_node * pParent = nullptr;
1222                 internal_node * pGrandParent = nullptr;
1223                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
1224
1225                 // Get leftmost leaf
1226                 while ( pLeaf->is_internal() ) {
1227                     pGrandParent = pParent;
1228                     pParent = static_cast<internal_node *>( pLeaf );
1229                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1230                 }
1231
1232                 if ( pLeaf->infinite_key()) {
1233                     // The tree is empty
1234                     return;
1235                 }
1236
1237                 // Remove leftmost leaf and its parent node
1238                 assert( pGrandParent );
1239                 assert( pParent );
1240                 assert( pLeaf->is_leaf() );
1241
1242                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1243                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
1244                 free_internal_node( pParent );
1245             }
1246         }
1247
1248         /// Returns item count in the tree
1249         /**
1250             Only leaf nodes containing user data are counted.
1251
1252             The value returned depends on item counter type provided by \p Traits template parameter.
1253             If it is \p atomicity::empty_item_counter this function always returns 0.
1254
1255             The function is not suitable for checking the tree emptiness, use \p empty()
1256             member function for that.
1257         */
1258         size_t size() const
1259         {
1260             return m_ItemCounter;
1261         }
1262
1263         /// Returns const reference to internal statistics
1264         stat const& statistics() const
1265         {
1266             return m_Stat;
1267         }
1268
1269         /// Checks internal consistency (not atomic, not thread-safe)
1270         /**
1271             The debugging function to check internal consistency of the tree.
1272         */
1273         bool check_consistency() const
1274         {
1275             return check_consistency( &m_Root );
1276         }
1277
1278     protected:
1279         //@cond
1280
1281         bool check_consistency( internal_node const * pRoot ) const
1282         {
1283             tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1284             tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1285             assert( pLeft );
1286             assert( pRight );
1287
1288             if ( node_compare()( *pLeft, *pRoot ) < 0
1289                 && node_compare()( *pRoot, *pRight ) <= 0
1290                 && node_compare()( *pLeft, *pRight ) < 0 )
1291             {
1292                 bool bRet = true;
1293                 if ( pLeft->is_internal() )
1294                     bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
1295                 assert( bRet );
1296
1297                 if ( bRet && pRight->is_internal() )
1298                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1299                 assert( bRet );
1300
1301                 return bRet;
1302             }
1303             return false;
1304         }
1305
1306         void help( update_ptr pUpdate, retired_list& rl )
1307         {
1308             /*
1309             switch ( pUpdate.bits() ) {
1310                 case update_desc::IFlag:
1311                     help_insert( pUpdate.ptr() );
1312                     m_Stat.onHelpInsert();
1313                     break;
1314                 case update_desc::DFlag:
1315                     //help_delete( pUpdate.ptr(), rl );
1316                     //m_Stat.onHelpDelete();
1317                     break;
1318                 case update_desc::Mark:
1319                     //help_marked( pUpdate.ptr() );
1320                     //m_Stat.onHelpMark();
1321                     break;
1322             }
1323             */
1324         }
1325
1326         void help_insert( update_desc * pOp )
1327         {
1328             assert( gc::is_locked() );
1329
1330             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1331             if ( pOp->iInfo.bRightLeaf ) {
1332                 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1333                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1334             }
1335             else {
1336                 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1337                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1338             }
1339
1340             update_ptr cur( pOp, update_desc::IFlag );
1341             pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1342                       memory_model::memory_order_release, atomics::memory_order_relaxed );
1343         }
1344
1345         bool check_delete_precondition( search_result& res )
1346         {
1347             assert( res.pGrandParent != nullptr );
1348
1349             return
1350                 static_cast<internal_node *>( res.bRightParent
1351                     ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1352                     : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1353                 ) == res.pParent
1354                 &&
1355                 static_cast<leaf_node *>( res.bRightLeaf
1356                     ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1357                     : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1358                 ) == res.pLeaf;
1359         }
1360
1361         bool help_delete( update_desc * pOp, retired_list& rl )
1362         {
1363             assert( gc::is_locked() );
1364
1365             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1366             update_ptr pMark( pOp, update_desc::Mark );
1367             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1368                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1369             {
1370                 help_marked( pOp );
1371                 retire_node( pOp->dInfo.pParent, rl );
1372                 // For extract operations the leaf should NOT be disposed
1373                 if ( pOp->dInfo.bDisposeLeaf )
1374                     retire_node( pOp->dInfo.pLeaf, rl );
1375                 retire_update_desc( pOp, rl, false );
1376
1377                 return true;
1378             }
1379             else if ( pUpdate == pMark ) {
1380                 // some other thread is processing help_marked()
1381                 help_marked( pOp );
1382                 m_Stat.onHelpMark();
1383                 return true;
1384             }
1385             else {
1386                 // pUpdate has been changed by CAS
1387                 help( pUpdate, rl );
1388
1389                 // Undo grandparent dInfo
1390                 update_ptr pDel( pOp, update_desc::DFlag );
1391                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1392                     memory_model::memory_order_release, atomics::memory_order_relaxed ))
1393                 {
1394                     retire_update_desc( pOp, rl, false );
1395                 }
1396                 return false;
1397             }
1398         }
1399
1400         void help_marked( update_desc * pOp )
1401         {
1402             assert( gc::is_locked() );
1403
1404             tree_node * p = pOp->dInfo.pParent;
1405             if ( pOp->dInfo.bRightParent ) {
1406                 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1407                     pOp->dInfo.bRightLeaf
1408                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1409                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1410                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1411             }
1412             else {
1413                 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1414                     pOp->dInfo.bRightLeaf
1415                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1416                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1417                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1418             }
1419
1420             update_ptr upd( pOp, update_desc::DFlag );
1421             pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1422                 memory_model::memory_order_release, atomics::memory_order_relaxed );
1423         }
1424
1425         template <typename KeyValue, typename Compare>
1426         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1427         {
1428             assert( gc::is_locked() );
1429
1430             internal_node * pParent;
1431             internal_node * pGrandParent = nullptr;
1432             tree_node *     pLeaf;
1433             update_ptr      updParent;
1434             update_ptr      updGrandParent;
1435             bool bRightLeaf;
1436             bool bRightParent = false;
1437
1438             int nCmp = 0;
1439
1440         retry:
1441             pParent = nullptr;
1442             pLeaf = const_cast<internal_node *>( &m_Root );
1443             updParent = nullptr;
1444             bRightLeaf = false;
1445             while ( pLeaf->is_internal() ) {
1446                 pGrandParent = pParent;
1447                 pParent = static_cast<internal_node *>( pLeaf );
1448                 bRightParent = bRightLeaf;
1449                 updGrandParent = updParent;
1450                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1451
1452                 switch ( updParent.bits() ) {
1453                     case update_desc::DFlag:
1454                     case update_desc::Mark:
1455                         m_Stat.onSearchRetry();
1456                         goto retry;
1457                 }
1458
1459                 nCmp = cmp( key, *pParent );
1460                 bRightLeaf = nCmp >= 0;
1461                 pLeaf = nCmp < 0 ? pParent->m_pLeft.load( memory_model::memory_order_acquire )
1462                                  : pParent->m_pRight.load( memory_model::memory_order_acquire );
1463             }
1464
1465             assert( pLeaf->is_leaf() );
1466             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1467
1468             res.pGrandParent    = pGrandParent;
1469             res.pParent         = pParent;
1470             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1471             res.updParent       = updParent;
1472             res.updGrandParent  = updGrandParent;
1473             res.bRightParent    = bRightParent;
1474             res.bRightLeaf      = bRightLeaf;
1475
1476             return nCmp == 0;
1477         }
1478
1479         bool search_min( search_result& res ) const
1480         {
1481             assert( gc::is_locked() );
1482
1483             internal_node * pParent;
1484             internal_node * pGrandParent = nullptr;
1485             tree_node *     pLeaf;
1486             update_ptr      updParent;
1487             update_ptr      updGrandParent;
1488
1489         retry:
1490             pParent = nullptr;
1491             pLeaf = const_cast<internal_node *>( &m_Root );
1492             while ( pLeaf->is_internal() ) {
1493                 pGrandParent = pParent;
1494                 pParent = static_cast<internal_node *>( pLeaf );
1495                 updGrandParent = updParent;
1496                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1497
1498                 switch ( updParent.bits() ) {
1499                     case update_desc::DFlag:
1500                     case update_desc::Mark:
1501                         m_Stat.onSearchRetry();
1502                         goto retry;
1503                 }
1504
1505                 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1506             }
1507
1508             if ( pLeaf->infinite_key())
1509                 return false;
1510
1511             res.pGrandParent    = pGrandParent;
1512             res.pParent         = pParent;
1513             assert( pLeaf->is_leaf() );
1514             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1515             res.updParent       = updParent;
1516             res.updGrandParent  = updGrandParent;
1517             res.bRightParent    = false;
1518             res.bRightLeaf      = false;
1519
1520             return true;
1521         }
1522
1523         bool search_max( search_result& res ) const
1524         {
1525             assert( gc::is_locked() );
1526
1527             internal_node * pParent;
1528             internal_node * pGrandParent = nullptr;
1529             tree_node *     pLeaf;
1530             update_ptr      updParent;
1531             update_ptr      updGrandParent;
1532             bool bRightLeaf;
1533             bool bRightParent = false;
1534
1535         retry:
1536             pParent = nullptr;
1537             pLeaf = const_cast<internal_node *>( &m_Root );
1538             bRightLeaf = false;
1539             while ( pLeaf->is_internal() ) {
1540                 pGrandParent = pParent;
1541                 pParent = static_cast<internal_node *>( pLeaf );
1542                 bRightParent = bRightLeaf;
1543                 updGrandParent = updParent;
1544                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1545
1546                 switch ( updParent.bits() ) {
1547                     case update_desc::DFlag:
1548                     case update_desc::Mark:
1549                         m_Stat.onSearchRetry();
1550                         goto retry;
1551                 }
1552
1553                 if ( pParent->infinite_key()) {
1554                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1555                     bRightLeaf = false;
1556                 }
1557                 else {
1558                     pLeaf = pParent->m_pRight.load( memory_model::memory_order_acquire );
1559                     bRightLeaf = true;
1560                 }
1561             }
1562
1563             if ( pLeaf->infinite_key())
1564                 return false;
1565
1566             res.pGrandParent    = pGrandParent;
1567             res.pParent         = pParent;
1568             assert( pLeaf->is_leaf() );
1569             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1570             res.updParent       = updParent;
1571             res.updGrandParent  = updGrandParent;
1572             res.bRightParent    = bRightParent;
1573             res.bRightLeaf      = bRightLeaf;
1574
1575             return true;
1576         }
1577
1578         template <typename Q, typename Compare, typename Equal, typename Func>
1579         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1580         {
1581             check_deadlock_policy::check();
1582
1583             retired_list updRetire;
1584             update_desc * pOp = nullptr;
1585             search_result res;
1586             back_off bkoff;
1587
1588             {
1589                 rcu_lock l;
1590                 for ( ;; ) {
1591                     if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1592                         if ( pOp )
1593                             retire_update_desc( pOp, updRetire, false );
1594                         m_Stat.onEraseFailed();
1595                         return false;
1596                     }
1597
1598                     if ( res.updGrandParent.bits() != update_desc::Clean )
1599                         help( res.updGrandParent, updRetire );
1600                     else if ( res.updParent.bits() != update_desc::Clean )
1601                         help( res.updParent, updRetire );
1602                     else {
1603                         if ( !pOp )
1604                             pOp = alloc_update_desc();
1605                         if ( check_delete_precondition( res ) ) {
1606                             pOp->dInfo.pGrandParent = res.pGrandParent;
1607                             pOp->dInfo.pParent = res.pParent;
1608                             pOp->dInfo.pLeaf = res.pLeaf;
1609                             pOp->dInfo.bDisposeLeaf = true;
1610                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1611                             pOp->dInfo.bRightParent = res.bRightParent;
1612                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1613
1614                             update_ptr updGP( res.updGrandParent.ptr() );
1615                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1616                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1617                             {
1618                                 if ( help_delete( pOp, updRetire )) {
1619                                     // res.pLeaf is not deleted yet since RCU is blocked
1620                                     f( *node_traits::to_value_ptr( res.pLeaf ));
1621                                     break;
1622                                 }
1623                                 pOp = nullptr;
1624                             }
1625                             else {
1626                                 // updGP has been changed by CAS
1627                                 help( updGP, updRetire );
1628                             }
1629                         }
1630                     }
1631
1632                     bkoff();
1633                     m_Stat.onEraseRetry();
1634                 }
1635             }
1636
1637             --m_ItemCounter;
1638             m_Stat.onEraseSuccess();
1639             return true;
1640         }
1641
1642         template <typename ExemptPtr, typename Q, typename Less>
1643         bool extract_with_( ExemptPtr& dest,  Q const& val, Less pred )
1644         {
1645             typedef ellen_bintree::details::compare<
1646                 key_type,
1647                 value_type,
1648                 opt::details::make_comparator_from_less<Less>,
1649                 node_traits
1650             > compare_functor;
1651
1652             return extract_( dest, val, compare_functor() );
1653         }
1654
1655         template <typename ExemptPtr, typename Q, typename Compare>
1656         bool extract_( ExemptPtr& ptr, Q const& val, Compare cmp )
1657         {
1658             check_deadlock_policy::check();
1659
1660             retired_list updRetire;
1661             update_desc * pOp = nullptr;
1662             search_result res;
1663             back_off bkoff;
1664
1665             {
1666                 rcu_lock l;
1667                 for ( ;; ) {
1668                     if ( !search( res, val, cmp ) ) {
1669                         if ( pOp )
1670                             retire_update_desc( pOp, updRetire, false );
1671                         m_Stat.onEraseFailed();
1672                         return false;
1673                     }
1674
1675                     if ( res.updGrandParent.bits() != update_desc::Clean )
1676                         help( res.updGrandParent, updRetire );
1677                     else if ( res.updParent.bits() != update_desc::Clean )
1678                         help( res.updParent, updRetire );
1679                     else {
1680                         if ( !pOp )
1681                             pOp = alloc_update_desc();
1682                         if ( check_delete_precondition( res )) {
1683                             pOp->dInfo.pGrandParent = res.pGrandParent;
1684                             pOp->dInfo.pParent = res.pParent;
1685                             pOp->dInfo.pLeaf = res.pLeaf;
1686                             pOp->dInfo.bDisposeLeaf = false;
1687                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1688                             pOp->dInfo.bRightParent = res.bRightParent;
1689                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1690
1691                             update_ptr updGP( res.updGrandParent.ptr() );
1692                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1693                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1694                             {
1695                                 if ( help_delete( pOp, updRetire )) {
1696                                     ptr = node_traits::to_value_ptr( res.pLeaf );
1697                                     break;
1698                                 }
1699                                 pOp = nullptr;
1700                             }
1701                             else {
1702                                 // updGP has been changed by CAS
1703                                 help( updGP, updRetire );
1704                             }
1705                         }
1706                     }
1707
1708                     bkoff();
1709                     m_Stat.onEraseRetry();
1710                 }
1711             }
1712
1713             --m_ItemCounter;
1714             m_Stat.onEraseSuccess();
1715             return true;
1716         }
1717
1718
1719         template <typename ExemptPtr>
1720         bool extract_max_( ExemptPtr& result )
1721         {
1722             check_deadlock_policy::check();
1723
1724             retired_list updRetire;
1725             update_desc * pOp = nullptr;
1726             search_result res;
1727             back_off bkoff;
1728
1729             {
1730                 rcu_lock l;
1731                 for ( ;; ) {
1732                     if ( !search_max( res )) {
1733                         // Tree is empty
1734                         if ( pOp )
1735                             retire_update_desc( pOp, updRetire, false );
1736                         m_Stat.onExtractMaxFailed();
1737                         return false;
1738                     }
1739
1740                     if ( res.updGrandParent.bits() != update_desc::Clean )
1741                         help( res.updGrandParent, updRetire );
1742                     else if ( res.updParent.bits() != update_desc::Clean )
1743                         help( res.updParent, updRetire );
1744                     else {
1745                         if ( !pOp )
1746                             pOp = alloc_update_desc();
1747                         if ( check_delete_precondition( res ) ) {
1748                             pOp->dInfo.pGrandParent = res.pGrandParent;
1749                             pOp->dInfo.pParent = res.pParent;
1750                             pOp->dInfo.pLeaf = res.pLeaf;
1751                             pOp->dInfo.bDisposeLeaf = false;
1752                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1753                             pOp->dInfo.bRightParent = res.bRightParent;
1754                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1755
1756                             update_ptr updGP( res.updGrandParent.ptr() );
1757                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1758                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1759                             {
1760                                 if ( help_delete( pOp, updRetire )) {
1761                                     result = node_traits::to_value_ptr( res.pLeaf );
1762                                     break;
1763                                 }
1764                                 pOp = nullptr;
1765                             }
1766                             else {
1767                                 // updGP has been changed by CAS
1768                                 help( updGP, updRetire );
1769                             }
1770                         }
1771                     }
1772
1773                     bkoff();
1774                     m_Stat.onExtractMaxRetry();
1775                 }
1776             }
1777
1778             --m_ItemCounter;
1779             m_Stat.onExtractMaxSuccess();
1780             return true;
1781         }
1782
1783         template <typename ExemptPtr>
1784         bool extract_min_(ExemptPtr& result)
1785         {
1786             check_deadlock_policy::check();
1787
1788             retired_list updRetire;
1789             update_desc * pOp = nullptr;
1790             search_result res;
1791             back_off bkoff;
1792
1793             {
1794                 rcu_lock l;
1795                 for ( ;; ) {
1796                     if ( !search_min( res )) {
1797                         // Tree is empty
1798                         if ( pOp )
1799                             retire_update_desc( pOp, updRetire, false );
1800                         m_Stat.onExtractMinFailed();
1801                         return false;
1802                     }
1803
1804                     if ( res.updGrandParent.bits() != update_desc::Clean )
1805                         help( res.updGrandParent, updRetire );
1806                     else if ( res.updParent.bits() != update_desc::Clean )
1807                         help( res.updParent, updRetire );
1808                     else {
1809                         if ( !pOp )
1810                             pOp = alloc_update_desc();
1811                         if ( check_delete_precondition( res ) ) {
1812                             pOp->dInfo.pGrandParent = res.pGrandParent;
1813                             pOp->dInfo.pParent = res.pParent;
1814                             pOp->dInfo.pLeaf = res.pLeaf;
1815                             pOp->dInfo.bDisposeLeaf = false;
1816                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1817                             pOp->dInfo.bRightParent = res.bRightParent;
1818                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1819
1820                             update_ptr updGP( res.updGrandParent.ptr() );
1821                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1822                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1823                             {
1824                                 if ( help_delete( pOp, updRetire )) {
1825                                     result = node_traits::to_value_ptr( res.pLeaf );
1826                                     break;
1827                                 }
1828                                 pOp = nullptr;
1829                             }
1830                             else {
1831                                 // updGP has been changed by CAS
1832                                 help( updGP, updRetire );
1833                             }
1834                         }
1835                     }
1836
1837                     bkoff();
1838                     m_Stat.onExtractMinRetry();
1839                 }
1840             }
1841
1842             --m_ItemCounter;
1843             m_Stat.onExtractMinSuccess();
1844             return true;
1845         }
1846
1847         template <typename Q, typename Less, typename Func>
1848         bool find_with_( Q& val, Less pred, Func f ) const
1849         {
1850             typedef ellen_bintree::details::compare<
1851                 key_type,
1852                 value_type,
1853                 opt::details::make_comparator_from_less<Less>,
1854                 node_traits
1855             > compare_functor;
1856
1857             rcu_lock l;
1858             search_result    res;
1859             if ( search( res, val, compare_functor() )) {
1860                 assert( res.pLeaf );
1861                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1862
1863                 m_Stat.onFindSuccess();
1864                 return true;
1865             }
1866
1867             m_Stat.onFindFailed();
1868             return false;
1869         }
1870
1871         template <typename Q, typename Func>
1872         bool find_( Q& key, Func f ) const
1873         {
1874             rcu_lock l;
1875             search_result    res;
1876             if ( search( res, key, node_compare() )) {
1877                 assert( res.pLeaf );
1878                 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1879
1880                 m_Stat.onFindSuccess();
1881                 return true;
1882             }
1883
1884             m_Stat.onFindFailed();
1885             return false;
1886         }
1887
1888         template <typename Q, typename Compare>
1889         value_type * get_( Q const& key, Compare cmp ) const
1890         {
1891             assert( gc::is_locked());
1892
1893             search_result    res;
1894             if ( search( res, key, cmp )) {
1895                 m_Stat.onFindSuccess();
1896                 return node_traits::to_value_ptr( res.pLeaf );
1897             }
1898
1899             m_Stat.onFindFailed();
1900             return nullptr;
1901         }
1902
1903
1904         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1905         {
1906             assert( gc::is_locked() );
1907             assert( res.updParent.bits() == update_desc::Clean );
1908
1909             // check search result
1910             if ( static_cast<leaf_node *>( res.bRightLeaf
1911                 ? res.pParent->m_pRight.load( memory_model::memory_order_relaxed )
1912                 : res.pParent->m_pLeft.load( memory_model::memory_order_relaxed ) ) == res.pLeaf )
1913             {
1914                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1915
1916                 int nCmp = node_compare()( val, *res.pLeaf );
1917                 if ( nCmp < 0 ) {
1918                     if ( res.pGrandParent ) {
1919                         pNewInternal->infinite_key( 0 );
1920                         key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
1921                         assert( !res.pLeaf->infinite_key() );
1922                     }
1923                     else {
1924                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1925                         pNewInternal->infinite_key( 1 );
1926                     }
1927                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1928                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1929                 }
1930                 else {
1931                     assert( !res.pLeaf->is_internal() );
1932                     pNewInternal->infinite_key( 0 );
1933
1934                     key_extractor()( pNewInternal->m_Key, val );
1935                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1936                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1937                     assert( !res.pLeaf->infinite_key());
1938                 }
1939
1940                 update_desc * pOp = alloc_update_desc();
1941
1942                 pOp->iInfo.pParent = res.pParent;
1943                 pOp->iInfo.pNew = pNewInternal;
1944                 pOp->iInfo.pLeaf = res.pLeaf;
1945                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1946
1947                 update_ptr updCur( res.updParent.ptr() );
1948                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1949                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1950                 {
1951                     // do insert
1952                     help_insert( pOp );
1953                     retire_update_desc( pOp, updRetire, false );
1954                     return true;
1955                 }
1956                 else {
1957                     // updCur has been updated by CAS
1958                     help( updCur, updRetire );
1959                     retire_update_desc( pOp, updRetire, true );
1960                 }
1961             }
1962             return false;
1963         }
1964
1965         //@endcond
1966     };
1967
1968 }} // namespace cds::intrusive
1969
1970 #endif  // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H