1 | #include "mycpp/gc_list.h"
|
2 |
|
3 | #include <assert.h>
|
4 | #include <stdarg.h> // va_list, etc.
|
5 | #include <stdio.h> // vprintf
|
6 |
|
7 | #include "mycpp/common.h"
|
8 | #include "mycpp/gc_alloc.h" // gHeap
|
9 | #include "mycpp/gc_obj.h"
|
10 | #include "vendor/greatest.h"
|
11 |
|
12 | using mylib::str_cmp;
|
13 |
|
14 | GLOBAL_STR(kStrFoo, "foo");
|
15 | GLOBAL_STR(kSpace, " ");
|
16 |
|
17 | void Print(List<BigStr*>* parts) {
|
18 | log("---");
|
19 | log("len = %d", len(parts));
|
20 | for (int i = 0; i < len(parts); ++i) {
|
21 | BigStr* s = parts->at(i);
|
22 | printf("%d [ %s ]\n", i, s->data_);
|
23 | }
|
24 | }
|
25 |
|
26 | // TODO:
|
27 | //
|
28 | // - Test what happens append() runs over the max heap size
|
29 | // - how does it trigger a collection?
|
30 |
|
31 | TEST test_list_gc_header() {
|
32 | auto list1 = NewList<int>();
|
33 | StackRoots _roots1({&list1});
|
34 | auto list2 = NewList<BigStr*>();
|
35 | StackRoots _roots2({&list2});
|
36 |
|
37 | ASSERT_EQ(0, len(list1));
|
38 | ASSERT_EQ(0, len(list2));
|
39 |
|
40 | ASSERT_EQ_FMT(0, list1->capacity_, "%d");
|
41 | ASSERT_EQ_FMT(0, list2->capacity_, "%d");
|
42 |
|
43 | ASSERT_EQ_FMT(HeapTag::FixedSize, ObjHeader::FromObject(list1)->heap_tag,
|
44 | "%d");
|
45 | ASSERT_EQ_FMT(HeapTag::FixedSize, ObjHeader::FromObject(list2)->heap_tag,
|
46 | "%d");
|
47 |
|
48 | #if 0
|
49 | // 8 byte obj header + 2 integers + pointer
|
50 | ASSERT_EQ_FMT(24, ObjHeader::FromObject(list1)->obj_len, "%d");
|
51 | ASSERT_EQ_FMT(24, ObjHeader::FromObject(list2)->obj_len, "%d");
|
52 | #endif
|
53 |
|
54 | // Make sure they're on the heap
|
55 | #ifndef MARK_SWEEP
|
56 | int diff1 = reinterpret_cast<char*>(list1) - gHeap.from_space_.begin_;
|
57 | int diff2 = reinterpret_cast<char*>(list2) - gHeap.from_space_.begin_;
|
58 | ASSERT(diff1 < 1024);
|
59 | ASSERT(diff2 < 1024);
|
60 | #endif
|
61 |
|
62 | auto more = NewList<int>(std::initializer_list<int>{11, 22, 33});
|
63 | StackRoots _roots3({&more});
|
64 | list1->extend(more);
|
65 | ASSERT_EQ_FMT(3, len(list1), "%d");
|
66 |
|
67 | ASSERT_EQ_FMT(HeapTag::Opaque, ObjHeader::FromObject(list1->slab_)->heap_tag,
|
68 | "%d");
|
69 |
|
70 | #if 0
|
71 | // 8 byte header + 3*4 == 8 + 12 == 20, rounded up to power of 2
|
72 | ASSERT_EQ_FMT(32, ObjHeader::FromObject(list1->slab_)->obj_len, "%d");
|
73 | #endif
|
74 |
|
75 | ASSERT_EQ_FMT(11, list1->at(0), "%d");
|
76 | ASSERT_EQ_FMT(22, list1->at(1), "%d");
|
77 | ASSERT_EQ_FMT(33, list1->at(2), "%d");
|
78 |
|
79 | log("extending");
|
80 | auto more2 = NewList<int>(std::initializer_list<int>{44, 55, 66, 77});
|
81 | StackRoots _roots4({&more2});
|
82 | list1->extend(more2);
|
83 |
|
84 | ASSERT_EQ_FMT(7, len(list1), "%d");
|
85 |
|
86 | #if 0
|
87 | // 8 bytes header + 7*4 == 8 + 28 == 36, rounded up to power of 2
|
88 | ASSERT_EQ_FMT(64, ObjHeader::FromObject(list1->slab_)->obj_len, "%d");
|
89 | #endif
|
90 |
|
91 | ASSERT_EQ_FMT(11, list1->at(0), "%d");
|
92 | ASSERT_EQ_FMT(22, list1->at(1), "%d");
|
93 | ASSERT_EQ_FMT(33, list1->at(2), "%d");
|
94 | ASSERT_EQ_FMT(44, list1->at(3), "%d");
|
95 | ASSERT_EQ_FMT(55, list1->at(4), "%d");
|
96 | ASSERT_EQ_FMT(66, list1->at(5), "%d");
|
97 | ASSERT_EQ_FMT(77, list1->at(6), "%d");
|
98 |
|
99 | list1->append(88);
|
100 | ASSERT_EQ_FMT(88, list1->at(7), "%d");
|
101 | ASSERT_EQ_FMT(8, len(list1), "%d");
|
102 |
|
103 | #ifndef MARK_SWEEP
|
104 | int d_slab = reinterpret_cast<char*>(list1->slab_) - gHeap.from_space_.begin_;
|
105 | ASSERT(d_slab < 1024);
|
106 | #endif
|
107 |
|
108 | log("list1_ = %p", list1);
|
109 | log("list1->slab_ = %p", list1->slab_);
|
110 |
|
111 | auto str1 = StrFromC("foo");
|
112 | StackRoots _roots5({&str1});
|
113 | log("str1 = %p", str1);
|
114 | auto str2 = StrFromC("bar");
|
115 | StackRoots _roots6({&str2});
|
116 | log("str2 = %p", str2);
|
117 |
|
118 | list2->append(str1);
|
119 | list2->append(str2);
|
120 | ASSERT_EQ(2, len(list2));
|
121 | ASSERT(str_equals(str1, list2->at(0)));
|
122 | ASSERT(str_equals(str2, list2->at(1)));
|
123 |
|
124 | PASS();
|
125 | }
|
126 |
|
127 | // Manual initialization. This helped me write the GLOBAL_LIST() macro.
|
128 | GcGlobal<GlobalSlab<int, 3>> _gSlab = {
|
129 | .header = {0, kZeroMask, HeapTag::Global, kUndefinedId},
|
130 | {.items_ = {5, 6, 7}}};
|
131 | GcGlobal<GlobalList<int, 3>> _gList = {
|
132 | .header = {0, kZeroMask, HeapTag::Global, kUndefinedId},
|
133 | {.len_ = 3, .capacity_ = 3, .slab_ = &_gSlab.obj}};
|
134 | List<int>* gList = reinterpret_cast<List<int>*>(&_gList.obj);
|
135 |
|
136 | GLOBAL_LIST(gList2, int, 4, {5 COMMA 4 COMMA 3 COMMA 2});
|
137 |
|
138 | GLOBAL_STR(gFoo, "foo");
|
139 | GLOBAL_LIST(gList3, BigStr*, 2, {gFoo COMMA gFoo});
|
140 |
|
141 | TEST test_global_list() {
|
142 | ASSERT_EQ(3, len(gList));
|
143 | ASSERT_EQ_FMT(5, gList->at(0), "%d");
|
144 | ASSERT_EQ_FMT(6, gList->at(1), "%d");
|
145 | ASSERT_EQ_FMT(7, gList->at(2), "%d");
|
146 |
|
147 | ASSERT_EQ(4, len(gList2));
|
148 | ASSERT_EQ_FMT(5, gList2->at(0), "%d");
|
149 | ASSERT_EQ_FMT(4, gList2->at(1), "%d");
|
150 | ASSERT_EQ_FMT(3, gList2->at(2), "%d");
|
151 | ASSERT_EQ_FMT(2, gList2->at(3), "%d");
|
152 |
|
153 | ASSERT_EQ(2, len(gList3));
|
154 | ASSERT(str_equals(gFoo, gList3->at(0)));
|
155 | ASSERT(str_equals(gFoo, gList3->at(1)));
|
156 |
|
157 | PASS();
|
158 | }
|
159 |
|
160 | TEST test_list_funcs() {
|
161 | log(" ints");
|
162 | auto ints = NewList<int>({4, 5, 6});
|
163 | log("-- before pop(0)");
|
164 | for (int i = 0; i < len(ints); ++i) {
|
165 | log("ints[%d] = %d", i, ints->at(i));
|
166 | }
|
167 | ASSERT_EQ(3, len(ints)); // [4, 5, 6]
|
168 | ints->pop(0); // [5, 6]
|
169 |
|
170 | ASSERT_EQ(2, len(ints));
|
171 | ASSERT_EQ_FMT(5, ints->at(0), "%d");
|
172 | ASSERT_EQ_FMT(6, ints->at(1), "%d");
|
173 |
|
174 | ints->reverse();
|
175 | ASSERT_EQ(2, len(ints)); // [6, 5]
|
176 |
|
177 | ASSERT_EQ_FMT(6, ints->at(0), "%d");
|
178 | ASSERT_EQ_FMT(5, ints->at(1), "%d");
|
179 |
|
180 | ints->append(9); // [6, 5, 9]
|
181 | ASSERT_EQ(3, len(ints));
|
182 |
|
183 | ints->reverse(); // [9, 5, 6]
|
184 | ASSERT_EQ(9, ints->at(0));
|
185 | ASSERT_EQ(5, ints->at(1));
|
186 | ASSERT_EQ(6, ints->at(2));
|
187 |
|
188 | ints->set(0, 42);
|
189 | ints->set(1, 43);
|
190 | log("-- after mutation");
|
191 | for (int i = 0; i < len(ints); ++i) {
|
192 | log("ints[%d] = %d", i, ints->at(i));
|
193 | }
|
194 |
|
195 | auto L = list_repeat<BigStr*>(nullptr, 3);
|
196 | log("list_repeat length = %d", len(L));
|
197 |
|
198 | auto L2 = list_repeat<bool>(true, 3);
|
199 | log("list_repeat length = %d", len(L2));
|
200 | log("item 0 %d", L2->at(0));
|
201 | log("item 1 %d", L2->at(1));
|
202 |
|
203 | auto strs = NewList<BigStr*>();
|
204 | strs->append(StrFromC("c"));
|
205 | strs->append(StrFromC("a"));
|
206 | strs->append(StrFromC("b"));
|
207 | strs->append(kEmptyString);
|
208 | ASSERT_EQ(4, len(strs)); // ['c', 'a', 'b', '']
|
209 |
|
210 | strs->sort();
|
211 | ASSERT_EQ(4, len(strs)); // ['', 'a', 'b', 'c']
|
212 | ASSERT(str_equals(kEmptyString, strs->at(0)));
|
213 | ASSERT(str_equals(StrFromC("a"), strs->at(1)));
|
214 | ASSERT(str_equals(StrFromC("b"), strs->at(2)));
|
215 | ASSERT(str_equals(StrFromC("c"), strs->at(3)));
|
216 |
|
217 | auto a = StrFromC("a");
|
218 | auto aa = StrFromC("aa");
|
219 | auto b = StrFromC("b");
|
220 |
|
221 | ASSERT_EQ(0, int_cmp(0, 0));
|
222 | ASSERT_EQ(-1, int_cmp(0, 5));
|
223 | ASSERT_EQ(1, int_cmp(0, -5));
|
224 |
|
225 | ASSERT_EQ(0, str_cmp(kEmptyString, kEmptyString));
|
226 | ASSERT_EQ(-1, str_cmp(kEmptyString, a));
|
227 | ASSERT_EQ(-1, str_cmp(a, aa));
|
228 | ASSERT_EQ(-1, str_cmp(a, b));
|
229 |
|
230 | ASSERT_EQ(1, str_cmp(b, a));
|
231 | ASSERT_EQ(1, str_cmp(b, kEmptyString));
|
232 |
|
233 | PASS();
|
234 | }
|
235 |
|
236 | void ListFunc(std::initializer_list<BigStr*> init) {
|
237 | log("init.size() = %d", init.size());
|
238 | }
|
239 |
|
240 | TEST test_list_iters() {
|
241 | log(" forward iteration over list");
|
242 | auto ints = NewList<int>({1, 2, 3});
|
243 | for (ListIter<int> it(ints); !it.Done(); it.Next()) {
|
244 | int x = it.Value();
|
245 | log("x = %d", x);
|
246 | }
|
247 |
|
248 | {
|
249 | ListIter<int> it(ints);
|
250 | auto ints2 = list(it);
|
251 | ASSERT_EQ(ints->at(0), ints2->at(0));
|
252 | ASSERT_EQ(ints->at(1), ints2->at(1));
|
253 | ASSERT_EQ(ints->at(2), ints2->at(2));
|
254 | }
|
255 |
|
256 | log(" backward iteration over list");
|
257 | for (ReverseListIter<int> it(ints); !it.Done(); it.Next()) {
|
258 | int x = it.Value();
|
259 | log("x = %d", x);
|
260 | }
|
261 |
|
262 | // hm std::initializer_list is "first class"
|
263 | auto strs = {StrFromC("foo"), StrFromC("bar")};
|
264 | ListFunc(strs);
|
265 |
|
266 | PASS();
|
267 | }
|
268 |
|
269 | TEST test_list_copy() {
|
270 | List<int>* a = NewList<int>(std::initializer_list<int>{1, 2, 3});
|
271 | List<int>* b = list(a);
|
272 |
|
273 | ASSERT_EQ(b->len_, a->len_);
|
274 | ASSERT_EQ(b->at(0), a->at(0));
|
275 | ASSERT_EQ(b->at(1), a->at(1));
|
276 | ASSERT_EQ(b->at(2), a->at(2));
|
277 |
|
278 | PASS();
|
279 | }
|
280 |
|
281 | TEST list_methods_test() {
|
282 | List<int>* ints = nullptr;
|
283 | StackRoots _roots({&ints});
|
284 |
|
285 | ints = NewList<int>(std::initializer_list<int>{5, 6, 7, 8});
|
286 |
|
287 | List<int>* slice1 = ints->slice(1);
|
288 | ASSERT_EQ(3, len(slice1));
|
289 | ASSERT_EQ(6, slice1->at(0));
|
290 |
|
291 | List<int>* slice2 = ints->slice(-4, -2);
|
292 | ASSERT_EQ(2, len(slice2));
|
293 | ASSERT_EQ(5, slice2->at(0));
|
294 |
|
295 | List<int>* slice3 = ints->slice(1, 4);
|
296 | ASSERT_EQ(3, len(slice3));
|
297 | ASSERT_EQ(6, slice3->at(0));
|
298 | ASSERT_EQ(7, slice3->at(1));
|
299 | ASSERT_EQ(8, slice3->at(2));
|
300 |
|
301 | log("-- before pop(0)");
|
302 | for (int i = 0; i < len(ints); ++i) {
|
303 | log("ints[%d] = %d", i, ints->at(i));
|
304 | }
|
305 | ASSERT_EQ(4, len(ints)); // [5, 6, 7, 8]
|
306 |
|
307 | log("pop()");
|
308 |
|
309 | ints->pop(); // [5, 6, 7]
|
310 | ASSERT_EQ(3, len(ints));
|
311 | ASSERT_EQ_FMT(5, ints->at(0), "%d");
|
312 | ASSERT_EQ_FMT(6, ints->at(1), "%d");
|
313 | ASSERT_EQ_FMT(7, ints->at(2), "%d");
|
314 |
|
315 | log("pop(0)");
|
316 |
|
317 | ints->pop(0); // [6, 7]
|
318 | ASSERT_EQ(2, len(ints));
|
319 | ASSERT_EQ_FMT(6, ints->at(0), "%d");
|
320 | ASSERT_EQ_FMT(7, ints->at(1), "%d");
|
321 |
|
322 | ints->reverse();
|
323 | ASSERT_EQ(2, len(ints)); // [7, 6]
|
324 |
|
325 | ASSERT_EQ_FMT(7, ints->at(0), "%d");
|
326 | ASSERT_EQ_FMT(6, ints->at(1), "%d");
|
327 |
|
328 | ints->append(9); // [7, 6, 9]
|
329 | ASSERT_EQ(3, len(ints));
|
330 |
|
331 | ints->reverse(); // [9, 6, 7]
|
332 | ASSERT_EQ(9, ints->at(0));
|
333 | ASSERT_EQ(6, ints->at(1));
|
334 | ASSERT_EQ(7, ints->at(2));
|
335 |
|
336 | auto other = NewList<int>(std::initializer_list<int>{-1, -2});
|
337 | ints->extend(other); // [9, 6, 7, 1, 2]
|
338 | ASSERT_EQ(5, len(ints));
|
339 | ASSERT_EQ(-2, ints->at(4));
|
340 | ASSERT_EQ(-1, ints->at(3));
|
341 |
|
342 | ints->clear();
|
343 | ASSERT_EQ(0, len(ints));
|
344 | ASSERT_EQ(0, ints->slab_->items_[0]); // make sure it's zero'd
|
345 |
|
346 | // Clear empty list
|
347 | auto empty = NewList<int*>();
|
348 | empty->clear();
|
349 |
|
350 | PASS();
|
351 | }
|
352 |
|
353 | TEST sort_test() {
|
354 | ASSERT_EQ(0, int_cmp(0, 0));
|
355 | ASSERT_EQ(-1, int_cmp(0, 5));
|
356 | ASSERT_EQ(1, int_cmp(0, -5));
|
357 |
|
358 | BigStr *a = nullptr, *aa = nullptr, *b = nullptr;
|
359 | StackRoots _roots({&a, &aa, &b});
|
360 |
|
361 | a = StrFromC("a");
|
362 | aa = StrFromC("aa");
|
363 | b = StrFromC("b");
|
364 |
|
365 | ASSERT_EQ(0, str_cmp(kEmptyString, kEmptyString));
|
366 | ASSERT_EQ(-1, str_cmp(kEmptyString, a));
|
367 | ASSERT_EQ(-1, str_cmp(a, aa));
|
368 | ASSERT_EQ(-1, str_cmp(a, b));
|
369 |
|
370 | ASSERT_EQ(1, str_cmp(b, a));
|
371 | ASSERT_EQ(1, str_cmp(b, kEmptyString));
|
372 |
|
373 | List<BigStr*>* strs = nullptr;
|
374 | StackRoots _roots2({&strs});
|
375 | strs = Alloc<List<BigStr*>>();
|
376 |
|
377 | strs->append(a);
|
378 | strs->append(aa);
|
379 | strs->append(b);
|
380 | strs->append(kEmptyString);
|
381 | ASSERT_EQ(4, len(strs)); // ['a', 'aa', 'b', '']
|
382 |
|
383 | strs->sort(); // ['', 'a', 'aa', 'b']
|
384 | ASSERT_EQ(4, len(strs));
|
385 | ASSERT(str_equals(kEmptyString, strs->at(0)));
|
386 | ASSERT(str_equals0("a", strs->at(1)));
|
387 | ASSERT(str_equals0("aa", strs->at(2)));
|
388 | ASSERT(str_equals0("b", strs->at(3)));
|
389 |
|
390 | PASS();
|
391 | }
|
392 |
|
393 | TEST contains_test() {
|
394 | BigStr* s = nullptr;
|
395 | BigStr* nul = nullptr;
|
396 | StackRoots _roots({&s, &nul});
|
397 |
|
398 | log(" List<BigStr*>");
|
399 | List<BigStr*>* strs = nullptr;
|
400 | List<int>* ints = nullptr;
|
401 | List<double>* floats = nullptr;
|
402 |
|
403 | StackRoots _roots2({&strs, &ints, &floats});
|
404 |
|
405 | strs = Alloc<List<BigStr*>>();
|
406 |
|
407 | strs->append(kSpace);
|
408 | s = StrFromC(" "); // LOCAL space
|
409 | ASSERT(list_contains(strs, s));
|
410 | ASSERT(!list_contains(strs, kStrFoo));
|
411 |
|
412 | strs->append(kStrFoo);
|
413 | ASSERT(list_contains(strs, kStrFoo));
|
414 |
|
415 | log(" ints");
|
416 | ints = NewList<int>(std::initializer_list<int>{1, 2, 3});
|
417 | ASSERT(list_contains(ints, 1));
|
418 |
|
419 | ASSERT(!list_contains(ints, 42));
|
420 |
|
421 | #if 0
|
422 | log(" floats");
|
423 | floats = NewList<double>(std::initializer_list<double>{0.5, 0.25, 0.0});
|
424 | ASSERT(list_contains(floats, 0.0));
|
425 | ASSERT(!list_contains(floats, 42.0));
|
426 | #endif
|
427 |
|
428 | PASS();
|
429 | }
|
430 |
|
431 | TEST test_list_sort() {
|
432 | auto s1 = StrFromC("fooA");
|
433 | auto s2 = StrFromC("fooB");
|
434 | auto s3 = StrFromC("fooC");
|
435 | auto l = NewList<BigStr*>(std::initializer_list<BigStr*>{s3, s1, s2});
|
436 |
|
437 | auto s = sorted(l);
|
438 | ASSERT(str_equals(s->at(0), s1));
|
439 | ASSERT(str_equals(s->at(1), s2));
|
440 | ASSERT(str_equals(s->at(2), s3));
|
441 |
|
442 | PASS();
|
443 | }
|
444 |
|
445 | TEST test_list_remove() {
|
446 | auto l = NewList<int>(std::initializer_list<int>{1, 3, 3, 3, 2});
|
447 |
|
448 | for (int i = 0; i < 3; ++i) {
|
449 | l->remove(3);
|
450 | }
|
451 |
|
452 | bool caught = false;
|
453 | try {
|
454 | l->index(3);
|
455 | } catch (ValueError* e) {
|
456 | caught = true;
|
457 | }
|
458 | ASSERT(caught);
|
459 |
|
460 | ASSERT_EQ(l->at(0), 1);
|
461 | ASSERT_EQ(l->at(1), 2);
|
462 |
|
463 | PASS();
|
464 | }
|
465 |
|
466 | TEST test_list_pop_mem_safe() {
|
467 | auto l = NewList<int>();
|
468 |
|
469 | // List::pop(int) had a memory bug where it would buffer overflow due to a
|
470 | // mistake when calling memmove. To reproduce, the list had to be at least 16
|
471 | // items long, otherwise ASAN will not catch the error.
|
472 | for (int i = 0; i < 16; ++i) {
|
473 | l->append(i);
|
474 | }
|
475 |
|
476 | l->pop(15); // This would cause a buffer overflow
|
477 |
|
478 | PASS();
|
479 | }
|
480 |
|
481 | GREATEST_MAIN_DEFS();
|
482 |
|
483 | int main(int argc, char** argv) {
|
484 | gHeap.Init();
|
485 |
|
486 | GREATEST_MAIN_BEGIN();
|
487 |
|
488 | RUN_TEST(test_list_gc_header);
|
489 | RUN_TEST(test_global_list);
|
490 |
|
491 | RUN_TEST(test_list_funcs);
|
492 | RUN_TEST(test_list_iters);
|
493 |
|
494 | RUN_TEST(list_methods_test);
|
495 | RUN_TEST(sort_test);
|
496 | RUN_TEST(contains_test);
|
497 |
|
498 | RUN_TEST(test_list_copy);
|
499 | RUN_TEST(test_list_sort);
|
500 | RUN_TEST(test_list_remove);
|
501 |
|
502 | RUN_TEST(test_list_pop_mem_safe);
|
503 |
|
504 | gHeap.CleanProcessExit();
|
505 |
|
506 | GREATEST_MAIN_END();
|
507 | return 0;
|
508 | }
|