2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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.
32 #include <cds/os/topology.h>
36 class Map_MinMax: public cds_test::stress_fixture
39 static size_t s_nInsThreadCount; // insert thread count
40 static size_t s_nExtractThreadCount; // extract thread count
41 static size_t s_nMapSize; // max map size
42 static size_t s_nPassCount;
44 static size_t s_nFeldmanMap_HeadBits;
45 static size_t s_nFeldmanMap_ArrayBits;
47 static size_t s_nLoadFactor; // current load factor
49 static void SetUpTestCase();
50 //static void TearDownTestCase();
54 typedef int value_type;
55 typedef std::pair<key_type const, value_type> pair_type;
57 atomics::atomic<size_t> m_nInsThreadCount;
67 class Inserter: public cds_test::thread
69 typedef cds_test::thread base_class;
71 std::vector<key_type> m_arr;
75 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
76 key_type keyMin = fixture.m_KeyMin;
77 key_type keyMax = fixture.m_KeyMax;
79 for ( key_type i = keyMin + 10; i >= keyMin; --i )
81 for ( key_type i = keyMax - 10; i <= keyMax; ++i )
83 shuffle( m_arr.begin(), m_arr.end() );
87 size_t m_nInsertMinSuccess = 0;
88 size_t m_nInsertMinFailed = 0;
89 size_t m_nInsertMaxSuccess = 0;
90 size_t m_nInsertMaxFailed = 0;
93 Inserter( cds_test::thread_pool& pool, Map& map )
94 : base_class( pool, inserter_thread )
100 Inserter( Inserter& src )
107 virtual thread * clone()
109 return new Inserter( *this );
114 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
116 key_type keyMin = fixture.m_KeyMin;
117 key_type keyMax = fixture.m_KeyMax;
119 for ( size_t nPass = 0; nPass < s_nPassCount; ++nPass ) {
120 for ( key_type key : m_arr ) {
121 if ( m_Map.insert( key, key ) ) {
123 ++m_nInsertMinSuccess;
124 else if ( key == keyMax )
125 ++m_nInsertMaxSuccess;
129 ++m_nInsertMinFailed;
130 else if ( key == keyMax )
131 ++m_nInsertMaxFailed;
136 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
140 // Deletes odd keys from [0..N)
141 template <class GC, class Map >
142 class Extractor: public cds_test::thread
144 typedef cds_test::thread base_class;
148 size_t m_nDeleteMin = 0;
149 size_t m_nDeleteMinFailed = 0;
150 size_t m_nDeleteMax = 0;
151 size_t m_nDeleteMaxFailed = 0;
154 Extractor( cds_test::thread_pool& pool, Map& map )
155 : base_class( pool, extractor_thread )
159 Extractor( Extractor& src )
164 virtual thread * clone()
166 return new Extractor( *this );
173 typename Map::guarded_ptr gp;
174 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
176 key_type keyMin = fixture.m_KeyMin;
177 key_type keyMax = fixture.m_KeyMax;
180 gp = rMap.extract_min();
182 if ( gp->first == keyMin )
186 ++m_nDeleteMinFailed;
188 gp = rMap.extract_max();
190 if ( gp->first == keyMax )
194 ++m_nDeleteMaxFailed;
196 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
198 gp = rMap.extract_min();
200 if ( gp->first == keyMin )
204 ++m_nDeleteMinFailed;
206 gp = rMap.extract_max();
208 if ( gp->first == keyMax )
212 ++m_nDeleteMaxFailed;
216 template <class RCU, class Map >
217 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
219 typedef cds_test::thread base_class;
223 size_t m_nDeleteMin = 0;
224 size_t m_nDeleteMinFailed = 0;
225 size_t m_nDeleteMax = 0;
226 size_t m_nDeleteMaxFailed = 0;
229 Extractor( cds_test::thread_pool& pool, Map& map )
230 : base_class( pool, extractor_thread )
234 Extractor( Extractor& src )
239 virtual thread * clone()
241 return new Extractor( *this );
247 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
249 key_type keyMin = fixture.m_KeyMin;
250 key_type keyMax = fixture.m_KeyMax;
252 static_assert( !Map::c_bExtractLockExternal, "No external RCU locking required" );
255 auto res = rMap.extract_min_key();
257 if ( res.first == keyMin )
261 ++m_nDeleteMinFailed;
263 res = rMap.extract_max_key();
265 if ( res.first == keyMax )
269 ++m_nDeleteMaxFailed;
270 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
272 auto res = rMap.extract_min_key();
274 if ( res.first == keyMin )
278 ++m_nDeleteMinFailed;
280 res = rMap.extract_max_key();
282 if ( res.first == keyMax )
286 ++m_nDeleteMaxFailed;
292 void do_test( Map& testMap )
294 typedef Inserter<Map> insert_thread;
295 typedef Extractor< typename Map::gc, Map > extract_thread;
297 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
300 std::vector<key_type> arr;
301 arr.resize( s_nMapSize );
302 for ( int i = 0; i < static_cast<int>( s_nMapSize ); ++i )
304 shuffle( arr.begin(), arr.end() );
306 for ( key_type key : arr )
307 testMap.insert( key, key );
311 m_KeyMax = static_cast<int>( s_nMapSize - 1 );
313 cds_test::thread_pool& pool = get_pool();
314 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
315 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
317 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
318 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
319 << std::make_pair( "map_size", s_nMapSize )
320 << std::make_pair( "pass_count", s_nPassCount );
322 std::chrono::milliseconds duration = pool.run();
324 propout() << std::make_pair( "duration", duration );
326 size_t nInsertMinSuccess = 0;
327 size_t nInsertMinFailed = 0;
328 size_t nInsertMaxSuccess = 0;
329 size_t nInsertMaxFailed = 0;
330 size_t nDeleteMin = 0;
331 size_t nDeleteMinFailed = 0;
332 size_t nDeleteMax = 0;
333 size_t nDeleteMaxFailed = 0;
335 for ( size_t i = 0; i < pool.size(); ++i ) {
336 cds_test::thread& thr = pool.get( i );
337 switch ( thr.type()) {
338 case inserter_thread:
340 insert_thread& inserter = static_cast<insert_thread&>(thr);
341 nInsertMinSuccess += inserter.m_nInsertMinSuccess;
342 nInsertMinFailed += inserter.m_nInsertMinFailed;
343 nInsertMaxSuccess += inserter.m_nInsertMaxSuccess;
344 nInsertMaxFailed += inserter.m_nInsertMaxFailed;
347 case extractor_thread:
349 extract_thread& extractor = static_cast<extract_thread&>(thr);
350 nDeleteMin += extractor.m_nDeleteMin;
351 nDeleteMinFailed += extractor.m_nDeleteMinFailed;
352 nDeleteMax += extractor.m_nDeleteMax;
353 nDeleteMaxFailed += extractor.m_nDeleteMaxFailed;
361 EXPECT_EQ( nDeleteMinFailed, 0u );
362 EXPECT_EQ( nDeleteMaxFailed, 0u );
364 EXPECT_EQ( nDeleteMin, nInsertMinSuccess + 1 );
365 EXPECT_EQ( nDeleteMax, nInsertMaxSuccess + 1 );
368 << std::make_pair( "insert_min", nInsertMinSuccess + 1 )
369 << std::make_pair( "insert_min_double", nInsertMinFailed )
370 << std::make_pair( "insert_max", nInsertMaxSuccess + 1 )
371 << std::make_pair( "insert_max_double", nInsertMaxFailed )
372 << std::make_pair( "extract_min", nDeleteMin )
373 << std::make_pair( "extract_min_failed", nDeleteMinFailed )
374 << std::make_pair( "extract_max", nDeleteMax )
375 << std::make_pair( "extract_max_failed", nDeleteMaxFailed );
381 void analyze( Map& testMap )
383 print_stat( propout(), testMap );
385 check_before_cleanup( testMap );
387 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
389 additional_check( testMap );
390 additional_cleanup( testMap );
396 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
397 Map testMap( *this );