2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #include "map2/map_type.h"
32 #include "cppunit/thread.h"
38 # define TEST_CASE(TAG, X) void X();
40 class Map_InsDel_int: public CppUnitMini::TestCase
43 size_t c_nMapSize = 1000000; // map size
44 size_t c_nInsertThreadCount = 4; // count of insertion thread
45 size_t c_nDeleteThreadCount = 4; // count of deletion thread
46 size_t c_nThreadPassCount = 4; // pass count for each thread
47 size_t c_nMaxLoadFactor = 8; // maximum load factor
49 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
50 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
51 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
53 size_t c_nFeldmanMap_HeadBits = 10;
54 size_t c_nFeldmanMap_ArrayBits = 4;
56 bool c_bPrintGCState = true;
58 size_t c_nLoadFactor; // current load factor
61 typedef size_t key_type;
62 typedef size_t value_type;
64 typedef std::vector<key_type> key_array;
65 key_array m_arrValues;
68 class Inserter: public CppUnitMini::TestThread
72 virtual Inserter * clone()
74 return new Inserter( *this );
77 size_t m_nInsertSuccess;
78 size_t m_nInsertFailed;
81 Inserter( CppUnitMini::ThreadPool& pool, Map& rMap )
82 : CppUnitMini::TestThread( pool )
85 Inserter( Inserter& src )
86 : CppUnitMini::TestThread( src )
90 Map_InsDel_int& getTest()
92 return reinterpret_cast<Map_InsDel_int&>( m_Pool.m_Test );
95 virtual void init() { cds::threading::Manager::attachThread() ; }
96 virtual void fini() { cds::threading::Manager::detachThread() ; }
104 key_array const& arr = getTest().m_arrValues;
106 size_t const nPassCount = getTest().c_nThreadPassCount;
108 if ( m_nThreadNo & 1 ) {
109 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
110 for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) {
111 if ( rMap.insert( *it, *it * 8 ) )
119 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
120 for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) {
121 if ( rMap.insert( *it, *it * 8 ) )
132 class Deleter: public CppUnitMini::TestThread
136 virtual Deleter * clone()
138 return new Deleter( *this );
141 size_t m_nDeleteSuccess;
142 size_t m_nDeleteFailed;
145 Deleter( CppUnitMini::ThreadPool& pool, Map& rMap )
146 : CppUnitMini::TestThread( pool )
149 Deleter( Deleter& src )
150 : CppUnitMini::TestThread( src )
154 Map_InsDel_int& getTest()
156 return reinterpret_cast<Map_InsDel_int&>( m_Pool.m_Test );
159 virtual void init() { cds::threading::Manager::attachThread() ; }
160 virtual void fini() { cds::threading::Manager::detachThread() ; }
168 key_array const& arr = getTest().m_arrValues;
170 size_t const nPassCount = getTest().c_nThreadPassCount;
172 if ( m_nThreadNo & 1 ) {
173 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
174 for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) {
175 if ( rMap.erase( *it ) )
183 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
184 for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) {
185 if ( rMap.erase( *it ) )
197 void do_test( Map& testMap )
199 typedef Inserter<Map> InserterThread;
200 typedef Deleter<Map> DeleterThread;
201 cds::OS::Timer timer;
203 CppUnitMini::ThreadPool pool( *this );
204 pool.add( new InserterThread( pool, testMap ), c_nInsertThreadCount );
205 pool.add( new DeleterThread( pool, testMap ), c_nDeleteThreadCount );
207 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
209 size_t nInsertSuccess = 0;
210 size_t nInsertFailed = 0;
211 size_t nDeleteSuccess = 0;
212 size_t nDeleteFailed = 0;
213 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
214 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
216 nInsertSuccess += pThread->m_nInsertSuccess;
217 nInsertFailed += pThread->m_nInsertFailed;
220 DeleterThread * p = static_cast<DeleterThread *>( *it );
221 nDeleteSuccess += p->m_nDeleteSuccess;
222 nDeleteFailed += p->m_nDeleteFailed;
226 CPPUNIT_MSG( " Totals: Ins succ=" << nInsertSuccess
227 << " Del succ=" << nDeleteSuccess << "\n"
228 << " : Ins fail=" << nInsertFailed
229 << " Del fail=" << nDeleteFailed
230 << " Map size=" << testMap.size()
233 check_before_cleanup( testMap );
235 CPPUNIT_MSG( " Clear map (single-threaded)..." );
237 for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
238 testMap.erase( nItem );
240 CPPUNIT_MSG( " Duration=" << timer.duration() );
241 CPPUNIT_CHECK( testMap.empty());
242 CPPUNIT_CHECK_EX( testMap.size() == 0, "size() == " << testMap.size() );
244 additional_check( testMap );
245 print_stat( testMap );
246 additional_cleanup( testMap );
252 CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
253 << " delete=" << c_nDeleteThreadCount
254 << " pass count=" << c_nThreadPassCount
255 << " map size=" << c_nMapSize
258 if ( Map::c_bLoadFactorDepended ) {
259 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
260 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
261 Map testMap( *this );
263 if ( c_bPrintGCState )
268 Map testMap( *this );
270 if ( c_bPrintGCState )
275 void setUpParams( const CppUnitMini::TestCfg& cfg );
277 # include "map2/map_defs.h"
278 CDSUNIT_DECLARE_MichaelMap
279 CDSUNIT_DECLARE_SplitList
280 CDSUNIT_DECLARE_SkipListMap
281 CDSUNIT_DECLARE_EllenBinTreeMap
282 CDSUNIT_DECLARE_BronsonAVLTreeMap
283 CDSUNIT_DECLARE_FeldmanHashMap_fixed
284 CDSUNIT_DECLARE_FeldmanHashMap_city
285 CDSUNIT_DECLARE_StripedMap
286 CDSUNIT_DECLARE_RefinableMap
287 CDSUNIT_DECLARE_CuckooMap
288 CDSUNIT_DECLARE_StdMap
290 CPPUNIT_TEST_SUITE(Map_InsDel_int)
291 CDSUNIT_TEST_MichaelMap
292 CDSUNIT_TEST_SplitList
293 CDSUNIT_TEST_SkipListMap
294 CDSUNIT_TEST_EllenBinTreeMap
295 CDSUNIT_TEST_BronsonAVLTreeMap
296 CDSUNIT_TEST_FeldmanHashMap_fixed
297 CDSUNIT_TEST_FeldmanHashMap_city
298 CDSUNIT_TEST_CuckooMap
299 CDSUNIT_TEST_StripedMap
300 CDSUNIT_TEST_RefinableMap
302 CPPUNIT_TEST_SUITE_END();