michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "js/HashTable.h"
michael@0: #include "jsapi-tests/tests.h"
michael@0: 
michael@0: //#define FUZZ
michael@0: 
michael@0: typedef js::HashMap<uint32_t, uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntMap;
michael@0: typedef js::HashSet<uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntSet;
michael@0: 
michael@0: /*
michael@0:  * The rekeying test as conducted by adding only keys masked with 0x0000FFFF
michael@0:  * that are unique. We rekey by shifting left 16 bits.
michael@0:  */
michael@0: #ifdef FUZZ
michael@0: const size_t TestSize = 0x0000FFFF / 2;
michael@0: const size_t TestIterations = SIZE_MAX;
michael@0: #else
michael@0: const size_t TestSize = 10000;
michael@0: const size_t TestIterations = 10;
michael@0: #endif
michael@0: 
michael@0: JS_STATIC_ASSERT(TestSize <= 0x0000FFFF / 2);
michael@0: 
michael@0: struct LowToHigh
michael@0: {
michael@0:     static uint32_t rekey(uint32_t initial) {
michael@0:         if (initial > uint32_t(0x0000FFFF))
michael@0:             return initial;
michael@0:         return initial << 16;
michael@0:     }
michael@0: 
michael@0:     static bool shouldBeRemoved(uint32_t initial) {
michael@0:         return false;
michael@0:     }
michael@0: };
michael@0: 
michael@0: struct LowToHighWithRemoval
michael@0: {
michael@0:     static uint32_t rekey(uint32_t initial) {
michael@0:         if (initial > uint32_t(0x0000FFFF))
michael@0:             return initial;
michael@0:         return initial << 16;
michael@0:     }
michael@0: 
michael@0:     static bool shouldBeRemoved(uint32_t initial) {
michael@0:         if (initial >= 0x00010000)
michael@0:             return (initial >> 16) % 2 == 0;
michael@0:         return initial % 2 == 0;
michael@0:     }
michael@0: };
michael@0: 
michael@0: static bool
michael@0: MapsAreEqual(IntMap &am, IntMap &bm)
michael@0: {
michael@0:     bool equal = true;
michael@0:     if (am.count() != bm.count()) {
michael@0:         equal = false;
michael@0:         fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
michael@0:     }
michael@0:     for (IntMap::Range r = am.all(); !r.empty(); r.popFront()) {
michael@0:         if (!bm.has(r.front().key())) {
michael@0:             equal = false;
michael@0:             fprintf(stderr, "B does not have %x which is in A\n", r.front().key());
michael@0:         }
michael@0:     }
michael@0:     for (IntMap::Range r = bm.all(); !r.empty(); r.popFront()) {
michael@0:         if (!am.has(r.front().key())) {
michael@0:             equal = false;
michael@0:             fprintf(stderr, "A does not have %x which is in B\n", r.front().key());
michael@0:         }
michael@0:     }
michael@0:     return equal;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: SetsAreEqual(IntSet &am, IntSet &bm)
michael@0: {
michael@0:     bool equal = true;
michael@0:     if (am.count() != bm.count()) {
michael@0:         equal = false;
michael@0:         fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
michael@0:     }
michael@0:     for (IntSet::Range r = am.all(); !r.empty(); r.popFront()) {
michael@0:         if (!bm.has(r.front())) {
michael@0:             equal = false;
michael@0:             fprintf(stderr, "B does not have %x which is in A\n", r.front());
michael@0:         }
michael@0:     }
michael@0:     for (IntSet::Range r = bm.all(); !r.empty(); r.popFront()) {
michael@0:         if (!am.has(r.front())) {
michael@0:             equal = false;
michael@0:             fprintf(stderr, "A does not have %x which is in B\n", r.front());
michael@0:         }
michael@0:     }
michael@0:     return equal;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: AddLowKeys(IntMap *am, IntMap *bm, int seed)
michael@0: {
michael@0:     size_t i = 0;
michael@0:     srand(seed);
michael@0:     while (i < TestSize) {
michael@0:         uint32_t n = rand() & 0x0000FFFF;
michael@0:         if (!am->has(n)) {
michael@0:             if (bm->has(n))
michael@0:                 return false;
michael@0:             am->putNew(n, n);
michael@0:             bm->putNew(n, n);
michael@0:             i++;
michael@0:         }
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: AddLowKeys(IntSet *as, IntSet *bs, int seed)
michael@0: {
michael@0:     size_t i = 0;
michael@0:     srand(seed);
michael@0:     while (i < TestSize) {
michael@0:         uint32_t n = rand() & 0x0000FFFF;
michael@0:         if (!as->has(n)) {
michael@0:             if (bs->has(n))
michael@0:                 return false;
michael@0:             as->putNew(n);
michael@0:             bs->putNew(n);
michael@0:             i++;
michael@0:         }
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: template <class NewKeyFunction>
michael@0: static bool
michael@0: SlowRekey(IntMap *m) {
michael@0:     IntMap tmp;
michael@0:     tmp.init();
michael@0: 
michael@0:     for (IntMap::Range r = m->all(); !r.empty(); r.popFront()) {
michael@0:         if (NewKeyFunction::shouldBeRemoved(r.front().key()))
michael@0:             continue;
michael@0:         uint32_t hi = NewKeyFunction::rekey(r.front().key());
michael@0:         if (tmp.has(hi))
michael@0:             return false;
michael@0:         tmp.putNew(hi, r.front().value());
michael@0:     }
michael@0: 
michael@0:     m->clear();
michael@0:     for (IntMap::Range r = tmp.all(); !r.empty(); r.popFront()) {
michael@0:         m->putNew(r.front().key(), r.front().value());
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: template <class NewKeyFunction>
michael@0: static bool
michael@0: SlowRekey(IntSet *s) {
michael@0:     IntSet tmp;
michael@0:     tmp.init();
michael@0: 
michael@0:     for (IntSet::Range r = s->all(); !r.empty(); r.popFront()) {
michael@0:         if (NewKeyFunction::shouldBeRemoved(r.front()))
michael@0:             continue;
michael@0:         uint32_t hi = NewKeyFunction::rekey(r.front());
michael@0:         if (tmp.has(hi))
michael@0:             return false;
michael@0:         tmp.putNew(hi);
michael@0:     }
michael@0: 
michael@0:     s->clear();
michael@0:     for (IntSet::Range r = tmp.all(); !r.empty(); r.popFront()) {
michael@0:         s->putNew(r.front());
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: BEGIN_TEST(testHashRekeyManual)
michael@0: {
michael@0:     IntMap am, bm;
michael@0:     am.init();
michael@0:     bm.init();
michael@0:     for (size_t i = 0; i < TestIterations; ++i) {
michael@0: #ifdef FUZZ
michael@0:         fprintf(stderr, "map1: %lu\n", i);
michael@0: #endif
michael@0:         CHECK(AddLowKeys(&am, &bm, i));
michael@0:         CHECK(MapsAreEqual(am, bm));
michael@0: 
michael@0:         for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
michael@0:             uint32_t tmp = LowToHigh::rekey(e.front().key());
michael@0:             if (tmp != e.front().key())
michael@0:                 e.rekeyFront(tmp);
michael@0:         }
michael@0:         CHECK(SlowRekey<LowToHigh>(&bm));
michael@0: 
michael@0:         CHECK(MapsAreEqual(am, bm));
michael@0:         am.clear();
michael@0:         bm.clear();
michael@0:     }
michael@0: 
michael@0:     IntSet as, bs;
michael@0:     as.init();
michael@0:     bs.init();
michael@0:     for (size_t i = 0; i < TestIterations; ++i) {
michael@0: #ifdef FUZZ
michael@0:         fprintf(stderr, "set1: %lu\n", i);
michael@0: #endif
michael@0:         CHECK(AddLowKeys(&as, &bs, i));
michael@0:         CHECK(SetsAreEqual(as, bs));
michael@0: 
michael@0:         for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
michael@0:             uint32_t tmp = LowToHigh::rekey(e.front());
michael@0:             if (tmp != e.front())
michael@0:                 e.rekeyFront(tmp);
michael@0:         }
michael@0:         CHECK(SlowRekey<LowToHigh>(&bs));
michael@0: 
michael@0:         CHECK(SetsAreEqual(as, bs));
michael@0:         as.clear();
michael@0:         bs.clear();
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: END_TEST(testHashRekeyManual)
michael@0: 
michael@0: BEGIN_TEST(testHashRekeyManualRemoval)
michael@0: {
michael@0:     IntMap am, bm;
michael@0:     am.init();
michael@0:     bm.init();
michael@0:     for (size_t i = 0; i < TestIterations; ++i) {
michael@0: #ifdef FUZZ
michael@0:         fprintf(stderr, "map2: %lu\n", i);
michael@0: #endif
michael@0:         CHECK(AddLowKeys(&am, &bm, i));
michael@0:         CHECK(MapsAreEqual(am, bm));
michael@0: 
michael@0:         for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
michael@0:             if (LowToHighWithRemoval::shouldBeRemoved(e.front().key())) {
michael@0:                 e.removeFront();
michael@0:             } else {
michael@0:                 uint32_t tmp = LowToHighWithRemoval::rekey(e.front().key());
michael@0:                 if (tmp != e.front().key())
michael@0:                     e.rekeyFront(tmp);
michael@0:             }
michael@0:         }
michael@0:         CHECK(SlowRekey<LowToHighWithRemoval>(&bm));
michael@0: 
michael@0:         CHECK(MapsAreEqual(am, bm));
michael@0:         am.clear();
michael@0:         bm.clear();
michael@0:     }
michael@0: 
michael@0:     IntSet as, bs;
michael@0:     as.init();
michael@0:     bs.init();
michael@0:     for (size_t i = 0; i < TestIterations; ++i) {
michael@0: #ifdef FUZZ
michael@0:         fprintf(stderr, "set1: %lu\n", i);
michael@0: #endif
michael@0:         CHECK(AddLowKeys(&as, &bs, i));
michael@0:         CHECK(SetsAreEqual(as, bs));
michael@0: 
michael@0:         for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
michael@0:             if (LowToHighWithRemoval::shouldBeRemoved(e.front())) {
michael@0:                 e.removeFront();
michael@0:             } else {
michael@0:                 uint32_t tmp = LowToHighWithRemoval::rekey(e.front());
michael@0:                 if (tmp != e.front())
michael@0:                     e.rekeyFront(tmp);
michael@0:             }
michael@0:         }
michael@0:         CHECK(SlowRekey<LowToHighWithRemoval>(&bs));
michael@0: 
michael@0:         CHECK(SetsAreEqual(as, bs));
michael@0:         as.clear();
michael@0:         bs.clear();
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: END_TEST(testHashRekeyManualRemoval)