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