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-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_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> ordered_list_adapter;
  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 ordered_list_adapter::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 typename ordered_list_adapter::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             , typename ordered_list_adapter::aux_node
 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 ordered_list_adapter::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 ordered_list_adapter::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         /// Returns internal statistics for \p OrderedList
 415         typename OrderedList::stat const& list_statistics() const
 416         {
 417             return m_List.statistics();
 418         }
 419
 420     protected:
 421         //@cond
 422         template <bool IsConst>
 423         class iterator_type
 424             : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 425         {
 426             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 427             typedef typename iterator_base_class::list_iterator list_iterator;
 428         public:
 429             iterator_type()
 430                 : iterator_base_class()
 431             {}
 432
 433             iterator_type( iterator_type const& src )
 434                 : iterator_base_class( src )
 435             {}
 436
 437             // This ctor should be protected...
 438             iterator_type( list_iterator itCur, list_iterator itEnd )
 439                 : iterator_base_class( itCur, itEnd )
 440             {}
 441         };
 442         //@endcond
 443
 444     public:
 445     ///@name Forward iterators
 446     //@{
 447         /// Forward iterator
 448         /**
 449             The forward iterator for a split-list has some features:
 450             - it has no post-increment operator
 451             - it depends on iterator of underlying \p OrderedList
 452         */
 453         typedef iterator_type<false>    iterator;
 454
 455         /// Const forward iterator
 456         /**
 457             For iterator's features and requirements see \ref iterator
 458         */
 459         typedef iterator_type<true>     const_iterator;
 460
 461         /// Returns a forward iterator addressing the first element in a split-list
 462         /**
 463             For empty list \code begin() == end() \endcode
 464         */
 465         iterator begin()
 466         {
 467             return iterator( m_List.begin(), m_List.end());
 468         }
 469
 470         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 471         /**
 472             Do not use the value returned by <tt>end</tt> function to access any item.
 473
 474             The returned value can be used only to control reaching the end of the split-list.
 475             For empty list \code begin() == end() \endcode
 476         */
 477         iterator end()
 478         {
 479             return iterator( m_List.end(), m_List.end());
 480         }
 481
 482         /// Returns a forward const iterator addressing the first element in a split-list
 483         const_iterator begin() const
 484         {
 485             return const_iterator( m_List.begin(), m_List.end());
 486         }
 487
 488         /// Returns a forward const iterator addressing the first element in a split-list
 489         const_iterator cbegin() const
 490         {
 491             return const_iterator( m_List.cbegin(), m_List.cend());
 492         }
 493
 494         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 495         const_iterator end() const
 496         {
 497             return const_iterator( m_List.end(), m_List.end());
 498         }
 499
 500         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 501         const_iterator cend() const
 502         {
 503             return const_iterator( m_List.cend(), m_List.cend());
 504         }
 505     //@}
 506
 507     protected:
 508         //@cond
 509         iterator insert_( value_type& val )
 510         {
 511             size_t nHash = hash_value( val );
 512             aux_node_type * pHead = get_bucket( nHash );
 513             assert( pHead != nullptr );
 514
 515             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 516
 517             list_iterator it = m_List.insert_at_( pHead, val );
 518             if ( it != m_List.end()) {
 519                 inc_item_count();
 520                 m_Stat.onInsertSuccess();
 521                 return iterator( it, m_List.end());
 522             }
 523             m_Stat.onInsertFailed();
 524             return end();
 525         }
 526
 527         template <typename Func>
 528         std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
 529         {
 530             size_t nHash = hash_value( val );
 531             aux_node_type * pHead = get_bucket( nHash );
 532             assert( pHead != nullptr );
 533
 534             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 535
 536             std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
 537             if ( ret.first != m_List.end()) {
 538                 if ( ret.second ) {
 539                     inc_item_count();
 540                     m_Stat.onUpdateNew();
 541                 }
 542                 else
 543                     m_Stat.onUpdateExist();
 544                 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
 545             }
 546             return std::make_pair( end(), ret.second );
 547         }
 548
 549         template <typename Q, typename Less >
 550         iterator find_with_( Q& val, Less pred )
 551         {
 552             CDS_UNUSED( pred );
 553             size_t nHash = hash_value( val );
 554             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 555             aux_node_type * pHead = get_bucket( nHash );
 556             assert( pHead != nullptr );
 557
 558             auto it = m_List.find_at_( pHead, sv, typename ordered_list_adapter::template make_compare_from_less<Less>());
 559             m_Stat.onFind( it != m_List.end());
 560             return iterator( it, m_List.end());
 561         }
 562
 563         template <typename Q>
 564         iterator find_( Q const& val )
 565         {
 566             size_t nHash = hash_value( val );
 567             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 568             aux_node_type * pHead = get_bucket( nHash );
 569             assert( pHead != nullptr );
 570
 571             auto it = m_List.find_at_( pHead, sv, key_comparator());
 572             m_Stat.onFind( it != m_List.end());
 573             return iterator( it, m_List.end());
 574         }
 575
 576         template <typename Q, typename Compare, typename Func>
 577         bool find_( Q& val, Compare cmp, Func f )
 578         {
 579             size_t nHash = hash_value( val );
 580             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 581             aux_node_type * pHead = get_bucket( nHash );
 582             assert( pHead != nullptr );
 583             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
 584                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
 585         }
 586
 587         aux_node_type * alloc_aux_node( size_t nHash )
 588         {
 589             m_Stat.onHeadNodeAllocated();
 590             aux_node_type* p = m_Buckets.alloc_aux_node();
 591             if ( p )
 592                 p->m_nHash = nHash;
 593             return p;
 594         }
 595
 596         void free_aux_node( aux_node_type * p )
 597         {
 598             m_Buckets.free_aux_node( p );
 599             m_Stat.onHeadNodeFreed();
 600         }
 601
 602         /// Calculates hash value of \p key
 603         template <typename Q>
 604         size_t hash_value( Q const& key ) const
 605         {
 606             return m_HashFunctor( key );
 607         }
 608
 609         size_t bucket_no( size_t nHash ) const
 610         {
 611             return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
 612         }
 613
 614         static size_t parent_bucket( size_t nBucket )
 615         {
 616             assert( nBucket > 0 );
 617             return nBucket & ~(1 << bitop::MSBnz( nBucket ));
 618         }
 619
 620         aux_node_type * init_bucket( size_t const nBucket )
 621         {
 622             assert( nBucket > 0 );
 623             size_t nParent = parent_bucket( nBucket );
 624
 625             aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
 626             if ( pParentBucket == nullptr ) {
 627                 pParentBucket = init_bucket( nParent );
 628                 m_Stat.onRecursiveInitBucket();
 629             }
 630
 631             assert( pParentBucket != nullptr );
 632
 633             // Allocate an aux node for new bucket
 634             aux_node_type * pBucket = m_Buckets.bucket( nBucket );
 635
 636             back_off bkoff;
 637             for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
 638                 if ( pBucket )
 639                     return pBucket;
 640
 641                 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ));
 642                 if ( pBucket ) {
 643                     if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
 644                         m_Buckets.bucket( nBucket, pBucket );
 645                         m_Stat.onNewBucket();
 646                         return pBucket;
 647                     }
 648
 649                     // Another thread set the bucket. Wait while it done
 650                     free_aux_node( pBucket );
 651                     m_Stat.onBucketInitContenton();
 652                     break;
 653                 }
 654
 655                 // There are no free buckets. It means that the bucket table is full
 656                 // Wait while another thread set the bucket or a free bucket will be available
 657                 m_Stat.onBucketsExhausted();
 658                 bkoff();
 659             }
 660
 661             // Another thread set the bucket. Wait while it done
 662             for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
 663                 bkoff();
 664                 m_Stat.onBusyWaitBucketInit();
 665             }
 666
 667             return pBucket;
 668         }
 669
 670         aux_node_type * get_bucket( size_t nHash )
 671         {
 672             size_t nBucket = bucket_no( nHash );
 673
 674             aux_node_type * pHead = m_Buckets.bucket( nBucket );
 675             if ( pHead == nullptr )
 676                 pHead = init_bucket( nBucket );
 677
 678             assert( pHead->is_dummy());
 679
 680             return pHead;
 681         }
 682
 683         void init()
 684         {
 685             // Initialize bucket 0
 686             aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
 687
 688             // insert_aux_node cannot return false for empty list
 689             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 690
 691             m_Buckets.bucket( 0, pNode );
 692         }
 693
 694         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
 695         {
 696             return nBucketCount * nLoadFactor;
 697         }
 698
 699         void inc_item_count()
 700         {
 701             size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
 702             if ( ++m_ItemCounter <= nMaxCount )
 703                 return;
 704
 705             size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
 706             const size_t nBucketCount = static_cast<size_t>(1) << sz;
 707             if ( nBucketCount < m_Buckets.capacity()) {
 708                 // we may grow the bucket table
 709                 const size_t nLoadFactor = m_Buckets.load_factor();
 710                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
 711                     return; // someone already have updated m_nBucketCountLog2, so stop here
 712
 713                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
 714                     memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 715                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 716             }
 717             else
 718                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
 719         }
 720         //@endcond
 721
 722     protected:
 723         //@cond
 724         static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
 725
 726         typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
 727         padded_bucket_table     m_Buckets;          ///< bucket table
 728
 729         typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
 730         padded_ordered_list     m_List;             ///< Ordered list containing split-list items
 731
 732         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
 733         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
 734         item_counter            m_ItemCounter;      ///< Item counter
 735         hash                    m_HashFunctor;      ///< Hash functor
 736         stat                    m_Stat;             ///< Internal statistics
 737         //@endcond
 738     };
 739
 740 }} // namespace cds::intrusive
 741
 742 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H