3 #ifndef __CDSTEST_HDR_STRIPED_SET_H
4 #define __CDSTEST_HDR_STRIPED_SET_H
6 #include "cppunit/cppunit_proxy.h"
7 #include "size_check.h"
9 #include <cds/opt/hash.h>
10 #include <cds/os/timer.h>
12 #include <algorithm> // random_shuffle
14 // forward namespace declaration
16 namespace container {}
21 using misc::check_size;
23 namespace cc = cds::container;
24 namespace co = cds::opt;
27 class StripedSetHdrTest: public CppUnitMini::TestCase
32 unsigned int nFindCount ; // count of find-functor calling
33 unsigned int nEnsureNewCount;
34 unsigned int nEnsureCount;
38 memset( this, 0, sizeof(*this));
41 void copy( stat const& s )
43 nFindCount = s.nFindCount;
44 nEnsureCount = s.nEnsureCount;
45 nEnsureNewCount = s.nEnsureNewCount;
49 struct item: public stat
62 item (int key, int val )
67 item( std::pair<int,int> const& p )
77 item& operator=(item const& i)
87 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
93 //item& operator=(item&& i)
113 size_t operator()( int i ) const
115 return co::v::hash<int>()( i );
118 size_t operator()( std::pair<int,int> const& i ) const
120 return co::v::hash<int>()( i.first );
123 template <typename Item>
124 size_t operator()( Item const& i ) const
126 return (*this)( i.key() );
130 struct simple_item_counter {
133 simple_item_counter()
152 operator size_t() const
158 template <typename T>
161 bool operator ()(const T& v1, const T& v2 ) const
163 return v1.key() < v2.key();
166 template <typename Q>
167 bool operator ()(const T& v1, const Q& v2 ) const
169 return v1.key() < v2;
172 template <typename Q>
173 bool operator ()(const Q& v1, const T& v2 ) const
175 return v1 < v2.key();
178 bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
180 return v1.first < v2.key();
183 bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
185 return v1.key() < v2.first;
189 template <typename T>
191 int operator ()(const T& v1, const T& v2 ) const
193 if ( v1.key() < v2.key() )
195 return v1.key() > v2.key() ? 1 : 0;
198 template <typename Q>
199 int operator ()(const T& v1, const Q& v2 ) const
203 return v1.key() > v2 ? 1 : 0;
206 template <typename Q>
207 int operator ()(const Q& v1, const T& v2 ) const
211 return v1 > v2.key() ? 1 : 0;
214 int operator()( std::pair<int,int> const& v1, T const& v2 ) const
216 if ( v1.first < v2.key() )
218 return v1.first > v2.key() ? 1 : 0;
221 int operator()( T const& v1, std::pair<int,int> const& v2 ) const
223 if ( v1.key() < v2.first )
225 return v1.key() > v2.first ? 1 : 0;
229 template <typename T>
232 bool operator ()(const T& v1, const T& v2 ) const
234 return v1.key() == v2.key();
237 template <typename Q>
238 bool operator ()(const T& v1, const Q& v2 ) const
240 return v1.key() == v2;
243 template <typename Q>
244 bool operator ()(const Q& v1, const T& v2 ) const
246 return v1 == v2.key();
249 bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
251 return v1.first == v2.key();
254 bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
256 return v1.key() == v2.first;
262 template <typename Item, typename T>
263 void operator()( Item& i, T& val )
267 template <typename Item, typename T>
268 void operator()( Item& i, T const& val )
274 template <typename Item>
279 template <typename T>
280 void operator()( Item& i, T& /*val*/ )
285 void operator()( Item const& i )
291 struct insert_functor
293 template <typename Item>
294 void operator()(Item& i )
296 i.nVal = i.nKey * 100;
300 template <typename Item, typename Q>
301 static void ensure_func( bool bNew, Item& i, Q& /*val*/ )
309 struct ensure_functor
311 template <typename Item, typename Q>
312 void operator()( bool bNew, Item& i, Q& val )
314 ensure_func( bNew, i, val );
323 CPPUNIT_ASSERT( s.bucket_count() == 32 );
324 CPPUNIT_ASSERT( s.lock_count() == 32 );
326 test_striped_with( s );
330 void test_striped_with( Set& s )
332 cds::OS::Timer timer;
337 for ( int i = 0; i < 10000; i++ ) {
341 CPPUNIT_MSG( " Duration=" << timer.duration() );
345 void test_int_with( Set& s)
347 typedef typename Set::value_type value_type;
353 CPPUNIT_ASSERT( !s.find( 10 ) );
354 CPPUNIT_ASSERT( s.insert( 10 ));
355 CPPUNIT_ASSERT( !s.empty() );
356 CPPUNIT_ASSERT( check_size( s, 1 ));
357 CPPUNIT_ASSERT( s.find( 10 ) );
359 CPPUNIT_ASSERT( !s.insert( 10 ));
360 CPPUNIT_ASSERT( !s.empty() );
361 CPPUNIT_ASSERT( check_size( s, 1 ));
363 CPPUNIT_ASSERT( !s.find( 20 ) );
364 CPPUNIT_ASSERT( s.insert( std::make_pair(20, 25) ));
365 CPPUNIT_ASSERT( !s.empty() );
366 CPPUNIT_ASSERT( check_size( s, 2 ));
367 CPPUNIT_ASSERT( s.find( 10 ) );
368 CPPUNIT_ASSERT( s.find( key = 20 ) );
369 CPPUNIT_ASSERT( s.find( key, find_functor() ) );
373 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
374 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
375 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
376 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
381 CPPUNIT_ASSERT( s.find( key, find_functor() ) );
382 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
383 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
384 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
385 CPPUNIT_ASSERT( f.m_found.nFindCount == 2 );
387 CPPUNIT_ASSERT( !s.empty() );
388 CPPUNIT_ASSERT( check_size( s, 2 ));
390 CPPUNIT_ASSERT( !s.find( 25 ) );
391 CPPUNIT_ASSERT( s.insert( std::make_pair(25, -1), insert_functor() ));
392 CPPUNIT_ASSERT( !s.empty() );
393 CPPUNIT_ASSERT( check_size( s, 3 ));
397 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
398 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
399 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
406 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
407 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
408 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
409 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
410 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
412 std::pair<bool, bool> ensureResult = s.ensure( key, ensure_functor() );
413 CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second );
414 CPPUNIT_ASSERT( !s.empty() );
415 CPPUNIT_ASSERT( check_size( s, 3 ));
418 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
419 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
420 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
421 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 1 );
422 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
425 ensureResult = s.ensure( std::make_pair(13, 1300), ensure_functor() );
426 CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
427 CPPUNIT_ASSERT( !s.empty() );
428 CPPUNIT_ASSERT( check_size( s, 4 ));
432 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
433 CPPUNIT_ASSERT( f.m_found.nKey == 13 );
434 CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
435 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
436 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 1 );
440 CPPUNIT_ASSERT( s.erase(13) );
441 CPPUNIT_ASSERT( !s.find( 13 ));
442 CPPUNIT_ASSERT( !s.empty() );
443 CPPUNIT_ASSERT( check_size( s, 3 ));
444 CPPUNIT_ASSERT( !s.erase(13) );
445 CPPUNIT_ASSERT( !s.empty() );
446 CPPUNIT_ASSERT( check_size( s, 3 ));
448 CPPUNIT_ASSERT( s.find( 10 ));
449 CPPUNIT_ASSERT( s.erase( 10 ));
450 CPPUNIT_ASSERT( !s.find( 10 ));
451 CPPUNIT_ASSERT( !s.empty() );
452 CPPUNIT_ASSERT( check_size( s, 2 ));
453 CPPUNIT_ASSERT( !s.erase(10) );
454 CPPUNIT_ASSERT( !s.empty() );
455 CPPUNIT_ASSERT( check_size( s, 2 ));
457 CPPUNIT_ASSERT( s.find(20) );
460 CPPUNIT_ASSERT( s.erase( 20, boost::ref(f) ));
461 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
462 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
464 CPPUNIT_ASSERT( s.insert(235))
465 CPPUNIT_ASSERT( s.erase( 235, boost::ref(f) ));
466 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
467 CPPUNIT_ASSERT( f.m_found.nVal == 235 );
469 CPPUNIT_ASSERT( !s.find( 20 ));
470 CPPUNIT_ASSERT( !s.empty() );
471 CPPUNIT_ASSERT( check_size( s, 1 ));
474 CPPUNIT_ASSERT( s.empty() );
475 CPPUNIT_ASSERT( check_size( s, 0 ));
477 # ifdef CDS_EMPLACE_SUPPORT
479 CPPUNIT_ASSERT( s.emplace( 151 )) ; // key = 151, val = 151
480 CPPUNIT_ASSERT( s.emplace( 174, 471 )) ; // key = 174, val = 471
481 CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
482 CPPUNIT_ASSERT( !s.empty() );
483 CPPUNIT_ASSERT( check_size( s, 3 ));
485 CPPUNIT_ASSERT( s.find(151));
486 CPPUNIT_ASSERT( s.find(174));
487 CPPUNIT_ASSERT( s.find(190));
492 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
493 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
494 CPPUNIT_ASSERT( f.m_found.nVal == 151 );
497 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
498 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
499 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
502 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
503 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
504 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
508 CPPUNIT_ASSERT( s.empty() );
509 CPPUNIT_ASSERT( check_size( s, 0 ));
513 //*******************************************
514 // If erase_with && find_with are supported
515 #ifndef CDS_CXX11_DEFAULT_FUNCTION_TEMPLATE_ARGS_SUPPORT
526 CPPUNIT_ASSERT( s.bucket_count() == 32 );
527 CPPUNIT_ASSERT( s.lock_count() == 32 );
529 test_striped_with2( s );
533 void test_striped_with2( Set& s )
535 cds::OS::Timer timer;
540 for ( int i = 0; i < 10000; i++ ) {
544 CPPUNIT_MSG( " Duration=" << timer.duration() );
548 void test_int_with2( Set& s)
550 typedef typename Set::value_type value_type;
556 CPPUNIT_ASSERT( !s.find( 10 ) );
557 CPPUNIT_ASSERT( s.insert( 10 ));
558 CPPUNIT_ASSERT( !s.empty() );
559 CPPUNIT_ASSERT( check_size( s, 1 ));
560 CPPUNIT_ASSERT( s.find( 10 ) );
562 CPPUNIT_ASSERT( !s.insert( 10 ));
563 CPPUNIT_ASSERT( !s.empty() );
564 CPPUNIT_ASSERT( check_size( s, 1 ));
566 CPPUNIT_ASSERT( !s.find_with( 20, less<value_type>() ) );
567 CPPUNIT_ASSERT( s.insert( std::make_pair(20, 25) ));
568 CPPUNIT_ASSERT( !s.empty() );
569 CPPUNIT_ASSERT( check_size( s, 2 ));
570 CPPUNIT_ASSERT( s.find( 10 ) );
571 CPPUNIT_ASSERT( s.find_with( key = 20, less<value_type>() ) );
572 CPPUNIT_ASSERT( s.find_with( key, less<value_type>(), find_functor() ) );
576 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
577 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
578 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
579 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
584 CPPUNIT_ASSERT( s.find_with( 20, less<value_type>(), find_functor() ) );
585 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
586 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
587 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
588 CPPUNIT_ASSERT( f.m_found.nFindCount == 2 );
590 CPPUNIT_ASSERT( !s.empty() );
591 CPPUNIT_ASSERT( check_size( s, 2 ));
593 CPPUNIT_ASSERT( !s.find( 25 ) );
594 CPPUNIT_ASSERT( s.insert( std::make_pair(25, -1), insert_functor() ));
595 CPPUNIT_ASSERT( !s.empty() );
596 CPPUNIT_ASSERT( check_size( s, 3 ));
600 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
601 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
602 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
609 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
610 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
611 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
612 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
613 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
615 std::pair<bool, bool> ensureResult = s.ensure( key, ensure_functor() );
616 CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second );
617 CPPUNIT_ASSERT( !s.empty() );
618 CPPUNIT_ASSERT( check_size( s, 3 ));
621 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
622 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
623 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
624 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 1 );
625 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
628 ensureResult = s.ensure( std::make_pair(13, 1300), ensure_functor() );
629 CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
630 CPPUNIT_ASSERT( !s.empty() );
631 CPPUNIT_ASSERT( check_size( s, 4 ));
635 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
636 CPPUNIT_ASSERT( f.m_found.nKey == 13 );
637 CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
638 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
639 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 1 );
643 CPPUNIT_ASSERT( s.erase(13) );
644 CPPUNIT_ASSERT( !s.find( 13 ));
645 CPPUNIT_ASSERT( !s.empty() );
646 CPPUNIT_ASSERT( check_size( s, 3 ));
647 CPPUNIT_ASSERT( !s.erase(13) );
648 CPPUNIT_ASSERT( !s.empty() );
649 CPPUNIT_ASSERT( check_size( s, 3 ));
651 CPPUNIT_ASSERT( s.find( 10 ));
652 CPPUNIT_ASSERT( s.erase_with( 10, less<value_type>() ));
653 CPPUNIT_ASSERT( !s.find( 10 ));
654 CPPUNIT_ASSERT( !s.empty() );
655 CPPUNIT_ASSERT( check_size( s, 2 ));
656 CPPUNIT_ASSERT( !s.erase_with( 10, less<value_type>() ) );
657 CPPUNIT_ASSERT( !s.empty() );
658 CPPUNIT_ASSERT( check_size( s, 2 ));
660 CPPUNIT_ASSERT( s.find(20) );
663 CPPUNIT_ASSERT( s.erase( 20, boost::ref(f) ));
664 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
665 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
667 CPPUNIT_ASSERT( s.insert(235))
668 CPPUNIT_ASSERT( s.erase_with( 235, less<value_type>(), boost::ref(f) ));
669 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
670 CPPUNIT_ASSERT( f.m_found.nVal == 235 );
672 CPPUNIT_ASSERT( !s.find( 20 ));
673 CPPUNIT_ASSERT( !s.empty() );
674 CPPUNIT_ASSERT( check_size( s, 1 ));
677 CPPUNIT_ASSERT( s.empty() );
678 CPPUNIT_ASSERT( check_size( s, 0 ));
680 # ifdef CDS_EMPLACE_SUPPORT
682 CPPUNIT_ASSERT( s.emplace( 151 )) ; // key = 151, val = 151
683 CPPUNIT_ASSERT( s.emplace( 174, 471 )) ; // key = 174, val = 471
684 CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
685 CPPUNIT_ASSERT( !s.empty() );
686 CPPUNIT_ASSERT( check_size( s, 3 ));
688 CPPUNIT_ASSERT( s.find(151));
689 CPPUNIT_ASSERT( s.find(174));
690 CPPUNIT_ASSERT( s.find(190));
695 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
696 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
697 CPPUNIT_ASSERT( f.m_found.nVal == 151 );
700 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
701 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
702 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
705 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
706 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
707 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
711 CPPUNIT_ASSERT( s.empty() );
712 CPPUNIT_ASSERT( check_size( s, 0 ));
715 #endif // CDS_CXX11_DEFAULT_FUNCTION_TEMPLATE_ARGS_SUPPORT
718 void Striped_vector();
720 void Striped_hashset();
721 void Striped_slist();
722 void Striped_boost_list();
723 void Striped_boost_vector();
724 void Striped_boost_stable_vector();
725 void Striped_boost_flat_set();
726 void Striped_boost_set();
727 void Striped_boost_unordered_set();
729 void Refinable_list();
730 void Refinable_vector();
731 void Refinable_set();
732 void Refinable_hashset();
733 void Refinable_slist();
734 void Refinable_boost_list();
735 void Refinable_boost_vector();
736 void Refinable_boost_stable_vector();
737 void Refinable_boost_flat_set();
738 void Refinable_boost_set();
739 void Refinable_boost_unordered_set();
741 CPPUNIT_TEST_SUITE(StripedSetHdrTest)
742 CPPUNIT_TEST(Striped_list)
743 CPPUNIT_TEST(Striped_vector)
744 CPPUNIT_TEST(Striped_set)
745 CPPUNIT_TEST(Striped_hashset)
746 CPPUNIT_TEST(Striped_slist)
747 CPPUNIT_TEST(Striped_boost_list)
748 CPPUNIT_TEST(Striped_boost_vector)
749 CPPUNIT_TEST(Striped_boost_stable_vector)
750 CPPUNIT_TEST(Striped_boost_flat_set)
751 CPPUNIT_TEST(Striped_boost_set)
752 CPPUNIT_TEST(Striped_boost_unordered_set)
754 CPPUNIT_TEST(Refinable_list)
755 CPPUNIT_TEST(Refinable_vector)
756 CPPUNIT_TEST(Refinable_set)
757 CPPUNIT_TEST(Refinable_hashset)
758 CPPUNIT_TEST(Refinable_slist)
759 CPPUNIT_TEST(Refinable_boost_list)
760 CPPUNIT_TEST(Refinable_boost_vector)
761 CPPUNIT_TEST(Refinable_boost_stable_vector)
762 CPPUNIT_TEST(Refinable_boost_flat_set)
763 CPPUNIT_TEST(Refinable_boost_set)
764 CPPUNIT_TEST(Refinable_boost_unordered_set)
766 CPPUNIT_TEST_SUITE_END()
770 #endif // #ifndef __CDSTEST_HDR_STRIPED_SET_H