From 5f8de423f190bbb79a62f804151bc24824fa32d8 Mon Sep 17 00:00:00 2001 From: "Matt A. Tobin" Date: Fri, 2 Feb 2018 04:16:08 -0500 Subject: Add m-esr52 at 52.6.0 --- js/src/jsapi-tests/testHashTable.cpp | 390 +++++++++++++++++++++++++++++++++++ 1 file changed, 390 insertions(+) create mode 100644 js/src/jsapi-tests/testHashTable.cpp (limited to 'js/src/jsapi-tests/testHashTable.cpp') diff --git a/js/src/jsapi-tests/testHashTable.cpp b/js/src/jsapi-tests/testHashTable.cpp new file mode 100644 index 0000000000..a22ff78471 --- /dev/null +++ b/js/src/jsapi-tests/testHashTable.cpp @@ -0,0 +1,390 @@ +/* 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 "js/HashTable.h" +#include "js/Utility.h" +#include "jsapi-tests/tests.h" + +//#define FUZZ + +typedef js::HashMap, js::SystemAllocPolicy> IntMap; +typedef js::HashSet, js::SystemAllocPolicy> IntSet; + +/* + * 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 + +JS_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 (IntMap::Range r = am.all(); !r.empty(); r.popFront()) { + if (!bm.has(r.front().key())) { + equal = false; + fprintf(stderr, "B does not have %x which is in A\n", r.front().key()); + } + } + for (IntMap::Range r = bm.all(); !r.empty(); r.popFront()) { + if (!am.has(r.front().key())) { + equal = false; + fprintf(stderr, "A does not have %x which is in B\n", r.front().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 (IntSet::Range r = am.all(); !r.empty(); r.popFront()) { + if (!bm.has(r.front())) { + equal = false; + fprintf(stderr, "B does not have %x which is in A\n", r.front()); + } + } + for (IntSet::Range r = bm.all(); !r.empty(); r.popFront()) { + if (!am.has(r.front())) { + equal = false; + fprintf(stderr, "A does not have %x which is in B\n", r.front()); + } + } + 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 +static bool +SlowRekey(IntMap* m) { + IntMap tmp; + if (!tmp.init()) + return false; + + for (IntMap::Range r = m->all(); !r.empty(); r.popFront()) { + if (NewKeyFunction::shouldBeRemoved(r.front().key())) + continue; + uint32_t hi = NewKeyFunction::rekey(r.front().key()); + if (tmp.has(hi)) + return false; + if (!tmp.putNew(hi, r.front().value())) + return false; + } + + m->clear(); + for (IntMap::Range r = tmp.all(); !r.empty(); r.popFront()) { + if (!m->putNew(r.front().key(), r.front().value())) + return false; + } + + return true; +} + +template +static bool +SlowRekey(IntSet* s) { + IntSet tmp; + if (!tmp.init()) + return false; + + for (IntSet::Range r = s->all(); !r.empty(); r.popFront()) { + if (NewKeyFunction::shouldBeRemoved(r.front())) + continue; + uint32_t hi = NewKeyFunction::rekey(r.front()); + if (tmp.has(hi)) + return false; + if (!tmp.putNew(hi)) + return false; + } + + s->clear(); + for (IntSet::Range r = tmp.all(); !r.empty(); r.popFront()) { + if (!s->putNew(r.front())) + return false; + } + + return true; +} + +BEGIN_TEST(testHashRekeyManual) +{ + IntMap am, bm; + CHECK(am.init()); + CHECK(bm.init()); + 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 (IntMap::Enum e(am); !e.empty(); e.popFront()) { + uint32_t tmp = LowToHigh::rekey(e.front().key()); + if (tmp != e.front().key()) + e.rekeyFront(tmp); + } + CHECK(SlowRekey(&bm)); + + CHECK(MapsAreEqual(am, bm)); + am.clear(); + bm.clear(); + } + + IntSet as, bs; + CHECK(as.init()); + CHECK(bs.init()); + 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 (IntSet::Enum e(as); !e.empty(); e.popFront()) { + uint32_t tmp = LowToHigh::rekey(e.front()); + if (tmp != e.front()) + e.rekeyFront(tmp); + } + CHECK(SlowRekey(&bs)); + + CHECK(SetsAreEqual(as, bs)); + as.clear(); + bs.clear(); + } + + return true; +} +END_TEST(testHashRekeyManual) + +BEGIN_TEST(testHashRekeyManualRemoval) +{ + IntMap am, bm; + CHECK(am.init()); + CHECK(bm.init()); + 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 (IntMap::Enum e(am); !e.empty(); e.popFront()) { + if (LowToHighWithRemoval::shouldBeRemoved(e.front().key())) { + e.removeFront(); + } else { + uint32_t tmp = LowToHighWithRemoval::rekey(e.front().key()); + if (tmp != e.front().key()) + e.rekeyFront(tmp); + } + } + CHECK(SlowRekey(&bm)); + + CHECK(MapsAreEqual(am, bm)); + am.clear(); + bm.clear(); + } + + IntSet as, bs; + CHECK(as.init()); + CHECK(bs.init()); + 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 (IntSet::Enum e(as); !e.empty(); e.popFront()) { + if (LowToHighWithRemoval::shouldBeRemoved(e.front())) { + e.removeFront(); + } else { + uint32_t tmp = LowToHighWithRemoval::rekey(e.front()); + if (tmp != e.front()) + e.rekeyFront(tmp); + } + } + CHECK(SlowRekey(&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(mozilla::Move(rhs)); + return *this; + } + + struct HashPolicy { + typedef MoveOnlyType Lookup; + + 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) +{ + typedef js::HashSet Set; + + Set set; + CHECK(set.init()); + + MoveOnlyType a(1); + + CHECK(set.put(mozilla::Move(a))); // This shouldn't generate a compiler error. + + return true; +} +END_TEST(testHashSetOfMoveOnlyType) + +#if defined(DEBUG) + +// Add entries to a HashMap using lookupWithDefault until either we get an OOM, +// or the table has been resized a few times. +static bool +LookupWithDefaultUntilResize() { + IntMap m; + + if (!m.init()) + return false; + + // 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) { + if (!m.lookupWithDefault(key++, 0)) + return false; + + size_t capacity = m.capacity(); + if (capacity != lastCapacity) { + resizes++; + lastCapacity = capacity; + } + } + + return true; +} + +BEGIN_TEST(testHashMapLookupWithDefaultOOM) +{ + uint32_t timeToFail; + for (timeToFail = 1; timeToFail < 1000; timeToFail++) { + js::oom::SimulateOOMAfter(timeToFail, js::oom::THREAD_TYPE_MAIN, false); + LookupWithDefaultUntilResize(); + } + + js::oom::ResetSimulatedOOM(); + return true; +} + +END_TEST(testHashMapLookupWithDefaultOOM) +#endif // defined(DEBUG) -- cgit v1.2.3