3 #include "map2/map_type.h"
4 #include "cppunit/thread.h"
10 #define TEST_CASE(TAG, X) void X();
12 class Map_find_string: public CppUnitMini::TestCase
15 size_t c_nThreadCount = 8; // thread count
16 size_t c_nMapSize = 10000000; // map size (count of searching item)
17 size_t c_nPercentExists = 50; // percent of existing keys in searching sequence
18 size_t c_nPassCount = 2;
19 size_t c_nMaxLoadFactor = 8; // maximum load factor
20 bool c_bPrintGCState = true;
22 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
23 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
24 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
26 size_t c_nFeldmanMap_HeadBits = 10;
27 size_t c_nFeldmanMap_ArrayBits = 4;
29 size_t c_nLoadFactor; // current load factor
32 typedef std::string key_type;
34 std::string const * pKey;
35 bool bExists ; // true - key in map, false - key not in map
38 typedef std::vector<value_type> ValueVector;
41 template <typename Iterator, typename Map>
42 static bool check_result( Iterator const& it, Map const& map )
44 return it != map.end();
46 template <typename Map>
47 static bool check_result( bool b, Map const& )
53 class TestThread: public CppUnitMini::TestThread
57 virtual TestThread * clone()
59 return new TestThread( *this );
76 TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
77 : CppUnitMini::TestThread( pool )
80 TestThread( TestThread& src )
81 : CppUnitMini::TestThread( src )
85 Map_find_string& getTest()
87 return reinterpret_cast<Map_find_string&>( m_Pool.m_Test );
90 virtual void init() { cds::threading::Manager::attachThread() ; }
91 virtual void fini() { cds::threading::Manager::detachThread() ; }
95 ValueVector& arr = getTest().m_Arr;
96 size_t const nPassCount = getTest().c_nPassCount;
99 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
100 if ( m_nThreadNo & 1 ) {
101 ValueVector::const_iterator itEnd = arr.end();
102 for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
103 auto bFound = rMap.contains( *(it->pKey) );
105 if ( check_result(bFound, rMap))
106 ++m_KeyExists.nSuccess;
108 ++m_KeyExists.nFailed;
111 if ( check_result(bFound, rMap))
112 ++m_KeyNotExists.nFailed;
114 ++m_KeyNotExists.nSuccess;
119 ValueVector::const_reverse_iterator itEnd = arr.rend();
120 for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
121 auto bFound = rMap.contains( *(it->pKey) );
123 if ( check_result(bFound, rMap))
124 ++m_KeyExists.nSuccess;
126 ++m_KeyExists.nFailed;
129 if ( check_result( bFound, rMap ))
130 ++m_KeyNotExists.nFailed;
132 ++m_KeyNotExists.nSuccess;
147 void generateSequence();
150 void find_string_test( Map& testMap )
152 typedef TestThread<Map> Thread;
153 cds::OS::Timer timer;
156 CPPUNIT_MSG( " Fill map...");
158 for ( size_t i = 0; i < m_Arr.size(); ++i ) {
159 // All keys in arrData are unique, insert() must be successful
160 if ( m_Arr[i].bExists )
161 CPPUNIT_ASSERT( check_result( testMap.insert( *(m_Arr[i].pKey), m_Arr[i] ), testMap ));
163 CPPUNIT_MSG( " Duration=" << timer.duration() );
165 CPPUNIT_MSG( " Searching...");
166 CppUnitMini::ThreadPool pool( *this );
167 pool.add( new Thread( pool, testMap ), c_nThreadCount );
169 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
171 // Postcondition: the number of success searching == the number of map item
172 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
173 Thread * pThread = static_cast<Thread *>( *it );
174 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == c_nMapSize * c_nPassCount );
175 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
176 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - c_nMapSize) * c_nPassCount );
177 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
180 check_before_cleanup( testMap );
183 additional_check( testMap );
184 print_stat( testMap );
185 additional_cleanup( testMap );
191 if ( Map::c_bLoadFactorDepended ) {
192 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
193 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
194 Map testMap( *this );
195 find_string_test( testMap );
196 if ( c_bPrintGCState )
201 Map testMap( *this );
202 find_string_test( testMap );
203 if ( c_bPrintGCState )
208 void setUpParams( const CppUnitMini::TestCfg& cfg );
210 # include "map2/map_defs.h"
211 CDSUNIT_DECLARE_MichaelMap
212 CDSUNIT_DECLARE_MichaelMap_nogc
213 CDSUNIT_DECLARE_SplitList
214 CDSUNIT_DECLARE_SplitList_nogc
215 CDSUNIT_DECLARE_SkipListMap
216 CDSUNIT_DECLARE_SkipListMap_nogc
217 CDSUNIT_DECLARE_EllenBinTreeMap
218 CDSUNIT_DECLARE_BronsonAVLTreeMap
219 CDSUNIT_DECLARE_FeldmanHashMap_md5
220 CDSUNIT_DECLARE_FeldmanHashMap_sha256
221 CDSUNIT_DECLARE_FeldmanHashMap_city
222 CDSUNIT_DECLARE_StripedMap
223 CDSUNIT_DECLARE_RefinableMap
224 CDSUNIT_DECLARE_CuckooMap
225 CDSUNIT_DECLARE_StdMap
226 CDSUNIT_DECLARE_StdMap_NoLock
228 CPPUNIT_TEST_SUITE(Map_find_string)
229 CDSUNIT_TEST_MichaelMap
230 CDSUNIT_TEST_MichaelMap_nogc
231 CDSUNIT_TEST_SplitList
232 CDSUNIT_TEST_SplitList_nogc
233 CDSUNIT_TEST_SkipListMap
234 CDSUNIT_TEST_SkipListMap_nogc
235 CDSUNIT_TEST_EllenBinTreeMap
236 CDSUNIT_TEST_BronsonAVLTreeMap
237 CDSUNIT_TEST_FeldmanHashMap_md5
238 CDSUNIT_TEST_FeldmanHashMap_sha256
239 CDSUNIT_TEST_FeldmanHashMap_city
240 CDSUNIT_TEST_CuckooMap
241 CDSUNIT_TEST_StripedMap
242 CDSUNIT_TEST_RefinableMap
244 CDSUNIT_TEST_StdMap_NoLock
245 CPPUNIT_TEST_SUITE_END();