js/src/jsapi-tests/testHashTable.cpp

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 #include "mozilla/HashFunctions.h"
   6
   7 #include <utility>
   8
   9 #include "ds/OrderedHashTable.h"
  10 #include "js/HashTable.h"
  11 #include "js/Utility.h"
  12 #include "jsapi-tests/tests.h"
  13
  14 // #define FUZZ
  15
  16 typedef js::HashMap<uint32_t, uint32_t, js::DefaultHasher<uint32_t>,
  17                     js::SystemAllocPolicy>
  18     IntMap;
  19 typedef js::HashSet<uint32_t, js::DefaultHasher<uint32_t>,
  20                     js::SystemAllocPolicy>
  21     IntSet;
  22
  23 /*
  24  * The rekeying test as conducted by adding only keys masked with 0x0000FFFF
  25  * that are unique. We rekey by shifting left 16 bits.
  26  */
  27 #ifdef FUZZ
  28 const size_t TestSize = 0x0000FFFF / 2;
  29 const size_t TestIterations = SIZE_MAX;
  30 #else
  31 const size_t TestSize = 10000;
  32 const size_t TestIterations = 10;
  33 #endif
  34
  35 static_assert(TestSize <= 0x0000FFFF / 2);
  36
  37 struct LowToHigh {
  38   static uint32_t rekey(uint32_t initial) {
  39     if (initial > uint32_t(0x0000FFFF)) {
  40       return initial;
  41     }
  42     return initial << 16;
  43   }
  44
  45   static bool shouldBeRemoved(uint32_t initial) { return false; }
  46 };
  47
  48 struct LowToHighWithRemoval {
  49   static uint32_t rekey(uint32_t initial) {
  50     if (initial > uint32_t(0x0000FFFF)) {
  51       return initial;
  52     }
  53     return initial << 16;
  54   }
  55
  56   static bool shouldBeRemoved(uint32_t initial) {
  57     if (initial >= 0x00010000) {
  58       return (initial >> 16) % 2 == 0;
  59     }
  60     return initial % 2 == 0;
  61   }
  62 };
  63
  64 static bool MapsAreEqual(IntMap& am, IntMap& bm) {
  65   bool equal = true;
  66   if (am.count() != bm.count()) {
  67     equal = false;
  68     fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(),
  69             bm.count());
  70   }
  71   for (auto iter = am.iter(); !iter.done(); iter.next()) {
  72     if (!bm.has(iter.get().key())) {
  73       equal = false;
  74       fprintf(stderr, "B does not have %x which is in A\n", iter.get().key());
  75     }
  76   }
  77   for (auto iter = bm.iter(); !iter.done(); iter.next()) {
  78     if (!am.has(iter.get().key())) {
  79       equal = false;
  80       fprintf(stderr, "A does not have %x which is in B\n", iter.get().key());
  81     }
  82   }
  83   return equal;
  84 }
  85
  86 static bool SetsAreEqual(IntSet& am, IntSet& bm) {
  87   bool equal = true;
  88   if (am.count() != bm.count()) {
  89     equal = false;
  90     fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(),
  91             bm.count());
  92   }
  93   for (auto iter = am.iter(); !iter.done(); iter.next()) {
  94     if (!bm.has(iter.get())) {
  95       equal = false;
  96       fprintf(stderr, "B does not have %x which is in A\n", iter.get());
  97     }
  98   }
  99   for (auto iter = bm.iter(); !iter.done(); iter.next()) {
 100     if (!am.has(iter.get())) {
 101       equal = false;
 102       fprintf(stderr, "A does not have %x which is in B\n", iter.get());
 103     }
 104   }
 105   return equal;
 106 }
 107
 108 static bool AddLowKeys(IntMap* am, IntMap* bm, int seed) {
 109   size_t i = 0;
 110   srand(seed);
 111   while (i < TestSize) {
 112     uint32_t n = rand() & 0x0000FFFF;
 113     if (!am->has(n)) {
 114       if (bm->has(n)) {
 115         return false;
 116       }
 117
 118       if (!am->putNew(n, n) || !bm->putNew(n, n)) {
 119         return false;
 120       }
 121       i++;
 122     }
 123   }
 124   return true;
 125 }
 126
 127 static bool AddLowKeys(IntSet* as, IntSet* bs, int seed) {
 128   size_t i = 0;
 129   srand(seed);
 130   while (i < TestSize) {
 131     uint32_t n = rand() & 0x0000FFFF;
 132     if (!as->has(n)) {
 133       if (bs->has(n)) {
 134         return false;
 135       }
 136       if (!as->putNew(n) || !bs->putNew(n)) {
 137         return false;
 138       }
 139       i++;
 140     }
 141   }
 142   return true;
 143 }
 144
 145 template <class NewKeyFunction>
 146 static bool SlowRekey(IntMap* m) {
 147   IntMap tmp;
 148
 149   for (auto iter = m->iter(); !iter.done(); iter.next()) {
 150     if (NewKeyFunction::shouldBeRemoved(iter.get().key())) {
 151       continue;
 152     }
 153     uint32_t hi = NewKeyFunction::rekey(iter.get().key());
 154     if (tmp.has(hi)) {
 155       return false;
 156     }
 157     if (!tmp.putNew(hi, iter.get().value())) {
 158       return false;
 159     }
 160   }
 161
 162   m->clear();
 163   for (auto iter = tmp.iter(); !iter.done(); iter.next()) {
 164     if (!m->putNew(iter.get().key(), iter.get().value())) {
 165       return false;
 166     }
 167   }
 168
 169   return true;
 170 }
 171
 172 template <class NewKeyFunction>
 173 static bool SlowRekey(IntSet* s) {
 174   IntSet tmp;
 175
 176   for (auto iter = s->iter(); !iter.done(); iter.next()) {
 177     if (NewKeyFunction::shouldBeRemoved(iter.get())) {
 178       continue;
 179     }
 180     uint32_t hi = NewKeyFunction::rekey(iter.get());
 181     if (tmp.has(hi)) {
 182       return false;
 183     }
 184     if (!tmp.putNew(hi)) {
 185       return false;
 186     }
 187   }
 188
 189   s->clear();
 190   for (auto iter = tmp.iter(); !iter.done(); iter.next()) {
 191     if (!s->putNew(iter.get())) {
 192       return false;
 193     }
 194   }
 195
 196   return true;
 197 }
 198
 199 BEGIN_TEST(testHashRekeyManual) {
 200   IntMap am, bm;
 201   for (size_t i = 0; i < TestIterations; ++i) {
 202 #ifdef FUZZ
 203     fprintf(stderr, "map1: %lu\n", i);
 204 #endif
 205     CHECK(AddLowKeys(&am, &bm, i));
 206     CHECK(MapsAreEqual(am, bm));
 207
 208     for (auto iter = am.modIter(); !iter.done(); iter.next()) {
 209       uint32_t tmp = LowToHigh::rekey(iter.get().key());
 210       if (tmp != iter.get().key()) {
 211         iter.rekey(tmp);
 212       }
 213     }
 214     CHECK(SlowRekey<LowToHigh>(&bm));
 215
 216     CHECK(MapsAreEqual(am, bm));
 217     am.clear();
 218     bm.clear();
 219   }
 220
 221   IntSet as, bs;
 222   for (size_t i = 0; i < TestIterations; ++i) {
 223 #ifdef FUZZ
 224     fprintf(stderr, "set1: %lu\n", i);
 225 #endif
 226     CHECK(AddLowKeys(&as, &bs, i));
 227     CHECK(SetsAreEqual(as, bs));
 228
 229     for (auto iter = as.modIter(); !iter.done(); iter.next()) {
 230       uint32_t tmp = LowToHigh::rekey(iter.get());
 231       if (tmp != iter.get()) {
 232         iter.rekey(tmp);
 233       }
 234     }
 235     CHECK(SlowRekey<LowToHigh>(&bs));
 236
 237     CHECK(SetsAreEqual(as, bs));
 238     as.clear();
 239     bs.clear();
 240   }
 241
 242   return true;
 243 }
 244 END_TEST(testHashRekeyManual)
 245
 246 BEGIN_TEST(testHashRekeyManualRemoval) {
 247   IntMap am, bm;
 248   for (size_t i = 0; i < TestIterations; ++i) {
 249 #ifdef FUZZ
 250     fprintf(stderr, "map2: %lu\n", i);
 251 #endif
 252     CHECK(AddLowKeys(&am, &bm, i));
 253     CHECK(MapsAreEqual(am, bm));
 254
 255     for (auto iter = am.modIter(); !iter.done(); iter.next()) {
 256       if (LowToHighWithRemoval::shouldBeRemoved(iter.get().key())) {
 257         iter.remove();
 258       } else {
 259         uint32_t tmp = LowToHighWithRemoval::rekey(iter.get().key());
 260         if (tmp != iter.get().key()) {
 261           iter.rekey(tmp);
 262         }
 263       }
 264     }
 265     CHECK(SlowRekey<LowToHighWithRemoval>(&bm));
 266
 267     CHECK(MapsAreEqual(am, bm));
 268     am.clear();
 269     bm.clear();
 270   }
 271
 272   IntSet as, bs;
 273   for (size_t i = 0; i < TestIterations; ++i) {
 274 #ifdef FUZZ
 275     fprintf(stderr, "set1: %lu\n", i);
 276 #endif
 277     CHECK(AddLowKeys(&as, &bs, i));
 278     CHECK(SetsAreEqual(as, bs));
 279
 280     for (auto iter = as.modIter(); !iter.done(); iter.next()) {
 281       if (LowToHighWithRemoval::shouldBeRemoved(iter.get())) {
 282         iter.remove();
 283       } else {
 284         uint32_t tmp = LowToHighWithRemoval::rekey(iter.get());
 285         if (tmp != iter.get()) {
 286           iter.rekey(tmp);
 287         }
 288       }
 289     }
 290     CHECK(SlowRekey<LowToHighWithRemoval>(&bs));
 291
 292     CHECK(SetsAreEqual(as, bs));
 293     as.clear();
 294     bs.clear();
 295   }
 296
 297   return true;
 298 }
 299 END_TEST(testHashRekeyManualRemoval)
 300
 301 // A type that is not copyable, only movable.
 302 struct MoveOnlyType {
 303   uint32_t val;
 304
 305   explicit MoveOnlyType(uint32_t val) : val(val) {}
 306
 307   MoveOnlyType(MoveOnlyType&& rhs) { val = rhs.val; }
 308
 309   MoveOnlyType& operator=(MoveOnlyType&& rhs) {
 310     MOZ_ASSERT(&rhs != this);
 311     this->~MoveOnlyType();
 312     new (this) MoveOnlyType(std::move(rhs));
 313     return *this;
 314   }
 315
 316   struct HashPolicy {
 317     typedef MoveOnlyType Lookup;
 318
 319     static js::HashNumber hash(const Lookup& lookup) { return lookup.val; }
 320
 321     static bool match(const MoveOnlyType& existing, const Lookup& lookup) {
 322       return existing.val == lookup.val;
 323     }
 324   };
 325
 326  private:
 327   MoveOnlyType(const MoveOnlyType&) = delete;
 328   MoveOnlyType& operator=(const MoveOnlyType&) = delete;
 329 };
 330
 331 BEGIN_TEST(testHashSetOfMoveOnlyType) {
 332   typedef js::HashSet<MoveOnlyType, MoveOnlyType::HashPolicy,
 333                       js::SystemAllocPolicy>
 334       Set;
 335
 336   Set set;
 337
 338   MoveOnlyType a(1);
 339
 340   CHECK(set.put(std::move(a)));  // This shouldn't generate a compiler error.
 341
 342   return true;
 343 }
 344 END_TEST(testHashSetOfMoveOnlyType)
 345
 346 #if defined(DEBUG)
 347
 348 // Add entries to a HashMap until either we get an OOM, or the table has been
 349 // resized a few times.
 350 static bool GrowUntilResize() {
 351   IntMap m;
 352
 353   // Add entries until we've resized the table four times.
 354   size_t lastCapacity = m.capacity();
 355   size_t resizes = 0;
 356   uint32_t key = 0;
 357   while (resizes < 4) {
 358     auto p = m.lookupForAdd(key);
 359     if (!p && !m.add(p, key, 0)) {
 360       return false;  // OOM'd in lookupForAdd() or add()
 361     }
 362
 363     size_t capacity = m.capacity();
 364     if (capacity != lastCapacity) {
 365       resizes++;
 366       lastCapacity = capacity;
 367     }
 368     key++;
 369   }
 370
 371   return true;
 372 }
 373
 374 BEGIN_TEST(testHashMapGrowOOM) {
 375   uint32_t timeToFail;
 376   for (timeToFail = 1; timeToFail < 1000; timeToFail++) {
 377     js::oom::simulator.simulateFailureAfter(
 378         js::oom::FailureSimulator::Kind::OOM, timeToFail, js::THREAD_TYPE_MAIN,
 379         false);
 380     GrowUntilResize();
 381   }
 382
 383   js::oom::simulator.reset();
 384   return true;
 385 }
 386
 387 END_TEST(testHashMapGrowOOM)
 388 #endif  // defined(DEBUG)
 389
 390 BEGIN_TEST(testHashTableMovableModIterator) {
 391   IntSet set;
 392
 393   // Exercise returning a hash table ModIterator object from a function.
 394
 395   CHECK(set.put(1));
 396   for (auto iter = setModIter(set); !iter.done(); iter.next()) {
 397     iter.remove();
 398   }
 399   CHECK(set.count() == 0);
 400
 401   // Test moving an ModIterator object explicitly.
 402
 403   CHECK(set.put(1));
 404   CHECK(set.put(2));
 405   CHECK(set.put(3));
 406   CHECK(set.count() == 3);
 407   {
 408     auto i1 = set.modIter();
 409     CHECK(!i1.done());
 410     i1.remove();
 411     i1.next();
 412
 413     auto i2 = std::move(i1);
 414     CHECK(!i2.done());
 415     i2.remove();
 416     i2.next();
 417   }
 418
 419   CHECK(set.count() == 1);
 420   return true;
 421 }
 422
 423 IntSet::ModIterator setModIter(IntSet& set) { return set.modIter(); }
 424
 425 END_TEST(testHashTableMovableModIterator)
 426
 427 BEGIN_TEST(testHashLazyStorage) {
 428   // The following code depends on the current capacity computation, which
 429   // could change in the future.
 430   uint32_t defaultCap = 32;
 431   uint32_t minCap = 4;
 432
 433   IntSet set;
 434   CHECK(set.capacity() == 0);
 435
 436   CHECK(set.put(1));
 437   CHECK(set.capacity() == defaultCap);
 438
 439   set.compact();  // effectively a no-op
 440   CHECK(set.capacity() == minCap);
 441
 442   set.clear();
 443   CHECK(set.capacity() == minCap);
 444
 445   set.compact();
 446   CHECK(set.capacity() == 0);
 447
 448   CHECK(set.putNew(1));
 449   CHECK(set.capacity() == minCap);
 450
 451   set.clear();
 452   set.compact();
 453   CHECK(set.capacity() == 0);
 454
 455   auto p = set.lookupForAdd(1);
 456   CHECK(set.capacity() == 0);
 457   CHECK(set.add(p, 1));
 458   CHECK(set.capacity() == minCap);
 459   CHECK(set.has(1));
 460
 461   set.clear();
 462   set.compact();
 463   CHECK(set.capacity() == 0);
 464
 465   p = set.lookupForAdd(1);
 466   CHECK(set.putNew(2));
 467   CHECK(set.capacity() == minCap);
 468   CHECK(set.relookupOrAdd(p, 1, 1));
 469   CHECK(set.capacity() == minCap);
 470   CHECK(set.has(1));
 471
 472   set.clear();
 473   set.compact();
 474   CHECK(set.capacity() == 0);
 475
 476   CHECK(set.putNew(1));
 477   p = set.lookupForAdd(1);
 478   set.clear();
 479   set.compact();
 480   CHECK(set.count() == 0);
 481   CHECK(set.relookupOrAdd(p, 1, 1));
 482   CHECK(set.count() == 1);
 483   CHECK(set.capacity() == minCap);
 484
 485   set.clear();
 486   set.compact();
 487   CHECK(set.capacity() == 0);
 488
 489   CHECK(set.reserve(0));  // a no-op
 490   CHECK(set.capacity() == 0);
 491
 492   CHECK(set.reserve(1));
 493   CHECK(set.capacity() == minCap);
 494
 495   CHECK(set.reserve(0));  // a no-op
 496   CHECK(set.capacity() == minCap);
 497
 498   CHECK(set.reserve(2));  // effectively a no-op
 499   CHECK(set.capacity() == minCap);
 500
 501   // No need to clear here because we didn't add anything.
 502   set.compact();
 503   CHECK(set.capacity() == 0);
 504
 505   CHECK(set.reserve(128));
 506   CHECK(set.capacity() == 256);
 507   CHECK(set.reserve(3));  // effectively a no-op
 508   CHECK(set.capacity() == 256);
 509   for (int i = 0; i < 8; i++) {
 510     CHECK(set.putNew(i));
 511   }
 512   CHECK(set.count() == 8);
 513   CHECK(set.capacity() == 256);
 514   set.compact();
 515   CHECK(set.capacity() == 16);
 516   set.compact();  // effectively a no-op
 517   CHECK(set.capacity() == 16);
 518   for (int i = 8; i < 16; i++) {
 519     CHECK(set.putNew(i));
 520   }
 521   CHECK(set.count() == 16);
 522   CHECK(set.capacity() == 32);
 523   set.clear();
 524   CHECK(set.capacity() == 32);
 525   set.compact();
 526   CHECK(set.capacity() == 0);
 527
 528   // Lowest length for which reserve() will fail.
 529   static const uint32_t toobig = (1 << 29) + 1;
 530   CHECK(!set.reserve(toobig));
 531   CHECK(set.capacity() == 0);  // unchanged
 532   CHECK(set.reserve(16));
 533   CHECK(set.capacity() == 32);
 534
 535   return true;
 536 }
 537 END_TEST(testHashLazyStorage)
 538
 539 BEGIN_TEST(testOrderedHashSetWithoutInit) {
 540   {
 541     struct NonzeroUint32HashPolicy {
 542       using Lookup = uint32_t;
 543       static js::HashNumber hash(const Lookup& v,
 544                                  const mozilla::HashCodeScrambler& hcs) {
 545         return mozilla::HashGeneric(v);
 546       }
 547       static bool match(const uint32_t& k, const Lookup& l) { return k == l; }
 548       static bool isEmpty(const uint32_t& v) { return v == 0; }
 549       static void makeEmpty(uint32_t* v) { *v = 0; }
 550     };
 551
 552     using OHS = js::OrderedHashSet<uint32_t, NonzeroUint32HashPolicy,
 553                                    js::SystemAllocPolicy>;
 554
 555     OHS set(js::SystemAllocPolicy(), mozilla::HashCodeScrambler(17, 42));
 556     CHECK(set.count() == 0);
 557
 558     // This test passes if the set is safely destructible even when |init()| is
 559     // never called.
 560   }
 561
 562   return true;
 563 }
 564 END_TEST(testOrderedHashSetWithoutInit)