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