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_string: 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 std::string key_type;
62 typedef size_t value_type;
64 const std::vector<std::string> * m_parrString;
67 class Inserter: public CppUnitMini::TestThread
71 virtual Inserter * clone()
73 return new Inserter( *this );
76 size_t m_nInsertSuccess;
77 size_t m_nInsertFailed;
80 Inserter( CppUnitMini::ThreadPool& pool, Map& rMap )
81 : CppUnitMini::TestThread( pool )
84 Inserter( Inserter& src )
85 : CppUnitMini::TestThread( src )
89 Map_InsDel_string& getTest()
91 return reinterpret_cast<Map_InsDel_string&>( m_Pool.m_Test );
94 virtual void init() { cds::threading::Manager::attachThread() ; }
95 virtual void fini() { cds::threading::Manager::detachThread() ; }
104 const std::vector<std::string>& arrString = *getTest().m_parrString;
105 size_t nArrSize = arrString.size();
106 size_t const nMapSize = getTest().c_nMapSize;
107 size_t const nPassCount = getTest().c_nThreadPassCount;
109 if ( m_nThreadNo & 1 ) {
110 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
111 for ( size_t nItem = 0; nItem < nMapSize; ++nItem ) {
112 if ( rMap.insert( arrString[nItem % nArrSize], nItem * 8 ) )
120 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
121 for ( size_t nItem = nMapSize; nItem > 0; --nItem ) {
122 if ( rMap.insert( arrString[nItem % nArrSize], nItem * 8 ) )
133 class Deleter: public CppUnitMini::TestThread
137 virtual Deleter * clone()
139 return new Deleter( *this );
142 size_t m_nDeleteSuccess;
143 size_t m_nDeleteFailed;
146 Deleter( CppUnitMini::ThreadPool& pool, Map& rMap )
147 : CppUnitMini::TestThread( pool )
150 Deleter( Deleter& src )
151 : CppUnitMini::TestThread( src )
155 Map_InsDel_string& getTest()
157 return reinterpret_cast<Map_InsDel_string&>( m_Pool.m_Test );
160 virtual void init() { cds::threading::Manager::attachThread() ; }
161 virtual void fini() { cds::threading::Manager::detachThread() ; }
170 const std::vector<std::string>& arrString = *getTest().m_parrString;
171 size_t nArrSize = arrString.size();
172 size_t const nMapSize = getTest().c_nMapSize;
173 size_t const nPassCount = getTest().c_nThreadPassCount;
175 if ( m_nThreadNo & 1 ) {
176 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
177 for ( size_t nItem = 0; nItem < nMapSize; ++nItem ) {
178 if ( rMap.erase( arrString[nItem % nArrSize] ) )
186 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
187 for ( size_t nItem = nMapSize; nItem > 0; --nItem ) {
188 if ( rMap.erase( arrString[nItem % nArrSize] ) )
201 void do_test( Map& testMap )
203 typedef Inserter<Map> InserterThread;
204 typedef Deleter<Map> DeleterThread;
205 cds::OS::Timer timer;
207 CppUnitMini::ThreadPool pool( *this );
208 pool.add( new InserterThread( pool, testMap ), c_nInsertThreadCount );
209 pool.add( new DeleterThread( pool, testMap ), c_nDeleteThreadCount );
211 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
213 size_t nInsertSuccess = 0;
214 size_t nInsertFailed = 0;
215 size_t nDeleteSuccess = 0;
216 size_t nDeleteFailed = 0;
217 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
218 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
220 nInsertSuccess += pThread->m_nInsertSuccess;
221 nInsertFailed += pThread->m_nInsertFailed;
224 DeleterThread * p = static_cast<DeleterThread *>( *it );
225 nDeleteSuccess += p->m_nDeleteSuccess;
226 nDeleteFailed += p->m_nDeleteFailed;
230 CPPUNIT_MSG( " Totals: Ins succ=" << nInsertSuccess
231 << " Del succ=" << nDeleteSuccess << "\n"
232 << " : Ins fail=" << nInsertFailed
233 << " Del fail=" << nDeleteFailed
234 << " Map size=" << testMap.size()
237 check_before_cleanup( testMap );
239 CPPUNIT_MSG( " Clear map (single-threaded)..." );
241 for ( size_t i = 0; i < m_parrString->size(); ++i )
242 testMap.erase( (*m_parrString)[i] );
243 CPPUNIT_MSG( " Duration=" << timer.duration() );
244 CPPUNIT_CHECK( testMap.empty() );
245 CPPUNIT_CHECK_EX( testMap.size() == 0, "size() == " << testMap.size() );
247 additional_check( testMap );
248 print_stat( testMap );
249 additional_cleanup( testMap );
255 m_parrString = &CppUnitMini::TestCase::getTestStrings();
257 CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
258 << " delete=" << c_nDeleteThreadCount
259 << " pass count=" << c_nThreadPassCount
260 << " map size=" << c_nMapSize
263 if ( Map::c_bLoadFactorDepended ) {
264 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
265 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
266 Map testMap( *this );
268 if ( c_bPrintGCState )
273 Map testMap( *this );
275 if ( c_bPrintGCState )
280 void setUpParams( const CppUnitMini::TestCfg& cfg );
282 # include "map2/map_defs.h"
283 CDSUNIT_DECLARE_MichaelMap
284 CDSUNIT_DECLARE_SplitList
285 CDSUNIT_DECLARE_SkipListMap
286 CDSUNIT_DECLARE_EllenBinTreeMap
287 CDSUNIT_DECLARE_BronsonAVLTreeMap
288 CDSUNIT_DECLARE_FeldmanHashMap_city
289 CDSUNIT_DECLARE_StripedMap
290 CDSUNIT_DECLARE_RefinableMap
291 CDSUNIT_DECLARE_CuckooMap
292 CDSUNIT_DECLARE_StdMap
294 CPPUNIT_TEST_SUITE_(Map_InsDel_string, "map_insdel_func")
295 CDSUNIT_TEST_MichaelMap
296 CDSUNIT_TEST_SplitList
297 CDSUNIT_TEST_SkipListMap
298 CDSUNIT_TEST_EllenBinTreeMap
299 CDSUNIT_TEST_BronsonAVLTreeMap
300 CDSUNIT_TEST_FeldmanHashMap_city
301 CDSUNIT_TEST_CuckooMap
302 CDSUNIT_TEST_StripedMap
303 CDSUNIT_TEST_RefinableMap
305 CPPUNIT_TEST_SUITE_END();