From: khizmax Date: Tue, 13 Sep 2016 21:00:58 +0000 (+0300) Subject: Improved management of SkipList auxiliary nodes: now aux nodes are allocated from... X-Git-Tag: v2.2.0~133 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=df91b83e7b3e4048b3ea6584cb78a7e7531224d6 Improved management of SkipList auxiliary nodes: now aux nodes are allocated from a pool residing in the bucket table. --- diff --git a/cds/compiler/clang/defs.h b/cds/compiler/clang/defs.h index 7d271354..473c8fb8 100644 --- a/cds/compiler/clang/defs.h +++ b/cds/compiler/clang/defs.h @@ -127,6 +127,17 @@ #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 #endif // #ifndef CDSLIB_COMPILER_GCC_DEFS_H diff --git a/cds/compiler/gcc/defs.h b/cds/compiler/gcc/defs.h index a6028cc6..e2c3b764 100644 --- a/cds/compiler/gcc/defs.h +++ b/cds/compiler/gcc/defs.h @@ -102,6 +102,17 @@ #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 #endif // #ifndef CDSLIB_COMPILER_GCC_DEFS_H diff --git a/cds/compiler/vc/defs.h b/cds/compiler/vc/defs.h index e9dd55b7..6d8aa406 100644 --- a/cds/compiler/vc/defs.h +++ b/cds/compiler/vc/defs.h @@ -159,6 +159,9 @@ # define CDS_DEPRECATED( reason ) __declspec(deprecated( reason )) #endif +// double-width CAS support +//#define CDS_DCAS_SUPPORT + #include //@endcond diff --git a/cds/container/details/split_list_base.h b/cds/container/details/split_list_base.h index ef566692..38b4603c 100644 --- a/cds/container/details/split_list_base.h +++ b/cds/container/details/split_list_base.h @@ -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 using dynamic_bucket_table = cds::intrusive::split_list::dynamic_bucket_table; diff --git a/cds/container/split_list_set.h b/cds/container/split_list_set.h index 4c48a5d4..3917b785 100644 --- a/cds/container/split_list_set.h +++ b/cds/container/split_list_set.h @@ -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: diff --git a/cds/container/split_list_set_nogc.h b/cds/container/split_list_set_nogc.h index 5dc0b9d9..a8cf7f9b 100644 --- a/cds/container/split_list_set_nogc.h +++ b/cds/container/split_list_set_nogc.h @@ -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 diff --git a/cds/container/split_list_set_rcu.h b/cds/container/split_list_set_rcu.h index f0795d09..91a9fc7f 100644 --- a/cds/container/split_list_set_rcu.h +++ b/cds/container/split_list_set_rcu.h @@ -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 diff --git a/cds/details/type_padding.h b/cds/details/type_padding.h index d2739263..e2c52610 100644 --- a/cds/details/type_padding.h +++ b/cds/details/type_padding.h @@ -42,8 +42,7 @@ namespace cds { namespace details { }; char _[Align - Modulo] ; // padding - type_padding_helper() CDS_NOEXCEPT_( noexcept( T() )) - {} + using T::T; }; template struct type_padding_helper: 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 class type_padding { public: + /// Align factor + enum { + align_factor = AlignFactor <= 0 ? 1 : AlignFactor + }; + /// Result type - typedef type_padding_helper type; + typedef type_padding_helper type; /// Padding constant enum { diff --git a/cds/intrusive/details/split_list_base.h b/cds/intrusive/details/split_list_base.h index b7b846ad..01fe6434 100644 --- a/cds/intrusive/details/split_list_base.h +++ b/cds/intrusive/details/split_list_base.h @@ -37,6 +37,7 @@ #include #include #include +#include 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 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 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 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 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 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 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 segment_type; ///< Bucket table segment type + //@cond + typedef atomics::atomic table_entry; ///< Table entry type + typedef atomics::atomic 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( 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::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( 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 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 type; }; - template - struct dummy_node_disposer { - template - void operator()( Node * p ) - { - typedef cds::details::Allocator< Node, Alloc > node_deallocator; - node_deallocator().Delete( p ); - } - }; - template struct search_value_type { @@ -731,9 +895,7 @@ namespace cds { namespace intrusive { void operator()( value_type * v ) { splitlist_node_type * p = static_cast( node_traits::to_node_ptr( v )); - if ( p->is_dummy() ) - dummy_node_disposer()( p ); - else + if ( !p->is_dummy() ) native_disposer()( v ); } }; diff --git a/cds/intrusive/free_list.h b/cds/intrusive/free_list.h index 870ea2a9..113610a9 100644 --- a/cds/intrusive/free_list.h +++ b/cds/intrusive/free_list.h @@ -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 index 00000000..d407b265 --- /dev/null +++ b/cds/intrusive/free_list_selector.h @@ -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 + +#ifdef CDS_DCAS_SUPPORT +# include +#else +# include +#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 diff --git a/cds/intrusive/free_list_tagged.h b/cds/intrusive/free_list_tagged.h index 38eefe98..ab71e8f9 100644 --- a/cds/intrusive/free_list_tagged.h +++ b/cds/intrusive/free_list_tagged.h @@ -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 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 diff --git a/cds/intrusive/options.h b/cds/intrusive/options.h index 17d73092..785f197a 100644 --- a/cds/intrusive/options.h +++ b/cds/intrusive/options.h @@ -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 diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h index 303f7e9e..4b7f8e4c 100644 --- a/cds/intrusive/split_list.h +++ b/cds/intrusive/split_list.h @@ -33,6 +33,7 @@ #include #include +#include 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 m_nBucketCountLog2; ///< log2( current bucket count ) atomics::atomic m_nMaxItemCount; ///< number of items container can hold, before we have to resize item_counter m_ItemCounter; ///< Item counter diff --git a/cds/intrusive/split_list_nogc.h b/cds/intrusive/split_list_nogc.h index a1bb3be7..15446090 100644 --- a/cds/intrusive/split_list_nogc.h +++ b/cds/intrusive/split_list_nogc.h @@ -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 #include +#include 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::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::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 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 m_nBucketCountLog2; ///< log2( current bucket count ) - atomics::atomic 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 - 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( 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::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::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(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::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& 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 + 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(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(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::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 m_nBucketCountLog2; ///< log2( current bucket count ) + atomics::atomic 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 }; diff --git a/cds/intrusive/split_list_rcu.h b/cds/intrusive/split_list_rcu.h index 6f264cce..8ea2078d 100644 --- a/cds/intrusive/split_list_rcu.h +++ b/cds/intrusive/split_list_rcu.h @@ -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 #include +#include 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::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::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 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 m_nBucketCountLog2; ///< log2( current bucket count ) - atomics::atomic 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 - 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( 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::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::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(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::max(), memory_model::memory_order_relaxed ); - } - - template - bool find_( Q& val, Compare cmp, Func f ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type 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& val){ f(item, val.val ); })); - } - - template - bool find_value( Q const& val, Compare cmp ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type 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 - raw_ptr get_( Q const& val, Compare cmp ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type 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 - value_type * extract_( Q const& val, Compare cmp ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type 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 - value_type * extract_with_( Q const& val, Less pred ) - { - CDS_UNUSED( pred ); - return extract_( val, typename wrapped_ordered_list::template make_compare_from_less()); - } - - template - bool erase_( const Q& val, Compare cmp ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type 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 - bool erase_( Q const& val, Compare cmp, Func f ) - { - size_t nHash = hash_value( val ); - split_list::details::search_value_type 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 + 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( 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(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::max(), memory_model::memory_order_relaxed ); + } + + template + bool find_( Q& val, Compare cmp, Func f ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type 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& val){ f(item, val.val ); })); + } + + template + bool find_value( Q const& val, Compare cmp ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type 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 + raw_ptr get_( Q const& val, Compare cmp ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type 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 + value_type * extract_( Q const& val, Compare cmp ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type 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 + value_type * extract_with_( Q const& val, Less pred ) + { + CDS_UNUSED( pred ); + return extract_( val, typename wrapped_ordered_list::template make_compare_from_less()); + } + + template + bool erase_( const Q& val, Compare cmp ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type 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 + bool erase_( Q const& val, Compare cmp, Func f ) + { + size_t nHash = hash_value( val ); + split_list::details::search_value_type 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 m_nBucketCountLog2; ///< log2( current bucket count ) + atomics::atomic 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 diff --git a/cds/opt/options.h b/cds/opt/options.h index f740f024..53e124c5 100644 --- a/cds/opt/options.h +++ b/cds/opt/options.h @@ -688,6 +688,20 @@ namespace opt { //@endcond }; + /// [type-option] Free-list implementation + /** + See \p cds::intrusive::FreeList for free-list interface + */ + template + struct free_list { + //@cond + template struct pack: public Base + { + typedef FreeList free_list; + }; + //@endcond + }; + //@cond // For internal use template @@ -881,7 +895,6 @@ namespace cds { namespace opt { return (result_type) std::rand(); } }; - } // namespace v }} // namespace cds::opt diff --git a/projects/Win/vc14/cds.vcxproj b/projects/Win/vc14/cds.vcxproj index 5fe27e3b..acd0a6c0 100644 --- a/projects/Win/vc14/cds.vcxproj +++ b/projects/Win/vc14/cds.vcxproj @@ -532,6 +532,7 @@ + diff --git a/projects/Win/vc14/cds.vcxproj.filters b/projects/Win/vc14/cds.vcxproj.filters index 3ad7fee3..e59bf011 100644 --- a/projects/Win/vc14/cds.vcxproj.filters +++ b/projects/Win/vc14/cds.vcxproj.filters @@ -1283,5 +1283,8 @@ Header Files\cds\container + + Header Files\cds\intrusive + \ No newline at end of file diff --git a/test/include/cds_test/stat_splitlist_out.h b/test/include/cds_test/stat_splitlist_out.h index 90343491..d08084ec 100644 --- a/test/include/cds_test/stat_splitlist_out.h +++ b/test/include/cds_test/stat_splitlist_out.h @@ -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 diff --git a/test/unit/intrusive-set/intrusive_split_lazy_dhp.cpp b/test/unit/intrusive-set/intrusive_split_lazy_dhp.cpp index aad82073..f1366e6e 100644 --- a/test/unit/intrusive-set/intrusive_split_lazy_dhp.cpp +++ b/test/unit/intrusive-set/intrusive_split_lazy_dhp.cpp @@ -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,13 +25,14 @@ 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 #include +#include #include @@ -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 > + ,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 > + ,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 > + ,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> hook; + typedef cmp 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> hook; + typedef cmp 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> hook; + typedef cmp 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 diff --git a/test/unit/intrusive-set/intrusive_split_lazy_hp.cpp b/test/unit/intrusive-set/intrusive_split_lazy_hp.cpp index eadc0232..f91c4ba6 100644 --- a/test/unit/intrusive-set/intrusive_split_lazy_hp.cpp +++ b/test/unit/intrusive-set/intrusive_split_lazy_hp.cpp @@ -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,13 +25,14 @@ 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 #include +#include #include @@ -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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef base_class::less less; + typedef cmp 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 diff --git a/test/unit/intrusive-set/intrusive_split_lazy_nogc.cpp b/test/unit/intrusive-set/intrusive_split_lazy_nogc.cpp index a832f383..139a814a 100644 --- a/test/unit/intrusive-set/intrusive_split_lazy_nogc.cpp +++ b/test/unit/intrusive-set/intrusive_split_lazy_nogc.cpp @@ -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,13 +25,14 @@ 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 #include +#include #include @@ -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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef base_class::less 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> hook; + typedef cmp 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef base_class::less 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> hook; + typedef cmp 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 diff --git a/test/unit/intrusive-set/intrusive_split_michael_dhp.cpp b/test/unit/intrusive-set/intrusive_split_michael_dhp.cpp index 5d067b79..1a1d665f 100644 --- a/test/unit/intrusive-set/intrusive_split_michael_dhp.cpp +++ b/test/unit/intrusive-set/intrusive_split_michael_dhp.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef cmp 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> hook; + typedef base_class::less 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef base_class::less 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> hook; + typedef base_class::less 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 diff --git a/test/unit/intrusive-set/intrusive_split_michael_hp.cpp b/test/unit/intrusive-set/intrusive_split_michael_hp.cpp index c904eeb3..f08ff04c 100644 --- a/test/unit/intrusive-set/intrusive_split_michael_hp.cpp +++ b/test/unit/intrusive-set/intrusive_split_michael_hp.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef base_class::less 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> hook; + typedef cmp 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef cmp 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> hook; + typedef base_class::less 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 diff --git a/test/unit/intrusive-set/intrusive_split_michael_nogc.cpp b/test/unit/intrusive-set/intrusive_split_michael_nogc.cpp index ed7c0c3b..87f74be3 100644 --- a/test/unit/intrusive-set/intrusive_split_michael_nogc.cpp +++ b/test/unit/intrusive-set/intrusive_split_michael_nogc.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef cmp 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> hook; + typedef base_class::less 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> hook; + typedef base_class::less less; + typedef cmp 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> hook; + typedef cmp 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> hook; + typedef base_class::less 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 diff --git a/test/unit/intrusive-set/test_intrusive_split_lazy_rcu.h b/test/unit/intrusive-set/test_intrusive_split_lazy_rcu.h index c516fba3..c9179297 100644 --- a/test/unit/intrusive-set/test_intrusive_split_lazy_rcu.h +++ b/test/unit/intrusive-set/test_intrusive_split_lazy_rcu.h @@ -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 #include +#include 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> hook; + typedef typename TestFixture::template less less; + typedef typename TestFixture::template cmp 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> hook; + typedef typename TestFixture::template less 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> hook; + typedef typename TestFixture::template cmp 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> hook; + typedef typename TestFixture::template less less; + typedef typename TestFixture::template cmp 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> hook; + typedef typename TestFixture::template less less; + typedef typename TestFixture::template cmp 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> hook; + typedef typename TestFixture::template cmp 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 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 ); diff --git a/test/unit/intrusive-set/test_intrusive_split_michael_rcu.h b/test/unit/intrusive-set/test_intrusive_split_michael_rcu.h index c45deb70..2a020a27 100644 --- a/test/unit/intrusive-set/test_intrusive_split_michael_rcu.h +++ b/test/unit/intrusive-set/test_intrusive_split_michael_rcu.h @@ -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 #include +#include 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> hook; + typedef typename TestFixture::template less less; + typedef typename TestFixture::template cmp 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> hook; + typedef typename TestFixture::template cmp 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> hook; + typedef typename TestFixture::template less 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> hook; + typedef typename TestFixture::template less less; + typedef typename TestFixture::template cmp 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> hook; + typedef typename TestFixture::template cmp 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> hook; + typedef typename TestFixture::template less 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 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 ); diff --git a/test/unit/map/split_lazy_dhp.cpp b/test/unit/map/split_lazy_dhp.cpp index 70a31243..62697e4d 100644 --- a/test/unit/map/split_lazy_dhp.cpp +++ b/test/unit/map/split_lazy_dhp.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/map/split_lazy_hp.cpp b/test/unit/map/split_lazy_hp.cpp index dc76e662..d4f8d6c5 100644 --- a/test/unit/map/split_lazy_hp.cpp +++ b/test/unit/map/split_lazy_hp.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/map/split_lazy_nogc.cpp b/test/unit/map/split_lazy_nogc.cpp index a8b89980..881e8814 100644 --- a/test/unit/map/split_lazy_nogc.cpp +++ b/test/unit/map/split_lazy_nogc.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/map/split_michael_dhp.cpp b/test/unit/map/split_michael_dhp.cpp index 7627d2c5..0d0fcbdc 100644 --- a/test/unit/map/split_michael_dhp.cpp +++ b/test/unit/map/split_michael_dhp.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/map/split_michael_hp.cpp b/test/unit/map/split_michael_hp.cpp index 16adc938..3384bbc6 100644 --- a/test/unit/map/split_michael_hp.cpp +++ b/test/unit/map/split_michael_hp.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/map/split_michael_nogc.cpp b/test/unit/map/split_michael_nogc.cpp index dfe9fc97..c55ab817 100644 --- a/test/unit/map/split_michael_nogc.cpp +++ b/test/unit/map/split_michael_nogc.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/map/test_split_lazy_rcu.h b/test/unit/map/test_split_lazy_rcu.h index 0305fa57..050da438 100644 --- a/test/unit/map/test_split_lazy_rcu.h +++ b/test/unit/map/test_split_lazy_rcu.h @@ -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 #include +#include 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 ); diff --git a/test/unit/map/test_split_michael_rcu.h b/test/unit/map/test_split_michael_rcu.h index 47713fe4..c2b12533 100644 --- a/test/unit/map/test_split_michael_rcu.h +++ b/test/unit/map/test_split_michael_rcu.h @@ -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 #include +#include 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 ); diff --git a/test/unit/set/split_lazy_dhp.cpp b/test/unit/set/split_lazy_dhp.cpp index 3054096c..d418ae4b 100644 --- a/test/unit/set/split_lazy_dhp.cpp +++ b/test/unit/set/split_lazy_dhp.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/set/split_lazy_hp.cpp b/test/unit/set/split_lazy_hp.cpp index 1b387491..9d9829f5 100644 --- a/test/unit/set/split_lazy_hp.cpp +++ b/test/unit/set/split_lazy_hp.cpp @@ -32,6 +32,7 @@ #include #include +#include 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 diff --git a/test/unit/set/split_lazy_nogc.cpp b/test/unit/set/split_lazy_nogc.cpp index afa95ab8..4317e323 100644 --- a/test/unit/set/split_lazy_nogc.cpp +++ b/test/unit/set/split_lazy_nogc.cpp @@ -25,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/set/split_michael_dhp.cpp b/test/unit/set/split_michael_dhp.cpp index 31b8dd94..41a950e7 100644 --- a/test/unit/set/split_michael_dhp.cpp +++ b/test/unit/set/split_michael_dhp.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/set/split_michael_hp.cpp b/test/unit/set/split_michael_hp.cpp index 0b779e2f..f9a88d6f 100644 --- a/test/unit/set/split_michael_hp.cpp +++ b/test/unit/set/split_michael_hp.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/set/split_michael_nogc.cpp b/test/unit/set/split_michael_nogc.cpp index 50af1e81..aac27641 100644 --- a/test/unit/set/split_michael_nogc.cpp +++ b/test/unit/set/split_michael_nogc.cpp @@ -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,13 +25,14 @@ 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 #include +#include 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 diff --git a/test/unit/set/test_split_lazy_rcu.h b/test/unit/set/test_split_lazy_rcu.h index 3eb6ddfe..f5a2ba6c 100644 --- a/test/unit/set/test_split_lazy_rcu.h +++ b/test/unit/set/test_split_lazy_rcu.h @@ -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 #include +#include 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 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 ); diff --git a/test/unit/set/test_split_michael_rcu.h b/test/unit/set/test_split_michael_rcu.h index b84bb0a3..44ee68b0 100644 --- a/test/unit/set/test_split_michael_rcu.h +++ b/test/unit/set/test_split_michael_rcu.h @@ -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 #include +#include 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 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 );