2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 // defines concurrent access to map::nonconcurrent_iterator::Sequence::TValue::nAccess field
33 #include "map2/map_type.h"
34 #include "cppunit/thread.h"
38 // find int test in map<int> in mutithreaded mode
41 #define TEST_CASE(TAG, X) void X();
43 class Map_find_int: public CppUnitMini::TestCase
46 size_t c_nThreadCount = 8; // thread count
47 size_t c_nMapSize = 10000000; // map size (count of searching item)
48 size_t c_nPercentExists = 50; // percent of existing keys in searching sequence
49 size_t c_nPassCount = 2;
50 size_t c_nMaxLoadFactor = 8; // maximum load factor
51 bool c_bPrintGCState = true;
53 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
54 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
55 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
57 size_t c_nFeldmanMap_HeadBits = 10;
58 size_t c_nFeldmanMap_ArrayBits = 4;
60 size_t c_nLoadFactor; // current load factor
63 typedef size_t key_type;
65 key_type nKey ; // key
66 bool bExists ; // true - key in map, false - key not in map
69 typedef std::vector<value_type> ValueVector;
71 size_t m_nRealMapSize;
73 void generateSequence();
75 template <typename Iterator, typename Map>
76 static bool check_result( Iterator const& it, Map const& map )
78 return it != map.end();
80 template <typename Map>
81 static bool check_result( bool b, Map const& )
87 class TestThread: public CppUnitMini::TestThread
91 virtual TestThread * clone()
93 return new TestThread( *this );
110 TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
111 : CppUnitMini::TestThread( pool )
114 TestThread( TestThread& src )
115 : CppUnitMini::TestThread( src )
119 Map_find_int& getTest()
121 return reinterpret_cast<Map_find_int&>( m_Pool.m_Test );
124 virtual void init() { cds::threading::Manager::attachThread() ; }
125 virtual void fini() { cds::threading::Manager::detachThread() ; }
129 ValueVector& arr = getTest().m_Arr;
130 size_t const nPassCount = getTest().c_nPassCount;
133 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
134 if ( m_nThreadNo & 1 ) {
135 ValueVector::const_iterator itEnd = arr.end();
136 for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
137 auto bFound = rMap.contains( it->nKey );
139 if ( check_result( bFound, rMap ))
140 ++m_KeyExists.nSuccess;
142 //rMap.find( it->nKey );
143 ++m_KeyExists.nFailed;
147 if ( check_result( bFound, rMap )) {
148 //rMap.find( it->nKey );
149 ++m_KeyNotExists.nFailed;
152 ++m_KeyNotExists.nSuccess;
157 ValueVector::const_reverse_iterator itEnd = arr.rend();
158 for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
159 auto bFound = rMap.contains( it->nKey );
161 if ( check_result( bFound, rMap ))
162 ++m_KeyExists.nSuccess;
164 //rMap.find( it->nKey );
165 ++m_KeyExists.nFailed;
169 if ( check_result( bFound, rMap )) {
170 //rMap.find( it->nKey );
171 ++m_KeyNotExists.nFailed;
174 ++m_KeyNotExists.nSuccess;
185 void find_int_test( Map& testMap )
187 typedef TestThread<Map> Thread;
188 cds::OS::Timer timer;
191 CPPUNIT_MSG( " Fill map with " << m_Arr.size() << " items...");
193 for ( size_t i = 0; i < m_Arr.size(); ++i ) {
194 if ( m_Arr[i].bExists ) {
195 CPPUNIT_ASSERT( check_result( testMap.insert( m_Arr[i].nKey, m_Arr[i] ), testMap ));
198 CPPUNIT_MSG( " Duration=" << timer.duration() );
200 CPPUNIT_MSG( " Searching...");
201 CppUnitMini::ThreadPool pool( *this );
202 pool.add( new Thread( pool, testMap ), c_nThreadCount );
204 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
206 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
207 Thread * pThread = static_cast<Thread *>( *it );
208 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
209 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
210 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
211 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
214 check_before_cleanup( testMap );
217 additional_check( testMap );
218 print_stat( testMap );
219 additional_cleanup( testMap );
225 if ( Map::c_bLoadFactorDepended ) {
226 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
227 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
228 Map testMap( *this );
229 find_int_test( testMap );
230 if ( c_bPrintGCState )
235 Map testMap( *this );
236 find_int_test( testMap );
237 if ( c_bPrintGCState )
242 void setUpParams( const CppUnitMini::TestCfg& cfg );
249 # include "map2/map_defs.h"
250 CDSUNIT_DECLARE_MichaelMap
251 CDSUNIT_DECLARE_MichaelMap_nogc
252 CDSUNIT_DECLARE_SplitList
253 CDSUNIT_DECLARE_SplitList_nogc
254 CDSUNIT_DECLARE_SkipListMap
255 CDSUNIT_DECLARE_SkipListMap_nogc
256 CDSUNIT_DECLARE_EllenBinTreeMap
257 CDSUNIT_DECLARE_BronsonAVLTreeMap
258 CDSUNIT_DECLARE_FeldmanHashMap
259 CDSUNIT_DECLARE_StripedMap
260 CDSUNIT_DECLARE_RefinableMap
261 CDSUNIT_DECLARE_CuckooMap
262 CDSUNIT_DECLARE_StdMap
263 CDSUNIT_DECLARE_StdMap_NoLock
265 CPPUNIT_TEST_SUITE(Map_find_int)
266 CDSUNIT_TEST_MichaelMap
267 CDSUNIT_TEST_MichaelMap_nogc
268 CDSUNIT_TEST_SplitList
269 CDSUNIT_TEST_SplitList_nogc
270 CDSUNIT_TEST_SkipListMap
271 CDSUNIT_TEST_SkipListMap_nogc
272 CDSUNIT_TEST_EllenBinTreeMap
273 CDSUNIT_TEST_BronsonAVLTreeMap
274 CDSUNIT_TEST_FeldmanHashMap
275 CDSUNIT_TEST_CuckooMap
276 CDSUNIT_TEST_StripedMap
277 CDSUNIT_TEST_RefinableMap
279 CDSUNIT_TEST_StdMap_NoLock
280 CPPUNIT_TEST_SUITE_END();