1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jsapi-tests/testHashTable.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,289 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +#include "js/HashTable.h"
1.9 +#include "jsapi-tests/tests.h"
1.10 +
1.11 +//#define FUZZ
1.12 +
1.13 +typedef js::HashMap<uint32_t, uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntMap;
1.14 +typedef js::HashSet<uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntSet;
1.15 +
1.16 +/*
1.17 + * The rekeying test as conducted by adding only keys masked with 0x0000FFFF
1.18 + * that are unique. We rekey by shifting left 16 bits.
1.19 + */
1.20 +#ifdef FUZZ
1.21 +const size_t TestSize = 0x0000FFFF / 2;
1.22 +const size_t TestIterations = SIZE_MAX;
1.23 +#else
1.24 +const size_t TestSize = 10000;
1.25 +const size_t TestIterations = 10;
1.26 +#endif
1.27 +
1.28 +JS_STATIC_ASSERT(TestSize <= 0x0000FFFF / 2);
1.29 +
1.30 +struct LowToHigh
1.31 +{
1.32 + static uint32_t rekey(uint32_t initial) {
1.33 + if (initial > uint32_t(0x0000FFFF))
1.34 + return initial;
1.35 + return initial << 16;
1.36 + }
1.37 +
1.38 + static bool shouldBeRemoved(uint32_t initial) {
1.39 + return false;
1.40 + }
1.41 +};
1.42 +
1.43 +struct LowToHighWithRemoval
1.44 +{
1.45 + static uint32_t rekey(uint32_t initial) {
1.46 + if (initial > uint32_t(0x0000FFFF))
1.47 + return initial;
1.48 + return initial << 16;
1.49 + }
1.50 +
1.51 + static bool shouldBeRemoved(uint32_t initial) {
1.52 + if (initial >= 0x00010000)
1.53 + return (initial >> 16) % 2 == 0;
1.54 + return initial % 2 == 0;
1.55 + }
1.56 +};
1.57 +
1.58 +static bool
1.59 +MapsAreEqual(IntMap &am, IntMap &bm)
1.60 +{
1.61 + bool equal = true;
1.62 + if (am.count() != bm.count()) {
1.63 + equal = false;
1.64 + fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
1.65 + }
1.66 + for (IntMap::Range r = am.all(); !r.empty(); r.popFront()) {
1.67 + if (!bm.has(r.front().key())) {
1.68 + equal = false;
1.69 + fprintf(stderr, "B does not have %x which is in A\n", r.front().key());
1.70 + }
1.71 + }
1.72 + for (IntMap::Range r = bm.all(); !r.empty(); r.popFront()) {
1.73 + if (!am.has(r.front().key())) {
1.74 + equal = false;
1.75 + fprintf(stderr, "A does not have %x which is in B\n", r.front().key());
1.76 + }
1.77 + }
1.78 + return equal;
1.79 +}
1.80 +
1.81 +static bool
1.82 +SetsAreEqual(IntSet &am, IntSet &bm)
1.83 +{
1.84 + bool equal = true;
1.85 + if (am.count() != bm.count()) {
1.86 + equal = false;
1.87 + fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
1.88 + }
1.89 + for (IntSet::Range r = am.all(); !r.empty(); r.popFront()) {
1.90 + if (!bm.has(r.front())) {
1.91 + equal = false;
1.92 + fprintf(stderr, "B does not have %x which is in A\n", r.front());
1.93 + }
1.94 + }
1.95 + for (IntSet::Range r = bm.all(); !r.empty(); r.popFront()) {
1.96 + if (!am.has(r.front())) {
1.97 + equal = false;
1.98 + fprintf(stderr, "A does not have %x which is in B\n", r.front());
1.99 + }
1.100 + }
1.101 + return equal;
1.102 +}
1.103 +
1.104 +static bool
1.105 +AddLowKeys(IntMap *am, IntMap *bm, int seed)
1.106 +{
1.107 + size_t i = 0;
1.108 + srand(seed);
1.109 + while (i < TestSize) {
1.110 + uint32_t n = rand() & 0x0000FFFF;
1.111 + if (!am->has(n)) {
1.112 + if (bm->has(n))
1.113 + return false;
1.114 + am->putNew(n, n);
1.115 + bm->putNew(n, n);
1.116 + i++;
1.117 + }
1.118 + }
1.119 + return true;
1.120 +}
1.121 +
1.122 +static bool
1.123 +AddLowKeys(IntSet *as, IntSet *bs, int seed)
1.124 +{
1.125 + size_t i = 0;
1.126 + srand(seed);
1.127 + while (i < TestSize) {
1.128 + uint32_t n = rand() & 0x0000FFFF;
1.129 + if (!as->has(n)) {
1.130 + if (bs->has(n))
1.131 + return false;
1.132 + as->putNew(n);
1.133 + bs->putNew(n);
1.134 + i++;
1.135 + }
1.136 + }
1.137 + return true;
1.138 +}
1.139 +
1.140 +template <class NewKeyFunction>
1.141 +static bool
1.142 +SlowRekey(IntMap *m) {
1.143 + IntMap tmp;
1.144 + tmp.init();
1.145 +
1.146 + for (IntMap::Range r = m->all(); !r.empty(); r.popFront()) {
1.147 + if (NewKeyFunction::shouldBeRemoved(r.front().key()))
1.148 + continue;
1.149 + uint32_t hi = NewKeyFunction::rekey(r.front().key());
1.150 + if (tmp.has(hi))
1.151 + return false;
1.152 + tmp.putNew(hi, r.front().value());
1.153 + }
1.154 +
1.155 + m->clear();
1.156 + for (IntMap::Range r = tmp.all(); !r.empty(); r.popFront()) {
1.157 + m->putNew(r.front().key(), r.front().value());
1.158 + }
1.159 +
1.160 + return true;
1.161 +}
1.162 +
1.163 +template <class NewKeyFunction>
1.164 +static bool
1.165 +SlowRekey(IntSet *s) {
1.166 + IntSet tmp;
1.167 + tmp.init();
1.168 +
1.169 + for (IntSet::Range r = s->all(); !r.empty(); r.popFront()) {
1.170 + if (NewKeyFunction::shouldBeRemoved(r.front()))
1.171 + continue;
1.172 + uint32_t hi = NewKeyFunction::rekey(r.front());
1.173 + if (tmp.has(hi))
1.174 + return false;
1.175 + tmp.putNew(hi);
1.176 + }
1.177 +
1.178 + s->clear();
1.179 + for (IntSet::Range r = tmp.all(); !r.empty(); r.popFront()) {
1.180 + s->putNew(r.front());
1.181 + }
1.182 +
1.183 + return true;
1.184 +}
1.185 +
1.186 +BEGIN_TEST(testHashRekeyManual)
1.187 +{
1.188 + IntMap am, bm;
1.189 + am.init();
1.190 + bm.init();
1.191 + for (size_t i = 0; i < TestIterations; ++i) {
1.192 +#ifdef FUZZ
1.193 + fprintf(stderr, "map1: %lu\n", i);
1.194 +#endif
1.195 + CHECK(AddLowKeys(&am, &bm, i));
1.196 + CHECK(MapsAreEqual(am, bm));
1.197 +
1.198 + for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
1.199 + uint32_t tmp = LowToHigh::rekey(e.front().key());
1.200 + if (tmp != e.front().key())
1.201 + e.rekeyFront(tmp);
1.202 + }
1.203 + CHECK(SlowRekey<LowToHigh>(&bm));
1.204 +
1.205 + CHECK(MapsAreEqual(am, bm));
1.206 + am.clear();
1.207 + bm.clear();
1.208 + }
1.209 +
1.210 + IntSet as, bs;
1.211 + as.init();
1.212 + bs.init();
1.213 + for (size_t i = 0; i < TestIterations; ++i) {
1.214 +#ifdef FUZZ
1.215 + fprintf(stderr, "set1: %lu\n", i);
1.216 +#endif
1.217 + CHECK(AddLowKeys(&as, &bs, i));
1.218 + CHECK(SetsAreEqual(as, bs));
1.219 +
1.220 + for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
1.221 + uint32_t tmp = LowToHigh::rekey(e.front());
1.222 + if (tmp != e.front())
1.223 + e.rekeyFront(tmp);
1.224 + }
1.225 + CHECK(SlowRekey<LowToHigh>(&bs));
1.226 +
1.227 + CHECK(SetsAreEqual(as, bs));
1.228 + as.clear();
1.229 + bs.clear();
1.230 + }
1.231 +
1.232 + return true;
1.233 +}
1.234 +END_TEST(testHashRekeyManual)
1.235 +
1.236 +BEGIN_TEST(testHashRekeyManualRemoval)
1.237 +{
1.238 + IntMap am, bm;
1.239 + am.init();
1.240 + bm.init();
1.241 + for (size_t i = 0; i < TestIterations; ++i) {
1.242 +#ifdef FUZZ
1.243 + fprintf(stderr, "map2: %lu\n", i);
1.244 +#endif
1.245 + CHECK(AddLowKeys(&am, &bm, i));
1.246 + CHECK(MapsAreEqual(am, bm));
1.247 +
1.248 + for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
1.249 + if (LowToHighWithRemoval::shouldBeRemoved(e.front().key())) {
1.250 + e.removeFront();
1.251 + } else {
1.252 + uint32_t tmp = LowToHighWithRemoval::rekey(e.front().key());
1.253 + if (tmp != e.front().key())
1.254 + e.rekeyFront(tmp);
1.255 + }
1.256 + }
1.257 + CHECK(SlowRekey<LowToHighWithRemoval>(&bm));
1.258 +
1.259 + CHECK(MapsAreEqual(am, bm));
1.260 + am.clear();
1.261 + bm.clear();
1.262 + }
1.263 +
1.264 + IntSet as, bs;
1.265 + as.init();
1.266 + bs.init();
1.267 + for (size_t i = 0; i < TestIterations; ++i) {
1.268 +#ifdef FUZZ
1.269 + fprintf(stderr, "set1: %lu\n", i);
1.270 +#endif
1.271 + CHECK(AddLowKeys(&as, &bs, i));
1.272 + CHECK(SetsAreEqual(as, bs));
1.273 +
1.274 + for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
1.275 + if (LowToHighWithRemoval::shouldBeRemoved(e.front())) {
1.276 + e.removeFront();
1.277 + } else {
1.278 + uint32_t tmp = LowToHighWithRemoval::rekey(e.front());
1.279 + if (tmp != e.front())
1.280 + e.rekeyFront(tmp);
1.281 + }
1.282 + }
1.283 + CHECK(SlowRekey<LowToHighWithRemoval>(&bs));
1.284 +
1.285 + CHECK(SetsAreEqual(as, bs));
1.286 + as.clear();
1.287 + bs.clear();
1.288 + }
1.289 +
1.290 + return true;
1.291 +}
1.292 +END_TEST(testHashRekeyManualRemoval)
