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
  87 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
  88             item( item&& i )
  89                 : nKey( i.nKey )
  90                 , nVal( i.nVal )
  91             {}
  92 #endif
  93
  94             int key() const
  95             {
  96                 return nKey;
  97             }
  98
  99             int val() const
 100             {
 101                 return nVal;
 102             }
 103         };
 104
 105         struct hash1 {
 106             size_t operator()( int i ) const
 107             {
 108                 return co::v::hash<int>()( i );
 109             }
 110
 111             size_t operator()( std::pair<int,int> const& i ) const
 112             {
 113                 return co::v::hash<int>()( i.first );
 114             }
 115
 116             template <typename Item>
 117             size_t operator()( Item const& i ) const
 118             {
 119                 return (*this)( i.key() );
 120             }
 121         };
 122
 123         struct hash2: private hash1
 124         {
 125             typedef hash1 base_class;
 126
 127             size_t operator()( int i ) const
 128             {
 129                 return ~( base_class::operator()(i));
 130             }
 131             template <typename Item>
 132             size_t operator()( const Item& i ) const
 133             {
 134                 return ~( base_class::operator()(i));
 135             }
 136             size_t operator()( std::pair<int,int> const& i ) const
 137             {
 138                 return ~( base_class::operator()(i));
 139             }
 140         };
 141
 142         struct simple_item_counter {
 143             size_t  m_nCount;
 144
 145             simple_item_counter()
 146                 : m_nCount(0)
 147             {}
 148
 149             size_t operator ++()
 150             {
 151                 return ++m_nCount;
 152             }
 153
 154             size_t operator --()
 155             {
 156                 return --m_nCount;
 157             }
 158
 159             void reset()
 160             {
 161                 m_nCount = 0;
 162             }
 163
 164             operator size_t() const
 165             {
 166                 return m_nCount;
 167             }
 168         };
 169
 170         template <typename T>
 171         struct less
 172         {
 173             bool operator ()(const T& v1, const T& v2 ) const
 174             {
 175                 return v1.key() < v2.key();
 176             }
 177
 178             template <typename Q>
 179             bool operator ()(const T& v1, const Q& v2 ) const
 180             {
 181                 return v1.key() < v2;
 182             }
 183
 184             template <typename Q>
 185             bool operator ()(const Q& v1, const T& v2 ) const
 186             {
 187                 return v1 < v2.key();
 188             }
 189
 190             bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
 191             {
 192                 return v1.first < v2.key();
 193             }
 194
 195             bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
 196             {
 197                 return v1.key() < v2.first;
 198             }
 199         };
 200
 201         template <typename T>
 202         struct cmp {
 203             int operator ()(const T& v1, const T& v2 ) const
 204             {
 205                 if ( v1.key() < v2.key() )
 206                     return -1;
 207                 return v1.key() > v2.key() ? 1 : 0;
 208             }
 209
 210             template <typename Q>
 211             int operator ()(const T& v1, const Q& v2 ) const
 212             {
 213                 if ( v1.key() < v2 )
 214                     return -1;
 215                 return v1.key() > v2 ? 1 : 0;
 216             }
 217
 218             template <typename Q>
 219             int operator ()(const Q& v1, const T& v2 ) const
 220             {
 221                 if ( v1 < v2.key() )
 222                     return -1;
 223                 return v1 > v2.key() ? 1 : 0;
 224             }
 225
 226             int operator()( std::pair<int,int> const& v1, T const& v2 ) const
 227             {
 228                 if ( v1.first < v2.key() )
 229                     return -1;
 230                 return v1.first > v2.key() ? 1 : 0;
 231             }
 232
 233             int operator()( T const& v1, std::pair<int,int> const& v2 ) const
 234             {
 235                 if ( v1.key() < v2.first )
 236                     return -1;
 237                 return v1.key() > v2.first ? 1 : 0;
 238             }
 239         };
 240
 241         template <typename T>
 242         struct equal
 243         {
 244             bool operator ()(const T& v1, const T& v2 ) const
 245             {
 246                 return v1.key() == v2.key();
 247             }
 248
 249             template <typename Q>
 250             bool operator ()(const T& v1, const Q& v2 ) const
 251             {
 252                 return v1.key() == v2;
 253             }
 254
 255             template <typename Q>
 256             bool operator ()(const Q& v1, const T& v2 ) const
 257             {
 258                 return v1 == v2.key();
 259             }
 260
 261             bool operator ()( std::pair<int, int> const& v1, const T& v2 ) const
 262             {
 263                 return v1.first == v2.key();
 264             }
 265
 266             bool operator ()(const T& v1, std::pair<int, int> const& v2 ) const
 267             {
 268                 return v1.key() == v2.first;
 269             }
 270         };
 271
 272         struct find_functor
 273         {
 274             template <typename Item, typename T>
 275             void operator()( Item& i, T& val )
 276             {
 277                 ++i.nFindCount;
 278             }
 279             template <typename Item, typename T>
 280             void operator()( Item& i, T const& val )
 281             {
 282                 ++i.nFindCount;
 283             }
 284         };
 285
 286         template <typename Item>
 287         struct copy_found
 288         {
 289             Item    m_found;
 290
 291             template <typename T>
 292             void operator()( Item& i, T& /*val*/ )
 293             {
 294                 m_found = i;
 295             }
 296
 297             void operator()( Item const& i )
 298             {
 299                 m_found = i;
 300             }
 301         };
 302
 303         struct insert_functor
 304         {
 305             template <typename Item>
 306             void operator()(Item& i )
 307             {
 308                 i.nVal = i.nKey * 100;
 309             }
 310         };
 311
 312         template <typename Item, typename Q>
 313         static void ensure_func( bool bNew, Item& i, Q& /*val*/ )
 314         {
 315             if ( bNew )
 316                 ++i.nEnsureNewCount;
 317             else
 318                 ++i.nEnsureCount;
 319         }
 320
 321         struct ensure_functor
 322         {
 323             template <typename Item, typename Q>
 324             void operator()( bool bNew, Item& i, Q& val )
 325             {
 326                 ensure_func( bNew, i, val );
 327             }
 328         };
 329
 330         template <class Set, typename Predicate>
 331         void test_int_with( Set& s, Predicate pred )
 332         {
 333             typedef typename Set::value_type    value_type;
 334
 335             item itm;
 336             int key;
 337
 338             // insert/find test
 339             CPPUNIT_ASSERT( !s.find( 10 ) );
 340             CPPUNIT_ASSERT( s.insert( 10 ));
 341             CPPUNIT_ASSERT( !s.empty() );
 342             CPPUNIT_ASSERT( check_size( s, 1 ));
 343             CPPUNIT_ASSERT( s.find( 10 ) );
 344
 345             CPPUNIT_ASSERT( !s.insert( 10 ));
 346             CPPUNIT_ASSERT( !s.empty() );
 347             CPPUNIT_ASSERT( check_size( s, 1 ));
 348
 349             CPPUNIT_ASSERT( !s.find_with( 20, pred ) );
 350             CPPUNIT_ASSERT( s.insert( std::make_pair(20, 25) ));
 351             CPPUNIT_ASSERT( !s.empty() );
 352             CPPUNIT_ASSERT( check_size( s, 2 ));
 353             CPPUNIT_ASSERT( s.find_with( 10, pred ) );
 354             CPPUNIT_ASSERT( s.find( key = 20 ) );
 355             CPPUNIT_ASSERT( s.find_with( key, pred, find_functor() ) );
 356             {
 357                 copy_found<item> f;
 358                 key = 20;
 359                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 360                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 361                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 362                 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
 363             }
 364             {
 365                 copy_found<item> f;
 366                 key = 20;
 367                 CPPUNIT_ASSERT( s.find_with( key, pred, boost::ref(f) ) );
 368                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 369                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 370                 CPPUNIT_ASSERT( f.m_found.nFindCount == 1 );
 371             }
 372             CPPUNIT_ASSERT( !s.empty() );
 373             CPPUNIT_ASSERT( check_size( s, 2 ));
 374
 375             CPPUNIT_ASSERT( !s.find( 25 ) );
 376             CPPUNIT_ASSERT( s.insert( std::make_pair(25, -1), insert_functor() ));
 377             CPPUNIT_ASSERT( !s.empty() );
 378             CPPUNIT_ASSERT( check_size( s, 3 ));
 379             {
 380                 copy_found<item> f;
 381                 key = 25;
 382                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 383                 CPPUNIT_ASSERT( f.m_found.nKey == 25 );
 384                 CPPUNIT_ASSERT( f.m_found.nVal == 2500 );
 385             }
 386
 387             // ensure test
 388             key = 10;
 389             {
 390                 copy_found<item> f;
 391                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 392                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 393                 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
 394                 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
 395                 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
 396             }
 397             std::pair<bool, bool> ensureResult = s.ensure( key, ensure_functor() );
 398             CPPUNIT_ASSERT( ensureResult.first && !ensureResult.second );
 399             CPPUNIT_ASSERT( !s.empty() );
 400             CPPUNIT_ASSERT( check_size( s, 3 ));
 401             {
 402                 copy_found<item> f;
 403                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 404                 CPPUNIT_ASSERT( f.m_found.nKey == 10 );
 405                 CPPUNIT_ASSERT( f.m_found.nVal == 10 );
 406                 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 1 );
 407                 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 0 );
 408             }
 409
 410             ensureResult = s.ensure( std::make_pair(13, 1300), ensure_functor() );
 411             CPPUNIT_ASSERT( ensureResult.first && ensureResult.second );
 412             CPPUNIT_ASSERT( !s.empty() );
 413             CPPUNIT_ASSERT( check_size( s, 4 ));
 414             {
 415                 copy_found<item> f;
 416                 key = 13;
 417                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 418                 CPPUNIT_ASSERT( f.m_found.nKey == 13 );
 419                 CPPUNIT_ASSERT( f.m_found.nVal == 1300 );
 420                 CPPUNIT_ASSERT( f.m_found.nEnsureCount == 0 );
 421                 CPPUNIT_ASSERT( f.m_found.nEnsureNewCount == 1 );
 422             }
 423
 424             // erase test
 425             CPPUNIT_ASSERT( s.erase(13) );
 426             CPPUNIT_ASSERT( !s.find( 13 ));
 427             CPPUNIT_ASSERT( !s.empty() );
 428             CPPUNIT_ASSERT( check_size( s, 3 ));
 429             CPPUNIT_ASSERT( !s.erase(13) );
 430             CPPUNIT_ASSERT( !s.empty() );
 431             CPPUNIT_ASSERT( check_size( s, 3 ));
 432
 433             CPPUNIT_ASSERT( s.find( 10 ));
 434             CPPUNIT_ASSERT( s.erase_with( 10, pred ));
 435             CPPUNIT_ASSERT( !s.find( 10 ));
 436             CPPUNIT_ASSERT( !s.empty() );
 437             CPPUNIT_ASSERT( check_size( s, 2 ));
 438             CPPUNIT_ASSERT( !s.erase_with(10, pred) );
 439             CPPUNIT_ASSERT( !s.empty() );
 440             CPPUNIT_ASSERT( check_size( s, 2 ));
 441
 442             CPPUNIT_ASSERT( s.find(20) );
 443             {
 444                 copy_found<item> f;
 445                 CPPUNIT_ASSERT( s.erase( 20, boost::ref(f) ));
 446                 CPPUNIT_ASSERT( f.m_found.nKey == 20 );
 447                 CPPUNIT_ASSERT( f.m_found.nVal == 25 );
 448
 449                 CPPUNIT_ASSERT( s.insert(235))
 450                     CPPUNIT_ASSERT( s.erase_with( 235, pred, boost::ref(f) ));
 451                 CPPUNIT_ASSERT( f.m_found.nKey == 235 );
 452                 CPPUNIT_ASSERT( f.m_found.nVal == 235 );
 453             }
 454             CPPUNIT_ASSERT( !s.find( 20 ));
 455             CPPUNIT_ASSERT( !s.empty() );
 456             CPPUNIT_ASSERT( check_size( s, 1 ));
 457
 458             s.clear();
 459             CPPUNIT_ASSERT( s.empty() );
 460             CPPUNIT_ASSERT( check_size( s, 0 ));
 461
 462 #       ifdef CDS_EMPLACE_SUPPORT
 463             // emplace test
 464             CPPUNIT_ASSERT( s.emplace( 151 )) ;  // key = 151,  val = 151
 465             CPPUNIT_ASSERT( s.emplace( 174, 471 )) ;    // key = 174, val = 471
 466             CPPUNIT_ASSERT( s.emplace( std::make_pair( 190, 91 ) )) ; // key == 190, val = 91
 467             CPPUNIT_ASSERT( !s.empty() );
 468             CPPUNIT_ASSERT( check_size( s, 3 ));
 469
 470             CPPUNIT_ASSERT( s.find(151));
 471             CPPUNIT_ASSERT( s.find_with(174, pred ));
 472             CPPUNIT_ASSERT( s.find(190));
 473
 474             {
 475                 copy_found<item> f;
 476                 key = 151;
 477                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 478                 CPPUNIT_ASSERT( f.m_found.nKey == 151 );
 479                 CPPUNIT_ASSERT( f.m_found.nVal == 151 );
 480
 481                 key = 174;
 482                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 483                 CPPUNIT_ASSERT( f.m_found.nKey == 174 );
 484                 CPPUNIT_ASSERT( f.m_found.nVal == 471 );
 485
 486                 key = 190;
 487                 CPPUNIT_ASSERT( s.find( key, boost::ref(f) ) );
 488                 CPPUNIT_ASSERT( f.m_found.nKey == 190 );
 489                 CPPUNIT_ASSERT( f.m_found.nVal == 91 );
 490             }
 491
 492             s.clear();
 493             CPPUNIT_ASSERT( s.empty() );
 494             CPPUNIT_ASSERT( check_size( s, 0 ));
 495 #       endif
 496         }
 497
 498         template <class Set, class Predicate>
 499         void test_int()
 500         {
 501             Set s( 32, 4, 3 );
 502             CPPUNIT_ASSERT( s.bucket_count() == 32 );
 503             CPPUNIT_ASSERT( s.lock_count() == 32 );
 504
 505             cds::OS::Timer    timer;
 506
 507             test_int_with( s, Predicate() );
 508
 509             // Resizing test
 510             for ( int i = 0; i < 10000; i++ ) {
 511                 s.insert( i );
 512             }
 513
 514             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 515         }
 516
 517     public:
 518         void Cuckoo_Striped_list_unord();
 519         void Cuckoo_Striped_list_unord_storehash();
 520         void Cuckoo_Striped_list_cmp();
 521         void Cuckoo_Striped_list_cmp_storehash();
 522         void Cuckoo_Striped_list_less();
 523         void Cuckoo_Striped_list_less_storehash();
 524         void Cuckoo_Striped_list_less_cmp();
 525         void Cuckoo_Striped_list_less_cmp_storehash();
 526         void Cuckoo_Striped_list_less_cmp_eq();
 527         void Cuckoo_Striped_list_less_cmp_eq_storehash();
 528
 529         void Cuckoo_Striped_vector_unord();
 530         void Cuckoo_Striped_vector_unord_storehash();
 531         void Cuckoo_Striped_vector_cmp();
 532         void Cuckoo_Striped_vector_cmp_storehash();
 533         void Cuckoo_Striped_vector_less();
 534         void Cuckoo_Striped_vector_less_storehash();
 535         void Cuckoo_Striped_vector_less_cmp();
 536         void Cuckoo_Striped_vector_less_cmp_storehash();
 537         void Cuckoo_Striped_vector_less_cmp_eq();
 538         void Cuckoo_Striped_vector_less_cmp_eq_storehash();
 539
 540         void Cuckoo_Refinable_list_unord();
 541         void Cuckoo_Refinable_list_unord_storehash();
 542         void Cuckoo_Refinable_list_cmp();
 543         void Cuckoo_Refinable_list_cmp_storehash();
 544         void Cuckoo_Refinable_list_less();
 545         void Cuckoo_Refinable_list_less_storehash();
 546         void Cuckoo_Refinable_list_less_cmp();
 547         void Cuckoo_Refinable_list_less_cmp_storehash();
 548         void Cuckoo_Refinable_list_less_cmp_eq();
 549         void Cuckoo_Refinable_list_less_cmp_eq_storehash();
 550
 551         void Cuckoo_Refinable_vector_unord();
 552         void Cuckoo_Refinable_vector_unord_storehash();
 553         void Cuckoo_Refinable_vector_cmp();
 554         void Cuckoo_Refinable_vector_cmp_storehash();
 555         void Cuckoo_Refinable_vector_less();
 556         void Cuckoo_Refinable_vector_less_storehash();
 557         void Cuckoo_Refinable_vector_less_cmp();
 558         void Cuckoo_Refinable_vector_less_cmp_storehash();
 559         void Cuckoo_Refinable_vector_less_cmp_eq();
 560         void Cuckoo_Refinable_vector_less_cmp_eq_storehash();
 561
 562         CPPUNIT_TEST_SUITE(CuckooSetHdrTest)
 563             CPPUNIT_TEST( Cuckoo_Striped_list_unord)
 564             CPPUNIT_TEST( Cuckoo_Striped_list_unord_storehash)
 565             CPPUNIT_TEST( Cuckoo_Striped_list_cmp)
 566             CPPUNIT_TEST( Cuckoo_Striped_list_cmp_storehash)
 567             CPPUNIT_TEST( Cuckoo_Striped_list_less)
 568             CPPUNIT_TEST( Cuckoo_Striped_list_less_storehash)
 569             CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp)
 570             CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp_storehash)
 571             CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp_eq)
 572             CPPUNIT_TEST( Cuckoo_Striped_list_less_cmp_eq_storehash)
 573
 574             CPPUNIT_TEST( Cuckoo_Striped_vector_unord)
 575             CPPUNIT_TEST( Cuckoo_Striped_vector_unord_storehash)
 576             CPPUNIT_TEST( Cuckoo_Striped_vector_cmp)
 577             CPPUNIT_TEST( Cuckoo_Striped_vector_cmp_storehash)
 578             CPPUNIT_TEST( Cuckoo_Striped_vector_less)
 579             CPPUNIT_TEST( Cuckoo_Striped_vector_less_storehash)
 580             CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp)
 581             CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp_storehash)
 582             CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp_eq)
 583             CPPUNIT_TEST( Cuckoo_Striped_vector_less_cmp_eq_storehash)
 584
 585             CPPUNIT_TEST( Cuckoo_Refinable_list_unord)
 586             CPPUNIT_TEST( Cuckoo_Refinable_list_unord_storehash)
 587             CPPUNIT_TEST( Cuckoo_Refinable_list_cmp)
 588             CPPUNIT_TEST( Cuckoo_Refinable_list_cmp_storehash)
 589             CPPUNIT_TEST( Cuckoo_Refinable_list_less)
 590             CPPUNIT_TEST( Cuckoo_Refinable_list_less_storehash)
 591             CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp)
 592             CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp_storehash)
 593             CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp_eq)
 594             CPPUNIT_TEST( Cuckoo_Refinable_list_less_cmp_eq_storehash)
 595
 596             CPPUNIT_TEST( Cuckoo_Refinable_vector_unord)
 597             CPPUNIT_TEST( Cuckoo_Refinable_vector_unord_storehash)
 598             CPPUNIT_TEST( Cuckoo_Refinable_vector_cmp)
 599             CPPUNIT_TEST( Cuckoo_Refinable_vector_cmp_storehash)
 600             CPPUNIT_TEST( Cuckoo_Refinable_vector_less)
 601             CPPUNIT_TEST( Cuckoo_Refinable_vector_less_storehash)
 602             CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp)
 603             CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp_storehash)
 604             CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp_eq)
 605             CPPUNIT_TEST( Cuckoo_Refinable_vector_less_cmp_eq_storehash)
 606         CPPUNIT_TEST_SUITE_END()
 607     };
 608
 609 } // namespace set
 610
 611 #endif // #ifndef __CDSTEST_HDR_CUCKOO_SET_H