cds/intrusive/split_list_nogc.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_NOGC_H
  32 #define CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
  33
  34 #include <limits>
  35
  36 #include <cds/intrusive/details/split_list_base.h>
  37 #include <cds/gc/nogc.h>
  38 #include <cds/details/type_padding.h>
  39
  40 namespace cds { namespace intrusive {
  41
  42     /// Split-ordered list (template specialization for gc::nogc)
  43     /** @ingroup cds_intrusive_map
  44         \anchor cds_intrusive_SplitListSet_nogc
  45
  46         This specialization is intended for so-called persistent usage when no item
  47         reclamation may be performed. The class does not support deleting of list item.
  48
  49         See \ref cds_intrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
  50         The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
  51         \ref cds_intrusive_MichaelList_nogc "persistent MichaelList",
  52         \ref cds_intrusive_LazyList_nogc "persistent LazyList"
  53     */
  54     template <
  55         class OrderedList,
  56 #ifdef CDS_DOXYGEN_INVOKED
  57         class Traits = split_list::traits
  58 #else
  59         class Traits
  60 #endif
  61     >
  62     class SplitListSet< cds::gc::nogc, OrderedList, Traits >
  63     {
  64     public:
  65         typedef cds::gc::nogc gc;     ///< Garbage collector
  66         typedef Traits        traits; ///< Traits template parameters
  67
  68         /// Hash functor for \p value_type and all its derivatives that you use
  69         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type   hash;
  70
  71     protected:
  72         //@cond
  73         typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
  74         //@endcond
  75
  76     public:
  77 #   ifdef CDS_DOXYGEN_INVOKED
  78         typedef OrderedList ordered_list;   ///< type of ordered list used as base for split-list
  79 #   else
  80         typedef typename wrapped_ordered_list::result ordered_list;
  81 #   endif
  82         typedef typename ordered_list::value_type     value_type;     ///< type of value stored in the split-list
  83         typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
  84         typedef typename ordered_list::disposer       disposer;       ///< Node disposer functor
  85
  86         typedef typename traits::item_counter item_counter; ///< Item counter type
  87         typedef typename traits::back_off     back_off;     ///< back-off strategy
  88         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
  89         typedef typename traits::stat         stat;         ///< Internal statistics, see \p spit_list::stat
  90
  91         // GC and OrderedList::gc must be the same
  92         static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
  93
  94         // atomicity::empty_item_counter is not allowed as a item counter
  95         static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
  96             "cds::atomicity::empty_item_counter is not allowed as a item counter");
  97
  98     protected:
  99         //@cond
 100         typedef typename ordered_list::node_type  list_node_type;  ///< Node type as declared in ordered list
 101         typedef split_list::node<list_node_type>  node_type;       ///< split-list node type
 102
 103         /// Split-list node traits
 104         /**
 105             This traits is intended for converting between underlying ordered list node type \ref list_node_type
 106             and split-list node type \ref node_type
 107         */
 108         typedef split_list::node_traits<typename ordered_list::node_traits>  node_traits;
 109
 110         /// Bucket table implementation
 111         typedef typename split_list::details::bucket_table_selector<
 112             traits::dynamic_bucket_table
 113             , gc
 114             , node_type
 115             , opt::allocator< typename traits::allocator >
 116             , opt::memory_model< memory_model >
 117             , opt::free_list< typename traits::free_list >
 118         >::type bucket_table;
 119
 120         typedef typename bucket_table::aux_node_type aux_node_type; ///< dummy node type
 121
 122         typedef typename ordered_list::iterator list_iterator;
 123         typedef typename ordered_list::const_iterator list_const_iterator;
 124         //@endcond
 125
 126     protected:
 127         //@cond
 128         /// Ordered list wrapper to access protected members
 129         class ordered_list_wrapper: public ordered_list
 130         {
 131             typedef ordered_list base_class;
 132             typedef typename base_class::auxiliary_head bucket_head_type;
 133
 134         public:
 135             list_iterator insert_at_( aux_node_type * pHead, value_type& val )
 136             {
 137                 assert( pHead != nullptr );
 138                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 139                 return base_class::insert_at_( h, val );
 140             }
 141
 142             template <typename Func>
 143             std::pair<list_iterator, bool> update_at_( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 144             {
 145                 assert( pHead != nullptr );
 146                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 147                 return base_class::update_at_( h, val, func, bAllowInsert );
 148             }
 149
 150             template <typename Q, typename Compare, typename Func>
 151             bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
 152             {
 153                 assert( pHead != nullptr );
 154                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 155                 return base_class::find_at( h, val, cmp, f );
 156             }
 157
 158             template <typename Q, typename Compare>
 159             list_iterator find_at_( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
 160             {
 161                 assert( pHead != nullptr );
 162                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 163                 return base_class::find_at_( h, val, cmp );
 164             }
 165
 166             bool insert_aux_node( aux_node_type * pNode )
 167             {
 168                 return base_class::insert_aux_node( pNode );
 169             }
 170             bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
 171             {
 172                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 173                 return base_class::insert_aux_node( h, pNode );
 174             }
 175
 176             template <typename Predicate>
 177             void erase_for( Predicate pred )
 178             {
 179                 return base_class::erase_for( pred );
 180             }
 181         };
 182         //@endcond
 183
 184     public:
 185         /// Initialize split-ordered list of default capacity
 186         /**
 187             The default capacity is defined in bucket table constructor.
 188             See split_list::expandable_bucket_table, split_list::static_ducket_table
 189             which selects by split_list::dynamic_bucket_table option.
 190         */
 191         SplitListSet()
 192             : m_nBucketCountLog2(1)
 193             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 194         {
 195             init();
 196         }
 197
 198         /// Initialize split-ordered list
 199         SplitListSet(
 200             size_t nItemCount           ///< estimate average of item count
 201             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
 202             )
 203             : m_Buckets( nItemCount, nLoadFactor )
 204             , m_nBucketCountLog2(1)
 205             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 206         {
 207             init();
 208         }
 209
 210         /// Destroys split-list
 211         ~SplitListSet()
 212         {
 213             m_List.clear();
 214         }
 215     public:
 216         /// Inserts new node
 217         /**
 218             The function inserts \p val in the set if it does not contain
 219             an item with key equal to \p val.
 220
 221             Returns \p true if \p val is placed into the set, \p false otherwise.
 222         */
 223         bool insert( value_type& val )
 224         {
 225             return insert_( val ) != end();
 226         }
 227
 228         /// Updates the node
 229         /**
 230             The operation performs inserting or changing data with lock-free manner.
 231
 232             If the item \p val is not found in the set, then \p val is inserted
 233             iff \p bAllowInsert is \p true.
 234             Otherwise, the functor \p func is called with item found.
 235             The functor signature is:
 236             \code
 237                 void func( bool bNew, value_type& item, value_type& val );
 238             \endcode
 239             with arguments:
 240             - \p bNew - \p true if the item has been inserted, \p false otherwise
 241             - \p item - item of the set
 242             - \p val - argument \p val passed into the \p update() function
 243             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 244             refers to the same thing.
 245
 246             The functor may change non-key fields of the \p item.
 247
 248             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 249             \p second is \p true if new item has been added or \p false if the item with \p key
 250             already is in the list.
 251
 252             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 253             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 254             synchronization.
 255         */
 256         template <typename Func>
 257         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 258         {
 259             std::pair<iterator, bool> ret = update_( val, func, bAllowInsert );
 260             return std::make_pair( ret.first != end(), ret.second );
 261         }
 262         //@cond
 263         template <typename Func>
 264         CDS_DEPRECATED("ensure() is deprecated, use update()")
 265         std::pair<bool, bool> ensure( value_type& val, Func func )
 266         {
 267             return update( val, func, true );
 268         }
 269         //@endcond
 270
 271         /// Checks whether the set contains \p key
 272         /**
 273             The function searches the item with key equal to \p key
 274             and returns \p true if it is found, and \p false otherwise.
 275
 276             Note the hash functor specified for class \p Traits template parameter
 277             should accept a parameter of type \p Q that can be not the same as \p value_type.
 278             Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
 279         */
 280         template <typename Q>
 281         value_type * contains( Q const& key )
 282         {
 283             iterator it = find_( key );
 284             if ( it == end() )
 285                 return nullptr;
 286             return &*it;
 287         }
 288         //@cond
 289         template <typename Q>
 290         CDS_DEPRECATED("deprecated, use contains()")
 291         value_type * find( Q const& key )
 292         {
 293             return contains( key );
 294         }
 295         //@endcond
 296
 297         /// Checks whether the set contains \p key using \p pred predicate for searching
 298         /**
 299             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 300             \p Less functor has the interface like \p std::less.
 301             \p Less must imply the same element order as the comparator used for building the list.
 302         */
 303         template <typename Q, typename Less>
 304         value_type * contains( Q const& key, Less pred )
 305         {
 306             iterator it = find_with_( key, pred );
 307             if ( it == end() )
 308                 return nullptr;
 309             return &*it;
 310         }
 311         //@cond
 312         template <typename Q, typename Less>
 313         CDS_DEPRECATED("deprecated, use contains()")
 314         value_type * find_with( Q const& key, Less pred )
 315         {
 316             return contains( key, pred );
 317         }
 318         //@endcond
 319
 320         /// Finds the key \p key
 321         /** \anchor cds_intrusive_SplitListSet_nogc_find_func
 322             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 323             The interface of \p Func functor is:
 324             \code
 325             struct functor {
 326                 void operator()( value_type& item, Q& key );
 327             };
 328             \endcode
 329             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 330
 331             The functor can change non-key fields of \p item.
 332             The functor does not serialize simultaneous access to the set \p item. If such access is
 333             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 334
 335             Note the hash functor specified for class \p Traits template parameter
 336             should accept a parameter of type \p Q that can be not the same as \p value_type.
 337
 338             The function returns \p true if \p key is found, \p false otherwise.
 339         */
 340         template <typename Q, typename Func>
 341         bool find( Q& key, Func f )
 342         {
 343             return find_( key, key_comparator(), f );
 344         }
 345         //@cond
 346         template <typename Q, typename Func>
 347         bool find( Q const& key, Func f )
 348         {
 349             return find_( key, key_comparator(), f );
 350         }
 351         //@endcond
 352
 353         /// Finds the key \p key with \p pred predicate for comparing
 354         /**
 355             The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
 356             but \p cmp is used for key compare.
 357             \p Less has the interface like \p std::less.
 358             \p cmp must imply the same element order as the comparator used for building the set.
 359         */
 360         template <typename Q, typename Less, typename Func>
 361         bool find_with( Q& key, Less pred, Func f )
 362         {
 363             CDS_UNUSED( pred );
 364             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 365         }
 366         //@cond
 367         template <typename Q, typename Less, typename Func>
 368         bool find_with( Q const& key, Less pred, Func f )
 369         {
 370             CDS_UNUSED( pred );
 371             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 372         }
 373         //@endcond
 374
 375
 376         /// Clears the set (non-atomic, not thread-safe)
 377         /**
 378             The function unlink all items from the set.
 379             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
 380             If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
 381             <tt> empty() </tt> may return \p true but the set may contain item(s).
 382             Therefore, \p %clear() may be used only for debugging purposes.
 383
 384             For each item the \p disposer is called after unlinking.
 385         */
 386         void clear()
 387         {
 388             m_List.erase_for( []( value_type const& val ) -> bool { return !node_traits::to_node_ptr( val )->is_dummy(); } );
 389             m_ItemCounter.reset();
 390         }
 391
 392         /// Checks if the set is empty
 393         /**
 394             Emptiness is checked by item counting: if item count is zero then the set is empty.
 395             Thus, the correct item counting feature is an important part of split-list implementation.
 396         */
 397         bool empty() const
 398         {
 399             return size() == 0;
 400         }
 401
 402         /// Returns item count in the set
 403         size_t size() const
 404         {
 405             return m_ItemCounter;
 406         }
 407
 408         /// Returns internal statistics
 409         stat const& statistics() const
 410         {
 411             return m_Stat;
 412         }
 413
 414     protected:
 415         //@cond
 416         template <bool IsConst>
 417         class iterator_type
 418             : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 419         {
 420             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 421             typedef typename iterator_base_class::list_iterator list_iterator;
 422         public:
 423             iterator_type()
 424                 : iterator_base_class()
 425             {}
 426
 427             iterator_type( iterator_type const& src )
 428                 : iterator_base_class( src )
 429             {}
 430
 431             // This ctor should be protected...
 432             iterator_type( list_iterator itCur, list_iterator itEnd )
 433                 : iterator_base_class( itCur, itEnd )
 434             {}
 435         };
 436         //@endcond
 437
 438     public:
 439     ///@name Forward iterators
 440     //@{
 441         /// Forward iterator
 442         /**
 443             The forward iterator for a split-list has some features:
 444             - it has no post-increment operator
 445             - it depends on iterator of underlying \p OrderedList
 446         */
 447         typedef iterator_type<false>    iterator;
 448
 449         /// Const forward iterator
 450         /**
 451             For iterator's features and requirements see \ref iterator
 452         */
 453         typedef iterator_type<true>     const_iterator;
 454
 455         /// Returns a forward iterator addressing the first element in a split-list
 456         /**
 457             For empty list \code begin() == end() \endcode
 458         */
 459         iterator begin()
 460         {
 461             return iterator( m_List.begin(), m_List.end() );
 462         }
 463
 464         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 465         /**
 466             Do not use the value returned by <tt>end</tt> function to access any item.
 467
 468             The returned value can be used only to control reaching the end of the split-list.
 469             For empty list \code begin() == end() \endcode
 470         */
 471         iterator end()
 472         {
 473             return iterator( m_List.end(), m_List.end() );
 474         }
 475
 476         /// Returns a forward const iterator addressing the first element in a split-list
 477         const_iterator begin() const
 478         {
 479             return const_iterator( m_List.begin(), m_List.end() );
 480         }
 481
 482         /// Returns a forward const iterator addressing the first element in a split-list
 483         const_iterator cbegin() const
 484         {
 485             return const_iterator( m_List.cbegin(), m_List.cend() );
 486         }
 487
 488         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 489         const_iterator end() const
 490         {
 491             return const_iterator( m_List.end(), m_List.end() );
 492         }
 493
 494         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 495         const_iterator cend() const
 496         {
 497             return const_iterator( m_List.cend(), m_List.cend() );
 498         }
 499     //@}
 500
 501     protected:
 502         //@cond
 503         iterator insert_( value_type& val )
 504         {
 505             size_t nHash = hash_value( val );
 506             aux_node_type * pHead = get_bucket( nHash );
 507             assert( pHead != nullptr );
 508
 509             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 510
 511             list_iterator it = m_List.insert_at_( pHead, val );
 512             if ( it != m_List.end() ) {
 513                 inc_item_count();
 514                 m_Stat.onInsertSuccess();
 515                 return iterator( it, m_List.end() );
 516             }
 517             m_Stat.onInsertFailed();
 518             return end();
 519         }
 520
 521         template <typename Func>
 522         std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
 523         {
 524             size_t nHash = hash_value( val );
 525             aux_node_type * pHead = get_bucket( nHash );
 526             assert( pHead != nullptr );
 527
 528             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 529
 530             std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
 531             if ( ret.first != m_List.end() ) {
 532                 if ( ret.second ) {
 533                     inc_item_count();
 534                     m_Stat.onUpdateNew();
 535                 }
 536                 else
 537                     m_Stat.onUpdateExist();
 538                 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
 539             }
 540             return std::make_pair( end(), ret.second );
 541         }
 542
 543         template <typename Q, typename Less >
 544         iterator find_with_( Q& val, Less pred )
 545         {
 546             CDS_UNUSED( pred );
 547             size_t nHash = hash_value( val );
 548             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 549             aux_node_type * pHead = get_bucket( nHash );
 550             assert( pHead != nullptr );
 551
 552             auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 553             m_Stat.onFind( it != m_List.end() );
 554             return iterator( it, m_List.end() );
 555         }
 556
 557         template <typename Q>
 558         iterator find_( Q const& val )
 559         {
 560             size_t nHash = hash_value( val );
 561             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 562             aux_node_type * pHead = get_bucket( nHash );
 563             assert( pHead != nullptr );
 564
 565             auto it = m_List.find_at_( pHead, sv, key_comparator() );
 566             m_Stat.onFind( it != m_List.end() );
 567             return iterator( it, m_List.end() );
 568         }
 569
 570         template <typename Q, typename Compare, typename Func>
 571         bool find_( Q& val, Compare cmp, Func f )
 572         {
 573             size_t nHash = hash_value( val );
 574             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 575             aux_node_type * pHead = get_bucket( nHash );
 576             assert( pHead != nullptr );
 577             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
 578                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
 579         }
 580
 581         aux_node_type * alloc_aux_node( size_t nHash )
 582         {
 583             m_Stat.onHeadNodeAllocated();
 584             aux_node_type* p = m_Buckets.alloc_aux_node();
 585             if ( p )
 586                 p->m_nHash = nHash;
 587             return p;
 588         }
 589
 590         void free_aux_node( aux_node_type * p )
 591         {
 592             m_Buckets.free_aux_node( p );
 593             m_Stat.onHeadNodeFreed();
 594         }
 595
 596         /// Calculates hash value of \p key
 597         template <typename Q>
 598         size_t hash_value( Q const& key ) const
 599         {
 600             return m_HashFunctor( key );
 601         }
 602
 603         size_t bucket_no( size_t nHash ) const
 604         {
 605             return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
 606         }
 607
 608         static size_t parent_bucket( size_t nBucket )
 609         {
 610             assert( nBucket > 0 );
 611             return nBucket & ~(1 << bitop::MSBnz( nBucket ));
 612         }
 613
 614         aux_node_type * init_bucket( size_t const nBucket )
 615         {
 616             assert( nBucket > 0 );
 617             size_t nParent = parent_bucket( nBucket );
 618
 619             aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
 620             if ( pParentBucket == nullptr ) {
 621                 pParentBucket = init_bucket( nParent );
 622                 m_Stat.onRecursiveInitBucket();
 623             }
 624
 625             assert( pParentBucket != nullptr );
 626
 627             // Allocate an aux node for new bucket
 628             aux_node_type * pBucket = m_Buckets.bucket( nBucket );
 629
 630             back_off bkoff;
 631             for ( ;; pBucket = m_Buckets.bucket( nBucket ) ) {
 632                 if ( pBucket )
 633                     return pBucket;
 634
 635                 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
 636                 if ( pBucket ) {
 637                     if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
 638                         m_Buckets.bucket( nBucket, pBucket );
 639                         m_Stat.onNewBucket();
 640                         return pBucket;
 641                     }
 642
 643                     // Another thread set the bucket. Wait while it done
 644                     free_aux_node( pBucket );
 645                     m_Stat.onBucketInitContenton();
 646                     break;
 647                 }
 648
 649                 // There are no free buckets. It means that the bucket table is full
 650                 // Wait while another thread set the bucket or a free bucket will be available
 651                 m_Stat.onBucketsExhausted();
 652                 bkoff();
 653             }
 654
 655             // Another thread set the bucket. Wait while it done
 656             for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket ) ) {
 657                 bkoff();
 658                 m_Stat.onBusyWaitBucketInit();
 659             }
 660
 661             return pBucket;
 662         }
 663
 664         aux_node_type * get_bucket( size_t nHash )
 665         {
 666             size_t nBucket = bucket_no( nHash );
 667
 668             aux_node_type * pHead = m_Buckets.bucket( nBucket );
 669             if ( pHead == nullptr )
 670                 pHead = init_bucket( nBucket );
 671
 672             assert( pHead->is_dummy() );
 673
 674             return pHead;
 675         }
 676
 677         void init()
 678         {
 679             // Initialize bucket 0
 680             aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
 681
 682             // insert_aux_node cannot return false for empty list
 683             CDS_VERIFY( m_List.insert_aux_node( pNode ) );
 684
 685             m_Buckets.bucket( 0, pNode );
 686         }
 687
 688         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
 689         {
 690             return nBucketCount * nLoadFactor;
 691         }
 692
 693         void inc_item_count()
 694         {
 695             size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
 696             if ( ++m_ItemCounter <= nMaxCount )
 697                 return;
 698
 699             size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
 700             const size_t nBucketCount = static_cast<size_t>(1) << sz;
 701             if ( nBucketCount < m_Buckets.capacity() ) {
 702                 // we may grow the bucket table
 703                 const size_t nLoadFactor = m_Buckets.load_factor();
 704                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ) )
 705                     return; // someone already have updated m_nBucketCountLog2, so stop here
 706
 707                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
 708                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 709                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 710             }
 711             else
 712                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
 713         }
 714         //@endcond
 715
 716     protected:
 717         //@cond
 718         static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
 719
 720         typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
 721         padded_bucket_table     m_Buckets;          ///< bucket table
 722
 723         typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
 724         padded_ordered_list     m_List;             ///< Ordered list containing split-list items
 725
 726         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
 727         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
 728         item_counter            m_ItemCounter;      ///< Item counter
 729         hash                    m_HashFunctor;      ///< Hash functor
 730         stat                    m_Stat;             ///< Internal statistics
 731         //@endcond
 732     };
 733
 734 }} // namespace cds::intrusive
 735
 736 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H