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.
35 #define TEST_CASE(TAG, X) void X();
37 class Set_InsDel_string: public cds_test::stress_fixture
40 static size_t s_nSetSize; // set size
41 static size_t s_nInsertThreadCount; // count of insertion thread
42 static size_t s_nDeleteThreadCount; // count of deletion thread
43 static size_t s_nThreadPassCount; // pass count for each thread
44 static size_t s_nMaxLoadFactor; // maximum load factor
46 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
47 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
48 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
50 static size_t s_nFeldmanSet_HeadBits;
51 static size_t s_nFeldmanSet_ArrayBits;
53 static size_t s_nLoadFactor;
54 static std::vector<std::string> m_arrString;
56 static void SetUpTestCase();
57 static void TearDownTestCase();
60 typedef std::string key_type;
61 typedef size_t value_type;
70 class Inserter: public cds_test::thread
72 typedef cds_test::thread base_class;
75 typedef typename Set::value_type keyval_type;
78 size_t m_nInsertSuccess = 0;
79 size_t m_nInsertFailed = 0;
82 Inserter( cds_test::thread_pool& pool, Set& set )
83 : base_class( pool, insert_thread )
87 Inserter( Inserter& src )
92 virtual thread * clone()
94 return new Inserter( *this );
101 Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
102 size_t nArrSize = m_arrString.size();
103 size_t const nSetSize = fixture.s_nSetSize;
104 size_t const nPassCount = fixture.s_nThreadPassCount;
107 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
108 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
109 if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
117 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
118 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
119 if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
130 class Deleter: public cds_test::thread
132 typedef cds_test::thread base_class;
136 size_t m_nDeleteSuccess = 0;
137 size_t m_nDeleteFailed = 0;
140 Deleter( cds_test::thread_pool& pool, Set& set )
141 : base_class( pool, delete_thread )
145 Deleter( Deleter& src )
150 virtual thread * clone()
152 return new Deleter( *this );
159 Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
160 size_t nArrSize = m_arrString.size();
161 size_t const nSetSize = fixture.s_nSetSize;
162 size_t const nPassCount = fixture.s_nThreadPassCount;
165 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
166 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
167 if ( rSet.erase( m_arrString[nItem % nArrSize] ))
175 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
176 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
177 if ( rSet.erase( m_arrString[nItem % nArrSize] ))
187 template <typename GC, class Set>
188 class Extractor: public cds_test::thread
190 typedef cds_test::thread base_class;
194 size_t m_nDeleteSuccess = 0;
195 size_t m_nDeleteFailed = 0;
198 Extractor( cds_test::thread_pool& pool, Set& set )
199 : base_class( pool, extract_thread )
203 Extractor( Extractor& src )
208 virtual thread * clone()
210 return new Extractor( *this );
217 typename Set::guarded_ptr gp;
219 Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
220 size_t nArrSize = m_arrString.size();
221 size_t const nSetSize = fixture.s_nSetSize;
222 size_t const nPassCount = fixture.s_nThreadPassCount;
225 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
226 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
227 gp = rSet.extract( m_arrString[nItem % nArrSize] );
237 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
238 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
239 gp = rSet.extract( m_arrString[nItem % nArrSize] );
251 template <typename RCU, class Set>
252 class Extractor<cds::urcu::gc<RCU>, Set >: public cds_test::thread
254 typedef cds_test::thread base_class;
258 size_t m_nDeleteSuccess = 0;
259 size_t m_nDeleteFailed = 0;
262 Extractor( cds_test::thread_pool& pool, Set& set )
263 : base_class( pool, extract_thread )
267 Extractor( Extractor& src )
272 virtual thread * clone()
274 return new Extractor( *this );
281 typename Set::exempt_ptr xp;
283 Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
284 size_t nArrSize = m_arrString.size();
285 size_t const nSetSize = fixture.s_nSetSize;
286 size_t const nPassCount = fixture.s_nThreadPassCount;
289 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
290 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
291 if ( Set::c_bExtractLockExternal ) {
292 typename Set::rcu_lock l;
293 xp = rSet.extract( m_arrString[nItem % nArrSize] );
300 xp = rSet.extract( m_arrString[nItem % nArrSize] );
311 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
312 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
313 if ( Set::c_bExtractLockExternal ) {
314 typename Set::rcu_lock l;
315 xp = rSet.extract( m_arrString[nItem % nArrSize] );
322 xp = rSet.extract( m_arrString[nItem % nArrSize] );
337 void do_test( Set& testSet )
339 typedef Inserter<Set> InserterThread;
340 typedef Deleter<Set> DeleterThread;
342 cds_test::thread_pool& pool = get_pool();
343 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
344 pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
346 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
347 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
348 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
349 << std::make_pair( "set_size", s_nSetSize );
351 std::chrono::milliseconds duration = pool.run();
353 propout() << std::make_pair( "duration", duration );
355 size_t nInsertSuccess = 0;
356 size_t nInsertFailed = 0;
357 size_t nDeleteSuccess = 0;
358 size_t nDeleteFailed = 0;
359 for ( size_t i = 0; i < pool.size(); ++i ) {
360 cds_test::thread& thr = pool.get( i );
361 switch ( thr.type() ) {
364 InserterThread& inserter = static_cast<InserterThread&>( thr );
365 nInsertSuccess += inserter.m_nInsertSuccess;
366 nInsertFailed += inserter.m_nInsertFailed;
371 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
372 nDeleteSuccess += deleter.m_nDeleteSuccess;
373 nDeleteFailed += deleter.m_nDeleteFailed;
377 assert( false ); // Forgot anything?..
382 << std::make_pair( "insert_success", nInsertSuccess )
383 << std::make_pair( "delete_success", nDeleteSuccess )
384 << std::make_pair( "insert_failed", nInsertFailed )
385 << std::make_pair( "delete_failed", nDeleteFailed )
386 << std::make_pair( "final_set_size", testSet.size() );
389 for (auto const& str: m_arrString )
390 testSet.erase( str );
391 EXPECT_TRUE( testSet.empty() );
392 EXPECT_EQ( testSet.size(), 0u );
394 additional_check( testSet );
395 print_stat( propout(), testSet );
396 additional_cleanup( testSet );
400 void do_test_extract( Set& testSet )
402 typedef Inserter<Set> InserterThread;
403 typedef Deleter<Set> DeleterThread;
404 typedef Extractor<typename Set::gc, Set> ExtractThread;
406 size_t const nDelThreadCount = s_nDeleteThreadCount / 2;
407 size_t const nExtractThreadCount = s_nDeleteThreadCount - nDelThreadCount;
409 cds_test::thread_pool& pool = get_pool();
410 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
411 pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
412 pool.add( new ExtractThread( pool, testSet ), nExtractThreadCount );
414 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
415 << std::make_pair( "delete_thread_count", nDelThreadCount )
416 << std::make_pair( "extract_thread_count", nExtractThreadCount )
417 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
418 << std::make_pair( "set_size", s_nSetSize );
420 std::chrono::milliseconds duration = pool.run();
422 propout() << std::make_pair( "duration", duration );
424 size_t nInsertSuccess = 0;
425 size_t nInsertFailed = 0;
426 size_t nDeleteSuccess = 0;
427 size_t nDeleteFailed = 0;
428 size_t nExtractSuccess = 0;
429 size_t nExtractFailed = 0;
430 for ( size_t i = 0; i < pool.size(); ++i ) {
431 cds_test::thread& thr = pool.get( i );
432 switch ( thr.type() ) {
435 InserterThread& inserter = static_cast<InserterThread&>(thr);
436 nInsertSuccess += inserter.m_nInsertSuccess;
437 nInsertFailed += inserter.m_nInsertFailed;
442 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
443 nDeleteSuccess += deleter.m_nDeleteSuccess;
444 nDeleteFailed += deleter.m_nDeleteFailed;
449 ExtractThread& extractor = static_cast<ExtractThread&>(thr);
450 nExtractSuccess += extractor.m_nDeleteSuccess;
451 nExtractFailed += extractor.m_nDeleteFailed;
455 assert( false ); // Forgot anything?..
460 << std::make_pair( "insert_success", nInsertSuccess )
461 << std::make_pair( "delete_success", nDeleteSuccess )
462 << std::make_pair( "extract_success", nExtractSuccess )
463 << std::make_pair( "insert_failed", nInsertFailed )
464 << std::make_pair( "delete_failed", nDeleteFailed )
465 << std::make_pair( "extract_failed", nExtractFailed )
466 << std::make_pair( "final_set_size", testSet.size() );
469 for ( auto const& str : m_arrString )
470 testSet.erase( str );
471 EXPECT_TRUE( testSet.empty() );
472 EXPECT_EQ( testSet.size(), 0u );
474 additional_check( testSet );
475 print_stat( propout(), testSet );
476 additional_cleanup( testSet );
482 ASSERT_TRUE( m_arrString.size() > 0 );
489 void run_test_extract()
491 ASSERT_TRUE( m_arrString.size() > 0 );
494 do_test_extract( s );
498 class Set_InsDel_string_LF: public Set_InsDel_string
499 , public ::testing::WithParamInterface<size_t>
505 s_nLoadFactor = GetParam();
506 propout() << std::make_pair( "load_factor", s_nLoadFactor );
507 Set_InsDel_string::run_test<Set>();
511 void run_test_extract()
513 s_nLoadFactor = GetParam();
514 propout() << std::make_pair( "load_factor", s_nLoadFactor );
515 Set_InsDel_string::run_test_extract<Set>();
518 static std::vector<size_t> get_load_factors();