/** @defgroup cds_intrusive_list List
@ingroup cds_intrusive_containers
*/
+ /** @defgroup cds_intrusive_freelist Free-list
+ @ingroup cds_intrusive_containers
+ */
//@cond
template <typename List>
//@endcond
public:
- typedef GC gc; ///< Garbage collector
- typedef Node node_type; ///< Bucket node type
- typedef atomics::atomic<node_type *> table_entry; ///< Table entry type
+ typedef GC gc; ///< Garbage collector
+ typedef Node node_type; ///< Bucket node type
typedef typename options::allocator allocator; ///< allocator
+ typedef typename options::memory_model memory_model; ///< Memory model for atomic operations
+ typedef typename options::free_list free_list; ///< Free-list
- /// 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;
+ /// Auxiliary node type
+ struct aux_node_type: public node_type, public free_list::node
+ {};
- /// Free-list
- typedef typename options::free_list free_list;
+ typedef atomics::atomic<aux_node_type *> table_entry; ///< Table entry type
+ typedef cds::details::Allocator< table_entry, allocator > bucket_table_allocator; ///< Bucket table allocator
protected:
//@cond
- struct aux_node_type: public node_type, public free_list::node
- {};
-
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
}
/// Returns head node of bucket \p nBucket
- node_type * bucket( size_t nBucket ) const
+ aux_node_type * bucket( size_t nBucket ) const
{
assert( nBucket < capacity() );
return m_Table[ nBucket ].load(memory_model::memory_order_acquire);
}
/// Set \p pNode as a head of bucket \p nBucket
- void bucket( size_t nBucket, node_type * pNode )
+ void bucket( size_t nBucket, aux_node_type * pNode )
{
assert( nBucket < capacity() );
assert( bucket( nBucket ) == nullptr );
}
/// Allocates auxiliary node; can return \p nullptr if the table exhausted
- node_type* alloc_aux_node()
+ aux_node_type* alloc_aux_node()
{
if ( m_nAuxNodeAllocated.load( memory_model::memory_order_relaxed ) < capacity() ) {
// alloc next free node from m_auxNode
}
/// Places node type to free-list
- void free_aux_node( node_type* p )
+ void free_aux_node( aux_node_type* p )
{
m_freeList.put( static_cast<aux_node_type*>( p ));
}
/// Free-list
typedef typename options::free_list free_list;
- protected:
- //@cond
- typedef atomics::atomic<node_type *> table_entry; ///< Table entry type
- typedef atomics::atomic<table_entry *> segment_type; ///< Bucket table segment type
-
+ /// Auxiliary node type
class aux_node_type: public node_type, public free_list::node
{};
+ protected:
+ //@cond
+ typedef atomics::atomic<aux_node_type *> table_entry; ///< Table entry type
+ typedef atomics::atomic<table_entry *> segment_type; ///< Bucket table segment type
+
struct aux_node_segment {
atomics::atomic< size_t > aux_node_count; // how many aux nodes allocated from the segment
aux_node_segment* next_segment;
}
/// Returns head node of the bucket \p nBucket
- node_type * bucket( size_t nBucket ) const
+ aux_node_type * bucket( size_t nBucket ) const
{
size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
assert( nSegment < m_metrics.nSegmentCount );
}
/// Set \p pNode as a head of bucket \p nBucket
- void bucket( size_t nBucket, node_type * pNode )
+ void bucket( size_t nBucket, aux_node_type * pNode )
{
size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
assert( nSegment < m_metrics.nSegmentCount );
}
/// Allocates auxiliary node; can return \p nullptr if the table exhausted
- node_type* alloc_aux_node()
+ aux_node_type* alloc_aux_node()
{
for ( ;; ) {
aux_node_segment* aux_segment = m_auxNodeList.load( memory_model::memory_order_relaxed );
}
/// Places auxiliary node type to free-list
- void free_aux_node( node_type* p )
+ void free_aux_node( aux_node_type* p )
{
m_freeList.put( static_cast<aux_node_type*>( p ));
}
namespace cds { namespace intrusive {
/// Lock-free free list
- /** @ingroup cds_intrusive_helper
+ /** @ingroup cds_intrusive_freelist
Free list is a helper class intended for reusing objects instead of freeing them completely;
this avoids the overhead of \p malloc(), and also avoids its worst-case behavior of taking an operating system lock.
--- /dev/null
+/*
+ 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_CACHED_H
+#define CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H
+
+#include <cds/algo/atomic.h>
+#include <cds/opt/options.h>
+#include <cds/user_setup/cache_line.h>
+#include <cds/details/type_padding.h>
+
+#include <thread>
+#include <functional>
+
+namespace cds { namespace intrusive {
+
+ /// Cached free list
+ /** @ingroup cds_intrusive_freelist
+
+ The class that is a wrapper over other \p FreeList contains a small cache of free elements.
+ Before placing a new item into underlying \p FreeList the cached free-list tryes
+ to put that item into the cache if its corresponding slot is empty. The slot is calculated by
+ current thread id:
+ \code
+ int slot = std::hash<std::thread::id>()( std::this_thread::get_id() ) & (CacheSize - 1);
+ \endcode
+
+ When getting the free-list checks the corresponding cache slot. If it is not empty, its
+ contents is returned.
+
+ In some cases such simple algorithm significantly reduces \p FreeList contention.
+
+ Template parameters:
+ - \p FreeList - a free-list implementation: \p FreeList, \p TaggedFreeList
+ - \p CacheSize - size of cache, a small power-of-two number, default is 16
+ - \p Padding - padding of cache elements for solving false sharing, default is \p cds::c_nCacheLineSize
+ */
+ template <typename FreeList, size_t CacheSize = 16, unsigned Padding = cds::c_nCacheLineSize >
+ class CachedFreeList
+ {
+ public:
+ typedef FreeList free_list_type; ///< Undelying free-list type
+ typedef typename free_list_type::node node; ///< Free-list node
+
+ static size_t const c_cache_size = CacheSize; ///< Cache size
+ static unsigned const c_padding = Padding; ///< Cache element padding
+
+ static_assert( c_cache_size >= 4, "Cache size is too small" );
+ static_assert( (c_cache_size & (c_cache_size - 1)) == 0, "CacheSize must be power of two" );
+ static_assert( (c_padding & (c_padding - 1)) == 0, "Padding must be power-of-two");
+
+ public:
+ /// Creates empty free list
+ CachedFreeList()
+ {
+ for ( auto& i: m_cache )
+ i.store( nullptr, atomics::memory_order_relaxed );
+ }
+
+ /// Destroys the free list. Free-list must be empty.
+ /**
+ @warning dtor does not free elements of the list.
+ To free elements you should manually call \p clear() with an appropriate disposer.
+ */
+ ~CachedFreeList()
+ {
+ assert( empty());
+ }
+
+ /// Puts \p pNode to the free list
+ void put( node* pNode )
+ {
+ // try to put into free cell of cache
+ node* expect = nullptr;
+ if ( m_cache[ get_hash() ].compare_exchange_weak( expect, pNode, atomics::memory_order_release, atomics::memory_order_relaxed ))
+ return;
+
+ // cache cell is not empty - use free-list
+ m_freeList.put( pNode );
+ }
+
+ /// Gets a node from the free list. If the list is empty, returns \p nullptr
+ node * get()
+ {
+ // try get from cache
+ atomics::atomic<node*>& cell = m_cache[ get_hash() ];
+ node* p = cell.load( atomics::memory_order_relaxed );
+ if ( p && cell.compare_exchange_weak( p, nullptr, atomics::memory_order_acquire, atomics::memory_order_relaxed ))
+ return p;
+
+ // try read from free-list
+ p = m_freeList.get();
+ if ( p )
+ return p;
+
+ // iterate the cache
+ for ( auto& cell : m_cache ) {
+ p = cell.load( atomics::memory_order_relaxed );
+ if ( p && cell.compare_exchange_weak( p, nullptr, atomics::memory_order_acquire, atomics::memory_order_relaxed ))
+ return p;
+ }
+
+ return m_freeList.get();
+ }
+
+ /// Checks whether the free list is empty
+ bool empty() const
+ {
+ if ( !m_freeList.empty() )
+ return false;
+
+ for ( auto& cell : m_cache ) {
+ node* p = cell.load( atomics::memory_order_relaxed );
+ if ( p )
+ return false;
+ }
+
+ return true;
+ }
+
+ /// Clears the free list (not atomic)
+ /**
+ For each element \p disp disposer is called to free memory.
+ The \p Disposer interface:
+ \code
+ struct disposer
+ {
+ void operator()( FreeList::node * node );
+ };
+ \endcode
+
+ This method must be explicitly called before the free list destructor.
+ */
+ template <typename Disposer>
+ void clear( Disposer disp )
+ {
+ m_freeList.clear( disp );
+ for ( auto& cell : m_cache ) {
+ node* p = cell.load( atomics::memory_order_relaxed );
+ if ( p ) {
+ disp( p );
+ cell.store( nullptr, atomics::memory_order_relaxed );
+ }
+ }
+ }
+
+ private:
+ //@cond
+ size_t get_hash()
+ {
+ return std::hash<std::thread::id>()( std::this_thread::get_id() ) & (c_cache_size - 1);
+ }
+ //@endcond
+ private:
+ //@cond
+ typedef typename cds::details::type_padding< atomics::atomic<node*>, c_padding >::type array_item;
+ array_item m_cache[ c_cache_size ];
+ free_list_type m_freeList;
+ //@endcond
+ };
+
+}} // namespace cds::intrusive
+//@endcond
+
+#endif // CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H
Source code repo: http://github.com/khizmax/libcds/
Download: http://sourceforge.net/projects/libcds/files/
-
+
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef CDSLIB_INTRUSIVE_FREE_LIST_SELECTOR_H
namespace cds { namespace intrusive {
/// Lock-free free list based on tagged pointers (required double-width CAS)
- /** @ingroup cds_intrusive_helper
+ /** @ingroup cds_intrusive_freelist
+
This variant of \p FreeList is intended for processor architectures that support double-width CAS.
It uses <a href="https://en.wikipedia.org/wiki/Tagged_pointer">tagged pointer</a> technique to solve ABA problem.
//@cond
typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
typedef split_list::node<list_node_type> node_type; ///< split-list node type
- typedef node_type aux_node_type; ///< dummy node type
/// Split-list node traits
/**
typedef typename split_list::details::bucket_table_selector<
traits::dynamic_bucket_table
, gc
- , aux_node_type
+ , node_type
, opt::allocator< typename traits::allocator >
, opt::memory_model< memory_model >
, opt::free_list< typename traits::free_list >
>::type bucket_table;
+
+ typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
//@endcond
protected:
typedef typename base_class::auxiliary_head bucket_head_type;
public:
- bool insert_at( aux_node_type * pHead, value_type& val )
+ bool insert_at( aux_node_type* pHead, value_type& val )
{
assert( pHead != nullptr );
bucket_head_type h(pHead);
"cds::atomicity::empty_item_counter is not allowed as a item counter");
protected:
+ //@cond
typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
typedef split_list::node<list_node_type> node_type; ///< split-list node type
- typedef node_type aux_node_type; ///< dummy node type
/// Split-list node traits
/**
*/
typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
- //@cond
/// Bucket table implementation
typedef typename split_list::details::bucket_table_selector<
traits::dynamic_bucket_table
, gc
- , aux_node_type
+ , node_type
, opt::allocator< typename traits::allocator >
, opt::memory_model< memory_model >
>::type bucket_table;
+ typedef typename bucket_table::aux_node_type aux_node_type; ///< dummy node type
+
typedef typename ordered_list::iterator list_iterator;
typedef typename ordered_list::const_iterator list_const_iterator;
//@endcond
protected:
//@cond
- typedef typename cds::details::type_padding< bucket_table, traits::padding >::type padded_bucket_table;
+ static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
+
+ typedef typename cds::details::type_padding< bucket_table, c_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;
+ typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
padded_ordered_list m_List; ///< Ordered list containing split-list items
atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
"cds::atomicity::empty_item_counter is not allowed as a item counter");
protected:
+ //@cond
typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
typedef split_list::node<list_node_type> node_type; ///< split-list node type
- typedef node_type aux_node_type; ///< dummy node type
/// Split-list node traits
/**
*/
typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
- //@cond
/// Bucket table implementation
typedef typename split_list::details::bucket_table_selector<
traits::dynamic_bucket_table
, gc
- , aux_node_type
+ , node_type
, opt::allocator< typename traits::allocator >
, opt::memory_model< memory_model >
>::type bucket_table;
+ typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
+
//@endcond
protected:
protected:
//@cond
- typedef typename cds::details::type_padding< bucket_table, traits::padding >::type padded_bucket_table;
+ static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
+
+ typedef typename cds::details::type_padding< bucket_table, c_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;
+ typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
padded_ordered_list m_List; ///< Ordered list containing split-list items
atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
{408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239}\r
EndProjectSection\r
EndProject\r
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-freelist", "stress-freelist.vcxproj", "{79A6845E-85BF-4000-94FF-9DF2473460D4}"\r
+ ProjectSection(ProjectDependencies) = postProject\r
+ {A34CED07-A442-4FA1-81C4-F8B9CD3C832B} = {A34CED07-A442-4FA1-81C4-F8B9CD3C832B}\r
+ {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239}\r
+ EndProjectSection\r
+EndProject\r
Global\r
GlobalSection(SolutionConfigurationPlatforms) = preSolution\r
Debug|Win32 = Debug|Win32\r
{31952FA8-A303-4A0B-94C4-ABA5A8A6DBCE}.Release|Win32.Build.0 = Release|Win32\r
{31952FA8-A303-4A0B-94C4-ABA5A8A6DBCE}.Release|x64.ActiveCfg = Release|x64\r
{31952FA8-A303-4A0B-94C4-ABA5A8A6DBCE}.Release|x64.Build.0 = Release|x64\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.Debug|Win32.ActiveCfg = Debug|Win32\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.Debug|Win32.Build.0 = Debug|Win32\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.Debug|x64.ActiveCfg = Debug|x64\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.Debug|x64.Build.0 = Debug|x64\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.DebugVLD|Win32.ActiveCfg = DebugVLD|Win32\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.DebugVLD|Win32.Build.0 = DebugVLD|Win32\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.DebugVLD|x64.ActiveCfg = DebugVLD|x64\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.DebugVLD|x64.Build.0 = DebugVLD|x64\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.Release|Win32.ActiveCfg = Release|Win32\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.Release|Win32.Build.0 = Release|Win32\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.Release|x64.ActiveCfg = Release|x64\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4}.Release|x64.Build.0 = Release|x64\r
EndGlobalSection\r
GlobalSection(SolutionProperties) = preSolution\r
HideSolutionNode = FALSE\r
{1BB746AC-7856-4E59-9430-51177621DC35} = {7D3EE35B-185D-40B5-88C2-7F9933426978}\r
{24DF3B87-387E-4EFC-BDE0-8DAD279FE19A} = {7D3EE35B-185D-40B5-88C2-7F9933426978}\r
{31952FA8-A303-4A0B-94C4-ABA5A8A6DBCE} = {0D83E8C7-97D1-4BA1-928A-6846E7089652}\r
+ {79A6845E-85BF-4000-94FF-9DF2473460D4} = {10E1FAF2-904D-405E-8AB5-6878A1B03346}\r
EndGlobalSection\r
GlobalSection(DPCodeReviewSolutionGUID) = preSolution\r
DPCodeReviewSolutionGUID = {00000000-0000-0000-0000-000000000000}\r
<ClInclude Include="..\..\..\cds\intrusive\ellen_bintree_hp.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\ellen_bintree_rcu.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\free_list.h" />\r
+ <ClInclude Include="..\..\..\cds\intrusive\free_list_cached.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\free_list_selector.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\free_list_tagged.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\impl\ellen_bintree.h" />\r
<Filter Include="Header Files\cds\intrusive">\r
<UniqueIdentifier>{7226715d-6777-4c01-8e66-83b3885c00c1}</UniqueIdentifier>\r
</Filter>\r
- <Filter Include="Resource Files">\r
- <UniqueIdentifier>{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}</UniqueIdentifier>\r
- <Extensions>rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx</Extensions>\r
- </Filter>\r
<Filter Include="Header Files\cds\compiler\clang">\r
<UniqueIdentifier>{ae97048d-bd62-4ff2-be28-3c84338e7186}</UniqueIdentifier>\r
</Filter>\r
<ClInclude Include="..\..\..\cds\intrusive\free_list_selector.h">\r
<Filter>Header Files\cds\intrusive</Filter>\r
</ClInclude>\r
+ <ClInclude Include="..\..\..\cds\intrusive\free_list_cached.h">\r
+ <Filter>Header Files\cds\intrusive</Filter>\r
+ </ClInclude>\r
</ItemGroup>\r
</Project>
\ No newline at end of file
--- /dev/null
+<?xml version="1.0" encoding="utf-8"?>
+<Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+ <ItemGroup Label="ProjectConfigurations">
+ <ProjectConfiguration Include="DebugVLD|Win32">
+ <Configuration>DebugVLD</Configuration>
+ <Platform>Win32</Platform>
+ </ProjectConfiguration>
+ <ProjectConfiguration Include="DebugVLD|x64">
+ <Configuration>DebugVLD</Configuration>
+ <Platform>x64</Platform>
+ </ProjectConfiguration>
+ <ProjectConfiguration Include="Debug|Win32">
+ <Configuration>Debug</Configuration>
+ <Platform>Win32</Platform>
+ </ProjectConfiguration>
+ <ProjectConfiguration Include="Release|Win32">
+ <Configuration>Release</Configuration>
+ <Platform>Win32</Platform>
+ </ProjectConfiguration>
+ <ProjectConfiguration Include="Debug|x64">
+ <Configuration>Debug</Configuration>
+ <Platform>x64</Platform>
+ </ProjectConfiguration>
+ <ProjectConfiguration Include="Release|x64">
+ <Configuration>Release</Configuration>
+ <Platform>x64</Platform>
+ </ProjectConfiguration>
+ </ItemGroup>
+ <ItemGroup>
+ <ClCompile Include="..\..\..\test\stress\freelist\put_get.cpp" />
+ <ClCompile Include="..\..\..\test\stress\freelist\put_get_single.cpp" />
+ <ClCompile Include="..\..\..\test\stress\main.cpp" />
+ </ItemGroup>
+ <PropertyGroup Label="Globals">
+ <ProjectGuid>{79A6845E-85BF-4000-94FF-9DF2473460D4}</ProjectGuid>
+ <Keyword>Win32Proj</Keyword>
+ <RootNamespace>stress_freelist</RootNamespace>
+ <WindowsTargetPlatformVersion>8.1</WindowsTargetPlatformVersion>
+ <ProjectName>stress-freelist</ProjectName>
+ </PropertyGroup>
+ <Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" />
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'" Label="Configuration">
+ <ConfigurationType>Application</ConfigurationType>
+ <UseDebugLibraries>true</UseDebugLibraries>
+ <PlatformToolset>v140</PlatformToolset>
+ <CharacterSet>Unicode</CharacterSet>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'" Label="Configuration">
+ <ConfigurationType>Application</ConfigurationType>
+ <UseDebugLibraries>true</UseDebugLibraries>
+ <PlatformToolset>v140</PlatformToolset>
+ <CharacterSet>Unicode</CharacterSet>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'" Label="Configuration">
+ <ConfigurationType>Application</ConfigurationType>
+ <UseDebugLibraries>false</UseDebugLibraries>
+ <PlatformToolset>v140</PlatformToolset>
+ <WholeProgramOptimization>true</WholeProgramOptimization>
+ <CharacterSet>Unicode</CharacterSet>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'" Label="Configuration">
+ <ConfigurationType>Application</ConfigurationType>
+ <UseDebugLibraries>true</UseDebugLibraries>
+ <PlatformToolset>v140</PlatformToolset>
+ <CharacterSet>Unicode</CharacterSet>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'" Label="Configuration">
+ <ConfigurationType>Application</ConfigurationType>
+ <UseDebugLibraries>true</UseDebugLibraries>
+ <PlatformToolset>v140</PlatformToolset>
+ <CharacterSet>Unicode</CharacterSet>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'" Label="Configuration">
+ <ConfigurationType>Application</ConfigurationType>
+ <UseDebugLibraries>false</UseDebugLibraries>
+ <PlatformToolset>v140</PlatformToolset>
+ <WholeProgramOptimization>true</WholeProgramOptimization>
+ <CharacterSet>Unicode</CharacterSet>
+ </PropertyGroup>
+ <Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" />
+ <ImportGroup Label="ExtensionSettings">
+ </ImportGroup>
+ <ImportGroup Label="Shared">
+ </ImportGroup>
+ <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+ <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+ </ImportGroup>
+ <ImportGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'" Label="PropertySheets">
+ <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+ </ImportGroup>
+ <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+ <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+ </ImportGroup>
+ <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+ <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+ </ImportGroup>
+ <ImportGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'" Label="PropertySheets">
+ <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+ </ImportGroup>
+ <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+ <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+ </ImportGroup>
+ <PropertyGroup Label="UserMacros" />
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+ <LinkIncremental>true</LinkIncremental>
+ <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+ <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+ <TargetName>$(ProjectName)_d</TargetName>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'">
+ <LinkIncremental>true</LinkIncremental>
+ <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+ <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+ <TargetName>$(ProjectName)_d</TargetName>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+ <LinkIncremental>true</LinkIncremental>
+ <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+ <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+ <TargetName>$(ProjectName)_d</TargetName>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'">
+ <LinkIncremental>true</LinkIncremental>
+ <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+ <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+ <TargetName>$(ProjectName)_d</TargetName>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+ <LinkIncremental>false</LinkIncremental>
+ <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\</OutDir>
+ <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+ </PropertyGroup>
+ <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+ <LinkIncremental>false</LinkIncremental>
+ <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\</OutDir>
+ <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+ </PropertyGroup>
+ <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+ <ClCompile>
+ <PrecompiledHeader>NotUsing</PrecompiledHeader>
+ <WarningLevel>Level3</WarningLevel>
+ <Optimization>Disabled</Optimization>
+ <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+ <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+ </ClCompile>
+ <Link>
+ <SubSystem>Console</SubSystem>
+ <GenerateDebugInformation>true</GenerateDebugInformation>
+ <AdditionalLibraryDirectories>$(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+ <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+ </Link>
+ </ItemDefinitionGroup>
+ <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'">
+ <ClCompile>
+ <PrecompiledHeader>NotUsing</PrecompiledHeader>
+ <WarningLevel>Level3</WarningLevel>
+ <Optimization>Disabled</Optimization>
+ <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+ <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+ </ClCompile>
+ <Link>
+ <SubSystem>Console</SubSystem>
+ <GenerateDebugInformation>true</GenerateDebugInformation>
+ <AdditionalLibraryDirectories>$(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+ <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+ </Link>
+ </ItemDefinitionGroup>
+ <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+ <ClCompile>
+ <PrecompiledHeader>NotUsing</PrecompiledHeader>
+ <WarningLevel>Level3</WarningLevel>
+ <Optimization>Disabled</Optimization>
+ <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+ <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+ </ClCompile>
+ <Link>
+ <SubSystem>Console</SubSystem>
+ <GenerateDebugInformation>true</GenerateDebugInformation>
+ <AdditionalLibraryDirectories>$(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+ <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+ </Link>
+ </ItemDefinitionGroup>
+ <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'">
+ <ClCompile>
+ <PrecompiledHeader>NotUsing</PrecompiledHeader>
+ <WarningLevel>Level3</WarningLevel>
+ <Optimization>Disabled</Optimization>
+ <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+ <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+ </ClCompile>
+ <Link>
+ <SubSystem>Console</SubSystem>
+ <GenerateDebugInformation>true</GenerateDebugInformation>
+ <AdditionalLibraryDirectories>$(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+ <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+ </Link>
+ </ItemDefinitionGroup>
+ <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+ <ClCompile>
+ <WarningLevel>Level3</WarningLevel>
+ <PrecompiledHeader>NotUsing</PrecompiledHeader>
+ <Optimization>MaxSpeed</Optimization>
+ <FunctionLevelLinking>true</FunctionLevelLinking>
+ <IntrinsicFunctions>true</IntrinsicFunctions>
+ <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+ <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+ </ClCompile>
+ <Link>
+ <SubSystem>Console</SubSystem>
+ <EnableCOMDATFolding>true</EnableCOMDATFolding>
+ <OptimizeReferences>true</OptimizeReferences>
+ <GenerateDebugInformation>true</GenerateDebugInformation>
+ <AdditionalLibraryDirectories>$(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+ <AdditionalDependencies>gtest.lib;stress-framework.lib;%(AdditionalDependencies)</AdditionalDependencies>
+ </Link>
+ </ItemDefinitionGroup>
+ <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+ <ClCompile>
+ <WarningLevel>Level3</WarningLevel>
+ <PrecompiledHeader>NotUsing</PrecompiledHeader>
+ <Optimization>MaxSpeed</Optimization>
+ <FunctionLevelLinking>true</FunctionLevelLinking>
+ <IntrinsicFunctions>true</IntrinsicFunctions>
+ <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+ <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+ </ClCompile>
+ <Link>
+ <SubSystem>Console</SubSystem>
+ <EnableCOMDATFolding>true</EnableCOMDATFolding>
+ <OptimizeReferences>true</OptimizeReferences>
+ <GenerateDebugInformation>true</GenerateDebugInformation>
+ <AdditionalLibraryDirectories>$(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+ <AdditionalDependencies>gtest.lib;stress-framework.lib;%(AdditionalDependencies)</AdditionalDependencies>
+ </Link>
+ </ItemDefinitionGroup>
+ <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
+ <ImportGroup Label="ExtensionTargets">
+ </ImportGroup>
+</Project>
\ No newline at end of file
--- /dev/null
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+ <ItemGroup>
+ <Filter Include="Source Files">
+ <UniqueIdentifier>{4FC737F1-C7A5-4376-A066-2A32D752A2FF}</UniqueIdentifier>
+ <Extensions>cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx</Extensions>
+ </Filter>
+ <Filter Include="Header Files">
+ <UniqueIdentifier>{93995380-89BD-4b04-88EB-625FBE52EBFB}</UniqueIdentifier>
+ <Extensions>h;hh;hpp;hxx;hm;inl;inc;xsd</Extensions>
+ </Filter>
+ </ItemGroup>
+ <ItemGroup>
+ <ClCompile Include="..\..\..\test\stress\main.cpp">
+ <Filter>Source Files</Filter>
+ </ClCompile>
+ <ClCompile Include="..\..\..\test\stress\freelist\put_get.cpp">
+ <Filter>Source Files</Filter>
+ </ClCompile>
+ <ClCompile Include="..\..\..\test\stress\freelist\put_get_single.cpp">
+ <Filter>Source Files</Filter>
+ </ClCompile>
+ </ItemGroup>
+</Project>
\ No newline at end of file
<UniqueIdentifier>{93995380-89BD-4b04-88EB-625FBE52EBFB}</UniqueIdentifier>\r
<Extensions>h;hh;hpp;hxx;hm;inl;inc;xsd</Extensions>\r
</Filter>\r
- <Filter Include="Resource Files">\r
- <UniqueIdentifier>{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}</UniqueIdentifier>\r
- <Extensions>rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms</Extensions>\r
- </Filter>\r
</ItemGroup>\r
<ItemGroup>\r
<ClCompile Include="..\..\..\test\stress\main.cpp">\r
${CMAKE_CURRENT_SOURCE_DIR}
)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/freelist)
add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/map)
add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/pqueue)
add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/queue)
add_custom_target( stress-all
DEPENDS
+ stress-freelist
stress-map
stress-pqueue
stress-queue
# *** FeldmanHashMap properties\r
FeldmanMapHeadBits=8\r
FeldmanMapArrayBits=4\r
+\r
+[free_list]\r
+ThreadCount=4\r
+PassCount=100000
\ No newline at end of file
# *** FeldmanHashMap properties\r
FeldmanMapHeadBits=8\r
FeldmanMapArrayBits=4\r
+\r
+[free_list]\r
+ThreadCount=4\r
+PassCount=1000000
\ No newline at end of file
# *** FeldmanHashMap properties\r
FeldmanMapHeadBits=10\r
FeldmanMapArrayBits=4\r
+\r
+[free_list]\r
+ThreadCount=4\r
+PassCount=1000000
\ No newline at end of file
--- /dev/null
+set(PACKAGE_NAME stress-freelist)
+
+set(CDSSTRESS_FREELIST_SOURCES
+ ../main.cpp
+ put_get.cpp
+ put_get_single.cpp
+)
+
+include_directories(
+ ${CMAKE_CURRENT_SOURCE_DIR}
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_FREELIST_SOURCES} $<TARGET_OBJECTS:${CDSSTRESS_FRAMEWORK_LIBRARY}>)
+target_link_libraries(${PACKAGE_NAME}
+ ${CDS_SHARED_LIBRARY}
+ ${GTEST_LIBRARY}
+ ${Boost_THREAD_LIBRARY}
+ ${Boost_SYSTEM_LIBRARY}
+ ${CMAKE_THREAD_LIBS_INIT}
+)
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
\ No newline at end of file
--- /dev/null
+/*
+ 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.
+*/
+
+#include <cds_test/stress_test.h>
+
+#include <cds/intrusive/free_list.h>
+#include <cds/intrusive/free_list_cached.h>
+#include <cds/intrusive/free_list_tagged.h>
+
+namespace {
+ class put_get: public cds_test::stress_fixture
+ {
+ protected:
+ static size_t s_nThreadCount;
+ static size_t s_nPassCount;
+ static size_t const c_nArraySize = 100;
+
+ template <typename FreeList >
+ struct value_type: public FreeList::node
+ {
+ size_t counter;
+
+ value_type()
+ : counter(0)
+ {}
+ };
+
+ template <class FreeList>
+ class Worker: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ public:
+ FreeList& m_FreeList;
+ size_t m_nSuccess = 0;
+
+ public:
+ Worker( cds_test::thread_pool& pool, FreeList& s )
+ : base_class( pool )
+ , m_FreeList( s )
+ {}
+
+ Worker( Worker& src )
+ : base_class( src )
+ , m_FreeList( src.m_FreeList )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Worker( *this );
+ }
+
+ virtual void test()
+ {
+ typedef value_type<FreeList> item_type;
+ item_type* arr[ c_nArraySize ];
+
+ for ( size_t pass = 0; pass < s_nPassCount; ++pass ) {
+ size_t n = 0;
+ item_type* p;
+
+ while ( (p = static_cast<item_type*>( m_FreeList.get())) != nullptr ) {
+ p->counter++;
+ arr[n] = p;
+ ++m_nSuccess;
+ ++n;
+ }
+
+ for ( size_t i = 0; i < n; ++i )
+ m_FreeList.put( arr[i] );
+ }
+ }
+ };
+
+ public:
+ static void SetUpTestCase()
+ {
+ cds_test::config const& cfg = get_config( "free_list" );
+
+ s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
+ s_nPassCount = cfg.get_size_t( "PassCount", s_nPassCount );
+
+ if ( s_nThreadCount == 0 )
+ s_nThreadCount = 1;
+ if ( s_nPassCount == 0 )
+ s_nPassCount = 1000;
+ }
+ //static void TearDownTestCase();
+
+ protected:
+
+ template <typename FreeList>
+ void test( FreeList& list )
+ {
+ cds_test::thread_pool& pool = get_pool();
+
+ value_type<FreeList> arr[c_nArraySize];
+
+ for ( auto& i : arr )
+ list.put( &i );
+
+ pool.add( new Worker<FreeList>( pool, list ), s_nThreadCount );
+
+ propout() << std::make_pair( "work_thread", s_nThreadCount )
+ << std::make_pair( "pass_count", s_nPassCount );
+
+ std::chrono::milliseconds duration = pool.run();
+
+ propout() << std::make_pair( "duration", duration );
+
+ // analyze result
+ size_t nTotal = 0;
+ for ( auto const& i : arr )
+ nTotal += i.counter;
+
+ size_t nSuccess = 0;
+ for ( size_t threadNo = 0; threadNo < pool.size(); ++threadNo )
+ nSuccess += static_cast<Worker<FreeList>&>( pool.get( threadNo )).m_nSuccess;
+
+ EXPECT_EQ( nSuccess, nTotal );
+
+ list.clear( []( typename FreeList::node* ) {} );
+ }
+ };
+
+ size_t put_get::s_nThreadCount = 4;
+ size_t put_get::s_nPassCount = 100000;
+
+#define CDSSTRESS_FREELIST_F( name, freelist_type ) \
+ TEST_F( put_get, name ) \
+ { \
+ freelist_type fl; \
+ test( fl ); \
+ }
+
+ CDSSTRESS_FREELIST_F( FreeList, cds::intrusive::FreeList )
+
+ typedef cds::intrusive::CachedFreeList<cds::intrusive::FreeList> cached_free_list;
+ CDSSTRESS_FREELIST_F( CachedFreeList, cached_free_list )
+
+ TEST_F( put_get, TaggetFreeList )
+ {
+ struct tagged_ptr {
+ void* p;
+ uintptr_t tag;
+ };
+
+ atomics::atomic<tagged_ptr> tp;
+ if ( tp.is_lock_free() ) {
+ cds::intrusive::TaggedFreeList fl;
+ test( fl );
+ }
+ else
+ std::cout << "Double-width CAS is not supported\n";
+ }
+
+} // namespace
--- /dev/null
+/*
+ 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.
+*/
+
+#include <cds_test/stress_test.h>
+
+#include <cds/intrusive/free_list.h>
+#include <cds/intrusive/free_list_cached.h>
+#include <cds/intrusive/free_list_tagged.h>
+
+namespace {
+ class put_get_single: public cds_test::stress_fixture
+ {
+ protected:
+ static size_t s_nThreadCount;
+ static size_t s_nPassCount;
+
+ template <typename FreeList >
+ struct value_type: public FreeList::node
+ {
+ size_t counter;
+
+ value_type()
+ : counter(0)
+ {}
+ };
+
+ template <class FreeList>
+ class Worker: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ public:
+ FreeList& m_FreeList;
+ size_t m_nSuccess = 0;
+
+ public:
+ Worker( cds_test::thread_pool& pool, FreeList& s )
+ : base_class( pool )
+ , m_FreeList( s )
+ {}
+
+ Worker( Worker& src )
+ : base_class( src )
+ , m_FreeList( src.m_FreeList )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Worker( *this );
+ }
+
+ virtual void test()
+ {
+ typedef value_type<FreeList> item_type;
+
+ for ( size_t pass = 0; pass < s_nPassCount; ++pass ) {
+ item_type* p;
+ while ( (p = static_cast<item_type*>( m_FreeList.get())) == nullptr );
+ p->counter++;
+ m_FreeList.put( p );
+ }
+ }
+ };
+
+ public:
+ static void SetUpTestCase()
+ {
+ cds_test::config const& cfg = get_config( "free_list" );
+
+ s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
+ s_nPassCount = cfg.get_size_t( "PassCount", s_nPassCount );
+
+ if ( s_nThreadCount == 0 )
+ s_nThreadCount = 1;
+ if ( s_nPassCount == 0 )
+ s_nPassCount = 1000;
+ }
+ //static void TearDownTestCase();
+
+ protected:
+
+ template <typename FreeList>
+ void test( FreeList& list )
+ {
+ cds_test::thread_pool& pool = get_pool();
+
+ value_type<FreeList> item;;
+ list.put( &item );
+
+ pool.add( new Worker<FreeList>( pool, list ), s_nThreadCount );
+
+ propout() << std::make_pair( "work_thread", s_nThreadCount )
+ << std::make_pair( "pass_count", s_nPassCount );
+
+ std::chrono::milliseconds duration = pool.run();
+
+ propout() << std::make_pair( "duration", duration );
+
+ // analyze result
+ EXPECT_EQ( item.counter, s_nPassCount * s_nThreadCount );
+
+ list.clear( []( typename FreeList::node* ) {} );
+ }
+ };
+
+ size_t put_get_single::s_nThreadCount = 4;
+ size_t put_get_single::s_nPassCount = 100000;
+
+#define CDSSTRESS_FREELIST_F( name, freelist_type ) \
+ TEST_F( put_get_single, name ) \
+ { \
+ freelist_type fl; \
+ test( fl ); \
+ }
+
+ CDSSTRESS_FREELIST_F( FreeList, cds::intrusive::FreeList )
+
+ typedef cds::intrusive::CachedFreeList<cds::intrusive::FreeList> cached_free_list;
+ CDSSTRESS_FREELIST_F( CachedFreeList, cached_free_list )
+
+ TEST_F( put_get_single, TaggetFreeList )
+ {
+ struct tagged_ptr {
+ void* p;
+ uintptr_t tag;
+ };
+
+ atomics::atomic<tagged_ptr> tp;
+ if ( tp.is_lock_free() ) {
+ cds::intrusive::TaggedFreeList fl;
+ test( fl );
+ }
+ else
+ std::cout << "Double-width CAS is not supported\n";
+ }
+
+} // namespace
projects / libcds.git / commitdiff