Fixed max bucket count error in SplitList

[libcds.git] / cds / intrusive / split_list_nogc.h

diff --git a/cds/intrusive/split_list_nogc.h b/cds/intrusive/split_list_nogc.h
index 28e7124dba2e70c57dd41888abfa548eae9e09a4..5eeb991fc03edf5ba8872b6e9dbdc2c24728d82e 100644 (file)
--- a/cds/intrusive/split_list_nogc.h
+++ b/cds/intrusive/split_list_nogc.h
@@ -1,7 +1,9 @@
 //$$CDS-header$$
 
-#ifndef __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H
-#define __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H
+#ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
+#define CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
+
+#include <limits>
 
 #include <cds/intrusive/details/split_list_base.h>
 #include <cds/gc/nogc.h>
@@ -37,6 +39,10 @@ namespace cds { namespace intrusive {
         /// Hash functor for \p value_type and all its derivatives that you use
         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type   hash;
 
+        //@cond
+        typedef cds::intrusive::split_list::implementation_tag implementation_tag;
+        //@endcond
+
     protected:
         //@cond
         typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
@@ -140,6 +146,7 @@ namespace cds { namespace intrusive {
         ordered_list_wrapper    m_List;             ///< Ordered list containing split-list items
         bucket_table            m_Buckets;          ///< bucket table
         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
+        atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
         item_counter            m_ItemCounter;      ///< Item counter
         hash                    m_HashFunctor;      ///< Hash functor
         stat                    m_Stat;             ///< Internal statistics
@@ -168,7 +175,7 @@ namespace cds { namespace intrusive {
 
         size_t bucket_no( size_t nHash ) const
         {
-            return nHash & ( (1 << m_nBucketCountLog2.load(atomics::memory_order_relaxed)) - 1 );
+            return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
         }
 
         static size_t parent_bucket( size_t nBucket )
@@ -237,7 +244,7 @@ namespace cds { namespace intrusive {
             static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 
             // atomicity::empty_item_counter is not allowed as a item counter
-            static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value, 
+            static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 
             // Initialize bucket 0
@@ -249,12 +256,30 @@ namespace cds { namespace intrusive {
             m_Buckets.bucket( 0, pNode );
         }
 
-        void    inc_item_count()
+        static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
         {
-            size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed);
-            if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
-            {
-                m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, atomics::memory_order_seq_cst, atomics::memory_order_relaxed );
+            return nBucketCount * nLoadFactor;
+        }
+
+        void inc_item_count()
+        {
+            size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
+            if ( ++m_ItemCounter <= nMaxCount )
+                return;
+
+            size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
+            const size_t nBucketCount = static_cast<size_t>(1) << sz;
+            if ( nBucketCount < m_Buckets.capacity() ) {
+                // we may grow the bucket table
+                const size_t nLoadFactor = m_Buckets.load_factor();
+                if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
+                    return; // someone already have updated m_nBucketCountLog2, so stop here
+
+                const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
+                                                                                  : std::numeric_limits<size_t>::max();
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
+                    atomics::memory_order_relaxed );
+                m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
             }
         }
 
@@ -269,6 +294,7 @@ namespace cds { namespace intrusive {
         */
         SplitListSet()
             : m_nBucketCountLog2(1)
+            , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
         {
             init();
         }
@@ -280,6 +306,7 @@ namespace cds { namespace intrusive {
             )
             : m_Buckets( nItemCount, nLoadFactor )
             , m_nBucketCountLog2(1)
+            , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
         {
             init();
         }
@@ -391,6 +418,13 @@ namespace cds { namespace intrusive {
         {
             return find_( key, key_comparator(), f );
         }
+        //@cond
+        template <typename Q, typename Func>
+        bool find( Q const& key, Func f )
+        {
+            return find_( key, key_comparator(), f );
+        }
+        //@endcond
 
         /// Finds the key \p key with \p pred predicate for comparing
         /**
@@ -402,8 +436,17 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Less, typename Func>
         bool find_with( Q& key, Less pred, Func f )
         {
+            CDS_UNUSED( pred );
             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
         }
+        //@cond
+        template <typename Q, typename Less, typename Func>
+        bool find_with( Q const& key, Less pred, Func f )
+        {
+            CDS_UNUSED( pred );
+            return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
+        }
+        //@endcond
 
         /// Checks if the set is empty
         /**
@@ -421,6 +464,12 @@ namespace cds { namespace intrusive {
             return m_ItemCounter;
         }
 
+        /// Returns internal statistics
+        stat const& statistics() const
+        {
+            return m_Stat;
+        }
+
     protected:
         //@cond
         template <bool IsConst>
@@ -486,7 +535,7 @@ namespace cds { namespace intrusive {
         {
             return const_iterator( m_List.begin(), m_List.end() );
         }
-        const_iterator cbegin()
+        const_iterator cbegin() const
         {
             return const_iterator( m_List.cbegin(), m_List.cend() );
         }
@@ -498,7 +547,7 @@ namespace cds { namespace intrusive {
         {
             return const_iterator( m_List.end(), m_List.end() );
         }
-        const_iterator cend()
+        const_iterator cend() const
         {
             return const_iterator( m_List.cend(), m_List.cend() );
         }
@@ -549,6 +598,7 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Less >
         iterator find_with_( Q& val, Less pred )
         {
+            CDS_UNUSED( pred );
             size_t nHash = hash_value( val );
             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
             dummy_node_type * pHead = get_bucket( nHash );
@@ -588,4 +638,4 @@ namespace cds { namespace intrusive {
 
 }} // namespace cds::intrusive
 
-#endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H
+#endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H