3 #include "map2/map_types.h"
4 #include "cppunit/thread.h"
10 # define TEST_MAP(X) void X() { test<MapTypes<key_type, value_type>::X >() ; }
11 # define TEST_MAP_NOLF(X) void X() { test_nolf<MapTypes<key_type, value_type>::X >() ; }
12 # define TEST_MAP_EXTRACT(X) TEST_MAP(X)
13 # define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X)
16 static size_t c_nThreadCount = 8 ; // thread count
17 static size_t c_nMapSize = 20000000 ; // map size (count of searching item)
18 static size_t c_nPercentExists = 50 ; // percent of existing keys in searching sequence
19 static size_t c_nPassCount = 2;
20 static size_t c_nMaxLoadFactor = 8 ; // maximum load factor
21 static bool c_bPrintGCState = true;
24 class Map_find_string: public CppUnitMini::TestCase
26 typedef std::string key_type;
28 std::string const * pKey;
29 bool bExists ; // true - key in map, false - key not in map
32 typedef std::vector<value_type> ValueVector;
34 size_t m_nRealMapSize;
37 template <typename Iterator, typename Map>
38 static bool check_result( Iterator const& it, Map const& map )
40 return it != map.end();
42 template <typename Map>
43 static bool check_result( bool b, Map const& )
49 class TestThread: public CppUnitMini::TestThread
53 virtual TestThread * clone()
55 return new TestThread( *this );
72 TestThread( CppUnitMini::ThreadPool& pool, MAP& rMap )
73 : CppUnitMini::TestThread( pool )
76 TestThread( TestThread& src )
77 : CppUnitMini::TestThread( src )
81 Map_find_string& getTest()
83 return reinterpret_cast<Map_find_string&>( m_Pool.m_Test );
86 virtual void init() { cds::threading::Manager::attachThread() ; }
87 virtual void fini() { cds::threading::Manager::detachThread() ; }
91 ValueVector& arr = getTest().m_Arr;
92 //size_t nSize = arr.size();
95 for ( size_t nPass = 0; nPass < c_nPassCount; ++nPass ) {
96 if ( m_nThreadNo & 1 ) {
97 ValueVector::const_iterator itEnd = arr.end();
98 for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
99 auto bFound = rMap.find( *(it->pKey) );
101 if ( check_result(bFound, rMap))
102 ++m_KeyExists.nSuccess;
104 ++m_KeyExists.nFailed;
107 if ( check_result(bFound, rMap))
108 ++m_KeyNotExists.nFailed;
110 ++m_KeyNotExists.nSuccess;
115 ValueVector::const_reverse_iterator itEnd = arr.rend();
116 for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
117 auto bFound = rMap.find( *(it->pKey) );
119 if ( check_result(bFound, rMap))
120 ++m_KeyExists.nSuccess;
122 ++m_KeyExists.nFailed;
125 if ( check_result( bFound, rMap ))
126 ++m_KeyNotExists.nFailed;
128 ++m_KeyNotExists.nSuccess;
138 : m_bSeqInit( false )
143 void generateSequence()
145 size_t nPercent = c_nPercentExists;
147 if ( nPercent > 100 )
149 else if ( nPercent < 1 )
154 std::vector<std::string> const & arrString = CppUnitMini::TestCase::getTestStrings();
155 size_t nSize = arrString.size();
156 if ( nSize > c_nMapSize )
158 m_Arr.resize( nSize );
159 for ( size_t i = 0; i < nSize; ++i ) {
160 m_Arr[i].pKey = &( arrString[i] );
161 m_Arr[i].bExists = CppUnitMini::Rand( 100 ) <= nPercent;
162 if ( m_Arr[i].bExists )
169 void find_string_test( MAP& testMap )
171 typedef TestThread<MAP> Thread;
172 cds::OS::Timer timer;
175 CPPUNIT_MSG( " Fill map...");
177 for ( size_t i = 0; i < m_Arr.size(); ++i ) {
178 // All keys in arrData are unique, insert() must be successful
179 if ( m_Arr[i].bExists )
180 CPPUNIT_ASSERT( check_result( testMap.insert( *(m_Arr[i].pKey), m_Arr[i] ), testMap ));
182 CPPUNIT_MSG( " Duration=" << timer.duration() );
184 CPPUNIT_MSG( " Searching...");
185 CppUnitMini::ThreadPool pool( *this );
186 pool.add( new Thread( pool, testMap ), c_nThreadCount );
188 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
190 // Postcondition: the number of success searching == the number of map item
191 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
192 Thread * pThread = static_cast<Thread *>( *it );
193 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
194 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
195 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
196 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
199 check_before_cleanup( testMap );
202 additional_check( testMap );
203 print_stat( testMap );
204 additional_cleanup( testMap );
207 void initTestSequence()
212 CPPUNIT_MSG( "Generating test data...");
213 cds::OS::Timer timer;
215 CPPUNIT_MSG( " Duration=" << timer.duration() );
216 CPPUNIT_MSG( "Map size=" << m_nRealMapSize << " find key loop=" << m_Arr.size() << " (" << c_nPercentExists << "% success)" );
217 CPPUNIT_MSG( "Thread count=" << c_nThreadCount << " Pass count=" << c_nPassCount );
226 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
227 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
228 MAP testMap( m_Arr.size(), nLoadFactor );
229 find_string_test( testMap );
230 if ( c_bPrintGCState )
241 find_string_test( testMap );
242 if ( c_bPrintGCState )
246 void setUpParams( const CppUnitMini::TestCfg& cfg ) {
247 c_nThreadCount = cfg.getULong("ThreadCount", 8 ) ; // thread count
248 c_nMapSize = cfg.getULong("MapSize", 20000000 ) ; // map size (count of searching item)
249 c_nPercentExists = cfg.getULong("PercentExists", 50 ) ; // percent of existing keys in searching sequence
250 c_nPassCount = cfg.getULong("PassCount", 2 );
251 c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
252 c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
255 # include "map2/map_defs.h"
256 CDSUNIT_DECLARE_MichaelMap
257 CDSUNIT_DECLARE_MichaelMap_nogc
258 CDSUNIT_DECLARE_SplitList
259 CDSUNIT_DECLARE_SplitList_nogc
260 CDSUNIT_DECLARE_SkipListMap
261 CDSUNIT_DECLARE_SkipListMap_nogc
262 CDSUNIT_DECLARE_EllenBinTreeMap
263 CDSUNIT_DECLARE_BronsonAVLTreeMap
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_BronsonAVLTreeMap
278 CDSUNIT_TEST_StripedMap
279 CDSUNIT_TEST_RefinableMap
280 CDSUNIT_TEST_CuckooMap
282 CPPUNIT_TEST_SUITE_END()
286 CPPUNIT_TEST_SUITE_REGISTRATION( Map_find_string );