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 <cds/intrusive/details/ellen_bintree_base.h>
   7 #include <cds/opt/compare.h>
   8 #include <cds/ref.h>
   9 #include <cds/details/binary_functor_wrapper.h>
  10 #include <cds/urcu/details/check_deadlock.h>
  11 #include <cds/details/std/memory.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
 712 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 713         struct trivial_equal_functor {
 714             template <typename Q>
 715             bool operator()( Q const& , leaf_node const& ) const
 716             {
 717                 return true;
 718             }
 719         };
 720
 721         struct empty_insert_functor {
 722             void operator()( value_type& )
 723             {}
 724         };
 725 #   endif
 726 #   if !defined(CDS_CXX11_LAMBDA_SUPPORT) || (CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
 727         struct unlink_equal_functor {
 728             bool operator()( value_type const& v, leaf_node const& n ) const
 729             {
 730                 return &v == node_traits::to_value_ptr( n );
 731             }
 732         };
 733         struct empty_erase_functor  {
 734             void operator()( value_type const& )
 735             {}
 736         };
 737 #   endif
 738         //@endcond
 739
 740     public:
 741         /// Default constructor
 742         EllenBinTree()
 743         {
 744             static_assert( (!std::is_same< key_extractor, opt::none >::value), "The key extractor option must be specified" );
 745             make_empty_tree();
 746         }
 747
 748         /// Clears the tree
 749         ~EllenBinTree()
 750         {
 751             unsafe_clear();
 752         }
 753
 754         /// Inserts new node
 755         /**
 756             The function inserts \p val in the tree if it does not contain
 757             an item with key equal to \p val.
 758
 759             The function applies RCU lock internally.
 760
 761             Returns \p true if \p val is placed into the set, \p false otherwise.
 762         */
 763         bool insert( value_type& val )
 764         {
 765 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 766             return insert( val, []( value_type& ) {} );
 767 #   else
 768             return insert( val, empty_insert_functor() );
 769 #   endif
 770         }
 771
 772         /// Inserts new node
 773         /**
 774             This function is intended for derived non-intrusive containers.
 775
 776             The function allows to split creating of new item into two part:
 777             - create item with key only
 778             - insert new item into the tree
 779             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 780
 781             The functor signature is:
 782             \code
 783                 void func( value_type& val );
 784             \endcode
 785             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 786             \p val no any other changes could be made on this tree's item by concurrent threads.
 787             The user-defined functor is called only if the inserting is success and may be passed by reference
 788             using <tt>boost::ref</tt>
 789
 790             RCU \p synchronize method can be called. RCU should not be locked.
 791         */
 792         template <typename Func>
 793         bool insert( value_type& val, Func f )
 794         {
 795             check_deadlock_policy::check();
 796
 797             unique_internal_node_ptr pNewInternal;
 798             retired_list updRetire;
 799
 800             {
 801                 rcu_lock l;
 802
 803                 search_result res;
 804                 for ( ;; ) {
 805                     if ( search( res, val, node_compare() )) {
 806                         if ( pNewInternal.get() )
 807                             m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 808                         m_Stat.onInsertFailed();
 809                         return false;
 810                     }
 811
 812                     if ( res.updParent.bits() != update_desc::Clean )
 813                         help( res.updParent, updRetire );
 814                     else {
 815                         if ( !pNewInternal.get() )
 816                             pNewInternal.reset( alloc_internal_node() );
 817
 818                         if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
 819                             cds::unref(f)( val );
 820                             pNewInternal.release()  ;   // internal node is linked into the tree and should not be deleted
 821                             break;
 822                         }
 823                     }
 824
 825                     m_Stat.onInsertRetry();
 826                 }
 827             }
 828
 829             ++m_ItemCounter;
 830             m_Stat.onInsertSuccess();
 831
 832             return true;
 833         }
 834
 835         /// Ensures that the \p val exists in the tree
 836         /**
 837             The operation performs inserting or changing data with lock-free manner.
 838
 839             If the item \p val is not found in the tree, then \p val is inserted into the tree.
 840             Otherwise, the functor \p func is called with item found.
 841             The functor signature is:
 842             \code
 843                 void func( bool bNew, value_type& item, value_type& val );
 844             \endcode
 845             with arguments:
 846             - \p bNew - \p true if the item has been inserted, \p false otherwise
 847             - \p item - item of the tree
 848             - \p val - argument \p val passed into the \p ensure function
 849             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 850             refer to the same thing.
 851
 852             The functor can change non-key fields of the \p item; however, \p func must guarantee
 853             that during changing no any other modifications could be made on this item by concurrent threads.
 854
 855             You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 856
 857             RCU \p synchronize method can be called. RCU should not be locked.
 858
 859             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 860             \p second is \p true if new item has been added or \p false if the item with \p key
 861             already is in the tree.
 862         */
 863         template <typename Func>
 864         std::pair<bool, bool> ensure( value_type& val, Func func )
 865         {
 866             check_deadlock_policy::check();
 867
 868             unique_internal_node_ptr pNewInternal;
 869             retired_list updRetire;
 870
 871             {
 872                 rcu_lock l;
 873
 874                 search_result res;
 875                 for ( ;; ) {
 876                     if ( search( res, val, node_compare() )) {
 877                         cds::unref(func)( false, *node_traits::to_value_ptr( res.pLeaf ), val );
 878                         if ( pNewInternal.get() )
 879                             m_Stat.onInternalNodeDeleted() ;    // unique_internal_node_ptr deletes internal node
 880                         m_Stat.onEnsureExist();
 881                         return std::make_pair( true, false );
 882                     }
 883
 884                     if ( res.updParent.bits() != update_desc::Clean )
 885                         help( res.updParent, updRetire );
 886                     else {
 887                         if ( !pNewInternal.get() )
 888                             pNewInternal.reset( alloc_internal_node() );
 889
 890                         if ( try_insert( val, pNewInternal.get(), res, updRetire )) {
 891                             cds::unref(func)( true, val, val );
 892                             pNewInternal.release()  ;   // internal node is linked into the tree and should not be deleted
 893                             break;
 894                         }
 895                     }
 896                     m_Stat.onEnsureRetry();
 897                 }
 898             }
 899
 900             ++m_ItemCounter;
 901             m_Stat.onEnsureNew();
 902
 903             return std::make_pair( true, true );
 904         }
 905
 906         /// Unlinks the item \p val from the tree
 907         /**
 908             The function searches the item \p val in the tree and unlink it from the tree
 909             if it is found and is equal to \p val.
 910
 911             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 912             and deletes the item found. \p unlink finds an item by key and deletes it
 913             only if \p val is an item of the tree, i.e. the pointer to item found
 914             is equal to <tt> &val </tt>.
 915
 916             RCU \p synchronize method can be called. RCU should not be locked.
 917
 918             The \ref disposer specified in \p Traits class template parameter is called
 919             by garbage collector \p GC asynchronously.
 920
 921             The function returns \p true if success and \p false otherwise.
 922         */
 923         bool unlink( value_type& val )
 924         {
 925 #       if defined(CDS_CXX11_LAMBDA_SUPPORT) && !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
 926             // vc10 generates an error for the lambda - it sees cds::intrusive::node_traits but not class-defined node_traits
 927             return erase_( val, node_compare(),
 928                 []( value_type const& v, leaf_node const& n ) -> bool { return &v == node_traits::to_value_ptr( n ); },
 929                 [](value_type const&) {} );
 930 #       else
 931             return erase_( val, node_compare(), unlink_equal_functor(), empty_erase_functor() );
 932 #       endif
 933         }
 934
 935         /// Deletes the item from the tree
 936         /** \anchor cds_intrusive_EllenBinTree_rcu_erase
 937             The function searches an item with key equal to \p val in the tree,
 938             unlinks it from the tree, and returns \p true.
 939             If the item with key equal to \p val is not found the function return \p false.
 940
 941             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 942
 943             RCU \p synchronize method can be called. RCU should not be locked.
 944         */
 945         template <typename Q>
 946         bool erase( const Q& val )
 947         {
 948 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 949             return erase_( val, node_compare(),
 950                 []( Q const&, leaf_node const& ) -> bool { return true; },
 951                 [](value_type const&) {} );
 952 #       else
 953             return erase_( val, node_compare(), trivial_equal_functor(), empty_erase_functor() );
 954 #       endif
 955         }
 956
 957         /// Delete the item from the tree with comparing functor \p pred
 958         /**
 959             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
 960             but \p pred predicate is used for key comparing.
 961             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 962             "Predicate requirements".
 963             \p pred must imply the same element order as the comparator used for building the tree.
 964         */
 965         template <typename Q, typename Less>
 966         bool erase_with( const Q& val, Less pred )
 967         {
 968             typedef ellen_bintree::details::compare<
 969                 key_type,
 970                 value_type,
 971                 opt::details::make_comparator_from_less<Less>,
 972                 node_traits
 973             > compare_functor;
 974
 975 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 976             return erase_( val, compare_functor(),
 977                 []( Q const&, leaf_node const& ) -> bool { return true; },
 978                 [](value_type const&) {} );
 979 #       else
 980             return erase_( val, compare_functor(), trivial_equal_functor(), empty_erase_functor() );
 981 #       endif
 982         }
 983
 984         /// Deletes the item from the tree
 985         /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
 986             The function searches an item with key equal to \p val in the tree,
 987             call \p f functor with item found, unlinks it from the tree, and returns \p true.
 988             The \ref disposer specified in \p Traits class template parameter is called
 989             by garbage collector \p GC asynchronously.
 990
 991             The \p Func interface is
 992             \code
 993             struct functor {
 994                 void operator()( value_type const& item );
 995             };
 996             \endcode
 997             The functor can be passed by reference with <tt>boost:ref</tt>
 998
 999             If the item with key equal to \p val is not found the function return \p false.
1000
1001             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1002
1003             RCU \p synchronize method can be called. RCU should not be locked.
1004         */
1005         template <typename Q, typename Func>
1006         bool erase( Q const& val, Func f )
1007         {
1008 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1009             return erase_( val, node_compare(),
1010                 []( Q const&, leaf_node const& ) -> bool { return true; },
1011                 f );
1012 #       else
1013             return erase_( val, node_compare(), trivial_equal_functor(), f );
1014 #       endif
1015         }
1016
1017         /// Delete the item from the tree with comparing functor \p pred
1018         /**
1019             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
1020             but \p pred predicate is used for key comparing.
1021             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1022             "Predicate requirements".
1023             \p pred must imply the same element order as the comparator used for building the tree.
1024         */
1025         template <typename Q, typename Less, typename Func>
1026         bool erase_with( Q const& val, Less pred, Func f )
1027         {
1028             typedef ellen_bintree::details::compare<
1029                 key_type,
1030                 value_type,
1031                 opt::details::make_comparator_from_less<Less>,
1032                 node_traits
1033             > compare_functor;
1034
1035 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1036             return erase_( val, compare_functor(),
1037                 []( Q const&, leaf_node const& ) -> bool { return true; },
1038                 f );
1039 #       else
1040             return erase_( val, compare_functor(), trivial_equal_functor(), f );
1041 #       endif
1042         }
1043
1044         /// Extracts an item with minimal key from the tree
1045         /**
1046             The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p result parameter.
1047             If the tree is empty the function returns \p false.
1048
1049             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
1050             It means that the function gets leftmost leaf of the tree and tries to unlink it.
1051             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1052             So, the function returns the item with minimum key at the moment of tree traversing.
1053
1054             RCU \p synchronize method can be called. RCU should NOT be locked.
1055             The function does not call the disposer for the item found.
1056             The disposer will be implicitly invoked when \p result object is destroyed or when
1057             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1058             @note Before reusing \p result object you should call its \p release() method.
1059         */
1060         bool extract_min(exempt_ptr& result)
1061         {
1062             return extract_min_(result);
1063         }
1064
1065         /// Extracts an item with maximal key from the tree
1066         /**
1067             The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p result prameter.
1068             If the tree is empty the function returns \p false.
1069
1070             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
1071             It means that the function gets rightmost leaf of the tree and tries to unlink it.
1072             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
1073             So, the function returns the item with maximum key at the moment of tree traversing.
1074
1075             RCU \p synchronize method can be called. RCU should NOT be locked.
1076             The function does not call the disposer for the item found.
1077             The disposer will be implicitly invoked when \p result object is destroyed or when
1078             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1079             @note Before reusing \p result object you should call its \p release() method.
1080         */
1081         bool extract_max(exempt_ptr& result)
1082         {
1083             return extract_max_(result);
1084         }
1085
1086         /// Extracts an item from the tree
1087         /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1088             The function searches an item with key equal to \p key in the tree,
1089             unlinks it, and returns pointer to an item found in \p result parameter.
1090             If the item with the key equal to \p key is not found the function returns \p false.
1091
1092             RCU \p synchronize method can be called. RCU should NOT be locked.
1093             The function does not call the disposer for the item found.
1094             The disposer will be implicitly invoked when \p result object is destroyed or when
1095             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1096             @note Before reusing \p result object you should call its \p release() method.
1097         */
1098         template <typename Q>
1099         bool extract( exempt_ptr& result, Q const& key )
1100         {
1101             return extract_( result, key, node_compare() );
1102         }
1103
1104         /// Extracts an item from the set using \p pred for searching
1105         /**
1106             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_extract "extract(exempt_ptr&, Q const&)"
1107             but \p pred is used for key compare.
1108             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1109             "predicate requirements".
1110             \p pred must imply the same element order as the comparator used for building the tree.
1111         */
1112         template <typename Q, typename Less>
1113         bool extract_with( exempt_ptr& dest,  Q const& val, Less pred )
1114         {
1115             return extract_with_( dest, val, pred );
1116         }
1117
1118         /// Finds the key \p val
1119         /** @anchor cds_intrusive_EllenBinTree_rcu_find_val
1120             The function searches the item with key equal to \p val
1121             and returns \p true if it is found, and \p false otherwise.
1122
1123             Note the hash functor specified for class \p Traits template parameter
1124             should accept a parameter of type \p Q that can be not the same as \p value_type.
1125
1126             The function applies RCU lock internally.
1127         */
1128         template <typename Q>
1129         bool find( Q const& val ) const
1130         {
1131             rcu_lock l;
1132             search_result    res;
1133             if ( search( res, val, node_compare() )) {
1134                 m_Stat.onFindSuccess();
1135                 return true;
1136             }
1137
1138             m_Stat.onFindFailed();
1139             return false;
1140         }
1141
1142         /// Finds the key \p val with comparing functor \p pred
1143         /**
1144             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_val "find(Q const&)"
1145             but \p pred is used for key compare.
1146             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1147             "Predicate requirements".
1148             \p pred must imply the same element order as the comparator used for building the tree.
1149             \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1150         */
1151         template <typename Q, typename Less>
1152         bool find_with( Q const& val, Less pred ) const
1153         {
1154             typedef ellen_bintree::details::compare<
1155                 key_type,
1156                 value_type,
1157                 opt::details::make_comparator_from_less<Less>,
1158                 node_traits
1159             > compare_functor;
1160
1161             rcu_lock l;
1162             search_result    res;
1163             if ( search( res, val, compare_functor() )) {
1164                 m_Stat.onFindSuccess();
1165                 return true;
1166             }
1167             m_Stat.onFindFailed();
1168             return false;
1169         }
1170
1171         /// Finds the key \p val
1172         /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1173             The function searches the item with key equal to \p val and calls the functor \p f for item found.
1174             The interface of \p Func functor is:
1175             \code
1176             struct functor {
1177                 void operator()( value_type& item, Q& val );
1178             };
1179             \endcode
1180             where \p item is the item found, \p val is the <tt>find</tt> function argument.
1181
1182             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1183
1184             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1185             that \p item cannot be disposed during functor is executing.
1186             The functor does not serialize simultaneous access to the tree \p item. If such access is
1187             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1188
1189             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
1190             can modify both arguments.
1191
1192             The function applies RCU lock internally.
1193
1194             The function returns \p true if \p val is found, \p false otherwise.
1195         */
1196         template <typename Q, typename Func>
1197         bool find( Q& val, Func f ) const
1198         {
1199             return find_( val, f );
1200         }
1201
1202         /// Finds the key \p val with comparing functor \p pred
1203         /**
1204             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1205             but \p pred is used for key comparison.
1206             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1207             "Predicate requirements".
1208             \p pred must imply the same element order as the comparator used for building the tree.
1209         */
1210         template <typename Q, typename Less, typename Func>
1211         bool find_with( Q& val, Less pred, Func f ) const
1212         {
1213             return find_with_( val, pred, f );
1214         }
1215
1216         /// Finds the key \p val
1217         /** @anchor cds_intrusive_EllenBinTree_rcu_find_cfunc
1218             The function searches the item with key equal to \p val and calls the functor \p f for item found.
1219             The interface of \p Func functor is:
1220             \code
1221             struct functor {
1222                 void operator()( value_type& item, Q const& val );
1223             };
1224             \endcode
1225             where \p item is the item found, \p val is the <tt>find</tt> function argument.
1226
1227             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1228
1229             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1230             that \p item cannot be disposed during functor is executing.
1231             The functor does not serialize simultaneous access to the tree \p item. If such access is
1232             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1233
1234             The function applies RCU lock internally.
1235
1236             The function returns \p true if \p val is found, \p false otherwise.
1237         */
1238         template <typename Q, typename Func>
1239         bool find( Q const& val, Func f ) const
1240         {
1241             return find_( val, f );
1242         }
1243
1244         /// Finds the key \p val with comparing functor \p pred
1245         /**
1246             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_cfunc "find(Q const&, Func)"
1247             but \p pred is used for key compare.
1248             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1249             "Predicate requirements".
1250             \p pred must imply the same element order as the comparator used for building the tree.
1251         */
1252         template <typename Q, typename Less, typename Func>
1253         bool find_with( Q const& val, Less pred, Func f ) const
1254         {
1255             return find_with_( val, pred, f );
1256         }
1257
1258         /// Finds \p key and return the item found
1259         /** \anchor cds_intrusive_EllenBinTree_rcu_get
1260             The function searches the item with key equal to \p key and returns the pointer to item found.
1261             If \p key is not found it returns \p NULL.
1262
1263             RCU should be locked before call the function.
1264             Returned pointer is valid while RCU is locked.
1265         */
1266         template <typename Q>
1267         value_type * get( Q const& key ) const
1268         {
1269             return get_( key, node_compare() );
1270         }
1271
1272         /// Finds \p key with \p pred predicate and return the item found
1273         /**
1274             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1275             but \p pred is used for comparing the keys.
1276
1277             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1278             in any order.
1279             \p pred must imply the same element order as the comparator used for building the tree.
1280         */
1281         template <typename Q, typename Less>
1282         value_type * get_with( Q const& key, Less pred ) const
1283         {
1284             typedef ellen_bintree::details::compare<
1285                 key_type,
1286                 value_type,
1287                 opt::details::make_comparator_from_less<Less>,
1288                 node_traits
1289             > compare_functor;
1290
1291             return get_( key, compare_functor());
1292         }
1293
1294         /// Checks if the tree is empty
1295         bool empty() const
1296         {
1297             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1298         }
1299
1300         /// Clears the tree (thread safe, non-atomic)
1301         /**
1302             The function unlink all items from the tree.
1303             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1304             this sequence
1305             \code
1306             set.clear();
1307             assert( set.empty() );
1308             \endcode
1309             the assertion could be raised.
1310
1311             For each leaf the \ref disposer will be called after unlinking.
1312
1313             RCU \p synchronize method can be called. RCU should not be locked.
1314         */
1315         void clear()
1316         {
1317             exempt_ptr ep;
1318             while ( extract_min(ep) )
1319                 ep.release();
1320         }
1321
1322         /// Clears the tree (not thread safe)
1323         /**
1324             This function is not thread safe and may be called only when no other thread deals with the tree.
1325             The function is used in the tree destructor.
1326         */
1327         void unsafe_clear()
1328         {
1329             rcu_lock l;
1330
1331             while ( true ) {
1332                 internal_node * pParent = nullptr;
1333                 internal_node * pGrandParent = nullptr;
1334                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
1335
1336                 // Get leftmost leaf
1337                 while ( pLeaf->is_internal() ) {
1338                     pGrandParent = pParent;
1339                     pParent = static_cast<internal_node *>( pLeaf );
1340                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1341                 }
1342
1343                 if ( pLeaf->infinite_key()) {
1344                     // The tree is empty
1345                     return;
1346                 }
1347
1348                 // Remove leftmost leaf and its parent node
1349                 assert( pGrandParent );
1350                 assert( pParent );
1351                 assert( pLeaf->is_leaf() );
1352
1353                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1354                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
1355                 free_internal_node( pParent );
1356             }
1357         }
1358
1359         /// Returns item count in the tree
1360         /**
1361             Only leaf nodes containing user data are counted.
1362
1363             The value returned depends on item counter type provided by \p Traits template parameter.
1364             If it is atomicity::empty_item_counter this function always returns 0.
1365             Therefore, the function is not suitable for checking the tree emptiness, use \ref empty
1366             member function for this purpose.
1367         */
1368         size_t size() const
1369         {
1370             return m_ItemCounter;
1371         }
1372
1373         /// Returns const reference to internal statistics
1374         stat const& statistics() const
1375         {
1376             return m_Stat;
1377         }
1378
1379         /// Checks internal consistency (not atomic, not thread-safe)
1380         /**
1381             The debugging function to check internal consistency of the tree.
1382         */
1383         bool check_consistency() const
1384         {
1385             return check_consistency( &m_Root );
1386         }
1387
1388     protected:
1389         //@cond
1390
1391         bool check_consistency( internal_node const * pRoot ) const
1392         {
1393             tree_node * pLeft  = pRoot->m_pLeft.load( CDS_ATOMIC::memory_order_relaxed );
1394             tree_node * pRight = pRoot->m_pRight.load( CDS_ATOMIC::memory_order_relaxed );
1395             assert( pLeft );
1396             assert( pRight );
1397
1398             if ( node_compare()( *pLeft, *pRoot ) < 0
1399                 && node_compare()( *pRoot, *pRight ) <= 0
1400                 && node_compare()( *pLeft, *pRight ) < 0 )
1401             {
1402                 bool bRet = true;
1403                 if ( pLeft->is_internal() )
1404                     bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
1405                 assert( bRet );
1406
1407                 if ( bRet && pRight->is_internal() )
1408                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1409                 assert( bRet );
1410
1411                 return bRet;
1412             }
1413             return false;
1414         }
1415
1416         void help( update_ptr pUpdate, retired_list& rl )
1417         {
1418             /*
1419             switch ( pUpdate.bits() ) {
1420                 case update_desc::IFlag:
1421                     help_insert( pUpdate.ptr() );
1422                     m_Stat.onHelpInsert();
1423                     break;
1424                 case update_desc::DFlag:
1425                     //help_delete( pUpdate.ptr(), rl );
1426                     //m_Stat.onHelpDelete();
1427                     break;
1428                 case update_desc::Mark:
1429                     //help_marked( pUpdate.ptr() );
1430                     //m_Stat.onHelpMark();
1431                     break;
1432             }
1433             */
1434         }
1435
1436         void help_insert( update_desc * pOp )
1437         {
1438             assert( gc::is_locked() );
1439
1440             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1441             if ( pOp->iInfo.bRightLeaf ) {
1442                 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1443                     memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1444             }
1445             else {
1446                 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1447                     memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1448             }
1449
1450             update_ptr cur( pOp, update_desc::IFlag );
1451             pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1452                       memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1453         }
1454
1455         bool check_delete_precondition( search_result& res )
1456         {
1457             assert( res.pGrandParent != nullptr );
1458
1459             return
1460                 static_cast<internal_node *>( res.bRightParent
1461                     ? res.pGrandParent->m_pRight.load(memory_model::memory_order_relaxed)
1462                     : res.pGrandParent->m_pLeft.load(memory_model::memory_order_relaxed)
1463                 ) == res.pParent
1464                 &&
1465                 static_cast<leaf_node *>( res.bRightLeaf
1466                     ? res.pParent->m_pRight.load(memory_model::memory_order_relaxed)
1467                     : res.pParent->m_pLeft.load(memory_model::memory_order_relaxed)
1468                 ) == res.pLeaf;
1469         }
1470
1471         bool help_delete( update_desc * pOp, retired_list& rl )
1472         {
1473             assert( gc::is_locked() );
1474
1475             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1476             update_ptr pMark( pOp, update_desc::Mark );
1477             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1478                     memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1479             {
1480                 help_marked( pOp );
1481                 retire_node( pOp->dInfo.pParent, rl );
1482                 // For extract operations the leaf should NOT be disposed
1483                 if ( pOp->dInfo.bDisposeLeaf )
1484                     retire_node( pOp->dInfo.pLeaf, rl );
1485                 retire_update_desc( pOp, rl, false );
1486
1487                 return true;
1488             }
1489             else if ( pUpdate == pMark ) {
1490                 // some other thread is processing help_marked()
1491                 help_marked( pOp );
1492                 m_Stat.onHelpMark();
1493                 return true;
1494             }
1495             else {
1496                 // pUpdate has been changed by CAS
1497                 help( pUpdate, rl );
1498
1499                 // Undo grandparent dInfo
1500                 update_ptr pDel( pOp, update_desc::DFlag );
1501                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1502                     memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
1503                 {
1504                     retire_update_desc( pOp, rl, false );
1505                 }
1506                 return false;
1507             }
1508         }
1509
1510         void help_marked( update_desc * pOp )
1511         {
1512             assert( gc::is_locked() );
1513
1514             tree_node * p = pOp->dInfo.pParent;
1515             if ( pOp->dInfo.bRightParent ) {
1516                 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1517                     pOp->dInfo.bRightLeaf
1518                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1519                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1520                     memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1521             }
1522             else {
1523                 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1524                     pOp->dInfo.bRightLeaf
1525                         ? pOp->dInfo.pParent->m_pLeft.load( memory_model::memory_order_acquire )
1526                         : pOp->dInfo.pParent->m_pRight.load( memory_model::memory_order_acquire ),
1527                     memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1528             }
1529
1530             update_ptr upd( pOp, update_desc::DFlag );
1531             pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1532                 memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1533         }
1534
1535         template <typename KeyValue, typename Compare>
1536         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1537         {
1538             assert( gc::is_locked() );
1539
1540             internal_node * pParent;
1541             internal_node * pGrandParent = nullptr;
1542             tree_node *     pLeaf;
1543             update_ptr      updParent;
1544             update_ptr      updGrandParent;
1545             bool bRightLeaf;
1546             bool bRightParent = false;
1547
1548             int nCmp = 0;
1549
1550         retry:
1551             pParent = nullptr;
1552             pLeaf = const_cast<internal_node *>( &m_Root );
1553             updParent = nullptr;
1554             bRightLeaf = false;
1555             while ( pLeaf->is_internal() ) {
1556                 pGrandParent = pParent;
1557                 pParent = static_cast<internal_node *>( pLeaf );
1558                 bRightParent = bRightLeaf;
1559                 updGrandParent = updParent;
1560                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1561
1562                 switch ( updParent.bits() ) {
1563                     case update_desc::DFlag:
1564                     case update_desc::Mark:
1565                         m_Stat.onSearchRetry();
1566                         goto retry;
1567                 }
1568
1569                 nCmp = cmp( key, *pParent );
1570                 bRightLeaf = nCmp >= 0;
1571                 pLeaf = nCmp < 0 ? pParent->m_pLeft.load( memory_model::memory_order_acquire )
1572                                  : pParent->m_pRight.load( memory_model::memory_order_acquire );
1573             }
1574
1575             assert( pLeaf->is_leaf() );
1576             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
1577
1578             res.pGrandParent    = pGrandParent;
1579             res.pParent         = pParent;
1580             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1581             res.updParent       = updParent;
1582             res.updGrandParent  = updGrandParent;
1583             res.bRightParent    = bRightParent;
1584             res.bRightLeaf      = bRightLeaf;
1585
1586             return nCmp == 0;
1587         }
1588
1589         bool search_min( search_result& res ) const
1590         {
1591             assert( gc::is_locked() );
1592
1593             internal_node * pParent;
1594             internal_node * pGrandParent = nullptr;
1595             tree_node *     pLeaf;
1596             update_ptr      updParent;
1597             update_ptr      updGrandParent;
1598
1599         retry:
1600             pParent = nullptr;
1601             pLeaf = const_cast<internal_node *>( &m_Root );
1602             while ( pLeaf->is_internal() ) {
1603                 pGrandParent = pParent;
1604                 pParent = static_cast<internal_node *>( pLeaf );
1605                 updGrandParent = updParent;
1606                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1607
1608                 switch ( updParent.bits() ) {
1609                     case update_desc::DFlag:
1610                     case update_desc::Mark:
1611                         m_Stat.onSearchRetry();
1612                         goto retry;
1613                 }
1614
1615                 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1616             }
1617
1618             if ( pLeaf->infinite_key())
1619                 return false;
1620
1621             res.pGrandParent    = pGrandParent;
1622             res.pParent         = pParent;
1623             assert( pLeaf->is_leaf() );
1624             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1625             res.updParent       = updParent;
1626             res.updGrandParent  = updGrandParent;
1627             res.bRightParent    = false;
1628             res.bRightLeaf      = false;
1629
1630             return true;
1631         }
1632
1633         bool search_max( search_result& res ) const
1634         {
1635             assert( gc::is_locked() );
1636
1637             internal_node * pParent;
1638             internal_node * pGrandParent = nullptr;
1639             tree_node *     pLeaf;
1640             update_ptr      updParent;
1641             update_ptr      updGrandParent;
1642             bool bRightLeaf;
1643             bool bRightParent = false;
1644
1645         retry:
1646             pParent = nullptr;
1647             pLeaf = const_cast<internal_node *>( &m_Root );
1648             bRightLeaf = false;
1649             while ( pLeaf->is_internal() ) {
1650                 pGrandParent = pParent;
1651                 pParent = static_cast<internal_node *>( pLeaf );
1652                 bRightParent = bRightLeaf;
1653                 updGrandParent = updParent;
1654                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1655
1656                 switch ( updParent.bits() ) {
1657                     case update_desc::DFlag:
1658                     case update_desc::Mark:
1659                         m_Stat.onSearchRetry();
1660                         goto retry;
1661                 }
1662
1663                 if ( pParent->infinite_key()) {
1664                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1665                     bRightLeaf = false;
1666                 }
1667                 else {
1668                     pLeaf = pParent->m_pRight.load( memory_model::memory_order_acquire );
1669                     bRightLeaf = true;
1670                 }
1671             }
1672
1673             if ( pLeaf->infinite_key())
1674                 return false;
1675
1676             res.pGrandParent    = pGrandParent;
1677             res.pParent         = pParent;
1678             assert( pLeaf->is_leaf() );
1679             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1680             res.updParent       = updParent;
1681             res.updGrandParent  = updGrandParent;
1682             res.bRightParent    = bRightParent;
1683             res.bRightLeaf      = bRightLeaf;
1684
1685             return true;
1686         }
1687
1688         template <typename Q, typename Compare, typename Equal, typename Func>
1689         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1690         {
1691             check_deadlock_policy::check();
1692
1693             retired_list updRetire;
1694             update_desc * pOp = nullptr;
1695             search_result res;
1696
1697             {
1698                 rcu_lock l;
1699                 for ( ;; ) {
1700                     if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
1701                         if ( pOp )
1702                             retire_update_desc( pOp, updRetire, false );
1703                         m_Stat.onEraseFailed();
1704                         return false;
1705                     }
1706
1707                     if ( res.updGrandParent.bits() != update_desc::Clean )
1708                         help( res.updGrandParent, updRetire );
1709                     else if ( res.updParent.bits() != update_desc::Clean )
1710                         help( res.updParent, updRetire );
1711                     else {
1712                         if ( !pOp )
1713                             pOp = alloc_update_desc();
1714                         if ( check_delete_precondition( res ) ) {
1715                             pOp->dInfo.pGrandParent = res.pGrandParent;
1716                             pOp->dInfo.pParent = res.pParent;
1717                             pOp->dInfo.pLeaf = res.pLeaf;
1718                             pOp->dInfo.bDisposeLeaf = true;
1719                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1720                             pOp->dInfo.bRightParent = res.bRightParent;
1721                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1722
1723                             update_ptr updGP( res.updGrandParent.ptr() );
1724                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1725                                 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1726                             {
1727                                 if ( help_delete( pOp, updRetire )) {
1728                                     // res.pLeaf is not deleted yet since RCU is blocked
1729                                     cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ));
1730                                     break;
1731                                 }
1732                                 pOp = nullptr;
1733                             }
1734                             else {
1735                                 // updGP has been changed by CAS
1736                                 help( updGP, updRetire );
1737                             }
1738                         }
1739                     }
1740
1741                     m_Stat.onEraseRetry();
1742                 }
1743             }
1744
1745             --m_ItemCounter;
1746             m_Stat.onEraseSuccess();
1747             return true;
1748         }
1749
1750         template <typename ExemptPtr, typename Q, typename Less>
1751         bool extract_with_( ExemptPtr& dest,  Q const& val, Less pred )
1752         {
1753             typedef ellen_bintree::details::compare<
1754                 key_type,
1755                 value_type,
1756                 opt::details::make_comparator_from_less<Less>,
1757                 node_traits
1758             > compare_functor;
1759
1760             return extract_( dest, val, compare_functor() );
1761         }
1762
1763         template <typename ExemptPtr, typename Q, typename Compare>
1764         bool extract_( ExemptPtr& ptr, Q const& val, Compare cmp )
1765         {
1766             check_deadlock_policy::check();
1767
1768             retired_list updRetire;
1769             update_desc * pOp = nullptr;
1770             search_result res;
1771
1772             {
1773                 rcu_lock l;
1774                 for ( ;; ) {
1775                     if ( !search( res, val, cmp ) ) {
1776                         if ( pOp )
1777                             retire_update_desc( pOp, updRetire, false );
1778                         m_Stat.onEraseFailed();
1779                         return false;
1780                     }
1781
1782                     if ( res.updGrandParent.bits() != update_desc::Clean )
1783                         help( res.updGrandParent, updRetire );
1784                     else if ( res.updParent.bits() != update_desc::Clean )
1785                         help( res.updParent, updRetire );
1786                     else {
1787                         if ( !pOp )
1788                             pOp = alloc_update_desc();
1789                         if ( check_delete_precondition( res )) {
1790                             pOp->dInfo.pGrandParent = res.pGrandParent;
1791                             pOp->dInfo.pParent = res.pParent;
1792                             pOp->dInfo.pLeaf = res.pLeaf;
1793                             pOp->dInfo.bDisposeLeaf = false;
1794                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1795                             pOp->dInfo.bRightParent = res.bRightParent;
1796                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1797
1798                             update_ptr updGP( res.updGrandParent.ptr() );
1799                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1800                                 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1801                             {
1802                                 if ( help_delete( pOp, updRetire )) {
1803                                     ptr = node_traits::to_value_ptr( res.pLeaf );
1804                                     break;
1805                                 }
1806                                 pOp = nullptr;
1807                             }
1808                             else {
1809                                 // updGP has been changed by CAS
1810                                 help( updGP, updRetire );
1811                             }
1812                         }
1813                     }
1814
1815                     m_Stat.onEraseRetry();
1816                 }
1817             }
1818
1819             --m_ItemCounter;
1820             m_Stat.onEraseSuccess();
1821             return true;
1822         }
1823
1824
1825         template <typename ExemptPtr>
1826         bool extract_max_( ExemptPtr& result )
1827         {
1828             check_deadlock_policy::check();
1829
1830             retired_list updRetire;
1831             update_desc * pOp = nullptr;
1832             search_result res;
1833
1834             {
1835                 rcu_lock l;
1836                 for ( ;; ) {
1837                     if ( !search_max( res )) {
1838                         // Tree is empty
1839                         if ( pOp )
1840                             retire_update_desc( pOp, updRetire, false );
1841                         m_Stat.onExtractMaxFailed();
1842                         return false;
1843                     }
1844
1845                     if ( res.updGrandParent.bits() != update_desc::Clean )
1846                         help( res.updGrandParent, updRetire );
1847                     else if ( res.updParent.bits() != update_desc::Clean )
1848                         help( res.updParent, updRetire );
1849                     else {
1850                         if ( !pOp )
1851                             pOp = alloc_update_desc();
1852                         if ( check_delete_precondition( res ) ) {
1853                             pOp->dInfo.pGrandParent = res.pGrandParent;
1854                             pOp->dInfo.pParent = res.pParent;
1855                             pOp->dInfo.pLeaf = res.pLeaf;
1856                             pOp->dInfo.bDisposeLeaf = false;
1857                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1858                             pOp->dInfo.bRightParent = res.bRightParent;
1859                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1860
1861                             update_ptr updGP( res.updGrandParent.ptr() );
1862                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1863                                 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1864                             {
1865                                 if ( help_delete( pOp, updRetire )) {
1866                                     result = node_traits::to_value_ptr( res.pLeaf );
1867                                     break;
1868                                 }
1869                                 pOp = nullptr;
1870                             }
1871                             else {
1872                                 // updGP has been changed by CAS
1873                                 help( updGP, updRetire );
1874                             }
1875                         }
1876                     }
1877                     m_Stat.onExtractMaxRetry();
1878                 }
1879             }
1880
1881             --m_ItemCounter;
1882             m_Stat.onExtractMaxSuccess();
1883             return true;
1884         }
1885
1886         template <typename ExemptPtr>
1887         bool extract_min_(ExemptPtr& result)
1888         {
1889             check_deadlock_policy::check();
1890
1891             retired_list updRetire;
1892             update_desc * pOp = nullptr;
1893             search_result res;
1894
1895             {
1896                 rcu_lock l;
1897                 for ( ;; ) {
1898                     if ( !search_min( res )) {
1899                         // Tree is empty
1900                         if ( pOp )
1901                             retire_update_desc( pOp, updRetire, false );
1902                         m_Stat.onExtractMinFailed();
1903                         return false;
1904                     }
1905
1906                     if ( res.updGrandParent.bits() != update_desc::Clean )
1907                         help( res.updGrandParent, updRetire );
1908                     else if ( res.updParent.bits() != update_desc::Clean )
1909                         help( res.updParent, updRetire );
1910                     else {
1911                         if ( !pOp )
1912                             pOp = alloc_update_desc();
1913                         if ( check_delete_precondition( res ) ) {
1914                             pOp->dInfo.pGrandParent = res.pGrandParent;
1915                             pOp->dInfo.pParent = res.pParent;
1916                             pOp->dInfo.pLeaf = res.pLeaf;
1917                             pOp->dInfo.bDisposeLeaf = false;
1918                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1919                             pOp->dInfo.bRightParent = res.bRightParent;
1920                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1921
1922                             update_ptr updGP( res.updGrandParent.ptr() );
1923                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1924                                 memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
1925                             {
1926                                 if ( help_delete( pOp, updRetire )) {
1927                                     result = node_traits::to_value_ptr( res.pLeaf );
1928                                     break;
1929                                 }
1930                                 pOp = nullptr;
1931                             }
1932                             else {
1933                                 // updGP has been changed by CAS
1934                                 help( updGP, updRetire );
1935                             }
1936                         }
1937                     }
1938
1939                     m_Stat.onExtractMinRetry();
1940                 }
1941             }
1942
1943             --m_ItemCounter;
1944             m_Stat.onExtractMinSuccess();
1945             return true;
1946         }
1947
1948         template <typename Q, typename Less, typename Func>
1949         bool find_with_( Q& val, Less pred, Func f ) const
1950         {
1951             typedef ellen_bintree::details::compare<
1952                 key_type,
1953                 value_type,
1954                 opt::details::make_comparator_from_less<Less>,
1955                 node_traits
1956             > compare_functor;
1957
1958             rcu_lock l;
1959             search_result    res;
1960             if ( search( res, val, compare_functor() )) {
1961                 assert( res.pLeaf );
1962                 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), val );
1963
1964                 m_Stat.onFindSuccess();
1965                 return true;
1966             }
1967
1968             m_Stat.onFindFailed();
1969             return false;
1970         }
1971
1972         template <typename Q, typename Func>
1973         bool find_( Q& key, Func f ) const
1974         {
1975             rcu_lock l;
1976             search_result    res;
1977             if ( search( res, key, node_compare() )) {
1978                 assert( res.pLeaf );
1979                 cds::unref(f)( *node_traits::to_value_ptr( res.pLeaf ), key );
1980
1981                 m_Stat.onFindSuccess();
1982                 return true;
1983             }
1984
1985             m_Stat.onFindFailed();
1986             return false;
1987         }
1988
1989         template <typename Q, typename Compare>
1990         value_type * get_( Q const& key, Compare cmp ) const
1991         {
1992             assert( gc::is_locked());
1993
1994             search_result    res;
1995             if ( search( res, key, cmp )) {
1996                 m_Stat.onFindSuccess();
1997                 return node_traits::to_value_ptr( res.pLeaf );
1998             }
1999
2000             m_Stat.onFindFailed();
2001             return nullptr;
2002         }
2003
2004
2005         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
2006         {
2007             assert( gc::is_locked() );
2008             assert( res.updParent.bits() == update_desc::Clean );
2009
2010             // check search result
2011             if ( static_cast<leaf_node *>( res.bRightLeaf
2012                 ? res.pParent->m_pRight.load( memory_model::memory_order_relaxed )
2013                 : res.pParent->m_pLeft.load( memory_model::memory_order_relaxed ) ) == res.pLeaf )
2014             {
2015                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
2016
2017                 int nCmp = node_compare()( val, *res.pLeaf );
2018                 if ( nCmp < 0 ) {
2019                     if ( res.pGrandParent ) {
2020                         pNewInternal->infinite_key( 0 );
2021                         key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ) );
2022                         assert( !res.pLeaf->infinite_key() );
2023                     }
2024                     else {
2025                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
2026                         pNewInternal->infinite_key( 1 );
2027                     }
2028                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
2029                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
2030                 }
2031                 else {
2032                     assert( !res.pLeaf->is_internal() );
2033                     pNewInternal->infinite_key( 0 );
2034
2035                     key_extractor()( pNewInternal->m_Key, val );
2036                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
2037                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
2038                     assert( !res.pLeaf->infinite_key());
2039                 }
2040
2041                 update_desc * pOp = alloc_update_desc();
2042
2043                 pOp->iInfo.pParent = res.pParent;
2044                 pOp->iInfo.pNew = pNewInternal;
2045                 pOp->iInfo.pLeaf = res.pLeaf;
2046                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
2047
2048                 update_ptr updCur( res.updParent.ptr() );
2049                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
2050                     memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
2051                 {
2052                     // do insert
2053                     help_insert( pOp );
2054                     retire_update_desc( pOp, updRetire, false );
2055                     return true;
2056                 }
2057                 else {
2058                     // updCur has been updated by CAS
2059                     help( updCur, updRetire );
2060                     retire_update_desc( pOp, updRetire, true );
2061                 }
2062             }
2063             return false;
2064         }
2065
2066         //@endcond
2067     };
2068
2069 }} // namespace cds::intrusive
2070
2071 #endif  // #ifndef __CDS_INTRUSIVE_ELLEN_BINTREE_RCU_H