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