Improved management of SkipList auxiliary nodes: now aux nodes are allocated from...
authorkhizmax <libcds.dev@gmail.com>
Tue, 13 Sep 2016 21:00:58 +0000 (00:00 +0300)
committerkhizmax <libcds.dev@gmail.com>
Tue, 13 Sep 2016 21:00:58 +0000 (00:00 +0300)
44 files changed:
cds/compiler/clang/defs.h
cds/compiler/gcc/defs.h
cds/compiler/vc/defs.h
cds/container/details/split_list_base.h
cds/container/split_list_set.h
cds/container/split_list_set_nogc.h
cds/container/split_list_set_rcu.h
cds/details/type_padding.h
cds/intrusive/details/split_list_base.h
cds/intrusive/free_list.h
cds/intrusive/free_list_selector.h [new file with mode: 0644]
cds/intrusive/free_list_tagged.h
cds/intrusive/options.h
cds/intrusive/split_list.h
cds/intrusive/split_list_nogc.h
cds/intrusive/split_list_rcu.h
cds/opt/options.h
projects/Win/vc14/cds.vcxproj
projects/Win/vc14/cds.vcxproj.filters
test/include/cds_test/stat_splitlist_out.h
test/unit/intrusive-set/intrusive_split_lazy_dhp.cpp
test/unit/intrusive-set/intrusive_split_lazy_hp.cpp
test/unit/intrusive-set/intrusive_split_lazy_nogc.cpp
test/unit/intrusive-set/intrusive_split_michael_dhp.cpp
test/unit/intrusive-set/intrusive_split_michael_hp.cpp
test/unit/intrusive-set/intrusive_split_michael_nogc.cpp
test/unit/intrusive-set/test_intrusive_split_lazy_rcu.h
test/unit/intrusive-set/test_intrusive_split_michael_rcu.h
test/unit/map/split_lazy_dhp.cpp
test/unit/map/split_lazy_hp.cpp
test/unit/map/split_lazy_nogc.cpp
test/unit/map/split_michael_dhp.cpp
test/unit/map/split_michael_hp.cpp
test/unit/map/split_michael_nogc.cpp
test/unit/map/test_split_lazy_rcu.h
test/unit/map/test_split_michael_rcu.h
test/unit/set/split_lazy_dhp.cpp
test/unit/set/split_lazy_hp.cpp
test/unit/set/split_lazy_nogc.cpp
test/unit/set/split_michael_dhp.cpp
test/unit/set/split_michael_hp.cpp
test/unit/set/split_michael_nogc.cpp
test/unit/set/test_split_lazy_rcu.h
test/unit/set/test_split_michael_rcu.h

index 7d27135..473c8fb 100644 (file)
 #define cds_likely( expr )   __builtin_expect( !!( expr ), 1 )
 #define cds_unlikely( expr ) __builtin_expect( !!( expr ), 0 )
 
+// double-width CAS support
+#if CDS_BUILD_BITS == 64
+#   ifdef __GCC_HAVE_SYNC_COMPARE_AND_SWAP_16
+#       define CDS_DCAS_SUPPORT
+#   endif
+#else
+#   ifdef __GCC_HAVE_SYNC_COMPARE_AND_SWAP_8
+#       define CDS_DCAS_SUPPORT
+#   endif
+#endif
+
 #include <cds/compiler/gcc/compiler_barriers.h>
 
 #endif // #ifndef CDSLIB_COMPILER_GCC_DEFS_H
index a6028cc..e2c3b76 100644 (file)
 #define cds_likely( expr )   __builtin_expect( !!( expr ), 1 )
 #define cds_unlikely( expr ) __builtin_expect( !!( expr ), 0 )
 
+// double-width CAS support
+#if CDS_BUILD_BITS == 64
+#   ifdef __GCC_HAVE_SYNC_COMPARE_AND_SWAP_16
+#       define CDS_DCAS_SUPPORT
+#   endif
+#else
+#   ifdef __GCC_HAVE_SYNC_COMPARE_AND_SWAP_8
+#       define CDS_DCAS_SUPPORT
+#   endif
+#endif
+
 #include <cds/compiler/gcc/compiler_barriers.h>
 
 #endif // #ifndef CDSLIB_COMPILER_GCC_DEFS_H
index e9dd55b..6d8aa40 100644 (file)
 #   define CDS_DEPRECATED( reason ) __declspec(deprecated( reason ))
 #endif
 
+// double-width CAS support
+//#define CDS_DCAS_SUPPORT
+
 #include <cds/compiler/vc/compiler_barriers.h>
 
 //@endcond
index ef56669..38b4603 100644 (file)
@@ -49,7 +49,7 @@ namespace cds { namespace container {
         /// Disabled internal statistics, see \p cds::intrusive::split_list::empty_stat
         typedef cds::intrusive::split_list::empty_stat empty_stat;
 
-        /// Selector of bucket table implementation =- typedef for \p intrusive::split_list::dynamic_bucket_table
+        /// Selector of bucket table implementation = typedef for \p intrusive::split_list::dynamic_bucket_table
         template <bool Value>
         using dynamic_bucket_table = cds::intrusive::split_list::dynamic_bucket_table<Value>;
 
index 4c48a5d..3917b78 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
index 5dc0b9d..a8cf7f9 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H
index f0795d0..91a9fc7 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_RCU_H
index d273926..e2c5261 100644 (file)
@@ -42,8 +42,7 @@ namespace cds { namespace details {
         };
         char _[Align - Modulo]   ;   // padding
 
-        type_padding_helper() CDS_NOEXCEPT_( noexcept( T() ))
-        {}
+        using T::T;
     };
     template <typename T, int Align>
     struct type_padding_helper<T, Align, 0>: public T
@@ -52,8 +51,7 @@ namespace cds { namespace details {
             value = 0
         };
 
-        type_padding_helper() CDS_NOEXCEPT_( noexcept( T()) )
-        {}
+        using T::T;
     };
     //@endcond
 
@@ -71,8 +69,13 @@ namespace cds { namespace details {
     template <typename T, int AlignFactor>
     class type_padding {
     public:
+        /// Align factor
+        enum {
+            align_factor = AlignFactor <= 0 ? 1 : AlignFactor
+        };
+
         /// Result type
-        typedef type_padding_helper<T, AlignFactor, sizeof(T) % AlignFactor>    type;
+        typedef type_padding_helper<T, align_factor, sizeof(T) % align_factor> type;
 
         /// Padding constant
         enum {
index b7b846a..01fe643 100644 (file)
@@ -37,6 +37,7 @@
 #include <cds/algo/int_algo.h>
 #include <cds/algo/bitop.h>
 #include <cds/opt/hash.h>
+#include <cds/intrusive/free_list_selector.h>
 
 namespace cds { namespace intrusive {
 
@@ -104,6 +105,7 @@ namespace cds { namespace intrusive {
             counter_type    m_nInitBucketRecursive;  ///< Count of recursive bucket initialization
             counter_type    m_nInitBucketContention; ///< Count of bucket init contention encountered
             counter_type    m_nBusyWaitBucketInit;   ///< Count of busy wait cycle while a bucket is initialized
+            counter_type    m_nBucketsExhausted;     ///< Count of failed bucket allocation
 
             //@cond
             void onInsertSuccess()       { ++m_nInsertSuccess; }
@@ -130,6 +132,7 @@ namespace cds { namespace intrusive {
             void onRecursiveInitBucket() { ++m_nInitBucketRecursive; }
             void onBucketInitContenton() { ++m_nInitBucketContention; }
             void onBusyWaitBucketInit()  { ++m_nBusyWaitBucketInit; }
+            void onBucketsExhausted()    { ++m_nBucketsExhausted; }
             //@endcond
         };
 
@@ -153,6 +156,7 @@ namespace cds { namespace intrusive {
             void onRecursiveInitBucket() const {}
             void onBucketInitContenton() const {}
             void onBusyWaitBucketInit()  const {}
+            void onBucketsExhausted()    const {}
             //@endcond
         };
 
@@ -212,6 +216,23 @@ namespace cds { namespace intrusive {
 
             /// Back-off strategy
             typedef cds::backoff::Default back_off;
+
+            /// Padding; default is cache-line padding
+            enum { 
+                padding = cds::opt::cache_line_padding
+            };
+
+            /// Free-list of auxiliary nodes
+            /**
+                The split-list contains auxiliary nodes marked the start of buckets.
+                To increase performance, there is a pool of preallocated aux nodes. The part of the pool is a free-list
+                of aux nodes.
+
+                Default is:
+                - \p cds::intrusive::FreeList - if architecture and/or compiler does not support double-width CAS primitive
+                - \p cds::intrusive::TaggedFreeList - if architecture and/or compiler supports double-width CAS primitive
+            */
+            typedef FreeListImpl free_list;
         };
 
         /// [value-option] Split-list dynamic bucket table option
@@ -247,6 +268,8 @@ namespace cds { namespace intrusive {
             - \p opt::back_off - back-off strategy used for spinning, default is \p cds::backoff::Default.
             - \p opt::stat - internal statistics, default is \p split_list::empty_stat (disabled).
                 To enable internal statistics use \p split_list::stat.
+            - \p opt::padding - a padding to solve false-sharing issues; default is cache-line padding
+            - \p opt::free_list - a free-list implementation, see \p traits::free_list
         */
         template <typename... Options>
         struct make_traits {
@@ -266,6 +289,8 @@ namespace cds { namespace intrusive {
             \p Options are:
             - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
             - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
+            - \p opt::free_list - free-list implementation; default is \p TaggedFreeList if the processor supports double-with CAS
+                 otherwise \p FreeList.
         */
         template <typename GC, typename Node, typename... Options>
         class static_bucket_table
@@ -275,6 +300,7 @@ namespace cds { namespace intrusive {
             {
                 typedef CDS_DEFAULT_ALLOCATOR       allocator;
                 typedef opt::v::relaxed_ordering    memory_model;
+                typedef FreeListImpl                free_list;
             };
             typedef typename opt::make_options< default_options, Options... >::type options;
             //@endcond
@@ -283,27 +309,50 @@ namespace cds { namespace intrusive {
             typedef GC      gc;         ///< Garbage collector
             typedef Node    node_type;  ///< Bucket node type
             typedef atomics::atomic<node_type *> table_entry;  ///< Table entry type
+            typedef typename options::allocator allocator; ///< allocator
 
             /// Bucket table allocator
-            typedef cds::details::Allocator< table_entry, typename options::allocator >  bucket_table_allocator;
+            typedef cds::details::Allocator< table_entry, allocator > bucket_table_allocator;
 
             /// Memory model for atomic operations
             typedef typename options::memory_model  memory_model;
 
+            /// Free-list
+            typedef typename options::free_list free_list;
+
         protected:
+            //@cond
             const size_t   m_nLoadFactor; ///< load factor (average count of items per bucket)
             const size_t   m_nCapacity;   ///< Bucket table capacity
             table_entry *  m_Table;       ///< Bucket table
 
+            typedef typename free_list::node free_list_node;
+            union internal_node_type {
+                node_type       node;
+                free_list_node  free_node;
+
+                ~internal_node_type() {} // to block compiler warnings
+            };
+
+            typedef typename allocator::template rebind< internal_node_type >::other aux_node_allocator;
+
+            internal_node_type*     m_auxNode;           ///< Array of pre-allocated auxiliary nodes
+            atomics::atomic<size_t> m_nAuxNodeAllocated; ///< how many auxiliary node allocated
+            free_list               m_freeList;          ///< Free list
+            //@endcond
+
         protected:
             //@cond
             void allocate_table()
             {
                 m_Table = bucket_table_allocator().NewArray( m_nCapacity, nullptr );
+                m_auxNode = aux_node_allocator().allocate( m_nCapacity );
             }
 
             void destroy_table()
             {
+                m_freeList.clear( []( typename free_list::node* ) {} );
+                aux_node_allocator().deallocate( m_auxNode, m_nCapacity );
                 bucket_table_allocator().Delete( m_Table, m_nCapacity );
             }
             //@endcond
@@ -313,6 +362,7 @@ namespace cds { namespace intrusive {
             static_bucket_table()
                 : m_nLoadFactor(1)
                 , m_nCapacity( 512 * 1024 )
+                , m_nAuxNodeAllocated( 0 )
             {
                 allocate_table();
             }
@@ -322,8 +372,9 @@ namespace cds { namespace intrusive {
                 size_t nItemCount,        ///< Max expected item count in split-ordered list
                 size_t nLoadFactor        ///< Load factor
                 )
-                : m_nLoadFactor( nLoadFactor > 0 ? nLoadFactor : (size_t) 1 ),
-                m_nCapacity( cds::beans::ceil2( nItemCount / m_nLoadFactor ) )
+                : m_nLoadFactor( nLoadFactor > 0 ? nLoadFactor : (size_t) 1 )
+                , m_nCapacity( cds::beans::ceil2( nItemCount / m_nLoadFactor ) )
+                , m_nAuxNodeAllocated( 0 )
             {
                 // m_nCapacity must be power of 2
                 assert( cds::beans::is_power2( m_nCapacity ) );
@@ -352,6 +403,32 @@ namespace cds { namespace intrusive {
                 m_Table[ nBucket ].store( pNode, memory_model::memory_order_release );
             }
 
+            /// Allocates auxiliary node; can return \p nullptr if the table exhausted
+            node_type* alloc_aux_node()
+            {
+                if ( m_nAuxNodeAllocated.load( memory_model::memory_order_relaxed ) < capacity() ) {
+                    // alloc next free node from m_auxNode
+                    size_t const idx = m_nAuxNodeAllocated.fetch_add( 1, memory_model::memory_order_relaxed );
+                    if ( idx < capacity() )
+                        return new( &m_auxNode[idx].node ) node_type;
+                }
+
+                // get from free-list
+                auto pFree = m_freeList.get();
+                if ( pFree )
+                    return new( pFree ) node_type;
+
+                // table exhausted
+                return nullptr;
+            }
+
+            /// Places node type to free-list
+            void free_aux_node( node_type* p )
+            {
+                p->~node_type();
+                m_freeList.put( new(p) free_list_node());
+            }
+
             /// Returns the capacity of the bucket table
             size_t capacity() const
             {
@@ -378,7 +455,9 @@ namespace cds { namespace intrusive {
             \p Options are:
             - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
             - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
-        */
+            - \p opt::free_list - free-list implementation; default is \p TaggedFreeList if the processor supports double-with CAS
+                otherwise \p FreeList.
+            */
         template <typename GC, typename Node, typename... Options>
         class expandable_bucket_table
         {
@@ -387,28 +466,52 @@ namespace cds { namespace intrusive {
             {
                 typedef CDS_DEFAULT_ALLOCATOR       allocator;
                 typedef opt::v::relaxed_ordering    memory_model;
+                typedef FreeListImpl                free_list;
             };
             typedef typename opt::make_options< default_options, Options... >::type options;
             //@endcond
+
         public:
-            typedef GC      gc;        ///< Garbage collector
-            typedef Node    node_type; ///< Bucket node type
-            typedef atomics::atomic<node_type *> table_entry; ///< Table entry type
+            typedef GC       gc;                            ///< Garbage collector
+            typedef Node     node_type;                     ///< Bucket node type
+            typedef typename options::allocator allocator;  ///< allocator
 
             /// Memory model for atomic operations
             typedef typename options::memory_model memory_model;
 
+            /// Free-list
+            typedef typename options::free_list free_list;
+
         protected:
-            typedef atomics::atomic<table_entry *>   segment_type; ///< Bucket table segment type
+            //@cond
+            typedef atomics::atomic<node_type *>    table_entry;    ///< Table entry type
+            typedef atomics::atomic<table_entry *>  segment_type;   ///< Bucket table segment type
 
-        public:
-            /// Bucket table allocator
-            typedef cds::details::Allocator< segment_type, typename options::allocator >  bucket_table_allocator;
+            typedef typename free_list::node free_list_node;
 
-            /// Bucket table segment allocator
-            typedef cds::details::Allocator< table_entry, typename options::allocator >  segment_allocator;
+            union internal_node_type {
+                node_type       aux_node;
+                free_list_node  free_node;
+
+                ~internal_node_type() {}  // to block compiler grumble
+            };
+
+            struct aux_node_segment {
+                atomics::atomic< size_t > aux_node_count; // how many aux nodes allocated from the segment
+                aux_node_segment*         next_segment;
+                // internal_node_type     nodes[];
+
+                aux_node_segment()
+                    : aux_node_count(0)
+                    , next_segment( nullptr )
+                {}
+
+                internal_node_type* segment()
+                {
+                    return reinterpret_cast<internal_node_type*>( this + 1 );
+                }
+            };
 
-        protected:
             /// Bucket table metrics
             struct metrics {
                 size_t    nSegmentCount;    ///< max count of segments in bucket table
@@ -417,85 +520,23 @@ namespace cds { namespace intrusive {
                 size_t    nLoadFactor;      ///< load factor
                 size_t    nCapacity;        ///< max capacity of bucket table
 
-                //@cond
                 metrics()
-                    : nSegmentCount(1024)
-                    , nSegmentSize(512)
+                    : nSegmentCount( 1024 )
+                    , nSegmentSize( 512 )
                     , nSegmentSizeLog2( cds::beans::log2( nSegmentSize ) )
-                    , nLoadFactor(1)
+                    , nLoadFactor( 1 )
                     , nCapacity( nSegmentCount * nSegmentSize )
                 {}
-                //@endcond
             };
-            const metrics   m_metrics; ///< Dynamic bucket table metrics
 
-        protected:
-            segment_type * m_Segments; ///< bucket table - array of segments
-
-        protected:
-            //@cond
-            metrics calc_metrics( size_t nItemCount, size_t nLoadFactor )
-            {
-                metrics m;
-
-                // Calculate m_nSegmentSize and m_nSegmentCount by nItemCount
-                m.nLoadFactor = nLoadFactor > 0 ? nLoadFactor : 1;
-
-                size_t nBucketCount = (size_t)( ((float) nItemCount) / m.nLoadFactor );
-                if ( nBucketCount <= 2 ) {
-                    m.nSegmentCount = 1;
-                    m.nSegmentSize = 2;
-                }
-                else if ( nBucketCount <= 1024 ) {
-                    m.nSegmentCount = 1;
-                    m.nSegmentSize = ((size_t) 1) << beans::log2ceil( nBucketCount );
-                }
-                else {
-                    nBucketCount = beans::log2ceil( nBucketCount );
-                    m.nSegmentCount =
-                        m.nSegmentSize = ((size_t) 1) << ( nBucketCount / 2 );
-                    if ( nBucketCount & 1 )
-                        m.nSegmentSize *= 2;
-                    if ( m.nSegmentCount * m.nSegmentSize * m.nLoadFactor < nItemCount )
-                        m.nSegmentSize *= 2;
-                }
-                m.nCapacity = m.nSegmentCount * m.nSegmentSize;
-                m.nSegmentSizeLog2 = cds::beans::log2( m.nSegmentSize );
-                assert( m.nSegmentSizeLog2 != 0 )   ;   //
-                return m;
-            }
-
-            segment_type * allocate_table()
-            {
-                return bucket_table_allocator().NewArray( m_metrics.nSegmentCount, nullptr );
-            }
-
-            void destroy_table( segment_type * pTable )
-            {
-                bucket_table_allocator().Delete( pTable, m_metrics.nSegmentCount );
-            }
-
-            table_entry * allocate_segment()
-            {
-                return segment_allocator().NewArray( m_metrics.nSegmentSize, nullptr );
-            }
-
-            void destroy_segment( table_entry * pSegment )
-            {
-                segment_allocator().Delete( pSegment, m_metrics.nSegmentSize );
-            }
-
-            void init_segments()
-            {
-                // m_nSegmentSize must be 2**N
-                assert( cds::beans::is_power2( m_metrics.nSegmentSize ));
-                assert( ( ((size_t) 1) << m_metrics.nSegmentSizeLog2) == m_metrics.nSegmentSize );
+            /// Bucket table allocator
+            typedef cds::details::Allocator< segment_type, allocator > bucket_table_allocator;
 
-                // m_nSegmentCount must be 2**K
-                assert( cds::beans::is_power2( m_metrics.nSegmentCount ));
+            /// Bucket table segment allocator
+            typedef cds::details::Allocator< table_entry, allocator > segment_allocator;
 
-                m_Segments = allocate_table();
-            }
+            // Aux node segment allocator
+            typedef typename allocator::template rebind<char>::other raw_allocator;
 
             //@endcond
 
@@ -504,7 +545,7 @@ namespace cds { namespace intrusive {
             expandable_bucket_table()
                 : m_metrics( calc_metrics( 512 * 1024, 1 ))
             {
-                init_segments();
+                init();
             }
 
             /// Creates the table with specified capacity rounded up to nearest power-of-two
@@ -514,18 +555,27 @@ namespace cds { namespace intrusive {
                 )
                 : m_metrics( calc_metrics( nItemCount, nLoadFactor ))
             {
-                init_segments();
+                init();
             }
 
             /// Destroys bucket table
             ~expandable_bucket_table()
             {
+                m_freeList.clear( []( typename free_list::node* ) {} );
+
+                for ( auto aux_segment  = m_auxNodeList.load( atomics::memory_order_relaxed ); aux_segment; ) {
+                    auto next_segment = aux_segment->next_segment;
+                    free_aux_segment( aux_segment );
+                    aux_segment = next_segment;
+                }
+
                 segment_type * pSegments = m_Segments;
                 for ( size_t i = 0; i < m_metrics.nSegmentCount; ++i ) {
-                    table_entry * pEntry = pSegments[i].load(memory_model::memory_order_relaxed);
+                    table_entry* pEntry = pSegments[i].load(memory_model::memory_order_relaxed);
                     if ( pEntry != nullptr )
                         destroy_segment( pEntry );
                 }
+
                 destroy_table( pSegments );
             }
 
@@ -535,7 +585,7 @@ namespace cds { namespace intrusive {
                 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
                 assert( nSegment < m_metrics.nSegmentCount );
 
-                table_entry * pSegment = m_Segments[ nSegment ].load(memory_model::memory_order_acquire);
+                table_entry* pSegment = m_Segments[ nSegment ].load(memory_model::memory_order_acquire);
                 if ( pSegment == nullptr )
                     return nullptr;    // uninitialized bucket
                 return pSegment[ nBucket & (m_metrics.nSegmentSize - 1) ].load(memory_model::memory_order_acquire);
@@ -549,7 +599,7 @@ namespace cds { namespace intrusive {
 
                 segment_type& segment = m_Segments[nSegment];
                 if ( segment.load( memory_model::memory_order_relaxed ) == nullptr ) {
-                    table_entry * pNewSegment = allocate_segment();
+                    table_entry* pNewSegment = allocate_segment();
                     table_entry * pNull = nullptr;
                     if ( !segment.compare_exchange_strong( pNull, pNewSegment, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
                         destroy_segment( pNewSegment );
@@ -558,6 +608,44 @@ namespace cds { namespace intrusive {
                 segment.load(memory_model::memory_order_acquire)[ nBucket & (m_metrics.nSegmentSize - 1) ].store( pNode, memory_model::memory_order_release );
             }
 
+            /// Allocates auxiliary node; can return \p nullptr if the table exhausted
+            node_type* alloc_aux_node()
+            {
+                for ( ;; ) {
+                    aux_node_segment* aux_segment = m_auxNodeList.load( memory_model::memory_order_relaxed );
+                    assert( aux_segment != nullptr );
+
+                    // try to allocate from current aux segment
+                    if ( aux_segment->aux_node_count.load( memory_model::memory_order_relaxed ) < m_metrics.nSegmentSize ) {
+                        size_t idx = aux_segment->aux_node_count.fetch_add( 1, memory_model::memory_order_relaxed );
+                        if ( idx < m_metrics.nSegmentSize )
+                            return new( aux_segment->segment() + idx ) node_type();
+                    }
+
+                    // try allocate from free-list
+                    auto pFree = m_freeList.get();
+                    if ( pFree )
+                        return new( pFree ) node_type;
+
+                    // free-list is empty, current segment is full
+                    // try to allocate new aux segment
+                    // We can allocate more aux segments than we need but it is not a problem in this context
+                    aux_node_segment* new_aux_segment = allocate_aux_segment();
+                    new_aux_segment->aux_node_count.fetch_add( 1, memory_model::memory_order_relaxed );
+                    if ( m_auxNodeList.compare_exchange_strong( aux_segment, new_aux_segment, memory_model::memory_order_relaxed, atomics::memory_order_relaxed ))
+                        return new( new_aux_segment->segment() ) node_type();
+
+                    free_aux_segment( new_aux_segment );
+                }
+            }
+
+            /// Places auxiliary node type to free-list
+            void free_aux_node( node_type* p )
+            {
+                p->~node_type();
+                m_freeList.put( new(p) free_list_node() );
+            }
+
             /// Returns the capacity of the bucket table
             size_t capacity() const
             {
@@ -569,6 +657,92 @@ namespace cds { namespace intrusive {
             {
                 return m_metrics.nLoadFactor;
             }
+
+        protected:
+            //@cond
+            metrics calc_metrics( size_t nItemCount, size_t nLoadFactor )
+            {
+                metrics m;
+
+                // Calculate m_nSegmentSize and m_nSegmentCount by nItemCount
+                m.nLoadFactor = nLoadFactor > 0 ? nLoadFactor : 1;
+
+                size_t nBucketCount = (size_t)(((float)nItemCount) / m.nLoadFactor);
+                if ( nBucketCount <= 2 ) {
+                    m.nSegmentCount = 1;
+                    m.nSegmentSize = 2;
+                }
+                else if ( nBucketCount <= 1024 ) {
+                    m.nSegmentCount = 1;
+                    m.nSegmentSize = ((size_t)1) << beans::log2ceil( nBucketCount );
+                }
+                else {
+                    nBucketCount = beans::log2ceil( nBucketCount );
+                    m.nSegmentCount =
+                        m.nSegmentSize = ((size_t)1) << (nBucketCount / 2);
+                    if ( nBucketCount & 1 )
+                        m.nSegmentSize *= 2;
+                    if ( m.nSegmentCount * m.nSegmentSize * m.nLoadFactor < nItemCount )
+                        m.nSegmentSize *= 2;
+                }
+                m.nCapacity = m.nSegmentCount * m.nSegmentSize;
+                m.nSegmentSizeLog2 = cds::beans::log2( m.nSegmentSize );
+                assert( m.nSegmentSizeLog2 != 0 );   //
+                return m;
+            }
+
+            segment_type * allocate_table()
+            {
+                return bucket_table_allocator().NewArray( m_metrics.nSegmentCount, nullptr );
+            }
+
+            void destroy_table( segment_type * pTable )
+            {
+                bucket_table_allocator().Delete( pTable, m_metrics.nSegmentCount );
+            }
+
+            table_entry* allocate_segment()
+            {
+                return segment_allocator().NewArray( m_metrics.nSegmentSize, nullptr );
+            }
+
+            void destroy_segment( table_entry* pSegment )
+            {
+                segment_allocator().Delete( pSegment, m_metrics.nSegmentSize );
+            }
+
+            aux_node_segment* allocate_aux_segment()
+            {
+                char* p = raw_allocator().allocate( sizeof( aux_node_segment ) + sizeof( internal_node_type ) * m_metrics.nSegmentSize );
+                return new(p) aux_node_segment();
+            }
+
+            void free_aux_segment( aux_node_segment* p )
+            {
+                raw_allocator().deallocate( reinterpret_cast<char*>( p ), sizeof( aux_node_segment ) + sizeof( internal_node_type ) * m_metrics.nSegmentSize );
+            }
+
+            void init()
+            {
+                // m_nSegmentSize must be 2**N
+                assert( cds::beans::is_power2( m_metrics.nSegmentSize ) );
+                assert( (((size_t)1) << m_metrics.nSegmentSizeLog2) == m_metrics.nSegmentSize );
+
+                // m_nSegmentCount must be 2**K
+                assert( cds::beans::is_power2( m_metrics.nSegmentCount ) );
+
+                m_Segments = allocate_table();
+                m_auxNodeList = allocate_aux_segment();
+            }
+            //@endcond
+
+        protected:
+            //@cond
+            metrics const       m_metrics;  ///< Dynamic bucket table metrics
+            segment_type*       m_Segments; ///< bucket table - array of segments
+            atomics::atomic<aux_node_segment*> m_auxNodeList;  ///< segment list of aux nodes
+            free_list           m_freeList; ///< List of free aux nodes
+            //@endcond
         };
 
         /// Split-list node traits
@@ -653,16 +827,6 @@ namespace cds { namespace intrusive {
                 typedef static_bucket_table<GC, Node, Options...>    type;
             };
 
-            template <typename GC, class Alloc >
-            struct dummy_node_disposer {
-                template <typename Node>
-                void operator()( Node * p )
-                {
-                    typedef cds::details::Allocator< Node, Alloc >  node_deallocator;
-                    node_deallocator().Delete( p );
-                }
-            };
-
             template <typename Q>
             struct search_value_type
             {
@@ -731,9 +895,7 @@ namespace cds { namespace intrusive {
                     void operator()( value_type * v )
                     {
                         splitlist_node_type * p = static_cast<splitlist_node_type *>( node_traits::to_node_ptr( v ));
-                        if ( p->is_dummy() )
-                            dummy_node_disposer<gc, typename traits::allocator>()( p );
-                        else
+                        if ( !p->is_dummy() )
                             native_disposer()( v );
                     }
                 };
index 870ea2a..113610a 100644 (file)
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_INTRUSIVE_FREE_LIST_H
diff --git a/cds/intrusive/free_list_selector.h b/cds/intrusive/free_list_selector.h
new file mode 100644 (file)
index 0000000..d407b26
--- /dev/null
@@ -0,0 +1,54 @@
+/*
+    This file is a part of libcds - Concurrent Data Structures library
+
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+    Source code repo: http://github.com/khizmax/libcds/
+    Download: http://sourceforge.net/projects/libcds/files/
+    
+    Redistribution and use in source and binary forms, with or without
+    modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+*/
+
+#ifndef CDSLIB_INTRUSIVE_FREE_LIST_SELECTOR_H
+#define CDSLIB_INTRUSIVE_FREE_LIST_SELECTOR_H
+
+#include <cds/details/defs.h>
+
+#ifdef CDS_DCAS_SUPPORT
+#   include <cds/intrusive/free_list_tagged.h>
+#else
+#   include <cds/intrusive/free_list.h>
+#endif
+
+//@cond
+namespace cds { namespace intrusive {
+
+#ifdef CDS_DCAS_SUPPORT
+    typedef TaggedFreeList  FreeListImpl;
+#else
+    typedef FreeList        FreeListImpl;
+#endif
+
+}} // namespace cds::intrusive
+//@endcond
+
+#endif // CDSLIB_INTRUSIVE_FREE_LIST_SELECTOR_H
index 38eefe9..ab71e8f 100644 (file)
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_INTRUSIVE_FREE_LIST_TAGGED_H
@@ -92,9 +92,31 @@ namespace cds { namespace intrusive {
             //@endcond
         };
 
+    private:
+        //@cond
+        struct tagged_ptr
+        {
+            node *    ptr;
+            uintptr_t tag;
+
+            tagged_ptr()
+                : ptr( nullptr )
+                , tag( 0 )
+            {}
+
+            tagged_ptr( node* p )
+                : ptr( p )
+                , tag( 0 )
+            {}
+        };
+
+        static_assert(sizeof( tagged_ptr ) == sizeof( void * ) * 2, "sizeof( tagged_ptr ) violation");
+        //@endcond
+
     public:
         /// Creates empty free-list
         TaggedFreeList()
+            : m_Head( tagged_ptr())
         {
             // Your platform must support double-width CAS
             assert( m_Head.is_lock_free());
@@ -110,10 +132,11 @@ namespace cds { namespace intrusive {
             assert( empty() );
         }
 
-
         /// Puts \p pNode to the free list
         void put( node * pNode )
         {
+            assert( m_Head.is_lock_free());
+
             tagged_ptr currentHead = m_Head.load( atomics::memory_order_relaxed );
             tagged_ptr newHead = { pNode };
             do {
@@ -169,23 +192,10 @@ namespace cds { namespace intrusive {
 
     private:
         //@cond
-        struct tagged_ptr
-        {
-            node *    ptr;
-            uintptr_t tag;
-
-            tagged_ptr()
-                : ptr( nullptr )
-                , tag( 0 )
-            {}
-        };
-
-        static_assert(sizeof( tagged_ptr ) == sizeof(void *) * 2, "sizeof( tagged_ptr ) violation" );
-
         atomics::atomic<tagged_ptr> m_Head;
         //@endcond    
     };
 
 }} // namespace cds::intrusive
 
-#endif // CDSLIB_INTRUSIVE_FREE_LIST_TAGGED_H
\ No newline at end of file
+#endif // CDSLIB_INTRUSIVE_FREE_LIST_TAGGED_H
index 17d7309..785f197 100644 (file)
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_INTRUSIVE_OPTIONS_H
index 303f7e9..4b7f8e4 100644 (file)
@@ -33,6 +33,7 @@
 
 #include <limits>
 #include <cds/intrusive/details/split_list_base.h>
+#include <cds/details/type_padding.h>
 
 namespace cds { namespace intrusive {
 
@@ -273,9 +274,8 @@ namespace cds { namespace intrusive {
             , aux_node_type
             , opt::allocator< typename traits::allocator >
             , opt::memory_model< memory_model >
+            , opt::free_list< typename traits::free_list >
         >::type bucket_table;
-
-        typedef cds::details::Allocator< aux_node_type, typename traits::allocator > aux_node_allocator;
         //@endcond
 
     protected:
@@ -953,11 +953,15 @@ namespace cds { namespace intrusive {
         aux_node_type * alloc_aux_node( size_t nHash )
         {
             m_Stat.onHeadNodeAllocated();
-            return aux_node_allocator().New( nHash );
+            aux_node_type* p = m_Buckets.alloc_aux_node();
+            if ( p )
+                p->m_nHash = nHash;
+            return p;
         }
+
         void free_aux_node( aux_node_type * p )
         {
-            aux_node_allocator().Delete( p );
+            m_Buckets.free_aux_node( p );
             m_Stat.onHeadNodeFreed();
         }
 
@@ -993,21 +997,35 @@ namespace cds { namespace intrusive {
             assert( pParentBucket != nullptr );
 
             // Allocate a dummy node for new bucket
-            {
-                aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
-                if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
-                    m_Buckets.bucket( nBucket, pBucket );
-                    m_Stat.onNewBucket();
-                    return pBucket;
+            aux_node_type * pBucket;
+            if ( ( pBucket = m_Buckets.bucket( nBucket )) == nullptr ) {
+                pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
+                if ( pBucket ) {
+                    if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
+                        m_Buckets.bucket( nBucket, pBucket );
+                        m_Stat.onNewBucket();
+                        return pBucket;
+                    }
+                    else {
+                        // Another thread set the bucket. Wait while it done
+                        free_aux_node( pBucket );
+                    }
+                }
+                else {
+                    // There are no free buckets. It means that the bucket table is full
+                    // Wait while another thread set th bucket
+                    m_Stat.onBucketsExhausted();
                 }
-                free_aux_node( pBucket );
             }
+            else
+                return pBucket;
 
             // Another thread set the bucket. Wait while it done
 
             // In this point, we must wait while nBucket is empty.
             // The compiler can decide that waiting loop can be "optimized" (stripped)
             // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
+
             m_Stat.onBucketInitContenton();
             back_off bkoff;
             while ( true ) {
@@ -1043,6 +1061,7 @@ namespace cds { namespace intrusive {
 
             // Initialize bucket 0
             aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
+            assert( pNode != nullptr );
 
             // insert_aux_node cannot return false for empty list
             CDS_VERIFY( m_List.insert_aux_node( pNode ) );
@@ -1194,8 +1213,12 @@ namespace cds { namespace intrusive {
 
     protected:
         //@cond
-        ordered_list_wrapper    m_List;             ///< Ordered list containing split-list items
-        bucket_table            m_Buckets;          ///< bucket table
+        typedef typename cds::details::type_padding< bucket_table, traits::padding >::type padded_bucket_table;
+        padded_bucket_table     m_Buckets;          ///< bucket table
+
+        typedef typename cds::details::type_padding< ordered_list_wrapper, traits::padding>::type padded_ordered_list;
+        padded_ordered_list     m_List;             ///< Ordered list containing split-list items
+
         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
index a1bb3be..1544609 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
@@ -35,6 +35,7 @@
 
 #include <cds/intrusive/details/split_list_base.h>
 #include <cds/gc/nogc.h>
+#include <cds/details/type_padding.h>
 
 namespace cds { namespace intrusive {
 
@@ -87,6 +88,13 @@ namespace cds { namespace intrusive {
         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
         typedef typename traits::stat         stat;         ///< Internal statistics, see \p spit_list::stat
 
+        // GC and OrderedList::gc must be the same
+        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,
+            "cds::atomicity::empty_item_counter is not allowed as a item counter");
+
     protected:
         typedef typename ordered_list::node_type  list_node_type;  ///< Node type as declared in ordered list
         typedef split_list::node<list_node_type>  node_type;       ///< split-list node type
@@ -169,150 +177,6 @@ namespace cds { namespace intrusive {
                 return base_class::erase_for( pred );
             }
         };
-
-        //@endcond
-
-    protected:
-        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
-
-    protected:
-        //@cond
-        typedef cds::details::Allocator< aux_node_type, typename traits::allocator >   aux_node_allocator;
-
-        aux_node_type * alloc_aux_node( size_t nHash )
-        {
-            m_Stat.onHeadNodeAllocated();
-            return aux_node_allocator().New( nHash );
-        }
-        void free_aux_node( aux_node_type * p )
-        {
-            aux_node_allocator().Delete( p );
-            m_Stat.onHeadNodeFreed();
-        }
-
-        /// Calculates hash value of \p key
-        template <typename Q>
-        size_t hash_value( Q const& key ) const
-        {
-            return m_HashFunctor( key );
-        }
-
-        size_t bucket_no( size_t nHash ) const
-        {
-            return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
-        }
-
-        static size_t parent_bucket( size_t nBucket )
-        {
-            assert( nBucket > 0 );
-            return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
-        }
-
-        aux_node_type * init_bucket( size_t nBucket )
-        {
-            assert( nBucket > 0 );
-            size_t nParent = parent_bucket( nBucket );
-
-            aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
-            if ( pParentBucket == nullptr ) {
-                pParentBucket = init_bucket( nParent );
-                m_Stat.onRecursiveInitBucket();
-            }
-
-            assert( pParentBucket != nullptr );
-
-            // Allocate a dummy node for new bucket
-            {
-                aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
-                if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
-                    m_Buckets.bucket( nBucket, pBucket );
-                    m_Stat.onNewBucket();
-                    return pBucket;
-                }
-                free_aux_node( pBucket );
-            }
-
-            // Another thread set the bucket. Wait while it done
-
-            // In this point, we must wait while nBucket is empty.
-            // The compiler can decide that waiting loop can be "optimized" (stripped)
-            // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
-            //
-            m_Stat.onBucketInitContenton();
-            back_off bkoff;
-            while ( true ) {
-                aux_node_type volatile * p = m_Buckets.bucket( nBucket );
-                if ( p && p != nullptr )
-                    return const_cast<aux_node_type *>( p );
-                bkoff();
-                m_Stat.onBusyWaitBucketInit();
-            }
-        }
-
-        aux_node_type * get_bucket( size_t nHash )
-        {
-            size_t nBucket = bucket_no( nHash );
-
-            aux_node_type * pHead = m_Buckets.bucket( nBucket );
-            if ( pHead == nullptr )
-                pHead = init_bucket( nBucket );
-
-            assert( pHead->is_dummy() );
-
-            return pHead;
-        }
-
-        void init()
-        {
-            // GC and OrderedList::gc must be the same
-            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,
-                           "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
-            // Initialize bucket 0
-            aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
-
-            // insert_aux_node cannot return false for empty list
-            CDS_VERIFY( m_List.insert_aux_node( pNode ));
-
-            m_Buckets.bucket( 0, pNode );
-        }
-
-        static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
-        {
-            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
-
-                m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
-                                                         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 );
-            }
-            else
-                m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
-        }
-
         //@endcond
 
     public:
@@ -707,6 +571,145 @@ namespace cds { namespace intrusive {
                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
         }
 
+        aux_node_type * alloc_aux_node( size_t nHash )
+        {
+            m_Stat.onHeadNodeAllocated();
+            aux_node_type* p = m_Buckets.alloc_aux_node();
+            if ( p )
+                p->m_nHash = nHash;
+            return p;
+        }
+
+        void free_aux_node( aux_node_type * p )
+        {
+            m_Buckets.free_aux_node( p );
+            m_Stat.onHeadNodeFreed();
+        }
+
+        /// Calculates hash value of \p key
+        template <typename Q>
+        size_t hash_value( Q const& key ) const
+        {
+            return m_HashFunctor( key );
+        }
+
+        size_t bucket_no( size_t nHash ) const
+        {
+            return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
+        }
+
+        static size_t parent_bucket( size_t nBucket )
+        {
+            assert( nBucket > 0 );
+            return nBucket & ~(1 << bitop::MSBnz( nBucket ));
+        }
+
+        aux_node_type * init_bucket( size_t nBucket )
+        {
+            assert( nBucket > 0 );
+            size_t nParent = parent_bucket( nBucket );
+
+            aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
+            if ( pParentBucket == nullptr ) {
+                pParentBucket = init_bucket( nParent );
+                m_Stat.onRecursiveInitBucket();
+            }
+
+            assert( pParentBucket != nullptr );
+
+            // Allocate a dummy node for new bucket
+            {
+                aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
+                if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
+                    m_Buckets.bucket( nBucket, pBucket );
+                    m_Stat.onNewBucket();
+                    return pBucket;
+                }
+                free_aux_node( pBucket );
+            }
+
+            // Another thread set the bucket. Wait while it done
+
+            // In this point, we must wait while nBucket is empty.
+            // The compiler can decide that waiting loop can be "optimized" (stripped)
+            // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
+            //
+            m_Stat.onBucketInitContenton();
+            back_off bkoff;
+            while ( true ) {
+                aux_node_type volatile * p = m_Buckets.bucket( nBucket );
+                if ( p && p != nullptr )
+                    return const_cast<aux_node_type *>(p);
+                bkoff();
+                m_Stat.onBusyWaitBucketInit();
+            }
+        }
+
+        aux_node_type * get_bucket( size_t nHash )
+        {
+            size_t nBucket = bucket_no( nHash );
+
+            aux_node_type * pHead = m_Buckets.bucket( nBucket );
+            if ( pHead == nullptr )
+                pHead = init_bucket( nBucket );
+
+            assert( pHead->is_dummy() );
+
+            return pHead;
+        }
+
+        void init()
+        {
+            // Initialize bucket 0
+            aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
+
+            // insert_aux_node cannot return false for empty list
+            CDS_VERIFY( m_List.insert_aux_node( pNode ) );
+
+            m_Buckets.bucket( 0, pNode );
+        }
+
+        static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
+        {
+            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
+
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
+                    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 );
+            }
+            else
+                m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
+        }
+        //@endcond
+
+    protected:
+        //@cond
+        typedef typename cds::details::type_padding< bucket_table, traits::padding >::type padded_bucket_table;
+        padded_bucket_table     m_Buckets;          ///< bucket table
+
+        typedef typename cds::details::type_padding< ordered_list_wrapper, traits::padding>::type padded_ordered_list;
+        padded_ordered_list     m_List;             ///< Ordered list containing split-list items
+
+        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
         //@endcond
     };
 
index 6f264cc..8ea2078 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
@@ -35,6 +35,7 @@
 
 #include <cds/intrusive/details/split_list_base.h>
 #include <cds/details/binary_functor_wrapper.h>
+#include <cds/details/type_padding.h>
 
 namespace cds { namespace intrusive {
 
@@ -123,6 +124,13 @@ namespace cds { namespace intrusive {
         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
         typedef typename traits::stat         stat;         ///< Internal statistics
 
+        // GC and OrderedList::gc must be the same
+        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,
+                        "cds::atomicity::empty_item_counter is not allowed as a item counter");
+
     protected:
         typedef typename ordered_list::node_type    list_node_type;  ///< Node type as declared in ordered list
         typedef split_list::node<list_node_type>    node_type;       ///< split-list node type
@@ -264,244 +272,6 @@ namespace cds { namespace intrusive {
         };
         //@endcond
 
-    protected:
-        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 accumulator
-
-    protected:
-        //@cond
-        typedef cds::details::Allocator< aux_node_type, typename traits::allocator >   aux_node_allocator;
-
-        aux_node_type * alloc_aux_node( size_t nHash )
-        {
-            m_Stat.onHeadNodeAllocated();
-            return aux_node_allocator().New( nHash );
-        }
-        void free_aux_node( aux_node_type * p )
-        {
-            aux_node_allocator().Delete( p );
-            m_Stat.onHeadNodeFreed();
-        }
-
-        /// Calculates hash value of \p key
-        template <typename Q>
-        size_t hash_value( Q const& key ) const
-        {
-            return m_HashFunctor( key );
-        }
-
-        size_t bucket_no( size_t nHash ) const
-        {
-            return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
-        }
-
-        static size_t parent_bucket( size_t nBucket )
-        {
-            assert( nBucket > 0 );
-            return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
-        }
-
-        aux_node_type * init_bucket( size_t nBucket )
-        {
-            assert( nBucket > 0 );
-            size_t nParent = parent_bucket( nBucket );
-
-            aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
-            if ( pParentBucket == nullptr ) {
-                pParentBucket = init_bucket( nParent );
-                m_Stat.onRecursiveInitBucket();
-            }
-
-            assert( pParentBucket != nullptr );
-
-            // Allocate a dummy node for new bucket
-            {
-                aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
-                if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
-                    m_Buckets.bucket( nBucket, pBucket );
-                    m_Stat.onNewBucket();
-                    return pBucket;
-                }
-                free_aux_node( pBucket );
-            }
-
-            // Another thread set the bucket. Wait while it done
-
-            // In this point, we must wait while nBucket is empty.
-            // The compiler can decide that waiting loop can be "optimized" (stripped)
-            // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
-            //
-            m_Stat.onBucketInitContenton();
-            back_off bkoff;
-            while ( true ) {
-                aux_node_type volatile * p = m_Buckets.bucket( nBucket );
-                if ( p != nullptr )
-                    return const_cast<aux_node_type *>( p );
-                bkoff();
-                m_Stat.onBusyWaitBucketInit();
-            }
-        }
-
-        aux_node_type * get_bucket( size_t nHash )
-        {
-            size_t nBucket = bucket_no( nHash );
-
-            aux_node_type * pHead = m_Buckets.bucket( nBucket );
-            if ( pHead == nullptr )
-                pHead = init_bucket( nBucket );
-
-            assert( pHead->is_dummy() );
-
-            return pHead;
-        }
-
-        void init()
-        {
-            // GC and OrderedList::gc must be the same
-            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,
-                           "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
-            // Initialize bucket 0
-            aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
-
-            // insert_aux_node cannot return false for empty list
-            CDS_VERIFY( m_List.insert_aux_node( pNode ));
-
-            m_Buckets.bucket( 0, pNode );
-        }
-
-        static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
-        {
-            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
-
-                m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
-                                                         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 );
-            }
-            else
-                m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
-        }
-
-        template <typename Q, typename Compare, typename Func>
-        bool find_( Q& val, Compare cmp, Func f )
-        {
-            size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
-            aux_node_type * pHead = get_bucket( nHash );
-            assert( pHead != nullptr );
-
-            return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
-                [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
-        }
-
-        template <typename Q, typename Compare>
-        bool find_value( Q const& val, Compare cmp )
-        {
-            size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            aux_node_type * pHead = get_bucket( nHash );
-            assert( pHead != nullptr );
-
-            return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
-        }
-
-        template <typename Q, typename Compare>
-        raw_ptr get_( Q const& val, Compare cmp )
-        {
-            size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            aux_node_type * pHead = get_bucket( nHash );
-            assert( pHead != nullptr );
-
-            raw_ptr p = m_List.get_at( pHead, sv, cmp );
-            m_Stat.onFind( !!p );
-            return p;
-        }
-
-        template <typename Q, typename Compare>
-        value_type * extract_( Q const& val, Compare cmp )
-        {
-            size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            aux_node_type * pHead = get_bucket( nHash );
-            assert( pHead != nullptr );
-
-            value_type * pNode = m_List.extract_at( pHead, sv, cmp );
-            if ( pNode ) {
-                --m_ItemCounter;
-                m_Stat.onExtractSuccess();
-            }
-            else
-                m_Stat.onExtractFailed();
-            return pNode;
-        }
-
-        template <typename Q, typename Less>
-        value_type * extract_with_( Q const& val, Less pred )
-        {
-            CDS_UNUSED( pred );
-            return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
-        }
-
-        template <typename Q, typename Compare>
-        bool erase_( const Q& val, Compare cmp )
-        {
-            size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            aux_node_type * pHead = get_bucket( nHash );
-            assert( pHead != nullptr );
-
-            if ( m_List.erase_at( pHead, sv, cmp ) ) {
-                --m_ItemCounter;
-                m_Stat.onEraseSuccess();
-                return true;
-            }
-            m_Stat.onEraseFailed();
-            return false;
-        }
-
-        template <typename Q, typename Compare, typename Func>
-        bool erase_( Q const& val, Compare cmp, Func f )
-        {
-            size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            aux_node_type * pHead = get_bucket( nHash );
-            assert( pHead != nullptr );
-
-            if ( m_List.erase_at( pHead, sv, cmp, f )) {
-                --m_ItemCounter;
-                m_Stat.onEraseSuccess();
-                return true;
-            }
-            m_Stat.onEraseFailed();
-            return false;
-        }
-
-        //@endcond
-
     public:
         /// Initialize split-ordered list of default capacity
         /**
@@ -1087,6 +857,244 @@ namespace cds { namespace intrusive {
             return const_iterator( m_List.cend(), m_List.cend() );
         }
     //@}
+
+    protected:
+        //@cond
+        aux_node_type * alloc_aux_node( size_t nHash )
+        {
+            m_Stat.onHeadNodeAllocated();
+            aux_node_type* p = m_Buckets.alloc_aux_node();
+            if ( p )
+                p->m_nHash = nHash;
+            return p;
+        }
+
+        void free_aux_node( aux_node_type * p )
+        {
+            m_Buckets.free_aux_node( p );
+            m_Stat.onHeadNodeFreed();
+        }
+
+        /// Calculates hash value of \p key
+        template <typename Q>
+        size_t hash_value( Q const& key ) const
+        {
+            return m_HashFunctor( key );
+        }
+
+        size_t bucket_no( size_t nHash ) const
+        {
+            return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
+        }
+
+        static size_t parent_bucket( size_t nBucket )
+        {
+            assert( nBucket > 0 );
+            return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
+        }
+
+        aux_node_type * init_bucket( size_t nBucket )
+        {
+            assert( nBucket > 0 );
+            size_t nParent = parent_bucket( nBucket );
+
+            aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
+            if ( pParentBucket == nullptr ) {
+                pParentBucket = init_bucket( nParent );
+                m_Stat.onRecursiveInitBucket();
+            }
+
+            assert( pParentBucket != nullptr );
+
+            // Allocate a dummy node for new bucket
+            {
+                aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
+                if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
+                    m_Buckets.bucket( nBucket, pBucket );
+                    m_Stat.onNewBucket();
+                    return pBucket;
+                }
+                free_aux_node( pBucket );
+            }
+
+            // Another thread set the bucket. Wait while it done
+
+            // In this point, we must wait while nBucket is empty.
+            // The compiler can decide that waiting loop can be "optimized" (stripped)
+            // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
+            //
+            m_Stat.onBucketInitContenton();
+            back_off bkoff;
+            while ( true ) {
+                aux_node_type volatile * p = m_Buckets.bucket( nBucket );
+                if ( p != nullptr )
+                    return const_cast<aux_node_type *>( p );
+                bkoff();
+                m_Stat.onBusyWaitBucketInit();
+            }
+        }
+
+        aux_node_type * get_bucket( size_t nHash )
+        {
+            size_t nBucket = bucket_no( nHash );
+
+            aux_node_type * pHead = m_Buckets.bucket( nBucket );
+            if ( pHead == nullptr )
+                pHead = init_bucket( nBucket );
+
+            assert( pHead->is_dummy() );
+
+            return pHead;
+        }
+
+        void init()
+        {
+            // Initialize bucket 0
+            aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
+
+            // insert_aux_node cannot return false for empty list
+            CDS_VERIFY( m_List.insert_aux_node( pNode ));
+
+            m_Buckets.bucket( 0, pNode );
+        }
+
+        static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
+        {
+            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
+
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
+                                                         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 );
+            }
+            else
+                m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
+        }
+
+        template <typename Q, typename Compare, typename Func>
+        bool find_( Q& val, Compare cmp, Func f )
+        {
+            size_t nHash = hash_value( val );
+            split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
+            aux_node_type * pHead = get_bucket( nHash );
+            assert( pHead != nullptr );
+
+            return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
+                [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
+        }
+
+        template <typename Q, typename Compare>
+        bool find_value( Q const& val, Compare cmp )
+        {
+            size_t nHash = hash_value( val );
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            aux_node_type * pHead = get_bucket( nHash );
+            assert( pHead != nullptr );
+
+            return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
+        }
+
+        template <typename Q, typename Compare>
+        raw_ptr get_( Q const& val, Compare cmp )
+        {
+            size_t nHash = hash_value( val );
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            aux_node_type * pHead = get_bucket( nHash );
+            assert( pHead != nullptr );
+
+            raw_ptr p = m_List.get_at( pHead, sv, cmp );
+            m_Stat.onFind( !!p );
+            return p;
+        }
+
+        template <typename Q, typename Compare>
+        value_type * extract_( Q const& val, Compare cmp )
+        {
+            size_t nHash = hash_value( val );
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            aux_node_type * pHead = get_bucket( nHash );
+            assert( pHead != nullptr );
+
+            value_type * pNode = m_List.extract_at( pHead, sv, cmp );
+            if ( pNode ) {
+                --m_ItemCounter;
+                m_Stat.onExtractSuccess();
+            }
+            else
+                m_Stat.onExtractFailed();
+            return pNode;
+        }
+
+        template <typename Q, typename Less>
+        value_type * extract_with_( Q const& val, Less pred )
+        {
+            CDS_UNUSED( pred );
+            return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
+        }
+
+        template <typename Q, typename Compare>
+        bool erase_( const Q& val, Compare cmp )
+        {
+            size_t nHash = hash_value( val );
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            aux_node_type * pHead = get_bucket( nHash );
+            assert( pHead != nullptr );
+
+            if ( m_List.erase_at( pHead, sv, cmp ) ) {
+                --m_ItemCounter;
+                m_Stat.onEraseSuccess();
+                return true;
+            }
+            m_Stat.onEraseFailed();
+            return false;
+        }
+
+        template <typename Q, typename Compare, typename Func>
+        bool erase_( Q const& val, Compare cmp, Func f )
+        {
+            size_t nHash = hash_value( val );
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            aux_node_type * pHead = get_bucket( nHash );
+            assert( pHead != nullptr );
+
+            if ( m_List.erase_at( pHead, sv, cmp, f )) {
+                --m_ItemCounter;
+                m_Stat.onEraseSuccess();
+                return true;
+            }
+            m_Stat.onEraseFailed();
+            return false;
+        }
+        //@endcond
+
+    protected:
+        //@cond
+        typedef typename cds::details::type_padding< bucket_table, traits::padding >::type padded_bucket_table;
+        padded_bucket_table     m_Buckets;          ///< bucket table
+
+        typedef typename cds::details::type_padding< ordered_list_wrapper, traits::padding>::type padded_ordered_list;
+        padded_ordered_list     m_List;             ///< Ordered list containing split-list items
+
+        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 accumulator
+        //@endcond
     };
 
 }}  // namespace cds::intrusive
index f740f02..53e124c 100644 (file)
@@ -688,6 +688,20 @@ namespace opt {
         //@endcond
     };
 
+    /// [type-option] Free-list implementation
+    /**
+        See \p cds::intrusive::FreeList for free-list interface
+    */
+    template <typename FreeList>
+    struct free_list {
+        //@cond
+        template <typename Base> struct pack: public Base
+        {
+            typedef FreeList free_list;
+        };
+        //@endcond
+    };
+
     //@cond
     // For internal use
     template <typename Accessor>
@@ -881,7 +895,6 @@ namespace cds { namespace opt {
                 return (result_type) std::rand();
             }
         };
-
     } // namespace v
 
 }} // namespace cds::opt
index 5fe27e3..acd0a6c 100644 (file)
     <ClInclude Include="..\..\..\cds\intrusive\ellen_bintree_hp.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\ellen_bintree_rcu.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\free_list.h" />\r
+    <ClInclude Include="..\..\..\cds\intrusive\free_list_selector.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\free_list_tagged.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\impl\ellen_bintree.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\impl\iterable_list.h" />\r
index 3ad7fee..e59bf01 100644 (file)
     <ClInclude Include="..\..\..\cds\container\iterable_kvlist_hp.h">\r
       <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
+    <ClInclude Include="..\..\..\cds\intrusive\free_list_selector.h">\r
+      <Filter>Header Files\cds\intrusive</Filter>\r
+    </ClInclude>\r
   </ItemGroup>\r
 </Project>
\ No newline at end of file
index 9034349..d08084e 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSTEST_STAT_SPLITLIST_OUT_H
@@ -58,7 +58,7 @@ namespace cds_test {
             << CDSSTRESS_STAT_OUT( s, m_nBucketCount )
             << CDSSTRESS_STAT_OUT( s, m_nInitBucketRecursive )
             << CDSSTRESS_STAT_OUT( s, m_nInitBucketContention )
-            << CDSSTRESS_STAT_OUT( s, m_nBusyWaitBucketInit );
+            << CDSSTRESS_STAT_OUT( s, m_nBucketsExhausted );
     }
 
 } // namespace cds_test
index aad8207..f1366e6 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_intrusive_set_hp.h"
 
 #include <cds/intrusive/lazy_list_dhp.h>
 #include <cds/intrusive/split_list.h>
+#include <cds/intrusive/free_list.h>
 
 #include <mutex>
 
@@ -161,6 +162,76 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListLazySet_DHP, base_static_bucket_table )
+    {
+        typedef ci::LazyList< gc_type
+            , base_item_type
+            ,ci::lazy_list::make_traits<
+                ci::opt::hook< ci::lazy_list::base_hook< ci::opt::gc< gc_type >>>
+                ,ci::opt::less< less<base_item_type> >
+                ,ci::opt::disposer< mock_disposer >
+            >::type
+        > bucket_type;
+
+        typedef ci::SplitListSet< gc_type, bucket_type,
+            ci::split_list::make_traits<
+                ci::opt::hash< hash_int >
+                , ci::opt::item_counter< cds::atomicity::item_counter >
+                , ci::split_list::dynamic_bucket_table< false >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_DHP, base_free_list )
+    {
+        typedef ci::LazyList< gc_type
+            , base_item_type
+            ,ci::lazy_list::make_traits<
+                ci::opt::hook< ci::lazy_list::base_hook< ci::opt::gc< gc_type >>>
+                ,ci::opt::less< less<base_item_type> >
+                ,ci::opt::disposer< mock_disposer >
+            >::type
+        > bucket_type;
+
+        typedef ci::SplitListSet< gc_type, bucket_type,
+            ci::split_list::make_traits<
+                ci::opt::hash< hash_int >
+                , ci::opt::item_counter< cds::atomicity::item_counter >
+                , ci::opt::free_list< ci::FreeList >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_DHP, base_static_bucket_table_free_list )
+    {
+        typedef ci::LazyList< gc_type
+            , base_item_type
+            ,ci::lazy_list::make_traits<
+                ci::opt::hook< ci::lazy_list::base_hook< ci::opt::gc< gc_type >>>
+                ,ci::opt::less< less<base_item_type> >
+                ,ci::opt::disposer< mock_disposer >
+            >::type
+        > bucket_type;
+
+        typedef ci::SplitListSet< gc_type, bucket_type,
+            ci::split_list::make_traits<
+                ci::opt::hash< hash_int >
+                , ci::opt::item_counter< cds::atomicity::item_counter >
+                , ci::split_list::dynamic_bucket_table< false >
+                , ci::opt::free_list< ci::FreeList >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 
     TEST_F( IntrusiveSplitListLazySet_DHP, member_cmp )
     {
@@ -255,4 +326,75 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListLazySet_DHP, member_static_bucket_table )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_DHP, member_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_DHP, member_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 } // namespace
index eadc023..f91c4ba 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_intrusive_set_hp.h"
 
 #include <cds/intrusive/lazy_list_hp.h>
 #include <cds/intrusive/split_list.h>
+#include <cds/intrusive/free_list.h>
 
 #include <mutex>
 
@@ -162,6 +163,83 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListLazySet_HP, base_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            typedef ci::FreeList  free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_HP, base_static_bucket_table )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef cds::backoff::empty back_off;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_HP, base_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef cds::backoff::empty back_off;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 
     TEST_F( IntrusiveSplitListLazySet_HP, member_cmp )
     {
@@ -256,4 +334,78 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListLazySet_HP, member_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_HP, member_static_bucket_table )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_HP, member_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 } // namespace
index a832f38..139a814 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_intrusive_set_nogc.h"
 
 #include <cds/intrusive/lazy_list_nogc.h>
 #include <cds/intrusive/split_list_nogc.h>
+#include <cds/intrusive/free_list.h>
 
 #include <mutex>
 
@@ -148,6 +149,80 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListLazySet_NoGC, base_static_bucket_table )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_NoGC, base_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_NoGC, base_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
 
     TEST_F( IntrusiveSplitListLazySet_NoGC, member_cmp )
     {
@@ -242,4 +317,76 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListLazySet_NoGC, member_static_bucket_table )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_NoGC, member_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListLazySet_NoGC, member_free_list )
+    {
+        struct list_traits: public ci::lazy_list::traits
+        {
+            typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::LazyList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 } // namespace
index 5d067b7..1a1d665 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_intrusive_set_hp.h"
 
 #include <cds/intrusive/michael_list_dhp.h>
 #include <cds/intrusive/split_list.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace ci = cds::intrusive;
@@ -133,6 +134,80 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListSet_DHP, base_static_bucket_table )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_DHP, base_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_DHP, base_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
 
     TEST_F( IntrusiveSplitListSet_DHP, member_cmp )
     {
@@ -205,4 +280,76 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListSet_DHP, member_static_bucket_table )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynami_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_DHP, member_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynami_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_DHP, member_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 } // namespace
index c904eeb..f08ff04 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_intrusive_set_hp.h"
 
 #include <cds/intrusive/michael_list_hp.h>
 #include <cds/intrusive/split_list.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace ci = cds::intrusive;
@@ -134,6 +135,81 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListSet_HP, base_static_bucket_table )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_HP, base_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_HP, base_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 
     TEST_F( IntrusiveSplitListSet_HP, member_cmp )
     {
@@ -206,4 +282,76 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListSet_HP, member_static_bucket_table )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_HP, member_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_HP, member_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 } // namespace
index ed7c0c3..87f74be 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_intrusive_set_nogc.h"
 
 #include <cds/intrusive/michael_list_nogc.h>
 #include <cds/intrusive/split_list_nogc.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace ci = cds::intrusive;
@@ -120,6 +121,80 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListSet_NoGC, base_static_bucket_table )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_NoGC, base_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef cmp<base_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_NoGC, base_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::base_hook< ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<base_item_type> less;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, base_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::split_list::stat<> stat;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
 
     TEST_F( IntrusiveSplitListSet_NoGC, member_cmp )
     {
@@ -192,4 +267,76 @@ namespace {
         test( s );
     }
 
+    TEST_F( IntrusiveSplitListSet_NoGC, member_static_bucket_table )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_NoGC, member_static_bucket_table_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef cmp<member_item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            enum {
+                dynamic_bucket_table = false
+            };
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveSplitListSet_NoGC, member_free_list )
+    {
+        struct list_traits: public ci::michael_list::traits
+        {
+            typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<gc_type>> hook;
+            typedef base_class::less<member_item_type> less;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::MichaelList< gc_type, member_item_type, list_traits > bucket_type;
+
+        struct set_traits: public ci::split_list::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+            typedef ci::FreeList free_list;
+        };
+        typedef ci::SplitListSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 } // namespace
index c516fba..c917929 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_LAZY_RCU_H
 #define CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_LAZY_RCU_H
@@ -33,6 +33,7 @@
 #include "test_intrusive_set_rcu.h"
 #include <cds/intrusive/lazy_list_rcu.h>
 #include <cds/intrusive/split_list_rcu.h>
+#include <cds/intrusive/free_list.h>
 
 namespace ci = cds::intrusive;
 
@@ -174,6 +175,95 @@ TYPED_TEST_P( IntrusiveSplitLazySet, base_mutex )
     this->test( s );
 }
 
+TYPED_TEST_P( IntrusiveSplitLazySet, base_static_bucket_table )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::base_item_type base_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::lazy_list::traits
+    {
+        typedef ci::lazy_list::base_hook< ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template less<base_item_type> less;
+        typedef typename TestFixture::template cmp<base_item_type> compare;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::LazyList< rcu_type, base_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        typedef ci::split_list::stat<> stat;
+        enum {
+            dynamic_bucket_table = false
+        };
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
+
+TYPED_TEST_P( IntrusiveSplitLazySet, base_static_bucket_table_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::base_item_type base_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::lazy_list::traits
+    {
+        typedef ci::lazy_list::base_hook< ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template less<base_item_type> less;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::LazyList< rcu_type, base_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        typedef ci::split_list::stat<> stat;
+        enum {
+            dynamic_bucket_table = false
+        };
+        typedef ci::FreeList free_list;
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
+
+TYPED_TEST_P( IntrusiveSplitLazySet, base_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::base_item_type base_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::lazy_list::traits
+    {
+        typedef ci::lazy_list::base_hook< ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template cmp<base_item_type> compare;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::LazyList< rcu_type, base_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        typedef ci::split_list::stat<> stat;
+        typedef ci::FreeList free_list;
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
 
 TYPED_TEST_P( IntrusiveSplitLazySet, member_cmp )
 {
@@ -290,11 +380,98 @@ TYPED_TEST_P( IntrusiveSplitLazySet, member_mutex )
     this->test( s );
 }
 
+TYPED_TEST_P( IntrusiveSplitLazySet, member_static_bucket_table )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::member_item_type member_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::lazy_list::traits
+    {
+        typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template less<member_item_type> less;
+        typedef typename TestFixture::template cmp<member_item_type> compare;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::LazyList< rcu_type, member_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        enum {
+            dynamic_bucket_table = false
+        };
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
+
+TYPED_TEST_P( IntrusiveSplitLazySet, member_static_bucket_table_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::member_item_type member_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::lazy_list::traits
+    {
+        typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template less<member_item_type> less;
+        typedef typename TestFixture::template cmp<member_item_type> compare;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::LazyList< rcu_type, member_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        enum {
+            dynamic_bucket_table = false
+        };
+        typedef ci::FreeList free_list;
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
+
+TYPED_TEST_P( IntrusiveSplitLazySet, member_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::member_item_type member_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::lazy_list::traits
+    {
+        typedef ci::lazy_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template cmp<member_item_type> compare;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::LazyList< rcu_type, member_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        typedef ci::FreeList free_list;
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
 
 // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as
 // "No test named <test_name> can be found in this test case"
 REGISTER_TYPED_TEST_CASE_P( IntrusiveSplitLazySet,
-    base_cmp, base_less, base_cmpmix, base_mutex, member_cmp, member_less, member_cmpmix, member_mutex
+    base_cmp, base_less, base_cmpmix, base_mutex, base_static_bucket_table, base_static_bucket_table_free_list, base_free_list, member_cmp, member_less, member_cmpmix, member_mutex, member_static_bucket_table, member_static_bucket_table_free_list, member_free_list
 );
 
 
index c45deb7..2a020a2 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_MICHAEL_RCU_H
 #define CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_MICHAEL_RCU_H
@@ -33,6 +33,7 @@
 #include "test_intrusive_set_rcu.h"
 #include <cds/intrusive/michael_list_rcu.h>
 #include <cds/intrusive/split_list_rcu.h>
+#include <cds/intrusive/free_list.h>
 
 namespace ci = cds::intrusive;
 
@@ -144,6 +145,94 @@ TYPED_TEST_P( IntrusiveSplitMichaelSet, base_cmpmix )
     this->test( s );
 }
 
+TYPED_TEST_P( IntrusiveSplitMichaelSet, base_static_bucket_table )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::base_item_type base_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::michael_list::traits
+    {
+        typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template less<base_item_type> less;
+        typedef typename TestFixture::template cmp<base_item_type> compare;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        typedef ci::split_list::stat<> stat;
+        enum {
+            dynamic_bucket_table = false
+        };
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
+
+TYPED_TEST_P( IntrusiveSplitMichaelSet, base_static_bucket_table_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::base_item_type base_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::michael_list::traits
+    {
+        typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template cmp<base_item_type> compare;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        enum {
+            dynamic_bucket_table = false
+        };
+        typedef ci::FreeList free_list;
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
+
+TYPED_TEST_P( IntrusiveSplitMichaelSet, base_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::base_item_type base_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::michael_list::traits
+    {
+        typedef ci::michael_list::base_hook< ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template less<base_item_type> less;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::MichaelList< rcu_type, base_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        typedef ci::split_list::stat<> stat;
+        typedef ci::FreeList free_list;
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
 
 TYPED_TEST_P( IntrusiveSplitMichaelSet, member_cmp )
 {
@@ -233,12 +322,97 @@ TYPED_TEST_P( IntrusiveSplitMichaelSet, member_cmpmix )
     this->test( s );
 }
 
+TYPED_TEST_P( IntrusiveSplitMichaelSet, member_static_bucket_table )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::member_item_type member_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::michael_list::traits
+    {
+        typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template less<member_item_type> less;
+        typedef typename TestFixture::template cmp<member_item_type> compare;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::MichaelList< rcu_type, member_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        enum {
+            dynamic_bucket_table = false
+        };
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
+
+TYPED_TEST_P( IntrusiveSplitMichaelSet, member_static_bucket_table_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::member_item_type member_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct list_traits: public ci::michael_list::traits
+    {
+        typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template cmp<member_item_type> compare;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::MichaelList< rcu_type, member_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        enum {
+            dynamic_bucket_table = false
+        };
+        typedef ci::FreeList free_list;
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
+
+TYPED_TEST_P( IntrusiveSplitMichaelSet, member_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::member_item_type member_item_type;
+    typedef typename TestFixture::mock_disposer mock_disposer;
+    typedef typename TestFixture::hash_int hash_int;
 
+    struct list_traits: public ci::michael_list::traits
+    {
+        typedef ci::michael_list::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc<rcu_type>> hook;
+        typedef typename TestFixture::template less<member_item_type> less;
+        typedef mock_disposer disposer;
+    };
+    typedef ci::MichaelList< rcu_type, member_item_type, list_traits > bucket_type;
+
+    struct set_traits: public ci::split_list::traits
+    {
+        typedef hash_int hash;
+        typedef typename TestFixture::simple_item_counter item_counter;
+        typedef ci::FreeList free_list;
+    };
+    typedef ci::SplitListSet< rcu_type, bucket_type, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
 
 // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as
 // "No test named <test_name> can be found in this test case"
 REGISTER_TYPED_TEST_CASE_P( IntrusiveSplitMichaelSet,
-    base_cmp, base_less, base_cmpmix, member_cmp, member_less, member_cmpmix
+    base_cmp, base_less, base_cmpmix, base_static_bucket_table, base_static_bucket_table_free_list, base_free_list, member_cmp, member_less, member_cmpmix, member_static_bucket_table, member_static_bucket_table_free_list, member_free_list
 );
 
 
index 70a3124..62697e4 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_map_hp.h"
 
 #include <cds/container/lazy_list_dhp.h>
 #include <cds/container/split_list_map.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -184,6 +185,26 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListLazyMap_DHP, free_list )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::empty back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 3 );
+        test( m );
+    }
+
     TEST_F( SplitListLazyMap_DHP, mutex )
     {
         struct map_traits: public cc::split_list::traits
@@ -232,4 +253,25 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListLazyMap_DHP, static_bucket_table_free_list )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
 } // namespace
index dc76e66..d4f8d6c 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_map_hp.h"
 
 #include <cds/container/lazy_list_hp.h>
 #include <cds/container/split_list_map.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -185,6 +186,26 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListLazyMap_HP, free_list )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::empty back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
     TEST_F( SplitListLazyMap_HP, mutex )
     {
         struct map_traits: public cc::split_list::traits
@@ -233,4 +254,25 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListLazyMap_HP, static_bucket_table_free_list )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
 } // namespace
index a8b8998..881e881 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_map_nogc.h"
 
 #include <cds/container/lazy_list_nogc.h>
 #include <cds/container/split_list_map_nogc.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -168,6 +169,26 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListLazyMap_NoGC, free_list )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::empty back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+    }
+
     TEST_F( SplitListLazyMap_NoGC, mutex )
     {
         struct map_traits: public cc::split_list::traits
@@ -216,5 +237,25 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListLazyMap_NoGC, static_bucket_table_free_list )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
 
 } // namespace
index 7627d2c..0d0fcbd 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_map_hp.h"
 
 #include <cds/container/michael_list_dhp.h>
 #include <cds/container/split_list_map.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -185,6 +186,26 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListMichaelMap_DHP, free_list )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 3 );
+        test( m );
+    }
+
     struct set_static_traits: public cc::split_list::traits
     {
         static bool const dynamic_bucket_table = false;
@@ -210,4 +231,25 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListMichaelMap_DHP, static_bucket_table_free_list )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
 } // namespace
index 16adc93..3384bbc 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_map_hp.h"
 
 #include <cds/container/michael_list_hp.h>
 #include <cds/container/split_list_map.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -185,6 +186,27 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListMichaelMap_HP, free_list )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 3 );
+        test( m );
+    }
+
     struct set_static_traits: public cc::split_list::traits
     {
         static bool const dynamic_bucket_table = false;
@@ -210,4 +232,25 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListMichaelMap_HP, static_bucket_table_free_list )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
 } // namespace
index dfe9fc9..c55ab81 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_map_nogc.h"
 
 #include <cds/container/michael_list_nogc.h>
 #include <cds/container/split_list_map_nogc.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -168,6 +169,27 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListMichaelMap_NoGC, free_list )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+    }
+
     struct set_static_traits: public cc::split_list::traits
     {
         static bool const dynamic_bucket_table = false;
@@ -193,5 +215,25 @@ namespace {
         test( m );
     }
 
+    TEST_F( SplitListMichaelMap_NoGC, static_bucket_table_free_list )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
 
 } // namespace
index 0305fa5..050da43 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 #ifndef CDSUNIT_MAP_TEST_SPLIT_LIST_LAZY_RCU_H
 #define CDSUNIT_MAP_TEST_SPLIT_LIST_LAZY_RCU_H
@@ -33,6 +33,7 @@
 #include "test_map_rcu.h"
 #include <cds/container/lazy_list_rcu.h>
 #include <cds/container/split_list_map_rcu.h>
+#include <cds/intrusive/free_list.h>
 
 namespace cc = cds::container;
 
@@ -209,6 +210,31 @@ TYPED_TEST_P( SplitListLazyMap, back_off )
     this->test( m );
 }
 
+TYPED_TEST_P( SplitListLazyMap, free_list )
+{
+    typedef typename TestFixture::rcu_type   rcu_type;
+    typedef typename TestFixture::key_type   key_type;
+    typedef typename TestFixture::value_type value_type;
+    typedef typename TestFixture::hash1      hash1;
+
+    struct map_traits: public cc::split_list::traits
+    {
+        typedef cc::lazy_list_tag ordered_list;
+        typedef hash1 hash;
+        typedef cds::intrusive::FreeList free_list;
+
+        struct ordered_list_traits: public cc::lazy_list::traits
+        {
+            typedef typename TestFixture::cmp compare;
+            typedef cds::backoff::pause back_off;
+        };
+    };
+    typedef cc::SplitListMap< rcu_type, key_type, value_type, map_traits > map_type;
+
+    map_type m( TestFixture::kSize, 2 );
+    this->test( m );
+}
+
 TYPED_TEST_P( SplitListLazyMap, mutex )
 {
     typedef typename TestFixture::rcu_type   rcu_type;
@@ -269,8 +295,34 @@ TYPED_TEST_P( SplitListLazyMap, static_bucket_table )
     this->test( m );
 }
 
+TYPED_TEST_P( SplitListLazyMap, static_bucket_table_free_list )
+{
+    typedef typename TestFixture::rcu_type   rcu_type;
+    typedef typename TestFixture::key_type   key_type;
+    typedef typename TestFixture::value_type value_type;
+    typedef typename TestFixture::hash1      hash1;
+
+    struct map_traits: public set_static_traits
+    {
+        typedef cc::lazy_list_tag ordered_list;
+        typedef hash1 hash;
+        typedef cds::atomicity::item_counter item_counter;
+        typedef cds::intrusive::FreeList free_list;
+
+        struct ordered_list_traits: public cc::lazy_list::traits
+        {
+            typedef typename TestFixture::cmp compare;
+            typedef cds::backoff::pause back_off;
+        };
+    };
+    typedef cc::SplitListMap< rcu_type, key_type, value_type, map_traits > map_type;
+
+    map_type m( TestFixture::kSize, 4 );
+    this->test( m );
+}
+
 REGISTER_TYPED_TEST_CASE_P( SplitListLazyMap,
-    compare, less, cmpmix, item_counting, stat, back_off, mutex, static_bucket_table
+    compare, less, cmpmix, item_counting, stat, back_off, mutex, free_list, static_bucket_table, static_bucket_table_free_list
 );
 
 
index 47713fe..c2b1253 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 #ifndef CDSUNIT_MAP_TEST_SPLIT_LIST_MICHAEL_RCU_H
 #define CDSUNIT_MAP_TEST_SPLIT_LIST_MICHAEL_RCU_H
@@ -33,6 +33,7 @@
 #include "test_map_rcu.h"
 #include <cds/container/michael_list_rcu.h>
 #include <cds/container/split_list_map_rcu.h>
+#include <cds/intrusive/free_list.h>
 
 namespace cc = cds::container;
 
@@ -208,6 +209,31 @@ TYPED_TEST_P( SplitListMichaelMap, back_off )
     this->test( m );
 }
 
+TYPED_TEST_P( SplitListMichaelMap, free_list )
+{
+    typedef typename TestFixture::rcu_type   rcu_type;
+    typedef typename TestFixture::key_type   key_type;
+    typedef typename TestFixture::value_type value_type;
+    typedef typename TestFixture::hash1      hash1;
+
+    struct map_traits: public cc::split_list::traits
+    {
+        typedef cc::michael_list_tag ordered_list;
+        typedef hash1 hash;
+        typedef cds::intrusive::FreeList free_list;
+
+        struct ordered_list_traits: public cc::michael_list::traits
+        {
+            typedef typename TestFixture::cmp compare;
+            typedef cds::backoff::pause back_off;
+        };
+    };
+    typedef cc::SplitListMap< rcu_type, key_type, value_type, map_traits > map_type;
+
+    map_type m( TestFixture::kSize, 2 );
+    this->test( m );
+}
+
 namespace {
     struct set_static_traits: public cc::split_list::traits
     {
@@ -240,8 +266,34 @@ TYPED_TEST_P( SplitListMichaelMap, static_bucket_table )
     this->test( m );
 }
 
+TYPED_TEST_P( SplitListMichaelMap, static_bucket_table_free_list )
+{
+    typedef typename TestFixture::rcu_type   rcu_type;
+    typedef typename TestFixture::key_type   key_type;
+    typedef typename TestFixture::value_type value_type;
+    typedef typename TestFixture::hash1      hash1;
+
+    struct map_traits: public set_static_traits
+    {
+        typedef cc::michael_list_tag ordered_list;
+        typedef hash1 hash;
+        typedef cds::atomicity::item_counter item_counter;
+        typedef cds::intrusive::FreeList free_list;
+
+        struct ordered_list_traits: public cc::michael_list::traits
+        {
+            typedef typename TestFixture::cmp compare;
+            typedef cds::backoff::pause back_off;
+        };
+    };
+    typedef cc::SplitListMap< rcu_type, key_type, value_type, map_traits > map_type;
+
+    map_type m( TestFixture::kSize, 4 );
+    this->test( m );
+}
+
 REGISTER_TYPED_TEST_CASE_P( SplitListMichaelMap,
-    compare, less, cmpmix, item_counting, stat, back_off, static_bucket_table
+    compare, less, cmpmix, item_counting, stat, back_off, free_list, static_bucket_table, static_bucket_table_free_list
 );
 
 
index 3054096..d418ae4 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_hp.h"
 
 #include <cds/container/lazy_list_dhp.h>
 #include <cds/container/split_list_set.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -232,4 +233,46 @@ namespace {
         test( s );
     }
 
+    TEST_F( SplitListLazySet_DHP, free_list )
+    {
+        struct set_traits: public cc::split_list::traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef base_class::less less;
+                typedef cds::backoff::empty back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( SplitListLazySet_DHP, static_bucket_table_free_list )
+    {
+        struct set_traits: public set_static_traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
index 1b38749..9d9829f 100644 (file)
@@ -32,6 +32,7 @@
 
 #include <cds/container/lazy_list_hp.h>
 #include <cds/container/split_list_set.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -233,4 +234,25 @@ namespace {
         test( s );
     }
 
+    TEST_F( SplitListLazySet_HP, free_list )
+    {
+        struct set_traits: public set_static_traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
index afa95ab..4317e32 100644 (file)
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_nogc.h"
 
 #include <cds/container/lazy_list_nogc.h>
 #include <cds/container/split_list_set_nogc.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -216,5 +217,47 @@ namespace {
         test( s );
     }
 
+    TEST_F( SplitListLazySet_NoGC, static_bucket_table_free_list )
+    {
+        struct set_traits: public set_static_traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( SplitListLazySet_NoGC, free_list )
+    {
+        struct set_traits: public cc::split_list::traits
+        {
+            typedef cc::lazy_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::lazy_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::empty back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
 
 } // namespace
index 31b8dd9..41a950e 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_hp.h"
 
 #include <cds/container/michael_list_dhp.h>
 #include <cds/container/split_list_set.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -184,6 +185,26 @@ namespace {
         test( s );
     }
 
+    TEST_F( SplitListMichaelSet_DHP, free_list )
+    {
+        struct set_traits: public cc::split_list::traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
     struct set_static_traits: public cc::split_list::traits
     {
         static bool const dynamic_bucket_table = false;
@@ -209,4 +230,25 @@ namespace {
         test( s );
     }
 
+    TEST_F( SplitListMichaelSet_DHP, static_bucket_table_free_list )
+    {
+        struct set_traits: public set_static_traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
index 0b779e2..f9a88d6 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_hp.h"
 
 #include <cds/container/michael_list_hp.h>
 #include <cds/container/split_list_set.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -185,6 +186,27 @@ namespace {
         test( s );
     }
 
+    TEST_F( SplitListMichaelSet_HP, free_list )
+    {
+        struct set_traits: public cc::split_list::traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 3 );
+        test( s );
+    }
+
     struct set_static_traits: public cc::split_list::traits
     {
         static bool const dynamic_bucket_table = false;
@@ -210,4 +232,25 @@ namespace {
         test( s );
     }
 
+    TEST_F( SplitListMichaelSet_HP, static_bucket_table_free_list )
+    {
+        struct set_traits: public set_static_traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
index 50af1e8..aac2764 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_nogc.h"
 
 #include <cds/container/michael_list_nogc.h>
 #include <cds/container/split_list_set_nogc.h>
+#include <cds/intrusive/free_list.h>
 
 namespace {
     namespace cc = cds::container;
@@ -168,6 +169,26 @@ namespace {
         test( s );
     }
 
+    TEST_F( SplitListMichaelSet_NoGC, free_list )
+    {
+        struct set_traits: public cc::split_list::traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
     struct set_static_traits: public cc::split_list::traits
     {
         static bool const dynamic_bucket_table = false;
@@ -193,5 +214,25 @@ namespace {
         test( s );
     }
 
+    TEST_F( SplitListMichaelSet_NoGC, static_bucket_table_free_list )
+    {
+        struct set_traits: public set_static_traits
+        {
+            typedef cc::michael_list_tag ordered_list;
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::michael_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListSet< gc_type, int_item, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
 
 } // namespace
index 3eb6ddf..f5a2ba6 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 #ifndef CDSUNIT_SET_TEST_SPLIT_LIST_LAZY_RCU_H
 #define CDSUNIT_SET_TEST_SPLIT_LIST_LAZY_RCU_H
@@ -33,6 +33,7 @@
 #include "test_set_rcu.h"
 #include <cds/container/lazy_list_rcu.h>
 #include <cds/container/split_list_set_rcu.h>
+#include <cds/intrusive/free_list.h>
 
 namespace cc = cds::container;
 
@@ -261,11 +262,58 @@ TYPED_TEST_P( SplitListLazySet, static_bucket_table )
     this->test( s );
 }
 
+TYPED_TEST_P( SplitListLazySet, free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::int_item int_item;
+    typedef typename TestFixture::hash_int hash_int;
+
+    typedef cc::SplitListSet< rcu_type, int_item,
+        typename cc::split_list::make_traits<
+            cc::split_list::ordered_list< cc::lazy_list_tag >
+            , cds::opt::hash< hash_int >
+            , cc::split_list::ordered_list_traits< 
+                typename cc::lazy_list::make_traits<
+                    cds::opt::less< typename TestFixture::less >
+                >::type
+            >
+            , cds::opt::free_list< cds::intrusive::FreeList >
+        >::type
+    > set_type;
+
+    set_type s( TestFixture::kSize, 4 );
+    this->test( s );
+}
+
+TYPED_TEST_P( SplitListLazySet, static_bucket_table_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::int_item int_item;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct set_traits: public set_static_traits
+    {
+        typedef cc::lazy_list_tag ordered_list;
+        typedef hash_int hash;
+        typedef cds::atomicity::item_counter item_counter;
+        typedef cds::intrusive::FreeList free_list;
+
+        struct ordered_list_traits: public cc::lazy_list::traits
+        {
+            typedef typename TestFixture::cmp compare;
+            typedef cds::backoff::pause back_off;
+        };
+    };
+    typedef cc::SplitListSet< rcu_type, int_item, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
 
 // GCC 5: All this->test names should be written on single line, otherwise a runtime error will be encountered like as
 // "No this->test named <test_name> can be found in this this->test case"
 REGISTER_TYPED_TEST_CASE_P( SplitListLazySet,
-    compare, less, cmpmix, item_counting, stat, back_off, mutex, static_bucket_table
+    compare, less, cmpmix, item_counting, stat, back_off, mutex, static_bucket_table, free_list, static_bucket_table_free_list
 );
 
 
index b84bb0a..44ee68b 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 #ifndef CDSUNIT_SET_TEST_SPLIT_LIST_MICHAEL_RCU_H
 #define CDSUNIT_SET_TEST_SPLIT_LIST_MICHAEL_RCU_H
@@ -33,6 +33,7 @@
 #include "test_set_rcu.h"
 #include <cds/container/michael_list_rcu.h>
 #include <cds/container/split_list_set_rcu.h>
+#include <cds/intrusive/free_list.h>
 
 namespace cc = cds::container;
 
@@ -202,6 +203,31 @@ TYPED_TEST_P( SplitListMichaelSet, back_off )
     this->test( s );
 }
 
+TYPED_TEST_P( SplitListMichaelSet, free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::int_item int_item;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct set_traits: public cc::split_list::traits
+    {
+        typedef cc::michael_list_tag ordered_list;
+        typedef hash_int hash;
+        typedef cds::atomicity::item_counter item_counter;
+        typedef cds::intrusive::FreeList free_list;
+
+        struct ordered_list_traits: public cc::michael_list::traits
+        {
+            typedef typename TestFixture::cmp compare;
+            typedef cds::backoff::pause back_off;
+        };
+    };
+    typedef cc::SplitListSet< rcu_type, int_item, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 2 );
+    this->test( s );
+}
+
 namespace {
     struct set_static_traits: public cc::split_list::traits
     {
@@ -233,11 +259,36 @@ TYPED_TEST_P( SplitListMichaelSet, static_bucket_table )
     this->test( s );
 }
 
+TYPED_TEST_P( SplitListMichaelSet, static_bucket_table_free_list )
+{
+    typedef typename TestFixture::rcu_type rcu_type;
+    typedef typename TestFixture::int_item int_item;
+    typedef typename TestFixture::hash_int hash_int;
+
+    struct set_traits: public set_static_traits
+    {
+        typedef cc::michael_list_tag ordered_list;
+        typedef hash_int hash;
+        typedef cds::atomicity::item_counter item_counter;
+        typedef cds::intrusive::FreeList free_list;
+
+        struct ordered_list_traits: public cc::michael_list::traits
+        {
+            typedef typename TestFixture::cmp compare;
+            typedef cds::backoff::pause back_off;
+        };
+    };
+    typedef cc::SplitListSet< rcu_type, int_item, set_traits > set_type;
+
+    set_type s( TestFixture::kSize, 4 );
+    this->test( s );
+}
+
 
 // GCC 5: All this->test names should be written on single line, otherwise a runtime error will be encountered like as
 // "No this->test named <test_name> can be found in this this->test case"
 REGISTER_TYPED_TEST_CASE_P( SplitListMichaelSet,
-    compare, less, cmpmix, item_counting, stat, back_off, static_bucket_table
+    compare, less, cmpmix, item_counting, stat, back_off, static_bucket_table, free_list, static_bucket_table_free_list
 );