tests/test-hdr/set/hdr_cuckoo_set.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDSTEST_HDR_CUCKOO_SET_H
   4 #define __CDSTEST_HDR_CUCKOO_SET_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7 #include "size_check.h"
   8
   9 #include <cds/opt/hash.h>
  10 #include <cds/os/timer.h>
  11 #include <cds/ref.h>
  12 #include <algorithm>    // random_shuffle
  13
  14 // forward namespace declaration
  15 namespace cds {
  16     namespace container {}
  17     namespace opt {}
  18 }
  19
  20 namespace set {
  21     using misc::check_size;
  22
  23     namespace cc = cds::container;
  24     namespace co = cds::opt;
  25
  26
  27     class CuckooSetHdrTest: public CppUnitMini::TestCase
  28     {
  29     public:
  30         struct stat
  31         {
  32             unsigned int nFindCount     ;   // count of find-functor calling
  33             unsigned int nEnsureNewCount;
  34             unsigned int nEnsureCount;
  35
  36             stat()
  37             {
  38                 memset( this, 0, sizeof(*this));
  39             }
  40
  41             void copy( stat const& s )
  42             {
  43                 nFindCount = s.nFindCount;
  44                 nEnsureCount = s.nEnsureCount;
  45                 nEnsureNewCount = s.nEnsureNewCount;
  46             }
  47         };
  48
  49         struct item: public stat
  50         {
  51             int nKey;
  52             int nVal;
  53
  54             item()
  55             {}
  56
  57             item( int key )
  58                 : nKey( key )
  59                 , nVal( key )
  60             {}
  61
  62             item (int key, int val )
  63                 : nKey(key)
  64                 , nVal( val )
  65             {}
  66
  67             item( std::pair<int,int> const& p )
  68                 : nKey( p.first )
  69                 , nVal( p.second )
  70             {}
  71
  72             item( item const& i )
  73                 : nKey( i.nKey )
  74                 , nVal( i.nVal )
  75             {}
  76
  77             item& operator=(item const& i)
  78             {
  79                 nKey = i.nKey;
  80                 nVal = i.nVal;
  81                 stat::copy(i);
  82
  83                 return *this;
  84             }
  85
  86             item( item&& i )
  87                 : nKey( i.nKey )
  88                 , nVal( i.nVal )
  89             {}
  90
  91             int key() const
  92             {
  93                 return nKey;
  94             }
  95
  96             int val() const
  97             {
  98                 return nVal;
  99             }
 100         };
 101
 102         struct hash1 {
 103             size_t operator()( int i ) const
 104             {
 105                 return co::v::hash<int>()( i );
 106             }
 107
 108             size_t operator()( std::pair<int,int> const& i ) const
 109             {
 110                 return co::v::hash<int>()( i.first );
 111             }
 112
 113             template <typename Item>
 114             size_t operator()( Item const& i ) const
 115             {
 116                 return (*this)( i.key() );
 117             }
 118         };
 119
 120         struct hash2: private hash1
 121         {
 122             typedef hash1 base_class;
 123
 124             size_t operator()( int i ) const
 125             {
 126                 return ~( base_class::operator()(i));
 127             }
 128             template <typename Item>
 129             size_t operator()( const Item& i ) const
 130             {
 131                 return ~( base_class::operator()(i));
 132             }
 133             size_t operator()( std::pair<int,int> const& i ) const
 134             {
 135                 return ~( base_class::operator()(i));
 136             }
 137         };
 138
 139         struct simple_item_counter {
 140             size_t  m_nCount;
 141
 142             simple_item_counter()
 143                 : m_nCount(0)
 144             {}
 145
 146             size_t operator ++()
 147             {
 148                 return ++m_nCount;
 149             }
 150
 151             size_t operator --()
 152             {
 153                 return --m_nCount;
 154             }
 155
 156             void reset()
 157             {
 158                 m_nCount = 0;
 159             }
 160
 161             operator size_t() const
 162             {
 163                 return m_nCount;
 164             }
 165         };
 166
 167         template <typename T>
 168         struct less
 169         {
 170             bool operator ()(const T& v1, const T& v2 ) const
 171             {
 172                 return v1.key() < v2.key();
 173             }
 174
 175             template <typename Q>
 176             bool operator ()(const T& v1, const Q& v2 ) const
 177             {
 178                 return v1.key() < v2;
 179             }
 180
 181             template <typename Q>
 182             bool operator ()(const Q& v1, const T& v2 ) const
 183             {
 184                 return v1 < v2.key();
 185             }
 186
 187             bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
 188             {
 189                 return v1.first < v2.key();
 190             }
 191
 192             bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
 193             {
 194                 return v1.key() < v2.first;
 195             }
 196         };
 197
 198         template <typename T>
 199         struct cmp {
 200             int operator ()(const T& v1, const T& v2 ) const
 201             {
 202                 if ( v1.key() < v2.key() )
 203                     return -1;
 204                 return v1.key() > v2.key() ? 1 : 0;
 205             }
 206
 207             template <typename Q>
 208             int operator ()(const T& v1, const Q& v2 ) const
 209             {
 210                 if ( v1.key() < v2 )
 211                     return -1;
 212                 return v1.key() > v2 ? 1 : 0;
 213             }
 214
 215             template <typename Q>
 216             int operator ()(const Q& v1, const T& v2 ) const
 217             {
 218                 if ( v1 < v2.key() )
 219                     return -1;
 220                 return v1 > v2.key() ? 1 : 0;
 221             }
 222
 223             int operator()( std::pair<int,int> const& v1, T const& v2 ) const
 224             {
 225                 if ( v1.first < v2.key() )
 226                     return -1;
 227                 return v1.first > v2.key() ? 1 : 0;
 228             }
 229
 230             int operator()( T const& v1, std::pair<int,int> const& v2 ) const
 231             {
 232                 if ( v1.key() < v2.first )
 233                     return -1;
 234                 return v1.key() > v2.first ? 1 : 0;
 235             }
 236         };
 237
 238         template <typename T>
 239         struct equal
 240         {
 241             bool operator ()(const T& v1, const T& v2 ) const
 242             {
 243                 return v1.key() == v2.key();
 244             }
 245
 246             template <typename Q>
 247             bool operator ()(const T& v1, const Q& v2 ) const
 248             {
 249                 return v1.key() == v2;
 250             }
 251
 252             template <typename Q>
 253             bool operator ()(const Q& v1, const T& v2 ) const
 254             {
 255                 return v1 == v2.key();
 256             }
 257
 258             bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
 259             {
 260                 return v1.first == v2.key();
 261             }
 262
 263             bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
 264             {
 265                 return v1.key() == v2.first;
 266             }
 267         };
 268
 269         struct find_functor
 270         {
 271             template <typename Item, typename T>
 272             void operator()( Item& i, T& val )
 273             {
 274                 ++i.nFindCount;
 275             }
 276             template <typename Item, typename T>
 277             void operator()( Item& i, T const& val )
 278             {
 279                 ++i.nFindCount;
 280             }
 281         };
 282
 283         template <typename Item>
 284         struct copy_found
 285         {
 286             Item    m_found;
 287
 288             template <typename T>
 289             void operator()( Item& i, T& /*val*/ )
 290             {
 291                 m_found = i;
 292             }
 293
 294             void operator()( Item const& i )
 295             {
 296                 m_found = i;
 297             }
 298         };
 299
 300         struct insert_functor
 301         {
 302             template <typename Item>
 303             void operator()(Item& i )
 304             {
 305                 i.nVal = i.nKey * 100;
 306             }
 307         };
 308
 309         template <typename Item, typename Q>
 310         static void ensure_func( bool bNew, Item& i, Q& /*val*/ )
 311         {
 312             if ( bNew )
 313                 ++i.nEnsureNewCount;
 314             else
 315                 ++i.nEnsureCount;
 316         }
 317
 318         struct ensure_functor
 319         {
 320             template <typename Item, typename Q>
 321             void operator()( bool bNew, Item& i, Q& val )
 322             {
 323                 ensure_func( bNew, i, val );
 324             }
 325         };
 326
 327         template <class Set, typename Predicate>
 328         void test_int_with( Set& s, Predicate pred )
 329         {
 330             typedef typename Set::value_type    value_type;
 331
 332             item itm;
 333             int key;
 334
 335             // insert/find test
 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 ) );
 341
 342             CPPUNIT_ASSERT( !s.insert( 10 ));
 343             CPPUNIT_ASSERT( !s.empty() );
 344             CPPUNIT_ASSERT( check_size( s, 1 ));
 345
 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() ) );
 353             {
 354                 copy_found<item> f;
 355                 key = 20;
 356                 CPPUNIT_ASSERT( s.find( key, boost::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 );
 360             }
 361             {
 362                 copy_found<item> f;
 363                 key = 20;
 364                 CPPUNIT_ASSERT( s.find_with( key, pred, boost::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 );
 368             }
 369             CPPUNIT_ASSERT( !s.empty() );
 370             CPPUNIT_ASSERT( check_size( s, 2 ));
 371
 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 ));
 376             {
 377                 copy_found<item> f;
 378                 key = 25;
 379                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 380                 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
 381                 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
 382             }
 383
 384             // ensure test
 385             key = 10;
 386             {
 387                 copy_found<item> f;
 388                 CPPUNIT_ASSERT( s.find( key, boost::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 );
 393             }
 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 ));
 398             {
 399                 copy_found<item> f;
 400                 CPPUNIT_ASSERT( s.find( key, boost::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 );
 405             }
 406
 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 ));
 411             {
 412                 copy_found<item> f;
 413                 key = 13;
 414                 CPPUNIT_ASSERT( s.find( key, boost::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 );
 419             }
 420
 421             // erase test
 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 ));
 429
 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 ));
 438
 439             CPPUNIT_ASSERT( s.find(20) );
 440             {
 441                 copy_found<item> f;
 442                 CPPUNIT_ASSERT( s.erase( 20, boost::ref(f) ));
 443                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 444                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 445
 446                 CPPUNIT_ASSERT( s.insert(235))
 447                     CPPUNIT_ASSERT( s.erase_with( 235, pred, boost::ref(f) ));
 448                 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
 449                 CPPUNIT_ASSERT( f.m_found.nVal == 235 );
 450             }
 451             CPPUNIT_ASSERT( !s.find( 20 ));
 452             CPPUNIT_ASSERT( !s.empty() );
 453             CPPUNIT_ASSERT( check_size( s, 1 ));
 454
 455             s.clear();
 456             CPPUNIT_ASSERT( s.empty() );
 457             CPPUNIT_ASSERT( check_size( s, 0 ));
 458
 459             // emplace test
 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 ));
 465
 466             CPPUNIT_ASSERT( s.find(151));
 467             CPPUNIT_ASSERT( s.find_with(174, pred ));
 468             CPPUNIT_ASSERT( s.find(190));
 469
 470             {
 471                 copy_found<item> f;
 472                 key = 151;
 473                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 474                 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
 475                 CPPUNIT_ASSERT( f.m_found.nVal == 151 );
 476
 477                 key = 174;
 478                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 479                 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
 480                 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
 481
 482                 key = 190;
 483                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 484                 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
 485                 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
 486             }
 487
 488             s.clear();
 489             CPPUNIT_ASSERT( s.empty() );
 490             CPPUNIT_ASSERT( check_size( s, 0 ));
 491         }
 492
 493         template <class Set, class Predicate>
 494         void test_int()
 495         {
 496             Set s( 32, 4, 3 );
 497             CPPUNIT_ASSERT( s.bucket_count() == 32 );
 498             CPPUNIT_ASSERT( s.lock_count() == 32 );
 499
 500             cds::OS::Timer    timer;
 501
 502             test_int_with( s, Predicate() );
 503
 504             // Resizing test
 505             for ( int i = 0; i < 10000; i++ ) {
 506                 s.insert( i );
 507             }
 508
 509             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 510         }
 511
 512     public:
 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();
 523
 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();
 534
 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();
 545
 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();
 556
 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)
 568
 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)
 579
 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)
 590
 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()
 602     };
 603
 604 } // namespace set
 605
 606 #endif // #ifndef __CDSTEST_HDR_CUCKOO_SET_H