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