Line data Source code
1 : // Copyright 2017 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 : #include <utility>
5 : #include "src/v8.h"
6 :
7 : #include "src/objects-inl.h"
8 : #include "test/cctest/cctest.h"
9 :
10 : namespace v8 {
11 : namespace internal {
12 : namespace test_orderedhashtable {
13 :
14 : static Isolate* GetIsolateFrom(LocalContext* context) {
15 72 : return reinterpret_cast<Isolate*>((*context)->GetIsolate());
16 : }
17 :
18 30 : void CopyHashCode(Handle<JSReceiver> from, Handle<JSReceiver> to) {
19 30 : int hash = Smi::ToInt(from->GetHash());
20 30 : to->SetIdentityHash(hash);
21 30 : }
22 :
23 0 : void Verify(Handle<HeapObject> obj) {
24 : #if VERIFY_HEAP
25 : obj->ObjectVerify();
26 : #endif
27 0 : }
28 :
29 23724 : TEST(SmallOrderedHashSetInsertion) {
30 6 : LocalContext context;
31 : Isolate* isolate = GetIsolateFrom(&context);
32 : Factory* factory = isolate->factory();
33 : HandleScope scope(isolate);
34 :
35 6 : Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
36 : Verify(set);
37 6 : CHECK_EQ(2, set->NumberOfBuckets());
38 6 : CHECK_EQ(0, set->NumberOfElements());
39 :
40 : // Add a new key.
41 : Handle<Smi> key1(Smi::FromInt(1), isolate);
42 6 : CHECK(!set->HasKey(isolate, key1));
43 6 : set = SmallOrderedHashSet::Add(set, key1);
44 : Verify(set);
45 6 : CHECK_EQ(2, set->NumberOfBuckets());
46 6 : CHECK_EQ(1, set->NumberOfElements());
47 6 : CHECK(set->HasKey(isolate, key1));
48 :
49 : // Add existing key.
50 6 : set = SmallOrderedHashSet::Add(set, key1);
51 : Verify(set);
52 6 : CHECK_EQ(2, set->NumberOfBuckets());
53 6 : CHECK_EQ(1, set->NumberOfElements());
54 6 : CHECK(set->HasKey(isolate, key1));
55 :
56 6 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
57 6 : CHECK(!set->HasKey(isolate, key2));
58 6 : set = SmallOrderedHashSet::Add(set, key2);
59 : Verify(set);
60 6 : CHECK_EQ(2, set->NumberOfBuckets());
61 6 : CHECK_EQ(2, set->NumberOfElements());
62 6 : CHECK(set->HasKey(isolate, key1));
63 6 : CHECK(set->HasKey(isolate, key2));
64 :
65 6 : set = SmallOrderedHashSet::Add(set, key2);
66 : Verify(set);
67 6 : CHECK_EQ(2, set->NumberOfBuckets());
68 6 : CHECK_EQ(2, set->NumberOfElements());
69 6 : CHECK(set->HasKey(isolate, key1));
70 6 : CHECK(set->HasKey(isolate, key2));
71 :
72 6 : Handle<Symbol> key3 = factory->NewSymbol();
73 6 : CHECK(!set->HasKey(isolate, key3));
74 6 : set = SmallOrderedHashSet::Add(set, key3);
75 : Verify(set);
76 6 : CHECK_EQ(2, set->NumberOfBuckets());
77 6 : CHECK_EQ(3, set->NumberOfElements());
78 6 : CHECK(set->HasKey(isolate, key1));
79 6 : CHECK(set->HasKey(isolate, key2));
80 6 : CHECK(set->HasKey(isolate, key3));
81 :
82 6 : set = SmallOrderedHashSet::Add(set, key3);
83 : Verify(set);
84 6 : CHECK_EQ(2, set->NumberOfBuckets());
85 6 : CHECK_EQ(3, set->NumberOfElements());
86 6 : CHECK(set->HasKey(isolate, key1));
87 6 : CHECK(set->HasKey(isolate, key2));
88 6 : CHECK(set->HasKey(isolate, key3));
89 :
90 : Handle<Object> key4 = factory->NewHeapNumber(42.0);
91 6 : CHECK(!set->HasKey(isolate, key4));
92 6 : set = SmallOrderedHashSet::Add(set, key4);
93 : Verify(set);
94 6 : CHECK_EQ(2, set->NumberOfBuckets());
95 6 : CHECK_EQ(4, set->NumberOfElements());
96 6 : CHECK(set->HasKey(isolate, key1));
97 6 : CHECK(set->HasKey(isolate, key2));
98 6 : CHECK(set->HasKey(isolate, key3));
99 6 : CHECK(set->HasKey(isolate, key4));
100 :
101 6 : set = SmallOrderedHashSet::Add(set, key4);
102 : Verify(set);
103 6 : CHECK_EQ(2, set->NumberOfBuckets());
104 6 : CHECK_EQ(4, set->NumberOfElements());
105 6 : CHECK(set->HasKey(isolate, key1));
106 6 : CHECK(set->HasKey(isolate, key2));
107 6 : CHECK(set->HasKey(isolate, key3));
108 12 : CHECK(set->HasKey(isolate, key4));
109 6 : }
110 :
111 23724 : TEST(SmallOrderedHashMapInsertion) {
112 6 : LocalContext context;
113 : Isolate* isolate = GetIsolateFrom(&context);
114 : Factory* factory = isolate->factory();
115 : HandleScope scope(isolate);
116 :
117 6 : Handle<SmallOrderedHashMap> map = factory->NewSmallOrderedHashMap();
118 : Verify(map);
119 6 : CHECK_EQ(2, map->NumberOfBuckets());
120 6 : CHECK_EQ(0, map->NumberOfElements());
121 :
122 : // Add a new key.
123 : Handle<Smi> key1(Smi::FromInt(1), isolate);
124 : Handle<Smi> value1(Smi::FromInt(1), isolate);
125 6 : CHECK(!map->HasKey(isolate, key1));
126 6 : map = SmallOrderedHashMap::Add(map, key1, value1);
127 : Verify(map);
128 6 : CHECK_EQ(2, map->NumberOfBuckets());
129 6 : CHECK_EQ(1, map->NumberOfElements());
130 6 : CHECK(map->HasKey(isolate, key1));
131 :
132 : // Add existing key.
133 6 : map = SmallOrderedHashMap::Add(map, key1, value1);
134 : Verify(map);
135 6 : CHECK_EQ(2, map->NumberOfBuckets());
136 6 : CHECK_EQ(1, map->NumberOfElements());
137 6 : CHECK(map->HasKey(isolate, key1));
138 :
139 6 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
140 6 : Handle<String> value = factory->NewStringFromAsciiChecked("foo");
141 6 : CHECK(!map->HasKey(isolate, key2));
142 6 : map = SmallOrderedHashMap::Add(map, key2, value);
143 : Verify(map);
144 6 : CHECK_EQ(2, map->NumberOfBuckets());
145 6 : CHECK_EQ(2, map->NumberOfElements());
146 6 : CHECK(map->HasKey(isolate, key1));
147 6 : CHECK(map->HasKey(isolate, key2));
148 :
149 6 : map = SmallOrderedHashMap::Add(map, key2, value);
150 : Verify(map);
151 6 : CHECK_EQ(2, map->NumberOfBuckets());
152 6 : CHECK_EQ(2, map->NumberOfElements());
153 6 : CHECK(map->HasKey(isolate, key1));
154 6 : CHECK(map->HasKey(isolate, key2));
155 :
156 6 : Handle<Symbol> key3 = factory->NewSymbol();
157 6 : CHECK(!map->HasKey(isolate, key3));
158 6 : map = SmallOrderedHashMap::Add(map, key3, value);
159 : Verify(map);
160 6 : CHECK_EQ(2, map->NumberOfBuckets());
161 6 : CHECK_EQ(3, map->NumberOfElements());
162 6 : CHECK(map->HasKey(isolate, key1));
163 6 : CHECK(map->HasKey(isolate, key2));
164 6 : CHECK(map->HasKey(isolate, key3));
165 :
166 6 : map = SmallOrderedHashMap::Add(map, key3, value);
167 : Verify(map);
168 6 : CHECK_EQ(2, map->NumberOfBuckets());
169 6 : CHECK_EQ(3, map->NumberOfElements());
170 6 : CHECK(map->HasKey(isolate, key1));
171 6 : CHECK(map->HasKey(isolate, key2));
172 6 : CHECK(map->HasKey(isolate, key3));
173 :
174 : Handle<Object> key4 = factory->NewHeapNumber(42.0);
175 6 : CHECK(!map->HasKey(isolate, key4));
176 6 : map = SmallOrderedHashMap::Add(map, key4, value);
177 : Verify(map);
178 6 : CHECK_EQ(2, map->NumberOfBuckets());
179 6 : CHECK_EQ(4, map->NumberOfElements());
180 6 : CHECK(map->HasKey(isolate, key1));
181 6 : CHECK(map->HasKey(isolate, key2));
182 6 : CHECK(map->HasKey(isolate, key3));
183 6 : CHECK(map->HasKey(isolate, key4));
184 :
185 6 : map = SmallOrderedHashMap::Add(map, key4, value);
186 : Verify(map);
187 6 : CHECK_EQ(2, map->NumberOfBuckets());
188 6 : CHECK_EQ(4, map->NumberOfElements());
189 6 : CHECK(map->HasKey(isolate, key1));
190 6 : CHECK(map->HasKey(isolate, key2));
191 6 : CHECK(map->HasKey(isolate, key3));
192 12 : CHECK(map->HasKey(isolate, key4));
193 6 : }
194 :
195 23724 : TEST(SmallOrderedHashSetDuplicateHashCode) {
196 6 : LocalContext context;
197 : Isolate* isolate = GetIsolateFrom(&context);
198 : Factory* factory = isolate->factory();
199 : HandleScope scope(isolate);
200 :
201 6 : Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
202 6 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
203 6 : set = SmallOrderedHashSet::Add(set, key1);
204 : Verify(set);
205 6 : CHECK_EQ(2, set->NumberOfBuckets());
206 6 : CHECK_EQ(1, set->NumberOfElements());
207 6 : CHECK(set->HasKey(isolate, key1));
208 :
209 6 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
210 6 : CopyHashCode(key1, key2);
211 :
212 6 : set = SmallOrderedHashSet::Add(set, key2);
213 : Verify(set);
214 6 : CHECK_EQ(2, set->NumberOfBuckets());
215 6 : CHECK_EQ(2, set->NumberOfElements());
216 6 : CHECK(set->HasKey(isolate, key1));
217 12 : CHECK(set->HasKey(isolate, key2));
218 6 : }
219 :
220 23724 : TEST(SmallOrderedHashMapDuplicateHashCode) {
221 6 : LocalContext context;
222 : Isolate* isolate = GetIsolateFrom(&context);
223 : Factory* factory = isolate->factory();
224 : HandleScope scope(isolate);
225 :
226 6 : Handle<SmallOrderedHashMap> map = factory->NewSmallOrderedHashMap();
227 6 : Handle<JSObject> value = factory->NewJSObjectWithNullProto();
228 6 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
229 6 : map = SmallOrderedHashMap::Add(map, key1, value);
230 : Verify(map);
231 6 : CHECK_EQ(2, map->NumberOfBuckets());
232 6 : CHECK_EQ(1, map->NumberOfElements());
233 6 : CHECK(map->HasKey(isolate, key1));
234 :
235 6 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
236 6 : CopyHashCode(key1, key2);
237 :
238 6 : CHECK(!key1->SameValue(*key2));
239 6 : Object* hash1 = key1->GetHash();
240 6 : Object* hash2 = key2->GetHash();
241 6 : CHECK_EQ(hash1, hash2);
242 :
243 6 : map = SmallOrderedHashMap::Add(map, key2, value);
244 : Verify(map);
245 6 : CHECK_EQ(2, map->NumberOfBuckets());
246 6 : CHECK_EQ(2, map->NumberOfElements());
247 6 : CHECK(map->HasKey(isolate, key1));
248 12 : CHECK(map->HasKey(isolate, key2));
249 6 : }
250 :
251 23724 : TEST(SmallOrderedHashSetGrow) {
252 6 : LocalContext context;
253 : Isolate* isolate = GetIsolateFrom(&context);
254 : Factory* factory = isolate->factory();
255 : HandleScope scope(isolate);
256 :
257 6 : Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
258 : std::vector<Handle<Object>> keys;
259 1530 : for (int i = 0; i < 254; i++) {
260 : Handle<Smi> key(Smi::FromInt(i), isolate);
261 1524 : keys.push_back(key);
262 : }
263 :
264 24 : for (size_t i = 0; i < 4; i++) {
265 48 : set = SmallOrderedHashSet::Add(set, keys[i]);
266 : Verify(set);
267 : }
268 :
269 24 : for (size_t i = 0; i < 4; i++) {
270 48 : CHECK(set->HasKey(isolate, keys[i]));
271 : Verify(set);
272 : }
273 :
274 6 : CHECK_EQ(4, set->NumberOfElements());
275 6 : CHECK_EQ(2, set->NumberOfBuckets());
276 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
277 : Verify(set);
278 :
279 24 : for (size_t i = 4; i < 8; i++) {
280 48 : set = SmallOrderedHashSet::Add(set, keys[i]);
281 : Verify(set);
282 : }
283 :
284 48 : for (size_t i = 0; i < 8; i++) {
285 96 : CHECK(set->HasKey(isolate, keys[i]));
286 : Verify(set);
287 : }
288 :
289 6 : CHECK_EQ(8, set->NumberOfElements());
290 6 : CHECK_EQ(4, set->NumberOfBuckets());
291 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
292 : Verify(set);
293 :
294 48 : for (size_t i = 8; i < 16; i++) {
295 96 : set = SmallOrderedHashSet::Add(set, keys[i]);
296 : Verify(set);
297 : }
298 :
299 96 : for (size_t i = 0; i < 16; i++) {
300 192 : CHECK(set->HasKey(isolate, keys[i]));
301 : Verify(set);
302 : }
303 :
304 6 : CHECK_EQ(16, set->NumberOfElements());
305 6 : CHECK_EQ(8, set->NumberOfBuckets());
306 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
307 : Verify(set);
308 :
309 96 : for (size_t i = 16; i < 32; i++) {
310 192 : set = SmallOrderedHashSet::Add(set, keys[i]);
311 : Verify(set);
312 : }
313 :
314 192 : for (size_t i = 0; i < 32; i++) {
315 384 : CHECK(set->HasKey(isolate, keys[i]));
316 : Verify(set);
317 : }
318 :
319 6 : CHECK_EQ(32, set->NumberOfElements());
320 6 : CHECK_EQ(16, set->NumberOfBuckets());
321 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
322 : Verify(set);
323 :
324 192 : for (size_t i = 32; i < 64; i++) {
325 384 : set = SmallOrderedHashSet::Add(set, keys[i]);
326 : Verify(set);
327 : }
328 :
329 384 : for (size_t i = 0; i < 64; i++) {
330 768 : CHECK(set->HasKey(isolate, keys[i]));
331 : Verify(set);
332 : }
333 :
334 6 : CHECK_EQ(64, set->NumberOfElements());
335 6 : CHECK_EQ(32, set->NumberOfBuckets());
336 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
337 : Verify(set);
338 :
339 384 : for (size_t i = 64; i < 128; i++) {
340 768 : set = SmallOrderedHashSet::Add(set, keys[i]);
341 : Verify(set);
342 : }
343 :
344 768 : for (size_t i = 0; i < 128; i++) {
345 1536 : CHECK(set->HasKey(isolate, keys[i]));
346 : Verify(set);
347 : }
348 :
349 6 : CHECK_EQ(128, set->NumberOfElements());
350 6 : CHECK_EQ(64, set->NumberOfBuckets());
351 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
352 : Verify(set);
353 :
354 756 : for (size_t i = 128; i < 254; i++) {
355 1512 : set = SmallOrderedHashSet::Add(set, keys[i]);
356 : Verify(set);
357 : }
358 :
359 1524 : for (size_t i = 0; i < 254; i++) {
360 3048 : CHECK(set->HasKey(isolate, keys[i]));
361 : Verify(set);
362 : }
363 :
364 6 : CHECK_EQ(254, set->NumberOfElements());
365 6 : CHECK_EQ(127, set->NumberOfBuckets());
366 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
367 6 : Verify(set);
368 6 : }
369 :
370 23724 : TEST(SmallOrderedHashMapGrow) {
371 6 : LocalContext context;
372 : Isolate* isolate = GetIsolateFrom(&context);
373 : Factory* factory = isolate->factory();
374 : HandleScope scope(isolate);
375 :
376 6 : Handle<SmallOrderedHashMap> map = factory->NewSmallOrderedHashMap();
377 : std::vector<Handle<Object>> keys;
378 1530 : for (int i = 0; i < 254; i++) {
379 : Handle<Smi> key(Smi::FromInt(i), isolate);
380 1524 : keys.push_back(key);
381 : }
382 :
383 24 : for (size_t i = 0; i < 4; i++) {
384 48 : map = SmallOrderedHashMap::Add(map, keys[i], keys[i]);
385 : Verify(map);
386 : }
387 :
388 24 : for (size_t i = 0; i < 4; i++) {
389 48 : CHECK(map->HasKey(isolate, keys[i]));
390 : Verify(map);
391 : }
392 :
393 6 : CHECK_EQ(4, map->NumberOfElements());
394 6 : CHECK_EQ(2, map->NumberOfBuckets());
395 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
396 : Verify(map);
397 :
398 24 : for (size_t i = 4; i < 8; i++) {
399 48 : map = SmallOrderedHashMap::Add(map, keys[i], keys[i]);
400 : Verify(map);
401 : }
402 :
403 48 : for (size_t i = 0; i < 8; i++) {
404 96 : CHECK(map->HasKey(isolate, keys[i]));
405 : Verify(map);
406 : }
407 :
408 6 : CHECK_EQ(8, map->NumberOfElements());
409 6 : CHECK_EQ(4, map->NumberOfBuckets());
410 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
411 : Verify(map);
412 :
413 48 : for (size_t i = 8; i < 16; i++) {
414 96 : map = SmallOrderedHashMap::Add(map, keys[i], keys[i]);
415 : Verify(map);
416 : }
417 :
418 96 : for (size_t i = 0; i < 16; i++) {
419 192 : CHECK(map->HasKey(isolate, keys[i]));
420 : Verify(map);
421 : }
422 :
423 6 : CHECK_EQ(16, map->NumberOfElements());
424 6 : CHECK_EQ(8, map->NumberOfBuckets());
425 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
426 : Verify(map);
427 :
428 96 : for (size_t i = 16; i < 32; i++) {
429 192 : map = SmallOrderedHashMap::Add(map, keys[i], keys[i]);
430 : Verify(map);
431 : }
432 :
433 192 : for (size_t i = 0; i < 32; i++) {
434 384 : CHECK(map->HasKey(isolate, keys[i]));
435 : Verify(map);
436 : }
437 :
438 6 : CHECK_EQ(32, map->NumberOfElements());
439 6 : CHECK_EQ(16, map->NumberOfBuckets());
440 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
441 : Verify(map);
442 :
443 192 : for (size_t i = 32; i < 64; i++) {
444 384 : map = SmallOrderedHashMap::Add(map, keys[i], keys[i]);
445 : Verify(map);
446 : }
447 :
448 384 : for (size_t i = 0; i < 64; i++) {
449 768 : CHECK(map->HasKey(isolate, keys[i]));
450 : Verify(map);
451 : }
452 :
453 6 : CHECK_EQ(64, map->NumberOfElements());
454 6 : CHECK_EQ(32, map->NumberOfBuckets());
455 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
456 : Verify(map);
457 :
458 384 : for (size_t i = 64; i < 128; i++) {
459 768 : map = SmallOrderedHashMap::Add(map, keys[i], keys[i]);
460 : Verify(map);
461 : }
462 :
463 768 : for (size_t i = 0; i < 128; i++) {
464 1536 : CHECK(map->HasKey(isolate, keys[i]));
465 : Verify(map);
466 : }
467 :
468 6 : CHECK_EQ(128, map->NumberOfElements());
469 6 : CHECK_EQ(64, map->NumberOfBuckets());
470 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
471 : Verify(map);
472 :
473 756 : for (size_t i = 128; i < 254; i++) {
474 1512 : map = SmallOrderedHashMap::Add(map, keys[i], keys[i]);
475 : Verify(map);
476 : }
477 :
478 1524 : for (size_t i = 0; i < 254; i++) {
479 3048 : CHECK(map->HasKey(isolate, keys[i]));
480 : Verify(map);
481 : }
482 :
483 6 : CHECK_EQ(254, map->NumberOfElements());
484 6 : CHECK_EQ(127, map->NumberOfBuckets());
485 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
486 6 : Verify(map);
487 6 : }
488 :
489 23724 : TEST(OrderedHashTableInsertion) {
490 6 : LocalContext context;
491 : Isolate* isolate = GetIsolateFrom(&context);
492 : Factory* factory = isolate->factory();
493 : HandleScope scope(isolate);
494 :
495 6 : Handle<OrderedHashMap> map = factory->NewOrderedHashMap();
496 : Verify(map);
497 6 : CHECK_EQ(2, map->NumberOfBuckets());
498 6 : CHECK_EQ(0, map->NumberOfElements());
499 :
500 : // Add a new key.
501 : Handle<Smi> key1(Smi::FromInt(1), isolate);
502 : Handle<Smi> value1(Smi::FromInt(1), isolate);
503 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
504 6 : map = OrderedHashMap::Add(map, key1, value1);
505 : Verify(map);
506 6 : CHECK_EQ(2, map->NumberOfBuckets());
507 6 : CHECK_EQ(1, map->NumberOfElements());
508 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
509 :
510 : // Add existing key.
511 6 : map = OrderedHashMap::Add(map, key1, value1);
512 : Verify(map);
513 6 : CHECK_EQ(2, map->NumberOfBuckets());
514 6 : CHECK_EQ(1, map->NumberOfElements());
515 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
516 :
517 6 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
518 6 : Handle<String> value = factory->NewStringFromAsciiChecked("bar");
519 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
520 6 : map = OrderedHashMap::Add(map, key2, value);
521 : Verify(map);
522 6 : CHECK_EQ(2, map->NumberOfBuckets());
523 6 : CHECK_EQ(2, map->NumberOfElements());
524 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
525 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
526 :
527 6 : map = OrderedHashMap::Add(map, key2, value);
528 : Verify(map);
529 6 : CHECK_EQ(2, map->NumberOfBuckets());
530 6 : CHECK_EQ(2, map->NumberOfElements());
531 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
532 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
533 :
534 6 : Handle<Symbol> key3 = factory->NewSymbol();
535 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
536 6 : map = OrderedHashMap::Add(map, key3, value);
537 : Verify(map);
538 6 : CHECK_EQ(2, map->NumberOfBuckets());
539 6 : CHECK_EQ(3, map->NumberOfElements());
540 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
541 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
542 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
543 :
544 6 : map = OrderedHashMap::Add(map, key3, value);
545 : Verify(map);
546 6 : CHECK_EQ(2, map->NumberOfBuckets());
547 6 : CHECK_EQ(3, map->NumberOfElements());
548 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
549 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
550 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
551 :
552 : Handle<Object> key4 = factory->NewHeapNumber(42.0);
553 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key4));
554 6 : map = OrderedHashMap::Add(map, key4, value);
555 : Verify(map);
556 6 : CHECK_EQ(2, map->NumberOfBuckets());
557 6 : CHECK_EQ(4, map->NumberOfElements());
558 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
559 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
560 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
561 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key4));
562 :
563 6 : map = OrderedHashMap::Add(map, key4, value);
564 : Verify(map);
565 6 : CHECK_EQ(2, map->NumberOfBuckets());
566 6 : CHECK_EQ(4, map->NumberOfElements());
567 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
568 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
569 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
570 12 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key4));
571 6 : }
572 :
573 23724 : TEST(OrderedHashMapDuplicateHashCode) {
574 6 : LocalContext context;
575 : Isolate* isolate = GetIsolateFrom(&context);
576 : Factory* factory = isolate->factory();
577 : HandleScope scope(isolate);
578 :
579 6 : Handle<OrderedHashMap> map = factory->NewOrderedHashMap();
580 6 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
581 6 : Handle<JSObject> value = factory->NewJSObjectWithNullProto();
582 6 : map = OrderedHashMap::Add(map, key1, value);
583 : Verify(map);
584 6 : CHECK_EQ(2, map->NumberOfBuckets());
585 6 : CHECK_EQ(1, map->NumberOfElements());
586 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
587 :
588 6 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
589 6 : CopyHashCode(key1, key2);
590 :
591 6 : map = OrderedHashMap::Add(map, key2, value);
592 : Verify(map);
593 6 : CHECK_EQ(2, map->NumberOfBuckets());
594 6 : CHECK_EQ(2, map->NumberOfElements());
595 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
596 12 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
597 6 : }
598 :
599 23724 : TEST(OrderedHashMapDeletion) {
600 6 : LocalContext context;
601 : Isolate* isolate = GetIsolateFrom(&context);
602 : Factory* factory = isolate->factory();
603 : HandleScope scope(isolate);
604 : Handle<Smi> value1(Smi::FromInt(1), isolate);
605 6 : Handle<String> value = factory->NewStringFromAsciiChecked("bar");
606 :
607 6 : Handle<OrderedHashMap> map = factory->NewOrderedHashMap();
608 : Verify(map);
609 6 : CHECK_EQ(2, map->NumberOfBuckets());
610 6 : CHECK_EQ(0, map->NumberOfElements());
611 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
612 :
613 : // Delete from an empty hash table
614 : Handle<Smi> key1(Smi::FromInt(1), isolate);
615 6 : CHECK(!OrderedHashMap::Delete(isolate, *map, *key1));
616 : Verify(map);
617 6 : CHECK_EQ(2, map->NumberOfBuckets());
618 6 : CHECK_EQ(0, map->NumberOfElements());
619 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
620 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
621 :
622 6 : map = OrderedHashMap::Add(map, key1, value1);
623 : Verify(map);
624 6 : CHECK_EQ(2, map->NumberOfBuckets());
625 6 : CHECK_EQ(1, map->NumberOfElements());
626 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
627 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
628 :
629 : // Delete single existing key
630 6 : CHECK(OrderedHashMap::Delete(isolate, *map, *key1));
631 : Verify(map);
632 6 : CHECK_EQ(2, map->NumberOfBuckets());
633 6 : CHECK_EQ(0, map->NumberOfElements());
634 6 : CHECK_EQ(1, map->NumberOfDeletedElements());
635 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
636 :
637 6 : map = OrderedHashMap::Add(map, key1, value1);
638 : Verify(map);
639 6 : CHECK_EQ(2, map->NumberOfBuckets());
640 6 : CHECK_EQ(1, map->NumberOfElements());
641 6 : CHECK_EQ(1, map->NumberOfDeletedElements());
642 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
643 :
644 6 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
645 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
646 6 : map = OrderedHashMap::Add(map, key2, value);
647 : Verify(map);
648 6 : CHECK_EQ(2, map->NumberOfBuckets());
649 6 : CHECK_EQ(2, map->NumberOfElements());
650 6 : CHECK_EQ(1, map->NumberOfDeletedElements());
651 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
652 :
653 6 : Handle<Symbol> key3 = factory->NewSymbol();
654 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
655 6 : map = OrderedHashMap::Add(map, key3, value);
656 : Verify(map);
657 6 : CHECK_EQ(2, map->NumberOfBuckets());
658 6 : CHECK_EQ(3, map->NumberOfElements());
659 6 : CHECK_EQ(1, map->NumberOfDeletedElements());
660 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
661 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
662 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
663 :
664 : // Delete multiple existing keys
665 6 : CHECK(OrderedHashMap::Delete(isolate, *map, *key1));
666 : Verify(map);
667 6 : CHECK_EQ(2, map->NumberOfBuckets());
668 6 : CHECK_EQ(2, map->NumberOfElements());
669 6 : CHECK_EQ(2, map->NumberOfDeletedElements());
670 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
671 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
672 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
673 :
674 6 : CHECK(OrderedHashMap::Delete(isolate, *map, *key2));
675 : Verify(map);
676 6 : CHECK_EQ(2, map->NumberOfBuckets());
677 6 : CHECK_EQ(1, map->NumberOfElements());
678 6 : CHECK_EQ(3, map->NumberOfDeletedElements());
679 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
680 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
681 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
682 :
683 6 : CHECK(OrderedHashMap::Delete(isolate, *map, *key3));
684 : Verify(map);
685 6 : CHECK_EQ(2, map->NumberOfBuckets());
686 6 : CHECK_EQ(0, map->NumberOfElements());
687 6 : CHECK_EQ(4, map->NumberOfDeletedElements());
688 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
689 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
690 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
691 :
692 : // Delete non existent key from non new hash table
693 6 : CHECK(!OrderedHashMap::Delete(isolate, *map, *key3));
694 : Verify(map);
695 6 : CHECK_EQ(2, map->NumberOfBuckets());
696 6 : CHECK_EQ(0, map->NumberOfElements());
697 6 : CHECK_EQ(4, map->NumberOfDeletedElements());
698 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
699 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
700 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
701 :
702 : // Delete non existent key from non empty hash table
703 6 : map = OrderedHashMap::Shrink(map);
704 6 : map = OrderedHashMap::Add(map, key1, value);
705 : Verify(map);
706 6 : CHECK_EQ(2, map->NumberOfBuckets());
707 6 : CHECK_EQ(1, map->NumberOfElements());
708 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
709 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
710 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
711 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
712 6 : CHECK(!OrderedHashMap::Delete(isolate, *map, *key2));
713 : Verify(map);
714 6 : CHECK_EQ(2, map->NumberOfBuckets());
715 6 : CHECK_EQ(1, map->NumberOfElements());
716 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
717 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
718 6 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
719 12 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
720 6 : }
721 :
722 23724 : TEST(OrderedHashMapDuplicateHashCodeDeletion) {
723 6 : LocalContext context;
724 : Isolate* isolate = GetIsolateFrom(&context);
725 : Factory* factory = isolate->factory();
726 : HandleScope scope(isolate);
727 :
728 6 : Handle<OrderedHashMap> map = factory->NewOrderedHashMap();
729 6 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
730 6 : Handle<JSObject> value = factory->NewJSObjectWithNullProto();
731 6 : map = OrderedHashMap::Add(map, key1, value);
732 : Verify(map);
733 6 : CHECK_EQ(2, map->NumberOfBuckets());
734 6 : CHECK_EQ(1, map->NumberOfElements());
735 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
736 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
737 :
738 6 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
739 6 : CopyHashCode(key1, key2);
740 :
741 : // We shouldn't be able to delete the key!
742 6 : CHECK(!OrderedHashMap::Delete(isolate, *map, *key2));
743 : Verify(map);
744 6 : CHECK_EQ(2, map->NumberOfBuckets());
745 6 : CHECK_EQ(1, map->NumberOfElements());
746 6 : CHECK_EQ(0, map->NumberOfDeletedElements());
747 6 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
748 12 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
749 6 : }
750 :
751 23724 : TEST(OrderedHashSetDeletion) {
752 6 : LocalContext context;
753 : Isolate* isolate = GetIsolateFrom(&context);
754 : Factory* factory = isolate->factory();
755 : HandleScope scope(isolate);
756 :
757 6 : Handle<OrderedHashSet> set = factory->NewOrderedHashSet();
758 : Verify(set);
759 6 : CHECK_EQ(2, set->NumberOfBuckets());
760 6 : CHECK_EQ(0, set->NumberOfElements());
761 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
762 :
763 : // Delete from an empty hash table
764 : Handle<Smi> key1(Smi::FromInt(1), isolate);
765 6 : CHECK(!OrderedHashSet::Delete(isolate, *set, *key1));
766 : Verify(set);
767 6 : CHECK_EQ(2, set->NumberOfBuckets());
768 6 : CHECK_EQ(0, set->NumberOfElements());
769 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
770 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
771 :
772 6 : set = OrderedHashSet::Add(set, key1);
773 : Verify(set);
774 6 : CHECK_EQ(2, set->NumberOfBuckets());
775 6 : CHECK_EQ(1, set->NumberOfElements());
776 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
777 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
778 :
779 : // Delete single existing key
780 6 : CHECK(OrderedHashSet::Delete(isolate, *set, *key1));
781 : Verify(set);
782 6 : CHECK_EQ(2, set->NumberOfBuckets());
783 6 : CHECK_EQ(0, set->NumberOfElements());
784 6 : CHECK_EQ(1, set->NumberOfDeletedElements());
785 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
786 :
787 6 : set = OrderedHashSet::Add(set, key1);
788 : Verify(set);
789 6 : CHECK_EQ(2, set->NumberOfBuckets());
790 6 : CHECK_EQ(1, set->NumberOfElements());
791 6 : CHECK_EQ(1, set->NumberOfDeletedElements());
792 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
793 :
794 6 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
795 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
796 6 : set = OrderedHashSet::Add(set, key2);
797 : Verify(set);
798 6 : CHECK_EQ(2, set->NumberOfBuckets());
799 6 : CHECK_EQ(2, set->NumberOfElements());
800 6 : CHECK_EQ(1, set->NumberOfDeletedElements());
801 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key2));
802 :
803 6 : Handle<Symbol> key3 = factory->NewSymbol();
804 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
805 6 : set = OrderedHashSet::Add(set, key3);
806 : Verify(set);
807 6 : CHECK_EQ(2, set->NumberOfBuckets());
808 6 : CHECK_EQ(3, set->NumberOfElements());
809 6 : CHECK_EQ(1, set->NumberOfDeletedElements());
810 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
811 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key2));
812 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key3));
813 :
814 : // Delete multiple existing keys
815 6 : CHECK(OrderedHashSet::Delete(isolate, *set, *key1));
816 : Verify(set);
817 6 : CHECK_EQ(2, set->NumberOfBuckets());
818 6 : CHECK_EQ(2, set->NumberOfElements());
819 6 : CHECK_EQ(2, set->NumberOfDeletedElements());
820 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
821 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key2));
822 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key3));
823 :
824 6 : CHECK(OrderedHashSet::Delete(isolate, *set, *key2));
825 : Verify(set);
826 6 : CHECK_EQ(2, set->NumberOfBuckets());
827 6 : CHECK_EQ(1, set->NumberOfElements());
828 6 : CHECK_EQ(3, set->NumberOfDeletedElements());
829 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
830 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
831 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key3));
832 :
833 6 : CHECK(OrderedHashSet::Delete(isolate, *set, *key3));
834 : Verify(set);
835 6 : CHECK_EQ(2, set->NumberOfBuckets());
836 6 : CHECK_EQ(0, set->NumberOfElements());
837 6 : CHECK_EQ(4, set->NumberOfDeletedElements());
838 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
839 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
840 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
841 :
842 : // Delete non existent key from non new hash table
843 6 : CHECK(!OrderedHashSet::Delete(isolate, *set, *key3));
844 : Verify(set);
845 6 : CHECK_EQ(2, set->NumberOfBuckets());
846 6 : CHECK_EQ(0, set->NumberOfElements());
847 6 : CHECK_EQ(4, set->NumberOfDeletedElements());
848 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
849 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
850 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
851 :
852 : // Delete non existent key from non empty hash table
853 6 : set = OrderedHashSet::Shrink(set);
854 6 : set = OrderedHashSet::Add(set, key1);
855 : Verify(set);
856 6 : CHECK_EQ(2, set->NumberOfBuckets());
857 6 : CHECK_EQ(1, set->NumberOfElements());
858 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
859 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
860 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
861 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
862 6 : CHECK(!OrderedHashSet::Delete(isolate, *set, *key2));
863 : Verify(set);
864 6 : CHECK_EQ(2, set->NumberOfBuckets());
865 6 : CHECK_EQ(1, set->NumberOfElements());
866 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
867 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
868 6 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
869 12 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
870 6 : }
871 :
872 23724 : TEST(OrderedHashSetDuplicateHashCodeDeletion) {
873 6 : LocalContext context;
874 : Isolate* isolate = GetIsolateFrom(&context);
875 : Factory* factory = isolate->factory();
876 : HandleScope scope(isolate);
877 :
878 6 : Handle<OrderedHashSet> set = factory->NewOrderedHashSet();
879 6 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
880 6 : set = OrderedHashSet::Add(set, key1);
881 : Verify(set);
882 6 : CHECK_EQ(2, set->NumberOfBuckets());
883 6 : CHECK_EQ(1, set->NumberOfElements());
884 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
885 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
886 :
887 6 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
888 6 : CopyHashCode(key1, key2);
889 :
890 : // We shouldn't be able to delete the key!
891 6 : CHECK(!OrderedHashSet::Delete(isolate, *set, *key2));
892 : Verify(set);
893 6 : CHECK_EQ(2, set->NumberOfBuckets());
894 6 : CHECK_EQ(1, set->NumberOfElements());
895 6 : CHECK_EQ(0, set->NumberOfDeletedElements());
896 6 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
897 12 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
898 6 : }
899 :
900 : } // namespace test_orderedhashtable
901 : } // namespace internal
902 71154 : } // namespace v8
|
