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 "src/objects/ordered-hash-table-inl.h"
9 : #include "test/cctest/cctest.h"
10 :
11 : namespace v8 {
12 : namespace internal {
13 : namespace test_orderedhashtable {
14 :
15 : static Isolate* GetIsolateFrom(LocalContext* context) {
16 170 : return reinterpret_cast<Isolate*>((*context)->GetIsolate());
17 : }
18 :
19 35 : void CopyHashCode(Handle<JSReceiver> from, Handle<JSReceiver> to) {
20 70 : int hash = Smi::ToInt(from->GetHash());
21 35 : to->SetIdentityHash(hash);
22 35 : }
23 :
24 0 : void Verify(Isolate* isolate, Handle<HeapObject> obj) {
25 : #if VERIFY_HEAP
26 : obj->ObjectVerify(isolate);
27 : #endif
28 0 : }
29 :
30 26644 : TEST(SmallOrderedHashSetInsertion) {
31 5 : LocalContext context;
32 : Isolate* isolate = GetIsolateFrom(&context);
33 : Factory* factory = isolate->factory();
34 : HandleScope scope(isolate);
35 :
36 5 : Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
37 : Verify(isolate, set);
38 5 : CHECK_EQ(2, set->NumberOfBuckets());
39 5 : CHECK_EQ(0, set->NumberOfElements());
40 :
41 : // Add a new key.
42 : Handle<Smi> key1(Smi::FromInt(1), isolate);
43 5 : CHECK(!set->HasKey(isolate, key1));
44 10 : set = SmallOrderedHashSet::Add(isolate, set, key1).ToHandleChecked();
45 : Verify(isolate, set);
46 5 : CHECK_EQ(2, set->NumberOfBuckets());
47 5 : CHECK_EQ(1, set->NumberOfElements());
48 5 : CHECK(set->HasKey(isolate, key1));
49 :
50 : // Add existing key.
51 10 : set = SmallOrderedHashSet::Add(isolate, set, key1).ToHandleChecked();
52 : Verify(isolate, set);
53 5 : CHECK_EQ(2, set->NumberOfBuckets());
54 5 : CHECK_EQ(1, set->NumberOfElements());
55 5 : CHECK(set->HasKey(isolate, key1));
56 :
57 5 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
58 5 : CHECK(!set->HasKey(isolate, key2));
59 10 : set = SmallOrderedHashSet::Add(isolate, set, key2).ToHandleChecked();
60 : Verify(isolate, set);
61 5 : CHECK_EQ(2, set->NumberOfBuckets());
62 5 : CHECK_EQ(2, set->NumberOfElements());
63 5 : CHECK(set->HasKey(isolate, key1));
64 : CHECK(set->HasKey(isolate, key2));
65 :
66 10 : set = SmallOrderedHashSet::Add(isolate, set, key2).ToHandleChecked();
67 : Verify(isolate, set);
68 5 : CHECK_EQ(2, set->NumberOfBuckets());
69 5 : CHECK_EQ(2, set->NumberOfElements());
70 5 : CHECK(set->HasKey(isolate, key1));
71 5 : CHECK(set->HasKey(isolate, key2));
72 :
73 5 : Handle<Symbol> key3 = factory->NewSymbol();
74 5 : CHECK(!set->HasKey(isolate, key3));
75 10 : set = SmallOrderedHashSet::Add(isolate, set, key3).ToHandleChecked();
76 : Verify(isolate, set);
77 5 : CHECK_EQ(2, set->NumberOfBuckets());
78 5 : CHECK_EQ(3, set->NumberOfElements());
79 5 : CHECK(set->HasKey(isolate, key1));
80 5 : CHECK(set->HasKey(isolate, key2));
81 5 : CHECK(set->HasKey(isolate, key3));
82 :
83 10 : set = SmallOrderedHashSet::Add(isolate, set, key3).ToHandleChecked();
84 : Verify(isolate, set);
85 5 : CHECK_EQ(2, set->NumberOfBuckets());
86 5 : CHECK_EQ(3, set->NumberOfElements());
87 5 : CHECK(set->HasKey(isolate, key1));
88 5 : CHECK(set->HasKey(isolate, key2));
89 5 : CHECK(set->HasKey(isolate, key3));
90 :
91 5 : Handle<Object> key4 = factory->NewHeapNumber(42.0);
92 5 : CHECK(!set->HasKey(isolate, key4));
93 10 : set = SmallOrderedHashSet::Add(isolate, set, key4).ToHandleChecked();
94 : Verify(isolate, set);
95 5 : CHECK_EQ(2, set->NumberOfBuckets());
96 5 : CHECK_EQ(4, set->NumberOfElements());
97 5 : CHECK(set->HasKey(isolate, key1));
98 5 : CHECK(set->HasKey(isolate, key2));
99 5 : CHECK(set->HasKey(isolate, key3));
100 5 : CHECK(set->HasKey(isolate, key4));
101 :
102 10 : set = SmallOrderedHashSet::Add(isolate, set, key4).ToHandleChecked();
103 : Verify(isolate, set);
104 5 : CHECK_EQ(2, set->NumberOfBuckets());
105 5 : CHECK_EQ(4, set->NumberOfElements());
106 5 : CHECK(set->HasKey(isolate, key1));
107 5 : CHECK(set->HasKey(isolate, key2));
108 5 : CHECK(set->HasKey(isolate, key3));
109 5 : CHECK(set->HasKey(isolate, key4));
110 5 : }
111 :
112 26644 : TEST(SmallOrderedHashMapInsertion) {
113 5 : LocalContext context;
114 : Isolate* isolate = GetIsolateFrom(&context);
115 : Factory* factory = isolate->factory();
116 : HandleScope scope(isolate);
117 :
118 5 : Handle<SmallOrderedHashMap> map = factory->NewSmallOrderedHashMap();
119 : Verify(isolate, map);
120 5 : CHECK_EQ(2, map->NumberOfBuckets());
121 5 : CHECK_EQ(0, map->NumberOfElements());
122 :
123 : // Add a new key.
124 : Handle<Smi> key1(Smi::FromInt(1), isolate);
125 : Handle<Smi> value1(Smi::FromInt(1), isolate);
126 5 : CHECK(!map->HasKey(isolate, key1));
127 10 : map = SmallOrderedHashMap::Add(isolate, map, key1, value1).ToHandleChecked();
128 : Verify(isolate, map);
129 5 : CHECK_EQ(2, map->NumberOfBuckets());
130 5 : CHECK_EQ(1, map->NumberOfElements());
131 5 : CHECK(map->HasKey(isolate, key1));
132 :
133 : // Add existing key.
134 10 : map = SmallOrderedHashMap::Add(isolate, map, key1, value1).ToHandleChecked();
135 : Verify(isolate, map);
136 5 : CHECK_EQ(2, map->NumberOfBuckets());
137 5 : CHECK_EQ(1, map->NumberOfElements());
138 5 : CHECK(map->HasKey(isolate, key1));
139 :
140 5 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
141 5 : Handle<String> value = factory->NewStringFromAsciiChecked("foo");
142 5 : CHECK(!map->HasKey(isolate, key2));
143 10 : map = SmallOrderedHashMap::Add(isolate, map, key2, value).ToHandleChecked();
144 : Verify(isolate, map);
145 5 : CHECK_EQ(2, map->NumberOfBuckets());
146 5 : CHECK_EQ(2, map->NumberOfElements());
147 5 : CHECK(map->HasKey(isolate, key1));
148 5 : CHECK(map->HasKey(isolate, key2));
149 :
150 10 : map = SmallOrderedHashMap::Add(isolate, map, key2, value).ToHandleChecked();
151 : Verify(isolate, map);
152 5 : CHECK_EQ(2, map->NumberOfBuckets());
153 5 : CHECK_EQ(2, map->NumberOfElements());
154 5 : CHECK(map->HasKey(isolate, key1));
155 5 : CHECK(map->HasKey(isolate, key2));
156 :
157 5 : Handle<Symbol> key3 = factory->NewSymbol();
158 5 : CHECK(!map->HasKey(isolate, key3));
159 10 : map = SmallOrderedHashMap::Add(isolate, map, key3, value).ToHandleChecked();
160 : Verify(isolate, map);
161 5 : CHECK_EQ(2, map->NumberOfBuckets());
162 5 : CHECK_EQ(3, map->NumberOfElements());
163 5 : CHECK(map->HasKey(isolate, key1));
164 5 : CHECK(map->HasKey(isolate, key2));
165 5 : CHECK(map->HasKey(isolate, key3));
166 :
167 10 : map = SmallOrderedHashMap::Add(isolate, map, key3, value).ToHandleChecked();
168 : Verify(isolate, map);
169 5 : CHECK_EQ(2, map->NumberOfBuckets());
170 5 : CHECK_EQ(3, map->NumberOfElements());
171 5 : CHECK(map->HasKey(isolate, key1));
172 5 : CHECK(map->HasKey(isolate, key2));
173 5 : CHECK(map->HasKey(isolate, key3));
174 :
175 5 : Handle<Object> key4 = factory->NewHeapNumber(42.0);
176 5 : CHECK(!map->HasKey(isolate, key4));
177 10 : map = SmallOrderedHashMap::Add(isolate, map, key4, value).ToHandleChecked();
178 : Verify(isolate, map);
179 5 : CHECK_EQ(2, map->NumberOfBuckets());
180 5 : CHECK_EQ(4, map->NumberOfElements());
181 5 : CHECK(map->HasKey(isolate, key1));
182 5 : CHECK(map->HasKey(isolate, key2));
183 5 : CHECK(map->HasKey(isolate, key3));
184 5 : CHECK(map->HasKey(isolate, key4));
185 :
186 10 : map = SmallOrderedHashMap::Add(isolate, map, key4, value).ToHandleChecked();
187 : Verify(isolate, map);
188 5 : CHECK_EQ(2, map->NumberOfBuckets());
189 5 : CHECK_EQ(4, map->NumberOfElements());
190 5 : CHECK(map->HasKey(isolate, key1));
191 5 : CHECK(map->HasKey(isolate, key2));
192 5 : CHECK(map->HasKey(isolate, key3));
193 5 : CHECK(map->HasKey(isolate, key4));
194 5 : }
195 :
196 26644 : TEST(SmallOrderedHashSetDuplicateHashCode) {
197 5 : LocalContext context;
198 : Isolate* isolate = GetIsolateFrom(&context);
199 : Factory* factory = isolate->factory();
200 : HandleScope scope(isolate);
201 :
202 5 : Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
203 5 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
204 10 : set = SmallOrderedHashSet::Add(isolate, set, key1).ToHandleChecked();
205 : Verify(isolate, set);
206 5 : CHECK_EQ(2, set->NumberOfBuckets());
207 5 : CHECK_EQ(1, set->NumberOfElements());
208 5 : CHECK(set->HasKey(isolate, key1));
209 :
210 5 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
211 5 : CopyHashCode(key1, key2);
212 :
213 10 : set = SmallOrderedHashSet::Add(isolate, set, key2).ToHandleChecked();
214 : Verify(isolate, set);
215 5 : CHECK_EQ(2, set->NumberOfBuckets());
216 5 : CHECK_EQ(2, set->NumberOfElements());
217 5 : CHECK(set->HasKey(isolate, key1));
218 5 : CHECK(set->HasKey(isolate, key2));
219 5 : }
220 :
221 26644 : TEST(SmallOrderedHashMapDuplicateHashCode) {
222 5 : LocalContext context;
223 : Isolate* isolate = GetIsolateFrom(&context);
224 : Factory* factory = isolate->factory();
225 : HandleScope scope(isolate);
226 :
227 5 : Handle<SmallOrderedHashMap> map = factory->NewSmallOrderedHashMap();
228 5 : Handle<JSObject> value = factory->NewJSObjectWithNullProto();
229 5 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
230 10 : map = SmallOrderedHashMap::Add(isolate, map, key1, value).ToHandleChecked();
231 : Verify(isolate, map);
232 5 : CHECK_EQ(2, map->NumberOfBuckets());
233 5 : CHECK_EQ(1, map->NumberOfElements());
234 5 : CHECK(map->HasKey(isolate, key1));
235 :
236 5 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
237 5 : CopyHashCode(key1, key2);
238 :
239 10 : CHECK(!key1->SameValue(*key2));
240 5 : Object hash1 = key1->GetHash();
241 5 : Object hash2 = key2->GetHash();
242 5 : CHECK_EQ(hash1, hash2);
243 :
244 10 : map = SmallOrderedHashMap::Add(isolate, map, key2, value).ToHandleChecked();
245 : Verify(isolate, map);
246 5 : CHECK_EQ(2, map->NumberOfBuckets());
247 5 : CHECK_EQ(2, map->NumberOfElements());
248 5 : CHECK(map->HasKey(isolate, key1));
249 5 : CHECK(map->HasKey(isolate, key2));
250 5 : }
251 :
252 26644 : TEST(SmallOrderedHashSetGrow) {
253 5 : LocalContext context;
254 : Isolate* isolate = GetIsolateFrom(&context);
255 : Factory* factory = isolate->factory();
256 : HandleScope scope(isolate);
257 :
258 5 : Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
259 : std::vector<Handle<Object>> keys;
260 2545 : for (int i = 0; i < 254; i++) {
261 : Handle<Smi> key(Smi::FromInt(i), isolate);
262 1270 : keys.push_back(key);
263 : }
264 :
265 45 : for (size_t i = 0; i < 4; i++) {
266 40 : set = SmallOrderedHashSet::Add(isolate, set, keys[i]).ToHandleChecked();
267 : Verify(isolate, set);
268 : }
269 :
270 45 : for (size_t i = 0; i < 4; i++) {
271 20 : CHECK(set->HasKey(isolate, keys[i]));
272 : Verify(isolate, set);
273 : }
274 :
275 5 : CHECK_EQ(4, set->NumberOfElements());
276 5 : CHECK_EQ(2, set->NumberOfBuckets());
277 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
278 : Verify(isolate, set);
279 :
280 45 : for (size_t i = 4; i < 8; i++) {
281 40 : set = SmallOrderedHashSet::Add(isolate, set, keys[i]).ToHandleChecked();
282 : Verify(isolate, set);
283 : }
284 :
285 85 : for (size_t i = 0; i < 8; i++) {
286 40 : CHECK(set->HasKey(isolate, keys[i]));
287 : Verify(isolate, set);
288 : }
289 :
290 5 : CHECK_EQ(8, set->NumberOfElements());
291 5 : CHECK_EQ(4, set->NumberOfBuckets());
292 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
293 : Verify(isolate, set);
294 :
295 85 : for (size_t i = 8; i < 16; i++) {
296 80 : set = SmallOrderedHashSet::Add(isolate, set, keys[i]).ToHandleChecked();
297 : Verify(isolate, set);
298 : }
299 :
300 165 : for (size_t i = 0; i < 16; i++) {
301 80 : CHECK(set->HasKey(isolate, keys[i]));
302 : Verify(isolate, set);
303 : }
304 :
305 5 : CHECK_EQ(16, set->NumberOfElements());
306 5 : CHECK_EQ(8, set->NumberOfBuckets());
307 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
308 : Verify(isolate, set);
309 :
310 165 : for (size_t i = 16; i < 32; i++) {
311 160 : set = SmallOrderedHashSet::Add(isolate, set, keys[i]).ToHandleChecked();
312 : Verify(isolate, set);
313 : }
314 :
315 325 : for (size_t i = 0; i < 32; i++) {
316 160 : CHECK(set->HasKey(isolate, keys[i]));
317 : Verify(isolate, set);
318 : }
319 :
320 5 : CHECK_EQ(32, set->NumberOfElements());
321 5 : CHECK_EQ(16, set->NumberOfBuckets());
322 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
323 : Verify(isolate, set);
324 :
325 325 : for (size_t i = 32; i < 64; i++) {
326 320 : set = SmallOrderedHashSet::Add(isolate, set, keys[i]).ToHandleChecked();
327 : Verify(isolate, set);
328 : }
329 :
330 645 : for (size_t i = 0; i < 64; i++) {
331 320 : CHECK(set->HasKey(isolate, keys[i]));
332 : Verify(isolate, set);
333 : }
334 :
335 5 : CHECK_EQ(64, set->NumberOfElements());
336 5 : CHECK_EQ(32, set->NumberOfBuckets());
337 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
338 : Verify(isolate, set);
339 :
340 645 : for (size_t i = 64; i < 128; i++) {
341 640 : set = SmallOrderedHashSet::Add(isolate, set, keys[i]).ToHandleChecked();
342 : Verify(isolate, set);
343 : }
344 :
345 1285 : for (size_t i = 0; i < 128; i++) {
346 640 : CHECK(set->HasKey(isolate, keys[i]));
347 : Verify(isolate, set);
348 : }
349 :
350 5 : CHECK_EQ(128, set->NumberOfElements());
351 5 : CHECK_EQ(64, set->NumberOfBuckets());
352 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
353 : Verify(isolate, set);
354 :
355 1265 : for (size_t i = 128; i < 254; i++) {
356 1260 : set = SmallOrderedHashSet::Add(isolate, set, keys[i]).ToHandleChecked();
357 : Verify(isolate, set);
358 : }
359 :
360 2545 : for (size_t i = 0; i < 254; i++) {
361 1270 : CHECK(set->HasKey(isolate, keys[i]));
362 : Verify(isolate, set);
363 : }
364 :
365 5 : CHECK_EQ(254, set->NumberOfElements());
366 5 : CHECK_EQ(127, set->NumberOfBuckets());
367 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
368 : Verify(isolate, set);
369 5 : }
370 :
371 26644 : TEST(SmallOrderedHashMapGrow) {
372 5 : LocalContext context;
373 : Isolate* isolate = GetIsolateFrom(&context);
374 : Factory* factory = isolate->factory();
375 : HandleScope scope(isolate);
376 :
377 5 : Handle<SmallOrderedHashMap> map = factory->NewSmallOrderedHashMap();
378 : std::vector<Handle<Object>> keys;
379 2545 : for (int i = 0; i < 254; i++) {
380 : Handle<Smi> key(Smi::FromInt(i), isolate);
381 1270 : keys.push_back(key);
382 : }
383 :
384 45 : for (size_t i = 0; i < 4; i++) {
385 40 : map = SmallOrderedHashMap::Add(isolate, map, keys[i], keys[i])
386 : .ToHandleChecked();
387 : Verify(isolate, map);
388 : }
389 :
390 45 : for (size_t i = 0; i < 4; i++) {
391 20 : CHECK(map->HasKey(isolate, keys[i]));
392 : Verify(isolate, map);
393 : }
394 :
395 5 : CHECK_EQ(4, map->NumberOfElements());
396 5 : CHECK_EQ(2, map->NumberOfBuckets());
397 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
398 : Verify(isolate, map);
399 :
400 45 : for (size_t i = 4; i < 8; i++) {
401 40 : map = SmallOrderedHashMap::Add(isolate, map, keys[i], keys[i])
402 : .ToHandleChecked();
403 : Verify(isolate, map);
404 : }
405 :
406 85 : for (size_t i = 0; i < 8; i++) {
407 40 : CHECK(map->HasKey(isolate, keys[i]));
408 : Verify(isolate, map);
409 : }
410 :
411 5 : CHECK_EQ(8, map->NumberOfElements());
412 5 : CHECK_EQ(4, map->NumberOfBuckets());
413 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
414 : Verify(isolate, map);
415 :
416 85 : for (size_t i = 8; i < 16; i++) {
417 80 : map = SmallOrderedHashMap::Add(isolate, map, keys[i], keys[i])
418 : .ToHandleChecked();
419 : Verify(isolate, map);
420 : }
421 :
422 165 : for (size_t i = 0; i < 16; i++) {
423 80 : CHECK(map->HasKey(isolate, keys[i]));
424 : Verify(isolate, map);
425 : }
426 :
427 5 : CHECK_EQ(16, map->NumberOfElements());
428 5 : CHECK_EQ(8, map->NumberOfBuckets());
429 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
430 : Verify(isolate, map);
431 :
432 165 : for (size_t i = 16; i < 32; i++) {
433 160 : map = SmallOrderedHashMap::Add(isolate, map, keys[i], keys[i])
434 : .ToHandleChecked();
435 : Verify(isolate, map);
436 : }
437 :
438 325 : for (size_t i = 0; i < 32; i++) {
439 160 : CHECK(map->HasKey(isolate, keys[i]));
440 : Verify(isolate, map);
441 : }
442 :
443 5 : CHECK_EQ(32, map->NumberOfElements());
444 5 : CHECK_EQ(16, map->NumberOfBuckets());
445 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
446 : Verify(isolate, map);
447 :
448 325 : for (size_t i = 32; i < 64; i++) {
449 320 : map = SmallOrderedHashMap::Add(isolate, map, keys[i], keys[i])
450 : .ToHandleChecked();
451 : Verify(isolate, map);
452 : }
453 :
454 645 : for (size_t i = 0; i < 64; i++) {
455 320 : CHECK(map->HasKey(isolate, keys[i]));
456 : Verify(isolate, map);
457 : }
458 :
459 5 : CHECK_EQ(64, map->NumberOfElements());
460 5 : CHECK_EQ(32, map->NumberOfBuckets());
461 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
462 : Verify(isolate, map);
463 :
464 645 : for (size_t i = 64; i < 128; i++) {
465 640 : map = SmallOrderedHashMap::Add(isolate, map, keys[i], keys[i])
466 : .ToHandleChecked();
467 : Verify(isolate, map);
468 : }
469 :
470 1285 : for (size_t i = 0; i < 128; i++) {
471 640 : CHECK(map->HasKey(isolate, keys[i]));
472 : Verify(isolate, map);
473 : }
474 :
475 5 : CHECK_EQ(128, map->NumberOfElements());
476 5 : CHECK_EQ(64, map->NumberOfBuckets());
477 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
478 : Verify(isolate, map);
479 :
480 1265 : for (size_t i = 128; i < 254; i++) {
481 1260 : map = SmallOrderedHashMap::Add(isolate, map, keys[i], keys[i])
482 : .ToHandleChecked();
483 : Verify(isolate, map);
484 : }
485 :
486 2545 : for (size_t i = 0; i < 254; i++) {
487 1270 : CHECK(map->HasKey(isolate, keys[i]));
488 : Verify(isolate, map);
489 : }
490 :
491 5 : CHECK_EQ(254, map->NumberOfElements());
492 5 : CHECK_EQ(127, map->NumberOfBuckets());
493 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
494 : Verify(isolate, map);
495 5 : }
496 :
497 26644 : TEST(OrderedHashTableInsertion) {
498 5 : LocalContext context;
499 : Isolate* isolate = GetIsolateFrom(&context);
500 : Factory* factory = isolate->factory();
501 : HandleScope scope(isolate);
502 :
503 5 : Handle<OrderedHashMap> map = factory->NewOrderedHashMap();
504 : Verify(isolate, map);
505 5 : CHECK_EQ(2, map->NumberOfBuckets());
506 5 : CHECK_EQ(0, map->NumberOfElements());
507 :
508 : // Add a new key.
509 : Handle<Smi> key1(Smi::FromInt(1), isolate);
510 : Handle<Smi> value1(Smi::FromInt(1), isolate);
511 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
512 5 : map = OrderedHashMap::Add(isolate, map, key1, value1);
513 : Verify(isolate, map);
514 5 : CHECK_EQ(2, map->NumberOfBuckets());
515 5 : CHECK_EQ(1, map->NumberOfElements());
516 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
517 :
518 : // Add existing key.
519 5 : map = OrderedHashMap::Add(isolate, map, key1, value1);
520 : Verify(isolate, map);
521 5 : CHECK_EQ(2, map->NumberOfBuckets());
522 5 : CHECK_EQ(1, map->NumberOfElements());
523 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
524 :
525 5 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
526 5 : Handle<String> value = factory->NewStringFromAsciiChecked("bar");
527 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
528 5 : map = OrderedHashMap::Add(isolate, map, key2, value);
529 : Verify(isolate, map);
530 5 : CHECK_EQ(2, map->NumberOfBuckets());
531 5 : CHECK_EQ(2, map->NumberOfElements());
532 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
533 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
534 :
535 5 : map = OrderedHashMap::Add(isolate, map, key2, value);
536 : Verify(isolate, map);
537 5 : CHECK_EQ(2, map->NumberOfBuckets());
538 5 : CHECK_EQ(2, map->NumberOfElements());
539 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
540 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
541 :
542 5 : Handle<Symbol> key3 = factory->NewSymbol();
543 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
544 5 : map = OrderedHashMap::Add(isolate, map, key3, value);
545 : Verify(isolate, map);
546 5 : CHECK_EQ(2, map->NumberOfBuckets());
547 5 : CHECK_EQ(3, map->NumberOfElements());
548 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
549 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
550 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
551 :
552 5 : map = OrderedHashMap::Add(isolate, map, key3, value);
553 : Verify(isolate, map);
554 5 : CHECK_EQ(2, map->NumberOfBuckets());
555 5 : CHECK_EQ(3, map->NumberOfElements());
556 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
557 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
558 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
559 :
560 5 : Handle<Object> key4 = factory->NewHeapNumber(42.0);
561 5 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key4));
562 5 : map = OrderedHashMap::Add(isolate, map, key4, value);
563 : Verify(isolate, map);
564 5 : CHECK_EQ(2, map->NumberOfBuckets());
565 5 : CHECK_EQ(4, map->NumberOfElements());
566 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
567 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
568 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
569 5 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key4));
570 :
571 5 : map = OrderedHashMap::Add(isolate, map, key4, value);
572 : Verify(isolate, map);
573 5 : CHECK_EQ(2, map->NumberOfBuckets());
574 5 : CHECK_EQ(4, map->NumberOfElements());
575 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
576 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
577 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
578 5 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key4));
579 5 : }
580 :
581 26644 : TEST(OrderedHashMapDuplicateHashCode) {
582 5 : LocalContext context;
583 : Isolate* isolate = GetIsolateFrom(&context);
584 : Factory* factory = isolate->factory();
585 : HandleScope scope(isolate);
586 :
587 5 : Handle<OrderedHashMap> map = factory->NewOrderedHashMap();
588 5 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
589 5 : Handle<JSObject> value = factory->NewJSObjectWithNullProto();
590 5 : map = OrderedHashMap::Add(isolate, map, key1, value);
591 : Verify(isolate, map);
592 5 : CHECK_EQ(2, map->NumberOfBuckets());
593 5 : CHECK_EQ(1, map->NumberOfElements());
594 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
595 :
596 5 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
597 5 : CopyHashCode(key1, key2);
598 :
599 5 : map = OrderedHashMap::Add(isolate, map, key2, value);
600 : Verify(isolate, map);
601 5 : CHECK_EQ(2, map->NumberOfBuckets());
602 5 : CHECK_EQ(2, map->NumberOfElements());
603 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
604 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
605 5 : }
606 :
607 26644 : TEST(OrderedHashMapDeletion) {
608 5 : LocalContext context;
609 : Isolate* isolate = GetIsolateFrom(&context);
610 : Factory* factory = isolate->factory();
611 : HandleScope scope(isolate);
612 : Handle<Smi> value1(Smi::FromInt(1), isolate);
613 5 : Handle<String> value = factory->NewStringFromAsciiChecked("bar");
614 :
615 5 : Handle<OrderedHashMap> map = factory->NewOrderedHashMap();
616 : Verify(isolate, map);
617 5 : CHECK_EQ(2, map->NumberOfBuckets());
618 5 : CHECK_EQ(0, map->NumberOfElements());
619 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
620 :
621 : // Delete from an empty hash table
622 : Handle<Smi> key1(Smi::FromInt(1), isolate);
623 10 : CHECK(!OrderedHashMap::Delete(isolate, *map, *key1));
624 : Verify(isolate, map);
625 5 : CHECK_EQ(2, map->NumberOfBuckets());
626 5 : CHECK_EQ(0, map->NumberOfElements());
627 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
628 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
629 :
630 5 : map = OrderedHashMap::Add(isolate, map, key1, value1);
631 : Verify(isolate, map);
632 5 : CHECK_EQ(2, map->NumberOfBuckets());
633 5 : CHECK_EQ(1, map->NumberOfElements());
634 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
635 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
636 :
637 : // Delete single existing key
638 10 : CHECK(OrderedHashMap::Delete(isolate, *map, *key1));
639 : Verify(isolate, map);
640 5 : CHECK_EQ(2, map->NumberOfBuckets());
641 5 : CHECK_EQ(0, map->NumberOfElements());
642 5 : CHECK_EQ(1, map->NumberOfDeletedElements());
643 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
644 :
645 5 : map = OrderedHashMap::Add(isolate, map, key1, value1);
646 : Verify(isolate, map);
647 5 : CHECK_EQ(2, map->NumberOfBuckets());
648 5 : CHECK_EQ(1, map->NumberOfElements());
649 5 : CHECK_EQ(1, map->NumberOfDeletedElements());
650 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
651 :
652 5 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
653 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
654 5 : map = OrderedHashMap::Add(isolate, map, key2, value);
655 : Verify(isolate, map);
656 5 : CHECK_EQ(2, map->NumberOfBuckets());
657 5 : CHECK_EQ(2, map->NumberOfElements());
658 5 : CHECK_EQ(1, map->NumberOfDeletedElements());
659 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
660 :
661 5 : Handle<Symbol> key3 = factory->NewSymbol();
662 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
663 5 : map = OrderedHashMap::Add(isolate, map, key3, value);
664 : Verify(isolate, map);
665 5 : CHECK_EQ(2, map->NumberOfBuckets());
666 5 : CHECK_EQ(3, map->NumberOfElements());
667 5 : CHECK_EQ(1, map->NumberOfDeletedElements());
668 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
669 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
670 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
671 :
672 : // Delete multiple existing keys
673 10 : CHECK(OrderedHashMap::Delete(isolate, *map, *key1));
674 : Verify(isolate, map);
675 5 : CHECK_EQ(2, map->NumberOfBuckets());
676 5 : CHECK_EQ(2, map->NumberOfElements());
677 5 : CHECK_EQ(2, map->NumberOfDeletedElements());
678 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
679 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key2));
680 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
681 :
682 10 : CHECK(OrderedHashMap::Delete(isolate, *map, *key2));
683 : Verify(isolate, map);
684 5 : CHECK_EQ(2, map->NumberOfBuckets());
685 5 : CHECK_EQ(1, map->NumberOfElements());
686 5 : CHECK_EQ(3, map->NumberOfDeletedElements());
687 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
688 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
689 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key3));
690 :
691 10 : CHECK(OrderedHashMap::Delete(isolate, *map, *key3));
692 : Verify(isolate, map);
693 5 : CHECK_EQ(2, map->NumberOfBuckets());
694 5 : CHECK_EQ(0, map->NumberOfElements());
695 5 : CHECK_EQ(4, map->NumberOfDeletedElements());
696 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
697 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
698 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
699 :
700 : // Delete non existent key from non new hash table
701 10 : CHECK(!OrderedHashMap::Delete(isolate, *map, *key3));
702 : Verify(isolate, map);
703 5 : CHECK_EQ(2, map->NumberOfBuckets());
704 5 : CHECK_EQ(0, map->NumberOfElements());
705 5 : CHECK_EQ(4, map->NumberOfDeletedElements());
706 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key1));
707 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
708 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
709 :
710 : // Delete non existent key from non empty hash table
711 5 : map = OrderedHashMap::Shrink(isolate, map);
712 5 : map = OrderedHashMap::Add(isolate, map, key1, value);
713 : Verify(isolate, map);
714 5 : CHECK_EQ(2, map->NumberOfBuckets());
715 5 : CHECK_EQ(1, map->NumberOfElements());
716 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
717 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
718 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
719 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
720 10 : CHECK(!OrderedHashMap::Delete(isolate, *map, *key2));
721 : Verify(isolate, map);
722 5 : CHECK_EQ(2, map->NumberOfBuckets());
723 5 : CHECK_EQ(1, map->NumberOfElements());
724 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
725 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
726 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
727 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key3));
728 5 : }
729 :
730 26644 : TEST(SmallOrderedHashMapDeletion) {
731 5 : LocalContext context;
732 : Isolate* isolate = GetIsolateFrom(&context);
733 : Factory* factory = isolate->factory();
734 : HandleScope scope(isolate);
735 : Handle<Smi> value1(Smi::FromInt(1), isolate);
736 5 : Handle<String> value = factory->NewStringFromAsciiChecked("bar");
737 :
738 5 : Handle<SmallOrderedHashMap> map = factory->NewSmallOrderedHashMap();
739 : Verify(isolate, map);
740 5 : CHECK_EQ(2, map->NumberOfBuckets());
741 5 : CHECK_EQ(0, map->NumberOfElements());
742 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
743 :
744 : // Delete from an empty hash table
745 : Handle<Smi> key1(Smi::FromInt(1), isolate);
746 10 : CHECK(!SmallOrderedHashMap::Delete(isolate, *map, *key1));
747 : Verify(isolate, map);
748 5 : CHECK_EQ(2, map->NumberOfBuckets());
749 5 : CHECK_EQ(0, map->NumberOfElements());
750 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
751 5 : CHECK(!map->HasKey(isolate, key1));
752 :
753 10 : map = SmallOrderedHashMap::Add(isolate, map, key1, value1).ToHandleChecked();
754 : Verify(isolate, map);
755 5 : CHECK_EQ(2, map->NumberOfBuckets());
756 5 : CHECK_EQ(1, map->NumberOfElements());
757 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
758 5 : CHECK(map->HasKey(isolate, key1));
759 :
760 : // Delete single existing key
761 10 : CHECK(SmallOrderedHashMap::Delete(isolate, *map, *key1));
762 : Verify(isolate, map);
763 5 : CHECK_EQ(2, map->NumberOfBuckets());
764 5 : CHECK_EQ(0, map->NumberOfElements());
765 5 : CHECK_EQ(1, map->NumberOfDeletedElements());
766 5 : CHECK(!map->HasKey(isolate, key1));
767 :
768 10 : map = SmallOrderedHashMap::Add(isolate, map, key1, value1).ToHandleChecked();
769 : Verify(isolate, map);
770 5 : CHECK_EQ(2, map->NumberOfBuckets());
771 5 : CHECK_EQ(1, map->NumberOfElements());
772 5 : CHECK_EQ(1, map->NumberOfDeletedElements());
773 5 : CHECK(map->HasKey(isolate, key1));
774 :
775 5 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
776 5 : CHECK(!map->HasKey(isolate, key2));
777 10 : map = SmallOrderedHashMap::Add(isolate, map, key2, value).ToHandleChecked();
778 : Verify(isolate, map);
779 5 : CHECK_EQ(2, map->NumberOfBuckets());
780 5 : CHECK_EQ(2, map->NumberOfElements());
781 5 : CHECK_EQ(1, map->NumberOfDeletedElements());
782 5 : CHECK(map->HasKey(isolate, key2));
783 :
784 5 : Handle<Symbol> key3 = factory->NewSymbol();
785 5 : CHECK(!map->HasKey(isolate, key3));
786 10 : map = SmallOrderedHashMap::Add(isolate, map, key3, value).ToHandleChecked();
787 : Verify(isolate, map);
788 5 : CHECK_EQ(2, map->NumberOfBuckets());
789 5 : CHECK_EQ(3, map->NumberOfElements());
790 5 : CHECK_EQ(1, map->NumberOfDeletedElements());
791 5 : CHECK(map->HasKey(isolate, key1));
792 5 : CHECK(map->HasKey(isolate, key2));
793 5 : CHECK(map->HasKey(isolate, key3));
794 :
795 : // Delete multiple existing keys
796 10 : CHECK(SmallOrderedHashMap::Delete(isolate, *map, *key1));
797 : Verify(isolate, map);
798 5 : CHECK_EQ(2, map->NumberOfBuckets());
799 5 : CHECK_EQ(2, map->NumberOfElements());
800 5 : CHECK_EQ(2, map->NumberOfDeletedElements());
801 5 : CHECK(!map->HasKey(isolate, key1));
802 5 : CHECK(map->HasKey(isolate, key2));
803 5 : CHECK(map->HasKey(isolate, key3));
804 :
805 10 : CHECK(SmallOrderedHashMap::Delete(isolate, *map, *key2));
806 : Verify(isolate, map);
807 5 : CHECK_EQ(2, map->NumberOfBuckets());
808 5 : CHECK_EQ(1, map->NumberOfElements());
809 5 : CHECK_EQ(3, map->NumberOfDeletedElements());
810 5 : CHECK(!map->HasKey(isolate, key1));
811 5 : CHECK(!map->HasKey(isolate, key2));
812 5 : CHECK(map->HasKey(isolate, key3));
813 :
814 10 : CHECK(SmallOrderedHashMap::Delete(isolate, *map, *key3));
815 : Verify(isolate, map);
816 5 : CHECK_EQ(2, map->NumberOfBuckets());
817 5 : CHECK_EQ(0, map->NumberOfElements());
818 5 : CHECK_EQ(4, map->NumberOfDeletedElements());
819 5 : CHECK(!map->HasKey(isolate, key1));
820 5 : CHECK(!map->HasKey(isolate, key2));
821 5 : CHECK(!map->HasKey(isolate, key3));
822 :
823 : // Delete non existent key from non new hash table
824 10 : CHECK(!SmallOrderedHashMap::Delete(isolate, *map, *key3));
825 : Verify(isolate, map);
826 5 : CHECK_EQ(2, map->NumberOfBuckets());
827 5 : CHECK_EQ(0, map->NumberOfElements());
828 5 : CHECK_EQ(4, map->NumberOfDeletedElements());
829 5 : CHECK(!map->HasKey(isolate, key1));
830 5 : CHECK(!map->HasKey(isolate, key2));
831 5 : CHECK(!map->HasKey(isolate, key3));
832 :
833 : // Delete non existent key from non empty hash table
834 10 : map = SmallOrderedHashMap::Add(isolate, map, key1, value).ToHandleChecked();
835 : Verify(isolate, map);
836 5 : CHECK_EQ(2, map->NumberOfBuckets());
837 5 : CHECK_EQ(1, map->NumberOfElements());
838 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
839 5 : CHECK(map->HasKey(isolate, key1));
840 5 : CHECK(!map->HasKey(isolate, key2));
841 5 : CHECK(!map->HasKey(isolate, key3));
842 10 : CHECK(!SmallOrderedHashMap::Delete(isolate, *map, *key2));
843 : Verify(isolate, map);
844 5 : CHECK_EQ(2, map->NumberOfBuckets());
845 5 : CHECK_EQ(1, map->NumberOfElements());
846 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
847 5 : CHECK(map->HasKey(isolate, key1));
848 5 : CHECK(!map->HasKey(isolate, key2));
849 5 : CHECK(!map->HasKey(isolate, key3));
850 5 : }
851 :
852 26644 : TEST(OrderedHashMapDuplicateHashCodeDeletion) {
853 5 : LocalContext context;
854 : Isolate* isolate = GetIsolateFrom(&context);
855 : Factory* factory = isolate->factory();
856 : HandleScope scope(isolate);
857 :
858 5 : Handle<OrderedHashMap> map = factory->NewOrderedHashMap();
859 5 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
860 5 : Handle<JSObject> value = factory->NewJSObjectWithNullProto();
861 5 : map = OrderedHashMap::Add(isolate, map, key1, value);
862 : Verify(isolate, map);
863 5 : CHECK_EQ(2, map->NumberOfBuckets());
864 5 : CHECK_EQ(1, map->NumberOfElements());
865 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
866 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
867 :
868 5 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
869 5 : CopyHashCode(key1, key2);
870 :
871 : // We shouldn't be able to delete the key!
872 10 : CHECK(!OrderedHashMap::Delete(isolate, *map, *key2));
873 : Verify(isolate, map);
874 5 : CHECK_EQ(2, map->NumberOfBuckets());
875 5 : CHECK_EQ(1, map->NumberOfElements());
876 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
877 10 : CHECK(OrderedHashMap::HasKey(isolate, *map, *key1));
878 10 : CHECK(!OrderedHashMap::HasKey(isolate, *map, *key2));
879 5 : }
880 :
881 26644 : TEST(SmallOrderedHashMapDuplicateHashCodeDeletion) {
882 5 : LocalContext context;
883 : Isolate* isolate = GetIsolateFrom(&context);
884 : Factory* factory = isolate->factory();
885 : HandleScope scope(isolate);
886 :
887 5 : Handle<SmallOrderedHashMap> map = factory->NewSmallOrderedHashMap();
888 5 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
889 5 : Handle<JSObject> value = factory->NewJSObjectWithNullProto();
890 10 : map = SmallOrderedHashMap::Add(isolate, map, key1, value).ToHandleChecked();
891 : Verify(isolate, map);
892 5 : CHECK_EQ(2, map->NumberOfBuckets());
893 5 : CHECK_EQ(1, map->NumberOfElements());
894 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
895 5 : CHECK(map->HasKey(isolate, key1));
896 :
897 5 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
898 5 : CopyHashCode(key1, key2);
899 :
900 : // We shouldn't be able to delete the key!
901 10 : CHECK(!SmallOrderedHashMap::Delete(isolate, *map, *key2));
902 : Verify(isolate, map);
903 5 : CHECK_EQ(2, map->NumberOfBuckets());
904 5 : CHECK_EQ(1, map->NumberOfElements());
905 5 : CHECK_EQ(0, map->NumberOfDeletedElements());
906 5 : CHECK(map->HasKey(isolate, key1));
907 5 : CHECK(!map->HasKey(isolate, key2));
908 5 : }
909 :
910 26644 : TEST(OrderedHashSetDeletion) {
911 5 : LocalContext context;
912 : Isolate* isolate = GetIsolateFrom(&context);
913 : Factory* factory = isolate->factory();
914 : HandleScope scope(isolate);
915 :
916 5 : Handle<OrderedHashSet> set = factory->NewOrderedHashSet();
917 : Verify(isolate, set);
918 5 : CHECK_EQ(2, set->NumberOfBuckets());
919 5 : CHECK_EQ(0, set->NumberOfElements());
920 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
921 :
922 : // Delete from an empty hash table
923 : Handle<Smi> key1(Smi::FromInt(1), isolate);
924 10 : CHECK(!OrderedHashSet::Delete(isolate, *set, *key1));
925 : Verify(isolate, set);
926 5 : CHECK_EQ(2, set->NumberOfBuckets());
927 5 : CHECK_EQ(0, set->NumberOfElements());
928 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
929 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
930 :
931 5 : set = OrderedHashSet::Add(isolate, set, key1);
932 : Verify(isolate, set);
933 5 : CHECK_EQ(2, set->NumberOfBuckets());
934 5 : CHECK_EQ(1, set->NumberOfElements());
935 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
936 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
937 :
938 : // Delete single existing key
939 10 : CHECK(OrderedHashSet::Delete(isolate, *set, *key1));
940 : Verify(isolate, set);
941 5 : CHECK_EQ(2, set->NumberOfBuckets());
942 5 : CHECK_EQ(0, set->NumberOfElements());
943 5 : CHECK_EQ(1, set->NumberOfDeletedElements());
944 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
945 :
946 5 : set = OrderedHashSet::Add(isolate, set, key1);
947 : Verify(isolate, set);
948 5 : CHECK_EQ(2, set->NumberOfBuckets());
949 5 : CHECK_EQ(1, set->NumberOfElements());
950 5 : CHECK_EQ(1, set->NumberOfDeletedElements());
951 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
952 :
953 5 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
954 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
955 5 : set = OrderedHashSet::Add(isolate, set, key2);
956 : Verify(isolate, set);
957 5 : CHECK_EQ(2, set->NumberOfBuckets());
958 5 : CHECK_EQ(2, set->NumberOfElements());
959 5 : CHECK_EQ(1, set->NumberOfDeletedElements());
960 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key2));
961 :
962 5 : Handle<Symbol> key3 = factory->NewSymbol();
963 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
964 5 : set = OrderedHashSet::Add(isolate, set, key3);
965 : Verify(isolate, set);
966 5 : CHECK_EQ(2, set->NumberOfBuckets());
967 5 : CHECK_EQ(3, set->NumberOfElements());
968 5 : CHECK_EQ(1, set->NumberOfDeletedElements());
969 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
970 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key2));
971 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key3));
972 :
973 : // Delete multiple existing keys
974 10 : CHECK(OrderedHashSet::Delete(isolate, *set, *key1));
975 : Verify(isolate, set);
976 5 : CHECK_EQ(2, set->NumberOfBuckets());
977 5 : CHECK_EQ(2, set->NumberOfElements());
978 5 : CHECK_EQ(2, set->NumberOfDeletedElements());
979 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
980 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key2));
981 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key3));
982 :
983 10 : CHECK(OrderedHashSet::Delete(isolate, *set, *key2));
984 : Verify(isolate, set);
985 5 : CHECK_EQ(2, set->NumberOfBuckets());
986 5 : CHECK_EQ(1, set->NumberOfElements());
987 5 : CHECK_EQ(3, set->NumberOfDeletedElements());
988 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
989 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
990 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key3));
991 :
992 10 : CHECK(OrderedHashSet::Delete(isolate, *set, *key3));
993 : Verify(isolate, set);
994 5 : CHECK_EQ(2, set->NumberOfBuckets());
995 5 : CHECK_EQ(0, set->NumberOfElements());
996 5 : CHECK_EQ(4, set->NumberOfDeletedElements());
997 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
998 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
999 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
1000 :
1001 : // Delete non existent key from non new hash table
1002 10 : CHECK(!OrderedHashSet::Delete(isolate, *set, *key3));
1003 : Verify(isolate, set);
1004 5 : CHECK_EQ(2, set->NumberOfBuckets());
1005 5 : CHECK_EQ(0, set->NumberOfElements());
1006 5 : CHECK_EQ(4, set->NumberOfDeletedElements());
1007 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key1));
1008 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
1009 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
1010 :
1011 : // Delete non existent key from non empty hash table
1012 5 : set = OrderedHashSet::Shrink(isolate, set);
1013 5 : set = OrderedHashSet::Add(isolate, set, key1);
1014 : Verify(isolate, set);
1015 5 : CHECK_EQ(2, set->NumberOfBuckets());
1016 5 : CHECK_EQ(1, set->NumberOfElements());
1017 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1018 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
1019 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
1020 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
1021 10 : CHECK(!OrderedHashSet::Delete(isolate, *set, *key2));
1022 : Verify(isolate, set);
1023 5 : CHECK_EQ(2, set->NumberOfBuckets());
1024 5 : CHECK_EQ(1, set->NumberOfElements());
1025 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1026 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
1027 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
1028 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key3));
1029 5 : }
1030 :
1031 26644 : TEST(SmallOrderedHashSetDeletion) {
1032 5 : LocalContext context;
1033 : Isolate* isolate = GetIsolateFrom(&context);
1034 : Factory* factory = isolate->factory();
1035 : HandleScope scope(isolate);
1036 :
1037 5 : Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
1038 : Verify(isolate, set);
1039 5 : CHECK_EQ(2, set->NumberOfBuckets());
1040 5 : CHECK_EQ(0, set->NumberOfElements());
1041 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1042 :
1043 : // Delete from an empty hash table
1044 : Handle<Smi> key1(Smi::FromInt(1), isolate);
1045 10 : CHECK(!SmallOrderedHashSet::Delete(isolate, *set, *key1));
1046 : Verify(isolate, set);
1047 5 : CHECK_EQ(2, set->NumberOfBuckets());
1048 5 : CHECK_EQ(0, set->NumberOfElements());
1049 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1050 5 : CHECK(!set->HasKey(isolate, key1));
1051 :
1052 10 : set = SmallOrderedHashSet::Add(isolate, set, key1).ToHandleChecked();
1053 : Verify(isolate, set);
1054 5 : CHECK_EQ(2, set->NumberOfBuckets());
1055 5 : CHECK_EQ(1, set->NumberOfElements());
1056 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1057 5 : CHECK(set->HasKey(isolate, key1));
1058 :
1059 : // Delete single existing key
1060 10 : CHECK(SmallOrderedHashSet::Delete(isolate, *set, *key1));
1061 : Verify(isolate, set);
1062 5 : CHECK_EQ(2, set->NumberOfBuckets());
1063 5 : CHECK_EQ(0, set->NumberOfElements());
1064 5 : CHECK_EQ(1, set->NumberOfDeletedElements());
1065 5 : CHECK(!set->HasKey(isolate, key1));
1066 :
1067 10 : set = SmallOrderedHashSet::Add(isolate, set, key1).ToHandleChecked();
1068 : Verify(isolate, set);
1069 5 : CHECK_EQ(2, set->NumberOfBuckets());
1070 5 : CHECK_EQ(1, set->NumberOfElements());
1071 5 : CHECK_EQ(1, set->NumberOfDeletedElements());
1072 5 : CHECK(set->HasKey(isolate, key1));
1073 :
1074 5 : Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
1075 5 : CHECK(!set->HasKey(isolate, key2));
1076 10 : set = SmallOrderedHashSet::Add(isolate, set, key2).ToHandleChecked();
1077 : Verify(isolate, set);
1078 5 : CHECK_EQ(2, set->NumberOfBuckets());
1079 5 : CHECK_EQ(2, set->NumberOfElements());
1080 5 : CHECK_EQ(1, set->NumberOfDeletedElements());
1081 5 : CHECK(set->HasKey(isolate, key2));
1082 :
1083 5 : Handle<Symbol> key3 = factory->NewSymbol();
1084 5 : CHECK(!set->HasKey(isolate, key3));
1085 10 : set = SmallOrderedHashSet::Add(isolate, set, key3).ToHandleChecked();
1086 : Verify(isolate, set);
1087 5 : CHECK_EQ(2, set->NumberOfBuckets());
1088 5 : CHECK_EQ(3, set->NumberOfElements());
1089 5 : CHECK_EQ(1, set->NumberOfDeletedElements());
1090 5 : CHECK(set->HasKey(isolate, key1));
1091 5 : CHECK(set->HasKey(isolate, key2));
1092 5 : CHECK(set->HasKey(isolate, key3));
1093 :
1094 : // Delete multiple existing keys
1095 10 : CHECK(SmallOrderedHashSet::Delete(isolate, *set, *key1));
1096 : Verify(isolate, set);
1097 5 : CHECK_EQ(2, set->NumberOfBuckets());
1098 5 : CHECK_EQ(2, set->NumberOfElements());
1099 5 : CHECK_EQ(2, set->NumberOfDeletedElements());
1100 5 : CHECK(!set->HasKey(isolate, key1));
1101 5 : CHECK(set->HasKey(isolate, key2));
1102 5 : CHECK(set->HasKey(isolate, key3));
1103 :
1104 10 : CHECK(SmallOrderedHashSet::Delete(isolate, *set, *key2));
1105 : Verify(isolate, set);
1106 5 : CHECK_EQ(2, set->NumberOfBuckets());
1107 5 : CHECK_EQ(1, set->NumberOfElements());
1108 5 : CHECK_EQ(3, set->NumberOfDeletedElements());
1109 5 : CHECK(!set->HasKey(isolate, key1));
1110 5 : CHECK(!set->HasKey(isolate, key2));
1111 5 : CHECK(set->HasKey(isolate, key3));
1112 :
1113 10 : CHECK(SmallOrderedHashSet::Delete(isolate, *set, *key3));
1114 : Verify(isolate, set);
1115 5 : CHECK_EQ(2, set->NumberOfBuckets());
1116 5 : CHECK_EQ(0, set->NumberOfElements());
1117 5 : CHECK_EQ(4, set->NumberOfDeletedElements());
1118 5 : CHECK(!set->HasKey(isolate, key1));
1119 5 : CHECK(!set->HasKey(isolate, key2));
1120 5 : CHECK(!set->HasKey(isolate, key3));
1121 :
1122 : // Delete non existent key from non new hash table
1123 10 : CHECK(!SmallOrderedHashSet::Delete(isolate, *set, *key3));
1124 : Verify(isolate, set);
1125 5 : CHECK_EQ(2, set->NumberOfBuckets());
1126 5 : CHECK_EQ(0, set->NumberOfElements());
1127 5 : CHECK_EQ(4, set->NumberOfDeletedElements());
1128 5 : CHECK(!set->HasKey(isolate, key1));
1129 5 : CHECK(!set->HasKey(isolate, key2));
1130 5 : CHECK(!set->HasKey(isolate, key3));
1131 :
1132 : // Delete non existent key from non empty hash table
1133 10 : set = SmallOrderedHashSet::Add(isolate, set, key1).ToHandleChecked();
1134 : Verify(isolate, set);
1135 5 : CHECK_EQ(2, set->NumberOfBuckets());
1136 5 : CHECK_EQ(1, set->NumberOfElements());
1137 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1138 5 : CHECK(set->HasKey(isolate, key1));
1139 5 : CHECK(!set->HasKey(isolate, key2));
1140 5 : CHECK(!set->HasKey(isolate, key3));
1141 10 : CHECK(!SmallOrderedHashSet::Delete(isolate, *set, *key2));
1142 : Verify(isolate, set);
1143 5 : CHECK_EQ(2, set->NumberOfBuckets());
1144 5 : CHECK_EQ(1, set->NumberOfElements());
1145 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1146 5 : CHECK(set->HasKey(isolate, key1));
1147 5 : CHECK(!set->HasKey(isolate, key2));
1148 5 : CHECK(!set->HasKey(isolate, key3));
1149 5 : }
1150 :
1151 26644 : TEST(OrderedHashSetDuplicateHashCodeDeletion) {
1152 5 : LocalContext context;
1153 : Isolate* isolate = GetIsolateFrom(&context);
1154 : Factory* factory = isolate->factory();
1155 : HandleScope scope(isolate);
1156 :
1157 5 : Handle<OrderedHashSet> set = factory->NewOrderedHashSet();
1158 5 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
1159 5 : set = OrderedHashSet::Add(isolate, set, key1);
1160 : Verify(isolate, set);
1161 5 : CHECK_EQ(2, set->NumberOfBuckets());
1162 5 : CHECK_EQ(1, set->NumberOfElements());
1163 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1164 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
1165 :
1166 5 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
1167 5 : CopyHashCode(key1, key2);
1168 :
1169 : // We shouldn't be able to delete the key!
1170 10 : CHECK(!OrderedHashSet::Delete(isolate, *set, *key2));
1171 : Verify(isolate, set);
1172 5 : CHECK_EQ(2, set->NumberOfBuckets());
1173 5 : CHECK_EQ(1, set->NumberOfElements());
1174 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1175 10 : CHECK(OrderedHashSet::HasKey(isolate, *set, *key1));
1176 10 : CHECK(!OrderedHashSet::HasKey(isolate, *set, *key2));
1177 5 : }
1178 :
1179 26644 : TEST(SmallOrderedHashSetDuplicateHashCodeDeletion) {
1180 5 : LocalContext context;
1181 : Isolate* isolate = GetIsolateFrom(&context);
1182 : Factory* factory = isolate->factory();
1183 : HandleScope scope(isolate);
1184 :
1185 5 : Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
1186 5 : Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
1187 10 : set = SmallOrderedHashSet::Add(isolate, set, key1).ToHandleChecked();
1188 : Verify(isolate, set);
1189 5 : CHECK_EQ(2, set->NumberOfBuckets());
1190 5 : CHECK_EQ(1, set->NumberOfElements());
1191 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1192 5 : CHECK(set->HasKey(isolate, key1));
1193 :
1194 5 : Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
1195 5 : CopyHashCode(key1, key2);
1196 :
1197 : // We shouldn't be able to delete the key!
1198 10 : CHECK(!SmallOrderedHashSet::Delete(isolate, *set, *key2));
1199 : Verify(isolate, set);
1200 5 : CHECK_EQ(2, set->NumberOfBuckets());
1201 5 : CHECK_EQ(1, set->NumberOfElements());
1202 5 : CHECK_EQ(0, set->NumberOfDeletedElements());
1203 5 : CHECK(set->HasKey(isolate, key1));
1204 5 : CHECK(!set->HasKey(isolate, key2));
1205 5 : }
1206 :
1207 26644 : TEST(OrderedHashSetHandlerInsertion) {
1208 5 : LocalContext context;
1209 : Isolate* isolate = GetIsolateFrom(&context);
1210 : HandleScope scope(isolate);
1211 :
1212 5 : Handle<HeapObject> set = OrderedHashSetHandler::Allocate(isolate, 4);
1213 : Verify(isolate, set);
1214 :
1215 : // Add a new key.
1216 : Handle<Smi> key1(Smi::FromInt(1), isolate);
1217 5 : CHECK(!OrderedHashSetHandler::HasKey(isolate, set, key1));
1218 5 : set = OrderedHashSetHandler::Add(isolate, set, key1);
1219 : Verify(isolate, set);
1220 5 : CHECK(OrderedHashSetHandler::HasKey(isolate, set, key1));
1221 :
1222 : // Add existing key.
1223 5 : set = OrderedHashSetHandler::Add(isolate, set, key1);
1224 : Verify(isolate, set);
1225 5 : CHECK(OrderedHashSetHandler::HasKey(isolate, set, key1));
1226 5 : CHECK(SmallOrderedHashSet::Is(set));
1227 :
1228 10245 : for (int i = 0; i < 1024; i++) {
1229 : Handle<Smi> key_i(Smi::FromInt(i), isolate);
1230 5120 : set = OrderedHashSetHandler::Add(isolate, set, key_i);
1231 : Verify(isolate, set);
1232 5253120 : for (int j = 0; j <= i; j++) {
1233 : Handle<Smi> key_j(Smi::FromInt(j), isolate);
1234 2624000 : CHECK(OrderedHashSetHandler::HasKey(isolate, set, key_j));
1235 : }
1236 : }
1237 5 : CHECK(OrderedHashSet::Is(set));
1238 5 : }
1239 :
1240 26644 : TEST(OrderedHashMapHandlerInsertion) {
1241 5 : LocalContext context;
1242 : Isolate* isolate = GetIsolateFrom(&context);
1243 : HandleScope scope(isolate);
1244 :
1245 5 : Handle<HeapObject> map = OrderedHashMapHandler::Allocate(isolate, 4);
1246 : Verify(isolate, map);
1247 :
1248 : // Add a new key.
1249 : Handle<Smi> key1(Smi::FromInt(1), isolate);
1250 : Handle<Smi> value1(Smi::FromInt(1), isolate);
1251 5 : CHECK(!OrderedHashMapHandler::HasKey(isolate, map, key1));
1252 5 : map = OrderedHashMapHandler::Add(isolate, map, key1, value1);
1253 : Verify(isolate, map);
1254 5 : CHECK(OrderedHashMapHandler::HasKey(isolate, map, key1));
1255 :
1256 : // Add existing key.
1257 5 : map = OrderedHashMapHandler::Add(isolate, map, key1, value1);
1258 : Verify(isolate, map);
1259 5 : CHECK(OrderedHashMapHandler::HasKey(isolate, map, key1));
1260 5 : CHECK(SmallOrderedHashMap::Is(map));
1261 10245 : for (int i = 0; i < 1024; i++) {
1262 : Handle<Smi> key_i(Smi::FromInt(i), isolate);
1263 : Handle<Smi> value_i(Smi::FromInt(i), isolate);
1264 5120 : map = OrderedHashMapHandler::Add(isolate, map, key_i, value_i);
1265 : Verify(isolate, map);
1266 5253120 : for (int j = 0; j <= i; j++) {
1267 : Handle<Smi> key_j(Smi::FromInt(j), isolate);
1268 2624000 : CHECK(OrderedHashMapHandler::HasKey(isolate, map, key_j));
1269 : }
1270 : }
1271 5 : CHECK(OrderedHashMap::Is(map));
1272 5 : }
1273 :
1274 26644 : TEST(OrderedNameDictionaryInsertion) {
1275 5 : LocalContext context;
1276 : Isolate* isolate = GetIsolateFrom(&context);
1277 : Factory* factory = isolate->factory();
1278 : HandleScope scope(isolate);
1279 :
1280 5 : Handle<OrderedNameDictionary> dict = factory->NewOrderedNameDictionary();
1281 : Verify(isolate, dict);
1282 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1283 5 : CHECK_EQ(0, dict->NumberOfElements());
1284 :
1285 5 : Handle<String> key1 = isolate->factory()->InternalizeUtf8String("foo");
1286 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1287 10 : CHECK_EQ(OrderedNameDictionary::kNotFound, dict->FindEntry(isolate, *key1));
1288 5 : PropertyDetails details = PropertyDetails::Empty();
1289 5 : dict = OrderedNameDictionary::Add(isolate, dict, key1, value, details);
1290 : Verify(isolate, dict);
1291 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1292 5 : CHECK_EQ(1, dict->NumberOfElements());
1293 :
1294 10 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1295 :
1296 5 : Handle<Symbol> key2 = factory->NewSymbol();
1297 10 : CHECK_EQ(OrderedNameDictionary::kNotFound, dict->FindEntry(isolate, *key2));
1298 5 : dict = OrderedNameDictionary::Add(isolate, dict, key2, value, details);
1299 : Verify(isolate, dict);
1300 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1301 5 : CHECK_EQ(2, dict->NumberOfElements());
1302 10 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1303 10 : CHECK_EQ(1, dict->FindEntry(isolate, *key2));
1304 5 : }
1305 :
1306 26644 : TEST(OrderedNameDictionaryFindEntry) {
1307 5 : LocalContext context;
1308 : Isolate* isolate = GetIsolateFrom(&context);
1309 : Factory* factory = isolate->factory();
1310 : HandleScope scope(isolate);
1311 :
1312 5 : Handle<OrderedNameDictionary> dict = factory->NewOrderedNameDictionary();
1313 : Verify(isolate, dict);
1314 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1315 5 : CHECK_EQ(0, dict->NumberOfElements());
1316 :
1317 5 : Handle<String> key1 = isolate->factory()->InternalizeUtf8String("foo");
1318 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1319 5 : PropertyDetails details = PropertyDetails::Empty();
1320 5 : dict = OrderedNameDictionary::Add(isolate, dict, key1, value, details);
1321 : Verify(isolate, dict);
1322 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1323 5 : CHECK_EQ(1, dict->NumberOfElements());
1324 :
1325 10 : int entry = dict->FindEntry(isolate, *key1);
1326 5 : CHECK_EQ(entry, 0);
1327 5 : CHECK_NE(entry, OrderedNameDictionary::kNotFound);
1328 :
1329 5 : Handle<Symbol> key2 = factory->NewSymbol();
1330 5 : dict = OrderedNameDictionary::Add(isolate, dict, key2, value, details);
1331 : Verify(isolate, dict);
1332 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1333 5 : CHECK_EQ(2, dict->NumberOfElements());
1334 :
1335 10 : entry = dict->FindEntry(isolate, *key1);
1336 5 : CHECK_NE(entry, OrderedNameDictionary::kNotFound);
1337 5 : CHECK_EQ(entry, 0);
1338 :
1339 10 : entry = dict->FindEntry(isolate, *key2);
1340 5 : CHECK_NE(entry, OrderedNameDictionary::kNotFound);
1341 5 : CHECK_EQ(entry, 1);
1342 5 : }
1343 :
1344 26644 : TEST(OrderedNameDictionaryValueAtAndValueAtPut) {
1345 5 : LocalContext context;
1346 : Isolate* isolate = GetIsolateFrom(&context);
1347 : Factory* factory = isolate->factory();
1348 : HandleScope scope(isolate);
1349 :
1350 5 : Handle<OrderedNameDictionary> dict = factory->NewOrderedNameDictionary();
1351 : Verify(isolate, dict);
1352 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1353 5 : CHECK_EQ(0, dict->NumberOfElements());
1354 :
1355 5 : Handle<String> key1 = isolate->factory()->InternalizeUtf8String("foo");
1356 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1357 10 : CHECK_EQ(OrderedNameDictionary::kNotFound, dict->FindEntry(isolate, *key1));
1358 5 : PropertyDetails details = PropertyDetails::Empty();
1359 5 : dict = OrderedNameDictionary::Add(isolate, dict, key1, value, details);
1360 : Verify(isolate, dict);
1361 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1362 5 : CHECK_EQ(1, dict->NumberOfElements());
1363 10 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1364 :
1365 10 : int entry = dict->FindEntry(isolate, *key1);
1366 10 : Handle<Object> found = handle(dict->ValueAt(entry), isolate);
1367 5 : CHECK_EQ(*found, *value);
1368 :
1369 : // Change the value
1370 5 : Handle<String> other_value = isolate->factory()->InternalizeUtf8String("baz");
1371 10 : dict->ValueAtPut(entry, *other_value);
1372 :
1373 10 : entry = dict->FindEntry(isolate, *key1);
1374 10 : found = handle(dict->ValueAt(entry), isolate);
1375 5 : CHECK_EQ(*found, *other_value);
1376 :
1377 5 : Handle<Symbol> key2 = factory->NewSymbol();
1378 10 : CHECK_EQ(OrderedNameDictionary::kNotFound, dict->FindEntry(isolate, *key2));
1379 5 : dict = OrderedNameDictionary::Add(isolate, dict, key2, value, details);
1380 : Verify(isolate, dict);
1381 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1382 5 : CHECK_EQ(2, dict->NumberOfElements());
1383 10 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1384 10 : CHECK_EQ(1, dict->FindEntry(isolate, *key2));
1385 :
1386 10 : entry = dict->FindEntry(isolate, *key1);
1387 10 : found = handle(dict->ValueAt(entry), isolate);
1388 5 : CHECK_EQ(*found, *other_value);
1389 :
1390 10 : entry = dict->FindEntry(isolate, *key2);
1391 10 : found = handle(dict->ValueAt(entry), isolate);
1392 5 : CHECK_EQ(*found, *value);
1393 :
1394 : // Change the value
1395 10 : dict->ValueAtPut(entry, *other_value);
1396 :
1397 10 : entry = dict->FindEntry(isolate, *key1);
1398 10 : found = handle(dict->ValueAt(entry), isolate);
1399 5 : CHECK_EQ(*found, *other_value);
1400 5 : }
1401 :
1402 26644 : TEST(OrderedNameDictionaryDetailsAtAndDetailsAtPut) {
1403 5 : LocalContext context;
1404 : Isolate* isolate = GetIsolateFrom(&context);
1405 : Factory* factory = isolate->factory();
1406 : HandleScope scope(isolate);
1407 :
1408 5 : Handle<OrderedNameDictionary> dict = factory->NewOrderedNameDictionary();
1409 : Verify(isolate, dict);
1410 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1411 5 : CHECK_EQ(0, dict->NumberOfElements());
1412 :
1413 5 : Handle<String> key1 = isolate->factory()->InternalizeUtf8String("foo");
1414 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1415 10 : CHECK_EQ(OrderedNameDictionary::kNotFound, dict->FindEntry(isolate, *key1));
1416 5 : PropertyDetails details = PropertyDetails::Empty();
1417 5 : dict = OrderedNameDictionary::Add(isolate, dict, key1, value, details);
1418 : Verify(isolate, dict);
1419 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1420 5 : CHECK_EQ(1, dict->NumberOfElements());
1421 10 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1422 :
1423 10 : int entry = dict->FindEntry(isolate, *key1);
1424 5 : PropertyDetails found = dict->DetailsAt(entry);
1425 5 : CHECK_EQ(PropertyDetails::Empty().AsSmi(), found.AsSmi());
1426 :
1427 : PropertyDetails other =
1428 : PropertyDetails(kAccessor, READ_ONLY, PropertyCellType::kNoCell);
1429 5 : dict->DetailsAtPut(entry, other);
1430 :
1431 5 : found = dict->DetailsAt(entry);
1432 5 : CHECK_NE(PropertyDetails::Empty().AsSmi(), found.AsSmi());
1433 5 : CHECK_EQ(other.AsSmi(), found.AsSmi());
1434 :
1435 5 : Handle<Symbol> key2 = factory->NewSymbol();
1436 10 : CHECK_EQ(OrderedNameDictionary::kNotFound, dict->FindEntry(isolate, *key2));
1437 5 : dict = OrderedNameDictionary::Add(isolate, dict, key2, value, details);
1438 : Verify(isolate, dict);
1439 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1440 5 : CHECK_EQ(2, dict->NumberOfElements());
1441 10 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1442 10 : CHECK_EQ(1, dict->FindEntry(isolate, *key2));
1443 :
1444 10 : entry = dict->FindEntry(isolate, *key1);
1445 5 : found = dict->DetailsAt(entry);
1446 5 : CHECK_EQ(other.AsSmi(), found.AsSmi());
1447 5 : CHECK_NE(PropertyDetails::Empty().AsSmi(), found.AsSmi());
1448 :
1449 10 : entry = dict->FindEntry(isolate, *key2);
1450 5 : dict->DetailsAtPut(entry, other);
1451 :
1452 5 : found = dict->DetailsAt(entry);
1453 5 : CHECK_NE(PropertyDetails::Empty().AsSmi(), found.AsSmi());
1454 5 : CHECK_EQ(other.AsSmi(), found.AsSmi());
1455 5 : }
1456 :
1457 26644 : TEST(SmallOrderedNameDictionaryInsertion) {
1458 5 : LocalContext context;
1459 : Isolate* isolate = GetIsolateFrom(&context);
1460 : Factory* factory = isolate->factory();
1461 : HandleScope scope(isolate);
1462 :
1463 : Handle<SmallOrderedNameDictionary> dict =
1464 5 : factory->NewSmallOrderedNameDictionary();
1465 : Verify(isolate, dict);
1466 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1467 5 : CHECK_EQ(0, dict->NumberOfElements());
1468 :
1469 5 : Handle<String> key1 = isolate->factory()->InternalizeUtf8String("foo");
1470 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1471 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1472 : dict->FindEntry(isolate, *key1));
1473 5 : PropertyDetails details = PropertyDetails::Empty();
1474 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key1, value, details)
1475 : .ToHandleChecked();
1476 : Verify(isolate, dict);
1477 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1478 5 : CHECK_EQ(1, dict->NumberOfElements());
1479 5 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1480 :
1481 5 : Handle<Symbol> key2 = factory->NewSymbol();
1482 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1483 : dict->FindEntry(isolate, *key2));
1484 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key2, value, details)
1485 : .ToHandleChecked();
1486 : Verify(isolate, dict);
1487 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1488 5 : CHECK_EQ(2, dict->NumberOfElements());
1489 5 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1490 10 : CHECK_EQ(1, dict->FindEntry(isolate, *key2));
1491 5 : }
1492 :
1493 26644 : TEST(SmallOrderedNameDictionaryInsertionMax) {
1494 5 : LocalContext context;
1495 : Isolate* isolate = GetIsolateFrom(&context);
1496 : Factory* factory = isolate->factory();
1497 : HandleScope scope(isolate);
1498 : Handle<SmallOrderedNameDictionary> dict =
1499 5 : factory->NewSmallOrderedNameDictionary();
1500 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1501 5 : PropertyDetails details = PropertyDetails::Empty();
1502 :
1503 : char buf[10];
1504 2545 : for (int i = 0; i < SmallOrderedNameDictionary::kMaxCapacity; i++) {
1505 1270 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", i));
1506 1270 : Handle<String> key = isolate->factory()->InternalizeUtf8String(buf);
1507 2540 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key, value, details)
1508 : .ToHandleChecked();
1509 : Verify(isolate, dict);
1510 : }
1511 :
1512 5 : CHECK_EQ(SmallOrderedNameDictionary::kMaxCapacity /
1513 : SmallOrderedNameDictionary::kLoadFactor,
1514 : dict->NumberOfBuckets());
1515 5 : CHECK_EQ(SmallOrderedNameDictionary::kMaxCapacity, dict->NumberOfElements());
1516 :
1517 : // This should overflow and fail.
1518 10 : CHECK(SmallOrderedNameDictionary::Add(isolate, dict, value, value, details)
1519 : .is_null());
1520 5 : }
1521 :
1522 26644 : TEST(SmallOrderedNameDictionaryFindEntry) {
1523 5 : LocalContext context;
1524 : Isolate* isolate = GetIsolateFrom(&context);
1525 : Factory* factory = isolate->factory();
1526 : HandleScope scope(isolate);
1527 :
1528 : Handle<SmallOrderedNameDictionary> dict =
1529 5 : factory->NewSmallOrderedNameDictionary();
1530 : Verify(isolate, dict);
1531 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1532 5 : CHECK_EQ(0, dict->NumberOfElements());
1533 :
1534 5 : Handle<String> key1 = isolate->factory()->InternalizeUtf8String("foo");
1535 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1536 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1537 : dict->FindEntry(isolate, *key1));
1538 5 : PropertyDetails details = PropertyDetails::Empty();
1539 :
1540 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key1, value, details)
1541 : .ToHandleChecked();
1542 : Verify(isolate, dict);
1543 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1544 5 : CHECK_EQ(1, dict->NumberOfElements());
1545 5 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1546 :
1547 10 : int entry = dict->FindEntry(isolate, *key1);
1548 5 : CHECK_NE(entry, OrderedNameDictionary::kNotFound);
1549 :
1550 5 : Handle<Symbol> key2 = factory->NewSymbol();
1551 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1552 : dict->FindEntry(isolate, *key2));
1553 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key2, value, details)
1554 : .ToHandleChecked();
1555 : Verify(isolate, dict);
1556 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1557 5 : CHECK_EQ(2, dict->NumberOfElements());
1558 :
1559 5 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1560 10 : CHECK_EQ(1, dict->FindEntry(isolate, *key2));
1561 5 : }
1562 :
1563 26644 : TEST(SmallOrderedNameDictionaryValueAtAndValueAtPut) {
1564 5 : LocalContext context;
1565 : Isolate* isolate = GetIsolateFrom(&context);
1566 : Factory* factory = isolate->factory();
1567 : HandleScope scope(isolate);
1568 :
1569 : Handle<SmallOrderedNameDictionary> dict =
1570 5 : factory->NewSmallOrderedNameDictionary();
1571 : Verify(isolate, dict);
1572 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1573 5 : CHECK_EQ(0, dict->NumberOfElements());
1574 :
1575 5 : Handle<String> key1 = isolate->factory()->InternalizeUtf8String("foo");
1576 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1577 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1578 : dict->FindEntry(isolate, *key1));
1579 5 : PropertyDetails details = PropertyDetails::Empty();
1580 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key1, value, details)
1581 : .ToHandleChecked();
1582 : Verify(isolate, dict);
1583 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1584 5 : CHECK_EQ(1, dict->NumberOfElements());
1585 5 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1586 :
1587 10 : int entry = dict->FindEntry(isolate, *key1);
1588 : Handle<Object> found = handle(dict->ValueAt(entry), isolate);
1589 5 : CHECK_EQ(*found, *value);
1590 :
1591 : // Change the value
1592 5 : Handle<String> other_value = isolate->factory()->InternalizeUtf8String("baz");
1593 10 : dict->ValueAtPut(entry, *other_value);
1594 :
1595 10 : entry = dict->FindEntry(isolate, *key1);
1596 : found = handle(dict->ValueAt(entry), isolate);
1597 5 : CHECK_EQ(*found, *other_value);
1598 :
1599 5 : Handle<Symbol> key2 = factory->NewSymbol();
1600 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1601 : dict->FindEntry(isolate, *key2));
1602 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key2, value, details)
1603 : .ToHandleChecked();
1604 : Verify(isolate, dict);
1605 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1606 5 : CHECK_EQ(2, dict->NumberOfElements());
1607 5 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1608 10 : CHECK_EQ(1, dict->FindEntry(isolate, *key2));
1609 :
1610 10 : entry = dict->FindEntry(isolate, *key1);
1611 : found = handle(dict->ValueAt(entry), isolate);
1612 5 : CHECK_EQ(*found, *other_value);
1613 :
1614 10 : entry = dict->FindEntry(isolate, *key2);
1615 : found = handle(dict->ValueAt(entry), isolate);
1616 5 : CHECK_EQ(*found, *value);
1617 :
1618 : // Change the value
1619 10 : dict->ValueAtPut(entry, *other_value);
1620 :
1621 10 : entry = dict->FindEntry(isolate, *key1);
1622 : found = handle(dict->ValueAt(entry), isolate);
1623 5 : CHECK_EQ(*found, *other_value);
1624 5 : }
1625 :
1626 26644 : TEST(SmallOrderedNameDictionaryDetailsAtAndDetailsAtPut) {
1627 5 : LocalContext context;
1628 : Isolate* isolate = GetIsolateFrom(&context);
1629 : Factory* factory = isolate->factory();
1630 : HandleScope scope(isolate);
1631 :
1632 : Handle<SmallOrderedNameDictionary> dict =
1633 5 : factory->NewSmallOrderedNameDictionary();
1634 : Verify(isolate, dict);
1635 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1636 5 : CHECK_EQ(0, dict->NumberOfElements());
1637 :
1638 5 : Handle<String> key1 = isolate->factory()->InternalizeUtf8String("foo");
1639 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1640 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1641 : dict->FindEntry(isolate, *key1));
1642 5 : PropertyDetails details = PropertyDetails::Empty();
1643 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key1, value, details)
1644 : .ToHandleChecked();
1645 : Verify(isolate, dict);
1646 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1647 5 : CHECK_EQ(1, dict->NumberOfElements());
1648 5 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1649 :
1650 10 : int entry = dict->FindEntry(isolate, *key1);
1651 : PropertyDetails found = dict->DetailsAt(entry);
1652 5 : CHECK_EQ(PropertyDetails::Empty().AsSmi(), found.AsSmi());
1653 :
1654 : PropertyDetails other =
1655 : PropertyDetails(kAccessor, READ_ONLY, PropertyCellType::kNoCell);
1656 10 : dict->DetailsAtPut(entry, other);
1657 :
1658 : found = dict->DetailsAt(entry);
1659 5 : CHECK_NE(PropertyDetails::Empty().AsSmi(), found.AsSmi());
1660 5 : CHECK_EQ(other.AsSmi(), found.AsSmi());
1661 :
1662 5 : Handle<Symbol> key2 = factory->NewSymbol();
1663 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1664 : dict->FindEntry(isolate, *key2));
1665 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key2, value, details)
1666 : .ToHandleChecked();
1667 : Verify(isolate, dict);
1668 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1669 5 : CHECK_EQ(2, dict->NumberOfElements());
1670 5 : CHECK_EQ(0, dict->FindEntry(isolate, *key1));
1671 10 : CHECK_EQ(1, dict->FindEntry(isolate, *key2));
1672 :
1673 10 : entry = dict->FindEntry(isolate, *key1);
1674 : found = dict->DetailsAt(entry);
1675 5 : CHECK_NE(PropertyDetails::Empty().AsSmi(), found.AsSmi());
1676 5 : CHECK_EQ(other.AsSmi(), found.AsSmi());
1677 :
1678 10 : entry = dict->FindEntry(isolate, *key2);
1679 10 : dict->DetailsAtPut(entry, other);
1680 :
1681 : found = dict->DetailsAt(entry);
1682 5 : CHECK_NE(PropertyDetails::Empty().AsSmi(), found.AsSmi());
1683 5 : CHECK_EQ(other.AsSmi(), found.AsSmi());
1684 5 : }
1685 :
1686 26644 : TEST(SmallOrderedNameDictionarySetAndMigrateHash) {
1687 5 : LocalContext context;
1688 : Isolate* isolate = GetIsolateFrom(&context);
1689 : Factory* factory = isolate->factory();
1690 : HandleScope scope(isolate);
1691 : Handle<SmallOrderedNameDictionary> dict =
1692 5 : factory->NewSmallOrderedNameDictionary();
1693 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1694 5 : PropertyDetails details = PropertyDetails::Empty();
1695 :
1696 5 : CHECK_EQ(PropertyArray::kNoHashSentinel, dict->Hash());
1697 : dict->SetHash(100);
1698 5 : CHECK_EQ(100, dict->Hash());
1699 :
1700 : char buf[10];
1701 2545 : for (int i = 0; i < SmallOrderedNameDictionary::kMaxCapacity; i++) {
1702 1270 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", i));
1703 1270 : Handle<String> key = isolate->factory()->InternalizeUtf8String(buf);
1704 2540 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key, value, details)
1705 : .ToHandleChecked();
1706 : Verify(isolate, dict);
1707 1270 : CHECK_EQ(100, dict->Hash());
1708 : }
1709 5 : }
1710 :
1711 26644 : TEST(OrderedNameDictionarySetAndMigrateHash) {
1712 5 : LocalContext context;
1713 : Isolate* isolate = GetIsolateFrom(&context);
1714 : Factory* factory = isolate->factory();
1715 : HandleScope scope(isolate);
1716 5 : Handle<OrderedNameDictionary> dict = factory->NewOrderedNameDictionary();
1717 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1718 5 : PropertyDetails details = PropertyDetails::Empty();
1719 :
1720 5 : CHECK_EQ(PropertyArray::kNoHashSentinel, dict->Hash());
1721 : dict->SetHash(100);
1722 5 : CHECK_EQ(100, dict->Hash());
1723 :
1724 : char buf[10];
1725 10255 : for (int i = 0; i <= 1024; i++) {
1726 5125 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", i));
1727 5125 : Handle<String> key = isolate->factory()->InternalizeUtf8String(buf);
1728 5125 : dict = OrderedNameDictionary::Add(isolate, dict, key, value, details);
1729 : Verify(isolate, dict);
1730 5125 : CHECK_EQ(100, dict->Hash());
1731 : }
1732 5 : }
1733 :
1734 26644 : TEST(OrderedNameDictionaryHandlerInsertion) {
1735 5 : LocalContext context;
1736 : Isolate* isolate = GetIsolateFrom(&context);
1737 : HandleScope scope(isolate);
1738 :
1739 5 : Handle<HeapObject> table = OrderedNameDictionaryHandler::Allocate(isolate, 4);
1740 5 : CHECK(table->IsSmallOrderedNameDictionary());
1741 : Verify(isolate, table);
1742 :
1743 : // Add a new key.
1744 5 : Handle<String> value = isolate->factory()->InternalizeUtf8String("bar");
1745 5 : Handle<String> key = isolate->factory()->InternalizeUtf8String("foo");
1746 5 : PropertyDetails details = PropertyDetails::Empty();
1747 :
1748 : table =
1749 5 : OrderedNameDictionaryHandler::Add(isolate, table, key, value, details);
1750 : DCHECK(key->IsUniqueName());
1751 : Verify(isolate, table);
1752 5 : CHECK(table->IsSmallOrderedNameDictionary());
1753 10 : CHECK_NE(OrderedNameDictionaryHandler::kNotFound,
1754 : OrderedNameDictionaryHandler::FindEntry(isolate, *table, *key));
1755 :
1756 : char buf[10];
1757 5125 : for (int i = 0; i < 1024; i++) {
1758 5120 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", i));
1759 5120 : key = isolate->factory()->InternalizeUtf8String(buf);
1760 : table =
1761 5120 : OrderedNameDictionaryHandler::Add(isolate, table, key, value, details);
1762 : DCHECK(key->IsUniqueName());
1763 : Verify(isolate, table);
1764 :
1765 5253120 : for (int j = 0; j <= i; j++) {
1766 2624000 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", j));
1767 2624000 : Handle<Name> key_j = isolate->factory()->InternalizeUtf8String(buf);
1768 2624000 : CHECK_NE(
1769 : OrderedNameDictionaryHandler::kNotFound,
1770 : OrderedNameDictionaryHandler::FindEntry(isolate, *table, *key_j));
1771 : }
1772 :
1773 2624000 : for (int j = i + 1; j < 1024; j++) {
1774 2618880 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", j));
1775 2618880 : Handle<Name> key_j = isolate->factory()->InternalizeUtf8String(buf);
1776 2618880 : CHECK_EQ(
1777 : OrderedNameDictionaryHandler::kNotFound,
1778 : OrderedNameDictionaryHandler::FindEntry(isolate, *table, *key_j));
1779 : }
1780 : }
1781 :
1782 5 : CHECK(table->IsOrderedNameDictionary());
1783 5 : }
1784 :
1785 26644 : TEST(OrderedNameDictionarySetEntry) {
1786 5 : LocalContext context;
1787 : Isolate* isolate = GetIsolateFrom(&context);
1788 : Factory* factory = isolate->factory();
1789 : HandleScope scope(isolate);
1790 :
1791 5 : Handle<OrderedNameDictionary> dict = factory->NewOrderedNameDictionary();
1792 : Verify(isolate, dict);
1793 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1794 5 : CHECK_EQ(0, dict->NumberOfElements());
1795 5 : CHECK_EQ(0, dict->NumberOfDeletedElements());
1796 :
1797 5 : Handle<String> key = factory->InternalizeUtf8String("foo");
1798 5 : Handle<String> value = factory->InternalizeUtf8String("bar");
1799 10 : CHECK_EQ(OrderedNameDictionary::kNotFound, dict->FindEntry(isolate, *key));
1800 5 : PropertyDetails details = PropertyDetails::Empty();
1801 5 : dict = OrderedNameDictionary::Add(isolate, dict, key, value, details);
1802 : Verify(isolate, dict);
1803 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1804 5 : CHECK_EQ(1, dict->NumberOfElements());
1805 :
1806 10 : int entry = dict->FindEntry(isolate, *key);
1807 5 : CHECK_EQ(0, entry);
1808 10 : Handle<Object> found = handle(dict->ValueAt(entry), isolate);
1809 5 : CHECK_EQ(*found, *value);
1810 :
1811 : // Change the value
1812 5 : Handle<String> other_value = isolate->factory()->InternalizeUtf8String("baz");
1813 : PropertyDetails other_details =
1814 : PropertyDetails(kAccessor, READ_ONLY, PropertyCellType::kNoCell);
1815 15 : dict->SetEntry(isolate, entry, *key, *other_value, other_details);
1816 :
1817 10 : entry = dict->FindEntry(isolate, *key);
1818 5 : CHECK_EQ(0, entry);
1819 10 : found = handle(dict->ValueAt(entry), isolate);
1820 5 : CHECK_EQ(*found, *other_value);
1821 10 : found = handle(dict->KeyAt(entry), isolate);
1822 5 : CHECK_EQ(*found, *key);
1823 5 : PropertyDetails found_details = dict->DetailsAt(entry);
1824 5 : CHECK_EQ(found_details.AsSmi(), other_details.AsSmi());
1825 5 : }
1826 :
1827 26644 : TEST(SmallOrderedNameDictionarySetEntry) {
1828 5 : LocalContext context;
1829 : Isolate* isolate = GetIsolateFrom(&context);
1830 : Factory* factory = isolate->factory();
1831 : HandleScope scope(isolate);
1832 :
1833 : Handle<SmallOrderedNameDictionary> dict =
1834 5 : factory->NewSmallOrderedNameDictionary();
1835 : Verify(isolate, dict);
1836 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1837 5 : CHECK_EQ(0, dict->NumberOfElements());
1838 :
1839 5 : Handle<String> key = factory->InternalizeUtf8String("foo");
1840 5 : Handle<String> value = factory->InternalizeUtf8String("bar");
1841 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1842 : dict->FindEntry(isolate, *key));
1843 5 : PropertyDetails details = PropertyDetails::Empty();
1844 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key, value, details)
1845 : .ToHandleChecked();
1846 : Verify(isolate, dict);
1847 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1848 5 : CHECK_EQ(1, dict->NumberOfElements());
1849 5 : CHECK_EQ(0, dict->NumberOfDeletedElements());
1850 :
1851 5 : int entry = dict->FindEntry(isolate, *key);
1852 5 : CHECK_EQ(0, entry);
1853 : Handle<Object> found = handle(dict->ValueAt(entry), isolate);
1854 5 : CHECK_EQ(*found, *value);
1855 :
1856 : // Change the value
1857 5 : Handle<String> other_value = factory->InternalizeUtf8String("baz");
1858 : PropertyDetails other_details =
1859 : PropertyDetails(kAccessor, READ_ONLY, PropertyCellType::kNoCell);
1860 15 : dict->SetEntry(isolate, entry, *key, *other_value, other_details);
1861 :
1862 10 : entry = dict->FindEntry(isolate, *key);
1863 5 : CHECK_EQ(0, entry);
1864 : found = handle(dict->ValueAt(entry), isolate);
1865 5 : CHECK_EQ(*found, *other_value);
1866 10 : found = handle(dict->KeyAt(entry), isolate);
1867 5 : CHECK_EQ(*found, *key);
1868 : PropertyDetails found_details = dict->DetailsAt(entry);
1869 5 : CHECK_EQ(found_details.AsSmi(), other_details.AsSmi());
1870 5 : }
1871 :
1872 26644 : TEST(OrderedNameDictionaryDeleteEntry) {
1873 5 : LocalContext context;
1874 : Isolate* isolate = GetIsolateFrom(&context);
1875 : Factory* factory = isolate->factory();
1876 : HandleScope scope(isolate);
1877 :
1878 5 : Handle<OrderedNameDictionary> dict = factory->NewOrderedNameDictionary();
1879 : Verify(isolate, dict);
1880 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1881 5 : CHECK_EQ(0, dict->NumberOfElements());
1882 :
1883 5 : Handle<String> key = factory->InternalizeUtf8String("foo");
1884 5 : Handle<String> value = factory->InternalizeUtf8String("bar");
1885 10 : CHECK_EQ(OrderedNameDictionary::kNotFound, dict->FindEntry(isolate, *key));
1886 5 : PropertyDetails details = PropertyDetails::Empty();
1887 5 : dict = OrderedNameDictionary::Add(isolate, dict, key, value, details);
1888 : Verify(isolate, dict);
1889 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1890 5 : CHECK_EQ(1, dict->NumberOfElements());
1891 5 : CHECK_EQ(0, dict->NumberOfDeletedElements());
1892 :
1893 10 : int entry = dict->FindEntry(isolate, *key);
1894 5 : CHECK_EQ(0, entry);
1895 5 : dict = OrderedNameDictionary::DeleteEntry(isolate, dict, entry);
1896 10 : entry = dict->FindEntry(isolate, *key);
1897 5 : CHECK_EQ(OrderedNameDictionary::kNotFound, entry);
1898 5 : CHECK_EQ(0, dict->NumberOfElements());
1899 :
1900 : char buf[10];
1901 : // Make sure we grow at least once.
1902 5 : CHECK_LT(OrderedNameDictionaryHandler::Capacity(*dict), 100);
1903 1005 : for (int i = 0; i < 100; i++) {
1904 500 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", i));
1905 500 : key = factory->InternalizeUtf8String(buf);
1906 500 : dict = OrderedNameDictionary::Add(isolate, dict, key, value, details);
1907 : DCHECK(key->IsUniqueName());
1908 : Verify(isolate, dict);
1909 : }
1910 :
1911 5 : CHECK_EQ(100, dict->NumberOfElements());
1912 : // Initial dictionary has grown.
1913 5 : CHECK_EQ(0, dict->NumberOfDeletedElements());
1914 :
1915 1005 : for (int i = 0; i < 100; i++) {
1916 500 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", i));
1917 500 : key = factory->InternalizeUtf8String(buf);
1918 1000 : entry = dict->FindEntry(isolate, *key);
1919 :
1920 500 : dict = OrderedNameDictionary::DeleteEntry(isolate, dict, entry);
1921 : Verify(isolate, dict);
1922 :
1923 1000 : entry = dict->FindEntry(isolate, *key);
1924 500 : CHECK_EQ(OrderedNameDictionary::kNotFound, entry);
1925 : }
1926 5 : CHECK_EQ(0, dict->NumberOfElements());
1927 : // Dictionary shrunk again.
1928 5 : CHECK_EQ(0, dict->NumberOfDeletedElements());
1929 5 : }
1930 :
1931 26644 : TEST(SmallOrderedNameDictionaryDeleteEntry) {
1932 5 : LocalContext context;
1933 : Isolate* isolate = GetIsolateFrom(&context);
1934 : Factory* factory = isolate->factory();
1935 : HandleScope scope(isolate);
1936 :
1937 : Handle<SmallOrderedNameDictionary> dict =
1938 5 : factory->NewSmallOrderedNameDictionary();
1939 : Verify(isolate, dict);
1940 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1941 5 : CHECK_EQ(0, dict->NumberOfElements());
1942 :
1943 5 : Handle<String> key = factory->InternalizeUtf8String("foo");
1944 5 : Handle<String> value = factory->InternalizeUtf8String("bar");
1945 15 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound,
1946 : dict->FindEntry(isolate, *key));
1947 5 : PropertyDetails details = PropertyDetails::Empty();
1948 10 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key, value, details)
1949 : .ToHandleChecked();
1950 : Verify(isolate, dict);
1951 5 : CHECK_EQ(2, dict->NumberOfBuckets());
1952 5 : CHECK_EQ(1, dict->NumberOfElements());
1953 5 : CHECK_EQ(0, dict->NumberOfDeletedElements());
1954 :
1955 5 : int entry = dict->FindEntry(isolate, *key);
1956 5 : CHECK_EQ(0, entry);
1957 5 : dict = SmallOrderedNameDictionary::DeleteEntry(isolate, dict, entry);
1958 10 : entry = dict->FindEntry(isolate, *key);
1959 5 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound, entry);
1960 :
1961 : char buf[10];
1962 : // Make sure we grow at least once.
1963 5 : CHECK_LT(dict->Capacity(), SmallOrderedNameDictionary::kMaxCapacity);
1964 :
1965 2545 : for (int i = 0; i < SmallOrderedNameDictionary::kMaxCapacity; i++) {
1966 1270 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", i));
1967 1270 : key = factory->InternalizeUtf8String(buf);
1968 2540 : dict = SmallOrderedNameDictionary::Add(isolate, dict, key, value, details)
1969 : .ToHandleChecked();
1970 : DCHECK(key->IsUniqueName());
1971 : Verify(isolate, dict);
1972 : }
1973 :
1974 5 : CHECK_EQ(SmallOrderedNameDictionary::kMaxCapacity, dict->NumberOfElements());
1975 : // Dictionary has grown.
1976 5 : CHECK_EQ(0, dict->NumberOfDeletedElements());
1977 :
1978 2545 : for (int i = 0; i < SmallOrderedNameDictionary::kMaxCapacity; i++) {
1979 1270 : CHECK_LT(0, snprintf(buf, sizeof(buf), "foo%d", i));
1980 1270 : key = factory->InternalizeUtf8String(buf);
1981 :
1982 2540 : entry = dict->FindEntry(isolate, *key);
1983 1270 : dict = SmallOrderedNameDictionary::DeleteEntry(isolate, dict, entry);
1984 : Verify(isolate, dict);
1985 :
1986 2540 : entry = dict->FindEntry(isolate, *key);
1987 1270 : CHECK_EQ(SmallOrderedNameDictionary::kNotFound, entry);
1988 : }
1989 :
1990 5 : CHECK_EQ(0, dict->NumberOfElements());
1991 : // Dictionary shrunk.
1992 5 : CHECK_EQ(0, dict->NumberOfDeletedElements());
1993 5 : }
1994 :
1995 : } // namespace test_orderedhashtable
1996 : } // namespace internal
1997 79917 : } // namespace v8
|
