tests/test-hdr/set/hdr_feldman_hashset.h

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