cds/intrusive/split_list.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_SPLIT_LIST_H
  32 #define CDSLIB_INTRUSIVE_SPLIT_LIST_H
  33
  34 #include <limits>
  35 #include <cds/intrusive/details/split_list_base.h>
  36 #include <cds/details/type_padding.h>
  37
  38 namespace cds { namespace intrusive {
  39
  40     /// Split-ordered list
  41     /** @ingroup cds_intrusive_map
  42         \anchor cds_intrusive_SplitListSet_hp
  43
  44         Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
  45         - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
  46         - [2008] Nir Shavit "The Art of Multiprocessor Programming"
  47
  48         The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
  49         recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
  50         without item moving on resizing.
  51
  52         \anchor cds_SplitList_algo_desc
  53         <b>Short description</b>
  54         [from [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"]
  55
  56         The algorithm keeps all the items in one lock-free linked list, and gradually assigns the bucket pointers to
  57         the places in the list where a sublist of 'correct' items can be found. A bucket is initialized upon first
  58         access by assigning it to a new 'dummy' node (dashed contour) in the list, preceding all items that should be
  59         in that bucket. A newly created bucket splits an older bucket's chain, reducing the access cost to its items. The
  60         table uses a modulo 2**i hash (there are known techniques for 'pre-hashing' before a modulo 2**i hash
  61         to overcome possible binary correlations among values). The table starts at size 2 and repeatedly doubles in size.
  62
  63         Unlike moving an item, the operation of directing a bucket pointer can be done
  64         in a single CAS operation, and since items are not moved, they are never 'lost'.
  65         However, to make this approach work, one must be able to keep the items in the
  66         list sorted in such a way that any bucket's sublist can be 'split' by directing a new
  67         bucket pointer within it. This operation must be recursively repeatable, as every
  68         split bucket may be split again and again as the hash table grows. To achieve this
  69         goal the authors introduced recursive split-ordering, a new ordering on keys that keeps items
  70         in a given bucket adjacent in the list throughout the repeated splitting process.
  71
  72         Magically, yet perhaps not surprisingly, recursive split-ordering is achieved by
  73         simple binary reversal: reversing the bits of the hash key so that the new key's
  74         most significant bits (MSB) are those that were originally its least significant.
  75         The split-order keys of regular nodes are exactly the bit-reverse image of the original
  76         keys after turning on their MSB. For example, items 9 and 13 are in the <tt>1 mod
  77         4</tt> bucket, which can be recursively split in two by inserting a new node between
  78         them.
  79
  80         To insert (respectively delete or search for) an item in the hash table, hash its
  81         key to the appropriate bucket using recursive split-ordering, follow the pointer to
  82         the appropriate location in the sorted items list, and traverse the list until the key's
  83         proper location in the split-ordering (respectively until the key or a key indicating
  84         the item is not in the list is found). Because of the combinatorial structure induced
  85         by the split-ordering, this will require traversal of no more than an expected constant number of items.
  86
  87         The design is modular: to implement the ordered items list, you can use one of several
  88         non-blocking list-based set algorithms: MichaelList, LazyList.
  89
  90         <b>Implementation</b>
  91
  92         Template parameters are:
  93         - \p GC - Garbage collector. Note the \p GC must be the same as the \p GC used for \p OrderedList
  94         - \p OrderedList - ordered list implementation used as a bucket for hash set, for example, \p MichaelList, \p LazyList.
  95             The intrusive ordered list implementation specifies the type \p T stored in the split-list set, the comparison
  96             functor for the type \p T and other features specific for the ordered list.
  97         - \p Traits - split-list traits, default is \p split_list::traits.
  98             Instead of defining \p Traits struct you can use option-based syntax provided by \p split_list::make_traits metafunction.
  99
 100         There are several specialization of the split-list class for different \p GC:
 101         - for \ref cds_urcu_gc "RCU type" include <tt><cds/intrusive/split_list_rcu.h></tt> - see
 102             \ref cds_intrusive_SplitListSet_rcu "RCU-based split-list"
 103         - for cds::gc::nogc include <tt><cds/intrusive/split_list_nogc.h></tt> - see
 104             \ref cds_intrusive_SplitListSet_nogc "persistent SplitListSet".
 105
 106         \anchor cds_SplitList_hash_functor
 107         <b>Hash functor</b>
 108
 109         Some member functions of split-ordered list accept the key parameter of type \p Q which differs from \p value_type.
 110         It is expected that type \p Q contains full key of \p value_type, and for equal keys of type \p Q and \p value_type
 111         the hash values of these keys must be equal too.
 112         The hash functor \p Traits::hash should accept parameters of both type:
 113         \code
 114         // Our node type
 115         struct Foo {
 116             std::string     key_    ;   // key field
 117             // ... other fields
 118         };
 119
 120         // Hash functor
 121         struct fooHash {
 122             size_t operator()( const std::string& s ) const
 123             {
 124                 return std::hash( s );
 125             }
 126
 127             size_t operator()( const Foo& f ) const
 128             {
 129                 return (*this)( f.key_ );
 130             }
 131         };
 132         \endcode
 133
 134         <b>How to use</b>
 135
 136         Split-list based on \p IterableList differs from split-list based on \p MichaelList or \p LazyList
 137         because \p %IterableList stores data "as is" - it cannot use any hook.
 138
 139         Suppose, your split-list contains values of type \p Foo.
 140         For \p %MichaelList and \p %LazyList, \p Foo declaration should be based on ordered-list node:
 141         - \p %MichaelList:
 142         \code
 143         struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
 144         {
 145             // ... field declarations
 146         };
 147         \endcode
 148         - \p %LazyList:
 149         \code
 150         struct Foo: public cds::intrusive::split_list::node< cds::intrusive::lazy_list::node< cds::gc::HP > >
 151         {
 152             // ... field declarations
 153         };
 154         \endcode
 155
 156         For \p %IterableList, \p Foo should be based on \p void:
 157         \code
 158         struct Foo: public cds::intrusive::split_list::node<void>
 159         {
 160             // ... field declarations
 161         };
 162         \endcode
 163
 164         Everything else is the same.
 165         Consider split-list based on \p MichaelList.
 166
 167         First, you should choose ordered list type to use in your split-list set:
 168         \code
 169         // For gc::HP-based MichaelList implementation
 170         #include <cds/intrusive/michael_list_hp.h>
 171
 172         // cds::intrusive::SplitListSet declaration
 173         #include <cds/intrusive/split_list.h>
 174
 175         // Type of set items
 176             //  Note you should declare your struct based on cds::intrusive::split_list::node
 177             //  which is a wrapper for ordered-list node struct.
 178             //  In our case, the node type for HP-based MichaelList is cds::intrusive::michael_list::node< cds::gc::HP >
 179         struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
 180         {
 181             std::string     key_    ;   // key field
 182             unsigned        val_    ;   // value field
 183             // ...  other value fields
 184         };
 185
 186         // Declare comparator for the item
 187         struct FooCmp
 188         {
 189             int operator()( const Foo& f1, const Foo& f2 ) const
 190             {
 191                 return f1.key_.compare( f2.key_ );
 192             }
 193         };
 194
 195         // Declare base ordered-list type for split-list
 196         typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
 197             typename cds::intrusive::michael_list::make_traits<
 198                 // hook option
 199                 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
 200                 // item comparator option
 201                 ,cds::opt::compare< FooCmp >
 202             >::type
 203         >  Foo_list;
 204         \endcode
 205
 206         Second, you should declare split-list set container:
 207         \code
 208
 209         // Declare hash functor
 210         // Note, the hash functor accepts parameter type Foo and std::string
 211         struct FooHash {
 212             size_t operator()( const Foo& f ) const
 213             {
 214                 return cds::opt::v::hash<std::string>()( f.key_ );
 215             }
 216             size_t operator()( const std::string& s ) const
 217             {
 218                 return cds::opt::v::hash<std::string>()( s );
 219             }
 220         };
 221
 222         // Split-list set typedef
 223         typedef cds::intrusive::SplitListSet<
 224             cds::gc::HP
 225             ,Foo_list
 226             ,typename cds::intrusive::split_list::make_traits<
 227                 cds::opt::hash< FooHash >
 228             >::type
 229         > Foo_set;
 230         \endcode
 231
 232         Now, you can use \p Foo_set in your application.
 233         \code
 234             Foo_set    fooSet;
 235             Foo * foo = new Foo;
 236             foo->key_ = "First";
 237
 238             fooSet.insert( *foo );
 239
 240             // and so on ...
 241         \endcode
 242     */
 243     template <
 244         class GC,
 245         class OrderedList,
 246 #   ifdef CDS_DOXYGEN_INVOKED
 247         class Traits = split_list::traits
 248 #   else
 249         class Traits
 250 #   endif
 251     >
 252     class SplitListSet
 253     {
 254     public:
 255         typedef GC     gc;     ///< Garbage collector
 256         typedef Traits traits; ///< Set traits
 257
 258     protected:
 259         //@cond
 260         typedef split_list::details::rebind_list_traits<OrderedList, traits> ordered_list_adapter;
 261         //@endcond
 262
 263     public:
 264 #   ifdef CDS_DOXYGEN_INVOKED
 265         typedef OrderedList         ordered_list;   ///< type of ordered list used as a base for split-list
 266 #   else
 267         typedef typename ordered_list_adapter::result   ordered_list;
 268 #   endif
 269         typedef typename ordered_list::value_type       value_type;     ///< type of value stored in the split-list
 270         typedef typename ordered_list::key_comparator   key_comparator; ///< key comparison functor
 271         typedef typename ordered_list::disposer         disposer;       ///< Node disposer functor
 272
 273         /// Hash functor for \p %value_type and all its derivatives you use
 274         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
 275
 276         typedef typename traits::bit_reversal      bit_reversal; ///< Bit reversal algorithm, see \p split_list::traits::bit_reversal
 277         typedef typename traits::item_counter      item_counter; ///< Item counter type
 278         typedef typename traits::back_off          back_off;     ///< back-off strategy for spinning
 279         typedef typename traits::memory_model      memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
 280         typedef typename traits::stat              stat;         ///< Internal statistics, see \p spit_list::stat
 281         typedef typename ordered_list::guarded_ptr guarded_ptr;  ///< Guarded pointer
 282
 283         /// Count of hazard pointer required
 284         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount + 4; // +4 - for iterators
 285
 286     protected:
 287         //@cond
 288         typedef split_list::node<typename ordered_list_adapter::ordered_list_node_type> node_type; ///< split-list node type
 289         typedef typename ordered_list_adapter::node_traits node_traits;
 290
 291         /// Bucket table implementation
 292         typedef typename split_list::details::bucket_table_selector<
 293             traits::dynamic_bucket_table
 294             , gc
 295             , typename ordered_list_adapter::aux_node
 296             , opt::allocator< typename traits::allocator >
 297             , opt::memory_model< memory_model >
 298             , opt::free_list< typename traits::free_list >
 299         >::type bucket_table;
 300
 301         typedef typename bucket_table::aux_node_type aux_node_type;   ///< auxiliary node type
 302         //@endcond
 303
 304     protected:
 305         //@cond
 306         /// Ordered list wrapper to access protected members
 307         class ordered_list_wrapper: public ordered_list
 308         {
 309             typedef ordered_list base_class;
 310             typedef typename base_class::auxiliary_head bucket_head_type;
 311
 312         public:
 313             bool insert_at( aux_node_type* pHead, value_type& val )
 314             {
 315                 assert( pHead != nullptr );
 316                 bucket_head_type h(pHead);
 317                 return base_class::insert_at( h, val );
 318             }
 319
 320             template <typename Func>
 321             bool insert_at( aux_node_type * pHead, value_type& val, Func f )
 322             {
 323                 assert( pHead != nullptr );
 324                 bucket_head_type h(pHead);
 325                 return base_class::insert_at( h, val, f );
 326             }
 327
 328             template <typename Func>
 329             std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 330             {
 331                 assert( pHead != nullptr );
 332                 bucket_head_type h(pHead);
 333                 return base_class::update_at( h, val, func, bAllowInsert );
 334             }
 335
 336             template <typename Q>
 337             typename std::enable_if<
 338                 std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
 339                 std::pair<bool, bool>
 340             >::type
 341             upsert_at( aux_node_type * pHead, Q& val, bool bAllowInsert )
 342             {
 343                 assert( pHead != nullptr );
 344                 bucket_head_type h( pHead );
 345                 return base_class::upsert_at( h, val, bAllowInsert );
 346             }
 347
 348             bool unlink_at( aux_node_type * pHead, value_type& val )
 349             {
 350                 assert( pHead != nullptr );
 351                 bucket_head_type h(pHead);
 352                 return base_class::unlink_at( h, val );
 353             }
 354
 355             template <typename Iterator>
 356             typename std::enable_if<
 357                 std::is_same< Iterator, typename ordered_list::iterator>::value && is_iterable_list< ordered_list >::value,
 358                 bool
 359             >::type
 360             erase_at( Iterator iter )
 361             {
 362                 return base_class::erase_at( iter );
 363             }
 364
 365             template <typename Q, typename Compare, typename Func>
 366             bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
 367             {
 368                 assert( pHead != nullptr );
 369                 bucket_head_type h(pHead);
 370                 return base_class::erase_at( h, val, cmp, f );
 371             }
 372
 373             template <typename Q, typename Compare>
 374             bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 375             {
 376                 assert( pHead != nullptr );
 377                 bucket_head_type h(pHead);
 378                 return base_class::erase_at( h, val, cmp );
 379             }
 380
 381             template <typename Q, typename Compare>
 382             guarded_ptr extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 383             {
 384                 assert( pHead != nullptr );
 385                 bucket_head_type h(pHead);
 386                 return base_class::extract_at( h, val, cmp );
 387             }
 388
 389             template <typename Q, typename Compare, typename Func>
 390             bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
 391             {
 392                 assert( pHead != nullptr );
 393                 bucket_head_type h(pHead);
 394                 return base_class::find_at( h, val, cmp, f );
 395             }
 396
 397             template <typename Q, typename Compare>
 398             bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 399             {
 400                 assert( pHead != nullptr );
 401                 bucket_head_type h(pHead);
 402                 return base_class::find_at( h, val, cmp );
 403             }
 404
 405             template <typename Q, typename Compare>
 406             typename std::enable_if<
 407                 std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value,
 408                 typename base_class::iterator
 409             >::type
 410             find_iterator_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 411             {
 412                 assert( pHead != nullptr );
 413                 bucket_head_type h( pHead );
 414                 return base_class::find_iterator_at( h, val, cmp );
 415             }
 416
 417             template <typename Q, typename Compare>
 418             guarded_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 419             {
 420                 assert( pHead != nullptr );
 421                 bucket_head_type h(pHead);
 422                 return base_class::get_at( h, val, cmp );
 423             }
 424
 425             bool insert_aux_node( aux_node_type * pNode )
 426             {
 427                 return base_class::insert_aux_node( pNode );
 428             }
 429             bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
 430             {
 431                 bucket_head_type h(pHead);
 432                 return base_class::insert_aux_node( h, pNode );
 433             }
 434
 435             template <typename Predicate>
 436             void destroy( Predicate pred )
 437             {
 438                 base_class::destroy( pred );
 439             }
 440         };
 441         //@endcond
 442
 443     protected:
 444         //@cond
 445         template <bool IsConst>
 446         class iterator_type
 447             : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 448         {
 449             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 450             typedef typename iterator_base_class::list_iterator list_iterator;
 451
 452             friend class SplitListSet;
 453
 454         public:
 455             iterator_type()
 456                 : iterator_base_class()
 457             {}
 458
 459             iterator_type( iterator_type const& src )
 460                 : iterator_base_class( src )
 461             {}
 462
 463             // This ctor should be protected...
 464             iterator_type( list_iterator itCur, list_iterator itEnd )
 465                 : iterator_base_class( itCur, itEnd )
 466             {}
 467         };
 468         //@endcond
 469
 470     public:
 471     ///@name Forward iterators
 472     //@{
 473         /// Forward iterator
 474         /**
 475             The forward iterator is based on \p OrderedList forward iterator and has some features:
 476             - it has no post-increment operator
 477             - it iterates items in unordered fashion
 478             - iterator cannot be moved across thread boundary because it may contain GC's guard that is thread-private GC data.
 479
 480             Iterator thread safety depends on type of \p OrderedList:
 481             - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to
 482               because that item is guarded by hazard pointer.
 483               However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set.
 484               Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
 485               Use this iterator on the concurrent container for debugging purpose only.
 486             - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
 487         */
 488         typedef iterator_type<false>    iterator;
 489
 490         /// Const forward iterator
 491         /**
 492             For iterator's features and requirements see \ref iterator
 493         */
 494         typedef iterator_type<true>     const_iterator;
 495
 496         /// Returns a forward iterator addressing the first element in a split-list
 497         /**
 498             For empty list \code begin() == end() \endcode
 499         */
 500         iterator begin()
 501         {
 502             return iterator( m_List.begin(), m_List.end());
 503         }
 504
 505         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 506         /**
 507             Do not use the value returned by <tt>end</tt> function to access any item.
 508
 509             The returned value can be used only to control reaching the end of the split-list.
 510             For empty list \code begin() == end() \endcode
 511         */
 512         iterator end()
 513         {
 514             return iterator( m_List.end(), m_List.end());
 515         }
 516
 517         /// Returns a forward const iterator addressing the first element in a split-list
 518         const_iterator begin() const
 519         {
 520             return cbegin();
 521         }
 522         /// Returns a forward const iterator addressing the first element in a split-list
 523         const_iterator cbegin() const
 524         {
 525             return const_iterator( m_List.cbegin(), m_List.cend());
 526         }
 527
 528         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 529         const_iterator end() const
 530         {
 531             return cend();
 532         }
 533         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 534         const_iterator cend() const
 535         {
 536             return const_iterator( m_List.cend(), m_List.cend());
 537         }
 538     //@}
 539
 540     public:
 541         /// Initialize split-ordered list of default capacity
 542         /**
 543             The default capacity is defined in bucket table constructor.
 544             See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
 545             which selects by \p split_list::dynamic_bucket_table option.
 546         */
 547         SplitListSet()
 548             : m_nBucketCountLog2(1)
 549             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
 550         {
 551             init();
 552         }
 553
 554         /// Initialize split-ordered list
 555         SplitListSet(
 556             size_t nItemCount           ///< estimate average of item count
 557             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
 558             )
 559             : m_Buckets( nItemCount, nLoadFactor )
 560             , m_nBucketCountLog2(1)
 561             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
 562         {
 563             init();
 564         }
 565
 566         /// Destroys split-list set
 567         ~SplitListSet()
 568         {
 569             // list contains aux node that cannot be retired
 570             // all aux nodes will be destroyed by bucket table dtor
 571             m_List.destroy(
 572                 []( node_type * pNode ) -> bool {
 573                     return !pNode->is_dummy();
 574                 }
 575             );
 576             gc::force_dispose();
 577         }
 578
 579     public:
 580         /// Inserts new node
 581         /**
 582             The function inserts \p val in the set if it does not contain
 583             an item with key equal to \p val.
 584
 585             Returns \p true if \p val is placed into the set, \p false otherwise.
 586         */
 587         bool insert( value_type& val )
 588         {
 589             size_t nHash = hash_value( val );
 590             aux_node_type * pHead = get_bucket( nHash );
 591             assert( pHead != nullptr );
 592
 593             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
 594
 595             if ( m_List.insert_at( pHead, val )) {
 596                 inc_item_count();
 597                 m_Stat.onInsertSuccess();
 598                 return true;
 599             }
 600             m_Stat.onInsertFailed();
 601             return false;
 602         }
 603
 604         /// Inserts new node
 605         /**
 606             This function is intended for derived non-intrusive containers.
 607
 608             The function allows to split creating of new item into two part:
 609             - create item with key only
 610             - insert new item into the set
 611             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 612
 613             The functor signature is:
 614             \code
 615                 void func( value_type& val );
 616             \endcode
 617             where \p val is the item inserted.
 618             The user-defined functor is called only if the inserting is success.
 619
 620             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 621             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 622             synchronization.
 623         */
 624         template <typename Func>
 625         bool insert( value_type& val, Func f )
 626         {
 627             size_t nHash = hash_value( val );
 628             aux_node_type * pHead = get_bucket( nHash );
 629             assert( pHead != nullptr );
 630
 631             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
 632
 633             if ( m_List.insert_at( pHead, val, f )) {
 634                 inc_item_count();
 635                 m_Stat.onInsertSuccess();
 636                 return true;
 637             }
 638             m_Stat.onInsertFailed();
 639             return false;
 640         }
 641
 642         /// Updates the node
 643         /**
 644             The operation performs inserting or changing data with lock-free manner.
 645
 646             If the item \p val is not found in the set, then \p val is inserted
 647             iff \p bAllowInsert is \p true.
 648             Otherwise, the functor \p func is called with item found.
 649
 650             The functor signature depends of the type of \p OrderedList:
 651
 652             <b>for \p MichaelList, \p LazyList</b>
 653                 \code
 654                     struct functor {
 655                         void operator()( bool bNew, value_type& item, value_type& val );
 656                     };
 657                 \endcode
 658                 with arguments:
 659                 - \p bNew - \p true if the item has been inserted, \p false otherwise
 660                 - \p item - item of the set
 661                 - \p val - argument \p val passed into the \p %update() function
 662                 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 663                 refers to the same thing.
 664
 665                 The functor may change non-key fields of the \p item.
 666                 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 667                 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 668                 synchronization.
 669
 670             <b>for \p IterableList</b>
 671                 \code
 672                 void func( value_type& val, value_type * old );
 673                 \endcode
 674                 where
 675                 - \p val - argument \p val passed into the \p %update() function
 676                 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
 677
 678             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 679             \p second is \p true if new item has been added or \p false if the item with \p val
 680             already is in the list.
 681         */
 682         template <typename Func>
 683         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 684         {
 685             size_t nHash = hash_value( val );
 686             aux_node_type * pHead = get_bucket( nHash );
 687             assert( pHead != nullptr );
 688
 689             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
 690
 691             std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
 692             if ( bRet.first && bRet.second ) {
 693                 inc_item_count();
 694                 m_Stat.onUpdateNew();
 695             }
 696             else
 697                 m_Stat.onUpdateExist();
 698             return bRet;
 699         }
 700         //@cond
 701         template <typename Func>
 702         CDS_DEPRECATED("ensure() is deprecated, use update()")
 703         std::pair<bool, bool> ensure( value_type& val, Func func )
 704         {
 705             return update( val, func, true );
 706         }
 707         //@endcond
 708
 709         /// Inserts or updates the node (only for \p IterableList)
 710         /**
 711             The operation performs inserting or changing data with lock-free manner.
 712
 713             If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
 714             Otherwise, the current element is changed to \p val, the old element will be retired later
 715             by call \p Traits::disposer.
 716
 717             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 718             \p second is \p true if \p val has been added or \p false if the item with that key
 719             already in the set.
 720         */
 721 #ifdef CDS_DOXYGEN_INVOKED
 722         std::pair<bool, bool> upsert( value_type& val, bool bAllowInsert = true )
 723 #else
 724         template <typename Q>
 725         typename std::enable_if<
 726             std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
 727             std::pair<bool, bool>
 728         >::type
 729         upsert( Q& val, bool bAllowInsert = true )
 730 #endif
 731         {
 732             size_t nHash = hash_value( val );
 733             aux_node_type * pHead = get_bucket( nHash );
 734             assert( pHead != nullptr );
 735
 736             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
 737
 738             std::pair<bool, bool> bRet = m_List.upsert_at( pHead, val, bAllowInsert );
 739             if ( bRet.first && bRet.second ) {
 740                 inc_item_count();
 741                 m_Stat.onUpdateNew();
 742             }
 743             else
 744                 m_Stat.onUpdateExist();
 745             return bRet;
 746         }
 747
 748         /// Unlinks the item \p val from the set
 749         /**
 750             The function searches the item \p val in the set and unlinks it from the set
 751             if it is found and is equal to \p val.
 752
 753             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 754             and deletes the item found. \p unlink finds an item by key and deletes it
 755             only if \p val is an item of that set, i.e. the pointer to item found
 756             is equal to <tt> &val </tt>.
 757
 758             The function returns \p true if success and \p false otherwise.
 759         */
 760         bool unlink( value_type& val )
 761         {
 762             size_t nHash = hash_value( val );
 763             aux_node_type * pHead = get_bucket( nHash );
 764             assert( pHead != nullptr );
 765
 766             if ( m_List.unlink_at( pHead, val )) {
 767                 --m_ItemCounter;
 768                 m_Stat.onEraseSuccess();
 769                 return true;
 770             }
 771             m_Stat.onEraseFailed();
 772             return false;
 773         }
 774
 775         /// Deletes the item from the set
 776         /** \anchor cds_intrusive_SplitListSet_hp_erase
 777             The function searches an item with key equal to \p key in the set,
 778             unlinks it from the set, and returns \p true.
 779             If the item with key equal to \p key is not found the function return \p false.
 780
 781             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 782             and deletes the item found. \p unlink finds an item by key and deletes it
 783             only if \p key is an item of that set, i.e. the pointer to item found
 784             is equal to <tt> &key </tt>.
 785
 786             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 787         */
 788         template <typename Q>
 789         bool erase( Q const& key )
 790         {
 791             return erase_( key, key_comparator());
 792         }
 793
 794         /// Deletes the item from the set with comparing functor \p pred
 795         /**
 796
 797             The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
 798             but \p pred predicate is used for key comparing.
 799             \p Less has the interface like \p std::less.
 800             \p pred must imply the same element order as the comparator used for building the set.
 801         */
 802         template <typename Q, typename Less>
 803         bool erase_with( const Q& key, Less pred )
 804         {
 805             CDS_UNUSED( pred );
 806             return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
 807         }
 808
 809         /// Deletes the item from the set
 810         /** \anchor cds_intrusive_SplitListSet_hp_erase_func
 811             The function searches an item with key equal to \p key in the set,
 812             call \p f functor with item found, unlinks it from the set, and returns \p true.
 813             The \ref disposer specified by \p OrderedList class template parameter is called
 814             by garbage collector \p GC asynchronously.
 815
 816             The \p Func interface is
 817             \code
 818             struct functor {
 819                 void operator()( value_type const& item );
 820             };
 821             \endcode
 822
 823             If the item with key equal to \p key is not found the function return \p false.
 824
 825             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 826         */
 827         template <typename Q, typename Func>
 828         bool erase( Q const& key, Func f )
 829         {
 830             return erase_( key, key_comparator(), f );
 831         }
 832
 833         /// Deletes the item from the set with comparing functor \p pred
 834         /**
 835             The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
 836             but \p pred predicate is used for key comparing.
 837             \p Less has the interface like \p std::less.
 838             \p pred must imply the same element order as the comparator used for building the set.
 839         */
 840         template <typename Q, typename Less, typename Func>
 841         bool erase_with( Q const& key, Less pred, Func f )
 842         {
 843             CDS_UNUSED( pred );
 844             return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
 845         }
 846
 847         /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set)
 848         /**
 849             Returns \p true if the operation is successful, \p false otherwise.
 850             The function can return \p false if the node the iterator points to has already been deleted
 851             by other thread.
 852
 853             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 854
 855             @note \p %erase_at() is supported only for \p %SplitListSet based on \p IterableList.
 856         */
 857 #ifdef CDS_DOXYGEN_INVOKED
 858         bool erase_at( iterator const& iter )
 859 #else
 860         template <typename Iterator>
 861         typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
 862         erase_at( Iterator const& iter )
 863 #endif
 864         {
 865             assert( iter != end());
 866
 867             if ( m_List.erase_at( iter.underlying_iterator())) {
 868                 --m_ItemCounter;
 869                 m_Stat.onEraseSuccess();
 870                 return true;
 871             }
 872             return false;
 873         }
 874
 875         /// Extracts the item with specified \p key
 876         /** \anchor cds_intrusive_SplitListSet_hp_extract
 877             The function searches an item with key equal to \p key,
 878             unlinks it from the set, and returns it as \p guarded_ptr.
 879             If \p key is not found the function returns an empty guarded pointer.
 880
 881             Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
 882
 883             The \p disposer specified in \p OrderedList class' template parameter is called automatically
 884             by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
 885             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 886
 887             Usage:
 888             \code
 889             typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
 890             splitlist_set theSet;
 891             // ...
 892             {
 893                 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
 894                 if ( gp) {
 895                     // Deal with gp
 896                     // ...
 897                 }
 898                 // Destructor of gp releases internal HP guard
 899             }
 900             \endcode
 901         */
 902         template <typename Q>
 903         guarded_ptr extract( Q const& key )
 904         {
 905             return extract_( key );
 906         }
 907
 908         /// Extracts the item using compare functor \p pred
 909         /**
 910             The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
 911             but \p pred predicate is used for key comparing.
 912
 913             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 914             in any order.
 915             \p pred must imply the same element order as the comparator used for building the set.
 916         */
 917         template <typename Q, typename Less>
 918         guarded_ptr extract_with( Q const& key, Less pred )
 919         {
 920             return extract_with_( key, pred );
 921         }
 922
 923         /// Finds the key \p key
 924         /** \anchor cds_intrusive_SplitListSet_hp_find_func
 925             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 926             The interface of \p Func functor is:
 927             \code
 928             struct functor {
 929                 void operator()( value_type& item, Q& key );
 930             };
 931             \endcode
 932             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 933
 934             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 935             that \p item cannot be disposed during functor is executing.
 936             The functor does not serialize simultaneous access to the set \p item. If such access is
 937             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 938
 939             Note the hash functor specified for class \p Traits template parameter
 940             should accept a parameter of type \p Q that can be not the same as \p value_type.
 941
 942             The function returns \p true if \p key is found, \p false otherwise.
 943         */
 944         template <typename Q, typename Func>
 945         bool find( Q& key, Func f )
 946         {
 947             return find_( key, key_comparator(), f );
 948         }
 949         //@cond
 950         template <typename Q, typename Func>
 951         bool find( Q const& key, Func f )
 952         {
 953             return find_( key, key_comparator(), f );
 954         }
 955         //@endcond
 956
 957         /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
 958         /**
 959             If \p key is not found the function returns \p end().
 960
 961             @note This function is supported only for the set based on \p IterableList
 962         */
 963         template <typename Q>
 964 #ifdef CDS_DOXYGEN_INVOKED
 965         iterator
 966 #else
 967         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
 968 #endif
 969         find( Q& key )
 970         {
 971             return find_iterator_( key, key_comparator());
 972         }
 973         //@cond
 974         template <typename Q>
 975         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
 976         find( Q const& key )
 977         {
 978             return find_iterator_( key, key_comparator());
 979         }
 980         //@endcond
 981
 982
 983         /// Finds the key \p key with \p pred predicate for comparing
 984         /**
 985             The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
 986             but \p cmp is used for key compare.
 987             \p Less has the interface like \p std::less.
 988             \p cmp must imply the same element order as the comparator used for building the set.
 989         */
 990         template <typename Q, typename Less, typename Func>
 991         bool find_with( Q& key, Less pred, Func f )
 992         {
 993             CDS_UNUSED( pred );
 994             return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
 995         }
 996         //@cond
 997         template <typename Q, typename Less, typename Func>
 998         bool find_with( Q const& key, Less pred, Func f )
 999         {
1000             CDS_UNUSED( pred );
1001             return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
1002         }
1003         //@endcond
1004
1005         /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
1006         /**
1007             The function is an analog of \p find(Q&) but \p pred is used for key comparing.
1008             \p Less functor has the interface like \p std::less.
1009             \p pred must imply the same element order as the comparator used for building the set.
1010
1011             If \p key is not found the function returns \p end().
1012
1013             @note This function is supported only for the set based on \p IterableList
1014         */
1015         template <typename Q, typename Less>
1016 #ifdef CDS_DOXYGEN_INVOKED
1017         iterator
1018 #else
1019         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
1020 #endif
1021         find_with( Q& key, Less pred )
1022         {
1023             CDS_UNUSED( pred );
1024             return find_iterator_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1025         }
1026         //@cond
1027         template <typename Q, typename Less>
1028         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
1029         find_with( Q const& key, Less pred )
1030         {
1031             CDS_UNUSED( pred );
1032             return find_iterator_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1033         }
1034         //@endcond
1035
1036
1037         /// Checks whether the set contains \p key
1038         /**
1039             The function searches the item with key equal to \p key
1040             and returns \p true if it is found, and \p false otherwise.
1041
1042             Note the hash functor specified for class \p Traits template parameter
1043             should accept a parameter of type \p Q that can be not the same as \p value_type.
1044             Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
1045         */
1046         template <typename Q>
1047         bool contains( Q const& key )
1048         {
1049             return find_( key, key_comparator());
1050         }
1051
1052         /// Checks whether the set contains \p key using \p pred predicate for searching
1053         /**
1054             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
1055             \p Less functor has the interface like \p std::less.
1056             \p Less must imply the same element order as the comparator used for building the set.
1057         */
1058         template <typename Q, typename Less>
1059         bool contains( Q const& key, Less pred )
1060         {
1061             CDS_UNUSED( pred );
1062             return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1063         }
1064
1065         /// Finds the key \p key and return the item found
1066         /** \anchor cds_intrusive_SplitListSet_hp_get
1067             The function searches the item with key equal to \p key
1068             and returns the item found as \p guarded_ptr.
1069             If \p key is not found the function returns an empty guarded pointer.
1070
1071             The \p disposer specified in \p OrderedList class' template parameter is called
1072             by garbage collector \p GC automatically when returned \p guarded_ptr object
1073             will be destroyed or released.
1074             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1075
1076             Usage:
1077             \code
1078             typedef cds::intrusive::SplitListSet< your_template_params >  splitlist_set;
1079             splitlist_set theSet;
1080             // ...
1081             {
1082                 splitlist_set::guarded_ptr gp = theSet.get( 5 );
1083                 if ( gp ) {
1084                     // Deal with gp
1085                     //...
1086                 }
1087                 // Destructor of guarded_ptr releases internal HP guard
1088             }
1089             \endcode
1090
1091             Note the compare functor specified for \p OrderedList template parameter
1092             should accept a parameter of type \p Q that can be not the same as \p value_type.
1093         */
1094         template <typename Q>
1095         guarded_ptr get( Q const& key )
1096         {
1097             return get_( key );
1098         }
1099
1100         /// Finds the key \p key and return the item found
1101         /**
1102             The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
1103             but \p pred is used for comparing the keys.
1104
1105             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1106             in any order.
1107             \p pred must imply the same element order as the comparator used for building the set.
1108         */
1109         template <typename Q, typename Less>
1110         guarded_ptr get_with( Q const& key, Less pred )
1111         {
1112             return get_with_( key, pred );
1113         }
1114
1115         /// Returns item count in the set
1116         size_t size() const
1117         {
1118             return m_ItemCounter;
1119         }
1120
1121         /// Checks if the set is empty
1122         /**
1123             Emptiness is checked by item counting: if item count is zero then the set is empty.
1124             Thus, the correct item counting feature is an important part of split-list set implementation.
1125         */
1126         bool empty() const
1127         {
1128             return size() == 0;
1129         }
1130
1131         /// Clears the set (non-atomic)
1132         /**
1133             The function unlink all items from the set.
1134             The function is not atomic. After call the split-list can be non-empty.
1135
1136             For each item the \p disposer is called after unlinking.
1137         */
1138         void clear()
1139         {
1140             iterator it = begin();
1141             while ( it != end()) {
1142                 iterator i(it);
1143                 ++i;
1144                 unlink( *it );
1145                 it = i;
1146             }
1147         }
1148
1149         /// Returns internal statistics
1150         stat const& statistics() const
1151         {
1152             return m_Stat;
1153         }
1154
1155         /// Returns internal statistics for \p OrderedList
1156         typename OrderedList::stat const& list_statistics() const
1157         {
1158             return m_List.statistics();
1159         }
1160
1161     protected:
1162         //@cond
1163         aux_node_type * alloc_aux_node( size_t nHash )
1164         {
1165             m_Stat.onHeadNodeAllocated();
1166             aux_node_type* p = m_Buckets.alloc_aux_node();
1167             if ( p ) {
1168                 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
1169                 // p->m_nHash is read-only data member
1170                 p->m_nHash = nHash;
1171                 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
1172 #       ifdef CDS_DEBUG
1173                 cds_assert( !p->m_busy.load( atomics::memory_order_acquire ));
1174                 p->m_busy.store( true, atomics::memory_order_release );
1175 #       endif
1176             }
1177             return p;
1178         }
1179
1180         void free_aux_node( aux_node_type * p )
1181         {
1182 #       ifdef CDS_DEBUG
1183             cds_assert( p->m_busy.load( atomics::memory_order_acquire ));
1184             p->m_busy.store( false, atomics::memory_order_release );
1185 #       endif
1186
1187             m_Buckets.free_aux_node( p );
1188             m_Stat.onHeadNodeFreed();
1189         }
1190
1191         /// Calculates hash value of \p key
1192         template <typename Q>
1193         size_t hash_value( Q const& key ) const
1194         {
1195             return m_HashFunctor( key );
1196         }
1197
1198         size_t bucket_no( size_t nHash ) const
1199         {
1200             return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
1201         }
1202
1203         static size_t parent_bucket( size_t nBucket )
1204         {
1205             assert( nBucket > 0 );
1206             return nBucket & ~(1 << bitop::MSBnz( nBucket ));
1207         }
1208
1209         aux_node_type * init_bucket( size_t const nBucket )
1210         {
1211             assert( nBucket > 0 );
1212             size_t nParent = parent_bucket( nBucket );
1213
1214             aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
1215             if ( pParentBucket == nullptr ) {
1216                 pParentBucket = init_bucket( nParent );
1217                 m_Stat.onRecursiveInitBucket();
1218             }
1219
1220             assert( pParentBucket != nullptr );
1221
1222             // Allocate an aux node for new bucket
1223             aux_node_type * pBucket = m_Buckets.bucket( nBucket );
1224
1225             back_off bkoff;
1226             for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
1227                 if ( pBucket )
1228                     return pBucket;
1229
1230                 pBucket = alloc_aux_node( split_list::dummy_hash<bit_reversal>( nBucket ));
1231                 if ( pBucket ) {
1232                     if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
1233                         m_Buckets.bucket( nBucket, pBucket );
1234                         m_Stat.onNewBucket();
1235                         return pBucket;
1236                     }
1237
1238                     // Another thread set the bucket. Wait while it done
1239                     free_aux_node( pBucket );
1240                     m_Stat.onBucketInitContenton();
1241                     break;
1242                 }
1243
1244                 // There are no free buckets. It means that the bucket table is full
1245                 // Wait while another thread set the bucket or a free bucket will be available
1246                 m_Stat.onBucketsExhausted();
1247                 bkoff();
1248             }
1249
1250             // Another thread set the bucket. Wait while it done
1251             for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
1252                 bkoff();
1253                 m_Stat.onBusyWaitBucketInit();
1254             }
1255
1256             return pBucket;
1257         }
1258
1259         aux_node_type * get_bucket( size_t nHash )
1260         {
1261             size_t nBucket = bucket_no( nHash );
1262
1263             aux_node_type * pHead = m_Buckets.bucket( nBucket );
1264             if ( pHead == nullptr )
1265                 pHead = init_bucket( nBucket );
1266
1267             assert( pHead->is_dummy());
1268
1269             return pHead;
1270         }
1271
1272         void init()
1273         {
1274             // GC and OrderedList::gc must be the same
1275             static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
1276
1277             // atomicity::empty_item_counter is not allowed as a item counter
1278             static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
1279                 "cds::atomicity::empty_item_counter is not allowed as a item counter");
1280
1281             // Initialize bucket 0
1282             aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash<bit_reversal>(0)*/ );
1283             assert( pNode != nullptr );
1284
1285             // insert_aux_node cannot return false for empty list
1286             CDS_VERIFY( m_List.insert_aux_node( pNode ));
1287
1288             m_Buckets.bucket( 0, pNode );
1289         }
1290
1291         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
1292         {
1293             return nBucketCount * nLoadFactor;
1294         }
1295
1296         void inc_item_count()
1297         {
1298             size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
1299             if ( ++m_ItemCounter <= nMaxCount )
1300                 return;
1301
1302             size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
1303             const size_t nBucketCount = static_cast<size_t>(1) << sz;
1304             if ( nBucketCount < m_Buckets.capacity()) {
1305                 // we may grow the bucket table
1306                 const size_t nLoadFactor = m_Buckets.load_factor();
1307                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
1308                     return; // someone already have updated m_nBucketCountLog2, so stop here
1309
1310                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
1311                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1312                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1313             }
1314             else
1315                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1316         }
1317
1318         template <typename Q, typename Compare, typename Func>
1319         bool find_( Q& val, Compare cmp, Func f )
1320         {
1321             size_t nHash = hash_value( val );
1322             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1323             aux_node_type * pHead = get_bucket( nHash );
1324             assert( pHead != nullptr );
1325
1326             return m_Stat.onFind(
1327                 m_List.find_at( pHead, sv, cmp,
1328                     [&f]( value_type& item, split_list::details::search_value_type<Q>& val ) { f( item, val.val ); } )
1329             );
1330         }
1331
1332         template <typename Q, typename Compare>
1333         bool find_( Q const& val, Compare cmp )
1334         {
1335             size_t nHash = hash_value( val );
1336             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1337             aux_node_type * pHead = get_bucket( nHash );
1338             assert( pHead != nullptr );
1339
1340             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
1341         }
1342
1343         template <typename Q, typename Compare>
1344         iterator find_iterator_( Q const& val, Compare cmp )
1345         {
1346             size_t nHash = hash_value( val );
1347             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1348             aux_node_type * pHead = get_bucket( nHash );
1349             assert( pHead != nullptr );
1350
1351             return iterator( m_List.find_iterator_at( pHead, sv, cmp ), m_List.end());
1352         }
1353
1354         template <typename Q, typename Compare>
1355         guarded_ptr get_( Q const& val, Compare cmp )
1356         {
1357             size_t nHash = hash_value( val );
1358             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1359             aux_node_type * pHead = get_bucket( nHash );
1360             assert( pHead != nullptr );
1361
1362             guarded_ptr gp = m_List.get_at( pHead, sv, cmp );
1363             m_Stat.onFind( !gp.empty());
1364             return gp;
1365         }
1366
1367         template <typename Q>
1368         guarded_ptr get_( Q const& key )
1369         {
1370             return get_( key, key_comparator());
1371         }
1372
1373         template <typename Q, typename Less>
1374         guarded_ptr get_with_( Q const& key, Less )
1375         {
1376             return get_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1377         }
1378
1379         template <typename Q, typename Compare, typename Func>
1380         bool erase_( Q const& val, Compare cmp, Func f )
1381         {
1382             size_t nHash = hash_value( val );
1383             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1384             aux_node_type * pHead = get_bucket( nHash );
1385             assert( pHead != nullptr );
1386
1387             if ( m_List.erase_at( pHead, sv, cmp, f )) {
1388                 --m_ItemCounter;
1389                 m_Stat.onEraseSuccess();
1390                 return true;
1391             }
1392             m_Stat.onEraseFailed();
1393             return false;
1394         }
1395
1396         template <typename Q, typename Compare>
1397         bool erase_( Q const& val, Compare cmp )
1398         {
1399             size_t nHash = hash_value( val );
1400             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1401             aux_node_type * pHead = get_bucket( nHash );
1402             assert( pHead != nullptr );
1403
1404             if ( m_List.erase_at( pHead, sv, cmp )) {
1405                 --m_ItemCounter;
1406                 m_Stat.onEraseSuccess();
1407                 return true;
1408             }
1409             m_Stat.onEraseFailed();
1410             return false;
1411         }
1412
1413         template <typename Q, typename Compare>
1414         guarded_ptr extract_( Q const& val, Compare cmp )
1415         {
1416             size_t nHash = hash_value( val );
1417             split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
1418             aux_node_type * pHead = get_bucket( nHash );
1419             assert( pHead != nullptr );
1420
1421             guarded_ptr gp = m_List.extract_at( pHead, sv, cmp );
1422             if ( gp ) {
1423                 --m_ItemCounter;
1424                 m_Stat.onExtractSuccess();
1425             }
1426             else
1427                 m_Stat.onExtractFailed();
1428             return gp;
1429         }
1430
1431         template <typename Q>
1432         guarded_ptr extract_( Q const& key )
1433         {
1434             return extract_( key, key_comparator());
1435         }
1436
1437         template <typename Q, typename Less>
1438         guarded_ptr extract_with_( Q const& key, Less )
1439         {
1440             return extract_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1441         }
1442         //@endcond
1443
1444     protected:
1445         //@cond
1446         static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
1447
1448         typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
1449         padded_bucket_table     m_Buckets;          ///< bucket table
1450
1451         typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
1452         padded_ordered_list     m_List;             ///< Ordered list containing split-list items
1453
1454         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1455         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
1456         hash                    m_HashFunctor;      ///< Hash functor
1457         item_counter            m_ItemCounter;      ///< Item counter
1458         stat                    m_Stat;             ///< Internal statistics
1459         //@endcond
1460     };
1461
1462 }}  // namespace cds::intrusive
1463
1464 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H