tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h

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