cds/intrusive/ellen_bintree_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H
   4 #define CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H
   5
   6 #include <memory>
   7 #include <cds/intrusive/details/ellen_bintree_base.h>
   8 #include <cds/opt/compare.h>
   9 #include <cds/details/binary_functor_wrapper.h>
  10 #include <cds/urcu/details/check_deadlock.h>
  11 #include <cds/urcu/exempt_ptr.h>
  12
  13 namespace cds { namespace intrusive {
  14     //@cond
  15     namespace ellen_bintree {
  16
  17         template <class RCU>
  18         struct base_node<cds::urcu::gc<RCU> >: public basic_node
  19         {
  20             typedef basic_node base_class;
  21
  22             base_node * m_pNextRetired;
  23
  24             typedef cds::urcu::gc<RCU> gc       ;   ///< Garbage collector
  25
  26             /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node
  27             explicit base_node( bool bInternal )
  28                 : basic_node( bInternal ? internal : 0 )
  29                 , m_pNextRetired( nullptr )
  30             {}
  31         };
  32
  33     } // namespace ellen_bintree
  34     //@endcond
  35
  36     /// Ellen's et al binary search tree (RCU specialization)
  37     /** @ingroup cds_intrusive_map
  38         @ingroup cds_intrusive_tree
  39         @anchor cds_intrusive_EllenBinTree_rcu
  40
  41         Source:
  42             - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
  43
  44         %EllenBinTree is an unbalanced leaf-oriented binary search tree that implements the <i>set</i>
  45         abstract data type. Nodes maintains child pointers but not parent pointers.
  46         Every internal node has exactly two children, and all data of type \p T currently in
  47         the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
  48         operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
  49         may or may not be in the set. \p Key type is a subset of \p T type.
  50         There should be exactly defined a key extracting functor for converting object of type \p T to
  51         object of type \p Key.
  52
  53         Due to \p extract_min and \p extract_max member functions the \p %EllenBinTree can act as
  54         a <i>priority queue</i>. In this case you should provide unique compound key, for example,
  55         the priority value plus some uniformly distributed random value.
  56
  57         @attention 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         Instead of helping, when a thread encounters a concurrent operation it just spins waiting for
  62         the operation done. Such solution allows greatly simplify the implementation of tree.
  63
  64         <b>Template arguments</b>:
  65         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  66         - \p Key - key type, a subset of \p T
  67         - \p T - type to be stored in tree's leaf nodes. The type must be based on \p ellen_bintree::node
  68             (for \p ellen_bintree::base_hook) or it must have a member of type \p ellen_bintree::node
  69             (for \p ellen_bintree::member_hook).
  70         - \p Traits - tree traits, default is \p ellen_bintree::traits
  71             It is possible to declare option-based tree with \p ellen_bintree::make_traits metafunction
  72             instead of \p Traits template argument.
  73
  74         @note Before including <tt><cds/intrusive/ellen_bintree_rcu.h></tt> you should include appropriate RCU header file,
  75         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  76
  77         @anchor cds_intrusive_EllenBinTree_rcu_less
  78         <b>Predicate requirements</b>
  79
  80         \p Traits::less, \p Traits::compare and other predicates using with member fuctions should accept at least parameters
  81         of type \p T and \p Key in any combination.
  82         For example, for \p Foo struct with \p std::string key field the appropiate \p less functor is:
  83         \code
  84         struct Foo: public cds::intrusive::ellen_bintree::node< ... >
  85         {
  86             std::string m_strKey;
  87             ...
  88         };
  89
  90         struct less {
  91             bool operator()( Foo const& v1, Foo const& v2 ) const
  92             { return v1.m_strKey < v2.m_strKey ; }
  93
  94             bool operator()( Foo const& v, std::string const& s ) const
  95             { return v.m_strKey < s ; }
  96
  97             bool operator()( std::string const& s, Foo const& v ) const
  98             { return s < v.m_strKey ; }
  99
 100             // Support comparing std::string and char const *
 101             bool operator()( std::string const& s, char const * p ) const
 102             { return s.compare(p) < 0 ; }
 103
 104             bool operator()( Foo const& v, char const * p ) const
 105             { return v.m_strKey.compare(p) < 0 ; }
 106
 107             bool operator()( char const * p, std::string const& s ) const
 108             { return s.compare(p) > 0; }
 109
 110             bool operator()( char const * p, Foo const& v ) const
 111             { return v.m_strKey.compare(p) > 0; }
 112         };
 113         \endcode
 114
 115         @anchor cds_intrusive_EllenBinTree_usage
 116         <b>Usage</b>
 117
 118         Suppose we have the following Foo struct with string key type:
 119         \code
 120         struct Foo {
 121             std::string     m_strKey    ;   // The key
 122             //...                           // other non-key data
 123         };
 124         \endcode
 125
 126         We want to utilize RCU-based \p %cds::intrusive::EllenBinTree set for \p Foo data.
 127         We may use base hook or member hook. Consider base hook variant.
 128         First, we need deriving \p Foo struct from \p cds::intrusive::ellen_bintree::node:
 129         \code
 130         #include <cds/urcu/general_buffered.h>
 131         #include <cds/intrusive/ellen_bintree_rcu.h>
 132
 133         // RCU type we use
 134         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  gpb_rcu;
 135
 136         struct Foo: public cds::intrusive:ellen_bintree::node< gpb_rcu >
 137         {
 138             std::string     m_strKey    ;   // The key
 139             //...                           // other non-key data
 140         };
 141         \endcode
 142
 143         Second, we need to implement auxiliary structures and functors:
 144         - key extractor functor for extracting the key from \p Foo object.
 145             Such functor is necessary because the tree internal nodes store the keys.
 146         - \p less predicate. We want our set should accept \p std::string
 147             and <tt>char const *</tt> parameters for searching, so our \p less
 148             predicate will not be trivial, see below.
 149         - item counting feature: we want our set's \p size() member function
 150             returns actual item count.
 151
 152         \code
 153         // Key extractor functor
 154         struct my_key_extractor
 155         {
 156             void operator ()( std::string& key, Foo const& src ) const
 157             {
 158                 key = src.m_strKey;
 159             }
 160         };
 161
 162         // Less predicate
 163         struct my_less {
 164             bool operator()( Foo const& v1, Foo const& v2 ) const
 165             { return v1.m_strKey < v2.m_strKey ; }
 166
 167             bool operator()( Foo const& v, std::string const& s ) const
 168             { return v.m_strKey < s ; }
 169
 170             bool operator()( std::string const& s, Foo const& v ) const
 171             { return s < v.m_strKey ; }
 172
 173             // Support comparing std::string and char const *
 174             bool operator()( std::string const& s, char const * p ) const
 175             { return s.compare(p) < 0 ; }
 176
 177             bool operator()( Foo const& v, char const * p ) const
 178             { return v.m_strKey.compare(p) < 0 ; }
 179
 180             bool operator()( char const * p, std::string const& s ) const
 181             { return s.compare(p) > 0; }
 182
 183             bool operator()( char const * p, Foo const& v ) const
 184             { return v.m_strKey.compare(p) > 0; }
 185         };
 186
 187         // Tree traits for our set
 188         // It is necessary to specify only those typedefs that differ from
 189         // cds::intrusive::ellen_bintree::traits defaults.
 190         struct set_traits: public cds::intrusive::ellen_bintree::traits
 191         {
 192             typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > > hook;
 193             typedef my_key_extractor    key_extractor;
 194             typedef my_less             less;
 195             typedef cds::atomicity::item_counter item_counter;
 196         };
 197         \endcode
 198
 199         Now we declare \p %EllenBinTree set and use it:
 200         \code
 201         typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, set_traits >   set_type;
 202
 203         set_type    theSet;
 204         // ...
 205         \endcode
 206
 207         Instead of declaring \p set_traits type traits we can use option-based syntax with
 208         \p ellen_bintree::make_traits metafunction, for example:
 209         \code
 210         typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo,
 211             typename cds::intrusive::ellen_bintree::make_traits<
 212                 cds::opt::hook< cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> > >
 213                 ,cds::intrusive::ellen_bintree::key_extractor< my_key_extractor >
 214                 ,cds::opt::less< my_less >
 215                 ,cds::opt::item_counter< cds::atomicity::item_counter >
 216             >::type
 217         >   set_type2;
 218         \endcode
 219
 220         Functionally, \p set_type and \p set_type2 are equivalent.
 221
 222         <b>Member-hooked tree</b>
 223
 224         Sometimes, we cannot use base hook, for example, when the \p Foo structure is external.
 225         In such case we can use member hook feature.
 226         \code
 227         #include <cds/urcu/general_buffered.h>
 228         #include <cds/intrusive/ellen_bintree_rcu.h>
 229
 230         // Struct Foo is external and its declaration cannot be modified.
 231         struct Foo {
 232             std::string     m_strKey    ;   // The key
 233             //...                           // other non-key data
 234         };
 235
 236         // RCU type we use
 237         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  gpb_rcu;
 238
 239         // Foo wrapper
 240         struct MyFoo
 241         {
 242             Foo     m_foo;
 243             cds::intrusive:ellen_bintree::node< gpb_rcu >   set_hook;   // member hook
 244         };
 245
 246         // Key extractor functor
 247         struct member_key_extractor
 248         {
 249             void operator ()( std::string& key, MyFoo const& src ) const
 250             {
 251                 key = src.m_foo.m_strKey;
 252             }
 253         };
 254
 255         // Less predicate
 256         struct member_less {
 257             bool operator()( MyFoo const& v1, MyFoo const& v2 ) const
 258             { return v1.m_foo.m_strKey < v2.m_foo.m_strKey ; }
 259
 260             bool operator()( MyFoo const& v, std::string const& s ) const
 261             { return v.m_foo.m_strKey < s ; }
 262
 263             bool operator()( std::string const& s, MyFoo const& v ) const
 264             { return s < v.m_foo.m_strKey ; }
 265
 266             // Support comparing std::string and char const *
 267             bool operator()( std::string const& s, char const * p ) const
 268             { return s.compare(p) < 0 ; }
 269
 270             bool operator()( MyFoo const& v, char const * p ) const
 271             { return v.m_foo.m_strKey.compare(p) < 0 ; }
 272
 273             bool operator()( char const * p, std::string const& s ) const
 274             { return s.compare(p) > 0; }
 275
 276             bool operator()( char const * p, MyFoo const& v ) const
 277             { return v.m_foo.m_strKey.compare(p) > 0; }
 278         };
 279
 280         // Tree traits for our member-based set
 281         struct member_set_traits: public cds::intrusive::ellen_bintree::traits
 282         {
 283             cds::intrusive::ellen_bintree::member_hook< offsetof(MyFoo, set_hook), cds::opt::gc<gpb_rcu> > > hook;
 284             typedef member_key_extractor    key_extractor;
 285             typedef member_less             less;
 286             typedef cds::atomicity::item_counter item_counter;
 287         };
 288
 289         // Tree containing MyFoo objects
 290         typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, MyFoo, member_set_traits >   member_set_type;
 291
 292         member_set_type    theMemberSet;
 293         \endcode
 294
 295         <b>Multiple containers</b>
 296
 297         Sometimes we need that our \p Foo struct should be used in several different containers.
 298         Suppose, \p Foo struct has two key fields:
 299         \code
 300         struct Foo {
 301             std::string m_strKey    ;   // string key
 302             int         m_nKey      ;   // int key
 303             //...                       // other non-key data fields
 304         };
 305         \endcode
 306
 307         We want to build two intrusive \p %EllenBinTree sets: one indexed on \p Foo::m_strKey field,
 308         another indexed on \p Foo::m_nKey field. To decide such case we should use a tag option for
 309         tree's hook:
 310         \code
 311         #include <cds/urcu/general_buffered.h>
 312         #include <cds/intrusive/ellen_bintree_rcu.h>
 313
 314         // RCU type we use
 315         typedef cds::urcu::gc< cds::urcu::general_buffered<> >  gpb_rcu;
 316
 317         // Declare tag structs
 318         struct int_tag      ;   // int key tag
 319         struct string_tag   ;   // string key tag
 320
 321         // Foo struct is derived from two ellen_bintree::node class
 322         // with different tags
 323         struct Foo
 324             : public cds::intrusive::ellen_bintree::node< gpb_rcu, cds::opt::tag< string_tag > >
 325             , public cds::intrusive::ellen_bintree::node< gpb_rcu >, cds::opt::tag< int_tag >
 326         {
 327             std::string m_strKey    ;   // string key
 328             int         m_nKey      ;   // int key
 329             //...                       // other non-key data fields
 330         };
 331
 332         // String key extractor functor
 333         struct string_key_extractor
 334         {
 335             void operator ()( std::string& key, Foo const& src ) const
 336             {
 337                 key = src.m_strKey;
 338             }
 339         };
 340
 341         // Int key extractor functor
 342         struct int_key_extractor
 343         {
 344             void operator ()( int& key, Foo const& src ) const
 345             {
 346                 key = src.m_nKey;
 347             }
 348         };
 349
 350         // String less predicate
 351         struct string_less {
 352             bool operator()( Foo const& v1, Foo const& v2 ) const
 353             { return v1.m_strKey < v2.m_strKey ; }
 354
 355             bool operator()( Foo const& v, std::string const& s ) const
 356             { return v.m_strKey < s ; }
 357
 358             bool operator()( std::string const& s, Foo const& v ) const
 359             { return s < v.m_strKey ; }
 360
 361             // Support comparing std::string and char const *
 362             bool operator()( std::string const& s, char const * p ) const
 363             { return s.compare(p) < 0 ; }
 364
 365             bool operator()( Foo const& v, char const * p ) const
 366             { return v.m_strKey.compare(p) < 0 ; }
 367
 368             bool operator()( char const * p, std::string const& s ) const
 369             { return s.compare(p) > 0; }
 370
 371             bool operator()( char const * p, Foo const& v ) const
 372             { return v.m_strKey.compare(p) > 0; }
 373         };
 374
 375         // Int less predicate
 376         struct int_less {
 377             bool operator()( Foo const& v1, Foo const& v2 ) const
 378             { return v1.m_nKey < v2.m_nKey ; }
 379
 380             bool operator()( Foo const& v, int n ) const
 381             { return v.m_nKey < n ; }
 382
 383             bool operator()( int n, Foo const& v ) const
 384             { return n < v.m_nKey ; }
 385         };
 386
 387         // Type traits for string-indexed set
 388         struct string_set_traits: public cds::intrusive::ellen_bintree::traits
 389         {
 390             typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< string_tag > > hook;
 391             typedef string_key_extractor    key_extractor;
 392             typedef string_less             less;
 393             typedef cds::atomicity::item_counter item_counter;
 394         };
 395
 396         // Type traits for int-indexed set
 397         struct int_set_traits: public cds::intrusive::ellen_bintree::traits
 398         {
 399             typedef cds::intrusive::ellen_bintree::base_hook< cds::opt::gc<gpb_rcu> >, cds::opt::tag< int_tag > > hook;
 400             typedef int_key_extractor    key_extractor;
 401             typedef int_less             less;
 402             typedef cds::atomicity::item_counter item_counter;
 403         };
 404
 405         // Declare string-indexed set
 406         typedef cds::intrusive::EllenBinTree< gpb_rcu, std::string, Foo, string_set_traits >   string_set_type;
 407         string_set_type theStringSet;
 408
 409         // Declare int-indexed set
 410         typedef cds::intrusive::EllenBinTree< gpb_rcu, int, Foo, int_set_traits >   int_set_type;
 411         int_set_type    theIntSet;
 412
 413         // Now we can use theStringSet and theIntSet in our program
 414         // ...
 415         \endcode
 416     */
 417     template < class RCU,
 418         typename Key,
 419         typename T,
 420 #ifdef CDS_DOXYGEN_INVOKED
 421         class Traits = ellen_bintree::traits
 422 #else
 423         class Traits
 424 #endif
 425     >
 426     class EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
 427     {
 428     public:
 429         typedef cds::urcu::gc<RCU>  gc;   ///< RCU Garbage collector
 430         typedef Key     key_type;         ///< type of a key stored in internal nodes; key is a part of \p value_type
 431         typedef T       value_type;       ///< type of value stored in the binary tree
 432         typedef Traits  traits;           ///< Traits template parameter
 433
 434         typedef typename traits::hook    hook;      ///< hook type
 435         typedef typename hook::node_type node_type; ///< node type
 436
 437         typedef typename traits::disposer disposer;   ///< leaf node disposer
 438         typedef typename traits::back_off back_off;   ///< back-off strategy
 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         using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >; ///< 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 \p 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             back_off bkoff;
 738
 739             {
 740                 rcu_lock l;
 741
 742                 search_result res;
 743                 for ( ;; ) {
 744                     if ( search( res, val, node_compare())) {
 745                         if ( pNewInternal.get())
 746                             m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 747                         m_Stat.onInsertFailed();
 748                         return false;
 749                     }
 750
 751                     if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
 752                         if ( !pNewInternal.get())
 753                             pNewInternal.reset( alloc_internal_node());
 754
 755                         if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
 756                             f( val );
 757                             pNewInternal.release()  ;   // internal node is linked into the tree and should not be deleted
 758                             break;
 759                         }
 760                     }
 761                     else
 762                         help( res.updParent, updRetire );
 763
 764                     bkoff();
 765                     m_Stat.onInsertRetry();
 766                 }
 767             }
 768
 769             ++m_ItemCounter;
 770             m_Stat.onInsertSuccess();
 771
 772             return true;
 773         }
 774
 775         /// Updates the node
 776         /**
 777             The operation performs inserting or changing data with lock-free manner.
 778
 779             If the item \p val is not found in the set, then \p val is inserted into the set
 780             iff \p bAllowInsert is \p true.
 781             Otherwise, the functor \p func is called with item found.
 782             The functor \p func 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 set
 789             - \p val - argument \p val passed into the \p %update() 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 std::pair<bool, bool> where \p first is \p true if operation is successfull,
 799             i.e. the node has been inserted or updated,
 800             \p second is \p true if new item has been added or \p false if the item with \p key
 801             already exists.
 802
 803             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 804         */
 805         template <typename Func>
 806         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 807         {
 808             check_deadlock_policy::check();
 809
 810             unique_internal_node_ptr pNewInternal;
 811             retired_list updRetire;
 812             back_off bkoff;
 813
 814             {
 815                 rcu_lock l;
 816
 817                 search_result res;
 818                 for ( ;; ) {
 819                     if ( search( res, val, node_compare())) {
 820                         func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
 821                         if ( pNewInternal.get())
 822                             m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 823                         m_Stat.onEnsureExist();
 824                         return std::make_pair( true, false );
 825                     }
 826
 827                     if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
 828                         if ( !bAllowInsert )
 829                             return std::make_pair( false, false );
 830
 831                         if ( !pNewInternal.get())
 832                             pNewInternal.reset( alloc_internal_node());
 833
 834                         if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
 835                             func( true, val, val );
 836                             pNewInternal.release()  ;   // internal node is linked into the tree and should not be deleted
 837                             break;
 838                         }
 839                     }
 840                     else
 841                         help( res.updParent, updRetire );
 842
 843                     bkoff();
 844                     m_Stat.onEnsureRetry();
 845                 }
 846             }
 847
 848             ++m_ItemCounter;
 849             m_Stat.onEnsureNew();
 850
 851             return std::make_pair( true, true );
 852         }
 853         //@cond
 854         template <typename Func>
 855         CDS_DEPRECATED("ensure() is deprecated, use update()")
 856         std::pair<bool, bool> ensure( value_type& val, Func func )
 857         {
 858             return update( val, func, true );
 859         }
 860         //@endcond
 861
 862         /// Unlinks the item \p val from the tree
 863         /**
 864             The function searches the item \p val in the tree and unlink it from the tree
 865             if it is found and is equal to \p val.
 866
 867             Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
 868             and deletes the item found. \p %unlink() finds an item by key and deletes it
 869             only if \p val is an item of the tree, i.e. the pointer to item found
 870             is equal to <tt> &val </tt>.
 871
 872             RCU \p synchronize method can be called. RCU should not be locked.
 873
 874             The \ref disposer specified in \p Traits class template parameter is called
 875             by garbage collector \p GC asynchronously.
 876
 877             The function returns \p true if success and \p false otherwise.
 878         */
 879         bool unlink( value_type& val )
 880         {
 881             return erase_( val, node_compare(),
 882                 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
 883                 [](value_type const&) {} );
 884         }
 885
 886         /// Deletes the item from the tree
 887         /** \anchor cds_intrusive_EllenBinTree_rcu_erase
 888             The function searches an item with key equal to \p key in the tree,
 889             unlinks it from the tree, and returns \p true.
 890             If the item with key equal to \p key is not found the function return \p false.
 891
 892             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 893
 894             RCU \p synchronize method can be called. RCU should not be locked.
 895         */
 896         template <typename Q>
 897         bool erase( const Q& key )
 898         {
 899             return erase_( key, node_compare(),
 900                 []( Q const&, leaf_node const& ) -> bool { return true; },
 901                 [](value_type const&) {} );
 902         }
 903
 904         /// Delete the item from the tree with comparing functor \p pred
 905         /**
 906             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
 907             but \p pred predicate is used for key comparing.
 908             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 909             "Predicate requirements".
 910             \p pred must imply the same element order as the comparator used for building the tree.
 911         */
 912         template <typename Q, typename Less>
 913         bool erase_with( const Q& key, Less pred )
 914         {
 915             CDS_UNUSED( pred );
 916             typedef ellen_bintree::details::compare<
 917                 key_type,
 918                 value_type,
 919                 opt::details::make_comparator_from_less<Less>,
 920                 node_traits
 921             > compare_functor;
 922
 923             return erase_( key, compare_functor(),
 924                 []( Q const&, leaf_node const& ) -> bool { return true; },
 925                 [](value_type const&) {} );
 926         }
 927
 928         /// Deletes the item from the tree
 929         /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
 930             The function searches an item with key equal to \p key in the tree,
 931             call \p f functor with item found, unlinks it from the tree, and returns \p true.
 932             The \ref disposer specified in \p Traits class template parameter is called
 933             by garbage collector \p GC asynchronously.
 934
 935             The \p Func interface is
 936             \code
 937             struct functor {
 938                 void operator()( value_type const& item );
 939             };
 940             \endcode
 941
 942             If the item with key equal to \p key is not found the function return \p false.
 943
 944             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 945
 946             RCU \p synchronize method can be called. RCU should not be locked.
 947         */
 948         template <typename Q, typename Func>
 949         bool erase( Q const& key, Func f )
 950         {
 951             return erase_( key, node_compare(),
 952                 []( Q const&, leaf_node const& ) -> bool { return true; },
 953                 f );
 954         }
 955
 956         /// Delete the item from the tree with comparing functor \p pred
 957         /**
 958             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
 959             but \p pred predicate is used for key comparing.
 960             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 961             "Predicate requirements".
 962             \p pred must imply the same element order as the comparator used for building the tree.
 963         */
 964         template <typename Q, typename Less, typename Func>
 965         bool erase_with( Q const& key, Less pred, Func f )
 966         {
 967             CDS_UNUSED( pred );
 968             typedef ellen_bintree::details::compare<
 969                 key_type,
 970                 value_type,
 971                 opt::details::make_comparator_from_less<Less>,
 972                 node_traits
 973             > compare_functor;
 974
 975             return erase_( key, compare_functor(),
 976                 []( Q const&, leaf_node const& ) -> bool { return true; },
 977                 f );
 978         }
 979
 980         /// Extracts an item with minimal key from the tree
 981         /**
 982             The function searches an item with minimal key, unlinks it, and returns
 983             \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
 984             If the tree is empty the function returns empty \p exempt_ptr.
 985
 986             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
 987             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 988             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 989             So, the function returns the item with minimum key at the moment of tree traversing.
 990
 991             RCU \p synchronize method can be called. RCU should NOT be locked.
 992             The function does not call the disposer for the item found.
 993             The disposer will be implicitly invoked when the returned object is destroyed or when
 994             its \p release() member function is called.
 995         */
 996         exempt_ptr extract_min()
 997         {
 998             return exempt_ptr( extract_min_());
 999         }
1000
1001         /// Extracts an item with maximal key from the tree
1002         /**
1003             The function searches an item with maximal key, unlinks it, and returns
1004             \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
1005             If the tree is empty the function returns empty \p exempt_ptr.
1006
1007             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
1008             It means that the function gets rightmost leaf of the tree and tries to unlink it.
1009             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
1010             So, the function returns the item with maximum key at the moment of tree traversing.
1011
1012             RCU \p synchronize method can be called. RCU should NOT be locked.
1013             The function does not call the disposer for the item found.
1014             The disposer will be implicitly invoked when the returned object is destroyed or when
1015             its \p release() member function is called.
1016         */
1017         exempt_ptr extract_max()
1018         {
1019             return exempt_ptr( extract_max_());
1020         }
1021
1022         /// Extracts an item from the tree
1023         /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1024             The function searches an item with key equal to \p key in the tree,
1025             unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
1026             If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr.
1027
1028             RCU \p synchronize method can be called. RCU should NOT be locked.
1029             The function does not call the disposer for the item found.
1030             The disposer will be implicitly invoked when the returned object is destroyed or when
1031             its \p release() member function is called.
1032         */
1033         template <typename Q>
1034         exempt_ptr extract( Q const& key )
1035         {
1036             return exempt_ptr( extract_( key, node_compare()));
1037         }
1038
1039         /// Extracts an item from the set using \p pred for searching
1040         /**
1041             The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
1042             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1043             "predicate requirements".
1044             \p pred must imply the same element order as the comparator used for building the tree.
1045         */
1046         template <typename Q, typename Less>
1047         exempt_ptr extract_with( Q const& key, Less pred )
1048         {
1049             return exempt_ptr( extract_with_( key, pred ));
1050         }
1051
1052         /// Checks whether the set contains \p key
1053         /**
1054             The function searches the item with key equal to \p key
1055             and returns \p true if it is found, and \p false otherwise.
1056
1057             The function applies RCU lock internally.
1058         */
1059         template <typename Q>
1060         bool contains( Q const& key ) const
1061         {
1062             rcu_lock l;
1063             search_result    res;
1064             if ( search( res, key, node_compare())) {
1065                 m_Stat.onFindSuccess();
1066                 return true;
1067             }
1068
1069             m_Stat.onFindFailed();
1070             return false;
1071         }
1072         //@cond
1073         template <typename Q>
1074         CDS_DEPRECATED("deprecated, use contains()")
1075         bool find( Q const& key ) const
1076         {
1077             return contains( key );
1078         }
1079         //@endcond
1080
1081         /// Checks whether the set contains \p key using \p pred predicate for searching
1082         /**
1083             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1084             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1085             "Predicate requirements".
1086             \p Less must imply the same element order as the comparator used for building the set.
1087             \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1088         */
1089         template <typename Q, typename Less>
1090         bool contains( Q const& key, Less pred ) const
1091         {
1092             CDS_UNUSED( pred );
1093             typedef ellen_bintree::details::compare<
1094                 key_type,
1095                 value_type,
1096                 opt::details::make_comparator_from_less<Less>,
1097                 node_traits
1098             > compare_functor;
1099
1100             rcu_lock l;
1101             search_result    res;
1102             if ( search( res, key, compare_functor())) {
1103                 m_Stat.onFindSuccess();
1104                 return true;
1105             }
1106             m_Stat.onFindFailed();
1107             return false;
1108         }
1109         //@cond
1110         template <typename Q, typename Less>
1111         CDS_DEPRECATED("deprecated, use contains()")
1112         bool find_with( Q const& key, Less pred ) const
1113         {
1114             return contains( key, pred );
1115         }
1116         //@endcond
1117
1118         /// Finds the key \p key
1119         /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1120             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1121             The interface of \p Func functor is:
1122             \code
1123             struct functor {
1124                 void operator()( value_type& item, Q& key );
1125             };
1126             \endcode
1127             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1128
1129             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1130             that \p item cannot be disposed during functor is executing.
1131             The functor does not serialize simultaneous access to the tree \p item. If such access is
1132             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1133
1134             The function applies RCU lock internally.
1135
1136             The function returns \p true if \p key is found, \p false otherwise.
1137         */
1138         template <typename Q, typename Func>
1139         bool find( Q& key, Func f ) const
1140         {
1141             return find_( key, f );
1142         }
1143         //@cond
1144         template <typename Q, typename Func>
1145         bool find( Q const& key, Func f ) const
1146         {
1147             return find_( key, f );
1148         }
1149         //@endcond
1150
1151         /// Finds the key \p key with comparing functor \p pred
1152         /**
1153             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1154             but \p pred is used for key comparison.
1155             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1156             "Predicate requirements".
1157             \p pred must imply the same element order as the comparator used for building the tree.
1158         */
1159         template <typename Q, typename Less, typename Func>
1160         bool find_with( Q& key, Less pred, Func f ) const
1161         {
1162             return find_with_( key, pred, f );
1163         }
1164         //@cond
1165         template <typename Q, typename Less, typename Func>
1166         bool find_with( Q const& key, Less pred, Func f ) const
1167         {
1168             return find_with_( key, pred, f );
1169         }
1170         //@endcond
1171
1172         /// Finds \p key and return the item found
1173         /** \anchor cds_intrusive_EllenBinTree_rcu_get
1174             The function searches the item with key equal to \p key and returns the pointer to item found.
1175             If \p key is not found it returns \p nullptr.
1176
1177             RCU should be locked before call the function.
1178             Returned pointer is valid while RCU is locked.
1179         */
1180         template <typename Q>
1181         value_type * get( Q const& key ) const
1182         {
1183             return get_( key, node_compare());
1184         }
1185
1186         /// Finds \p key with \p pred predicate and return the item found
1187         /**
1188             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1189             but \p pred is used for comparing the keys.
1190
1191             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1192             in any order.
1193             \p pred must imply the same element order as the comparator used for building the tree.
1194         */
1195         template <typename Q, typename Less>
1196         value_type * get_with( Q const& key, Less pred ) const
1197         {
1198             CDS_UNUSED( pred );
1199             typedef ellen_bintree::details::compare<
1200                 key_type,
1201                 value_type,
1202                 opt::details::make_comparator_from_less<Less>,
1203                 node_traits
1204             > compare_functor;
1205
1206             return get_( key, compare_functor());
1207         }
1208
1209         /// Checks if the tree is empty
1210         bool empty() const
1211         {
1212             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1213         }
1214
1215         /// Clears the tree (thread safe, not atomic)
1216         /**
1217             The function unlink all items from the tree.
1218             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1219             this sequence
1220             \code
1221             set.clear();
1222             assert( set.empty());
1223             \endcode
1224             the assertion could be raised.
1225
1226             For each leaf the \ref disposer will be called after unlinking.
1227
1228             RCU \p synchronize method can be called. RCU should not be locked.
1229         */
1230         void clear()
1231         {
1232             for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min())
1233                 ep.release();
1234         }
1235
1236         /// Clears the tree (not thread safe)
1237         /**
1238             This function is not thread safe and may be called only when no other thread deals with the tree.
1239             The function is used in the tree destructor.
1240         */
1241         void unsafe_clear()
1242         {
1243             rcu_lock l;
1244
1245             while ( true ) {
1246                 internal_node * pParent = nullptr;
1247                 internal_node * pGrandParent = nullptr;
1248                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
1249
1250                 // Get leftmost leaf
1251                 while ( pLeaf->is_internal()) {
1252                     pGrandParent = pParent;
1253                     pParent = static_cast<internal_node *>( pLeaf );
1254                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1255                 }
1256
1257                 if ( pLeaf->infinite_key()) {
1258                     // The tree is empty
1259                     return;
1260                 }
1261
1262                 // Remove leftmost leaf and its parent node
1263                 assert( pGrandParent );
1264                 assert( pParent );
1265                 assert( pLeaf->is_leaf());
1266
1267                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1268                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf )));
1269                 free_internal_node( pParent );
1270             }
1271         }
1272
1273         /// Returns item count in the tree
1274         /**
1275             Only leaf nodes containing user data are counted.
1276
1277             The value returned depends on item counter type provided by \p Traits template parameter.
1278             If it is \p atomicity::empty_item_counter this function always returns 0.
1279
1280             The function is not suitable for checking the tree emptiness, use \p empty()
1281             member function for that.
1282         */
1283         size_t size() const
1284         {
1285             return m_ItemCounter;
1286         }
1287
1288         /// Returns const reference to internal statistics
1289         stat const& statistics() const
1290         {
1291             return m_Stat;
1292         }
1293
1294         /// Checks internal consistency (not atomic, not thread-safe)
1295         /**
1296             The debugging function to check internal consistency of the tree.
1297         */
1298         bool check_consistency() const
1299         {
1300             return check_consistency( &m_Root );
1301         }
1302
1303     protected:
1304         //@cond
1305
1306         bool check_consistency( internal_node const * pRoot ) const
1307         {
1308             tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1309             tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1310             assert( pLeft );
1311             assert( pRight );
1312
1313             if ( node_compare()( *pLeft, *pRoot ) < 0
1314                 && node_compare()( *pRoot, *pRight ) <= 0
1315                 && node_compare()( *pLeft, *pRight ) < 0 )
1316             {
1317                 bool bRet = true;
1318                 if ( pLeft->is_internal())
1319                     bRet = check_consistency( static_cast<internal_node *>( pLeft ));
1320                 assert( bRet );
1321
1322                 if ( bRet && pRight->is_internal())
1323                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1324                 assert( bRet );
1325
1326                 return bRet;
1327             }
1328             return false;
1329         }
1330
1331         void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
1332         {
1333             /*
1334             switch ( pUpdate.bits()) {
1335                 case update_desc::IFlag:
1336                     help_insert( pUpdate.ptr());
1337                     m_Stat.onHelpInsert();
1338                     break;
1339                 case update_desc::DFlag:
1340                     //help_delete( pUpdate.ptr(), rl );
1341                     //m_Stat.onHelpDelete();
1342                     break;
1343                 case update_desc::Mark:
1344                     //help_marked( pUpdate.ptr());
1345                     //m_Stat.onHelpMark();
1346                     break;
1347             }
1348             */
1349         }
1350
1351         void help_insert( update_desc * pOp )
1352         {
1353             assert( gc::is_locked());
1354
1355             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1356             if ( pOp->iInfo.bRightLeaf ) {
1357                 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1358                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1359             }
1360             else {
1361                 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1362                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1363             }
1364
1365             update_ptr cur( pOp, update_desc::IFlag );
1366             pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1367                       memory_model::memory_order_release, atomics::memory_order_relaxed );
1368         }
1369
1370         bool check_delete_precondition( search_result& res )
1371         {
1372             assert( res.pGrandParent != nullptr );
1373
1374             return
1375                 static_cast<internal_node *>( res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1376              && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1377         }
1378
1379         bool help_delete( update_desc * pOp, retired_list& rl )
1380         {
1381             assert( gc::is_locked());
1382
1383             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1384             update_ptr pMark( pOp, update_desc::Mark );
1385             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1386                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1387             {
1388                 help_marked( pOp );
1389                 retire_node( pOp->dInfo.pParent, rl );
1390                 // For extract operations the leaf should NOT be disposed
1391                 if ( pOp->dInfo.bDisposeLeaf )
1392                     retire_node( pOp->dInfo.pLeaf, rl );
1393                 retire_update_desc( pOp, rl, false );
1394
1395                 return true;
1396             }
1397             else if ( pUpdate == pMark ) {
1398                 // some other thread is processing help_marked()
1399                 help_marked( pOp );
1400                 m_Stat.onHelpMark();
1401                 return true;
1402             }
1403             else {
1404                 // pUpdate has been changed by CAS
1405                 help( pUpdate, rl );
1406
1407                 // Undo grandparent dInfo
1408                 update_ptr pDel( pOp, update_desc::DFlag );
1409                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1410                     memory_model::memory_order_release, atomics::memory_order_relaxed ))
1411                 {
1412                     retire_update_desc( pOp, rl, false );
1413                 }
1414                 return false;
1415             }
1416         }
1417
1418         void help_marked( update_desc * pOp )
1419         {
1420             assert( gc::is_locked());
1421
1422             tree_node * p = pOp->dInfo.pParent;
1423             if ( pOp->dInfo.bRightParent ) {
1424                 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1425                     pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1426                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1427             }
1428             else {
1429                 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1430                     pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1431                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1432             }
1433
1434             update_ptr upd( pOp, update_desc::DFlag );
1435             pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1436                 memory_model::memory_order_release, atomics::memory_order_relaxed );
1437         }
1438
1439         template <typename KeyValue, typename Compare>
1440         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1441         {
1442             assert( gc::is_locked());
1443
1444             internal_node * pParent;
1445             internal_node * pGrandParent = nullptr;
1446             tree_node *     pLeaf;
1447             update_ptr      updParent;
1448             update_ptr      updGrandParent;
1449             bool bRightLeaf;
1450             bool bRightParent = false;
1451
1452             int nCmp = 0;
1453
1454         retry:
1455             pParent = nullptr;
1456             pLeaf = const_cast<internal_node *>( &m_Root );
1457             updParent = nullptr;
1458             bRightLeaf = false;
1459             while ( pLeaf->is_internal()) {
1460                 pGrandParent = pParent;
1461                 pParent = static_cast<internal_node *>( pLeaf );
1462                 bRightParent = bRightLeaf;
1463                 updGrandParent = updParent;
1464                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1465
1466                 switch ( updParent.bits()) {
1467                     case update_desc::DFlag:
1468                     case update_desc::Mark:
1469                         m_Stat.onSearchRetry();
1470                         goto retry;
1471                 }
1472
1473                 nCmp = cmp( key, *pParent );
1474                 bRightLeaf = nCmp >= 0;
1475                 pLeaf = pParent->get_child( nCmp >= 0, memory_model::memory_order_acquire );
1476             }
1477
1478             assert( pLeaf->is_leaf());
1479             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf));
1480
1481             res.pGrandParent    = pGrandParent;
1482             res.pParent         = pParent;
1483             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1484             res.updParent       = updParent;
1485             res.updGrandParent  = updGrandParent;
1486             res.bRightParent    = bRightParent;
1487             res.bRightLeaf      = bRightLeaf;
1488
1489             return nCmp == 0;
1490         }
1491
1492         bool search_min( search_result& res ) const
1493         {
1494             assert( gc::is_locked());
1495
1496             internal_node * pParent;
1497             internal_node * pGrandParent = nullptr;
1498             tree_node *     pLeaf;
1499             update_ptr      updParent;
1500             update_ptr      updGrandParent;
1501
1502         retry:
1503             pParent = nullptr;
1504             pLeaf = const_cast<internal_node *>( &m_Root );
1505             while ( pLeaf->is_internal()) {
1506                 pGrandParent = pParent;
1507                 pParent = static_cast<internal_node *>( pLeaf );
1508                 updGrandParent = updParent;
1509                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1510
1511                 switch ( updParent.bits()) {
1512                     case update_desc::DFlag:
1513                     case update_desc::Mark:
1514                         m_Stat.onSearchRetry();
1515                         goto retry;
1516                 }
1517
1518                 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1519             }
1520
1521             if ( pLeaf->infinite_key())
1522                 return false;
1523
1524             res.pGrandParent    = pGrandParent;
1525             res.pParent         = pParent;
1526             assert( pLeaf->is_leaf());
1527             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1528             res.updParent       = updParent;
1529             res.updGrandParent  = updGrandParent;
1530             res.bRightParent    = false;
1531             res.bRightLeaf      = false;
1532
1533             return true;
1534         }
1535
1536         bool search_max( search_result& res ) const
1537         {
1538             assert( gc::is_locked());
1539
1540             internal_node * pParent;
1541             internal_node * pGrandParent = nullptr;
1542             tree_node *     pLeaf;
1543             update_ptr      updParent;
1544             update_ptr      updGrandParent;
1545             bool bRightLeaf;
1546             bool bRightParent = false;
1547
1548         retry:
1549             pParent = nullptr;
1550             pLeaf = const_cast<internal_node *>( &m_Root );
1551             bRightLeaf = false;
1552             while ( pLeaf->is_internal()) {
1553                 pGrandParent = pParent;
1554                 pParent = static_cast<internal_node *>( pLeaf );
1555                 bRightParent = bRightLeaf;
1556                 updGrandParent = updParent;
1557                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1558
1559                 switch ( updParent.bits()) {
1560                     case update_desc::DFlag:
1561                     case update_desc::Mark:
1562                         m_Stat.onSearchRetry();
1563                         goto retry;
1564                 }
1565
1566                 bRightLeaf = !pParent->infinite_key();
1567                 pLeaf = pParent->get_child( bRightLeaf, memory_model::memory_order_acquire );
1568             }
1569
1570             if ( pLeaf->infinite_key())
1571                 return false;
1572
1573             res.pGrandParent    = pGrandParent;
1574             res.pParent         = pParent;
1575             assert( pLeaf->is_leaf());
1576             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1577             res.updParent       = updParent;
1578             res.updGrandParent  = updGrandParent;
1579             res.bRightParent    = bRightParent;
1580             res.bRightLeaf      = bRightLeaf;
1581
1582             return true;
1583         }
1584
1585         template <typename Q, typename Compare, typename Equal, typename Func>
1586         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1587         {
1588             check_deadlock_policy::check();
1589
1590             retired_list updRetire;
1591             update_desc * pOp = nullptr;
1592             search_result res;
1593             back_off bkoff;
1594
1595             {
1596                 rcu_lock l;
1597                 for ( ;; ) {
1598                     if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf )) {
1599                         if ( pOp )
1600                             retire_update_desc( pOp, updRetire, false );
1601                         m_Stat.onEraseFailed();
1602                         return false;
1603                     }
1604
1605                     if ( res.updGrandParent.bits() != update_desc::Clean )
1606                         help( res.updGrandParent, updRetire );
1607                     else if ( res.updParent.bits() != update_desc::Clean )
1608                         help( res.updParent, updRetire );
1609                     else {
1610                         if ( !pOp )
1611                             pOp = alloc_update_desc();
1612                         if ( check_delete_precondition( res )) {
1613                             pOp->dInfo.pGrandParent = res.pGrandParent;
1614                             pOp->dInfo.pParent = res.pParent;
1615                             pOp->dInfo.pLeaf = res.pLeaf;
1616                             pOp->dInfo.bDisposeLeaf = true;
1617                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1618                             pOp->dInfo.bRightParent = res.bRightParent;
1619                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1620
1621                             update_ptr updGP( res.updGrandParent.ptr());
1622                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1623                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1624                             {
1625                                 if ( help_delete( pOp, updRetire )) {
1626                                     // res.pLeaf is not deleted yet since RCU is blocked
1627                                     f( *node_traits::to_value_ptr( res.pLeaf ));
1628                                     break;
1629                                 }
1630                                 pOp = nullptr;
1631                             }
1632                             else {
1633                                 // updGP has been changed by CAS
1634                                 help( updGP, updRetire );
1635                             }
1636                         }
1637                     }
1638
1639                     bkoff();
1640                     m_Stat.onEraseRetry();
1641                 }
1642             }
1643
1644             --m_ItemCounter;
1645             m_Stat.onEraseSuccess();
1646             return true;
1647         }
1648
1649         template <typename Q, typename Less>
1650         value_type * extract_with_( Q const& val, Less /*pred*/ )
1651         {
1652             typedef ellen_bintree::details::compare<
1653                 key_type,
1654                 value_type,
1655                 opt::details::make_comparator_from_less<Less>,
1656                 node_traits
1657             > compare_functor;
1658
1659             return extract_( val, compare_functor());
1660         }
1661
1662         template <typename Q, typename Compare>
1663         value_type * extract_( Q const& val, Compare cmp )
1664         {
1665             check_deadlock_policy::check();
1666
1667             retired_list updRetire;
1668             update_desc * pOp = nullptr;
1669             search_result res;
1670             back_off bkoff;
1671             value_type * pResult;
1672
1673             {
1674                 rcu_lock l;
1675                 for ( ;; ) {
1676                     if ( !search( res, val, cmp )) {
1677                         if ( pOp )
1678                             retire_update_desc( pOp, updRetire, false );
1679                         m_Stat.onEraseFailed();
1680                         return nullptr;
1681                     }
1682
1683                     if ( res.updGrandParent.bits() != update_desc::Clean )
1684                         help( res.updGrandParent, updRetire );
1685                     else if ( res.updParent.bits() != update_desc::Clean )
1686                         help( res.updParent, updRetire );
1687                     else {
1688                         if ( !pOp )
1689                             pOp = alloc_update_desc();
1690                         if ( check_delete_precondition( res )) {
1691                             pOp->dInfo.pGrandParent = res.pGrandParent;
1692                             pOp->dInfo.pParent = res.pParent;
1693                             pOp->dInfo.pLeaf = res.pLeaf;
1694                             pOp->dInfo.bDisposeLeaf = false;
1695                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1696                             pOp->dInfo.bRightParent = res.bRightParent;
1697                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1698
1699                             update_ptr updGP( res.updGrandParent.ptr());
1700                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1701                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1702                             {
1703                                 if ( help_delete( pOp, updRetire )) {
1704                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1705                                     break;
1706                                 }
1707                                 pOp = nullptr;
1708                             }
1709                             else {
1710                                 // updGP has been changed by CAS
1711                                 help( updGP, updRetire );
1712                             }
1713                         }
1714                     }
1715
1716                     bkoff();
1717                     m_Stat.onEraseRetry();
1718                 }
1719             }
1720
1721             --m_ItemCounter;
1722             m_Stat.onEraseSuccess();
1723             return pResult;
1724         }
1725
1726
1727         value_type * extract_max_()
1728         {
1729             check_deadlock_policy::check();
1730
1731             retired_list updRetire;
1732             update_desc * pOp = nullptr;
1733             search_result res;
1734             back_off bkoff;
1735             value_type * pResult;
1736
1737             {
1738                 rcu_lock l;
1739                 for ( ;; ) {
1740                     if ( !search_max( res )) {
1741                         // Tree is empty
1742                         if ( pOp )
1743                             retire_update_desc( pOp, updRetire, false );
1744                         m_Stat.onExtractMaxFailed();
1745                         return nullptr;
1746                     }
1747
1748                     if ( res.updGrandParent.bits() != update_desc::Clean )
1749                         help( res.updGrandParent, updRetire );
1750                     else if ( res.updParent.bits() != update_desc::Clean )
1751                         help( res.updParent, updRetire );
1752                     else {
1753                         if ( !pOp )
1754                             pOp = alloc_update_desc();
1755                         if ( check_delete_precondition( res )) {
1756                             pOp->dInfo.pGrandParent = res.pGrandParent;
1757                             pOp->dInfo.pParent = res.pParent;
1758                             pOp->dInfo.pLeaf = res.pLeaf;
1759                             pOp->dInfo.bDisposeLeaf = false;
1760                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1761                             pOp->dInfo.bRightParent = res.bRightParent;
1762                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1763
1764                             update_ptr updGP( res.updGrandParent.ptr());
1765                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1766                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1767                             {
1768                                 if ( help_delete( pOp, updRetire )) {
1769                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1770                                     break;
1771                                 }
1772                                 pOp = nullptr;
1773                             }
1774                             else {
1775                                 // updGP has been changed by CAS
1776                                 help( updGP, updRetire );
1777                             }
1778                         }
1779                     }
1780
1781                     bkoff();
1782                     m_Stat.onExtractMaxRetry();
1783                 }
1784             }
1785
1786             --m_ItemCounter;
1787             m_Stat.onExtractMaxSuccess();
1788             return pResult;
1789         }
1790
1791         value_type * extract_min_()
1792         {
1793             check_deadlock_policy::check();
1794
1795             retired_list updRetire;
1796             update_desc * pOp = nullptr;
1797             search_result res;
1798             back_off bkoff;
1799             value_type * pResult;
1800
1801             {
1802                 rcu_lock l;
1803                 for ( ;; ) {
1804                     if ( !search_min( res )) {
1805                         // Tree is empty
1806                         if ( pOp )
1807                             retire_update_desc( pOp, updRetire, false );
1808                         m_Stat.onExtractMinFailed();
1809                         return nullptr;
1810                     }
1811
1812                     if ( res.updGrandParent.bits() != update_desc::Clean )
1813                         help( res.updGrandParent, updRetire );
1814                     else if ( res.updParent.bits() != update_desc::Clean )
1815                         help( res.updParent, updRetire );
1816                     else {
1817                         if ( !pOp )
1818                             pOp = alloc_update_desc();
1819                         if ( check_delete_precondition( res )) {
1820                             pOp->dInfo.pGrandParent = res.pGrandParent;
1821                             pOp->dInfo.pParent = res.pParent;
1822                             pOp->dInfo.pLeaf = res.pLeaf;
1823                             pOp->dInfo.bDisposeLeaf = false;
1824                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1825                             pOp->dInfo.bRightParent = res.bRightParent;
1826                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1827
1828                             update_ptr updGP( res.updGrandParent.ptr());
1829                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1830                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1831                             {
1832                                 if ( help_delete( pOp, updRetire )) {
1833                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1834                                     break;
1835                                 }
1836                                 pOp = nullptr;
1837                             }
1838                             else {
1839                                 // updGP has been changed by CAS
1840                                 help( updGP, updRetire );
1841                             }
1842                         }
1843                     }
1844
1845                     bkoff();
1846                     m_Stat.onExtractMinRetry();
1847                 }
1848             }
1849
1850             --m_ItemCounter;
1851             m_Stat.onExtractMinSuccess();
1852             return pResult;
1853         }
1854
1855         template <typename Q, typename Less, typename Func>
1856         bool find_with_( Q& val, Less /*pred*/, Func f ) const
1857         {
1858             typedef ellen_bintree::details::compare<
1859                 key_type,
1860                 value_type,
1861                 opt::details::make_comparator_from_less<Less>,
1862                 node_traits
1863             > compare_functor;
1864
1865             rcu_lock l;
1866             search_result    res;
1867             if ( search( res, val, compare_functor())) {
1868                 assert( res.pLeaf );
1869                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1870
1871                 m_Stat.onFindSuccess();
1872                 return true;
1873             }
1874
1875             m_Stat.onFindFailed();
1876             return false;
1877         }
1878
1879         template <typename Q, typename Func>
1880         bool find_( Q& key, Func f ) const
1881         {
1882             rcu_lock l;
1883             search_result    res;
1884             if ( search( res, key, node_compare())) {
1885                 assert( res.pLeaf );
1886                 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1887
1888                 m_Stat.onFindSuccess();
1889                 return true;
1890             }
1891
1892             m_Stat.onFindFailed();
1893             return false;
1894         }
1895
1896         template <typename Q, typename Compare>
1897         value_type * get_( Q const& key, Compare cmp ) const
1898         {
1899             assert( gc::is_locked());
1900
1901             search_result    res;
1902             if ( search( res, key, cmp )) {
1903                 m_Stat.onFindSuccess();
1904                 return node_traits::to_value_ptr( res.pLeaf );
1905             }
1906
1907             m_Stat.onFindFailed();
1908             return nullptr;
1909         }
1910
1911
1912         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1913         {
1914             assert( gc::is_locked());
1915             assert( res.updParent.bits() == update_desc::Clean );
1916
1917             // check search result
1918             if ( static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf ) {
1919                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1920
1921                 int nCmp = node_compare()( val, *res.pLeaf );
1922                 if ( nCmp < 0 ) {
1923                     if ( res.pGrandParent ) {
1924                         pNewInternal->infinite_key( 0 );
1925                         key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1926                         assert( !res.pLeaf->infinite_key());
1927                     }
1928                     else {
1929                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1930                         pNewInternal->infinite_key( 1 );
1931                     }
1932                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1933                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1934                 }
1935                 else {
1936                     assert( !res.pLeaf->is_internal());
1937                     pNewInternal->infinite_key( 0 );
1938
1939                     key_extractor()( pNewInternal->m_Key, val );
1940                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1941                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1942                     assert( !res.pLeaf->infinite_key());
1943                 }
1944
1945                 update_desc * pOp = alloc_update_desc();
1946
1947                 pOp->iInfo.pParent = res.pParent;
1948                 pOp->iInfo.pNew = pNewInternal;
1949                 pOp->iInfo.pLeaf = res.pLeaf;
1950                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1951
1952                 update_ptr updCur( res.updParent.ptr());
1953                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1954                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1955                 {
1956                     // do insert
1957                     help_insert( pOp );
1958                     retire_update_desc( pOp, updRetire, false );
1959                     return true;
1960                 }
1961                 else {
1962                     // updCur has been updated by CAS
1963                     help( updCur, updRetire );
1964                     retire_update_desc( pOp, updRetire, true );
1965                 }
1966             }
1967             return false;
1968         }
1969
1970         //@endcond
1971     };
1972
1973 }} // namespace cds::intrusive
1974
1975 #endif  // #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H