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