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 #include "map2/map_type.h"
32 #include "cppunit/thread.h"
38 #define TEST_CASE(TAG, X) void X();
40 class Map_find_string: public CppUnitMini::TestCase
43 size_t c_nThreadCount = 8; // thread count
44 size_t c_nMapSize = 10000000; // map size (count of searching item)
45 size_t c_nPercentExists = 50; // percent of existing keys in searching sequence
46 size_t c_nPassCount = 2;
47 size_t c_nMaxLoadFactor = 8; // maximum load factor
48 bool c_bPrintGCState = true;
50 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
51 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
52 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
54 size_t c_nFeldmanMap_HeadBits = 10;
55 size_t c_nFeldmanMap_ArrayBits = 4;
57 size_t c_nLoadFactor; // current load factor
60 typedef std::string key_type;
62 std::string const * pKey;
63 bool bExists ; // true - key in map, false - key not in map
66 typedef std::vector<value_type> ValueVector;
69 template <typename Iterator, typename Map>
70 static bool check_result( Iterator const& it, Map const& map )
72 return it != map.end();
74 template <typename Map>
75 static bool check_result( bool b, Map const& )
81 class TestThread: public CppUnitMini::TestThread
85 virtual TestThread * clone()
87 return new TestThread( *this );
104 TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
105 : CppUnitMini::TestThread( pool )
108 TestThread( TestThread& src )
109 : CppUnitMini::TestThread( src )
113 Map_find_string& getTest()
115 return reinterpret_cast<Map_find_string&>( m_Pool.m_Test );
118 virtual void init() { cds::threading::Manager::attachThread() ; }
119 virtual void fini() { cds::threading::Manager::detachThread() ; }
123 ValueVector& arr = getTest().m_Arr;
124 size_t const nPassCount = getTest().c_nPassCount;
127 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
128 if ( m_nThreadNo & 1 ) {
129 ValueVector::const_iterator itEnd = arr.end();
130 for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
131 auto bFound = rMap.contains( *(it->pKey) );
133 if ( check_result(bFound, rMap))
134 ++m_KeyExists.nSuccess;
136 ++m_KeyExists.nFailed;
139 if ( check_result(bFound, rMap))
140 ++m_KeyNotExists.nFailed;
142 ++m_KeyNotExists.nSuccess;
147 ValueVector::const_reverse_iterator itEnd = arr.rend();
148 for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
149 auto bFound = rMap.contains( *(it->pKey) );
151 if ( check_result(bFound, rMap))
152 ++m_KeyExists.nSuccess;
154 ++m_KeyExists.nFailed;
157 if ( check_result( bFound, rMap ))
158 ++m_KeyNotExists.nFailed;
160 ++m_KeyNotExists.nSuccess;
175 void generateSequence();
178 void find_string_test( Map& testMap )
180 typedef TestThread<Map> Thread;
181 cds::OS::Timer timer;
183 CPPUNIT_MSG( "Map size=" << c_nMapSize << " find key loop=" << m_Arr.size() << " (" << c_nPercentExists << "% success)" );
184 CPPUNIT_MSG( "Thread count=" << c_nThreadCount << " Pass count=" << c_nPassCount );
187 CPPUNIT_MSG( " Fill map...");
189 for ( size_t i = 0; i < m_Arr.size(); ++i ) {
190 // All keys in arrData are unique, insert() must be successful
191 if ( m_Arr[i].bExists )
192 CPPUNIT_ASSERT( check_result( testMap.insert( *(m_Arr[i].pKey), m_Arr[i] ), testMap ));
194 CPPUNIT_MSG( " Duration=" << timer.duration() );
196 CPPUNIT_MSG( " Searching...");
197 CppUnitMini::ThreadPool pool( *this );
198 pool.add( new Thread( pool, testMap ), c_nThreadCount );
200 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
202 // Postcondition: the number of success searching == the number of map item
203 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
204 Thread * pThread = static_cast<Thread *>( *it );
205 CPPUNIT_CHECK( pThread->m_KeyExists.nSuccess == c_nMapSize * c_nPassCount );
206 CPPUNIT_CHECK( pThread->m_KeyExists.nFailed == 0 );
207 CPPUNIT_CHECK( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - c_nMapSize) * c_nPassCount );
208 CPPUNIT_CHECK( pThread->m_KeyNotExists.nFailed == 0 );
211 check_before_cleanup( testMap );
214 additional_check( testMap );
215 print_stat( testMap );
216 additional_cleanup( testMap );
222 if ( Map::c_bLoadFactorDepended ) {
223 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
224 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
225 Map testMap( *this );
226 find_string_test( testMap );
227 if ( c_bPrintGCState )
232 Map testMap( *this );
233 find_string_test( testMap );
234 if ( c_bPrintGCState )
239 void setUpParams( const CppUnitMini::TestCfg& cfg );
241 # include "map2/map_defs.h"
242 CDSUNIT_DECLARE_MichaelMap
243 CDSUNIT_DECLARE_MichaelMap_nogc
244 CDSUNIT_DECLARE_SplitList
245 CDSUNIT_DECLARE_SplitList_nogc
246 CDSUNIT_DECLARE_SkipListMap
247 CDSUNIT_DECLARE_SkipListMap_nogc
248 CDSUNIT_DECLARE_EllenBinTreeMap
249 CDSUNIT_DECLARE_BronsonAVLTreeMap
250 CDSUNIT_DECLARE_FeldmanHashMap_city
251 CDSUNIT_DECLARE_StripedMap
252 CDSUNIT_DECLARE_RefinableMap
253 CDSUNIT_DECLARE_CuckooMap
254 CDSUNIT_DECLARE_StdMap
255 CDSUNIT_DECLARE_StdMap_NoLock
257 CPPUNIT_TEST_SUITE(Map_find_string)
258 CDSUNIT_TEST_MichaelMap
259 CDSUNIT_TEST_MichaelMap_nogc
260 CDSUNIT_TEST_SplitList
261 CDSUNIT_TEST_SplitList_nogc
262 CDSUNIT_TEST_SkipListMap
263 CDSUNIT_TEST_SkipListMap_nogc
264 CDSUNIT_TEST_EllenBinTreeMap
265 CDSUNIT_TEST_BronsonAVLTreeMap
266 CDSUNIT_TEST_FeldmanHashMap_city
267 CDSUNIT_TEST_CuckooMap
268 CDSUNIT_TEST_StripedMap
269 CDSUNIT_TEST_RefinableMap
271 CDSUNIT_TEST_StdMap_NoLock
272 CPPUNIT_TEST_SUITE_END();