tests/test-hdr/set/hdr_feldman_hashset.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_FELDMAN_HASHSET_H
   4 #define CDSTEST_HDR_FELDMAN_HASHSET_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7
   8 // forward declaration
   9 namespace cds {
  10     namespace container {}
  11     namespace opt {}
  12 }
  13
  14 namespace set {
  15     namespace cc = cds::container;
  16     namespace co = cds::opt;
  17
  18     class FeldmanHashSetHdrTest : public CppUnitMini::TestCase
  19     {
  20         template <typename Hash>
  21         struct Arg
  22         {
  23             size_t key;
  24             Hash hash;
  25
  26             Arg( size_t k, Hash const& h )
  27                 : key( k )
  28                 , hash( h )
  29             {}
  30         };
  31
  32         template <typename Hash>
  33         struct Item
  34         {
  35             unsigned int nInsertCall;
  36             unsigned int nFindCall;
  37             unsigned int nEraseCall;
  38             mutable unsigned int nIteratorCall;
  39             Hash hash;
  40             size_t key;
  41
  42             Item( size_t k, Hash const& h )
  43                 : nInsertCall(0)
  44                 , nFindCall(0)
  45                 , nEraseCall(0)
  46                 , nIteratorCall(0)
  47                 , hash( h )
  48                 , key( k )
  49             {}
  50
  51             explicit Item( Arg<Hash> const& arg )
  52                 : nInsertCall(0)
  53                 , nFindCall(0)
  54                 , nEraseCall(0)
  55                 , nIteratorCall(0)
  56                 , hash( arg.hash )
  57                 , key( arg.key )
  58             {}
  59
  60             Item( Item const& i )
  61                 : nInsertCall(0)
  62                 , nFindCall(0)
  63                 , nEraseCall(0)
  64                 , nIteratorCall(0)
  65                 , hash( i.hash )
  66                 , key( i.key )
  67             {}
  68         };
  69
  70         template <typename Hash>
  71         struct get_hash
  72         {
  73             Hash const& operator()( Item<Hash> const& i ) const
  74             {
  75                 return i.hash;
  76             }
  77         };
  78
  79         template <typename Key>
  80         struct get_key
  81         {
  82             Key operator()(Item<Key> const& i)const
  83             {
  84                 return i.hash;
  85             }
  86         };
  87
  88         template <typename Key>
  89         struct nohash {
  90             Key operator()(Key k) const
  91             {
  92                 return k;
  93             }
  94         };
  95
  96         struct hash128
  97         {
  98             size_t lo;
  99             size_t hi;
 100
 101             hash128() {}
 102             hash128(size_t l, size_t h) : lo(l), hi(h) {}
 103             hash128( hash128 const& h) : lo(h.lo), hi(h.hi) {}
 104
 105             struct make {
 106                 hash128 operator()( size_t n ) const
 107                 {
 108                     return hash128( std::hash<size_t>()( n ), std::hash<size_t>()( ~n ));
 109                 }
 110                 hash128 operator()( hash128 const& n ) const
 111                 {
 112                     return hash128( std::hash<size_t>()( n.lo ), std::hash<size_t>()( ~n.hi ));
 113                 }
 114             };
 115
 116             struct less {
 117                 bool operator()( hash128 const& lhs, hash128 const& rhs ) const
 118                 {
 119                     if ( lhs.hi != rhs.hi )
 120                         return lhs.hi < rhs.hi;
 121                     return lhs.lo < rhs.lo;
 122                 }
 123             };
 124
 125             struct cmp {
 126                 int operator()( hash128 const& lhs, hash128 const& rhs ) const
 127                 {
 128                     if ( lhs.hi != rhs.hi )
 129                         return lhs.hi < rhs.hi ? -1 : 1;
 130                     return lhs.lo < rhs.lo ? -1 : lhs.lo == rhs.lo ? 0 : 1;
 131                 }
 132             };
 133
 134             friend bool operator==( hash128 const& lhs, hash128 const& rhs )
 135             {
 136                 return cmp()( lhs, rhs ) == 0;
 137             }
 138             friend bool operator!=(hash128 const& lhs, hash128 const& rhs)
 139             {
 140                 return !( lhs == rhs );
 141             }
 142         };
 143
 144         template <typename Set, typename Hasher>
 145         void test_hp( size_t nHeadBits, size_t nArrayBits )
 146         {
 147             typedef typename Set::hash_type hash_type;
 148             typedef typename Set::value_type value_type;
 149             typedef Arg<hash_type> arg_type;
 150             typedef typename Set::guarded_ptr guarded_ptr;
 151
 152             Hasher hasher;
 153
 154             size_t const capacity = 1000;
 155
 156             Set s( nHeadBits, nArrayBits );
 157             CPPUNIT_MSG("Array size: head=" << s.head_size() << ", array_node=" << s.array_node_size());
 158             CPPUNIT_ASSERT(s.head_size() >= (size_t(1) << nHeadBits));
 159             CPPUNIT_ASSERT(s.array_node_size() == (size_t(1) << nArrayBits));
 160
 161             CPPUNIT_ASSERT( s.empty() );
 162             CPPUNIT_ASSERT(s.size() == 0);
 163
 164             // insert test
 165             for ( size_t i = 0; i < capacity; ++i ) {
 166                 hash_type h = hasher(i);
 167                 CPPUNIT_ASSERT( !s.contains( h ));
 168                 CPPUNIT_ASSERT( s.insert( value_type( i, h )));
 169                 CPPUNIT_ASSERT(s.contains( h ));
 170
 171                 CPPUNIT_ASSERT( !s.empty() );
 172                 CPPUNIT_ASSERT( s.size() == i + 1);
 173
 174                 CPPUNIT_ASSERT( !s.insert( arg_type(i, h) ));
 175                 CPPUNIT_ASSERT( s.size() == i + 1);
 176             }
 177
 178             // update existing test
 179             for ( size_t i = 0; i < capacity; ++i ) {
 180                 hash_type h = hasher(i);
 181                 CPPUNIT_ASSERT( s.contains( h ));
 182                 std::pair<bool, bool> ret = s.update( arg_type( i, h ),
 183                     [](value_type& i, value_type * prev ) {
 184                         CPPUNIT_ASSERT_CURRENT( prev != nullptr );
 185                         CPPUNIT_ASSERT_CURRENT( i.key == prev->key );
 186                         CPPUNIT_ASSERT_CURRENT( i.hash == prev->hash );
 187                         i.nInsertCall += 1;
 188                     }, false );
 189                 CPPUNIT_ASSERT( ret.first );
 190                 CPPUNIT_ASSERT( !ret.second );
 191                 CPPUNIT_ASSERT( s.contains( h ));
 192                 CPPUNIT_ASSERT( s.size() == capacity );
 193
 194                 guarded_ptr gp(s.get( h ));
 195                 CPPUNIT_ASSERT( gp );
 196                 CPPUNIT_ASSERT( gp->nInsertCall == 1 );
 197                 CPPUNIT_ASSERT( gp->key == i );
 198                 CPPUNIT_ASSERT( gp->hash == h );
 199             }
 200
 201             // erase test
 202             for ( size_t i = 0; i < capacity; ++i ) {
 203                 CPPUNIT_ASSERT( !s.empty() );
 204                 CPPUNIT_ASSERT( s.size() == capacity - i );
 205                 CPPUNIT_ASSERT(s.find(hasher(i), []( value_type &) {}));
 206                 CPPUNIT_ASSERT( s.erase(hasher(i)) );
 207                 CPPUNIT_ASSERT( !s.find(hasher(i), []( value_type &) {}));
 208                 CPPUNIT_ASSERT( s.size() == capacity - i - 1);
 209             }
 210             CPPUNIT_ASSERT( s.empty() );
 211
 212             // Iterators on empty set
 213             CPPUNIT_ASSERT(s.begin() == s.end());
 214             CPPUNIT_ASSERT(s.cbegin() == s.cend());
 215             CPPUNIT_ASSERT(s.rbegin() == s.rend());
 216             CPPUNIT_ASSERT(s.crbegin() == s.crend());
 217
 218             // insert with functor
 219             for ( size_t i = capacity; i > 0; --i ) {
 220                 CPPUNIT_ASSERT( s.size() == capacity - i );
 221                 CPPUNIT_ASSERT(s.insert( arg_type( i, hasher(i)), []( value_type& val ) { val.nInsertCall += 1; } ));
 222                 CPPUNIT_ASSERT( s.size() == capacity - i + 1 );
 223                 CPPUNIT_ASSERT( !s.empty() );
 224
 225                 CPPUNIT_ASSERT(s.find( hasher(i), []( value_type& val ) {
 226                     CPPUNIT_ASSERT_CURRENT( val.nInsertCall == 1 );
 227                     val.nFindCall += 1;
 228                 } ));
 229             }
 230                 CPPUNIT_ASSERT( s.size() == capacity );
 231
 232             // for-each iterator test
 233             for ( auto& el : s ) {
 234                 CPPUNIT_ASSERT( el.nInsertCall == 1 );
 235                 CPPUNIT_ASSERT( el.nFindCall == 1 );
 236                 el.nFindCall += 1;
 237             }
 238
 239             // iterator test
 240             for ( auto it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 241                 CPPUNIT_ASSERT( it->nInsertCall == 1 );
 242                 CPPUNIT_ASSERT( it->nFindCall == 2 );
 243                 it->nFindCall += 1;
 244             }
 245
 246             // reverse iterator test
 247             for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) {
 248                 CPPUNIT_ASSERT( it->nInsertCall == 1 );
 249                 CPPUNIT_ASSERT( it->nFindCall == 3 );
 250                 it->nFindCall += 1;
 251             }
 252
 253             // const iterator test
 254             for ( auto it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it ) {
 255                 CPPUNIT_ASSERT( it->nInsertCall == 1 );
 256                 CPPUNIT_ASSERT( it->nFindCall == 4 );
 257                 it->nIteratorCall += 1;
 258             }
 259
 260             // const reverse iterator test
 261             for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) {
 262                 CPPUNIT_ASSERT( it->nInsertCall == 1 );
 263                 CPPUNIT_ASSERT( it->nFindCall == 4 );
 264                 CPPUNIT_ASSERT( it->nIteratorCall == 1 );
 265                 it->nIteratorCall += 1;
 266             }
 267
 268             // check completeness
 269             for ( size_t i = 1; i <= capacity; ++i ) {
 270                 CPPUNIT_ASSERT( s.find( hasher( i ), []( value_type const& el ) {
 271                     CPPUNIT_ASSERT_CURRENT( el.nInsertCall == 1 );
 272                     CPPUNIT_ASSERT_CURRENT( el.nFindCall == 4 );
 273                     CPPUNIT_ASSERT_CURRENT( el.nIteratorCall == 2 );
 274                 } ));
 275             }
 276
 277             // erase with functor test
 278             {
 279                 size_t nSum = 0;
 280                 for ( size_t i = 1; i <= capacity; ++i ) {
 281                     CPPUNIT_ASSERT( s.size() == capacity - i + 1 );
 282                     CPPUNIT_ASSERT(s.erase(hasher(i), [&nSum]( value_type const& val ) {
 283                         CPPUNIT_ASSERT_CURRENT( val.nInsertCall == 1 );
 284                         CPPUNIT_ASSERT_CURRENT( val.nFindCall == 4 );
 285                         CPPUNIT_ASSERT_CURRENT( val.nIteratorCall == 2 );
 286                         nSum += val.key;
 287                     } ))
 288                     CPPUNIT_ASSERT( s.size() == capacity - i );
 289                     CPPUNIT_ASSERT( !s.erase(hasher(i), [&nSum]( value_type const& val ) { nSum += val.key; } ))
 290                 }
 291                 CPPUNIT_ASSERT(s.empty() );
 292                 CPPUNIT_ASSERT(nSum == (1 + capacity) * capacity / 2 );
 293             }
 294
 295             // update test with insert allowing
 296             for ( size_t i = 0; i < capacity; ++i ) {
 297                 hash_type h = hasher(i);
 298                 CPPUNIT_ASSERT( !s.contains( h ));
 299                 guarded_ptr gp(s.get( h ));
 300                 CPPUNIT_ASSERT( !gp );
 301                 std::pair<bool, bool> ret = s.update( arg_type( i, h ),
 302                     [](value_type& i, value_type * prev ) {
 303                         CPPUNIT_ASSERT_CURRENT( prev == nullptr );
 304                         i.nInsertCall += 1;
 305                     });
 306                 CPPUNIT_ASSERT( ret.first );
 307                 CPPUNIT_ASSERT( ret.second );
 308                 CPPUNIT_ASSERT( s.contains( h ));
 309                 CPPUNIT_ASSERT( s.size() == i + 1 );
 310
 311                 gp = s.get( h );
 312                 CPPUNIT_ASSERT( gp );
 313                 CPPUNIT_ASSERT( gp->nInsertCall == 1 );
 314                 CPPUNIT_ASSERT( gp->key == i );
 315                 CPPUNIT_ASSERT( gp->hash == h );
 316             }
 317             CPPUNIT_ASSERT( !s.empty() );
 318             CPPUNIT_ASSERT(s.size() == capacity );
 319
 320             // erase_at( iterator ) test
 321             for ( auto it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 322                 CPPUNIT_ASSERT( s.erase_at( it ));
 323             }
 324             CPPUNIT_ASSERT( s.empty() );
 325             CPPUNIT_ASSERT( s.size() == 0 );
 326
 327             // emplace test
 328             for ( size_t i = 0; i < capacity; ++i ) {
 329                 hash_type h = hasher(i);
 330                 CPPUNIT_ASSERT( !s.contains( h ));
 331                 CPPUNIT_ASSERT( s.emplace( i, hasher(i) ));
 332                 CPPUNIT_ASSERT(s.contains( h ));
 333
 334                 CPPUNIT_ASSERT( !s.empty() );
 335                 CPPUNIT_ASSERT( s.size() == i + 1);
 336
 337                 CPPUNIT_ASSERT( !s.emplace( arg_type(i, h) ));
 338                 CPPUNIT_ASSERT( s.size() == i + 1);
 339             }
 340             CPPUNIT_ASSERT( !s.empty() );
 341             CPPUNIT_ASSERT(s.size() == capacity );
 342
 343             // erase_at( reverse_iterator ) test
 344             for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) {
 345                 CPPUNIT_ASSERT( s.erase_at( it ));
 346             }
 347             CPPUNIT_ASSERT( s.empty() );
 348             CPPUNIT_ASSERT( s.size() == 0 );
 349
 350             // extract test
 351             for ( size_t i = 0; i < capacity; ++i ) {
 352                 hash_type h = hasher(i);
 353                 CPPUNIT_ASSERT( !s.contains( h ));
 354                 CPPUNIT_ASSERT( s.emplace( arg_type( i, hasher(i) )));
 355                 CPPUNIT_ASSERT(s.contains( h ));
 356
 357                 CPPUNIT_ASSERT( !s.empty() );
 358                 CPPUNIT_ASSERT( s.size() == i + 1);
 359
 360                 CPPUNIT_ASSERT( !s.emplace( i, h ));
 361                 CPPUNIT_ASSERT( s.size() == i + 1);
 362             }
 363             CPPUNIT_ASSERT( !s.empty() );
 364             CPPUNIT_ASSERT(s.size() == capacity );
 365
 366             for ( size_t i = capacity; i != 0; --i ) {
 367                 CPPUNIT_ASSERT( !s.empty() );
 368                 CPPUNIT_ASSERT( s.size() == i );
 369
 370                 guarded_ptr gp{ s.extract( hasher(i-1)) };
 371                 CPPUNIT_ASSERT( gp );
 372                 CPPUNIT_ASSERT( gp->key == i - 1);
 373                 CPPUNIT_ASSERT(gp->hash == hasher(i-1));
 374                 CPPUNIT_ASSERT( !s.contains(hasher(i-1)));
 375
 376                 gp = s.get(hasher(i-1));
 377                 CPPUNIT_ASSERT( !gp );
 378
 379                 CPPUNIT_ASSERT( s.size() == i - 1 );
 380             }
 381             CPPUNIT_ASSERT( s.empty() );
 382             CPPUNIT_ASSERT(s.size() == 0 );
 383
 384             // clear test
 385             for ( size_t i = 0; i < capacity; ++i ) {
 386                 hash_type h = hasher(i);
 387                 CPPUNIT_ASSERT( !s.contains( h ));
 388                 CPPUNIT_ASSERT( s.emplace( arg_type( i, hasher(i) )));
 389                 CPPUNIT_ASSERT(s.contains( h ));
 390
 391                 CPPUNIT_ASSERT( !s.empty() );
 392                 CPPUNIT_ASSERT( s.size() == i + 1);
 393
 394                 CPPUNIT_ASSERT( !s.emplace( i, h ));
 395                 CPPUNIT_ASSERT( s.size() == i + 1);
 396             }
 397             CPPUNIT_ASSERT( !s.empty() );
 398             CPPUNIT_ASSERT(s.size() == capacity );
 399
 400             s.clear();
 401             CPPUNIT_ASSERT( s.empty() );
 402             CPPUNIT_ASSERT(s.size() == 0 );
 403
 404             CPPUNIT_MSG( s.statistics() );
 405         }
 406
 407         template <typename Set, typename Hasher>
 408         void test_rcu(size_t nHeadBits, size_t nArrayBits)
 409         {
 410             typedef typename Set::hash_type hash_type;
 411             typedef typename Set::value_type value_type;
 412             typedef Arg<hash_type> arg_type;
 413             typedef typename Set::exempt_ptr exempt_ptr;
 414             typedef typename Set::rcu_lock rcu_lock;
 415
 416             Hasher hasher;
 417
 418             size_t const capacity = 1000;
 419
 420             Set s(nHeadBits, nArrayBits);
 421             CPPUNIT_MSG("Array size: head=" << s.head_size() << ", array_node=" << s.array_node_size());
 422             CPPUNIT_ASSERT(s.head_size() >= (size_t(1) << nHeadBits));
 423             CPPUNIT_ASSERT(s.array_node_size() == (size_t(1) << nArrayBits));
 424
 425             CPPUNIT_ASSERT(s.empty());
 426             CPPUNIT_ASSERT(s.size() == 0);
 427
 428             // insert test
 429             for (size_t i = 0; i < capacity; ++i) {
 430                 hash_type h = hasher(i);
 431                 CPPUNIT_ASSERT(!s.contains(h));
 432                 CPPUNIT_ASSERT(s.insert(value_type(i, h)));
 433                 CPPUNIT_ASSERT(s.contains(h));
 434
 435                 CPPUNIT_ASSERT(!s.empty());
 436                 CPPUNIT_ASSERT(s.size() == i + 1);
 437
 438                 CPPUNIT_ASSERT(!s.insert(arg_type(i, h)));
 439                 CPPUNIT_ASSERT(s.size() == i + 1);
 440             }
 441
 442             // update existing test
 443             for (size_t i = 0; i < capacity; ++i) {
 444                 hash_type h = hasher(i);
 445                 CPPUNIT_ASSERT(s.contains(h));
 446                 std::pair<bool, bool> ret = s.update(arg_type(i, h),
 447                     [](value_type& i, value_type * prev) {
 448                     CPPUNIT_ASSERT_CURRENT(prev != nullptr);
 449                     CPPUNIT_ASSERT_CURRENT(i.key == prev->key);
 450                     CPPUNIT_ASSERT_CURRENT(i.hash == prev->hash);
 451                     i.nInsertCall += 1;
 452                 }, false);
 453                 CPPUNIT_ASSERT(ret.first);
 454                 CPPUNIT_ASSERT(!ret.second);
 455                 CPPUNIT_ASSERT(s.contains(h));
 456                 CPPUNIT_ASSERT(s.size() == capacity);
 457
 458                 {
 459                     rcu_lock l;
 460                     value_type * p = s.get(h);
 461                     CPPUNIT_ASSERT(p);
 462                     CPPUNIT_ASSERT(p->nInsertCall == 1);
 463                     CPPUNIT_ASSERT(p->key == i);
 464                     CPPUNIT_ASSERT(p->hash == h);
 465                 }
 466             }
 467
 468             // erase test
 469             for (size_t i = 0; i < capacity; ++i) {
 470                 CPPUNIT_ASSERT(!s.empty());
 471                 CPPUNIT_ASSERT(s.size() == capacity - i);
 472                 CPPUNIT_ASSERT(s.find(hasher(i), [](value_type &) {}));
 473                 CPPUNIT_ASSERT(s.erase(hasher(i)));
 474                 CPPUNIT_ASSERT(!s.find(hasher(i), [](value_type &) {}));
 475                 CPPUNIT_ASSERT(s.size() == capacity - i - 1);
 476             }
 477             CPPUNIT_ASSERT(s.empty());
 478
 479             // Iterators on empty set
 480             {
 481                 rcu_lock l;
 482                 CPPUNIT_ASSERT(s.begin() == s.end());
 483                 CPPUNIT_ASSERT(s.cbegin() == s.cend());
 484                 CPPUNIT_ASSERT(s.rbegin() == s.rend());
 485                 CPPUNIT_ASSERT(s.crbegin() == s.crend());
 486             }
 487
 488             // insert with functor
 489             for (size_t i = capacity; i > 0; --i) {
 490                 CPPUNIT_ASSERT(s.size() == capacity - i);
 491                 CPPUNIT_ASSERT(s.insert(arg_type(i, hasher(i)), [](value_type& val) { val.nInsertCall += 1; }));
 492                 CPPUNIT_ASSERT(s.size() == capacity - i + 1);
 493                 CPPUNIT_ASSERT(!s.empty());
 494
 495                 CPPUNIT_ASSERT(s.find(hasher(i), [](value_type& val) {
 496                     CPPUNIT_ASSERT_CURRENT(val.nInsertCall == 1);
 497                     val.nFindCall += 1;
 498                 }));
 499             }
 500             CPPUNIT_ASSERT(s.size() == capacity);
 501
 502             // for-each iterator test
 503             {
 504                 rcu_lock l;
 505                 for (auto& el : s) {
 506                     CPPUNIT_ASSERT(el.nInsertCall == 1);
 507                     CPPUNIT_ASSERT(el.nFindCall == 1);
 508                     el.nFindCall += 1;
 509                 }
 510             }
 511
 512             // iterator test
 513             {
 514                 rcu_lock l;
 515                 for (auto it = s.begin(), itEnd = s.end(); it != itEnd; ++it) {
 516                     CPPUNIT_ASSERT(it->nInsertCall == 1);
 517                     CPPUNIT_ASSERT(it->nFindCall == 2);
 518                     it->nFindCall += 1;
 519                 }
 520             }
 521
 522             // reverse iterator test
 523             {
 524                 rcu_lock l;
 525                 for (auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it) {
 526                     CPPUNIT_ASSERT(it->nInsertCall == 1);
 527                     CPPUNIT_ASSERT(it->nFindCall == 3);
 528                     it->nFindCall += 1;
 529                 }
 530             }
 531
 532             // const iterator test
 533             {
 534                 rcu_lock l;
 535                 for (auto it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it) {
 536                     CPPUNIT_ASSERT(it->nInsertCall == 1);
 537                     CPPUNIT_ASSERT(it->nFindCall == 4);
 538                     it->nIteratorCall += 1;
 539                 }
 540             }
 541
 542             // const reverse iterator test
 543             {
 544                 rcu_lock l;
 545                 for (auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it) {
 546                     CPPUNIT_ASSERT(it->nInsertCall == 1);
 547                     CPPUNIT_ASSERT(it->nFindCall == 4);
 548                     CPPUNIT_ASSERT(it->nIteratorCall == 1);
 549                     it->nIteratorCall += 1;
 550                 }
 551             }
 552
 553             // check completeness
 554             for (size_t i = 1; i <= capacity; ++i) {
 555                 CPPUNIT_ASSERT(s.find(hasher(i), [](value_type const& el) {
 556                     CPPUNIT_ASSERT_CURRENT(el.nInsertCall == 1);
 557                     CPPUNIT_ASSERT_CURRENT(el.nFindCall == 4);
 558                     CPPUNIT_ASSERT_CURRENT(el.nIteratorCall == 2);
 559                 }));
 560             }
 561
 562             // erase with functor test
 563             {
 564                 size_t nSum = 0;
 565                 for (size_t i = 1; i <= capacity; ++i) {
 566                     CPPUNIT_ASSERT(s.size() == capacity - i + 1);
 567                     CPPUNIT_ASSERT(s.erase(hasher(i), [&nSum](value_type const& val) {
 568                         CPPUNIT_ASSERT_CURRENT(val.nInsertCall == 1);
 569                         CPPUNIT_ASSERT_CURRENT(val.nFindCall == 4);
 570                         CPPUNIT_ASSERT_CURRENT(val.nIteratorCall == 2);
 571                         nSum += val.key;
 572                     }));
 573                     CPPUNIT_ASSERT(s.size() == capacity - i);
 574                     CPPUNIT_ASSERT(!s.erase(hasher(i), [&nSum](value_type const& val) { nSum += val.key; }))
 575                 }
 576                 CPPUNIT_ASSERT(s.empty());
 577                 CPPUNIT_ASSERT(nSum == (1 + capacity) * capacity / 2);
 578             }
 579
 580             // update test with insert allowing
 581             for (size_t i = 0; i < capacity; ++i) {
 582                 hash_type h = hasher(i);
 583                 CPPUNIT_ASSERT(!s.contains(h));
 584
 585                 {
 586                     rcu_lock l;
 587                     value_type * p = s.get(h);
 588                     CPPUNIT_ASSERT(!p);
 589                 }
 590                 std::pair<bool, bool> ret = s.update(arg_type(i, h),
 591                     [](value_type& i, value_type * prev) {
 592                     CPPUNIT_ASSERT_CURRENT(prev == nullptr);
 593                     i.nInsertCall += 1;
 594                 });
 595                 CPPUNIT_ASSERT(ret.first);
 596                 CPPUNIT_ASSERT(ret.second);
 597                 CPPUNIT_ASSERT(s.contains(h));
 598                 CPPUNIT_ASSERT(s.size() == i + 1);
 599
 600                 {
 601                     rcu_lock l;
 602                     value_type * p = s.get(h);
 603                     CPPUNIT_ASSERT(p);
 604                     CPPUNIT_ASSERT(p->nInsertCall == 1);
 605                     CPPUNIT_ASSERT(p->key == i);
 606                     CPPUNIT_ASSERT(p->hash == h);
 607                 }
 608             }
 609             CPPUNIT_ASSERT(!s.empty());
 610             CPPUNIT_ASSERT(s.size() == capacity);
 611
 612             s.clear();
 613             CPPUNIT_ASSERT(s.empty());
 614             CPPUNIT_ASSERT(s.size() == 0);
 615
 616             // emplace test
 617             for (size_t i = 0; i < capacity; ++i) {
 618                 hash_type h = hasher(i);
 619                 CPPUNIT_ASSERT(!s.contains(h));
 620                 CPPUNIT_ASSERT(s.emplace(i, hasher(i)));
 621                 CPPUNIT_ASSERT(s.contains(h));
 622
 623                 CPPUNIT_ASSERT(!s.empty());
 624                 CPPUNIT_ASSERT(s.size() == i + 1);
 625
 626                 CPPUNIT_ASSERT(!s.emplace(arg_type(i, h)));
 627                 CPPUNIT_ASSERT(s.size() == i + 1);
 628             }
 629             CPPUNIT_ASSERT(!s.empty());
 630             CPPUNIT_ASSERT(s.size() == capacity);
 631
 632             // extract test
 633             for (size_t i = capacity; i != 0; --i) {
 634                 CPPUNIT_ASSERT(!s.empty());
 635                 CPPUNIT_ASSERT(s.size() == i);
 636
 637                 exempt_ptr gp{ s.extract(hasher(i - 1)) };
 638                 CPPUNIT_ASSERT(gp);
 639                 CPPUNIT_ASSERT(gp->key == i - 1);
 640                 CPPUNIT_ASSERT(gp->hash == hasher(i - 1));
 641                 CPPUNIT_ASSERT(!s.contains(hasher(i - 1)));
 642
 643                 {
 644                     rcu_lock l;
 645                     value_type * p = s.get(hasher(i - 1));
 646                     CPPUNIT_ASSERT( p == nullptr );
 647                 }
 648                 CPPUNIT_ASSERT(s.size() == i - 1);
 649             }
 650             CPPUNIT_ASSERT(s.empty());
 651             CPPUNIT_ASSERT(s.size() == 0);
 652
 653             CPPUNIT_MSG(s.statistics());
 654         }
 655
 656         void hp_nohash();
 657         void hp_nohash_stat();
 658         void hp_nohash_5_3();
 659         void hp_nohash_5_3_stat();
 660         void hp_stdhash();
 661         void hp_stdhash_stat();
 662         void hp_stdhash_5_3();
 663         void hp_stdhash_5_3_stat();
 664         void hp_hash128();
 665         void hp_hash128_stat();
 666         void hp_hash128_4_3();
 667         void hp_hash128_4_3_stat();
 668
 669         void dhp_nohash();
 670         void dhp_nohash_stat();
 671         void dhp_nohash_5_3();
 672         void dhp_nohash_5_3_stat();
 673         void dhp_stdhash();
 674         void dhp_stdhash_stat();
 675         void dhp_stdhash_5_3();
 676         void dhp_stdhash_5_3_stat();
 677         void dhp_hash128();
 678         void dhp_hash128_stat();
 679         void dhp_hash128_4_3();
 680         void dhp_hash128_4_3_stat();
 681
 682         void rcu_gpi_nohash();
 683         void rcu_gpi_nohash_stat();
 684         void rcu_gpi_nohash_5_3();
 685         void rcu_gpi_nohash_5_3_stat();
 686         void rcu_gpi_stdhash();
 687         void rcu_gpi_stdhash_stat();
 688         void rcu_gpi_stdhash_5_3();
 689         void rcu_gpi_stdhash_5_3_stat();
 690         void rcu_gpi_hash128();
 691         void rcu_gpi_hash128_stat();
 692         void rcu_gpi_hash128_4_3();
 693         void rcu_gpi_hash128_4_3_stat();
 694
 695         void rcu_gpb_nohash();
 696         void rcu_gpb_nohash_stat();
 697         void rcu_gpb_nohash_5_3();
 698         void rcu_gpb_nohash_5_3_stat();
 699         void rcu_gpb_stdhash();
 700         void rcu_gpb_stdhash_stat();
 701         void rcu_gpb_stdhash_5_3();
 702         void rcu_gpb_stdhash_5_3_stat();
 703         void rcu_gpb_hash128();
 704         void rcu_gpb_hash128_stat();
 705         void rcu_gpb_hash128_4_3();
 706         void rcu_gpb_hash128_4_3_stat();
 707
 708         void rcu_gpt_nohash();
 709         void rcu_gpt_nohash_stat();
 710         void rcu_gpt_nohash_5_3();
 711         void rcu_gpt_nohash_5_3_stat();
 712         void rcu_gpt_stdhash();
 713         void rcu_gpt_stdhash_stat();
 714         void rcu_gpt_stdhash_5_3();
 715         void rcu_gpt_stdhash_5_3_stat();
 716         void rcu_gpt_hash128();
 717         void rcu_gpt_hash128_stat();
 718         void rcu_gpt_hash128_4_3();
 719         void rcu_gpt_hash128_4_3_stat();
 720
 721         void rcu_shb_nohash();
 722         void rcu_shb_nohash_stat();
 723         void rcu_shb_nohash_5_3();
 724         void rcu_shb_nohash_5_3_stat();
 725         void rcu_shb_stdhash();
 726         void rcu_shb_stdhash_stat();
 727         void rcu_shb_stdhash_5_3();
 728         void rcu_shb_stdhash_5_3_stat();
 729         void rcu_shb_hash128();
 730         void rcu_shb_hash128_stat();
 731         void rcu_shb_hash128_4_3();
 732         void rcu_shb_hash128_4_3_stat();
 733
 734         void rcu_sht_nohash();
 735         void rcu_sht_nohash_stat();
 736         void rcu_sht_nohash_5_3();
 737         void rcu_sht_nohash_5_3_stat();
 738         void rcu_sht_stdhash();
 739         void rcu_sht_stdhash_stat();
 740         void rcu_sht_stdhash_5_3();
 741         void rcu_sht_stdhash_5_3_stat();
 742         void rcu_sht_hash128();
 743         void rcu_sht_hash128_stat();
 744         void rcu_sht_hash128_4_3();
 745         void rcu_sht_hash128_4_3_stat();
 746
 747         CPPUNIT_TEST_SUITE(FeldmanHashSetHdrTest)
 748             CPPUNIT_TEST(hp_nohash)
 749             CPPUNIT_TEST(hp_nohash_stat)
 750             CPPUNIT_TEST(hp_nohash_5_3)
 751             CPPUNIT_TEST(hp_nohash_5_3_stat)
 752             CPPUNIT_TEST(hp_stdhash)
 753             CPPUNIT_TEST(hp_stdhash_stat)
 754             CPPUNIT_TEST(hp_stdhash_5_3)
 755             CPPUNIT_TEST(hp_stdhash_5_3_stat)
 756             CPPUNIT_TEST(hp_hash128)
 757             CPPUNIT_TEST(hp_hash128_stat)
 758             CPPUNIT_TEST(hp_hash128_4_3)
 759             CPPUNIT_TEST(hp_hash128_4_3_stat)
 760
 761             CPPUNIT_TEST(dhp_nohash)
 762             CPPUNIT_TEST(dhp_nohash_stat)
 763             CPPUNIT_TEST(dhp_nohash_5_3)
 764             CPPUNIT_TEST(dhp_nohash_5_3_stat)
 765             CPPUNIT_TEST(dhp_stdhash)
 766             CPPUNIT_TEST(dhp_stdhash_stat)
 767             CPPUNIT_TEST(dhp_stdhash_5_3)
 768             CPPUNIT_TEST(dhp_stdhash_5_3_stat)
 769             CPPUNIT_TEST(dhp_hash128)
 770             CPPUNIT_TEST(dhp_hash128_stat)
 771             CPPUNIT_TEST(dhp_hash128_4_3)
 772             CPPUNIT_TEST(dhp_hash128_4_3_stat)
 773
 774             CPPUNIT_TEST(rcu_gpi_nohash)
 775             CPPUNIT_TEST(rcu_gpi_nohash_stat)
 776             CPPUNIT_TEST(rcu_gpi_nohash_5_3)
 777             CPPUNIT_TEST(rcu_gpi_nohash_5_3_stat)
 778             CPPUNIT_TEST(rcu_gpi_stdhash)
 779             CPPUNIT_TEST(rcu_gpi_stdhash_stat)
 780             CPPUNIT_TEST(rcu_gpi_stdhash_5_3)
 781             CPPUNIT_TEST(rcu_gpi_stdhash_5_3_stat)
 782             CPPUNIT_TEST(rcu_gpi_hash128)
 783             CPPUNIT_TEST(rcu_gpi_hash128_stat)
 784             CPPUNIT_TEST(rcu_gpi_hash128_4_3)
 785             CPPUNIT_TEST(rcu_gpi_hash128_4_3_stat)
 786
 787             CPPUNIT_TEST(rcu_gpb_nohash)
 788             CPPUNIT_TEST(rcu_gpb_nohash_stat)
 789             CPPUNIT_TEST(rcu_gpb_nohash_5_3)
 790             CPPUNIT_TEST(rcu_gpb_nohash_5_3_stat)
 791             CPPUNIT_TEST(rcu_gpb_stdhash)
 792             CPPUNIT_TEST(rcu_gpb_stdhash_stat)
 793             CPPUNIT_TEST(rcu_gpb_stdhash_5_3)
 794             CPPUNIT_TEST(rcu_gpb_stdhash_5_3_stat)
 795             CPPUNIT_TEST(rcu_gpb_hash128)
 796             CPPUNIT_TEST(rcu_gpb_hash128_stat)
 797             CPPUNIT_TEST(rcu_gpb_hash128_4_3)
 798             CPPUNIT_TEST(rcu_gpb_hash128_4_3_stat)
 799
 800             CPPUNIT_TEST(rcu_gpt_nohash)
 801             CPPUNIT_TEST(rcu_gpt_nohash_stat)
 802             CPPUNIT_TEST(rcu_gpt_nohash_5_3)
 803             CPPUNIT_TEST(rcu_gpt_nohash_5_3_stat)
 804             CPPUNIT_TEST(rcu_gpt_stdhash)
 805             CPPUNIT_TEST(rcu_gpt_stdhash_stat)
 806             CPPUNIT_TEST(rcu_gpt_stdhash_5_3)
 807             CPPUNIT_TEST(rcu_gpt_stdhash_5_3_stat)
 808             CPPUNIT_TEST(rcu_gpt_hash128)
 809             CPPUNIT_TEST(rcu_gpt_hash128_stat)
 810             CPPUNIT_TEST(rcu_gpt_hash128_4_3)
 811             CPPUNIT_TEST(rcu_gpt_hash128_4_3_stat)
 812
 813             CPPUNIT_TEST(rcu_shb_nohash)
 814             CPPUNIT_TEST(rcu_shb_nohash_stat)
 815             CPPUNIT_TEST(rcu_shb_nohash_5_3)
 816             CPPUNIT_TEST(rcu_shb_nohash_5_3_stat)
 817             CPPUNIT_TEST(rcu_shb_stdhash)
 818             CPPUNIT_TEST(rcu_shb_stdhash_stat)
 819             CPPUNIT_TEST(rcu_shb_stdhash_5_3)
 820             CPPUNIT_TEST(rcu_shb_stdhash_5_3_stat)
 821             CPPUNIT_TEST(rcu_shb_hash128)
 822             CPPUNIT_TEST(rcu_shb_hash128_stat)
 823             CPPUNIT_TEST(rcu_shb_hash128_4_3)
 824             CPPUNIT_TEST(rcu_shb_hash128_4_3_stat)
 825
 826             CPPUNIT_TEST(rcu_sht_nohash)
 827             CPPUNIT_TEST(rcu_sht_nohash_stat)
 828             CPPUNIT_TEST(rcu_sht_nohash_5_3)
 829             CPPUNIT_TEST(rcu_sht_nohash_5_3_stat)
 830             CPPUNIT_TEST(rcu_sht_stdhash)
 831             CPPUNIT_TEST(rcu_sht_stdhash_stat)
 832             CPPUNIT_TEST(rcu_sht_stdhash_5_3)
 833             CPPUNIT_TEST(rcu_sht_stdhash_5_3_stat)
 834             CPPUNIT_TEST(rcu_sht_hash128)
 835             CPPUNIT_TEST(rcu_sht_hash128_stat)
 836             CPPUNIT_TEST(rcu_sht_hash128_4_3)
 837             CPPUNIT_TEST(rcu_sht_hash128_4_3_stat)
 838         CPPUNIT_TEST_SUITE_END()
 839     };
 840
 841 } // namespace set
 842
 843 #endif // #ifndef CDSTEST_HDR_FELDMAN_HASHSET_H