The Tor Browser / file comparison

comparison: js/src/jsapi-tests/testHashTable.cpp

js/src/jsapi-tests/testHashTable.cpp

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:77e0fc9aaa04
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 "js/HashTable.h"
6 #include "jsapi-tests/tests.h"
7
8 //#define FUZZ
9
10 typedef js::HashMap<uint32_t, uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntMap;
11 typedef js::HashSet<uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntSet;
12
13 /*
14 * The rekeying test as conducted by adding only keys masked with 0x0000FFFF
15 * that are unique. We rekey by shifting left 16 bits.
16 */
17 #ifdef FUZZ
18 const size_t TestSize = 0x0000FFFF / 2;
19 const size_t TestIterations = SIZE_MAX;
20 #else
21 const size_t TestSize = 10000;
22 const size_t TestIterations = 10;
23 #endif
24
25 JS_STATIC_ASSERT(TestSize <= 0x0000FFFF / 2);
26
27 struct LowToHigh
28 {
29 static uint32_t rekey(uint32_t initial) {
30 if (initial > uint32_t(0x0000FFFF))
31 return initial;
32 return initial << 16;
33 }
34
35 static bool shouldBeRemoved(uint32_t initial) {
36 return false;
37 }
38 };
39
40 struct LowToHighWithRemoval
41 {
42 static uint32_t rekey(uint32_t initial) {
43 if (initial > uint32_t(0x0000FFFF))
44 return initial;
45 return initial << 16;
46 }
47
48 static bool shouldBeRemoved(uint32_t initial) {
49 if (initial >= 0x00010000)
50 return (initial >> 16) % 2 == 0;
51 return initial % 2 == 0;
52 }
53 };
54
55 static bool
56 MapsAreEqual(IntMap &am, IntMap &bm)
57 {
58 bool equal = true;
59 if (am.count() != bm.count()) {
60 equal = false;
61 fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
62 }
63 for (IntMap::Range r = am.all(); !r.empty(); r.popFront()) {
64 if (!bm.has(r.front().key())) {
65 equal = false;
66 fprintf(stderr, "B does not have %x which is in A\n", r.front().key());
67 }
68 }
69 for (IntMap::Range r = bm.all(); !r.empty(); r.popFront()) {
70 if (!am.has(r.front().key())) {
71 equal = false;
72 fprintf(stderr, "A does not have %x which is in B\n", r.front().key());
73 }
74 }
75 return equal;
76 }
77
78 static bool
79 SetsAreEqual(IntSet &am, IntSet &bm)
80 {
81 bool equal = true;
82 if (am.count() != bm.count()) {
83 equal = false;
84 fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
85 }
86 for (IntSet::Range r = am.all(); !r.empty(); r.popFront()) {
87 if (!bm.has(r.front())) {
88 equal = false;
89 fprintf(stderr, "B does not have %x which is in A\n", r.front());
90 }
91 }
92 for (IntSet::Range r = bm.all(); !r.empty(); r.popFront()) {
93 if (!am.has(r.front())) {
94 equal = false;
95 fprintf(stderr, "A does not have %x which is in B\n", r.front());
96 }
97 }
98 return equal;
99 }
100
101 static bool
102 AddLowKeys(IntMap *am, IntMap *bm, int seed)
103 {
104 size_t i = 0;
105 srand(seed);
106 while (i < TestSize) {
107 uint32_t n = rand() & 0x0000FFFF;
108 if (!am->has(n)) {
109 if (bm->has(n))
110 return false;
111 am->putNew(n, n);
112 bm->putNew(n, n);
113 i++;
114 }
115 }
116 return true;
117 }
118
119 static bool
120 AddLowKeys(IntSet *as, IntSet *bs, int seed)
121 {
122 size_t i = 0;
123 srand(seed);
124 while (i < TestSize) {
125 uint32_t n = rand() & 0x0000FFFF;
126 if (!as->has(n)) {
127 if (bs->has(n))
128 return false;
129 as->putNew(n);
130 bs->putNew(n);
131 i++;
132 }
133 }
134 return true;
135 }
136
137 template <class NewKeyFunction>
138 static bool
139 SlowRekey(IntMap *m) {
140 IntMap tmp;
141 tmp.init();
142
143 for (IntMap::Range r = m->all(); !r.empty(); r.popFront()) {
144 if (NewKeyFunction::shouldBeRemoved(r.front().key()))
145 continue;
146 uint32_t hi = NewKeyFunction::rekey(r.front().key());
147 if (tmp.has(hi))
148 return false;
149 tmp.putNew(hi, r.front().value());
150 }
151
152 m->clear();
153 for (IntMap::Range r = tmp.all(); !r.empty(); r.popFront()) {
154 m->putNew(r.front().key(), r.front().value());
155 }
156
157 return true;
158 }
159
160 template <class NewKeyFunction>
161 static bool
162 SlowRekey(IntSet *s) {
163 IntSet tmp;
164 tmp.init();
165
166 for (IntSet::Range r = s->all(); !r.empty(); r.popFront()) {
167 if (NewKeyFunction::shouldBeRemoved(r.front()))
168 continue;
169 uint32_t hi = NewKeyFunction::rekey(r.front());
170 if (tmp.has(hi))
171 return false;
172 tmp.putNew(hi);
173 }
174
175 s->clear();
176 for (IntSet::Range r = tmp.all(); !r.empty(); r.popFront()) {
177 s->putNew(r.front());
178 }
179
180 return true;
181 }
182
183 BEGIN_TEST(testHashRekeyManual)
184 {
185 IntMap am, bm;
186 am.init();
187 bm.init();
188 for (size_t i = 0; i < TestIterations; ++i) {
189 #ifdef FUZZ
190 fprintf(stderr, "map1: %lu\n", i);
191 #endif
192 CHECK(AddLowKeys(&am, &bm, i));
193 CHECK(MapsAreEqual(am, bm));
194
195 for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
196 uint32_t tmp = LowToHigh::rekey(e.front().key());
197 if (tmp != e.front().key())
198 e.rekeyFront(tmp);
199 }
200 CHECK(SlowRekey<LowToHigh>(&bm));
201
202 CHECK(MapsAreEqual(am, bm));
203 am.clear();
204 bm.clear();
205 }
206
207 IntSet as, bs;
208 as.init();
209 bs.init();
210 for (size_t i = 0; i < TestIterations; ++i) {
211 #ifdef FUZZ
212 fprintf(stderr, "set1: %lu\n", i);
213 #endif
214 CHECK(AddLowKeys(&as, &bs, i));
215 CHECK(SetsAreEqual(as, bs));
216
217 for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
218 uint32_t tmp = LowToHigh::rekey(e.front());
219 if (tmp != e.front())
220 e.rekeyFront(tmp);
221 }
222 CHECK(SlowRekey<LowToHigh>(&bs));
223
224 CHECK(SetsAreEqual(as, bs));
225 as.clear();
226 bs.clear();
227 }
228
229 return true;
230 }
231 END_TEST(testHashRekeyManual)
232
233 BEGIN_TEST(testHashRekeyManualRemoval)
234 {
235 IntMap am, bm;
236 am.init();
237 bm.init();
238 for (size_t i = 0; i < TestIterations; ++i) {
239 #ifdef FUZZ
240 fprintf(stderr, "map2: %lu\n", i);
241 #endif
242 CHECK(AddLowKeys(&am, &bm, i));
243 CHECK(MapsAreEqual(am, bm));
244
245 for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
246 if (LowToHighWithRemoval::shouldBeRemoved(e.front().key())) {
247 e.removeFront();
248 } else {
249 uint32_t tmp = LowToHighWithRemoval::rekey(e.front().key());
250 if (tmp != e.front().key())
251 e.rekeyFront(tmp);
252 }
253 }
254 CHECK(SlowRekey<LowToHighWithRemoval>(&bm));
255
256 CHECK(MapsAreEqual(am, bm));
257 am.clear();
258 bm.clear();
259 }
260
261 IntSet as, bs;
262 as.init();
263 bs.init();
264 for (size_t i = 0; i < TestIterations; ++i) {
265 #ifdef FUZZ
266 fprintf(stderr, "set1: %lu\n", i);
267 #endif
268 CHECK(AddLowKeys(&as, &bs, i));
269 CHECK(SetsAreEqual(as, bs));
270
271 for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
272 if (LowToHighWithRemoval::shouldBeRemoved(e.front())) {
273 e.removeFront();
274 } else {
275 uint32_t tmp = LowToHighWithRemoval::rekey(e.front());
276 if (tmp != e.front())
277 e.rekeyFront(tmp);
278 }
279 }
280 CHECK(SlowRekey<LowToHighWithRemoval>(&bs));
281
282 CHECK(SetsAreEqual(as, bs));
283 as.clear();
284 bs.clear();
285 }
286
287 return true;
288 }
289 END_TEST(testHashRekeyManualRemoval)

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial