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