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 "../../misc/common.h"
33 #include <cds/os/topology.h>
37 class Map_MinMax: public cds_test::stress_fixture
40 static size_t s_nInsThreadCount; // insert thread count
41 static size_t s_nExtractThreadCount; // extract thread count
42 static size_t s_nMapSize; // max map size
43 static size_t s_nPassCount;
45 static size_t s_nFeldmanMap_HeadBits;
46 static size_t s_nFeldmanMap_ArrayBits;
48 static size_t s_nLoadFactor; // current load factor
50 static void SetUpTestCase();
51 //static void TearDownTestCase();
55 typedef int value_type;
56 typedef std::pair<key_type const, value_type> pair_type;
58 atomics::atomic<size_t> m_nInsThreadCount;
68 class Inserter: public cds_test::thread
70 typedef cds_test::thread base_class;
72 std::vector<key_type> m_arr;
76 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
77 key_type keyMin = fixture.m_KeyMin;
78 key_type keyMax = fixture.m_KeyMax;
80 for ( key_type i = keyMin + 10; i >= keyMin; --i )
82 for ( key_type i = keyMax - 10; i <= keyMax; ++i )
84 shuffle( m_arr.begin(), m_arr.end());
88 size_t m_nInsertMinSuccess = 0;
89 size_t m_nInsertMinFailed = 0;
90 size_t m_nInsertMaxSuccess = 0;
91 size_t m_nInsertMaxFailed = 0;
94 Inserter( cds_test::thread_pool& pool, Map& map )
95 : base_class( pool, inserter_thread )
101 Inserter( Inserter& src )
108 virtual thread * clone()
110 return new Inserter( *this );
115 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
117 key_type keyMin = fixture.m_KeyMin;
118 key_type keyMax = fixture.m_KeyMax;
120 for ( size_t nPass = 0; nPass < s_nPassCount; ++nPass ) {
121 for ( key_type key : m_arr ) {
122 if ( m_Map.insert( key, key )) {
124 ++m_nInsertMinSuccess;
125 else if ( key == keyMax )
126 ++m_nInsertMaxSuccess;
130 ++m_nInsertMinFailed;
131 else if ( key == keyMax )
132 ++m_nInsertMaxFailed;
137 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
141 // Deletes odd keys from [0..N)
142 template <class GC, class Map >
143 class Extractor: public cds_test::thread
145 typedef cds_test::thread base_class;
149 size_t m_nDeleteMin = 0;
150 size_t m_nDeleteMinFailed = 0;
151 size_t m_nDeleteMax = 0;
152 size_t m_nDeleteMaxFailed = 0;
155 Extractor( cds_test::thread_pool& pool, Map& map )
156 : base_class( pool, extractor_thread )
160 Extractor( Extractor& src )
165 virtual thread * clone()
167 return new Extractor( *this );
174 typename Map::guarded_ptr gp;
175 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
177 key_type keyMin = fixture.m_KeyMin;
178 key_type keyMax = fixture.m_KeyMax;
181 gp = rMap.extract_min();
183 if ( gp->first == keyMin )
187 ++m_nDeleteMinFailed;
189 gp = rMap.extract_max();
191 if ( gp->first == keyMax )
195 ++m_nDeleteMaxFailed;
197 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
199 gp = rMap.extract_min();
201 if ( gp->first == keyMin )
205 ++m_nDeleteMinFailed;
207 gp = rMap.extract_max();
209 if ( gp->first == keyMax )
213 ++m_nDeleteMaxFailed;
217 template <class RCU, class Map >
218 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
220 typedef cds_test::thread base_class;
224 size_t m_nDeleteMin = 0;
225 size_t m_nDeleteMinFailed = 0;
226 size_t m_nDeleteMax = 0;
227 size_t m_nDeleteMaxFailed = 0;
230 Extractor( cds_test::thread_pool& pool, Map& map )
231 : base_class( pool, extractor_thread )
235 Extractor( Extractor& src )
240 virtual thread * clone()
242 return new Extractor( *this );
248 Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
250 key_type keyMin = fixture.m_KeyMin;
251 key_type keyMax = fixture.m_KeyMax;
253 static_assert( !Map::c_bExtractLockExternal, "No external RCU locking required" );
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;
271 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
273 auto res = rMap.extract_min_key();
275 if ( res.first == keyMin )
279 ++m_nDeleteMinFailed;
281 res = rMap.extract_max_key();
283 if ( res.first == keyMax )
287 ++m_nDeleteMaxFailed;
293 void do_test( Map& testMap )
295 typedef Inserter<Map> insert_thread;
296 typedef Extractor< typename Map::gc, Map > extract_thread;
298 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
301 std::vector<key_type> arr;
302 arr.resize( s_nMapSize );
303 for ( int i = 0; i < static_cast<int>( s_nMapSize ); ++i )
305 shuffle( arr.begin(), arr.end());
307 for ( key_type key : arr )
308 testMap.insert( key, key );
312 m_KeyMax = static_cast<int>( s_nMapSize - 1 );
314 cds_test::thread_pool& pool = get_pool();
315 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
316 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
318 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
319 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
320 << std::make_pair( "map_size", s_nMapSize )
321 << std::make_pair( "pass_count", s_nPassCount );
323 std::chrono::milliseconds duration = pool.run();
325 propout() << std::make_pair( "duration", duration );
327 size_t nInsertMinSuccess = 0;
328 size_t nInsertMinFailed = 0;
329 size_t nInsertMaxSuccess = 0;
330 size_t nInsertMaxFailed = 0;
331 size_t nDeleteMin = 0;
332 size_t nDeleteMinFailed = 0;
333 size_t nDeleteMax = 0;
334 size_t nDeleteMaxFailed = 0;
336 for ( size_t i = 0; i < pool.size(); ++i ) {
337 cds_test::thread& thr = pool.get( i );
338 switch ( thr.type()) {
339 case inserter_thread:
341 insert_thread& inserter = static_cast<insert_thread&>(thr);
342 nInsertMinSuccess += inserter.m_nInsertMinSuccess;
343 nInsertMinFailed += inserter.m_nInsertMinFailed;
344 nInsertMaxSuccess += inserter.m_nInsertMaxSuccess;
345 nInsertMaxFailed += inserter.m_nInsertMaxFailed;
348 case extractor_thread:
350 extract_thread& extractor = static_cast<extract_thread&>(thr);
351 nDeleteMin += extractor.m_nDeleteMin;
352 nDeleteMinFailed += extractor.m_nDeleteMinFailed;
353 nDeleteMax += extractor.m_nDeleteMax;
354 nDeleteMaxFailed += extractor.m_nDeleteMaxFailed;
362 EXPECT_EQ( nDeleteMinFailed, 0u );
363 EXPECT_EQ( nDeleteMaxFailed, 0u );
365 EXPECT_EQ( nDeleteMin, nInsertMinSuccess + 1 );
366 EXPECT_EQ( nDeleteMax, nInsertMaxSuccess + 1 );
369 << std::make_pair( "insert_min", nInsertMinSuccess + 1 )
370 << std::make_pair( "insert_min_double", nInsertMinFailed )
371 << std::make_pair( "insert_max", nInsertMaxSuccess + 1 )
372 << std::make_pair( "insert_max_double", nInsertMaxFailed )
373 << std::make_pair( "extract_min", nDeleteMin )
374 << std::make_pair( "extract_min_failed", nDeleteMinFailed )
375 << std::make_pair( "extract_max", nDeleteMax )
376 << std::make_pair( "extract_max_failed", nDeleteMaxFailed );
378 DEBUG(analyze( testMap ));
382 void analyze( Map& testMap )
384 print_stat( propout(), testMap );
386 check_before_cleanup( testMap );
388 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
390 additional_check( testMap );
391 additional_cleanup( testMap );
397 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
398 Map testMap( *this );