OILS / mycpp / gc_dict_test.cc View on Github | oilshell.org

718 lines, 487 significant
1#include "mycpp/gc_dict.h"
2
3#include "mycpp/gc_mylib.h"
4#include "vendor/greatest.h"
5
6// Convenience function
7template <typename K, typename V>
8Dict<K, V>* NewDict() {
9 return Alloc<Dict<K, V>>();
10}
11
12GLOBAL_STR(kStrFoo, "foo");
13GLOBAL_STR(kStrBar, "bar");
14
15TEST test_dict_init() {
16 BigStr* s = StrFromC("foo");
17 BigStr* s2 = StrFromC("bar");
18
19 Dict<int, BigStr*>* d = Alloc<Dict<int, BigStr*>>(
20 std::initializer_list<int>{42}, std::initializer_list<BigStr*>{s});
21 ASSERT_EQ(s, d->at(42));
22
23 Dict<BigStr*, int>* d2 =
24 Alloc<Dict<BigStr*, int>>(std::initializer_list<BigStr*>{s, s2},
25 std::initializer_list<int>{43, 99});
26 ASSERT_EQ(43, d2->at(s));
27 ASSERT_EQ(99, d2->at(s2));
28
29 PASS();
30}
31
32TEST test_dict() {
33 Dict<int, BigStr*>* d = NewDict<int, BigStr*>();
34
35 // Regression: clear empty dict
36 d->clear();
37
38 d->set(1, StrFromC("foo"));
39 log("d[1] = %s", d->at(1)->data_);
40
41 auto d2 = NewDict<BigStr*, int>();
42 BigStr* key = StrFromC("key");
43 d2->set(key, 42);
44
45 log("d2['key'] = %d", d2->at(key));
46 d2->set(StrFromC("key2"), 2);
47 d2->set(StrFromC("key3"), 3);
48
49 ASSERT_EQ_FMT(3, len(d2), "%d");
50 ASSERT_EQ_FMT(3, len(d2->keys()), "%d");
51 ASSERT_EQ_FMT(3, len(d2->values()), "%d");
52
53 d2->clear();
54 ASSERT_EQ(0, len(d2));
55
56 log(" iterating over Dict");
57 for (DictIter<BigStr*, int> it(d2); !it.Done(); it.Next()) {
58 log("k = %s, v = %d", it.Key()->data_, it.Value());
59 }
60
61 ASSERT(dict_contains(d, 1));
62 ASSERT(!dict_contains(d, 423));
63
64 BigStr* v1 = d->get(1);
65 log("v1 = %s", v1->data_);
66 ASSERT(str_equals0("foo", v1));
67
68 BigStr* v2 = d->get(423); // nonexistent
69 ASSERT_EQ(nullptr, v2);
70 log("v2 = %p", v2);
71
72 auto d3 = NewDict<BigStr*, int>();
73 ASSERT_EQ(0, len(d3));
74
75 auto a = StrFromC("a");
76
77 d3->set(StrFromC("b"), 11);
78 ASSERT_EQ(1, len(d3));
79
80 d3->set(StrFromC("c"), 12);
81 ASSERT_EQ(2, len(d3));
82
83 d3->set(StrFromC("a"), 10);
84 ASSERT_EQ(3, len(d3));
85
86 ASSERT_EQ(10, d3->at(StrFromC("a")));
87 ASSERT_EQ(11, d3->at(StrFromC("b")));
88 ASSERT_EQ(12, d3->at(StrFromC("c")));
89 ASSERT_EQ(3, len(d3));
90
91 auto keys = sorted(d3);
92 ASSERT(str_equals0("a", keys->at(0)));
93 ASSERT(str_equals0("b", keys->at(1)));
94 ASSERT(str_equals0("c", keys->at(2)));
95 ASSERT_EQ(3, len(keys));
96
97 auto keys3 = d3->keys();
98 ASSERT(list_contains(keys3, a));
99 ASSERT(!list_contains(keys3, StrFromC("zzz")));
100
101 ASSERT(dict_contains(d3, a));
102 mylib::dict_erase(d3, a);
103 ASSERT(!dict_contains(d3, a));
104 ASSERT_EQ(2, len(d3));
105
106 // Test removed item
107 for (DictIter<BigStr*, int> it(d3); !it.Done(); it.Next()) {
108 auto key = it.Key();
109 printf("d3 key = ");
110 print(key);
111 }
112
113 // Test a different type of dict, to make sure partial template
114 // specialization works
115 auto ss = NewDict<BigStr*, BigStr*>();
116 ss->set(a, a);
117 ASSERT_EQ(1, len(ss));
118
119 ASSERT_EQ(1, len(ss->keys()));
120 ASSERT_EQ(1, len(ss->values()));
121
122 mylib::dict_erase(ss, a);
123 ASSERT_EQ(0, len(ss));
124
125 // Test removed item
126 for (DictIter<BigStr*, BigStr*> it(ss); !it.Done(); it.Next()) {
127 auto key = it.Key();
128 printf("ss key = ");
129 print(key);
130 }
131
132 // Testing NewDict() stub for ordered dicts ... hm.
133 //
134 // Dict<int, int>* frame = nullptr;
135 // frame = NewDict<int, int>();
136
137 PASS();
138}
139
140// TODO:
141// - Test set() can resize the dict
142// - I guess you have to do rehashing?
143
144TEST test_dict_internals() {
145 auto dict1 = NewDict<int, int>();
146 StackRoots _roots1({&dict1});
147 auto dict2 = NewDict<BigStr*, BigStr*>();
148 StackRoots _roots2({&dict2});
149
150 ASSERT_EQ(0, len(dict1));
151 ASSERT_EQ(0, len(dict2));
152
153 ASSERT_EQ_FMT(HeapTag::FixedSize, ObjHeader::FromObject(dict1)->heap_tag,
154 "%d");
155 ASSERT_EQ_FMT(HeapTag::FixedSize, ObjHeader::FromObject(dict1)->heap_tag,
156 "%d");
157
158 ASSERT_EQ_FMT(0, dict1->capacity_, "%d");
159 ASSERT_EQ_FMT(0, dict2->capacity_, "%d");
160
161 ASSERT_EQ(nullptr, dict1->index_);
162 ASSERT_EQ(nullptr, dict1->keys_);
163 ASSERT_EQ(nullptr, dict1->values_);
164
165 // Make sure they're on the heap
166#ifndef MARK_SWEEP
167 int diff1 = reinterpret_cast<char*>(dict1) - gHeap.from_space_.begin_;
168 int diff2 = reinterpret_cast<char*>(dict2) - gHeap.from_space_.begin_;
169 ASSERT(diff1 < 1024);
170 ASSERT(diff2 < 1024);
171#endif
172
173 dict1->set(42, 5);
174 ASSERT_EQ(5, dict1->at(42));
175 ASSERT_EQ(1, len(dict1));
176#if 0
177 ASSERT_EQ_FMT(6, dict1->capacity_, "%d");
178#endif
179
180#if 0
181 ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict1->index_)->obj_len, "%d");
182 ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict1->keys_)->obj_len, "%d");
183 ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict1->values_)->obj_len, "%d");
184#endif
185
186 dict1->set(42, 99);
187 ASSERT_EQ(99, dict1->at(42));
188 ASSERT_EQ(1, len(dict1));
189#if 0
190 ASSERT_EQ_FMT(6, dict1->capacity_, "%d");
191#endif
192
193 dict1->set(43, 10);
194 ASSERT_EQ(10, dict1->at(43));
195 ASSERT_EQ(2, len(dict1));
196#if 0
197 ASSERT_EQ_FMT(6, dict1->capacity_, "%d");
198#endif
199
200 // Dict<int, int>
201 // capacity: 6 -> 14 -> 30 -> ...
202 // index len: 9 -> 21 -> 45 -> ...
203
204 // 6 * 4 bytes = 24, plus 8 byte header = 32, which fits in the second pool
205 // 9 * 4 bytes = 36, plus 8 byte header = 44, which fits in the second pool
206 for (int i = 0; i < 14; ++i) {
207 dict1->set(i, i + 999);
208 log("len_ = %d, capacity = %d, index len %d", dict1->len_, dict1->capacity_,
209 dict1->index_len_);
210
211 // make sure we didn't lose old entry after resize
212 ASSERT_EQ(10, dict1->at(43));
213 }
214
215 BigStr* foo = nullptr;
216 BigStr* bar = nullptr;
217 StackRoots _roots3({&foo, &bar});
218 foo = StrFromC("foo");
219 bar = StrFromC("bar");
220
221 dict2->set(foo, bar);
222
223 ASSERT_EQ(1, len(dict2));
224 ASSERT(str_equals(bar, dict2->at(foo)));
225
226#if 0
227 ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict2->index_)->obj_len, "%d");
228 ASSERT_EQ_FMT(64, ObjHeader::FromObject(dict2->keys_)->obj_len, "%d");
229 ASSERT_EQ_FMT(64, ObjHeader::FromObject(dict2->values_)->obj_len, "%d");
230#endif
231
232 auto dict_si = NewDict<BigStr*, int>();
233 StackRoots _roots4({&dict_si});
234 dict_si->set(foo, 42);
235 ASSERT_EQ(1, len(dict_si));
236
237#if 0
238 ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict_si->index_)->obj_len, "%d");
239 ASSERT_EQ_FMT(64, ObjHeader::FromObject(dict_si->keys_)->obj_len, "%d");
240 ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict_si->values_)->obj_len, "%d");
241#endif
242
243 auto dict_is = NewDict<int, BigStr*>();
244 StackRoots _roots5({&dict_is});
245 dict_is->set(42, foo);
246 PASS();
247
248 ASSERT_EQ(1, len(dict_is));
249
250#if 0
251 ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict_is->index_)->obj_len, "%d");
252 ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict_is->keys_)->obj_len, "%d");
253 ASSERT_EQ_FMT(64, ObjHeader::FromObject(dict_is->values_)->obj_len, "%d");
254#endif
255
256 auto two = StrFromC("two");
257 StackRoots _roots6({&two});
258
259 auto dict3 = Alloc<Dict<int, BigStr*>>(
260 std::initializer_list<int>{1, 2},
261 std::initializer_list<BigStr*>{kEmptyString, two});
262 StackRoots _roots7({&dict3});
263
264 ASSERT_EQ_FMT(2, len(dict3), "%d");
265 ASSERT(str_equals(kEmptyString, dict3->get(1)));
266 ASSERT(str_equals(two, dict3->get(2)));
267
268 PASS();
269}
270
271TEST test_empty_dict() {
272 auto d = Alloc<Dict<BigStr*, BigStr*>>();
273
274 // Look up in empty dict
275 BigStr* val = d->get(StrFromC("nonexistent"));
276 log("val %p", val);
277 ASSERT_EQ(nullptr, val);
278
279 BigStr* val2 = d->get(StrFromC("nonexistent"), kEmptyString);
280 ASSERT_EQ(kEmptyString, val2);
281
282 PASS();
283}
284
285TEST dict_methods_test() {
286 Dict<int, BigStr*>* d = nullptr;
287 Dict<BigStr*, int>* d2 = nullptr;
288 BigStr* key = nullptr;
289 StackRoots _roots({&d, &d2, &key});
290
291 d = Alloc<Dict<int, BigStr*>>();
292 d->set(1, kStrFoo);
293 ASSERT(str_equals0("foo", d->at(1)));
294
295 d2 = Alloc<Dict<BigStr*, int>>();
296 key = StrFromC("key");
297 d2->set(key, 42);
298 ASSERT_EQ(42, d2->at(key));
299
300 PASS();
301
302 d2->set(StrFromC("key2"), 2);
303 d2->set(StrFromC("key3"), 3);
304
305 ASSERT_EQ_FMT(3, len(d2), "%d");
306
307 auto keys = d2->keys();
308 ASSERT_EQ_FMT(3, len(keys), "%d");
309
310 // Retain insertion order
311 ASSERT(str_equals0("key", keys->at(0)));
312 ASSERT(str_equals0("key2", keys->at(1)));
313 ASSERT(str_equals0("key3", keys->at(2)));
314
315 mylib::dict_erase(d2, StrFromC("key"));
316 ASSERT_EQ_FMT(2, len(d2), "%d");
317
318 auto keys2 = d2->keys();
319 ASSERT_EQ_FMT(2, len(keys2), "%d");
320 ASSERT(str_equals0("key2", keys2->at(0)));
321 ASSERT(str_equals0("key3", keys2->at(1)));
322
323 auto values = d2->values();
324 ASSERT_EQ_FMT(2, len(values), "%d");
325 ASSERT_EQ(2, values->at(0));
326 ASSERT_EQ(3, values->at(1));
327
328 int j = 0;
329 for (DictIter<BigStr*, int> it(d2); !it.Done(); it.Next()) {
330 auto key = it.Key();
331 auto value = it.Value();
332 log("d2 key = %s, value = %d", key->data_, value);
333 ++j;
334 }
335 ASSERT_EQ_FMT(len(d2), j, "%d");
336
337 d2->clear();
338 ASSERT_EQ(0, len(d2));
339 // Ensure it was zero'd
340 ASSERT_EQ(nullptr, d2->keys_->items_[0]);
341 ASSERT_EQ(0, d2->values_->items_[0]);
342
343 // get()
344 ASSERT(str_equals0("foo", d->get(1)));
345
346 // dict_contains()
347 ASSERT(dict_contains(d, 1));
348 ASSERT(!dict_contains(d, 2));
349
350 ASSERT_EQ(nullptr, d->get(423)); // nonexistent
351
352 // get(k, default)
353 ASSERT_EQ(kEmptyString, d->get(423, kEmptyString));
354 ASSERT_EQ(-99, d2->get(kEmptyString, -99));
355
356 // sorted()
357 auto d3 = Alloc<Dict<BigStr*, int>>();
358 auto a = StrFromC("a");
359
360 d3->set(StrFromC("b"), 11);
361 d3->set(StrFromC("c"), 12);
362 d3->set(StrFromC("a"), 10);
363 ASSERT_EQ(10, d3->at(StrFromC("a")));
364 ASSERT_EQ(11, d3->at(StrFromC("b")));
365 ASSERT_EQ(12, d3->at(StrFromC("c")));
366 ASSERT_EQ(3, len(d3));
367
368 auto keys3 = sorted(d3);
369 ASSERT_EQ(3, len(keys3));
370 ASSERT(str_equals0("a", keys3->at(0)));
371 ASSERT(str_equals0("b", keys3->at(1)));
372 ASSERT(str_equals0("c", keys3->at(2)));
373
374 auto keys4 = d3->keys();
375 ASSERT(list_contains(keys4, a));
376 ASSERT(!list_contains(keys4, StrFromC("zzz")));
377
378 ASSERT(dict_contains(d3, a));
379 mylib::dict_erase(d3, a);
380 ASSERT(!dict_contains(d3, a));
381 ASSERT_EQ(2, len(d3));
382
383 // Test a different type of dict, to make sure partial template
384 // specialization works
385 auto ss = Alloc<Dict<BigStr*, BigStr*>>();
386 ss->set(a, a);
387 ASSERT_EQ(1, len(ss));
388 ASSERT_EQ(1, len(ss->keys()));
389 ASSERT_EQ(1, len(ss->values()));
390
391 int k = 0;
392 for (DictIter<BigStr*, BigStr*> it(ss); !it.Done(); it.Next()) {
393 auto key = it.Key();
394 log("ss key = %s", key->data_);
395 ++k;
396 }
397 ASSERT_EQ_FMT(len(ss), k, "%d");
398
399 mylib::dict_erase(ss, a);
400 ASSERT_EQ(0, len(ss));
401
402 int m = 0;
403 for (DictIter<BigStr*, BigStr*> it(ss); !it.Done(); it.Next()) {
404 auto key = it.Key();
405 log("ss key = %s", key->data_);
406 ++m;
407 }
408 ASSERT_EQ_FMT(0, m, "%d");
409 ASSERT_EQ_FMT(len(ss), m, "%d");
410
411 PASS();
412}
413
414TEST dict_iters_test() {
415 Dict<BigStr*, int>* d2 = nullptr;
416 List<BigStr*>* keys = nullptr;
417 StackRoots _roots({&d2, &keys});
418
419 d2 = Alloc<Dict<BigStr*, int>>();
420 d2->set(kStrFoo, 2);
421 d2->set(kStrBar, 3);
422
423 keys = d2->keys();
424 for (int i = 0; i < len(keys); ++i) {
425 printf("k %s\n", keys->at(i)->data_);
426 }
427
428 log(" iterating over Dict");
429 for (DictIter<BigStr*, int> it(d2); !it.Done(); it.Next()) {
430 log("k = %s, v = %d", it.Key()->data_, it.Value());
431 }
432
433 PASS();
434}
435
436TEST test_tuple_construct() {
437 auto kvs = Alloc<List<Tuple2<int, int>*>>();
438 auto t1 = Alloc<Tuple2<int, int>>(0xdead, 0xbeef);
439 auto t2 = Alloc<Tuple2<int, int>>(0xbeee, 0xeeef);
440 kvs->append(t1);
441 kvs->append(t2);
442
443 auto d = dict(kvs);
444 ASSERT_EQ(d->at(0xdead), 0xbeef);
445 ASSERT_EQ(d->at(0xbeee), 0xeeef);
446
447 PASS();
448}
449
450TEST test_update_dict() {
451 auto d = Alloc<Dict<int, int>>();
452 d->set(1, 0xdead);
453 d->set(2, 0xbeef);
454 ASSERT_EQ(d->at(1), 0xdead);
455 ASSERT_EQ(d->at(2), 0xbeef);
456
457 auto kvs = Alloc<List<Tuple2<int, int>*>>();
458 auto t1 = Alloc<Tuple2<int, int>>(2, 0xfeeb);
459 auto t2 = Alloc<Tuple2<int, int>>(3, 0x3333);
460 kvs->append(t1);
461 kvs->append(t2);
462 d->update(kvs);
463 ASSERT_EQ(d->at(1), 0xdead);
464 ASSERT_EQ(d->at(2), 0xfeeb);
465 ASSERT_EQ(d->at(3), 0x3333);
466
467 PASS();
468}
469
470TEST test_tuple_key() {
471 auto d1 = Alloc<Dict<Tuple2<int, int>*, int>>();
472 auto t1 = Alloc<Tuple2<int, int>>(0xdead, 0xbeef);
473 auto t2 = Alloc<Tuple2<int, int>>(0xbeee, 0xeeef);
474 d1->set(t1, -42);
475 d1->set(t2, 17);
476 ASSERT_EQ(d1->at(t1), -42);
477 ASSERT_EQ(d1->at(t2), 17);
478
479 auto d2 = Alloc<Dict<Tuple2<BigStr*, int>*, int>>();
480 auto t3 = Alloc<Tuple2<BigStr*, int>>(StrFromC("foo"), 0xbeef);
481 auto t4 = Alloc<Tuple2<BigStr*, int>>(StrFromC("bar"), 0xeeef);
482 d2->set(t3, 12345);
483 d2->set(t4, 67890);
484 ASSERT_EQ(d2->at(t3), 12345);
485 ASSERT_EQ(d2->at(t4), 67890);
486
487 PASS();
488}
489
490TEST test_dict_erase() {
491 auto d = Alloc<Dict<int, int>>();
492 d->set(25315, 0xdead);
493 d->set(25316, 0xbeef);
494 d->set(25317, 0xc0ffee);
495
496 ASSERT_EQ(0xdead, d->at(25315));
497 ASSERT_EQ(0xbeef, d->at(25316));
498 ASSERT_EQ(0xc0ffee, d->at(25317));
499
500 mylib::dict_erase(d, 25315);
501 ASSERT_FALSE(dict_contains(d, 25315));
502 ASSERT_EQ(0xbeef, d->at(25316));
503 ASSERT_EQ(0xc0ffee, d->at(25317));
504
505 mylib::dict_erase(d, 25316);
506 ASSERT_FALSE(dict_contains(d, 25316));
507 ASSERT_EQ(0xc0ffee, d->at(25317));
508
509 // This is a trace of processes coming and going in a real shell. It tickles a
510 // (now fixed) bug in dict_erase() that would prematurely open a slot in the
511 // index before compacting the last inserted entry. With the right sequence of
512 // collisions (hence this trace) this behavior can lead to an index slot that
513 // points to an invalid entry, causing future calls to `find_key_in_index()`
514 // to crash (e.g. by dereferencing a bad pointer).
515 d = Alloc<Dict<int, int>>();
516 d->set(326224, 0);
517 d->set(326225, 1);
518 d->set(326226, 2);
519 d->set(326227, 3);
520 d->set(326228, 4);
521 mylib::dict_erase(d, 326227);
522 d->set(326229, 4);
523 d->set(326230, 5);
524 mylib::dict_erase(d, 326229);
525 d->set(326231, 5);
526 d->set(326232, 6);
527 mylib::dict_erase(d, 326231);
528 d->set(326233, 6);
529 d->set(326234, 7);
530 mylib::dict_erase(d, 326233);
531 d->set(326235, 7);
532 d->set(326236, 8);
533 mylib::dict_erase(d, 326235);
534 d->set(326237, 8);
535 d->set(326238, 9);
536 mylib::dict_erase(d, 326237);
537 d->set(326239, 9);
538 d->set(326240, 10);
539 mylib::dict_erase(d, 326239);
540 d->set(326241, 10);
541
542 PASS();
543}
544
545TEST test_dict_erase2() {
546 auto d = NewDict<int, BigStr*>();
547
548 for (int i = 0; i < 6; ++i) {
549 d->set(i, kEmptyString);
550 }
551 log("len(d) = %d", len(d));
552 ASSERT_EQ(6, len(d));
553
554 mylib::dict_erase(d, 99);
555 ASSERT_EQ(6, len(d));
556
557 PASS();
558}
559
560// Ints hash to themselves, so we can control when collisions happen. This test
561// sets up a few contrived workloads and checks that Dict still operates as
562// expected.
563TEST test_dict_probe() {
564 auto d = Alloc<Dict<int, int>>();
565
566 // This trace is a regression test for a weird bug where the index is full but
567 // the table has two free slots, causing a write to needlessly fail.
568 d->set(584818, -1);
569 d->set(584828, -1);
570 mylib::dict_erase(d, 584828);
571 d->set(584833, -1);
572 mylib::dict_erase(d, 584833);
573 d->set(584888, -1);
574
575 d->reserve(32);
576 d->clear();
577
578 // First, fill the table to the brim and check that we can recall
579 // everything.
580 int n = d->capacity_;
581 for (int i = 0; i < n; i++) {
582 d->set(i, i);
583 }
584 ASSERT_EQ(n, d->capacity_);
585 for (int i = 0; i < n; i++) {
586 ASSERT_EQ(i, d->at(i));
587 }
588 // Triger a rehash, and check that everything is OK.
589 d->set(n, n);
590 ASSERT(d->capacity_ > n);
591 for (int i = 0; i <= n; i++) {
592 ASSERT_EQ(i, d->at(i));
593 }
594 for (int i = 0; i <= n; i++) {
595 d->set(i, n * i);
596 }
597 for (int i = 0; i <= n; i++) {
598 ASSERT_EQ(n * i, d->at(i));
599 }
600
601 // Reset and fill the table with keys that all has onto the same index slot
602 n = d->capacity_;
603 int target = n / 2; // pick a slot in the middle to test wrap around
604 d->clear();
605 for (int i = 0; i < n; i++) {
606 d->set(target * i, i);
607 }
608 // Remove each entry one-by-one, stopping after each removal to check that
609 // the other keys can be set and retrieved without issue. This implicitly
610 // checks that special index entries like tombstones are working correctly.
611 for (int i = 0; i < n; i++) {
612 mylib::dict_erase(d, target * i);
613 for (int j = i + 1; j < n; j++) {
614 d->set(target * j, j + 1);
615 ASSERT_EQ(j + 1, d->at(target * j));
616 }
617 }
618
619 PASS();
620}
621
622GLOBAL_DICT(gDict, int, int, 2, {42 COMMA 43}, {1 COMMA 2});
623
624GLOBAL_DICT(gStrDict, BigStr*, BigStr*, 2, {kStrFoo COMMA kStrBar},
625 {kStrBar COMMA kStrFoo});
626
627TEST test_global_dict() {
628 log("gDict len = %d", len(gDict));
629 ASSERT_EQ(2, len(gDict));
630 ASSERT_EQ(1, gDict->at(42));
631 ASSERT_EQ(2, gDict->at(43));
632
633 log("gStrDict len = %d", len(gStrDict));
634 ASSERT_EQ(kStrFoo, gStrDict->at(kStrBar));
635 ASSERT_EQ(kStrBar, gStrDict->at(kStrFoo));
636
637 ASSERT(dict_contains(gStrDict, kStrFoo));
638 ASSERT(dict_contains(gStrDict, kStrBar));
639 ASSERT(!dict_contains(gStrDict, kEmptyString));
640
641 PASS();
642}
643
644TEST test_dict_ordering() {
645 auto d = Alloc<Dict<int, int>>();
646
647 auto in = NewList<int>(std::initializer_list<int>{95, 9, 67, 70, 93, 30, 25,
648 98, 80, 39, 56, 48, 99});
649 for (ListIter<int> it(in); !it.Done(); it.Next()) {
650 d->set(it.Value(), -1);
651 }
652
653 auto keys = d->keys();
654 ASSERT_EQ(len(in), len(keys));
655 for (int i = 0; i < len(in); i++) {
656 ASSERT_EQ(in->at(i), keys->at(i));
657 }
658
659 // check that order survives rehashing
660 d->reserve(2 * len(d));
661 keys = d->keys();
662 ASSERT_EQ(len(in), len(keys));
663 for (int i = 0; i < len(in); i++) {
664 ASSERT_EQ(in->at(i), keys->at(i));
665 }
666
667 PASS();
668}
669
670TEST test_hash() {
671 int i = 0;
672 int j = 0;
673 log("&i = %p", &i);
674 log("&j = %p", &j);
675
676 unsigned h1 = hash_key(&i);
677 log("h1 = %d", h1);
678 unsigned h2 = hash_key(&i);
679 log("h2 = %d", h2);
680 unsigned h3 = hash_key(&j);
681 log("h3 = %d", h3);
682
683 ASSERT_EQ_FMT(h1, h2, "%d");
684 ASSERT(h1 != h3);
685
686 PASS();
687}
688
689GREATEST_MAIN_DEFS();
690
691int main(int argc, char** argv) {
692 gHeap.Init();
693
694 GREATEST_MAIN_BEGIN();
695
696 RUN_TEST(test_dict_init);
697 RUN_TEST(test_dict);
698 RUN_TEST(test_dict_internals);
699 RUN_TEST(test_empty_dict);
700 RUN_TEST(test_tuple_construct);
701 RUN_TEST(test_update_dict);
702 RUN_TEST(test_tuple_key);
703 RUN_TEST(test_dict_erase);
704 RUN_TEST(test_dict_erase2);
705 RUN_TEST(test_global_dict);
706 RUN_TEST(test_dict_ordering);
707 RUN_TEST(test_dict_probe);
708
709 RUN_TEST(dict_methods_test);
710 RUN_TEST(dict_iters_test);
711
712 RUN_TEST(test_hash);
713
714 gHeap.CleanProcessExit();
715
716 GREATEST_MAIN_END();
717 return 0;
718}