3 // defines concurrent access to map::nonconcurrent_iterator::Sequence::TValue::nAccess field
5 #include "map2/map_types.h"
6 #include "cppunit/thread.h"
9 #include <algorithm> // random_shuffle
11 // find int test in map<int> in mutithreaded mode
14 # define TEST_MAP(X) void X() { test<MapTypes<key_type, value_type>::X >() ; }
15 # define TEST_MAP_NOLF(X) void X() { test_nolf<MapTypes<key_type, value_type>::X >() ; }
16 # define TEST_MAP_EXTRACT(X) TEST_MAP(X)
17 # define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X)
19 class Map_find_int: public CppUnitMini::TestCase
21 static size_t c_nThreadCount; // thread count
22 static size_t c_nMapSize; // map size (count of searching item)
23 static size_t c_nPercentExists; // percent of existing keys in searching sequence
24 static size_t c_nPassCount;
25 static size_t c_nMaxLoadFactor; // maximum load factor
26 static bool c_bPrintGCState;
28 typedef CppUnitMini::TestCase Base;
29 typedef size_t key_type;
31 key_type nKey ; // key
32 bool bExists ; // true - key in map, false - key not in map
35 typedef std::vector<value_type> ValueVector;
37 size_t m_nRealMapSize;
38 bool m_bSequenceInitialized;
40 void generateSequence();
42 template <typename Iterator, typename Map>
43 static bool check_result( Iterator const& it, Map const& map )
45 return it != map.end();
47 template <typename Map>
48 static bool check_result( bool b, Map const& )
54 class TestThread: public CppUnitMini::TestThread
58 virtual TestThread * clone()
60 return new TestThread( *this );
77 TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
78 : CppUnitMini::TestThread( pool )
81 TestThread( TestThread& src )
82 : CppUnitMini::TestThread( src )
86 Map_find_int& getTest()
88 return reinterpret_cast<Map_find_int&>( m_Pool.m_Test );
91 virtual void init() { cds::threading::Manager::attachThread() ; }
92 virtual void fini() { cds::threading::Manager::detachThread() ; }
96 ValueVector& arr = getTest().m_Arr;
97 //size_t nSize = arr.size();
100 for ( size_t nPass = 0; nPass < c_nPassCount; ++nPass ) {
101 if ( m_nThreadNo & 1 ) {
102 ValueVector::const_iterator itEnd = arr.end();
103 for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
104 auto bFound = rMap.find( it->nKey );
106 if ( check_result( bFound, rMap ))
107 ++m_KeyExists.nSuccess;
109 //rMap.find( it->nKey );
110 ++m_KeyExists.nFailed;
114 if ( check_result( bFound, rMap )) {
115 //rMap.find( it->nKey );
116 ++m_KeyNotExists.nFailed;
119 ++m_KeyNotExists.nSuccess;
124 ValueVector::const_reverse_iterator itEnd = arr.rend();
125 for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
126 auto bFound = rMap.find( it->nKey );
128 if ( check_result( bFound, rMap ))
129 ++m_KeyExists.nSuccess;
131 //rMap.find( it->nKey );
132 ++m_KeyExists.nFailed;
136 if ( check_result( bFound, rMap )) {
137 //rMap.find( it->nKey );
138 ++m_KeyNotExists.nFailed;
141 ++m_KeyNotExists.nSuccess;
152 void find_int_test( Map& testMap )
154 typedef TestThread<Map> Thread;
155 cds::OS::Timer timer;
158 CPPUNIT_MSG( " Fill map with " << m_Arr.size() << " items...");
160 for ( size_t i = 0; i < m_Arr.size(); ++i ) {
161 if ( m_Arr[i].bExists ) {
162 CPPUNIT_ASSERT( check_result( testMap.insert( m_Arr[i].nKey, m_Arr[i] ), testMap ));
165 CPPUNIT_MSG( " Duration=" << timer.duration() );
167 CPPUNIT_MSG( " Searching...");
168 CppUnitMini::ThreadPool pool( *this );
169 pool.add( new Thread( pool, testMap ), c_nThreadCount );
171 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
173 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
174 Thread * pThread = static_cast<Thread *>( *it );
175 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
176 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
177 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
178 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
181 check_before_cleanup( testMap );
184 additional_check( testMap );
185 print_stat( testMap );
186 additional_cleanup( testMap );
189 void initTestSequence();
194 if ( !m_bSequenceInitialized )
197 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
198 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
199 Map testMap( c_nMapSize, nLoadFactor );
200 find_int_test( testMap );
201 if ( c_bPrintGCState )
209 if ( !m_bSequenceInitialized )
213 find_int_test( testMap );
214 if ( c_bPrintGCState )
218 void setUpParams( const CppUnitMini::TestCfg& cfg );
220 void run_MichaelMap(const char *in_name, bool invert = false);
221 void run_SplitList(const char *in_name, bool invert = false);
222 void run_StripedMap(const char *in_name, bool invert = false);
223 void run_RefinableMap(const char *in_name, bool invert = false);
224 void run_CuckooMap(const char *in_name, bool invert = false);
225 void run_SkipListMap(const char *in_name, bool invert = false);
226 void run_EllenBinTreeMap(const char *in_name, bool invert = false);
227 void run_BronsonAVLTreeMap(const char *in_name, bool invert = false);
228 void run_StdMap(const char *in_name, bool invert = false);
230 virtual void myRun(const char *in_name, bool invert = false);
234 : m_bSequenceInitialized( false )
237 # include "map2/map_defs.h"
238 CDSUNIT_DECLARE_MichaelMap
239 CDSUNIT_DECLARE_MichaelMap_nogc
240 CDSUNIT_DECLARE_SplitList
241 CDSUNIT_DECLARE_SplitList_nogc
242 CDSUNIT_DECLARE_SkipListMap
243 CDSUNIT_DECLARE_SkipListMap_nogc
244 CDSUNIT_DECLARE_EllenBinTreeMap
245 CDSUNIT_DECLARE_BronsonAVLTreeMap
246 CDSUNIT_DECLARE_StripedMap
247 CDSUNIT_DECLARE_RefinableMap
248 CDSUNIT_DECLARE_CuckooMap
249 CDSUNIT_DECLARE_StdMap