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
13 // forward namespace declaration
15 namespace container {}
20 using misc::check_size;
22 namespace cc = cds::container;
23 namespace co = cds::opt;
26 class CuckooSetHdrTest: public CppUnitMini::TestCase
31 unsigned int nFindCount ; // count of find-functor calling
32 unsigned int nEnsureNewCount;
33 unsigned int nEnsureCount;
37 memset( this, 0, sizeof(*this));
40 void copy( stat const& s )
42 nFindCount = s.nFindCount;
43 nEnsureCount = s.nEnsureCount;
44 nEnsureNewCount = s.nEnsureNewCount;
48 struct item: public stat
61 item (int key, int val )
66 item( std::pair<int,int> const& p )
76 item& operator=(item const& i)
102 size_t operator()( int i ) const
104 return co::v::hash<int>()( i );
107 size_t operator()( std::pair<int,int> const& i ) const
109 return co::v::hash<int>()( i.first );
112 template <typename Item>
113 size_t operator()( Item const& i ) const
115 return (*this)( i.key() );
119 struct hash2: private hash1
121 typedef hash1 base_class;
123 size_t operator()( int i ) const
125 return ~( base_class::operator()(i));
127 template <typename Item>
128 size_t operator()( const Item& i ) const
130 return ~( base_class::operator()(i));
132 size_t operator()( std::pair<int,int> const& i ) const
134 return ~( base_class::operator()(i));
138 struct simple_item_counter {
141 simple_item_counter()
160 operator size_t() const
166 template <typename T>
169 bool operator ()(const T& v1, const T& v2 ) const
171 return v1.key() < v2.key();
174 template <typename Q>
175 bool operator ()(const T& v1, const Q& v2 ) const
177 return v1.key() < v2;
180 template <typename Q>
181 bool operator ()(const Q& v1, const T& v2 ) const
183 return v1 < v2.key();
186 bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
188 return v1.first < v2.key();
191 bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
193 return v1.key() < v2.first;
197 template <typename T>
199 int operator ()(const T& v1, const T& v2 ) const
201 if ( v1.key() < v2.key() )
203 return v1.key() > v2.key() ? 1 : 0;
206 template <typename Q>
207 int operator ()(const T& v1, const Q& v2 ) const
211 return v1.key() > v2 ? 1 : 0;
214 template <typename Q>
215 int operator ()(const Q& v1, const T& v2 ) const
219 return v1 > v2.key() ? 1 : 0;
222 int operator()( std::pair<int,int> const& v1, T const& v2 ) const
224 if ( v1.first < v2.key() )
226 return v1.first > v2.key() ? 1 : 0;
229 int operator()( T const& v1, std::pair<int,int> const& v2 ) const
231 if ( v1.key() < v2.first )
233 return v1.key() > v2.first ? 1 : 0;
237 template <typename T>
240 bool operator ()(const T& v1, const T& v2 ) const
242 return v1.key() == v2.key();
245 template <typename Q>
246 bool operator ()(const T& v1, const Q& v2 ) const
248 return v1.key() == v2;
251 template <typename Q>
252 bool operator ()(const Q& v1, const T& v2 ) const
254 return v1 == v2.key();
257 bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
259 return v1.first == v2.key();
262 bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
264 return v1.key() == v2.first;
270 template <typename Item, typename T>
271 void operator()( Item& i, T& /*val*/ )
275 template <typename Item, typename T>
276 void operator()( Item& i, T const& /*val*/ )
282 template <typename Item>
287 template <typename T>
288 void operator()( Item& i, T& /*val*/ )
293 void operator()( Item const& i )
299 struct insert_functor
301 template <typename Item>
302 void operator()(Item& i )
304 i.nVal = i.nKey * 100;
308 template <typename Item, typename Q>
309 static void ensure_func( bool bNew, Item& i, Q& /*val*/ )
317 struct ensure_functor
319 template <typename Item, typename Q>
320 void operator()( bool bNew, Item& i, Q& val )
322 ensure_func( bNew, i, val );
326 template <class Set, typename Predicate>
327 void test_int_with( Set& s, Predicate pred )
329 typedef typename Set::value_type value_type;
335 CPPUNIT_ASSERT( !s.find( 10 ) );
336 CPPUNIT_ASSERT( s.insert( 10 ));
337 CPPUNIT_ASSERT( !s.empty() );
338 CPPUNIT_ASSERT( check_size( s, 1 ));
339 CPPUNIT_ASSERT( s.find( 10 ) );
341 CPPUNIT_ASSERT( !s.insert( 10 ));
342 CPPUNIT_ASSERT( !s.empty() );
343 CPPUNIT_ASSERT( check_size( s, 1 ));
345 CPPUNIT_ASSERT( !s.find_with( 20, pred ) );
346 CPPUNIT_ASSERT( s.insert( std::make_pair(20, 25) ));
347 CPPUNIT_ASSERT( !s.empty() );
348 CPPUNIT_ASSERT( check_size( s, 2 ));
349 CPPUNIT_ASSERT( s.find_with( 10, pred ) );
350 CPPUNIT_ASSERT( s.find( key = 20 ) );
351 CPPUNIT_ASSERT( s.find_with( key, pred, find_functor() ) );
355 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
356 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
357 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
358 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
363 CPPUNIT_ASSERT( s.find_with( key, pred, std::ref( f ) ) );
364 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
365 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
366 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
368 CPPUNIT_ASSERT( !s.empty() );
369 CPPUNIT_ASSERT( check_size( s, 2 ));
371 CPPUNIT_ASSERT( !s.find( 25 ) );
372 CPPUNIT_ASSERT( s.insert( std::make_pair(25, -1), insert_functor() ));
373 CPPUNIT_ASSERT( !s.empty() );
374 CPPUNIT_ASSERT( check_size( s, 3 ));
378 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
379 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
380 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
387 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
388 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
389 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
390 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
391 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
393 std::pair<bool, bool> ensureResult = s.ensure( key, ensure_functor() );
394 CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second );
395 CPPUNIT_ASSERT( !s.empty() );
396 CPPUNIT_ASSERT( check_size( s, 3 ));
399 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
400 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
401 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
402 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 1 );
403 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
406 ensureResult = s.ensure( std::make_pair(13, 1300), ensure_functor() );
407 CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
408 CPPUNIT_ASSERT( !s.empty() );
409 CPPUNIT_ASSERT( check_size( s, 4 ));
413 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
414 CPPUNIT_ASSERT( f.m_found.nKey == 13 );
415 CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
416 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
417 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 1 );
421 CPPUNIT_ASSERT( s.erase(13) );
422 CPPUNIT_ASSERT( !s.find( 13 ));
423 CPPUNIT_ASSERT( !s.empty() );
424 CPPUNIT_ASSERT( check_size( s, 3 ));
425 CPPUNIT_ASSERT( !s.erase(13) );
426 CPPUNIT_ASSERT( !s.empty() );
427 CPPUNIT_ASSERT( check_size( s, 3 ));
429 CPPUNIT_ASSERT( s.find( 10 ));
430 CPPUNIT_ASSERT( s.erase_with( 10, pred ));
431 CPPUNIT_ASSERT( !s.find( 10 ));
432 CPPUNIT_ASSERT( !s.empty() );
433 CPPUNIT_ASSERT( check_size( s, 2 ));
434 CPPUNIT_ASSERT( !s.erase_with(10, pred) );
435 CPPUNIT_ASSERT( !s.empty() );
436 CPPUNIT_ASSERT( check_size( s, 2 ));
438 CPPUNIT_ASSERT( s.find(20) );
441 CPPUNIT_ASSERT( s.erase( 20, std::ref( f ) ) );
442 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
443 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
445 CPPUNIT_ASSERT( s.insert(235))
446 CPPUNIT_ASSERT( s.erase_with( 235, pred, std::ref( f ) ) );
447 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
448 CPPUNIT_ASSERT( f.m_found.nVal == 235 );
450 CPPUNIT_ASSERT( !s.find( 20 ));
451 CPPUNIT_ASSERT( !s.empty() );
452 CPPUNIT_ASSERT( check_size( s, 1 ));
455 CPPUNIT_ASSERT( s.empty() );
456 CPPUNIT_ASSERT( check_size( s, 0 ));
459 CPPUNIT_ASSERT( s.emplace( 151 )) ; // key = 151, val = 151
460 CPPUNIT_ASSERT( s.emplace( 174, 471 )) ; // key = 174, val = 471
461 CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
462 CPPUNIT_ASSERT( !s.empty() );
463 CPPUNIT_ASSERT( check_size( s, 3 ));
465 CPPUNIT_ASSERT( s.find(151));
466 CPPUNIT_ASSERT( s.find_with(174, pred ));
467 CPPUNIT_ASSERT( s.find(190));
472 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
473 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
474 CPPUNIT_ASSERT( f.m_found.nVal == 151 );
477 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
478 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
479 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
482 CPPUNIT_ASSERT( s.find( key, std::ref( f ) ) );
483 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
484 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
488 CPPUNIT_ASSERT( s.empty() );
489 CPPUNIT_ASSERT( check_size( s, 0 ));
492 template <class Set, class Predicate>
496 CPPUNIT_ASSERT( s.bucket_count() == 32 );
497 CPPUNIT_ASSERT( s.lock_count() == 32 );
499 cds::OS::Timer timer;
501 test_int_with( s, Predicate() );
504 for ( int i = 0; i < 10000; i++ ) {
508 CPPUNIT_MSG( " Duration=" << timer.duration() );
512 void Cuckoo_Striped_list_unord();
513 void Cuckoo_Striped_list_unord_storehash();
514 void Cuckoo_Striped_list_cmp();
515 void Cuckoo_Striped_list_cmp_storehash();
516 void Cuckoo_Striped_list_less();
517 void Cuckoo_Striped_list_less_storehash();
518 void Cuckoo_Striped_list_less_cmp();
519 void Cuckoo_Striped_list_less_cmp_storehash();
520 void Cuckoo_Striped_list_less_cmp_eq();
521 void Cuckoo_Striped_list_less_cmp_eq_storehash();
523 void Cuckoo_Striped_vector_unord();
524 void Cuckoo_Striped_vector_unord_storehash();
525 void Cuckoo_Striped_vector_cmp();
526 void Cuckoo_Striped_vector_cmp_storehash();
527 void Cuckoo_Striped_vector_less();
528 void Cuckoo_Striped_vector_less_storehash();
529 void Cuckoo_Striped_vector_less_cmp();
530 void Cuckoo_Striped_vector_less_cmp_storehash();
531 void Cuckoo_Striped_vector_less_cmp_eq();
532 void Cuckoo_Striped_vector_less_cmp_eq_storehash();
534 void Cuckoo_Refinable_list_unord();
535 void Cuckoo_Refinable_list_unord_storehash();
536 void Cuckoo_Refinable_list_cmp();
537 void Cuckoo_Refinable_list_cmp_storehash();
538 void Cuckoo_Refinable_list_less();
539 void Cuckoo_Refinable_list_less_storehash();
540 void Cuckoo_Refinable_list_less_cmp();
541 void Cuckoo_Refinable_list_less_cmp_storehash();
542 void Cuckoo_Refinable_list_less_cmp_eq();
543 void Cuckoo_Refinable_list_less_cmp_eq_storehash();
545 void Cuckoo_Refinable_vector_unord();
546 void Cuckoo_Refinable_vector_unord_storehash();
547 void Cuckoo_Refinable_vector_cmp();
548 void Cuckoo_Refinable_vector_cmp_storehash();
549 void Cuckoo_Refinable_vector_less();
550 void Cuckoo_Refinable_vector_less_storehash();
551 void Cuckoo_Refinable_vector_less_cmp();
552 void Cuckoo_Refinable_vector_less_cmp_storehash();
553 void Cuckoo_Refinable_vector_less_cmp_eq();
554 void Cuckoo_Refinable_vector_less_cmp_eq_storehash();
556 CPPUNIT_TEST_SUITE(CuckooSetHdrTest)
557 CPPUNIT_TEST( Cuckoo_Striped_list_unord)
558 CPPUNIT_TEST( Cuckoo_Striped_list_unord_storehash)
559 CPPUNIT_TEST( Cuckoo_Striped_list_cmp)
560 CPPUNIT_TEST( Cuckoo_Striped_list_cmp_storehash)
561 CPPUNIT_TEST( Cuckoo_Striped_list_less)
562 CPPUNIT_TEST( Cuckoo_Striped_list_less_storehash)
563 CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp)
564 CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp_storehash)
565 CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp_eq)
566 CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp_eq_storehash)
568 CPPUNIT_TEST( Cuckoo_Striped_vector_unord)
569 CPPUNIT_TEST( Cuckoo_Striped_vector_unord_storehash)
570 CPPUNIT_TEST( Cuckoo_Striped_vector_cmp)
571 CPPUNIT_TEST( Cuckoo_Striped_vector_cmp_storehash)
572 CPPUNIT_TEST( Cuckoo_Striped_vector_less)
573 CPPUNIT_TEST( Cuckoo_Striped_vector_less_storehash)
574 CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp)
575 CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp_storehash)
576 CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp_eq)
577 CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp_eq_storehash)
579 CPPUNIT_TEST( Cuckoo_Refinable_list_unord)
580 CPPUNIT_TEST( Cuckoo_Refinable_list_unord_storehash)
581 CPPUNIT_TEST( Cuckoo_Refinable_list_cmp)
582 CPPUNIT_TEST( Cuckoo_Refinable_list_cmp_storehash)
583 CPPUNIT_TEST( Cuckoo_Refinable_list_less)
584 CPPUNIT_TEST( Cuckoo_Refinable_list_less_storehash)
585 CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp)
586 CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp_storehash)
587 CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp_eq)
588 CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp_eq_storehash)
590 CPPUNIT_TEST( Cuckoo_Refinable_vector_unord)
591 CPPUNIT_TEST( Cuckoo_Refinable_vector_unord_storehash)
592 CPPUNIT_TEST( Cuckoo_Refinable_vector_cmp)
593 CPPUNIT_TEST( Cuckoo_Refinable_vector_cmp_storehash)
594 CPPUNIT_TEST( Cuckoo_Refinable_vector_less)
595 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_storehash)
596 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp)
597 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp_storehash)
598 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp_eq)
599 CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp_eq_storehash)
600 CPPUNIT_TEST_SUITE_END()
605 #endif // #ifndef CDSTEST_HDR_CUCKOO_SET_H