tor-browser

testHashTable.cpp (12482B)

---

/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "mozilla/HashFunctions.h"

#include <utility>

#include "js/HashTable.h"
#include "js/Utility.h"
#include "jsapi-tests/tests.h"

// #define FUZZ

using IntMap = js::HashMap<uint32_t, uint32_t, js::DefaultHasher<uint32_t>,
                          js::SystemAllocPolicy>;
using IntSet =
   js::HashSet<uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy>;

/*
* The rekeying test as conducted by adding only keys masked with 0x0000FFFF
* that are unique. We rekey by shifting left 16 bits.
*/
#ifdef FUZZ
const size_t TestSize = 0x0000FFFF / 2;
const size_t TestIterations = SIZE_MAX;
#else
const size_t TestSize = 10000;
const size_t TestIterations = 10;
#endif

static_assert(TestSize <= 0x0000FFFF / 2);

struct LowToHigh {
 static uint32_t rekey(uint32_t initial) {
   if (initial > uint32_t(0x0000FFFF)) {
     return initial;
   }
   return initial << 16;
 }

 static bool shouldBeRemoved(uint32_t initial) { return false; }
};

struct LowToHighWithRemoval {
 static uint32_t rekey(uint32_t initial) {
   if (initial > uint32_t(0x0000FFFF)) {
     return initial;
   }
   return initial << 16;
 }

 static bool shouldBeRemoved(uint32_t initial) {
   if (initial >= 0x00010000) {
     return (initial >> 16) % 2 == 0;
   }
   return initial % 2 == 0;
 }
};

static bool MapsAreEqual(IntMap& am, IntMap& bm) {
 bool equal = true;
 if (am.count() != bm.count()) {
   equal = false;
   fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(),
           bm.count());
 }
 for (auto iter = am.iter(); !iter.done(); iter.next()) {
   if (!bm.has(iter.get().key())) {
     equal = false;
     fprintf(stderr, "B does not have %x which is in A\n", iter.get().key());
   }
 }
 for (auto iter = bm.iter(); !iter.done(); iter.next()) {
   if (!am.has(iter.get().key())) {
     equal = false;
     fprintf(stderr, "A does not have %x which is in B\n", iter.get().key());
   }
 }
 return equal;
}

static bool SetsAreEqual(IntSet& am, IntSet& bm) {
 bool equal = true;
 if (am.count() != bm.count()) {
   equal = false;
   fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(),
           bm.count());
 }
 for (auto iter = am.iter(); !iter.done(); iter.next()) {
   if (!bm.has(iter.get())) {
     equal = false;
     fprintf(stderr, "B does not have %x which is in A\n", iter.get());
   }
 }
 for (auto iter = bm.iter(); !iter.done(); iter.next()) {
   if (!am.has(iter.get())) {
     equal = false;
     fprintf(stderr, "A does not have %x which is in B\n", iter.get());
   }
 }
 return equal;
}

static bool AddLowKeys(IntMap* am, IntMap* bm, int seed) {
 size_t i = 0;
 srand(seed);
 while (i < TestSize) {
   uint32_t n = rand() & 0x0000FFFF;
   if (!am->has(n)) {
     if (bm->has(n)) {
       return false;
     }

     if (!am->putNew(n, n) || !bm->putNew(n, n)) {
       return false;
     }
     i++;
   }
 }
 return true;
}

static bool AddLowKeys(IntSet* as, IntSet* bs, int seed) {
 size_t i = 0;
 srand(seed);
 while (i < TestSize) {
   uint32_t n = rand() & 0x0000FFFF;
   if (!as->has(n)) {
     if (bs->has(n)) {
       return false;
     }
     if (!as->putNew(n) || !bs->putNew(n)) {
       return false;
     }
     i++;
   }
 }
 return true;
}

template <class NewKeyFunction>
static bool SlowRekey(IntMap* m) {
 IntMap tmp;

 for (auto iter = m->iter(); !iter.done(); iter.next()) {
   if (NewKeyFunction::shouldBeRemoved(iter.get().key())) {
     continue;
   }
   uint32_t hi = NewKeyFunction::rekey(iter.get().key());
   if (tmp.has(hi)) {
     return false;
   }
   if (!tmp.putNew(hi, iter.get().value())) {
     return false;
   }
 }

 m->clear();
 for (auto iter = tmp.iter(); !iter.done(); iter.next()) {
   if (!m->putNew(iter.get().key(), iter.get().value())) {
     return false;
   }
 }

 return true;
}

template <class NewKeyFunction>
static bool SlowRekey(IntSet* s) {
 IntSet tmp;

 for (auto iter = s->iter(); !iter.done(); iter.next()) {
   if (NewKeyFunction::shouldBeRemoved(iter.get())) {
     continue;
   }
   uint32_t hi = NewKeyFunction::rekey(iter.get());
   if (tmp.has(hi)) {
     return false;
   }
   if (!tmp.putNew(hi)) {
     return false;
   }
 }

 s->clear();
 for (auto iter = tmp.iter(); !iter.done(); iter.next()) {
   if (!s->putNew(iter.get())) {
     return false;
   }
 }

 return true;
}

BEGIN_TEST(testHashRekeyManual) {
 IntMap am, bm;
 for (size_t i = 0; i < TestIterations; ++i) {
#ifdef FUZZ
   fprintf(stderr, "map1: %lu\n", i);
#endif
   CHECK(AddLowKeys(&am, &bm, i));
   CHECK(MapsAreEqual(am, bm));

   for (auto iter = am.modIter(); !iter.done(); iter.next()) {
     uint32_t tmp = LowToHigh::rekey(iter.get().key());
     if (tmp != iter.get().key()) {
       iter.rekey(tmp);
     }
   }
   CHECK(SlowRekey<LowToHigh>(&bm));

   CHECK(MapsAreEqual(am, bm));
   am.clear();
   bm.clear();
 }

 IntSet as, bs;
 for (size_t i = 0; i < TestIterations; ++i) {
#ifdef FUZZ
   fprintf(stderr, "set1: %lu\n", i);
#endif
   CHECK(AddLowKeys(&as, &bs, i));
   CHECK(SetsAreEqual(as, bs));

   for (auto iter = as.modIter(); !iter.done(); iter.next()) {
     uint32_t tmp = LowToHigh::rekey(iter.get());
     if (tmp != iter.get()) {
       iter.rekey(tmp);
     }
   }
   CHECK(SlowRekey<LowToHigh>(&bs));

   CHECK(SetsAreEqual(as, bs));
   as.clear();
   bs.clear();
 }

 return true;
}
END_TEST(testHashRekeyManual)

BEGIN_TEST(testHashRekeyManualRemoval) {
 IntMap am, bm;
 for (size_t i = 0; i < TestIterations; ++i) {
#ifdef FUZZ
   fprintf(stderr, "map2: %lu\n", i);
#endif
   CHECK(AddLowKeys(&am, &bm, i));
   CHECK(MapsAreEqual(am, bm));

   for (auto iter = am.modIter(); !iter.done(); iter.next()) {
     if (LowToHighWithRemoval::shouldBeRemoved(iter.get().key())) {
       iter.remove();
     } else {
       uint32_t tmp = LowToHighWithRemoval::rekey(iter.get().key());
       if (tmp != iter.get().key()) {
         iter.rekey(tmp);
       }
     }
   }
   CHECK(SlowRekey<LowToHighWithRemoval>(&bm));

   CHECK(MapsAreEqual(am, bm));
   am.clear();
   bm.clear();
 }

 IntSet as, bs;
 for (size_t i = 0; i < TestIterations; ++i) {
#ifdef FUZZ
   fprintf(stderr, "set1: %lu\n", i);
#endif
   CHECK(AddLowKeys(&as, &bs, i));
   CHECK(SetsAreEqual(as, bs));

   for (auto iter = as.modIter(); !iter.done(); iter.next()) {
     if (LowToHighWithRemoval::shouldBeRemoved(iter.get())) {
       iter.remove();
     } else {
       uint32_t tmp = LowToHighWithRemoval::rekey(iter.get());
       if (tmp != iter.get()) {
         iter.rekey(tmp);
       }
     }
   }
   CHECK(SlowRekey<LowToHighWithRemoval>(&bs));

   CHECK(SetsAreEqual(as, bs));
   as.clear();
   bs.clear();
 }

 return true;
}
END_TEST(testHashRekeyManualRemoval)

// A type that is not copyable, only movable.
struct MoveOnlyType {
 uint32_t val;

 explicit MoveOnlyType(uint32_t val) : val(val) {}

 MoveOnlyType(MoveOnlyType&& rhs) { val = rhs.val; }

 MoveOnlyType& operator=(MoveOnlyType&& rhs) {
   MOZ_ASSERT(&rhs != this);
   this->~MoveOnlyType();
   new (this) MoveOnlyType(std::move(rhs));
   return *this;
 }

 struct HashPolicy {
   using Lookup = MoveOnlyType;

   static js::HashNumber hash(const Lookup& lookup) { return lookup.val; }

   static bool match(const MoveOnlyType& existing, const Lookup& lookup) {
     return existing.val == lookup.val;
   }
 };

private:
 MoveOnlyType(const MoveOnlyType&) = delete;
 MoveOnlyType& operator=(const MoveOnlyType&) = delete;
};

BEGIN_TEST(testHashSetOfMoveOnlyType) {
 using Set = js::HashSet<MoveOnlyType, MoveOnlyType::HashPolicy,
                         js::SystemAllocPolicy>;

 Set set;

 MoveOnlyType a(1);

 CHECK(set.put(std::move(a)));  // This shouldn't generate a compiler error.

 return true;
}
END_TEST(testHashSetOfMoveOnlyType)

#if defined(DEBUG)

// Add entries to a HashMap until either we get an OOM, or the table has been
// resized a few times.
static bool GrowUntilResize() {
 IntMap m;

 // Add entries until we've resized the table four times.
 size_t lastCapacity = m.capacity();
 size_t resizes = 0;
 uint32_t key = 0;
 while (resizes < 4) {
   auto p = m.lookupForAdd(key);
   if (!p && !m.add(p, key, 0)) {
     return false;  // OOM'd in lookupForAdd() or add()
   }

   size_t capacity = m.capacity();
   if (capacity != lastCapacity) {
     resizes++;
     lastCapacity = capacity;
   }
   key++;
 }

 return true;
}

BEGIN_TEST(testHashMapGrowOOM) {
 uint32_t timeToFail;
 for (timeToFail = 1; timeToFail < 1000; timeToFail++) {
   js::oom::simulator.simulateFailureAfter(
       js::oom::FailureSimulator::Kind::OOM, timeToFail, js::THREAD_TYPE_MAIN,
       false);
   GrowUntilResize();
 }

 js::oom::simulator.reset();
 return true;
}

END_TEST(testHashMapGrowOOM)
#endif  // defined(DEBUG)

BEGIN_TEST(testHashTableMovableModIterator) {
 IntSet set;

 // Exercise returning a hash table ModIterator object from a function.

 CHECK(set.put(1));
 for (auto iter = setModIter(set); !iter.done(); iter.next()) {
   iter.remove();
 }
 CHECK(set.count() == 0);

 // Test moving an ModIterator object explicitly.

 CHECK(set.put(1));
 CHECK(set.put(2));
 CHECK(set.put(3));
 CHECK(set.count() == 3);
 {
   auto i1 = set.modIter();
   CHECK(!i1.done());
   i1.remove();
   i1.next();

   auto i2 = std::move(i1);
   CHECK(!i2.done());
   i2.remove();
   i2.next();
 }

 CHECK(set.count() == 1);
 return true;
}

IntSet::ModIterator setModIter(IntSet& set) { return set.modIter(); }

END_TEST(testHashTableMovableModIterator)

BEGIN_TEST(testHashLazyStorage) {
 // The following code depends on the current capacity computation, which
 // could change in the future.
 uint32_t defaultCap = 32;
 uint32_t minCap = 4;

 IntSet set;
 CHECK(set.capacity() == 0);

 CHECK(set.put(1));
 CHECK(set.capacity() == defaultCap);

 set.compact();  // effectively a no-op
 CHECK(set.capacity() == minCap);

 set.clear();
 CHECK(set.capacity() == minCap);

 set.compact();
 CHECK(set.capacity() == 0);

 CHECK(set.putNew(1));
 CHECK(set.capacity() == minCap);

 set.clear();
 set.compact();
 CHECK(set.capacity() == 0);

 auto p = set.lookupForAdd(1);
 CHECK(set.capacity() == 0);
 CHECK(set.add(p, 1));
 CHECK(set.capacity() == minCap);
 CHECK(set.has(1));

 set.clear();
 set.compact();
 CHECK(set.capacity() == 0);

 p = set.lookupForAdd(1);
 CHECK(set.putNew(2));
 CHECK(set.capacity() == minCap);
 CHECK(set.relookupOrAdd(p, 1, 1));
 CHECK(set.capacity() == minCap);
 CHECK(set.has(1));

 set.clear();
 set.compact();
 CHECK(set.capacity() == 0);

 CHECK(set.putNew(1));
 p = set.lookupForAdd(1);
 set.clear();
 set.compact();
 CHECK(set.count() == 0);
 CHECK(set.relookupOrAdd(p, 1, 1));
 CHECK(set.count() == 1);
 CHECK(set.capacity() == minCap);

 set.clear();
 set.compact();
 CHECK(set.capacity() == 0);

 CHECK(set.reserve(0));  // a no-op
 CHECK(set.capacity() == 0);

 CHECK(set.reserve(1));
 CHECK(set.capacity() == minCap);

 CHECK(set.reserve(0));  // a no-op
 CHECK(set.capacity() == minCap);

 CHECK(set.reserve(2));  // effectively a no-op
 CHECK(set.capacity() == minCap);

 // No need to clear here because we didn't add anything.
 set.compact();
 CHECK(set.capacity() == 0);

 CHECK(set.reserve(128));
 CHECK(set.capacity() == 256);
 CHECK(set.reserve(3));  // effectively a no-op
 CHECK(set.capacity() == 256);
 for (int i = 0; i < 8; i++) {
   CHECK(set.putNew(i));
 }
 CHECK(set.count() == 8);
 CHECK(set.capacity() == 256);
 set.compact();
 CHECK(set.capacity() == 16);
 set.compact();  // effectively a no-op
 CHECK(set.capacity() == 16);
 for (int i = 8; i < 16; i++) {
   CHECK(set.putNew(i));
 }
 CHECK(set.count() == 16);
 CHECK(set.capacity() == 32);
 set.clear();
 CHECK(set.capacity() == 32);
 set.compact();
 CHECK(set.capacity() == 0);

 // Lowest length for which reserve() will fail.
 static const uint32_t toobig = (1 << 29) + 1;
 CHECK(!set.reserve(toobig));
 CHECK(set.capacity() == 0);  // unchanged
 CHECK(set.reserve(16));
 CHECK(set.capacity() == 32);

 return true;
}
END_TEST(testHashLazyStorage)