3 // defines concurrent access to map::nonconcurrent_iterator::Sequence::TValue::nAccess field
5 #include "map2/map_types.h"
6 #include "cppunit/thread.h"
10 // find int test in map<int> in mutithreaded mode
13 # define TEST_MAP(X) void X() { test<MapTypes<key_type, value_type>::X >() ; }
14 # define TEST_MAP_NOLF(X) void X() { test_nolf<MapTypes<key_type, value_type>::X >() ; }
15 # define TEST_MAP_EXTRACT(X) TEST_MAP(X)
16 # define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X)
19 static size_t c_nThreadCount = 8 ; // thread count
20 static size_t c_nMapSize = 20000000 ; // map size (count of searching item)
21 static size_t c_nPercentExists = 50 ; // percent of existing keys in searching sequence
22 static size_t c_nPassCount = 2;
23 static size_t c_nMaxLoadFactor = 8 ; // maximum load factor
24 static bool c_bPrintGCState = true;
27 class Map_find_string: public CppUnitMini::TestCase
29 typedef std::string key_type;
31 std::string const * pKey;
32 bool bExists ; // true - key in map, false - key not in map
35 typedef std::vector<value_type> ValueVector;
37 size_t m_nRealMapSize;
40 template <typename Iterator, typename Map>
41 static bool check_result( Iterator const& it, Map const& map )
43 return it != map.end();
45 template <typename Map>
46 static bool check_result( bool b, Map const& )
52 class TestThread: public CppUnitMini::TestThread
56 virtual TestThread * clone()
58 return new TestThread( *this );
75 TestThread( CppUnitMini::ThreadPool& pool, MAP& rMap )
76 : CppUnitMini::TestThread( pool )
79 TestThread( TestThread& src )
80 : CppUnitMini::TestThread( src )
84 Map_find_string& getTest()
86 return reinterpret_cast<Map_find_string&>( m_Pool.m_Test );
89 virtual void init() { cds::threading::Manager::attachThread() ; }
90 virtual void fini() { cds::threading::Manager::detachThread() ; }
94 ValueVector& arr = getTest().m_Arr;
95 //size_t nSize = arr.size();
98 for ( size_t nPass = 0; nPass < c_nPassCount; ++nPass ) {
99 if ( m_nThreadNo & 1 ) {
100 ValueVector::const_iterator itEnd = arr.end();
101 for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
102 auto bFound = rMap.find( *(it->pKey) );
104 if ( check_result(bFound, rMap))
105 ++m_KeyExists.nSuccess;
107 ++m_KeyExists.nFailed;
110 if ( check_result(bFound, rMap))
111 ++m_KeyNotExists.nFailed;
113 ++m_KeyNotExists.nSuccess;
118 ValueVector::const_reverse_iterator itEnd = arr.rend();
119 for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
120 auto bFound = rMap.find( *(it->pKey) );
122 if ( check_result(bFound, rMap))
123 ++m_KeyExists.nSuccess;
125 ++m_KeyExists.nFailed;
128 if ( check_result( bFound, rMap ))
129 ++m_KeyNotExists.nFailed;
131 ++m_KeyNotExists.nSuccess;
141 : m_bSeqInit( false )
146 void generateSequence()
148 size_t nPercent = c_nPercentExists;
150 if ( nPercent > 100 )
152 else if ( nPercent < 1 )
157 std::vector<std::string> const & arrString = CppUnitMini::TestCase::getTestStrings();
158 size_t nSize = arrString.size();
159 if ( nSize > c_nMapSize )
161 m_Arr.resize( nSize );
162 for ( size_t i = 0; i < nSize; ++i ) {
163 m_Arr[i].pKey = &( arrString[i] );
164 m_Arr[i].bExists = CppUnitMini::Rand( 100 ) <= nPercent;
165 if ( m_Arr[i].bExists )
172 void find_string_test( MAP& testMap )
174 typedef TestThread<MAP> Thread;
175 cds::OS::Timer timer;
178 CPPUNIT_MSG( " Fill map...");
180 for ( size_t i = 0; i < m_Arr.size(); ++i ) {
181 // Âñå êëþ÷è â arrData - óíèêàëüíûå, ïîýòîìó îøèáîê ïðè âñòàâêå áûòü íå äîëæíî
182 if ( m_Arr[i].bExists )
183 CPPUNIT_ASSERT( check_result( testMap.insert( *(m_Arr[i].pKey), m_Arr[i] ), testMap ));
185 CPPUNIT_MSG( " Duration=" << timer.duration() );
187 CPPUNIT_MSG( " Searching...");
188 CppUnitMini::ThreadPool pool( *this );
189 pool.add( new Thread( pool, testMap ), c_nThreadCount );
191 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
193 // Ïðîâåðÿåì, ÷òî ó âñåõ threads ÷èñëî óñïåøíûõ ïîèñêîâ = ÷èñëó ýëåìåíòîâ â map
194 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
195 Thread * pThread = static_cast<Thread *>( *it );
196 CPPUNIT_ASSERT( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
197 CPPUNIT_ASSERT( pThread->m_KeyExists.nFailed == 0 );
198 CPPUNIT_ASSERT( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
199 CPPUNIT_ASSERT( pThread->m_KeyNotExists.nFailed == 0 );
203 additional_check( testMap );
204 print_stat( testMap );
205 additional_cleanup( testMap );
208 void initTestSequence()
213 CPPUNIT_MSG( "Generating test data...");
214 cds::OS::Timer timer;
216 CPPUNIT_MSG( " Duration=" << timer.duration() );
217 CPPUNIT_MSG( "Map size=" << m_nRealMapSize << " find key loop=" << m_Arr.size() << " (" << c_nPercentExists << "% success)" );
218 CPPUNIT_MSG( "Thread count=" << c_nThreadCount << " Pass count=" << c_nPassCount );
227 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
228 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
229 MAP testMap( m_Arr.size(), nLoadFactor );
230 find_string_test( testMap );
231 if ( c_bPrintGCState )
242 find_string_test( testMap );
243 if ( c_bPrintGCState )
247 void setUpParams( const CppUnitMini::TestCfg& cfg ) {
248 c_nThreadCount = cfg.getULong("ThreadCount", 8 ) ; // thread count
249 c_nMapSize = cfg.getULong("MapSize", 20000000 ) ; // map size (count of searching item)
250 c_nPercentExists = cfg.getULong("PercentExists", 50 ) ; // percent of existing keys in searching sequence
251 c_nPassCount = cfg.getULong("PassCount", 2 );
252 c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
253 c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
256 # include "map2/map_defs.h"
257 CDSUNIT_DECLARE_MichaelMap
258 CDSUNIT_DECLARE_MichaelMap_nogc
259 CDSUNIT_DECLARE_SplitList
260 CDSUNIT_DECLARE_SplitList_nogc
261 CDSUNIT_DECLARE_SkipListMap
262 CDSUNIT_DECLARE_SkipListMap_nogc
263 CDSUNIT_DECLARE_EllenBinTreeMap
264 CDSUNIT_DECLARE_StripedMap
265 CDSUNIT_DECLARE_RefinableMap
266 CDSUNIT_DECLARE_CuckooMap
267 CDSUNIT_DECLARE_StdMap
269 CPPUNIT_TEST_SUITE( Map_find_string )
270 CDSUNIT_TEST_MichaelMap
271 CDSUNIT_TEST_MichaelMap_nogc
272 CDSUNIT_TEST_SplitList
273 CDSUNIT_TEST_SplitList_nogc
274 CDSUNIT_TEST_SkipListMap
275 CDSUNIT_TEST_SkipListMap_nogc
276 CDSUNIT_TEST_EllenBinTreeMap
277 CDSUNIT_TEST_StripedMap
278 CDSUNIT_TEST_RefinableMap
279 CDSUNIT_TEST_CuckooMap
281 CPPUNIT_TEST_SUITE_END()
285 CPPUNIT_TEST_SUITE_REGISTRATION( Map_find_string );