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 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 successfull,
 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.onEnsureExist();
 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.onEnsureRetry();
 873                 }
 874             }
 875
 876             ++m_ItemCounter;
 877             m_Stat.onEnsureNew();
 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 hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 921
 922             RCU \p synchronize method can be called. RCU should not be locked.
 923         */
 924         template <typename Q>
 925         bool erase( const Q& key )
 926         {
 927             return erase_( key, node_compare(),
 928                 []( Q const&, leaf_node const& ) -> bool { return true; },
 929                 [](value_type const&) {} );
 930         }
 931
 932         /// Delete the item from the tree with comparing functor \p pred
 933         /**
 934             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase "erase(Q const&)"
 935             but \p pred predicate is used for key comparing.
 936             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 937             "Predicate requirements".
 938             \p pred must imply the same element order as the comparator used for building the tree.
 939         */
 940         template <typename Q, typename Less>
 941         bool erase_with( const Q& key, Less pred )
 942         {
 943             CDS_UNUSED( pred );
 944             typedef ellen_bintree::details::compare<
 945                 key_type,
 946                 value_type,
 947                 opt::details::make_comparator_from_less<Less>,
 948                 node_traits
 949             > compare_functor;
 950
 951             return erase_( key, compare_functor(),
 952                 []( Q const&, leaf_node const& ) -> bool { return true; },
 953                 [](value_type const&) {} );
 954         }
 955
 956         /// Deletes the item from the tree
 957         /** \anchor cds_intrusive_EllenBinTree_rcu_erase_func
 958             The function searches an item with key equal to \p key in the tree,
 959             call \p f functor with item found, unlinks it from the tree, and returns \p true.
 960             The \ref disposer specified in \p Traits class template parameter is called
 961             by garbage collector \p GC asynchronously.
 962
 963             The \p Func interface is
 964             \code
 965             struct functor {
 966                 void operator()( value_type const& item );
 967             };
 968             \endcode
 969
 970             If the item with key equal to \p key is not found the function return \p false.
 971
 972             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 973
 974             RCU \p synchronize method can be called. RCU should not be locked.
 975         */
 976         template <typename Q, typename Func>
 977         bool erase( Q const& key, Func f )
 978         {
 979             return erase_( key, node_compare(),
 980                 []( Q const&, leaf_node const& ) -> bool { return true; },
 981                 f );
 982         }
 983
 984         /// Delete the item from the tree with comparing functor \p pred
 985         /**
 986             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_erase_func "erase(Q const&, Func)"
 987             but \p pred predicate is used for key comparing.
 988             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
 989             "Predicate requirements".
 990             \p pred must imply the same element order as the comparator used for building the tree.
 991         */
 992         template <typename Q, typename Less, typename Func>
 993         bool erase_with( Q const& key, Less pred, Func f )
 994         {
 995             CDS_UNUSED( pred );
 996             typedef ellen_bintree::details::compare<
 997                 key_type,
 998                 value_type,
 999                 opt::details::make_comparator_from_less<Less>,
1000                 node_traits
1001             > compare_functor;
1002
1003             return erase_( key, compare_functor(),
1004                 []( Q const&, leaf_node const& ) -> bool { return true; },
1005                 f );
1006         }
1007
1008         /// Extracts an item with minimal key from the tree
1009         /**
1010             The function searches an item with minimal key, unlinks it, and returns
1011             \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
1012             If the tree is empty the function returns empty \p exempt_ptr.
1013
1014             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
1015             It means that the function gets leftmost leaf of the tree and tries to unlink it.
1016             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1017             So, the function returns the item with minimum key at the moment of tree traversing.
1018
1019             RCU \p synchronize method can be called. RCU should NOT be locked.
1020             The function does not call the disposer for the item found.
1021             The disposer will be implicitly invoked when the returned object is destroyed or when
1022             its \p release() member function is called.
1023         */
1024         exempt_ptr extract_min()
1025         {
1026             return exempt_ptr( extract_min_());
1027         }
1028
1029         /// Extracts an item with maximal key from the tree
1030         /**
1031             The function searches an item with maximal key, unlinks it, and returns
1032             \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
1033             If the tree is empty the function returns empty \p exempt_ptr.
1034
1035             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
1036             It means that the function gets rightmost leaf of the tree and tries to unlink it.
1037             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
1038             So, the function returns the item with maximum key at the moment of tree traversing.
1039
1040             RCU \p synchronize method can be called. RCU should NOT be locked.
1041             The function does not call the disposer for the item found.
1042             The disposer will be implicitly invoked when the returned object is destroyed or when
1043             its \p release() member function is called.
1044         */
1045         exempt_ptr extract_max()
1046         {
1047             return exempt_ptr( extract_max_());
1048         }
1049
1050         /// Extracts an item from the tree
1051         /** \anchor cds_intrusive_EllenBinTree_rcu_extract
1052             The function searches an item with key equal to \p key in the tree,
1053             unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
1054             If the item with the key equal to \p key is not found the function returns empty \p exempt_ptr.
1055
1056             RCU \p synchronize method can be called. RCU should NOT be locked.
1057             The function does not call the disposer for the item found.
1058             The disposer will be implicitly invoked when the returned object is destroyed or when
1059             its \p release() member function is called.
1060         */
1061         template <typename Q>
1062         exempt_ptr extract( Q const& key )
1063         {
1064             return exempt_ptr( extract_( key, node_compare()));
1065         }
1066
1067         /// Extracts an item from the set using \p pred for searching
1068         /**
1069             The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
1070             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1071             "predicate requirements".
1072             \p pred must imply the same element order as the comparator used for building the tree.
1073         */
1074         template <typename Q, typename Less>
1075         exempt_ptr extract_with( Q const& key, Less pred )
1076         {
1077             return exempt_ptr( extract_with_( key, pred ));
1078         }
1079
1080         /// Checks whether the set contains \p key
1081         /**
1082             The function searches the item with key equal to \p key
1083             and returns \p true if it is found, and \p false otherwise.
1084
1085             The function applies RCU lock internally.
1086         */
1087         template <typename Q>
1088         bool contains( Q const& key ) const
1089         {
1090             rcu_lock l;
1091             search_result    res;
1092             if ( search( res, key, node_compare())) {
1093                 m_Stat.onFindSuccess();
1094                 return true;
1095             }
1096
1097             m_Stat.onFindFailed();
1098             return false;
1099         }
1100         //@cond
1101         template <typename Q>
1102         CDS_DEPRECATED("deprecated, use contains()")
1103         bool find( Q const& key ) const
1104         {
1105             return contains( key );
1106         }
1107         //@endcond
1108
1109         /// Checks whether the set contains \p key using \p pred predicate for searching
1110         /**
1111             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1112             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1113             "Predicate requirements".
1114             \p Less must imply the same element order as the comparator used for building the set.
1115             \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
1116         */
1117         template <typename Q, typename Less>
1118         bool contains( Q const& key, Less pred ) const
1119         {
1120             CDS_UNUSED( pred );
1121             typedef ellen_bintree::details::compare<
1122                 key_type,
1123                 value_type,
1124                 opt::details::make_comparator_from_less<Less>,
1125                 node_traits
1126             > compare_functor;
1127
1128             rcu_lock l;
1129             search_result    res;
1130             if ( search( res, key, compare_functor())) {
1131                 m_Stat.onFindSuccess();
1132                 return true;
1133             }
1134             m_Stat.onFindFailed();
1135             return false;
1136         }
1137         //@cond
1138         template <typename Q, typename Less>
1139         CDS_DEPRECATED("deprecated, use contains()")
1140         bool find_with( Q const& key, Less pred ) const
1141         {
1142             return contains( key, pred );
1143         }
1144         //@endcond
1145
1146         /// Finds the key \p key
1147         /** @anchor cds_intrusive_EllenBinTree_rcu_find_func
1148             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1149             The interface of \p Func functor is:
1150             \code
1151             struct functor {
1152                 void operator()( value_type& item, Q& key );
1153             };
1154             \endcode
1155             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1156
1157             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1158             that \p item cannot be disposed during functor is executing.
1159             The functor does not serialize simultaneous access to the tree \p item. If such access is
1160             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1161
1162             The function applies RCU lock internally.
1163
1164             The function returns \p true if \p key is found, \p false otherwise.
1165         */
1166         template <typename Q, typename Func>
1167         bool find( Q& key, Func f ) const
1168         {
1169             return find_( key, f );
1170         }
1171         //@cond
1172         template <typename Q, typename Func>
1173         bool find( Q const& key, Func f ) const
1174         {
1175             return find_( key, f );
1176         }
1177         //@endcond
1178
1179         /// Finds the key \p key with comparing functor \p pred
1180         /**
1181             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_find_func "find(Q&, Func)"
1182             but \p pred is used for key comparison.
1183             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
1184             "Predicate requirements".
1185             \p pred must imply the same element order as the comparator used for building the tree.
1186         */
1187         template <typename Q, typename Less, typename Func>
1188         bool find_with( Q& key, Less pred, Func f ) const
1189         {
1190             return find_with_( key, pred, f );
1191         }
1192         //@cond
1193         template <typename Q, typename Less, typename Func>
1194         bool find_with( Q const& key, Less pred, Func f ) const
1195         {
1196             return find_with_( key, pred, f );
1197         }
1198         //@endcond
1199
1200         /// Finds \p key and return the item found
1201         /** \anchor cds_intrusive_EllenBinTree_rcu_get
1202             The function searches the item with key equal to \p key and returns the pointer to item found.
1203             If \p key is not found it returns \p nullptr.
1204
1205             RCU should be locked before call the function.
1206             Returned pointer is valid while RCU is locked.
1207         */
1208         template <typename Q>
1209         value_type * get( Q const& key ) const
1210         {
1211             return get_( key, node_compare());
1212         }
1213
1214         /// Finds \p key with \p pred predicate and return the item found
1215         /**
1216             The function is an analog of \ref cds_intrusive_EllenBinTree_rcu_get "get(Q const&)"
1217             but \p pred is used for comparing the keys.
1218
1219             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1220             in any order.
1221             \p pred must imply the same element order as the comparator used for building the tree.
1222         */
1223         template <typename Q, typename Less>
1224         value_type * get_with( Q const& key, Less pred ) const
1225         {
1226             CDS_UNUSED( pred );
1227             typedef ellen_bintree::details::compare<
1228                 key_type,
1229                 value_type,
1230                 opt::details::make_comparator_from_less<Less>,
1231                 node_traits
1232             > compare_functor;
1233
1234             return get_( key, compare_functor());
1235         }
1236
1237         /// Checks if the tree is empty
1238         bool empty() const
1239         {
1240             return m_Root.m_pLeft.load( memory_model::memory_order_relaxed )->is_leaf();
1241         }
1242
1243         /// Clears the tree (thread safe, not atomic)
1244         /**
1245             The function unlink all items from the tree.
1246             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
1247             this sequence
1248             \code
1249             set.clear();
1250             assert( set.empty());
1251             \endcode
1252             the assertion could be raised.
1253
1254             For each leaf the \ref disposer will be called after unlinking.
1255
1256             RCU \p synchronize method can be called. RCU should not be locked.
1257         */
1258         void clear()
1259         {
1260             for ( exempt_ptr ep = extract_min(); !ep.empty(); ep = extract_min())
1261                 ep.release();
1262         }
1263
1264         /// Clears the tree (not thread safe)
1265         /**
1266             This function is not thread safe and may be called only when no other thread deals with the tree.
1267             The function is used in the tree destructor.
1268         */
1269         void unsafe_clear()
1270         {
1271             rcu_lock l;
1272
1273             while ( true ) {
1274                 internal_node * pParent = nullptr;
1275                 internal_node * pGrandParent = nullptr;
1276                 tree_node *     pLeaf = const_cast<internal_node *>( &m_Root );
1277
1278                 // Get leftmost leaf
1279                 while ( pLeaf->is_internal()) {
1280                     pGrandParent = pParent;
1281                     pParent = static_cast<internal_node *>( pLeaf );
1282                     pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
1283                 }
1284
1285                 if ( pLeaf->infinite_key()) {
1286                     // The tree is empty
1287                     return;
1288                 }
1289
1290                 // Remove leftmost leaf and its parent node
1291                 assert( pGrandParent );
1292                 assert( pParent );
1293                 assert( pLeaf->is_leaf());
1294
1295                 pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
1296                 free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf )));
1297                 free_internal_node( pParent );
1298             }
1299         }
1300
1301         /// Returns item count in the tree
1302         /**
1303             Only leaf nodes containing user data are counted.
1304
1305             The value returned depends on item counter type provided by \p Traits template parameter.
1306             If it is \p atomicity::empty_item_counter this function always returns 0.
1307
1308             The function is not suitable for checking the tree emptiness, use \p empty()
1309             member function for that.
1310         */
1311         size_t size() const
1312         {
1313             return m_ItemCounter;
1314         }
1315
1316         /// Returns const reference to internal statistics
1317         stat const& statistics() const
1318         {
1319             return m_Stat;
1320         }
1321
1322         /// Checks internal consistency (not atomic, not thread-safe)
1323         /**
1324             The debugging function to check internal consistency of the tree.
1325         */
1326         bool check_consistency() const
1327         {
1328             return check_consistency( &m_Root );
1329         }
1330
1331     protected:
1332         //@cond
1333
1334         bool check_consistency( internal_node const * pRoot ) const
1335         {
1336             tree_node * pLeft  = pRoot->m_pLeft.load( atomics::memory_order_relaxed );
1337             tree_node * pRight = pRoot->m_pRight.load( atomics::memory_order_relaxed );
1338             assert( pLeft );
1339             assert( pRight );
1340
1341             if ( node_compare()( *pLeft, *pRoot ) < 0
1342                 && node_compare()( *pRoot, *pRight ) <= 0
1343                 && node_compare()( *pLeft, *pRight ) < 0 )
1344             {
1345                 bool bRet = true;
1346                 if ( pLeft->is_internal())
1347                     bRet = check_consistency( static_cast<internal_node *>( pLeft ));
1348                 assert( bRet );
1349
1350                 if ( bRet && pRight->is_internal())
1351                     bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
1352                 assert( bRet );
1353
1354                 return bRet;
1355             }
1356             return false;
1357         }
1358
1359         void help( update_ptr /*pUpdate*/, retired_list& /*rl*/ )
1360         {
1361             /*
1362             switch ( pUpdate.bits()) {
1363                 case update_desc::IFlag:
1364                     help_insert( pUpdate.ptr());
1365                     m_Stat.onHelpInsert();
1366                     break;
1367                 case update_desc::DFlag:
1368                     //help_delete( pUpdate.ptr(), rl );
1369                     //m_Stat.onHelpDelete();
1370                     break;
1371                 case update_desc::Mark:
1372                     //help_marked( pUpdate.ptr());
1373                     //m_Stat.onHelpMark();
1374                     break;
1375             }
1376             */
1377         }
1378
1379         void help_insert( update_desc * pOp )
1380         {
1381             assert( gc::is_locked());
1382
1383             tree_node * pLeaf = static_cast<tree_node *>( pOp->iInfo.pLeaf );
1384             if ( pOp->iInfo.bRightLeaf ) {
1385                 pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1386                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1387             }
1388             else {
1389                 pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast<tree_node *>( pOp->iInfo.pNew ),
1390                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1391             }
1392
1393             update_ptr cur( pOp, update_desc::IFlag );
1394             pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(),
1395                       memory_model::memory_order_release, atomics::memory_order_relaxed );
1396         }
1397
1398         bool check_delete_precondition( search_result& res )
1399         {
1400             assert( res.pGrandParent != nullptr );
1401
1402             return
1403                 static_cast<internal_node *>( res.pGrandParent->get_child( res.bRightParent, memory_model::memory_order_relaxed )) == res.pParent
1404              && static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf;
1405         }
1406
1407         bool help_delete( update_desc * pOp, retired_list& rl )
1408         {
1409             assert( gc::is_locked());
1410
1411             update_ptr pUpdate( pOp->dInfo.pUpdateParent );
1412             update_ptr pMark( pOp, update_desc::Mark );
1413             if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark,
1414                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1415             {
1416                 help_marked( pOp );
1417                 retire_node( pOp->dInfo.pParent, rl );
1418                 // For extract operations the leaf should NOT be disposed
1419                 if ( pOp->dInfo.bDisposeLeaf )
1420                     retire_node( pOp->dInfo.pLeaf, rl );
1421                 retire_update_desc( pOp, rl, false );
1422
1423                 return true;
1424             }
1425             else if ( pUpdate == pMark ) {
1426                 // some other thread is processing help_marked()
1427                 help_marked( pOp );
1428                 m_Stat.onHelpMark();
1429                 return true;
1430             }
1431             else {
1432                 // pUpdate has been changed by CAS
1433                 help( pUpdate, rl );
1434
1435                 // Undo grandparent dInfo
1436                 update_ptr pDel( pOp, update_desc::DFlag );
1437                 if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(),
1438                     memory_model::memory_order_release, atomics::memory_order_relaxed ))
1439                 {
1440                     retire_update_desc( pOp, rl, false );
1441                 }
1442                 return false;
1443             }
1444         }
1445
1446         void help_marked( update_desc * pOp )
1447         {
1448             assert( gc::is_locked());
1449
1450             tree_node * p = pOp->dInfo.pParent;
1451             if ( pOp->dInfo.bRightParent ) {
1452                 pOp->dInfo.pGrandParent->m_pRight.compare_exchange_strong( p,
1453                     pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1454                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1455             }
1456             else {
1457                 pOp->dInfo.pGrandParent->m_pLeft.compare_exchange_strong( p,
1458                     pOp->dInfo.pParent->get_child( !pOp->dInfo.bRightLeaf, memory_model::memory_order_acquire ),
1459                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1460             }
1461
1462             update_ptr upd( pOp, update_desc::DFlag );
1463             pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(),
1464                 memory_model::memory_order_release, atomics::memory_order_relaxed );
1465         }
1466
1467         template <typename KeyValue, typename Compare>
1468         bool search( search_result& res, KeyValue const& key, Compare cmp ) const
1469         {
1470             assert( gc::is_locked());
1471
1472             internal_node * pParent;
1473             internal_node * pGrandParent = nullptr;
1474             tree_node *     pLeaf;
1475             update_ptr      updParent;
1476             update_ptr      updGrandParent;
1477             bool bRightLeaf;
1478             bool bRightParent = false;
1479
1480             int nCmp = 0;
1481
1482         retry:
1483             pParent = nullptr;
1484             pLeaf = const_cast<internal_node *>( &m_Root );
1485             updParent = nullptr;
1486             bRightLeaf = false;
1487             while ( pLeaf->is_internal()) {
1488                 pGrandParent = pParent;
1489                 pParent = static_cast<internal_node *>( pLeaf );
1490                 bRightParent = bRightLeaf;
1491                 updGrandParent = updParent;
1492                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1493
1494                 switch ( updParent.bits()) {
1495                     case update_desc::DFlag:
1496                     case update_desc::Mark:
1497                         m_Stat.onSearchRetry();
1498                         goto retry;
1499                 }
1500
1501                 nCmp = cmp( key, *pParent );
1502                 bRightLeaf = nCmp >= 0;
1503                 pLeaf = pParent->get_child( nCmp >= 0, memory_model::memory_order_acquire );
1504             }
1505
1506             assert( pLeaf->is_leaf());
1507             nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf));
1508
1509             res.pGrandParent    = pGrandParent;
1510             res.pParent         = pParent;
1511             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1512             res.updParent       = updParent;
1513             res.updGrandParent  = updGrandParent;
1514             res.bRightParent    = bRightParent;
1515             res.bRightLeaf      = bRightLeaf;
1516
1517             return nCmp == 0;
1518         }
1519
1520         bool search_min( search_result& res ) const
1521         {
1522             assert( gc::is_locked());
1523
1524             internal_node * pParent;
1525             internal_node * pGrandParent = nullptr;
1526             tree_node *     pLeaf;
1527             update_ptr      updParent;
1528             update_ptr      updGrandParent;
1529
1530         retry:
1531             pParent = nullptr;
1532             pLeaf = const_cast<internal_node *>( &m_Root );
1533             while ( pLeaf->is_internal()) {
1534                 pGrandParent = pParent;
1535                 pParent = static_cast<internal_node *>( pLeaf );
1536                 updGrandParent = updParent;
1537                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1538
1539                 switch ( updParent.bits()) {
1540                     case update_desc::DFlag:
1541                     case update_desc::Mark:
1542                         m_Stat.onSearchRetry();
1543                         goto retry;
1544                 }
1545
1546                 pLeaf = pParent->m_pLeft.load( memory_model::memory_order_acquire );
1547             }
1548
1549             if ( pLeaf->infinite_key())
1550                 return false;
1551
1552             res.pGrandParent    = pGrandParent;
1553             res.pParent         = pParent;
1554             assert( pLeaf->is_leaf());
1555             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1556             res.updParent       = updParent;
1557             res.updGrandParent  = updGrandParent;
1558             res.bRightParent    = false;
1559             res.bRightLeaf      = false;
1560
1561             return true;
1562         }
1563
1564         bool search_max( search_result& res ) const
1565         {
1566             assert( gc::is_locked());
1567
1568             internal_node * pParent;
1569             internal_node * pGrandParent = nullptr;
1570             tree_node *     pLeaf;
1571             update_ptr      updParent;
1572             update_ptr      updGrandParent;
1573             bool bRightLeaf;
1574             bool bRightParent = false;
1575
1576         retry:
1577             pParent = nullptr;
1578             pLeaf = const_cast<internal_node *>( &m_Root );
1579             bRightLeaf = false;
1580             while ( pLeaf->is_internal()) {
1581                 pGrandParent = pParent;
1582                 pParent = static_cast<internal_node *>( pLeaf );
1583                 bRightParent = bRightLeaf;
1584                 updGrandParent = updParent;
1585                 updParent = pParent->m_pUpdate.load( memory_model::memory_order_acquire );
1586
1587                 switch ( updParent.bits()) {
1588                     case update_desc::DFlag:
1589                     case update_desc::Mark:
1590                         m_Stat.onSearchRetry();
1591                         goto retry;
1592                 }
1593
1594                 bRightLeaf = !pParent->infinite_key();
1595                 pLeaf = pParent->get_child( bRightLeaf, memory_model::memory_order_acquire );
1596             }
1597
1598             if ( pLeaf->infinite_key())
1599                 return false;
1600
1601             res.pGrandParent    = pGrandParent;
1602             res.pParent         = pParent;
1603             assert( pLeaf->is_leaf());
1604             res.pLeaf           = static_cast<leaf_node *>( pLeaf );
1605             res.updParent       = updParent;
1606             res.updGrandParent  = updGrandParent;
1607             res.bRightParent    = bRightParent;
1608             res.bRightLeaf      = bRightLeaf;
1609
1610             return true;
1611         }
1612
1613         template <typename Q, typename Compare, typename Equal, typename Func>
1614         bool erase_( Q const& val, Compare cmp, Equal eq, Func f )
1615         {
1616             check_deadlock_policy::check();
1617
1618             retired_list updRetire;
1619             update_desc * pOp = nullptr;
1620             search_result res;
1621             back_off bkoff;
1622
1623             {
1624                 rcu_lock l;
1625                 for ( ;; ) {
1626                     if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf )) {
1627                         if ( pOp )
1628                             retire_update_desc( pOp, updRetire, false );
1629                         m_Stat.onEraseFailed();
1630                         return false;
1631                     }
1632
1633                     if ( res.updGrandParent.bits() != update_desc::Clean )
1634                         help( res.updGrandParent, updRetire );
1635                     else if ( res.updParent.bits() != update_desc::Clean )
1636                         help( res.updParent, updRetire );
1637                     else {
1638                         if ( !pOp )
1639                             pOp = alloc_update_desc();
1640                         if ( check_delete_precondition( res )) {
1641                             pOp->dInfo.pGrandParent = res.pGrandParent;
1642                             pOp->dInfo.pParent = res.pParent;
1643                             pOp->dInfo.pLeaf = res.pLeaf;
1644                             pOp->dInfo.bDisposeLeaf = true;
1645                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1646                             pOp->dInfo.bRightParent = res.bRightParent;
1647                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1648
1649                             update_ptr updGP( res.updGrandParent.ptr());
1650                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1651                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1652                             {
1653                                 if ( help_delete( pOp, updRetire )) {
1654                                     // res.pLeaf is not deleted yet since RCU is blocked
1655                                     f( *node_traits::to_value_ptr( res.pLeaf ));
1656                                     break;
1657                                 }
1658                                 pOp = nullptr;
1659                             }
1660                             else {
1661                                 // updGP has been changed by CAS
1662                                 help( updGP, updRetire );
1663                             }
1664                         }
1665                     }
1666
1667                     bkoff();
1668                     m_Stat.onEraseRetry();
1669                 }
1670             }
1671
1672             --m_ItemCounter;
1673             m_Stat.onEraseSuccess();
1674             return true;
1675         }
1676
1677         template <typename Q, typename Less>
1678         value_type * extract_with_( Q const& val, Less /*pred*/ )
1679         {
1680             typedef ellen_bintree::details::compare<
1681                 key_type,
1682                 value_type,
1683                 opt::details::make_comparator_from_less<Less>,
1684                 node_traits
1685             > compare_functor;
1686
1687             return extract_( val, compare_functor());
1688         }
1689
1690         template <typename Q, typename Compare>
1691         value_type * extract_( Q const& val, Compare cmp )
1692         {
1693             check_deadlock_policy::check();
1694
1695             retired_list updRetire;
1696             update_desc * pOp = nullptr;
1697             search_result res;
1698             back_off bkoff;
1699             value_type * pResult;
1700
1701             {
1702                 rcu_lock l;
1703                 for ( ;; ) {
1704                     if ( !search( res, val, cmp )) {
1705                         if ( pOp )
1706                             retire_update_desc( pOp, updRetire, false );
1707                         m_Stat.onEraseFailed();
1708                         return nullptr;
1709                     }
1710
1711                     if ( res.updGrandParent.bits() != update_desc::Clean )
1712                         help( res.updGrandParent, updRetire );
1713                     else if ( res.updParent.bits() != update_desc::Clean )
1714                         help( res.updParent, updRetire );
1715                     else {
1716                         if ( !pOp )
1717                             pOp = alloc_update_desc();
1718                         if ( check_delete_precondition( res )) {
1719                             pOp->dInfo.pGrandParent = res.pGrandParent;
1720                             pOp->dInfo.pParent = res.pParent;
1721                             pOp->dInfo.pLeaf = res.pLeaf;
1722                             pOp->dInfo.bDisposeLeaf = false;
1723                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1724                             pOp->dInfo.bRightParent = res.bRightParent;
1725                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1726
1727                             update_ptr updGP( res.updGrandParent.ptr());
1728                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1729                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1730                             {
1731                                 if ( help_delete( pOp, updRetire )) {
1732                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1733                                     break;
1734                                 }
1735                                 pOp = nullptr;
1736                             }
1737                             else {
1738                                 // updGP has been changed by CAS
1739                                 help( updGP, updRetire );
1740                             }
1741                         }
1742                     }
1743
1744                     bkoff();
1745                     m_Stat.onEraseRetry();
1746                 }
1747             }
1748
1749             --m_ItemCounter;
1750             m_Stat.onEraseSuccess();
1751             return pResult;
1752         }
1753
1754
1755         value_type * extract_max_()
1756         {
1757             check_deadlock_policy::check();
1758
1759             retired_list updRetire;
1760             update_desc * pOp = nullptr;
1761             search_result res;
1762             back_off bkoff;
1763             value_type * pResult;
1764
1765             {
1766                 rcu_lock l;
1767                 for ( ;; ) {
1768                     if ( !search_max( res )) {
1769                         // Tree is empty
1770                         if ( pOp )
1771                             retire_update_desc( pOp, updRetire, false );
1772                         m_Stat.onExtractMaxFailed();
1773                         return nullptr;
1774                     }
1775
1776                     if ( res.updGrandParent.bits() != update_desc::Clean )
1777                         help( res.updGrandParent, updRetire );
1778                     else if ( res.updParent.bits() != update_desc::Clean )
1779                         help( res.updParent, updRetire );
1780                     else {
1781                         if ( !pOp )
1782                             pOp = alloc_update_desc();
1783                         if ( check_delete_precondition( res )) {
1784                             pOp->dInfo.pGrandParent = res.pGrandParent;
1785                             pOp->dInfo.pParent = res.pParent;
1786                             pOp->dInfo.pLeaf = res.pLeaf;
1787                             pOp->dInfo.bDisposeLeaf = false;
1788                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1789                             pOp->dInfo.bRightParent = res.bRightParent;
1790                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1791
1792                             update_ptr updGP( res.updGrandParent.ptr());
1793                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1794                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1795                             {
1796                                 if ( help_delete( pOp, updRetire )) {
1797                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1798                                     break;
1799                                 }
1800                                 pOp = nullptr;
1801                             }
1802                             else {
1803                                 // updGP has been changed by CAS
1804                                 help( updGP, updRetire );
1805                             }
1806                         }
1807                     }
1808
1809                     bkoff();
1810                     m_Stat.onExtractMaxRetry();
1811                 }
1812             }
1813
1814             --m_ItemCounter;
1815             m_Stat.onExtractMaxSuccess();
1816             return pResult;
1817         }
1818
1819         value_type * extract_min_()
1820         {
1821             check_deadlock_policy::check();
1822
1823             retired_list updRetire;
1824             update_desc * pOp = nullptr;
1825             search_result res;
1826             back_off bkoff;
1827             value_type * pResult;
1828
1829             {
1830                 rcu_lock l;
1831                 for ( ;; ) {
1832                     if ( !search_min( res )) {
1833                         // Tree is empty
1834                         if ( pOp )
1835                             retire_update_desc( pOp, updRetire, false );
1836                         m_Stat.onExtractMinFailed();
1837                         return nullptr;
1838                     }
1839
1840                     if ( res.updGrandParent.bits() != update_desc::Clean )
1841                         help( res.updGrandParent, updRetire );
1842                     else if ( res.updParent.bits() != update_desc::Clean )
1843                         help( res.updParent, updRetire );
1844                     else {
1845                         if ( !pOp )
1846                             pOp = alloc_update_desc();
1847                         if ( check_delete_precondition( res )) {
1848                             pOp->dInfo.pGrandParent = res.pGrandParent;
1849                             pOp->dInfo.pParent = res.pParent;
1850                             pOp->dInfo.pLeaf = res.pLeaf;
1851                             pOp->dInfo.bDisposeLeaf = false;
1852                             pOp->dInfo.pUpdateParent = res.updParent.ptr();
1853                             pOp->dInfo.bRightParent = res.bRightParent;
1854                             pOp->dInfo.bRightLeaf = res.bRightLeaf;
1855
1856                             update_ptr updGP( res.updGrandParent.ptr());
1857                             if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
1858                                 memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1859                             {
1860                                 if ( help_delete( pOp, updRetire )) {
1861                                     pResult = node_traits::to_value_ptr( res.pLeaf );
1862                                     break;
1863                                 }
1864                                 pOp = nullptr;
1865                             }
1866                             else {
1867                                 // updGP has been changed by CAS
1868                                 help( updGP, updRetire );
1869                             }
1870                         }
1871                     }
1872
1873                     bkoff();
1874                     m_Stat.onExtractMinRetry();
1875                 }
1876             }
1877
1878             --m_ItemCounter;
1879             m_Stat.onExtractMinSuccess();
1880             return pResult;
1881         }
1882
1883         template <typename Q, typename Less, typename Func>
1884         bool find_with_( Q& val, Less /*pred*/, Func f ) const
1885         {
1886             typedef ellen_bintree::details::compare<
1887                 key_type,
1888                 value_type,
1889                 opt::details::make_comparator_from_less<Less>,
1890                 node_traits
1891             > compare_functor;
1892
1893             rcu_lock l;
1894             search_result    res;
1895             if ( search( res, val, compare_functor())) {
1896                 assert( res.pLeaf );
1897                 f( *node_traits::to_value_ptr( res.pLeaf ), val );
1898
1899                 m_Stat.onFindSuccess();
1900                 return true;
1901             }
1902
1903             m_Stat.onFindFailed();
1904             return false;
1905         }
1906
1907         template <typename Q, typename Func>
1908         bool find_( Q& key, Func f ) const
1909         {
1910             rcu_lock l;
1911             search_result    res;
1912             if ( search( res, key, node_compare())) {
1913                 assert( res.pLeaf );
1914                 f( *node_traits::to_value_ptr( res.pLeaf ), key );
1915
1916                 m_Stat.onFindSuccess();
1917                 return true;
1918             }
1919
1920             m_Stat.onFindFailed();
1921             return false;
1922         }
1923
1924         template <typename Q, typename Compare>
1925         value_type * get_( Q const& key, Compare cmp ) const
1926         {
1927             assert( gc::is_locked());
1928
1929             search_result    res;
1930             if ( search( res, key, cmp )) {
1931                 m_Stat.onFindSuccess();
1932                 return node_traits::to_value_ptr( res.pLeaf );
1933             }
1934
1935             m_Stat.onFindFailed();
1936             return nullptr;
1937         }
1938
1939
1940         bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res, retired_list& updRetire )
1941         {
1942             assert( gc::is_locked());
1943             assert( res.updParent.bits() == update_desc::Clean );
1944
1945             // check search result
1946             if ( static_cast<leaf_node *>( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_relaxed )) == res.pLeaf ) {
1947                 leaf_node * pNewLeaf = node_traits::to_node_ptr( val );
1948
1949                 int nCmp = node_compare()( val, *res.pLeaf );
1950                 if ( nCmp < 0 ) {
1951                     if ( res.pGrandParent ) {
1952                         pNewInternal->infinite_key( 0 );
1953                         key_extractor()( pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
1954                         assert( !res.pLeaf->infinite_key());
1955                     }
1956                     else {
1957                         assert( res.pLeaf->infinite_key() == tree_node::key_infinite1 );
1958                         pNewInternal->infinite_key( 1 );
1959                     }
1960                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_relaxed );
1961                     pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
1962                 }
1963                 else {
1964                     assert( !res.pLeaf->is_internal());
1965                     pNewInternal->infinite_key( 0 );
1966
1967                     key_extractor()( pNewInternal->m_Key, val );
1968                     pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
1969                     pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
1970                     assert( !res.pLeaf->infinite_key());
1971                 }
1972
1973                 update_desc * pOp = alloc_update_desc();
1974
1975                 pOp->iInfo.pParent = res.pParent;
1976                 pOp->iInfo.pNew = pNewInternal;
1977                 pOp->iInfo.pLeaf = res.pLeaf;
1978                 pOp->iInfo.bRightLeaf = res.bRightLeaf;
1979
1980                 update_ptr updCur( res.updParent.ptr());
1981                 if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
1982                     memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1983                 {
1984                     // do insert
1985                     help_insert( pOp );
1986                     retire_update_desc( pOp, updRetire, false );
1987                     return true;
1988                 }
1989                 else {
1990                     // updCur has been updated by CAS
1991                     help( updCur, updRetire );
1992                     retire_update_desc( pOp, updRetire, true );
1993                 }
1994             }
1995             return false;
1996         }
1997
1998         //@endcond
1999     };
2000
2001 }} // namespace cds::intrusive
2002
2003 #endif  // #ifndef CDSLIB_INTRUSIVE_ELLEN_BINTREE_RCU_H