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