-//$$CDS-header$$
+/*
+ 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 "cppunit/thread.h"
-#include "set2/set_types.h"
-#include <algorithm> // random_shuffle
+#include "set2/set_type.h"
namespace set2 {
-# define TEST_SET(X) void X() { test<SetTypes<key_type, value_type>::X >() ; }
-# define TEST_SET_EXTRACT(X) void X() { test_extract<SetTypes<key_type, value_type>::X >() ; }
-# define TEST_SET_NOLF(X) void X() { test_nolf<SetTypes<key_type, value_type>::X >() ; }
-# define TEST_SET_NOLF_EXTRACT(X) void X() { test_nolf_extract<SetTypes<key_type, value_type>::X >() ; }
+#define TEST_CASE(TAG, X) void X();
namespace {
struct key_thread
{
- size_t nKey;
- size_t nThread;
+ uint32_t nKey;
+ uint16_t nThread;
+ uint16_t pad_;
key_thread( size_t key, size_t threadNo )
- : nKey( key )
- , nThread( threadNo )
+ : nKey( static_cast<uint32_t>(key))
+ , nThread( static_cast<uint16_t>(threadNo))
+ , pad_(0)
{}
key_thread()
{}
};
- typedef SetTypes<key_thread, size_t>::key_val key_value_pair;
+ typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
}
template <>
class Set_DelOdd: public CppUnitMini::TestCase
{
- static size_t c_nSetSize; // max set size
- static size_t c_nInsThreadCount; // insert thread count
- static size_t c_nDelThreadCount; // delete thread count
- static size_t c_nExtractThreadCount; // extract thread count
- static size_t c_nMaxLoadFactor; // maximum load factor
- static bool c_bPrintGCState;
-
+ public:
+ size_t c_nSetSize =1000000; // max set size
+ size_t c_nInsThreadCount = 4; // insert thread count
+ size_t c_nDelThreadCount = 4; // delete thread count
+ size_t c_nExtractThreadCount = 4; // extract thread count
+ size_t c_nMaxLoadFactor = 8; // maximum load factor
+ bool c_bPrintGCState = true;
+
+ size_t c_nCuckooInitialSize = 1024;// initial size for CuckooSet
+ size_t c_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
+ size_t c_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
+
+ size_t c_nFeldmanSet_HeadBits = 10;
+ size_t c_nFeldmanSet_ArrayBits = 4;
+
+ size_t c_nLoadFactor = 2;
std::vector<size_t> m_arrData;
protected:
- typedef CppUnitMini::TestCase Base;
typedef key_thread key_type;
typedef size_t value_type;
return new InsertThread( *this );
}
- struct ensure_func
+ struct update_functor
{
template <typename Q>
void operator()( bool /*bNew*/, key_value_pair const&, Q const& )
{}
+
+ void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/)
+ {}
};
public:
size_t m_nInsertSuccess;
++m_nInsertFailed;
}
- ensure_func f;
+ update_functor f;
for ( size_t i = arrData.size() - 1; i > 0; --i ) {
if ( arrData[i] & 1 ) {
- rSet.ensure( key_type( arrData[i], m_nThreadNo ), f );
+ rSet.update( key_type( arrData[i], m_nThreadNo ), f, true );
}
}
virtual void init() { cds::threading::Manager::attachThread() ; }
virtual void fini() { cds::threading::Manager::detachThread() ; }
+ template <typename SetType, bool>
+ struct eraser {
+ static bool erase( SetType& s, size_t key, size_t /*thread*/)
+ {
+ return s.erase_with( key, key_less() );
+ }
+ };
+
+ template <typename SetType>
+ struct eraser<SetType, true> {
+ static bool erase(SetType& s, size_t key, size_t thread)
+ {
+ return s.erase( key_type(key, thread));
+ }
+ };
+
virtual void test()
{
Set& rSet = m_Set;
m_nDeleteSuccess =
m_nDeleteFailed = 0;
+ size_t const nInsThreadCount = getTest().c_nInsThreadCount;
std::vector<size_t>& arrData = getTest().m_arrData;
+
if ( m_nThreadNo & 1 ) {
- for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
- for ( size_t i = 0; i < arrData.size(); ++i ) {
- if ( arrData[i] & 1 ) {
- if ( rSet.erase_with( arrData[i], key_less() ))
+ for (size_t i = 0; i < arrData.size(); ++i) {
+ if (arrData[i] & 1) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ if ( eraser<Set, Set::c_bEraseExactKey>::erase( rSet, arrData[i], k ))
++m_nDeleteSuccess;
else
++m_nDeleteFailed;
}
}
else {
- for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
- for ( size_t i = arrData.size() - 1; i > 0; --i ) {
- if ( arrData[i] & 1 ) {
- if ( rSet.erase_with( arrData[i], key_less() ))
+ for (size_t i = arrData.size() - 1; i > 0; --i) {
+ if (arrData[i] & 1) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ if (eraser<Set, Set::c_bEraseExactKey>::erase(rSet, arrData[i], k))
++m_nDeleteSuccess;
else
++m_nDeleteFailed;
virtual void init() { cds::threading::Manager::attachThread() ; }
virtual void fini() { cds::threading::Manager::detachThread() ; }
+ template <typename SetType, bool>
+ struct extractor {
+ static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t /*thread*/)
+ {
+ return s.extract_with( key, key_less());
+ }
+ };
+
+ template <typename SetType>
+ struct extractor<SetType, true> {
+ static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t thread)
+ {
+ return s.extract( key_type(key, thread));
+ }
+ };
+
virtual void test()
{
Set& rSet = m_Set;
typename Set::guarded_ptr gp;
std::vector<size_t>& arrData = getTest().m_arrData;
+ size_t const nInsThreadCount = getTest().c_nInsThreadCount;
+
if ( m_nThreadNo & 1 ) {
- for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
- for ( size_t i = 0; i < arrData.size(); ++i ) {
- if ( arrData[i] & 1 ) {
- gp = rSet.extract_with( arrData[i], key_less());
+ for ( size_t i = 0; i < arrData.size(); ++i ) {
+ if (arrData[i] & 1) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k );
if ( gp )
++m_nExtractSuccess;
else
}
}
else {
- for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
- for ( size_t i = arrData.size() - 1; i > 0; --i ) {
- if ( arrData[i] & 1 ) {
- gp = rSet.extract_with( arrData[i], key_less());
+ for (size_t i = arrData.size() - 1; i > 0; --i) {
+ if (arrData[i] & 1) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
if ( gp )
++m_nExtractSuccess;
else
virtual void init() { cds::threading::Manager::attachThread() ; }
virtual void fini() { cds::threading::Manager::detachThread() ; }
+ template <typename SetType, bool>
+ struct extractor {
+ static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t /*thread*/)
+ {
+ return s.extract_with(key, key_less());
+ }
+ };
+
+ template <typename SetType>
+ struct extractor<SetType, true> {
+ static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t thread)
+ {
+ return s.extract(key_type(key, thread));
+ }
+ };
+
virtual void test()
{
Set& rSet = m_Set;
typename Set::exempt_ptr xp;
std::vector<size_t>& arrData = getTest().m_arrData;
+ size_t const nInsThreadCount = getTest().c_nInsThreadCount;
+
if ( m_nThreadNo & 1 ) {
- for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
- for ( size_t i = 0; i < arrData.size(); ++i ) {
- if ( arrData[i] & 1 ) {
+ for (size_t i = 0; i < arrData.size(); ++i) {
+ if (arrData[i] & 1) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
if ( Set::c_bExtractLockExternal ) {
typename Set::rcu_lock l;
- xp = rSet.extract_with( arrData[i], key_less() );
+ xp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
if ( xp )
++m_nExtractSuccess;
else
++m_nExtractFailed;
}
else {
- xp = rSet.extract_with( arrData[i], key_less() );
+ xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
if ( xp )
++m_nExtractSuccess;
else
}
}
else {
- for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
- for ( size_t i = arrData.size() - 1; i > 0; --i ) {
- if ( arrData[i] & 1 ) {
+ for (size_t i = arrData.size() - 1; i > 0; --i) {
+ if (arrData[i] & 1) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
if ( Set::c_bExtractLockExternal ) {
typename Set::rcu_lock l;
- xp = rSet.extract_with( arrData[i], key_less() );
+ xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
if ( xp )
++m_nExtractSuccess;
else
++m_nExtractFailed;
}
else {
- xp = rSet.extract_with( arrData[i], key_less() );
+ xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
if ( xp )
++m_nExtractSuccess;
else
size_t nErrorCount = 0;
for ( size_t n = 0; n < c_nSetSize; n +=2 ) {
for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
- if ( !testSet.find( key_type(n, i) ) ) {
+ if ( !testSet.contains( key_type(n, i) ) ) {
if ( ++nErrorCount < 10 ) {
CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
}
}
template <class Set>
- void test()
+ void run_test()
{
+ static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
+
CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
<< " delete thread count=" << c_nDelThreadCount
<< " set size=" << c_nSetSize
);
- for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
- CPPUNIT_MSG( "Load factor=" << nLoadFactor );
- do_test<Set>( nLoadFactor );
- if ( c_bPrintGCState )
- print_gc_state();
- }
- }
+ if ( Set::c_bLoadFactorDepended ) {
+ for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
+ CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
- template <class Set>
- void test_extract()
- {
- CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
- << " delete thread count=" << c_nDelThreadCount
- << " extract thread count=" << c_nExtractThreadCount
- << " set size=" << c_nSetSize
- );
+ Set testSet( *this );
+ do_test_with( testSet );
+ analyze( testSet );
+
+ if ( c_bPrintGCState )
+ print_gc_state();
+ }
+ }
+ else {
+ Set testSet( *this );
+ do_test_with( testSet );
+ analyze( testSet );
- for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
- CPPUNIT_MSG( "Load factor=" << nLoadFactor );
- do_test_extract<Set>( nLoadFactor );
if ( c_bPrintGCState )
print_gc_state();
}
}
template <class Set>
- void test_nolf()
+ void run_test_extract()
{
- CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
- << " delete thread count=" << c_nDelThreadCount
- << " set size=" << c_nSetSize
- );
+ static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
- {
- Set s;
- do_test_with( s );
- analyze( s );
- }
-
- if ( c_bPrintGCState )
- print_gc_state();
- }
-
- template <class Set>
- void test_nolf_extract()
- {
CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
<< " delete thread count=" << c_nDelThreadCount
<< " extract thread count=" << c_nExtractThreadCount
<< " set size=" << c_nSetSize
);
- {
- Set s;
- do_test_extract_with( s );
- analyze( s );
+ if ( Set::c_bLoadFactorDepended ) {
+ for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
+ CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
+
+ Set testSet( *this );
+ do_test_extract_with( testSet );
+ analyze( testSet );
+
+ if ( c_bPrintGCState )
+ print_gc_state();
+ }
}
+ else {
+ Set testSet( *this );
+ do_test_extract_with( testSet );
+ analyze( testSet );
- if ( c_bPrintGCState )
- print_gc_state();
+ if ( c_bPrintGCState )
+ print_gc_state();
+ }
}
void setUpParams( const CppUnitMini::TestCfg& cfg );
-
- void run_MichaelSet(const char *in_name, bool invert = false);
- void run_SplitList(const char *in_name, bool invert = false);
- void run_CuckooSet(const char *in_name, bool invert = false);
- void run_SkipListSet(const char *in_name, bool invert = false);
- void run_EllenBinTreeSet(const char *in_name, bool invert = false);
-
- virtual void myRun(const char *in_name, bool invert = false);
-
+ virtual void endTestCase();
# include "set2/set_defs.h"
CDSUNIT_DECLARE_MichaelSet
CDSUNIT_DECLARE_SplitList
- CDSUNIT_DECLARE_CuckooSet
CDSUNIT_DECLARE_SkipListSet
CDSUNIT_DECLARE_EllenBinTreeSet
+ CDSUNIT_DECLARE_CuckooSet
+ CDSUNIT_DECLARE_FeldmanHashSet_fixed
+ CDSUNIT_DECLARE_FeldmanHashSet_city
+
+ CPPUNIT_TEST_SUITE_(Set_DelOdd, "Map_DelOdd")
+ CDSUNIT_TEST_MichaelSet
+ CDSUNIT_TEST_SplitList
+ CDSUNIT_TEST_SkipListSet
+ CDSUNIT_TEST_EllenBinTreeSet
+ CDSUNIT_TEST_FeldmanHashSet_fixed
+ CDSUNIT_TEST_FeldmanHashSet_city
+ CDSUNIT_TEST_CuckooSet
+ CPPUNIT_TEST_SUITE_END();
};
} // namespace set2
projects / libcds.git / blobdiff