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         struct item_disposer {
  49             template <typename Hash>
  50             void operator()( Item<Hash> * p )
  51             {
  52                 ++p->nDisposeCount;
  53             }
  54         };
  55
  56         struct hash128
  57         {
  58             size_t lo;
  59             size_t hi;
  60
  61             hash128() {}
  62             hash128(size_t l, size_t h) : lo(l), hi(h) {}
  63
  64             struct make {
  65                 hash128 operator()( size_t n ) const
  66                 {
  67                     return hash128( std::hash<size_t>()( n ), std::hash<size_t>()( ~n ));
  68                 }
  69                 hash128 operator()( hash128 const& n ) const
  70                 {
  71                     return hash128( std::hash<size_t>()( n.lo ), std::hash<size_t>()( ~n.hi ));
  72                 }
  73             };
  74
  75             struct less {
  76                 bool operator()( hash128 const& lhs, hash128 const& rhs ) const
  77                 {
  78                     if ( lhs.hi != rhs.hi )
  79                         return lhs.hi < rhs.hi;
  80                     return lhs.lo < rhs.lo;
  81                 }
  82             };
  83
  84             struct cmp {
  85                 int operator()( hash128 const& lhs, hash128 const& rhs ) const
  86                 {
  87                     if ( lhs.hi != rhs.hi )
  88                         return lhs.hi < rhs.hi ? -1 : 1;
  89                     return lhs.lo < rhs.lo ? -1 : lhs.lo == rhs.lo ? 0 : 1;
  90                 }
  91             };
  92         };
  93
  94
  95         template <typename Set, typename Hash>
  96         void test_hp( size_t nHeadBits, size_t nArrayBits )
  97         {
  98             typedef typename Set::hash_type hash_type;
  99             typedef typename Set::value_type value_type;
 100
 101             Hash hasher;
 102
 103             size_t const arrCapacity = 1000;
 104             std::vector< value_type > arrValue;
 105             arrValue.reserve( arrCapacity );
 106             for ( size_t i = 0; i < arrCapacity; ++i ) {
 107                 arrValue.emplace_back( value_type() );
 108                 arrValue.back().hash = hasher( i );
 109             }
 110             CPPUNIT_ASSERT( arrValue.size() == arrCapacity );
 111
 112             Set s( nHeadBits, nArrayBits );
 113             CPPUNIT_MSG("Array size: head=" << s.head_size() << ", array_node=" << s.array_node_size());
 114             CPPUNIT_ASSERT(s.head_size() >= (size_t(1) << nHeadBits));
 115             CPPUNIT_ASSERT(s.array_node_size() == (size_t(1) << nArrayBits));
 116
 117             // insert() test
 118             CPPUNIT_ASSERT(s.size() == 0 );
 119             CPPUNIT_ASSERT(s.empty() );
 120             for ( auto& el : arrValue ) {
 121                 CPPUNIT_ASSERT( s.insert( el ));
 122                 CPPUNIT_ASSERT(s.contains( el.hash ));
 123             }
 124             CPPUNIT_ASSERT(s.size() == arrCapacity );
 125             for ( auto& el : arrValue ) {
 126                 CPPUNIT_ASSERT(s.contains( el.hash ));
 127                 CPPUNIT_ASSERT( !s.insert( el ) );
 128             }
 129             CPPUNIT_ASSERT(s.size() == arrCapacity );
 130             CPPUNIT_ASSERT( !s.empty() );
 131
 132             // Iterator test
 133             {
 134                 typedef typename Set::iterator iterator;
 135                 for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it )
 136                     ++(it->nIteratorCall);
 137                 for ( auto& el : arrValue ) {
 138                     CPPUNIT_ASSERT( el.nIteratorCall == 1 );
 139                     el.nIteratorCall = 0;
 140                 }
 141             }
 142
 143             {
 144                 // Const iterator test
 145                 for ( typename Set::const_iterator it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it )
 146                     (*it).nIteratorCall += 1;
 147                 for ( auto& el : arrValue ) {
 148                     CPPUNIT_ASSERT( el.nIteratorCall == 1 );
 149                     el.nIteratorCall = 0;
 150                 }
 151             }
 152
 153             {
 154                 // Reverse iterator test
 155                 for ( typename Set::reverse_iterator it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it )
 156                     it->nIteratorCall += 1;
 157                 for ( auto& el : arrValue ) {
 158                     CPPUNIT_ASSERT( el.nIteratorCall == 1 );
 159                     el.nIteratorCall = 0;
 160                 }
 161             }
 162
 163             {
 164                 // Reverse const iterator test
 165                 for ( typename Set::const_reverse_iterator it = s.crbegin(), itEnd = s.crend(); it != itEnd; ++it ) {
 166                     (*it).nIteratorCall += 1;
 167                     it.release();
 168                 }
 169                 for ( auto& el : arrValue ) {
 170                     CPPUNIT_ASSERT( el.nIteratorCall == 1 );
 171                     el.nIteratorCall = 0;
 172                 }
 173             }
 174
 175             // update() exists test
 176             for ( auto& el : arrValue ) {
 177                 bool bOp, bInsert;
 178                 std::tie(bOp, bInsert) = s.update( el, false );
 179                 CPPUNIT_ASSERT( bOp );
 180                 CPPUNIT_ASSERT( !bInsert );
 181                 CPPUNIT_ASSERT( el.nFindCall == 0 );
 182                 CPPUNIT_ASSERT(s.find(el.hash, [](value_type& v) { v.nFindCall++; } ));
 183                 CPPUNIT_ASSERT( el.nFindCall == 1 );
 184             }
 185
 186             // unlink test
 187             CPPUNIT_ASSERT(s.size() == arrCapacity );
 188             for ( auto const& el : arrValue ) {
 189                 CPPUNIT_ASSERT(s.unlink( el ));
 190                 CPPUNIT_ASSERT(!s.contains( el.hash ));
 191             }
 192             CPPUNIT_ASSERT(s.size() == 0 );
 193             Set::gc::force_dispose();
 194             for ( auto const& el : arrValue ) {
 195                 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
 196             }
 197
 198             // new hash values
 199             for ( auto& el : arrValue )
 200                 el.hash = hasher( el.hash );
 201
 202             // insert( func )
 203             CPPUNIT_ASSERT(s.size() == 0 );
 204             for ( auto& el : arrValue ) {
 205                 CPPUNIT_ASSERT( s.insert( el, []( value_type& v ) { ++v.nInsertCall; } ));
 206                 CPPUNIT_ASSERT(s.contains( el.hash ));
 207                 CPPUNIT_ASSERT( el.nInsertCall == 1 );
 208             }
 209             CPPUNIT_ASSERT(s.size() == arrCapacity );
 210             for ( auto& el : arrValue ) {
 211                 CPPUNIT_ASSERT(s.contains( el.hash ));
 212                 CPPUNIT_ASSERT( !s.insert( el ) );
 213             }
 214             CPPUNIT_ASSERT(s.size() == arrCapacity );
 215             CPPUNIT_ASSERT( !s.empty() );
 216
 217             for ( auto& el : arrValue )
 218                 el.nDisposeCount = 0;
 219
 220             s.clear();
 221             CPPUNIT_ASSERT(s.size() == 0 );
 222             Set::gc::force_dispose();
 223             for ( auto const& el : arrValue ) {
 224                 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
 225             }
 226
 227             // new hash values
 228             for ( auto& el : arrValue )
 229                 el.hash = hasher( el.hash );
 230
 231             // update test
 232             for ( auto& el : arrValue ) {
 233                 bool bOp, bInsert;
 234                 std::tie(bOp, bInsert) = s.update( el, false );
 235                 CPPUNIT_ASSERT( !bOp );
 236                 CPPUNIT_ASSERT( !bInsert );
 237                 CPPUNIT_ASSERT( !s.contains( el.hash ));
 238
 239                 std::tie(bOp, bInsert) = s.update( el, true );
 240                 CPPUNIT_ASSERT( bOp );
 241                 CPPUNIT_ASSERT( bInsert );
 242                 CPPUNIT_ASSERT( s.contains( el.hash ));
 243             }
 244             CPPUNIT_ASSERT(s.size() == arrCapacity );
 245
 246             // erase test
 247             for ( auto& el : arrValue ) {
 248                 el.nDisposeCount = 0;
 249                 CPPUNIT_ASSERT( s.contains( el.hash ));
 250                 CPPUNIT_ASSERT(s.erase( el.hash ));
 251                 CPPUNIT_ASSERT( !s.contains( el.hash ));
 252                 CPPUNIT_ASSERT( !s.erase( el.hash ));
 253             }
 254             CPPUNIT_ASSERT(s.size() == 0 );
 255             Set::gc::force_dispose();
 256             for ( auto& el : arrValue ) {
 257                 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
 258                 CPPUNIT_ASSERT(s.insert( el ));
 259             }
 260
 261             // erase with functor, get() test
 262             for ( auto& el : arrValue ) {
 263                 el.nDisposeCount = 0;
 264                 CPPUNIT_ASSERT( s.contains( el.hash ) );
 265                 {
 266                     typename Set::guarded_ptr gp{ s.get( el.hash ) };
 267                     CPPUNIT_ASSERT( gp );
 268                     CPPUNIT_ASSERT( gp->nEraseCall == 0);
 269                     CPPUNIT_ASSERT(s.erase( gp->hash, []( value_type& i ) { ++i.nEraseCall; } ));
 270                     CPPUNIT_ASSERT( gp->nEraseCall == 1);
 271                     Set::gc::force_dispose();
 272                     CPPUNIT_ASSERT( gp->nDisposeCount == 0 );
 273                 }
 274                 CPPUNIT_ASSERT( !s.contains( el.hash ));
 275                 CPPUNIT_ASSERT( !s.erase( el.hash ));
 276                 CPPUNIT_ASSERT( el.nEraseCall == 1 );
 277                 Set::gc::force_dispose();
 278                 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
 279             }
 280             CPPUNIT_ASSERT(s.size() == 0 );
 281
 282             // new hash values
 283             for ( auto& el : arrValue ) {
 284                 el.hash = hasher( el.hash );
 285                 el.nDisposeCount = 0;
 286                 bool bOp, bInsert;
 287                 std::tie(bOp, bInsert) = s.update( el );
 288                 CPPUNIT_ASSERT( bOp );
 289                 CPPUNIT_ASSERT( bInsert );
 290             }
 291             CPPUNIT_ASSERT(s.size() == arrCapacity );
 292
 293             // extract test
 294             for ( auto& el : arrValue ) {
 295                 CPPUNIT_ASSERT( s.contains( el.hash ) );
 296                 typename Set::guarded_ptr gp = s.extract( el.hash );
 297                 CPPUNIT_ASSERT( gp );
 298                 Set::gc::force_dispose();
 299                 CPPUNIT_ASSERT( el.nDisposeCount == 0 );
 300                 CPPUNIT_ASSERT( gp->nDisposeCount == 0 );
 301                 gp = s.get( el.hash );
 302                 CPPUNIT_ASSERT( !gp );
 303                 Set::gc::force_dispose();
 304                 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
 305                 CPPUNIT_ASSERT( !s.contains( el.hash ) );
 306             }
 307             CPPUNIT_ASSERT(s.size() == 0 );
 308             CPPUNIT_ASSERT(s.empty() );
 309
 310             // erase with iterator
 311             for ( auto& el : arrValue ) {
 312                 el.nDisposeCount = 0;
 313                 el.nIteratorCall = 0;
 314                 CPPUNIT_ASSERT(s.insert( el ));
 315             }
 316             for ( auto it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) {
 317                 s.erase_at( it );
 318                 it->nIteratorCall = 1;
 319             }
 320             CPPUNIT_ASSERT(s.size() == 0 );
 321             Set::gc::force_dispose();
 322             for ( auto& el : arrValue ) {
 323                 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
 324                 CPPUNIT_ASSERT( el.nIteratorCall == 1 );
 325             }
 326             CPPUNIT_ASSERT(s.empty() );
 327
 328             // erase with reverse_iterator
 329             for ( auto& el : arrValue ) {
 330                 el.nDisposeCount = 0;
 331                 el.nIteratorCall = 0;
 332                 CPPUNIT_ASSERT(s.insert( el ));
 333             }
 334             for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) {
 335                 s.erase_at( it );
 336                 it->nIteratorCall = 1;
 337             }
 338             CPPUNIT_ASSERT(s.size() == 0 );
 339             Set::gc::force_dispose();
 340             for ( auto& el : arrValue ) {
 341                 CPPUNIT_ASSERT( el.nDisposeCount == 1 );
 342                 CPPUNIT_ASSERT( el.nIteratorCall == 1 );
 343             }
 344             CPPUNIT_ASSERT(s.empty() );
 345
 346             CPPUNIT_MSG( s.statistics() );
 347         }
 348
 349         void hp_stdhash();
 350         void hp_stdhash_stat();
 351         void hp_stdhash_5_3();
 352         void hp_stdhash_5_3_stat();
 353         void hp_hash128();
 354         void hp_hash128_stat();
 355         void hp_hash128_4_3();
 356         void hp_hash128_4_3_stat();
 357
 358         void dhp_stdhash();
 359         void dhp_stdhash_stat();
 360         void dhp_stdhash_5_3();
 361         void dhp_stdhash_5_3_stat();
 362         void dhp_hash128();
 363         void dhp_hash128_stat();
 364         void dhp_hash128_4_3();
 365         void dhp_hash128_4_3_stat();
 366
 367         CPPUNIT_TEST_SUITE(IntrusiveMultiLevelHashSetHdrTest)
 368             CPPUNIT_TEST(hp_stdhash)
 369             CPPUNIT_TEST(hp_stdhash_stat)
 370             CPPUNIT_TEST(hp_stdhash_5_3)
 371             CPPUNIT_TEST(hp_stdhash_5_3_stat)
 372             CPPUNIT_TEST(hp_hash128)
 373             CPPUNIT_TEST(hp_hash128_stat)
 374             CPPUNIT_TEST(hp_hash128_4_3)
 375             CPPUNIT_TEST(hp_hash128_4_3_stat)
 376
 377             CPPUNIT_TEST(dhp_stdhash)
 378             CPPUNIT_TEST(dhp_stdhash_stat)
 379             CPPUNIT_TEST(dhp_stdhash_5_3)
 380             CPPUNIT_TEST(dhp_stdhash_5_3_stat)
 381             CPPUNIT_TEST(dhp_hash128)
 382             CPPUNIT_TEST(dhp_hash128_stat)
 383             CPPUNIT_TEST(dhp_hash128_4_3)
 384             CPPUNIT_TEST(dhp_hash128_4_3_stat)
 385         CPPUNIT_TEST_SUITE_END()
 386     };
 387 } // namespace set
 388
 389 #endif // #ifndef CDSTEST_HDR_INTRUSIVE_MULTILEVEL_HASHSET_H