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.
41 key_thread( size_t key, size_t threadNo )
42 : nKey( static_cast<uint32_t>(key))
43 , nThread( static_cast<uint16_t>(threadNo))
54 static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
56 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
59 struct cmp<key_thread> {
60 int operator ()(key_thread const& k1, key_thread const& k2) const
62 if ( k1.nKey < k2.nKey )
64 if ( k1.nKey > k2.nKey )
66 if ( k1.nThread < k2.nThread )
68 if ( k1.nThread > k2.nThread )
72 int operator ()(key_thread const& k1, size_t k2) const
80 int operator ()(size_t k1, key_thread const& k2) const
91 struct less<set::key_thread>
93 bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
95 if ( k1.nKey <= k2.nKey )
96 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
102 struct hash<set::key_thread>
104 typedef size_t result_type;
105 typedef set::key_thread argument_type;
107 size_t operator()( set::key_thread const& k ) const
109 return std::hash<size_t>()(k.nKey);
112 size_t operator()( size_t k ) const
114 return std::hash<size_t>()(k);
119 class Set_DelOdd: public cds_test::stress_fixture
122 static size_t s_nSetSize; // max set size
123 static size_t s_nInsThreadCount; // insert thread count
124 static size_t s_nDelThreadCount; // delete thread count
125 static size_t s_nExtractThreadCount; // extract thread count
126 static size_t s_nMaxLoadFactor; // maximum load factor
128 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
129 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
130 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
132 static size_t s_nFeldmanSet_HeadBits;
133 static size_t s_nFeldmanSet_ArrayBits;
135 static size_t s_nLoadFactor;
137 static std::vector<size_t> m_arrData;
139 static void SetUpTestCase();
140 static void TearDownTestCase();
143 typedef key_thread key_type;
144 typedef size_t value_type;
146 atomics::atomic<size_t> m_nInsThreadCount;
155 // Inserts keys from [0..N)
157 class Inserter: public cds_test::thread
159 typedef cds_test::thread base_class;
162 struct update_functor
164 template <typename Q>
165 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
168 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
172 size_t m_nInsertSuccess = 0;
173 size_t m_nInsertFailed = 0;
176 Inserter( cds_test::thread_pool& pool, Set& set )
177 : base_class( pool, inserter_thread )
181 Inserter( Inserter& src )
186 virtual thread * clone()
188 return new Inserter( *this );
194 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
196 std::vector<size_t>& arrData = fixture.m_arrData;
197 for ( size_t i = 0; i < arrData.size(); ++i ) {
198 if ( rSet.insert( key_type( arrData[i], id())))
205 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
206 if ( arrData[i] & 1 )
207 rSet.update( key_type( arrData[i], id()), f, true );
210 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
215 bool operator()( key_type const& k1, key_type const& k2 ) const
217 return k1.nKey == k2.nKey;
219 bool operator()( size_t k1, key_type const& k2 ) const
221 return k1 == k2.nKey;
223 bool operator()( key_type const& k1, size_t k2 ) const
225 return k1.nKey == k2;
227 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
229 return operator()( k1.key, k2.key );
231 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
233 return operator()( k1.key, k2 );
235 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
237 return operator()( k1, k2.key );
239 bool operator ()( key_value_pair const& k1, size_t k2 ) const
241 return operator()( k1.key, k2 );
243 bool operator ()( size_t k1, key_value_pair const& k2 ) const
245 return operator()( k1, k2.key );
250 bool operator()( key_type const& k1, key_type const& k2 ) const
252 return k1.nKey < k2.nKey;
254 bool operator()( size_t k1, key_type const& k2 ) const
258 bool operator()( key_type const& k1, size_t k2 ) const
262 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
264 return operator()( k1.key, k2.key );
266 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
268 return operator()( k1.key, k2 );
270 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
272 return operator()( k1, k2.key );
274 bool operator ()( key_value_pair const& k1, size_t k2 ) const
276 return operator()( k1.key, k2 );
278 bool operator ()( size_t k1, key_value_pair const& k2 ) const
280 return operator()( k1, k2.key );
283 typedef key_equal equal_to;
286 // Deletes odd keys from [0..N)
288 class Deleter: public cds_test::thread
290 typedef cds_test::thread base_class;
294 size_t m_nDeleteSuccess = 0;
295 size_t m_nDeleteFailed = 0;
298 Deleter( cds_test::thread_pool& pool, Set& set )
299 : base_class( pool, deleter_thread )
302 Deleter( Deleter& src )
307 virtual thread * clone()
309 return new Deleter( *this );
312 template <typename SetType, bool>
314 static bool erase( SetType& s, size_t key, size_t /*thread*/)
316 return s.erase_with( key, key_less());
320 template <typename SetType>
321 struct eraser<SetType, true> {
322 static bool erase(SetType& s, size_t key, size_t thread)
324 return s.erase( key_type(key, thread));
332 size_t const nInsThreadCount = s_nInsThreadCount;
333 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
334 std::vector<size_t>& arrData = fixture.m_arrData;
337 for (size_t i = 0; i < arrData.size(); ++i) {
338 if ( arrData[i] & 1 ) {
339 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
340 if ( eraser<Set, Set::c_bEraseExactKey>::erase( rSet, arrData[i], k ))
346 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
351 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
352 if ( arrData[i] & 1 ) {
353 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
354 if (eraser<Set, Set::c_bEraseExactKey>::erase(rSet, arrData[i], k))
360 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
367 // Extracts odd keys from [0..N)
368 template <typename GC, class Set>
369 class Extractor: public cds_test::thread
371 typedef cds_test::thread base_class;
375 size_t m_nExtractSuccess = 0;
376 size_t m_nExtractFailed = 0;
379 Extractor( cds_test::thread_pool& pool, Set& set )
380 : base_class( pool, extractor_thread )
384 Extractor( Extractor& src )
389 virtual thread * clone()
391 return new Extractor( *this );
394 template <typename SetType, bool>
396 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t /*thread*/)
398 return s.extract_with( key, key_less());
402 template <typename SetType>
403 struct extractor<SetType, true> {
404 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t thread)
406 return s.extract( key_type(key, thread));
414 typename Set::guarded_ptr gp;
416 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
417 std::vector<size_t>& arrData = fixture.m_arrData;
418 size_t const nInsThreadCount = s_nInsThreadCount;
421 for ( size_t i = 0; i < arrData.size(); ++i ) {
422 if ( arrData[i] & 1 ) {
423 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
424 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k );
432 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
437 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
438 if ( arrData[i] & 1 ) {
439 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
440 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
448 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
455 template <typename RCU, class Set>
456 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
458 typedef cds_test::thread base_class;
462 size_t m_nExtractSuccess = 0;
463 size_t m_nExtractFailed = 0;
466 Extractor( cds_test::thread_pool& pool, Set& set )
467 : base_class( pool, extractor_thread )
471 Extractor( Extractor& src )
476 virtual thread * clone()
478 return new Extractor( *this );
481 template <typename SetType, bool>
483 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t /*thread*/)
485 return s.extract_with(key, key_less());
489 template <typename SetType>
490 struct extractor<SetType, true> {
491 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t thread)
493 return s.extract(key_type(key, thread));
501 typename Set::exempt_ptr xp;
503 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
504 std::vector<size_t>& arrData = fixture.m_arrData;
505 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
508 for ( size_t i = 0; i < arrData.size(); ++i ) {
509 if ( arrData[i] & 1 ) {
510 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
511 if ( Set::c_bExtractLockExternal ) {
512 typename Set::rcu_lock l;
513 xp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
520 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
529 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
534 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
535 if ( arrData[i] & 1 ) {
536 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
537 if ( Set::c_bExtractLockExternal ) {
538 typename Set::rcu_lock l;
539 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
546 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
555 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
564 void do_test_with( Set& testSet )
566 typedef Inserter<Set> insert_thread;
567 typedef Deleter<Set> delete_thread;
569 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
571 cds_test::thread_pool& pool = get_pool();
572 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
573 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
575 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
576 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
577 << std::make_pair( "set_size", s_nSetSize );
579 std::chrono::milliseconds duration = pool.run();
581 propout() << std::make_pair( "duration", duration );
583 size_t nInsertSuccess = 0;
584 size_t nInsertFailed = 0;
585 size_t nDeleteSuccess = 0;
586 size_t nDeleteFailed = 0;
588 for ( size_t i = 0; i < pool.size(); ++i ) {
589 cds_test::thread& thr = pool.get( i );
590 if ( thr.type() == inserter_thread ) {
591 insert_thread& inserter = static_cast<insert_thread&>(thr);
592 nInsertSuccess += inserter.m_nInsertSuccess;
593 nInsertFailed += inserter.m_nInsertFailed;
596 assert( thr.type() == deleter_thread );
597 delete_thread& deleter = static_cast<delete_thread&>(thr);
598 nDeleteSuccess += deleter.m_nDeleteSuccess;
599 nDeleteFailed += deleter.m_nDeleteFailed;
603 EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount );
604 EXPECT_EQ( nInsertFailed, 0u );
607 << std::make_pair( "insert_success", nInsertSuccess )
608 << std::make_pair( "insert_failed", nInsertFailed )
609 << std::make_pair( "delete_success", nDeleteSuccess )
610 << std::make_pair( "delete_failed", nDeleteFailed );
614 void do_test_extract_with( Set& testSet )
616 typedef Inserter<Set> insert_thread;
617 typedef Deleter<Set> delete_thread;
618 typedef Extractor< typename Set::gc, Set > extract_thread;
620 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
622 cds_test::thread_pool& pool = get_pool();
623 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
624 if ( s_nDelThreadCount )
625 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
626 if ( s_nExtractThreadCount )
627 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
629 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
630 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
631 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
632 << std::make_pair( "set_size", s_nSetSize );
634 std::chrono::milliseconds duration = pool.run();
636 propout() << std::make_pair( "duration", duration );
638 size_t nInsertSuccess = 0;
639 size_t nInsertFailed = 0;
640 size_t nDeleteSuccess = 0;
641 size_t nDeleteFailed = 0;
642 size_t nExtractSuccess = 0;
643 size_t nExtractFailed = 0;
644 for ( size_t i = 0; i < pool.size(); ++i ) {
645 cds_test::thread& thr = pool.get( i );
646 switch ( thr.type()) {
647 case inserter_thread:
649 insert_thread& inserter = static_cast<insert_thread&>( thr );
650 nInsertSuccess += inserter.m_nInsertSuccess;
651 nInsertFailed += inserter.m_nInsertFailed;
656 delete_thread& deleter = static_cast<delete_thread&>(thr);
657 nDeleteSuccess += deleter.m_nDeleteSuccess;
658 nDeleteFailed += deleter.m_nDeleteFailed;
661 case extractor_thread:
663 extract_thread& extractor = static_cast<extract_thread&>(thr);
664 nExtractSuccess += extractor.m_nExtractSuccess;
665 nExtractFailed += extractor.m_nExtractFailed;
673 EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount );
674 EXPECT_EQ( nInsertFailed, 0u );
677 << std::make_pair( "insert_success", nInsertSuccess )
678 << std::make_pair( "insert_failed", nInsertFailed )
679 << std::make_pair( "delete_success", nDeleteSuccess )
680 << std::make_pair( "delete_failed", nDeleteFailed )
681 << std::make_pair( "extract_success", nExtractSuccess )
682 << std::make_pair( "extract_failed", nExtractFailed );
685 template <typename Set>
686 void analyze( Set& testSet )
688 // All even keys must be in the set
690 for ( size_t n = 0; n < s_nSetSize; n +=2 ) {
691 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
692 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
697 check_before_clear( testSet );
700 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
702 additional_check( testSet );
703 print_stat( propout(), testSet );
704 additional_cleanup( testSet );
710 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
712 Set testSet( *this );
713 do_test_with( testSet );
718 void run_test_extract()
720 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
722 Set testSet( *this );
723 do_test_extract_with( testSet );
728 class Set_DelOdd_LF: public Set_DelOdd
729 , public ::testing::WithParamInterface<size_t>
735 s_nLoadFactor = GetParam();
736 propout() << std::make_pair( "load_factor", s_nLoadFactor );
737 Set_DelOdd::run_test<Set>();
741 void run_test_extract()
743 s_nLoadFactor = GetParam();
744 propout() << std::make_pair( "load_factor", s_nLoadFactor );
745 Set_DelOdd::run_test_extract<Set>();
748 static std::vector<size_t> get_load_factors();