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.
40 key_thread( size_t key, size_t threadNo )
41 : nKey( static_cast<uint32_t>(key))
42 , nThread( static_cast<uint16_t>(threadNo))
51 static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
53 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
56 struct cmp<key_thread> {
57 int operator ()(key_thread const& k1, key_thread const& k2) const
59 if ( k1.nKey < k2.nKey )
61 if ( k1.nKey > k2.nKey )
63 if ( k1.nThread < k2.nThread )
65 if ( k1.nThread > k2.nThread )
69 int operator ()(key_thread const& k1, size_t k2) const
77 int operator ()(size_t k1, key_thread const& k2) const
88 struct less<set::key_thread>
90 bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
92 if ( k1.nKey <= k2.nKey )
93 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
99 struct hash<set::key_thread>
101 typedef size_t result_type;
102 typedef set::key_thread argument_type;
104 size_t operator()( set::key_thread const& k ) const
106 return std::hash<size_t>()(k.nKey);
109 size_t operator()( size_t k ) const
111 return std::hash<size_t>()(k);
116 class Set_DelOdd: public cds_test::stress_fixture
119 static size_t s_nSetSize; // max set size
120 static size_t s_nInsThreadCount; // insert thread count
121 static size_t s_nDelThreadCount; // delete thread count
122 static size_t s_nExtractThreadCount; // extract thread count
123 static size_t s_nMaxLoadFactor; // maximum load factor
125 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
126 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
127 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
129 static size_t s_nFeldmanSet_HeadBits;
130 static size_t s_nFeldmanSet_ArrayBits;
132 static size_t s_nLoadFactor;
134 static std::vector<size_t> m_arrData;
136 static void SetUpTestCase();
137 static void TearDownTestCase();
140 typedef key_thread key_type;
141 typedef size_t value_type;
143 atomics::atomic<size_t> m_nInsThreadCount;
152 // Inserts keys from [0..N)
154 class Inserter: public cds_test::thread
156 typedef cds_test::thread base_class;
159 struct update_functor
161 template <typename Q>
162 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
165 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
169 size_t m_nInsertSuccess = 0;
170 size_t m_nInsertFailed = 0;
173 Inserter( cds_test::thread_pool& pool, Set& set )
174 : base_class( pool, inserter_thread )
178 Inserter( Inserter& src )
183 virtual thread * clone()
185 return new Inserter( *this );
191 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
193 std::vector<size_t>& arrData = fixture.m_arrData;
194 for ( size_t i = 0; i < arrData.size(); ++i ) {
195 if ( rSet.insert( key_type( arrData[i], id())))
202 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
203 if ( arrData[i] & 1 )
204 rSet.update( key_type( arrData[i], id()), f, true );
207 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
212 bool operator()( key_type const& k1, key_type const& k2 ) const
214 return k1.nKey == k2.nKey;
216 bool operator()( size_t k1, key_type const& k2 ) const
218 return k1 == k2.nKey;
220 bool operator()( key_type const& k1, size_t k2 ) const
222 return k1.nKey == k2;
224 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
226 return operator()( k1.key, k2.key );
228 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
230 return operator()( k1.key, k2 );
232 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
234 return operator()( k1, k2.key );
236 bool operator ()( key_value_pair const& k1, size_t k2 ) const
238 return operator()( k1.key, k2 );
240 bool operator ()( size_t k1, key_value_pair const& k2 ) const
242 return operator()( k1, k2.key );
247 bool operator()( key_type const& k1, key_type const& k2 ) const
249 return k1.nKey < k2.nKey;
251 bool operator()( size_t k1, key_type const& k2 ) const
255 bool operator()( key_type const& k1, size_t k2 ) const
259 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
261 return operator()( k1.key, k2.key );
263 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
265 return operator()( k1.key, k2 );
267 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
269 return operator()( k1, k2.key );
271 bool operator ()( key_value_pair const& k1, size_t k2 ) const
273 return operator()( k1.key, k2 );
275 bool operator ()( size_t k1, key_value_pair const& k2 ) const
277 return operator()( k1, k2.key );
280 typedef key_equal equal_to;
283 // Deletes odd keys from [0..N)
285 class Deleter: public cds_test::thread
287 typedef cds_test::thread base_class;
291 size_t m_nDeleteSuccess = 0;
292 size_t m_nDeleteFailed = 0;
295 Deleter( cds_test::thread_pool& pool, Set& set )
296 : base_class( pool, deleter_thread )
299 Deleter( Deleter& src )
304 virtual thread * clone()
306 return new Deleter( *this );
309 template <typename SetType, bool>
311 static bool erase( SetType& s, size_t key, size_t /*thread*/)
313 return s.erase_with( key, key_less());
317 template <typename SetType>
318 struct eraser<SetType, true> {
319 static bool erase(SetType& s, size_t key, size_t thread)
321 return s.erase( key_type(key, thread));
329 size_t const nInsThreadCount = s_nInsThreadCount;
330 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
331 std::vector<size_t>& arrData = fixture.m_arrData;
334 for (size_t i = 0; i < arrData.size(); ++i) {
335 if ( arrData[i] & 1 ) {
336 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
337 if ( eraser<Set, Set::c_bEraseExactKey>::erase( rSet, arrData[i], k ))
343 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
348 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
349 if ( arrData[i] & 1 ) {
350 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
351 if (eraser<Set, Set::c_bEraseExactKey>::erase(rSet, arrData[i], k))
357 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
364 // Extracts odd keys from [0..N)
365 template <typename GC, class Set>
366 class Extractor: public cds_test::thread
368 typedef cds_test::thread base_class;
372 size_t m_nExtractSuccess = 0;
373 size_t m_nExtractFailed = 0;
376 Extractor( cds_test::thread_pool& pool, Set& set )
377 : base_class( pool, extractor_thread )
381 Extractor( Extractor& src )
386 virtual thread * clone()
388 return new Extractor( *this );
391 template <typename SetType, bool>
393 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t /*thread*/)
395 return s.extract_with( key, key_less());
399 template <typename SetType>
400 struct extractor<SetType, true> {
401 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t thread)
403 return s.extract( key_type(key, thread));
411 typename Set::guarded_ptr gp;
413 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
414 std::vector<size_t>& arrData = fixture.m_arrData;
415 size_t const nInsThreadCount = s_nInsThreadCount;
418 for ( size_t i = 0; i < arrData.size(); ++i ) {
419 if ( arrData[i] & 1 ) {
420 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
421 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k );
429 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
434 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
435 if ( arrData[i] & 1 ) {
436 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
437 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
445 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
452 template <typename RCU, class Set>
453 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
455 typedef cds_test::thread base_class;
459 size_t m_nExtractSuccess = 0;
460 size_t m_nExtractFailed = 0;
463 Extractor( cds_test::thread_pool& pool, Set& set )
464 : base_class( pool, extractor_thread )
468 Extractor( Extractor& src )
473 virtual thread * clone()
475 return new Extractor( *this );
478 template <typename SetType, bool>
480 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t /*thread*/)
482 return s.extract_with(key, key_less());
486 template <typename SetType>
487 struct extractor<SetType, true> {
488 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t thread)
490 return s.extract(key_type(key, thread));
498 typename Set::exempt_ptr xp;
500 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
501 std::vector<size_t>& arrData = fixture.m_arrData;
502 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
505 for ( size_t i = 0; i < arrData.size(); ++i ) {
506 if ( arrData[i] & 1 ) {
507 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
508 if ( Set::c_bExtractLockExternal ) {
509 typename Set::rcu_lock l;
510 xp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
517 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
526 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
531 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
532 if ( arrData[i] & 1 ) {
533 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
534 if ( Set::c_bExtractLockExternal ) {
535 typename Set::rcu_lock l;
536 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
543 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
552 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
561 void do_test_with( Set& testSet )
563 typedef Inserter<Set> insert_thread;
564 typedef Deleter<Set> delete_thread;
566 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
568 cds_test::thread_pool& pool = get_pool();
569 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
570 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
572 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
573 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
574 << std::make_pair( "set_size", s_nSetSize );
576 std::chrono::milliseconds duration = pool.run();
578 propout() << std::make_pair( "duration", duration );
580 size_t nInsertSuccess = 0;
581 size_t nInsertFailed = 0;
582 size_t nDeleteSuccess = 0;
583 size_t nDeleteFailed = 0;
585 for ( size_t i = 0; i < pool.size(); ++i ) {
586 cds_test::thread& thr = pool.get( i );
587 if ( thr.type() == inserter_thread ) {
588 insert_thread& inserter = static_cast<insert_thread&>(thr);
589 nInsertSuccess += inserter.m_nInsertSuccess;
590 nInsertFailed += inserter.m_nInsertFailed;
593 assert( thr.type() == deleter_thread );
594 delete_thread& deleter = static_cast<delete_thread&>(thr);
595 nDeleteSuccess += deleter.m_nDeleteSuccess;
596 nDeleteFailed += deleter.m_nDeleteFailed;
600 EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount );
601 EXPECT_EQ( nInsertFailed, 0u );
604 << std::make_pair( "insert_success", nInsertSuccess )
605 << std::make_pair( "insert_failed", nInsertFailed )
606 << std::make_pair( "delete_success", nDeleteSuccess )
607 << std::make_pair( "delete_failed", nDeleteFailed );
611 void do_test_extract_with( Set& testSet )
613 typedef Inserter<Set> insert_thread;
614 typedef Deleter<Set> delete_thread;
615 typedef Extractor< typename Set::gc, Set > extract_thread;
617 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
619 cds_test::thread_pool& pool = get_pool();
620 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
621 if ( s_nDelThreadCount )
622 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
623 if ( s_nExtractThreadCount )
624 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
626 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
627 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
628 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
629 << std::make_pair( "set_size", s_nSetSize );
631 std::chrono::milliseconds duration = pool.run();
633 propout() << std::make_pair( "duration", duration );
635 size_t nInsertSuccess = 0;
636 size_t nInsertFailed = 0;
637 size_t nDeleteSuccess = 0;
638 size_t nDeleteFailed = 0;
639 size_t nExtractSuccess = 0;
640 size_t nExtractFailed = 0;
641 for ( size_t i = 0; i < pool.size(); ++i ) {
642 cds_test::thread& thr = pool.get( i );
643 switch ( thr.type()) {
644 case inserter_thread:
646 insert_thread& inserter = static_cast<insert_thread&>( thr );
647 nInsertSuccess += inserter.m_nInsertSuccess;
648 nInsertFailed += inserter.m_nInsertFailed;
653 delete_thread& deleter = static_cast<delete_thread&>(thr);
654 nDeleteSuccess += deleter.m_nDeleteSuccess;
655 nDeleteFailed += deleter.m_nDeleteFailed;
658 case extractor_thread:
660 extract_thread& extractor = static_cast<extract_thread&>(thr);
661 nExtractSuccess += extractor.m_nExtractSuccess;
662 nExtractFailed += extractor.m_nExtractFailed;
670 EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount );
671 EXPECT_EQ( nInsertFailed, 0u );
674 << std::make_pair( "insert_success", nInsertSuccess )
675 << std::make_pair( "insert_failed", nInsertFailed )
676 << std::make_pair( "delete_success", nDeleteSuccess )
677 << std::make_pair( "delete_failed", nDeleteFailed )
678 << std::make_pair( "extract_success", nExtractSuccess )
679 << std::make_pair( "extract_failed", nExtractFailed );
682 template <typename Set>
683 void analyze( Set& testSet )
685 // All even keys must be in the set
687 for ( size_t n = 0; n < s_nSetSize; n +=2 ) {
688 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
689 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
694 check_before_clear( testSet );
697 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
699 additional_check( testSet );
700 print_stat( propout(), testSet );
701 additional_cleanup( testSet );
707 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
709 Set testSet( *this );
710 do_test_with( testSet );
715 void run_test_extract()
717 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
719 Set testSet( *this );
720 do_test_extract_with( testSet );
725 class Set_DelOdd_LF: public Set_DelOdd
726 , public ::testing::WithParamInterface<size_t>
732 s_nLoadFactor = GetParam();
733 propout() << std::make_pair( "load_factor", s_nLoadFactor );
734 Set_DelOdd::run_test<Set>();
738 void run_test_extract()
740 s_nLoadFactor = GetParam();
741 propout() << std::make_pair( "load_factor", s_nLoadFactor );
742 Set_DelOdd::run_test_extract<Set>();
745 static std::vector<size_t> get_load_factors();