cds/intrusive/ellen_bintree_rcu.h

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