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