3 #ifndef __CDSTEST_HDR_CUCKOO_SET_H
4 #define __CDSTEST_HDR_CUCKOO_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>
11 #include <functional> // ref
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 CuckooSetHdrTest: 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)
103 size_t operator()( int i ) const
105 return co::v::hash<int>()( i );
108 size_t operator()( std::pair<int,int> const& i ) const
110 return co::v::hash<int>()( i.first );
113 template <typename Item>
114 size_t operator()( Item const& i ) const
116 return (*this)( i.key() );
120 struct hash2: private hash1
122 typedef hash1 base_class;
124 size_t operator()( int i ) const
126 return ~( base_class::operator()(i));
128 template <typename Item>
129 size_t operator()( const Item& i ) const
131 return ~( base_class::operator()(i));
133 size_t operator()( std::pair<int,int> const& i ) const
135 return ~( base_class::operator()(i));
139 struct simple_item_counter {
142 simple_item_counter()
161 operator size_t() const
167 template <typename T>
170 bool operator ()(const T& v1, const T& v2 ) const
172 return v1.key() < v2.key();
175 template <typename Q>
176 bool operator ()(const T& v1, const Q& v2 ) const
178 return v1.key() < v2;
181 template <typename Q>
182 bool operator ()(const Q& v1, const T& v2 ) const
184 return v1 < v2.key();
187 bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
189 return v1.first < v2.key();
192 bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
194 return v1.key() < v2.first;
198 template <typename T>
200 int operator ()(const T& v1, const T& v2 ) const
202 if ( v1.key() < v2.key() )
204 return v1.key() > v2.key() ? 1 : 0;
207 template <typename Q>
208 int operator ()(const T& v1, const Q& v2 ) const
212 return v1.key() > v2 ? 1 : 0;
215 template <typename Q>
216 int operator ()(const Q& v1, const T& v2 ) const
220 return v1 > v2.key() ? 1 : 0;
223 int operator()( std::pair<int,int> const& v1, T const& v2 ) const
225 if ( v1.first < v2.key() )
227 return v1.first > v2.key() ? 1 : 0;
230 int operator()( T const& v1, std::pair<int,int> const& v2 ) const
232 if ( v1.key() < v2.first )
234 return v1.key() > v2.first ? 1 : 0;
238 template <typename T>
241 bool operator ()(const T& v1, const T& v2 ) const
243 return v1.key() == v2.key();
246 template <typename Q>
247 bool operator ()(const T& v1, const Q& v2 ) const
249 return v1.key() == v2;
252 template <typename Q>
253 bool operator ()(const Q& v1, const T& v2 ) const
255 return v1 == v2.key();
258 bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
260 return v1.first == v2.key();
263 bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
265 return v1.key() == v2.first;
271 template <typename Item, typename T>
272 void operator()( Item& i, T& val )
276 template <typename Item, typename T>
277 void operator()( Item& i, T const& val )
283 template <typename Item>
288 template <typename T>
289 void operator()( Item& i, T& /*val*/ )
294 void operator()( Item const& i )
300 struct insert_functor
302 template <typename Item>
303 void operator()(Item& i )
305 i.nVal = i.nKey * 100;
309 template <typename Item, typename Q>
310 static void ensure_func( bool bNew, Item& i, Q& /*val*/ )
318 struct ensure_functor
320 template <typename Item, typename Q>
321 void operator()( bool bNew, Item& i, Q& val )
323 ensure_func( bNew, i, val );
327 template <class Set, typename Predicate>
328 void test_int_with( Set& s, Predicate pred )
330 typedef typename Set::value_type value_type;
336 CPPUNIT_ASSERT( !s.find( 10 ) );
337 CPPUNIT_ASSERT( s.insert( 10 ));
338 CPPUNIT_ASSERT( !s.empty() );
339 CPPUNIT_ASSERT( check_size( s, 1 ));
340 CPPUNIT_ASSERT( s.find( 10 ) );
342 CPPUNIT_ASSERT( !s.insert( 10 ));
343 CPPUNIT_ASSERT( !s.empty() );
344 CPPUNIT_ASSERT( check_size( s, 1 ));
346 CPPUNIT_ASSERT( !s.find_with( 20, pred ) );
347 CPPUNIT_ASSERT( s.insert( std::make_pair(20, 25) ));
348 CPPUNIT_ASSERT( !s.empty() );
349 CPPUNIT_ASSERT( check_size( s, 2 ));
350 CPPUNIT_ASSERT( s.find_with( 10, pred ) );
351 CPPUNIT_ASSERT( s.find( key = 20 ) );
352 CPPUNIT_ASSERT( s.find_with( key, pred, find_functor() ) );
356 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
357 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
358 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
359 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
364 CPPUNIT_ASSERT( s.find_with( key, pred, std::ref( f ) ) );
365 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
366 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
367 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
369 CPPUNIT_ASSERT( !s.empty() );
370 CPPUNIT_ASSERT( check_size( s, 2 ));
372 CPPUNIT_ASSERT( !s.find( 25 ) );
373 CPPUNIT_ASSERT( s.insert( std::make_pair(25, -1), insert_functor() ));
374 CPPUNIT_ASSERT( !s.empty() );
375 CPPUNIT_ASSERT( check_size( s, 3 ));
379 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
380 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
381 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
388 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
389 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
390 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
391 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
392 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
394 std::pair<bool, bool> ensureResult = s.ensure( key, ensure_functor() );
395 CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second );
396 CPPUNIT_ASSERT( !s.empty() );
397 CPPUNIT_ASSERT( check_size( s, 3 ));
400 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
401 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
402 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
403 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 1 );
404 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
407 ensureResult = s.ensure( std::make_pair(13, 1300), ensure_functor() );
408 CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
409 CPPUNIT_ASSERT( !s.empty() );
410 CPPUNIT_ASSERT( check_size( s, 4 ));
414 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
415 CPPUNIT_ASSERT( f.m_found.nKey == 13 );
416 CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
417 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
418 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 1 );
422 CPPUNIT_ASSERT( s.erase(13) );
423 CPPUNIT_ASSERT( !s.find( 13 ));
424 CPPUNIT_ASSERT( !s.empty() );
425 CPPUNIT_ASSERT( check_size( s, 3 ));
426 CPPUNIT_ASSERT( !s.erase(13) );
427 CPPUNIT_ASSERT( !s.empty() );
428 CPPUNIT_ASSERT( check_size( s, 3 ));
430 CPPUNIT_ASSERT( s.find( 10 ));
431 CPPUNIT_ASSERT( s.erase_with( 10, pred ));
432 CPPUNIT_ASSERT( !s.find( 10 ));
433 CPPUNIT_ASSERT( !s.empty() );
434 CPPUNIT_ASSERT( check_size( s, 2 ));
435 CPPUNIT_ASSERT( !s.erase_with(10, pred) );
436 CPPUNIT_ASSERT( !s.empty() );
437 CPPUNIT_ASSERT( check_size( s, 2 ));
439 CPPUNIT_ASSERT( s.find(20) );
442 CPPUNIT_ASSERT( s.erase( 20, std::ref( f ) ) );
443 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
444 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
446 CPPUNIT_ASSERT( s.insert(235))
447 CPPUNIT_ASSERT( s.erase_with( 235, pred, std::ref( f ) ) );
448 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
449 CPPUNIT_ASSERT( f.m_found.nVal == 235 );
451 CPPUNIT_ASSERT( !s.find( 20 ));
452 CPPUNIT_ASSERT( !s.empty() );
453 CPPUNIT_ASSERT( check_size( s, 1 ));
456 CPPUNIT_ASSERT( s.empty() );
457 CPPUNIT_ASSERT( check_size( s, 0 ));
460 CPPUNIT_ASSERT( s.emplace( 151 )) ; // key = 151, val = 151
461 CPPUNIT_ASSERT( s.emplace( 174, 471 )) ; // key = 174, val = 471
462 CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
463 CPPUNIT_ASSERT( !s.empty() );
464 CPPUNIT_ASSERT( check_size( s, 3 ));
466 CPPUNIT_ASSERT( s.find(151));
467 CPPUNIT_ASSERT( s.find_with(174, pred ));
468 CPPUNIT_ASSERT( s.find(190));
473 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
474 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
475 CPPUNIT_ASSERT( f.m_found.nVal == 151 );
478 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
479 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
480 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
483 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
484 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
485 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
489 CPPUNIT_ASSERT( s.empty() );
490 CPPUNIT_ASSERT( check_size( s, 0 ));
493 template <class Set, class Predicate>
497 CPPUNIT_ASSERT( s.bucket_count() == 32 );
498 CPPUNIT_ASSERT( s.lock_count() == 32 );
500 cds::OS::Timer timer;
502 test_int_with( s, Predicate() );
505 for ( int i = 0; i < 10000; i++ ) {
509 CPPUNIT_MSG( " Duration=" << timer.duration() );
513 void Cuckoo_Striped_list_unord();
514 void Cuckoo_Striped_list_unord_storehash();
515 void Cuckoo_Striped_list_cmp();
516 void Cuckoo_Striped_list_cmp_storehash();
517 void Cuckoo_Striped_list_less();
518 void Cuckoo_Striped_list_less_storehash();
519 void Cuckoo_Striped_list_less_cmp();
520 void Cuckoo_Striped_list_less_cmp_storehash();
521 void Cuckoo_Striped_list_less_cmp_eq();
522 void Cuckoo_Striped_list_less_cmp_eq_storehash();
524 void Cuckoo_Striped_vector_unord();
525 void Cuckoo_Striped_vector_unord_storehash();
526 void Cuckoo_Striped_vector_cmp();
527 void Cuckoo_Striped_vector_cmp_storehash();
528 void Cuckoo_Striped_vector_less();
529 void Cuckoo_Striped_vector_less_storehash();
530 void Cuckoo_Striped_vector_less_cmp();
531 void Cuckoo_Striped_vector_less_cmp_storehash();
532 void Cuckoo_Striped_vector_less_cmp_eq();
533 void Cuckoo_Striped_vector_less_cmp_eq_storehash();
535 void Cuckoo_Refinable_list_unord();
536 void Cuckoo_Refinable_list_unord_storehash();
537 void Cuckoo_Refinable_list_cmp();
538 void Cuckoo_Refinable_list_cmp_storehash();
539 void Cuckoo_Refinable_list_less();
540 void Cuckoo_Refinable_list_less_storehash();
541 void Cuckoo_Refinable_list_less_cmp();
542 void Cuckoo_Refinable_list_less_cmp_storehash();
543 void Cuckoo_Refinable_list_less_cmp_eq();
544 void Cuckoo_Refinable_list_less_cmp_eq_storehash();
546 void Cuckoo_Refinable_vector_unord();
547 void Cuckoo_Refinable_vector_unord_storehash();
548 void Cuckoo_Refinable_vector_cmp();
549 void Cuckoo_Refinable_vector_cmp_storehash();
550 void Cuckoo_Refinable_vector_less();
551 void Cuckoo_Refinable_vector_less_storehash();
552 void Cuckoo_Refinable_vector_less_cmp();
553 void Cuckoo_Refinable_vector_less_cmp_storehash();
554 void Cuckoo_Refinable_vector_less_cmp_eq();
555 void Cuckoo_Refinable_vector_less_cmp_eq_storehash();
557 CPPUNIT_TEST_SUITE(CuckooSetHdrTest)
558 CPPUNIT_TEST( Cuckoo_Striped_list_unord)
559 CPPUNIT_TEST( Cuckoo_Striped_list_unord_storehash)
560 CPPUNIT_TEST( Cuckoo_Striped_list_cmp)
561 CPPUNIT_TEST( Cuckoo_Striped_list_cmp_storehash)
562 CPPUNIT_TEST( Cuckoo_Striped_list_less)
563 CPPUNIT_TEST( Cuckoo_Striped_list_less_storehash)
564 CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp)
565 CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp_storehash)
566 CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp_eq)
567 CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp_eq_storehash)
569 CPPUNIT_TEST( Cuckoo_Striped_vector_unord)
570 CPPUNIT_TEST( Cuckoo_Striped_vector_unord_storehash)
571 CPPUNIT_TEST( Cuckoo_Striped_vector_cmp)
572 CPPUNIT_TEST( Cuckoo_Striped_vector_cmp_storehash)
573 CPPUNIT_TEST( Cuckoo_Striped_vector_less)
574 CPPUNIT_TEST( Cuckoo_Striped_vector_less_storehash)
575 CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp)
576 CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp_storehash)
577 CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp_eq)
578 CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp_eq_storehash)
580 CPPUNIT_TEST( Cuckoo_Refinable_list_unord)
581 CPPUNIT_TEST( Cuckoo_Refinable_list_unord_storehash)
582 CPPUNIT_TEST( Cuckoo_Refinable_list_cmp)
583 CPPUNIT_TEST( Cuckoo_Refinable_list_cmp_storehash)
584 CPPUNIT_TEST( Cuckoo_Refinable_list_less)
585 CPPUNIT_TEST( Cuckoo_Refinable_list_less_storehash)
586 CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp)
587 CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp_storehash)
588 CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp_eq)
589 CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp_eq_storehash)
591 CPPUNIT_TEST( Cuckoo_Refinable_vector_unord)
592 CPPUNIT_TEST( Cuckoo_Refinable_vector_unord_storehash)
593 CPPUNIT_TEST( Cuckoo_Refinable_vector_cmp)
594 CPPUNIT_TEST( Cuckoo_Refinable_vector_cmp_storehash)
595 CPPUNIT_TEST( Cuckoo_Refinable_vector_less)
596 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_storehash)
597 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp)
598 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp_storehash)
599 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp_eq)
600 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp_eq_storehash)
601 CPPUNIT_TEST_SUITE_END()
606 #endif // #ifndef __CDSTEST_HDR_CUCKOO_SET_H