cds/intrusive/ellen_bintree_rcu.h

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