tests/test-hdr/map/hdr_feldman_hashmap.h

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