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