3 // defines concurrent access to map::nonconcurrent_iterator::Sequence::TValue::nAccess field
5 #include "map2/map_type.h"
6 #include "cppunit/thread.h"
10 // find int test in map<int> in mutithreaded mode
13 #define TEST_CASE(TAG, X) void X();
15 class Map_find_int: public CppUnitMini::TestCase
18 size_t c_nThreadCount = 8; // thread count
19 size_t c_nMapSize = 10000000; // map size (count of searching item)
20 size_t c_nPercentExists = 50; // percent of existing keys in searching sequence
21 size_t c_nPassCount = 2;
22 size_t c_nMaxLoadFactor = 8; // maximum load factor
23 bool c_bPrintGCState = true;
25 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
26 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
27 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
29 size_t c_nFeldmanMap_HeadBits = 10;
30 size_t c_nFeldmanMap_ArrayBits = 4;
32 size_t c_nLoadFactor; // current load factor
35 typedef size_t key_type;
37 key_type nKey ; // key
38 bool bExists ; // true - key in map, false - key not in map
41 typedef std::vector<value_type> ValueVector;
43 size_t m_nRealMapSize;
45 void generateSequence();
47 template <typename Iterator, typename Map>
48 static bool check_result( Iterator const& it, Map const& map )
50 return it != map.end();
52 template <typename Map>
53 static bool check_result( bool b, Map const& )
59 class TestThread: public CppUnitMini::TestThread
63 virtual TestThread * clone()
65 return new TestThread( *this );
82 TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
83 : CppUnitMini::TestThread( pool )
86 TestThread( TestThread& src )
87 : CppUnitMini::TestThread( src )
91 Map_find_int& getTest()
93 return reinterpret_cast<Map_find_int&>( m_Pool.m_Test );
96 virtual void init() { cds::threading::Manager::attachThread() ; }
97 virtual void fini() { cds::threading::Manager::detachThread() ; }
101 ValueVector& arr = getTest().m_Arr;
102 size_t const nPassCount = getTest().c_nPassCount;
105 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
106 if ( m_nThreadNo & 1 ) {
107 ValueVector::const_iterator itEnd = arr.end();
108 for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
109 auto bFound = rMap.contains( it->nKey );
111 if ( check_result( bFound, rMap ))
112 ++m_KeyExists.nSuccess;
114 //rMap.find( it->nKey );
115 ++m_KeyExists.nFailed;
119 if ( check_result( bFound, rMap )) {
120 //rMap.find( it->nKey );
121 ++m_KeyNotExists.nFailed;
124 ++m_KeyNotExists.nSuccess;
129 ValueVector::const_reverse_iterator itEnd = arr.rend();
130 for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
131 auto bFound = rMap.contains( it->nKey );
133 if ( check_result( bFound, rMap ))
134 ++m_KeyExists.nSuccess;
136 //rMap.find( it->nKey );
137 ++m_KeyExists.nFailed;
141 if ( check_result( bFound, rMap )) {
142 //rMap.find( it->nKey );
143 ++m_KeyNotExists.nFailed;
146 ++m_KeyNotExists.nSuccess;
157 void find_int_test( Map& testMap )
159 typedef TestThread<Map> Thread;
160 cds::OS::Timer timer;
163 CPPUNIT_MSG( " Fill map with " << m_Arr.size() << " items...");
165 for ( size_t i = 0; i < m_Arr.size(); ++i ) {
166 if ( m_Arr[i].bExists ) {
167 CPPUNIT_ASSERT( check_result( testMap.insert( m_Arr[i].nKey, m_Arr[i] ), testMap ));
170 CPPUNIT_MSG( " Duration=" << timer.duration() );
172 CPPUNIT_MSG( " Searching...");
173 CppUnitMini::ThreadPool pool( *this );
174 pool.add( new Thread( pool, testMap ), c_nThreadCount );
176 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
178 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
179 Thread * pThread = static_cast<Thread *>( *it );
180 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
181 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
182 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
183 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
186 check_before_cleanup( testMap );
189 additional_check( testMap );
190 print_stat( testMap );
191 additional_cleanup( testMap );
197 if ( Map::c_bLoadFactorDepended ) {
198 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
199 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
200 Map testMap( *this );
201 find_int_test( testMap );
202 if ( c_bPrintGCState )
207 Map testMap( *this );
208 find_int_test( testMap );
209 if ( c_bPrintGCState )
214 void setUpParams( const CppUnitMini::TestCfg& cfg );
221 # include "map2/map_defs.h"
222 CDSUNIT_DECLARE_MichaelMap
223 CDSUNIT_DECLARE_MichaelMap_nogc
224 CDSUNIT_DECLARE_SplitList
225 CDSUNIT_DECLARE_SplitList_nogc
226 CDSUNIT_DECLARE_SkipListMap
227 CDSUNIT_DECLARE_SkipListMap_nogc
228 CDSUNIT_DECLARE_EllenBinTreeMap
229 CDSUNIT_DECLARE_BronsonAVLTreeMap
230 CDSUNIT_DECLARE_FeldmanHashMap
231 CDSUNIT_DECLARE_StripedMap
232 CDSUNIT_DECLARE_RefinableMap
233 CDSUNIT_DECLARE_CuckooMap
234 CDSUNIT_DECLARE_StdMap
235 CDSUNIT_DECLARE_StdMap_NoLock
237 CPPUNIT_TEST_SUITE(Map_find_int)
238 CDSUNIT_TEST_MichaelMap
239 CDSUNIT_TEST_MichaelMap_nogc
240 CDSUNIT_TEST_SplitList
241 CDSUNIT_TEST_SplitList_nogc
242 CDSUNIT_TEST_SkipListMap
243 CDSUNIT_TEST_SkipListMap_nogc
244 CDSUNIT_TEST_EllenBinTreeMap
245 CDSUNIT_TEST_BronsonAVLTreeMap
246 CDSUNIT_TEST_FeldmanHashMap
247 CDSUNIT_TEST_CuckooMap
248 CDSUNIT_TEST_StripedMap
249 CDSUNIT_TEST_RefinableMap
251 CDSUNIT_TEST_StdMap_NoLock
252 CPPUNIT_TEST_SUITE_END();