tests/test-hdr/set/hdr_multilevel_hashset.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSTEST_HDR_MULTILEVEL_HASHSET_H
   4 #define CDSTEST_HDR_MULTILEVEL_HASHSET_H
   5
   6 #include "cppunit/cppunit_proxy.h"
   7
   8 // forward declaration
   9 namespace cds {
  10     namespace container {}
  11     namespace opt {}
  12 }
  13
  14 namespace set {
  15     namespace cc = cds::container;
  16     namespace co = cds::opt;
  17
  18     class MultiLevelHashSetHdrTest : public CppUnitMini::TestCase
  19     {
  20         template <typename Hash>
  21         struct Arg
  22         {
  23             size_t key;
  24             Hash hash;
  25
  26             Arg( size_t k, Hash const& h )
  27                 : key( k )
  28                 , hash( h )
  29             {}
  30         };
  31
  32         template <typename Hash>
  33         struct Item
  34         {
  35             unsigned int nInsertCall;
  36             unsigned int nFindCall;
  37             unsigned int nEraseCall;
  38             mutable unsigned int nIteratorCall;
  39             Hash hash;
  40             size_t key;
  41
  42             Item( size_t k, Hash const& h )
  43                 : nInsertCall(0)
  44                 , nFindCall(0)
  45                 , nEraseCall(0)
  46                 , nIteratorCall(0)
  47                 , hash( h )
  48                 , key( k )
  49             {}
  50
  51             explicit Item( Arg<Hash> const& arg )
  52                 : nInsertCall(0)
  53                 , nFindCall(0)
  54                 , nEraseCall(0)
  55                 , nIteratorCall(0)
  56                 , hash( arg.hash )
  57                 , key( arg.key )
  58             {}
  59
  60             Item( Item const& i )
  61                 : nInsertCall(0)
  62                 , nFindCall(0)
  63                 , nEraseCall(0)
  64                 , nIteratorCall(0)
  65                 , hash( i.hash )
  66                 , key( i.key )
  67             {}
  68         };
  69
  70         template <typename Hash>
  71         struct get_hash
  72         {
  73             Hash const& operator()( Item<Hash> const& i ) const
  74             {
  75                 return i.hash;
  76             }
  77         };
  78
  79         struct hash128
  80         {
  81             size_t lo;
  82             size_t hi;
  83
  84             hash128() {}
  85             hash128(size_t l, size_t h) : lo(l), hi(h) {}
  86             hash128( hash128 const& h) : lo(h.lo), hi(h.hi) {}
  87
  88             struct make {
  89                 hash128 operator()( size_t n ) const
  90                 {
  91                     return hash128( std::hash<size_t>()( n ), std::hash<size_t>()( ~n ));
  92                 }
  93                 hash128 operator()( hash128 const& n ) const
  94                 {
  95                     return hash128( std::hash<size_t>()( n.lo ), std::hash<size_t>()( ~n.hi ));
  96                 }
  97             };
  98
  99             struct less {
 100                 bool operator()( hash128 const& lhs, hash128 const& rhs ) const
 101                 {
 102                     if ( lhs.hi != rhs.hi )
 103                         return lhs.hi < rhs.hi;
 104                     return lhs.lo < rhs.lo;
 105                 }
 106             };
 107
 108             struct cmp {
 109                 int operator()( hash128 const& lhs, hash128 const& rhs ) const
 110                 {
 111                     if ( lhs.hi != rhs.hi )
 112                         return lhs.hi < rhs.hi ? -1 : 1;
 113                     return lhs.lo < rhs.lo ? -1 : lhs.lo == rhs.lo ? 0 : 1;
 114                 }
 115             };
 116
 117             friend bool operator==( hash128 const& lhs, hash128 const& rhs )
 118             {
 119                 return cmp()( lhs, rhs ) == 0;
 120             }
 121             friend bool operator!=(hash128 const& lhs, hash128 const& rhs)
 122             {
 123                 return !( lhs == rhs );
 124             }
 125         };
 126
 127         template <typename Set, typename Hasher>
 128         void test_hp( size_t nHeadBits, size_t nArrayBits )
 129         {
 130             typedef typename Set::hash_type hash_type;
 131             typedef typename Set::value_type value_type;
 132             typedef Arg<hash_type> arg_type;
 133             typedef typename Set::guarded_ptr guarded_ptr;
 134
 135             Hasher hasher;
 136
 137             size_t const capacity = 1000;
 138
 139             Set s( nHeadBits, nArrayBits );
 140             CPPUNIT_MSG("Array size: head=" << s.head_size() << ", array_node=" << s.array_node_size());
 141             CPPUNIT_ASSERT(s.head_size() >= (size_t(1) << nHeadBits));
 142             CPPUNIT_ASSERT(s.array_node_size() == (size_t(1) << nArrayBits));
 143
 144             CPPUNIT_ASSERT( s.empty() );
 145             CPPUNIT_ASSERT(s.size() == 0);
 146
 147             // insert test
 148             for ( size_t i = 0; i < capacity; ++i ) {
 149                 hash_type h = hasher(i);
 150                 CPPUNIT_ASSERT( !s.contains( h ));
 151                 CPPUNIT_ASSERT( s.insert( value_type( i, h )));
 152                 CPPUNIT_ASSERT(s.contains( h ));
 153
 154                 CPPUNIT_ASSERT( !s.empty() );
 155                 CPPUNIT_ASSERT( s.size() == i + 1);
 156
 157                 CPPUNIT_ASSERT( !s.insert( arg_type(i, h) ));
 158                 CPPUNIT_ASSERT( s.size() == i + 1);
 159             }
 160
 161             // update existing test
 162             for ( size_t i = 0; i < capacity; ++i ) {
 163                 hash_type h = hasher(i);
 164                 CPPUNIT_ASSERT( s.contains( h ));
 165                 std::pair<bool, bool> ret = s.update( arg_type( i, h ),
 166                     [](value_type& i, value_type * prev ) {
 167                         CPPUNIT_ASSERT_CURRENT( prev != nullptr );
 168                         CPPUNIT_ASSERT_CURRENT( i.key == prev->key );
 169                         CPPUNIT_ASSERT_CURRENT( i.hash == prev->hash );
 170                         i.nInsertCall += 1;
 171                     }, false );
 172                 CPPUNIT_ASSERT( ret.first );
 173                 CPPUNIT_ASSERT( !ret.second );
 174                 CPPUNIT_ASSERT( s.contains( h ));
 175                 CPPUNIT_ASSERT( s.size() == capacity );
 176
 177                 guarded_ptr gp(s.get( h ));
 178                 CPPUNIT_ASSERT( gp );
 179                 CPPUNIT_ASSERT( gp->nInsertCall == 1 );
 180                 CPPUNIT_ASSERT( gp->key == i );
 181                 CPPUNIT_ASSERT( gp->hash == h );
 182             }
 183
 184             // erase test
 185             for ( size_t i = 0; i < capacity; ++i ) {
 186                 CPPUNIT_ASSERT( !s.empty() );
 187                 CPPUNIT_ASSERT( s.size() == capacity - i );
 188                 CPPUNIT_ASSERT(s.find(hasher(i), []( value_type &) {}));
 189                 CPPUNIT_ASSERT( s.erase(hasher(i)) );
 190                 CPPUNIT_ASSERT( !s.find(hasher(i), []( value_type &) {}));
 191                 CPPUNIT_ASSERT( s.size() == capacity - i - 1);
 192             }
 193             CPPUNIT_ASSERT( s.empty() );
 194
 195             // Iterators on empty set
 196             CPPUNIT_ASSERT(s.begin() == s.end());
 197             CPPUNIT_ASSERT(s.cbegin() == s.cend());
 198             CPPUNIT_ASSERT(s.rbegin() == s.rend());
 199             CPPUNIT_ASSERT(s.crbegin() == s.crend());
 200
 201             // insert with functor
 202             for ( size_t i = capacity; i > 0; --i ) {
 203                 CPPUNIT_ASSERT( s.size() == capacity - i );
 204                 CPPUNIT_ASSERT(s.insert( arg_type( i, hasher(i)), []( value_type& val ) { val.nInsertCall += 1; } ));
 205                 CPPUNIT_ASSERT( s.size() == capacity - i + 1 );
 206                 CPPUNIT_ASSERT( !s.empty() );
 207
 208                 CPPUNIT_ASSERT(s.find( hasher(i), []( value_type& val ) {
 209                     CPPUNIT_ASSERT_CURRENT( val.nInsertCall == 1 );
 210                     val.nFindCall += 1;
 211                 } ));
 212             }
 213                 CPPUNIT_ASSERT( s.size() == capacity );
 214
 215             // for-each iterator test
 216             for ( auto& el : s ) {
 217                 CPPUNIT_ASSERT( el.nInsertCall == 1 );
 218                 CPPUNIT_ASSERT( el.nFindCall == 1 );
 219                 el.nFindCall += 1;
 220             }
 221
 222             // iterator test
 223             for ( auto it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 224                 CPPUNIT_ASSERT( it->nInsertCall == 1 );
 225                 CPPUNIT_ASSERT( it->nFindCall == 2 );
 226                 it->nFindCall += 1;
 227             }
 228
 229             // reverse iterator test
 230             for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) {
 231                 CPPUNIT_ASSERT( it->nInsertCall == 1 );
 232                 CPPUNIT_ASSERT( it->nFindCall == 3 );
 233                 it->nFindCall += 1;
 234             }
 235
 236             // const iterator test
 237             for ( auto it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it ) {
 238                 CPPUNIT_ASSERT( it->nInsertCall == 1 );
 239                 CPPUNIT_ASSERT( it->nFindCall == 4 );
 240                 it->nIteratorCall += 1;
 241             }
 242
 243             // const reverse iterator test
 244             for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) {
 245                 CPPUNIT_ASSERT( it->nInsertCall == 1 );
 246                 CPPUNIT_ASSERT( it->nFindCall == 4 );
 247                 CPPUNIT_ASSERT( it->nIteratorCall == 1 );
 248                 it->nIteratorCall += 1;
 249             }
 250
 251             // check completeness
 252             for ( size_t i = 1; i <= capacity; ++i ) {
 253                 CPPUNIT_ASSERT( s.find( hasher( i ), []( value_type const& el ) {
 254                     CPPUNIT_ASSERT_CURRENT( el.nInsertCall == 1 );
 255                     CPPUNIT_ASSERT_CURRENT( el.nFindCall == 4 );
 256                     CPPUNIT_ASSERT_CURRENT( el.nIteratorCall == 2 );
 257                 } ));
 258             }
 259
 260             // erase with functor test
 261             {
 262                 size_t nSum = 0;
 263                 for ( size_t i = 1; i <= capacity; ++i ) {
 264                     CPPUNIT_ASSERT( s.size() == capacity - i + 1 );
 265                     CPPUNIT_ASSERT(s.erase(hasher(i), [&nSum]( value_type const& val ) {
 266                         CPPUNIT_ASSERT_CURRENT( val.nInsertCall == 1 );
 267                         CPPUNIT_ASSERT_CURRENT( val.nFindCall == 4 );
 268                         CPPUNIT_ASSERT_CURRENT( val.nIteratorCall == 2 );
 269                         nSum += val.key;
 270                     } ))
 271                     CPPUNIT_ASSERT( s.size() == capacity - i );
 272                     CPPUNIT_ASSERT( !s.erase(hasher(i), [&nSum]( value_type const& val ) { nSum += val.key; } ))
 273                 }
 274                 CPPUNIT_ASSERT(s.empty() );
 275                 CPPUNIT_ASSERT(nSum == (1 + capacity) * capacity / 2 );
 276             }
 277
 278             // update test with insert allowing
 279             for ( size_t i = 0; i < capacity; ++i ) {
 280                 hash_type h = hasher(i);
 281                 CPPUNIT_ASSERT( !s.contains( h ));
 282                 guarded_ptr gp(s.get( h ));
 283                 CPPUNIT_ASSERT( !gp );
 284                 std::pair<bool, bool> ret = s.update( arg_type( i, h ),
 285                     [](value_type& i, value_type * prev ) {
 286                         CPPUNIT_ASSERT_CURRENT( prev == nullptr );
 287                         i.nInsertCall += 1;
 288                     });
 289                 CPPUNIT_ASSERT( ret.first );
 290                 CPPUNIT_ASSERT( ret.second );
 291                 CPPUNIT_ASSERT( s.contains( h ));
 292                 CPPUNIT_ASSERT( s.size() == i + 1 );
 293
 294                 gp = s.get( h );
 295                 CPPUNIT_ASSERT( gp );
 296                 CPPUNIT_ASSERT( gp->nInsertCall == 1 );
 297                 CPPUNIT_ASSERT( gp->key == i );
 298                 CPPUNIT_ASSERT( gp->hash == h );
 299             }
 300             CPPUNIT_ASSERT( !s.empty() );
 301             CPPUNIT_ASSERT(s.size() == capacity );
 302
 303             // erase_at( iterator ) test
 304             for ( auto it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 305                 CPPUNIT_ASSERT( s.erase_at( it ));
 306             }
 307             CPPUNIT_ASSERT( s.empty() );
 308             CPPUNIT_ASSERT( s.size() == 0 );
 309
 310             // emplace test
 311             for ( size_t i = 0; i < capacity; ++i ) {
 312                 hash_type h = hasher(i);
 313                 CPPUNIT_ASSERT( !s.contains( h ));
 314                 CPPUNIT_ASSERT( s.emplace( i, hasher(i) ));
 315                 CPPUNIT_ASSERT(s.contains( h ));
 316
 317                 CPPUNIT_ASSERT( !s.empty() );
 318                 CPPUNIT_ASSERT( s.size() == i + 1);
 319
 320                 CPPUNIT_ASSERT( !s.emplace( arg_type(i, h) ));
 321                 CPPUNIT_ASSERT( s.size() == i + 1);
 322             }
 323             CPPUNIT_ASSERT( !s.empty() );
 324             CPPUNIT_ASSERT(s.size() == capacity );
 325
 326             // erase_at( reverse_iterator ) test
 327             for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) {
 328                 CPPUNIT_ASSERT( s.erase_at( it ));
 329             }
 330             CPPUNIT_ASSERT( s.empty() );
 331             CPPUNIT_ASSERT( s.size() == 0 );
 332
 333             // extract test
 334             for ( size_t i = 0; i < capacity; ++i ) {
 335                 hash_type h = hasher(i);
 336                 CPPUNIT_ASSERT( !s.contains( h ));
 337                 CPPUNIT_ASSERT( s.emplace( arg_type( i, hasher(i) )));
 338                 CPPUNIT_ASSERT(s.contains( h ));
 339
 340                 CPPUNIT_ASSERT( !s.empty() );
 341                 CPPUNIT_ASSERT( s.size() == i + 1);
 342
 343                 CPPUNIT_ASSERT( !s.emplace( i, h ));
 344                 CPPUNIT_ASSERT( s.size() == i + 1);
 345             }
 346             CPPUNIT_ASSERT( !s.empty() );
 347             CPPUNIT_ASSERT(s.size() == capacity );
 348
 349             for ( size_t i = capacity; i != 0; --i ) {
 350                 CPPUNIT_ASSERT( !s.empty() );
 351                 CPPUNIT_ASSERT( s.size() == i );
 352
 353                 guarded_ptr gp{ s.extract( hasher(i-1)) };
 354                 CPPUNIT_ASSERT( gp );
 355                 CPPUNIT_ASSERT( gp->key == i - 1);
 356                 CPPUNIT_ASSERT(gp->hash == hasher(i-1));
 357                 CPPUNIT_ASSERT( !s.contains(hasher(i-1)));
 358
 359                 gp = s.get(hasher(i-1));
 360                 CPPUNIT_ASSERT( !gp );
 361
 362                 CPPUNIT_ASSERT( s.size() == i - 1 );
 363             }
 364             CPPUNIT_ASSERT( s.empty() );
 365             CPPUNIT_ASSERT(s.size() == 0 );
 366
 367             // clear test
 368             for ( size_t i = 0; i < capacity; ++i ) {
 369                 hash_type h = hasher(i);
 370                 CPPUNIT_ASSERT( !s.contains( h ));
 371                 CPPUNIT_ASSERT( s.emplace( arg_type( i, hasher(i) )));
 372                 CPPUNIT_ASSERT(s.contains( h ));
 373
 374                 CPPUNIT_ASSERT( !s.empty() );
 375                 CPPUNIT_ASSERT( s.size() == i + 1);
 376
 377                 CPPUNIT_ASSERT( !s.emplace( i, h ));
 378                 CPPUNIT_ASSERT( s.size() == i + 1);
 379             }
 380             CPPUNIT_ASSERT( !s.empty() );
 381             CPPUNIT_ASSERT(s.size() == capacity );
 382
 383             s.clear();
 384             CPPUNIT_ASSERT( s.empty() );
 385             CPPUNIT_ASSERT(s.size() == 0 );
 386
 387             CPPUNIT_MSG( s.statistics() );
 388         }
 389
 390         void hp_stdhash();
 391         void hp_stdhash_stat();
 392         void hp_stdhash_5_3();
 393         void hp_stdhash_5_3_stat();
 394         void hp_hash128();
 395         void hp_hash128_stat();
 396         void hp_hash128_4_3();
 397         void hp_hash128_4_3_stat();
 398
 399         void dhp_stdhash();
 400         void dhp_stdhash_stat();
 401         void dhp_stdhash_5_3();
 402         void dhp_stdhash_5_3_stat();
 403         void dhp_hash128();
 404         void dhp_hash128_stat();
 405         void dhp_hash128_4_3();
 406         void dhp_hash128_4_3_stat();
 407
 408         CPPUNIT_TEST_SUITE(MultiLevelHashSetHdrTest)
 409             CPPUNIT_TEST(hp_stdhash)
 410             CPPUNIT_TEST(hp_stdhash_stat)
 411             CPPUNIT_TEST(hp_stdhash_5_3)
 412             CPPUNIT_TEST(hp_stdhash_5_3_stat)
 413             CPPUNIT_TEST(hp_hash128)
 414             CPPUNIT_TEST(hp_hash128_stat)
 415             CPPUNIT_TEST(hp_hash128_4_3)
 416             CPPUNIT_TEST(hp_hash128_4_3_stat)
 417
 418             CPPUNIT_TEST(dhp_stdhash)
 419             CPPUNIT_TEST(dhp_stdhash_stat)
 420             CPPUNIT_TEST(dhp_stdhash_5_3)
 421             CPPUNIT_TEST(dhp_stdhash_5_3_stat)
 422             CPPUNIT_TEST(dhp_hash128)
 423             CPPUNIT_TEST(dhp_hash128_stat)
 424             CPPUNIT_TEST(dhp_hash128_4_3)
 425             CPPUNIT_TEST(dhp_hash128_4_3_stat)
 426         CPPUNIT_TEST_SUITE_END()
 427     };
 428
 429 } // namespace set
 430
 431 #endif // #ifndef CDSTEST_HDR_MULTILEVEL_HASHSET_H