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 );
200 template <class RCU, class Map >
201 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
203 typedef cds_test::thread base_class;
207 size_t m_nDeleteMin = 0;
208 size_t m_nDeleteMinFailed = 0;
209 size_t m_nDeleteMax = 0;
210 size_t m_nDeleteMaxFailed = 0;
213 Extractor( cds_test::thread_pool& pool, Map& map )
214 : base_class( pool, extractor_thread )
218 Extractor( Extractor& src )
223 virtual thread * clone()
225 return new Extractor( *this );
231 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
233 key_type keyMin = fixture.m_KeyMin;
234 key_type keyMax = fixture.m_KeyMax;
236 static_assert( !Map::c_bExtractLockExternal, "No external RCU locking required" );
239 auto res = rMap.extract_min_key();
241 if ( res.first == keyMin )
245 ++m_nDeleteMinFailed;
247 res = rMap.extract_max_key();
249 if ( res.first == keyMax )
253 ++m_nDeleteMaxFailed;
254 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
256 auto res = rMap.extract_min_key();
258 if ( res.first == keyMin )
262 ++m_nDeleteMinFailed;
264 res = rMap.extract_max_key();
266 if ( res.first == keyMax )
270 ++m_nDeleteMaxFailed;
276 void do_test( Map& testMap )
278 typedef Inserter<Map> insert_thread;
279 typedef Extractor< typename Map::gc, Map > extract_thread;
281 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
284 std::vector<key_type> arr;
285 arr.resize( s_nMapSize );
286 for ( int i = 0; i < static_cast<int>( s_nMapSize ); ++i )
288 shuffle( arr.begin(), arr.end() );
290 for ( key_type key : arr )
291 testMap.insert( key, key );
295 m_KeyMax = static_cast<int>( s_nMapSize - 1 );
297 cds_test::thread_pool& pool = get_pool();
298 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
299 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
301 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
302 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
303 << std::make_pair( "map_size", s_nMapSize )
304 << std::make_pair( "pass_count", s_nPassCount );
306 std::chrono::milliseconds duration = pool.run();
308 propout() << std::make_pair( "duration", duration );
310 size_t nInsertMinSuccess = 0;
311 size_t nInsertMinFailed = 0;
312 size_t nInsertMaxSuccess = 0;
313 size_t nInsertMaxFailed = 0;
314 size_t nDeleteMin = 0;
315 size_t nDeleteMinFailed = 0;
316 size_t nDeleteMax = 0;
317 size_t nDeleteMaxFailed = 0;
319 for ( size_t i = 0; i < pool.size(); ++i ) {
320 cds_test::thread& thr = pool.get( i );
321 switch ( thr.type()) {
322 case inserter_thread:
324 insert_thread& inserter = static_cast<insert_thread&>(thr);
325 nInsertMinSuccess += inserter.m_nInsertMinSuccess;
326 nInsertMinFailed += inserter.m_nInsertMinFailed;
327 nInsertMaxSuccess += inserter.m_nInsertMaxSuccess;
328 nInsertMaxFailed += inserter.m_nInsertMaxFailed;
331 case extractor_thread:
333 extract_thread& extractor = static_cast<extract_thread&>(thr);
334 nDeleteMin += extractor.m_nDeleteMin;
335 nDeleteMinFailed += extractor.m_nDeleteMinFailed;
336 nDeleteMax += extractor.m_nDeleteMax;
337 nDeleteMaxFailed += extractor.m_nDeleteMaxFailed;
345 EXPECT_EQ( nDeleteMinFailed, 0u );
346 EXPECT_EQ( nDeleteMaxFailed, 0u );
348 EXPECT_EQ( nDeleteMin, nInsertMinSuccess + 1 );
349 EXPECT_EQ( nDeleteMax, nInsertMaxSuccess + 1 );
352 << std::make_pair( "insert_min", nInsertMinSuccess + 1 )
353 << std::make_pair( "insert_min_double", nInsertMinFailed )
354 << std::make_pair( "insert_max", nInsertMaxSuccess + 1 )
355 << std::make_pair( "insert_max_double", nInsertMaxFailed )
356 << std::make_pair( "extract_min", nDeleteMin )
357 << std::make_pair( "extract_min_failed", nDeleteMinFailed )
358 << std::make_pair( "extract_max", nDeleteMax )
359 << std::make_pair( "extract_max_failed", nDeleteMaxFailed );
365 void analyze( Map& testMap )
367 print_stat( propout(), testMap );
369 check_before_cleanup( testMap );
371 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
373 additional_check( testMap );
374 additional_cleanup( testMap );
380 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
381 Map testMap( *this );