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::item_counter      item_counter; ///< Item counter type
 277         typedef typename traits::back_off          back_off;     ///< back-off strategy for spinning
 278         typedef typename traits::memory_model      memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
 279         typedef typename traits::stat              stat;         ///< Internal statistics, see \p spit_list::stat
 280         typedef typename ordered_list::guarded_ptr guarded_ptr;  ///< Guarded pointer
 281
 282         /// Count of hazard pointer required
 283         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount + 4; // +4 - for iterators
 284
 285     protected:
 286         //@cond
 287         typedef split_list::node<typename ordered_list_adapter::ordered_list_node_type> node_type; ///< split-list node type
 288         typedef typename ordered_list_adapter::node_traits node_traits;
 289
 290         /// Bucket table implementation
 291         typedef typename split_list::details::bucket_table_selector<
 292             traits::dynamic_bucket_table
 293             , gc
 294             , typename ordered_list_adapter::aux_node
 295             , opt::allocator< typename traits::allocator >
 296             , opt::memory_model< memory_model >
 297             , opt::free_list< typename traits::free_list >
 298         >::type bucket_table;
 299
 300         typedef typename bucket_table::aux_node_type aux_node_type;   ///< auxiliary node type
 301         //@endcond
 302
 303     protected:
 304         //@cond
 305         /// Ordered list wrapper to access protected members
 306         class ordered_list_wrapper: public ordered_list
 307         {
 308             typedef ordered_list base_class;
 309             typedef typename base_class::auxiliary_head bucket_head_type;
 310
 311         public:
 312             bool insert_at( aux_node_type* pHead, value_type& val )
 313             {
 314                 assert( pHead != nullptr );
 315                 bucket_head_type h(pHead);
 316                 return base_class::insert_at( h, val );
 317             }
 318
 319             template <typename Func>
 320             bool insert_at( aux_node_type * pHead, value_type& val, Func f )
 321             {
 322                 assert( pHead != nullptr );
 323                 bucket_head_type h(pHead);
 324                 return base_class::insert_at( h, val, f );
 325             }
 326
 327             template <typename Func>
 328             std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 329             {
 330                 assert( pHead != nullptr );
 331                 bucket_head_type h(pHead);
 332                 return base_class::update_at( h, val, func, bAllowInsert );
 333             }
 334
 335             template <typename Q>
 336             typename std::enable_if<
 337                 std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
 338                 std::pair<bool, bool>
 339             >::type
 340             upsert_at( aux_node_type * pHead, Q& val, bool bAllowInsert )
 341             {
 342                 assert( pHead != nullptr );
 343                 bucket_head_type h( pHead );
 344                 return base_class::upsert_at( h, val, bAllowInsert );
 345             }
 346
 347             bool unlink_at( aux_node_type * pHead, value_type& val )
 348             {
 349                 assert( pHead != nullptr );
 350                 bucket_head_type h(pHead);
 351                 return base_class::unlink_at( h, val );
 352             }
 353
 354             template <typename Iterator>
 355             typename std::enable_if<
 356                 std::is_same< Iterator, typename ordered_list::iterator>::value && is_iterable_list< ordered_list >::value,
 357                 bool
 358             >::type
 359             erase_at( Iterator iter )
 360             {
 361                 return base_class::erase_at( iter );
 362             }
 363
 364             template <typename Q, typename Compare, typename Func>
 365             bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
 366             {
 367                 assert( pHead != nullptr );
 368                 bucket_head_type h(pHead);
 369                 return base_class::erase_at( h, val, cmp, f );
 370             }
 371
 372             template <typename Q, typename Compare>
 373             bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 374             {
 375                 assert( pHead != nullptr );
 376                 bucket_head_type h(pHead);
 377                 return base_class::erase_at( h, val, cmp );
 378             }
 379
 380             template <typename Q, typename Compare>
 381             guarded_ptr extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 382             {
 383                 assert( pHead != nullptr );
 384                 bucket_head_type h(pHead);
 385                 return base_class::extract_at( h, val, cmp );
 386             }
 387
 388             template <typename Q, typename Compare, typename Func>
 389             bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
 390             {
 391                 assert( pHead != nullptr );
 392                 bucket_head_type h(pHead);
 393                 return base_class::find_at( h, val, cmp, f );
 394             }
 395
 396             template <typename Q, typename Compare>
 397             bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 398             {
 399                 assert( pHead != nullptr );
 400                 bucket_head_type h(pHead);
 401                 return base_class::find_at( h, val, cmp );
 402             }
 403
 404             template <typename Q, typename Compare>
 405             typename std::enable_if<
 406                 std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value,
 407                 typename base_class::iterator
 408             >::type
 409             find_iterator_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 410             {
 411                 assert( pHead != nullptr );
 412                 bucket_head_type h( pHead );
 413                 return base_class::find_iterator_at( h, val, cmp );
 414             }
 415
 416             template <typename Q, typename Compare>
 417             guarded_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 418             {
 419                 assert( pHead != nullptr );
 420                 bucket_head_type h(pHead);
 421                 return base_class::get_at( h, val, cmp );
 422             }
 423
 424             bool insert_aux_node( aux_node_type * pNode )
 425             {
 426                 return base_class::insert_aux_node( pNode );
 427             }
 428             bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
 429             {
 430                 bucket_head_type h(pHead);
 431                 return base_class::insert_aux_node( h, pNode );
 432             }
 433
 434             template <typename Predicate>
 435             void destroy( Predicate pred )
 436             {
 437                 base_class::destroy( pred );
 438             }
 439         };
 440         //@endcond
 441
 442     protected:
 443         //@cond
 444         template <bool IsConst>
 445         class iterator_type
 446             : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 447         {
 448             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 449             typedef typename iterator_base_class::list_iterator list_iterator;
 450
 451             friend class SplitListSet;
 452
 453         public:
 454             iterator_type()
 455                 : iterator_base_class()
 456             {}
 457
 458             iterator_type( iterator_type const& src )
 459                 : iterator_base_class( src )
 460             {}
 461
 462             // This ctor should be protected...
 463             iterator_type( list_iterator itCur, list_iterator itEnd )
 464                 : iterator_base_class( itCur, itEnd )
 465             {}
 466         };
 467         //@endcond
 468
 469     public:
 470     ///@name Forward iterators
 471     //@{
 472         /// Forward iterator
 473         /**
 474             The forward iterator is based on \p OrderedList forward iterator and has some features:
 475             - it has no post-increment operator
 476             - it iterates items in unordered fashion
 477             - iterator cannot be moved across thread boundary because it may contain GC's guard that is thread-private GC data.
 478
 479             Iterator thread safety depends on type of \p OrderedList:
 480             - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to
 481               because that item is guarded by hazard pointer.
 482               However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set.
 483               Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
 484               Use this iterator on the concurrent container for debugging purpose only.
 485             - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
 486         */
 487         typedef iterator_type<false>    iterator;
 488
 489         /// Const forward iterator
 490         /**
 491             For iterator's features and requirements see \ref iterator
 492         */
 493         typedef iterator_type<true>     const_iterator;
 494
 495         /// Returns a forward iterator addressing the first element in a split-list
 496         /**
 497             For empty list \code begin() == end() \endcode
 498         */
 499         iterator begin()
 500         {
 501             return iterator( m_List.begin(), m_List.end());
 502         }
 503
 504         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 505         /**
 506             Do not use the value returned by <tt>end</tt> function to access any item.
 507
 508             The returned value can be used only to control reaching the end of the split-list.
 509             For empty list \code begin() == end() \endcode
 510         */
 511         iterator end()
 512         {
 513             return iterator( m_List.end(), m_List.end());
 514         }
 515
 516         /// Returns a forward const iterator addressing the first element in a split-list
 517         const_iterator begin() const
 518         {
 519             return cbegin();
 520         }
 521         /// Returns a forward const iterator addressing the first element in a split-list
 522         const_iterator cbegin() const
 523         {
 524             return const_iterator( m_List.cbegin(), m_List.cend());
 525         }
 526
 527         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 528         const_iterator end() const
 529         {
 530             return cend();
 531         }
 532         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 533         const_iterator cend() const
 534         {
 535             return const_iterator( m_List.cend(), m_List.cend());
 536         }
 537     //@}
 538
 539     public:
 540         /// Initialize split-ordered list of default capacity
 541         /**
 542             The default capacity is defined in bucket table constructor.
 543             See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
 544             which selects by \p split_list::dynamic_bucket_table option.
 545         */
 546         SplitListSet()
 547             : m_nBucketCountLog2(1)
 548             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
 549         {
 550             init();
 551         }
 552
 553         /// Initialize split-ordered list
 554         SplitListSet(
 555             size_t nItemCount           ///< estimate average of item count
 556             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
 557             )
 558             : m_Buckets( nItemCount, nLoadFactor )
 559             , m_nBucketCountLog2(1)
 560             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
 561         {
 562             init();
 563         }
 564
 565         /// Destroys split-list set
 566         ~SplitListSet()
 567         {
 568             // list contains aux node that cannot be retired
 569             // all aux nodes will be destroyed by bucket table dtor
 570             m_List.destroy(
 571                 []( node_type * pNode ) -> bool {
 572                     return !pNode->is_dummy();
 573                 }
 574             );
 575             gc::force_dispose();
 576         }
 577
 578     public:
 579         /// Inserts new node
 580         /**
 581             The function inserts \p val in the set if it does not contain
 582             an item with key equal to \p val.
 583
 584             Returns \p true if \p val is placed into the set, \p false otherwise.
 585         */
 586         bool insert( value_type& val )
 587         {
 588             size_t nHash = hash_value( val );
 589             aux_node_type * pHead = get_bucket( nHash );
 590             assert( pHead != nullptr );
 591
 592             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 593
 594             if ( m_List.insert_at( pHead, val )) {
 595                 inc_item_count();
 596                 m_Stat.onInsertSuccess();
 597                 return true;
 598             }
 599             m_Stat.onInsertFailed();
 600             return false;
 601         }
 602
 603         /// Inserts new node
 604         /**
 605             This function is intended for derived non-intrusive containers.
 606
 607             The function allows to split creating of new item into two part:
 608             - create item with key only
 609             - insert new item into the set
 610             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 611
 612             The functor signature is:
 613             \code
 614                 void func( value_type& val );
 615             \endcode
 616             where \p val is the item inserted.
 617             The user-defined functor is called only if the inserting is success.
 618
 619             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 620             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 621             synchronization.
 622         */
 623         template <typename Func>
 624         bool insert( value_type& val, Func f )
 625         {
 626             size_t nHash = hash_value( val );
 627             aux_node_type * pHead = get_bucket( nHash );
 628             assert( pHead != nullptr );
 629
 630             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 631
 632             if ( m_List.insert_at( pHead, val, f )) {
 633                 inc_item_count();
 634                 m_Stat.onInsertSuccess();
 635                 return true;
 636             }
 637             m_Stat.onInsertFailed();
 638             return false;
 639         }
 640
 641         /// Updates the node
 642         /**
 643             The operation performs inserting or changing data with lock-free manner.
 644
 645             If the item \p val is not found in the set, then \p val is inserted
 646             iff \p bAllowInsert is \p true.
 647             Otherwise, the functor \p func is called with item found.
 648
 649             The functor signature depends of the type of \p OrderedList:
 650
 651             <b>for \p MichaelList, \p LazyList</b>
 652                 \code
 653                     struct functor {
 654                         void operator()( bool bNew, value_type& item, value_type& val );
 655                     };
 656                 \endcode
 657                 with arguments:
 658                 - \p bNew - \p true if the item has been inserted, \p false otherwise
 659                 - \p item - item of the set
 660                 - \p val - argument \p val passed into the \p %update() function
 661                 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 662                 refers to the same thing.
 663
 664                 The functor may change non-key fields of the \p item.
 665                 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 666                 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 667                 synchronization.
 668
 669             <b>for \p IterableList</b>
 670                 \code
 671                 void func( value_type& val, value_type * old );
 672                 \endcode
 673                 where
 674                 - \p val - argument \p val passed into the \p %update() function
 675                 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
 676
 677             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 678             \p second is \p true if new item has been added or \p false if the item with \p val
 679             already is in the list.
 680         */
 681         template <typename Func>
 682         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 683         {
 684             size_t nHash = hash_value( val );
 685             aux_node_type * pHead = get_bucket( nHash );
 686             assert( pHead != nullptr );
 687
 688             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 689
 690             std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
 691             if ( bRet.first && bRet.second ) {
 692                 inc_item_count();
 693                 m_Stat.onUpdateNew();
 694             }
 695             else
 696                 m_Stat.onUpdateExist();
 697             return bRet;
 698         }
 699         //@cond
 700         template <typename Func>
 701         CDS_DEPRECATED("ensure() is deprecated, use update()")
 702         std::pair<bool, bool> ensure( value_type& val, Func func )
 703         {
 704             return update( val, func, true );
 705         }
 706         //@endcond
 707
 708         /// Inserts or updates the node (only for \p IterableList)
 709         /**
 710             The operation performs inserting or changing data with lock-free manner.
 711
 712             If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
 713             Otherwise, the current element is changed to \p val, the old element will be retired later
 714             by call \p Traits::disposer.
 715
 716             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 717             \p second is \p true if \p val has been added or \p false if the item with that key
 718             already in the set.
 719         */
 720 #ifdef CDS_DOXYGEN_INVOKED
 721         std::pair<bool, bool> upsert( value_type& val, bool bAllowInsert = true )
 722 #else
 723         template <typename Q>
 724         typename std::enable_if<
 725             std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
 726             std::pair<bool, bool>
 727         >::type
 728         upsert( Q& val, bool bAllowInsert = true )
 729 #endif
 730         {
 731             size_t nHash = hash_value( val );
 732             aux_node_type * pHead = get_bucket( nHash );
 733             assert( pHead != nullptr );
 734
 735             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 736
 737             std::pair<bool, bool> bRet = m_List.upsert_at( pHead, val, bAllowInsert );
 738             if ( bRet.first && bRet.second ) {
 739                 inc_item_count();
 740                 m_Stat.onUpdateNew();
 741             }
 742             else
 743                 m_Stat.onUpdateExist();
 744             return bRet;
 745         }
 746
 747         /// Unlinks the item \p val from the set
 748         /**
 749             The function searches the item \p val in the set and unlinks it from the set
 750             if it is found and is equal to \p val.
 751
 752             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 753             and deletes the item found. \p unlink finds an item by key and deletes it
 754             only if \p val is an item of that set, i.e. the pointer to item found
 755             is equal to <tt> &val </tt>.
 756
 757             The function returns \p true if success and \p false otherwise.
 758         */
 759         bool unlink( value_type& val )
 760         {
 761             size_t nHash = hash_value( val );
 762             aux_node_type * pHead = get_bucket( nHash );
 763             assert( pHead != nullptr );
 764
 765             if ( m_List.unlink_at( pHead, val )) {
 766                 --m_ItemCounter;
 767                 m_Stat.onEraseSuccess();
 768                 return true;
 769             }
 770             m_Stat.onEraseFailed();
 771             return false;
 772         }
 773
 774         /// Deletes the item from the set
 775         /** \anchor cds_intrusive_SplitListSet_hp_erase
 776             The function searches an item with key equal to \p key in the set,
 777             unlinks it from the set, and returns \p true.
 778             If the item with key equal to \p key is not found the function return \p false.
 779
 780             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 781             and deletes the item found. \p unlink finds an item by key and deletes it
 782             only if \p key is an item of that set, i.e. the pointer to item found
 783             is equal to <tt> &key </tt>.
 784
 785             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 786         */
 787         template <typename Q>
 788         bool erase( Q const& key )
 789         {
 790             return erase_( key, key_comparator());
 791         }
 792
 793         /// Deletes the item from the set with comparing functor \p pred
 794         /**
 795
 796             The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
 797             but \p pred predicate is used for key comparing.
 798             \p Less has the interface like \p std::less.
 799             \p pred must imply the same element order as the comparator used for building the set.
 800         */
 801         template <typename Q, typename Less>
 802         bool erase_with( const Q& key, Less pred )
 803         {
 804             CDS_UNUSED( pred );
 805             return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
 806         }
 807
 808         /// Deletes the item from the set
 809         /** \anchor cds_intrusive_SplitListSet_hp_erase_func
 810             The function searches an item with key equal to \p key in the set,
 811             call \p f functor with item found, unlinks it from the set, and returns \p true.
 812             The \ref disposer specified by \p OrderedList class template parameter is called
 813             by garbage collector \p GC asynchronously.
 814
 815             The \p Func interface is
 816             \code
 817             struct functor {
 818                 void operator()( value_type const& item );
 819             };
 820             \endcode
 821
 822             If the item with key equal to \p key is not found the function return \p false.
 823
 824             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 825         */
 826         template <typename Q, typename Func>
 827         bool erase( Q const& key, Func f )
 828         {
 829             return erase_( key, key_comparator(), f );
 830         }
 831
 832         /// Deletes the item from the set with comparing functor \p pred
 833         /**
 834             The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
 835             but \p pred predicate is used for key comparing.
 836             \p Less has the interface like \p std::less.
 837             \p pred must imply the same element order as the comparator used for building the set.
 838         */
 839         template <typename Q, typename Less, typename Func>
 840         bool erase_with( Q const& key, Less pred, Func f )
 841         {
 842             CDS_UNUSED( pred );
 843             return erase_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
 844         }
 845
 846         /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set)
 847         /**
 848             Returns \p true if the operation is successful, \p false otherwise.
 849             The function can return \p false if the node the iterator points to has already been deleted
 850             by other thread.
 851
 852             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 853
 854             @note \p %erase_at() is supported only for \p %SplitListSet based on \p IterableList.
 855         */
 856 #ifdef CDS_DOXYGEN_INVOKED
 857         bool erase_at( iterator const& iter )
 858 #else
 859         template <typename Iterator>
 860         typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
 861         erase_at( Iterator const& iter )
 862 #endif
 863         {
 864             assert( iter != end() );
 865
 866             if ( m_List.erase_at( iter.underlying_iterator())) {
 867                 --m_ItemCounter;
 868                 m_Stat.onEraseSuccess();
 869                 return true;
 870             }
 871             return false;
 872         }
 873
 874         /// Extracts the item with specified \p key
 875         /** \anchor cds_intrusive_SplitListSet_hp_extract
 876             The function searches an item with key equal to \p key,
 877             unlinks it from the set, and returns it as \p guarded_ptr.
 878             If \p key is not found the function returns an empty guarded pointer.
 879
 880             Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
 881
 882             The \p disposer specified in \p OrderedList class' template parameter is called automatically
 883             by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
 884             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 885
 886             Usage:
 887             \code
 888             typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
 889             splitlist_set theSet;
 890             // ...
 891             {
 892                 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
 893                 if ( gp) {
 894                     // Deal with gp
 895                     // ...
 896                 }
 897                 // Destructor of gp releases internal HP guard
 898             }
 899             \endcode
 900         */
 901         template <typename Q>
 902         guarded_ptr extract( Q const& key )
 903         {
 904             return extract_( key );
 905         }
 906
 907         /// Extracts the item using compare functor \p pred
 908         /**
 909             The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
 910             but \p pred predicate is used for key comparing.
 911
 912             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 913             in any order.
 914             \p pred must imply the same element order as the comparator used for building the set.
 915         */
 916         template <typename Q, typename Less>
 917         guarded_ptr extract_with( Q const& key, Less pred )
 918         {
 919             return extract_with_( key, pred );
 920         }
 921
 922         /// Finds the key \p key
 923         /** \anchor cds_intrusive_SplitListSet_hp_find_func
 924             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 925             The interface of \p Func functor is:
 926             \code
 927             struct functor {
 928                 void operator()( value_type& item, Q& key );
 929             };
 930             \endcode
 931             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 932
 933             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 934             that \p item cannot be disposed during functor is executing.
 935             The functor does not serialize simultaneous access to the set \p item. If such access is
 936             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 937
 938             Note the hash functor specified for class \p Traits template parameter
 939             should accept a parameter of type \p Q that can be not the same as \p value_type.
 940
 941             The function returns \p true if \p key is found, \p false otherwise.
 942         */
 943         template <typename Q, typename Func>
 944         bool find( Q& key, Func f )
 945         {
 946             return find_( key, key_comparator(), f );
 947         }
 948         //@cond
 949         template <typename Q, typename Func>
 950         bool find( Q const& key, Func f )
 951         {
 952             return find_( key, key_comparator(), f );
 953         }
 954         //@endcond
 955
 956         /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
 957         /**
 958             If \p key is not found the function returns \p end().
 959
 960             @note This function is supported only for the set based on \p IterableList
 961         */
 962         template <typename Q>
 963 #ifdef CDS_DOXYGEN_INVOKED
 964         iterator
 965 #else
 966         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
 967 #endif
 968         find( Q& key )
 969         {
 970             return find_iterator_( key, key_comparator());
 971         }
 972         //@cond
 973         template <typename Q>
 974         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
 975         find( Q const& key )
 976         {
 977             return find_iterator_( key, key_comparator());
 978         }
 979         //@endcond
 980
 981
 982         /// Finds the key \p key with \p pred predicate for comparing
 983         /**
 984             The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
 985             but \p cmp is used for key compare.
 986             \p Less has the interface like \p std::less.
 987             \p cmp must imply the same element order as the comparator used for building the set.
 988         */
 989         template <typename Q, typename Less, typename Func>
 990         bool find_with( Q& key, Less pred, Func f )
 991         {
 992             CDS_UNUSED( pred );
 993             return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
 994         }
 995         //@cond
 996         template <typename Q, typename Less, typename Func>
 997         bool find_with( Q const& key, Less pred, Func f )
 998         {
 999             CDS_UNUSED( pred );
1000             return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
1001         }
1002         //@endcond
1003
1004         /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
1005         /**
1006             The function is an analog of \p find(Q&) but \p pred is used for key comparing.
1007             \p Less functor has the interface like \p std::less.
1008             \p pred must imply the same element order as the comparator used for building the set.
1009
1010             If \p key is not found the function returns \p end().
1011
1012             @note This function is supported only for the set based on \p IterableList
1013         */
1014         template <typename Q, typename Less>
1015 #ifdef CDS_DOXYGEN_INVOKED
1016         iterator
1017 #else
1018         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
1019 #endif
1020         find_with( Q& key, Less pred )
1021         {
1022             CDS_UNUSED( pred );
1023             return find_iterator_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1024         }
1025         //@cond
1026         template <typename Q, typename Less>
1027         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
1028         find_with( Q const& key, Less pred )
1029         {
1030             CDS_UNUSED( pred );
1031             return find_iterator_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1032         }
1033         //@endcond
1034
1035
1036         /// Checks whether the set contains \p key
1037         /**
1038             The function searches the item with key equal to \p key
1039             and returns \p true if it is found, and \p false otherwise.
1040
1041             Note the hash functor specified for class \p Traits template parameter
1042             should accept a parameter of type \p Q that can be not the same as \p value_type.
1043             Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
1044         */
1045         template <typename Q>
1046         bool contains( Q const& key )
1047         {
1048             return find_( key, key_comparator());
1049         }
1050
1051         /// Checks whether the set contains \p key using \p pred predicate for searching
1052         /**
1053             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
1054             \p Less functor has the interface like \p std::less.
1055             \p Less must imply the same element order as the comparator used for building the set.
1056         */
1057         template <typename Q, typename Less>
1058         bool contains( Q const& key, Less pred )
1059         {
1060             CDS_UNUSED( pred );
1061             return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1062         }
1063
1064         /// Finds the key \p key and return the item found
1065         /** \anchor cds_intrusive_SplitListSet_hp_get
1066             The function searches the item with key equal to \p key
1067             and returns the item found as \p guarded_ptr.
1068             If \p key is not found the function returns an empty guarded pointer.
1069
1070             The \p disposer specified in \p OrderedList class' template parameter is called
1071             by garbage collector \p GC automatically when returned \p guarded_ptr object
1072             will be destroyed or released.
1073             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1074
1075             Usage:
1076             \code
1077             typedef cds::intrusive::SplitListSet< your_template_params >  splitlist_set;
1078             splitlist_set theSet;
1079             // ...
1080             {
1081                 splitlist_set::guarded_ptr gp = theSet.get( 5 );
1082                 if ( gp ) {
1083                     // Deal with gp
1084                     //...
1085                 }
1086                 // Destructor of guarded_ptr releases internal HP guard
1087             }
1088             \endcode
1089
1090             Note the compare functor specified for \p OrderedList template parameter
1091             should accept a parameter of type \p Q that can be not the same as \p value_type.
1092         */
1093         template <typename Q>
1094         guarded_ptr get( Q const& key )
1095         {
1096             return get_( key );
1097         }
1098
1099         /// Finds the key \p key and return the item found
1100         /**
1101             The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
1102             but \p pred is used for comparing the keys.
1103
1104             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1105             in any order.
1106             \p pred must imply the same element order as the comparator used for building the set.
1107         */
1108         template <typename Q, typename Less>
1109         guarded_ptr get_with( Q const& key, Less pred )
1110         {
1111             return get_with_( key, pred );
1112         }
1113
1114         /// Returns item count in the set
1115         size_t size() const
1116         {
1117             return m_ItemCounter;
1118         }
1119
1120         /// Checks if the set is empty
1121         /**
1122             Emptiness is checked by item counting: if item count is zero then the set is empty.
1123             Thus, the correct item counting feature is an important part of split-list set implementation.
1124         */
1125         bool empty() const
1126         {
1127             return size() == 0;
1128         }
1129
1130         /// Clears the set (non-atomic)
1131         /**
1132             The function unlink all items from the set.
1133             The function is not atomic. After call the split-list can be non-empty.
1134
1135             For each item the \p disposer is called after unlinking.
1136         */
1137         void clear()
1138         {
1139             iterator it = begin();
1140             while ( it != end()) {
1141                 iterator i(it);
1142                 ++i;
1143                 unlink( *it );
1144                 it = i;
1145             }
1146         }
1147
1148         /// Returns internal statistics
1149         stat const& statistics() const
1150         {
1151             return m_Stat;
1152         }
1153
1154         /// Returns internal statistics for \p OrderedList
1155         typename OrderedList::stat const& list_statistics() const
1156         {
1157             return m_List.statistics();
1158         }
1159
1160     protected:
1161         //@cond
1162         aux_node_type * alloc_aux_node( size_t nHash )
1163         {
1164             m_Stat.onHeadNodeAllocated();
1165             aux_node_type* p = m_Buckets.alloc_aux_node();
1166             if ( p )
1167                 p->m_nHash = nHash;
1168             return p;
1169         }
1170
1171         void free_aux_node( aux_node_type * p )
1172         {
1173             m_Buckets.free_aux_node( p );
1174             m_Stat.onHeadNodeFreed();
1175         }
1176
1177         /// Calculates hash value of \p key
1178         template <typename Q>
1179         size_t hash_value( Q const& key ) const
1180         {
1181             return m_HashFunctor( key );
1182         }
1183
1184         size_t bucket_no( size_t nHash ) const
1185         {
1186             return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
1187         }
1188
1189         static size_t parent_bucket( size_t nBucket )
1190         {
1191             assert( nBucket > 0 );
1192             return nBucket & ~(1 << bitop::MSBnz( nBucket ));
1193         }
1194
1195         aux_node_type * init_bucket( size_t const nBucket )
1196         {
1197             assert( nBucket > 0 );
1198             size_t nParent = parent_bucket( nBucket );
1199
1200             aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
1201             if ( pParentBucket == nullptr ) {
1202                 pParentBucket = init_bucket( nParent );
1203                 m_Stat.onRecursiveInitBucket();
1204             }
1205
1206             assert( pParentBucket != nullptr );
1207
1208             // Allocate an aux node for new bucket
1209             aux_node_type * pBucket = m_Buckets.bucket( nBucket );
1210
1211             back_off bkoff;
1212             for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
1213                 if ( pBucket )
1214                     return pBucket;
1215
1216                 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ));
1217                 if ( pBucket ) {
1218                     if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
1219                         m_Buckets.bucket( nBucket, pBucket );
1220                         m_Stat.onNewBucket();
1221                         return pBucket;
1222                     }
1223
1224                     // Another thread set the bucket. Wait while it done
1225                     free_aux_node( pBucket );
1226                     m_Stat.onBucketInitContenton();
1227                     break;
1228                 }
1229
1230                 // There are no free buckets. It means that the bucket table is full
1231                 // Wait while another thread set the bucket or a free bucket will be available
1232                 m_Stat.onBucketsExhausted();
1233                 bkoff();
1234             }
1235
1236             // Another thread set the bucket. Wait while it done
1237             for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
1238                 bkoff();
1239                 m_Stat.onBusyWaitBucketInit();
1240             }
1241
1242             return pBucket;
1243         }
1244
1245         aux_node_type * get_bucket( size_t nHash )
1246         {
1247             size_t nBucket = bucket_no( nHash );
1248
1249             aux_node_type * pHead = m_Buckets.bucket( nBucket );
1250             if ( pHead == nullptr )
1251                 pHead = init_bucket( nBucket );
1252
1253             assert( pHead->is_dummy());
1254
1255             return pHead;
1256         }
1257
1258         void init()
1259         {
1260             // GC and OrderedList::gc must be the same
1261             static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
1262
1263             // atomicity::empty_item_counter is not allowed as a item counter
1264             static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
1265                 "cds::atomicity::empty_item_counter is not allowed as a item counter");
1266
1267             // Initialize bucket 0
1268             aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
1269             assert( pNode != nullptr );
1270
1271             // insert_aux_node cannot return false for empty list
1272             CDS_VERIFY( m_List.insert_aux_node( pNode ));
1273
1274             m_Buckets.bucket( 0, pNode );
1275         }
1276
1277         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
1278         {
1279             return nBucketCount * nLoadFactor;
1280         }
1281
1282         void inc_item_count()
1283         {
1284             size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
1285             if ( ++m_ItemCounter <= nMaxCount )
1286                 return;
1287
1288             size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
1289             const size_t nBucketCount = static_cast<size_t>(1) << sz;
1290             if ( nBucketCount < m_Buckets.capacity()) {
1291                 // we may grow the bucket table
1292                 const size_t nLoadFactor = m_Buckets.load_factor();
1293                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
1294                     return; // someone already have updated m_nBucketCountLog2, so stop here
1295
1296                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
1297                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1298                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1299             }
1300             else
1301                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1302         }
1303
1304         template <typename Q, typename Compare, typename Func>
1305         bool find_( Q& val, Compare cmp, Func f )
1306         {
1307             size_t nHash = hash_value( val );
1308             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
1309             aux_node_type * pHead = get_bucket( nHash );
1310             assert( pHead != nullptr );
1311
1312             return m_Stat.onFind(
1313                 m_List.find_at( pHead, sv, cmp,
1314                     [&f]( value_type& item, split_list::details::search_value_type<Q>& val ) { f( item, val.val ); } )
1315             );
1316         }
1317
1318         template <typename Q, typename Compare>
1319         bool find_( Q const& val, Compare cmp )
1320         {
1321             size_t nHash = hash_value( val );
1322             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1323             aux_node_type * pHead = get_bucket( nHash );
1324             assert( pHead != nullptr );
1325
1326             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
1327         }
1328
1329         template <typename Q, typename Compare>
1330         iterator find_iterator_( Q const& val, Compare cmp )
1331         {
1332             size_t nHash = hash_value( val );
1333             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1334             aux_node_type * pHead = get_bucket( nHash );
1335             assert( pHead != nullptr );
1336
1337             return iterator( m_List.find_iterator_at( pHead, sv, cmp ), m_List.end());
1338         }
1339
1340         template <typename Q, typename Compare>
1341         guarded_ptr get_( Q const& val, Compare cmp )
1342         {
1343             size_t nHash = hash_value( val );
1344             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1345             aux_node_type * pHead = get_bucket( nHash );
1346             assert( pHead != nullptr );
1347
1348             guarded_ptr gp = m_List.get_at( pHead, sv, cmp );
1349             m_Stat.onFind( !gp.empty());
1350             return gp;
1351         }
1352
1353         template <typename Q>
1354         guarded_ptr get_( Q const& key )
1355         {
1356             return get_( key, key_comparator());
1357         }
1358
1359         template <typename Q, typename Less>
1360         guarded_ptr get_with_( Q const& key, Less )
1361         {
1362             return get_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1363         }
1364
1365         template <typename Q, typename Compare, typename Func>
1366         bool erase_( Q const& val, Compare cmp, Func f )
1367         {
1368             size_t nHash = hash_value( val );
1369             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1370             aux_node_type * pHead = get_bucket( nHash );
1371             assert( pHead != nullptr );
1372
1373             if ( m_List.erase_at( pHead, sv, cmp, f )) {
1374                 --m_ItemCounter;
1375                 m_Stat.onEraseSuccess();
1376                 return true;
1377             }
1378             m_Stat.onEraseFailed();
1379             return false;
1380         }
1381
1382         template <typename Q, typename Compare>
1383         bool erase_( Q const& val, Compare cmp )
1384         {
1385             size_t nHash = hash_value( val );
1386             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1387             aux_node_type * pHead = get_bucket( nHash );
1388             assert( pHead != nullptr );
1389
1390             if ( m_List.erase_at( pHead, sv, cmp )) {
1391                 --m_ItemCounter;
1392                 m_Stat.onEraseSuccess();
1393                 return true;
1394             }
1395             m_Stat.onEraseFailed();
1396             return false;
1397         }
1398
1399         template <typename Q, typename Compare>
1400         guarded_ptr extract_( Q const& val, Compare cmp )
1401         {
1402             size_t nHash = hash_value( val );
1403             split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
1404             aux_node_type * pHead = get_bucket( nHash );
1405             assert( pHead != nullptr );
1406
1407             guarded_ptr gp = m_List.extract_at( pHead, sv, cmp );
1408             if ( gp ) {
1409                 --m_ItemCounter;
1410                 m_Stat.onExtractSuccess();
1411             }
1412             else
1413                 m_Stat.onExtractFailed();
1414             return gp;
1415         }
1416
1417         template <typename Q>
1418         guarded_ptr extract_( Q const& key )
1419         {
1420             return extract_( key, key_comparator());
1421         }
1422
1423         template <typename Q, typename Less>
1424         guarded_ptr extract_with_( Q const& key, Less )
1425         {
1426             return extract_( key, typename ordered_list_adapter::template make_compare_from_less<Less>());
1427         }
1428         //@endcond
1429
1430     protected:
1431         //@cond
1432         static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
1433
1434         typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
1435         padded_bucket_table     m_Buckets;          ///< bucket table
1436
1437         typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
1438         padded_ordered_list     m_List;             ///< Ordered list containing split-list items
1439
1440         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1441         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
1442         item_counter            m_ItemCounter;      ///< Item counter
1443         hash                    m_HashFunctor;      ///< Hash functor
1444         stat                    m_Stat;             ///< Internal statistics
1445         //@endcond
1446     };
1447
1448 }}  // namespace cds::intrusive
1449
1450 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H