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