1 #include <r_list.h>
2 #include "minunit.h"
3 #define BUF_LENGTH 100
4
test_r_list_size(void)5 bool test_r_list_size(void) {
6 // Test that r_list adding and deleting works correctly.
7 int i;
8 RList* list = r_list_new ();
9 intptr_t test = 0x101010;
10 // Add 100 items.
11 for (i = 0; i < 100; i++) {
12 r_list_append (list, (void*)test);
13 mu_assert_eq (r_list_length (list), i + 1, "r_list_length failed on append");
14 }
15 // Delete 50 of them.
16 for (i = 0; i < 50; i++) {
17 (void)r_list_pop (list);
18 mu_assert_eq(99 - i, r_list_length (list), "r_list_length failed on pop");
19 }
20 // Purge the list.
21 r_list_purge (list);
22 mu_assert_eq(0, r_list_length (list), "r_list_length failed on purged list");
23 r_list_free (list);
24 mu_end;
25 }
26
test_r_list_values(void)27 bool test_r_list_values(void) {
28 RList* list = r_list_new ();
29 intptr_t test1 = 0x12345;
30 intptr_t test2 = 0x88888;
31 r_list_append (list, (void*)test1);
32 r_list_append (list, (void*)test2);
33 int top1 = (intptr_t)r_list_pop (list);
34 int top2 = (intptr_t)r_list_pop (list);
35 mu_assert_eq(top1, 0x88888, "first value not 0x88888");
36 mu_assert_eq(top2, 0x12345, "first value not 0x12345");
37 r_list_free (list);
38 mu_end;
39 }
40
test_r_list_join(void)41 bool test_r_list_join(void) {
42 RList* list1 = r_list_new ();
43 RList* list2 = r_list_new ();
44 intptr_t test1 = 0x12345;
45 intptr_t test2 = 0x88888;
46 r_list_append (list1, (void*)test1);
47 r_list_append (list2, (void*)test2);
48 int joined = r_list_join (list1, list2);
49 mu_assert_eq(joined, 1, "r_list_join of two lists");
50 mu_assert_eq(r_list_length (list1), 2, "r_list_join two single element lists result length is 1");
51 r_list_free (list1);
52 r_list_free (list2);
53 mu_end;
54 }
55
56
test_r_list_free(void)57 bool test_r_list_free(void) {
58 RList* list = r_list_newf ((void*)0x9999);
59 mu_assert_eq((int)(intptr_t)list->free, 0x9999, "r_list_newf function gets set properly");
60 r_list_free (list);
61 mu_end;
62 }
63
test_r_list_del_n(void)64 bool test_r_list_del_n(void) {
65 RList* list = r_list_new ();
66 intptr_t test1 = 0x12345;
67 intptr_t test2 = 0x88888;
68 r_list_append (list, (void*)test1);
69 r_list_append (list, (void*)test2);
70 mu_assert_eq (r_list_length (list), 2,
71 "list is of length 2 when adding 2 values");
72 r_list_del_n (list, 0);
73 int top1 = (intptr_t)r_list_pop (list);
74 mu_assert_eq(top1, 0x88888,
75 "error, first value not 0x88888");
76 r_list_free (list);
77 mu_end;
78 }
79
test_r_list_sort(void)80 bool test_r_list_sort(void) {
81 RList* list = r_list_new ();
82 char* test1 = "AAAA";
83 char* test2 = "BBBB";
84 char* test3 = "CCCC";
85 // Put in not sorted order.
86 r_list_append (list, (void*)test1);
87 r_list_append (list, (void*)test3);
88 r_list_append (list, (void*)test2);
89 // Sort.
90 r_list_sort (list, (RListComparator)strcmp);
91 // Check that the list is actually sorted.
92 mu_assert_streq ((char*)list->head->data, "AAAA", "first value in sorted list");
93 mu_assert_streq ((char*)list->head->n->data, "BBBB", "second value in sorted list");
94 mu_assert_streq ((char*)list->head->n->n->data, "CCCC", "third value in sorted list");
95 r_list_free (list);
96 mu_end;
97 }
98
99
test_r_list_sort2(void)100 bool test_r_list_sort2(void) {
101 RList* list = r_list_new ();
102 char* test1 = "AAAA";
103 char* test2 = "BBBB";
104 char* test3 = "CCCC";
105 // Put in not sorted order.
106 r_list_append (list, (void*)test3);
107 r_list_append (list, (void*)test2);
108 r_list_append (list, (void*)test1);
109 // Sort.
110 r_list_merge_sort (list, (RListComparator)strcmp);
111 // Check that the list is actually sorted.
112 mu_assert_streq ((char*)list->head->data, "AAAA", "first value in sorted list");
113 mu_assert_streq ((char*)list->head->n->data, "BBBB", "second value in sorted list");
114 mu_assert_streq ((char*)list->head->n->n->data, "CCCC", "third value in sorted list");
115 r_list_free (list);
116 mu_end;
117 }
118
119
cmp_range(const void * a,const void * b)120 static int cmp_range(const void *a, const void *b) {
121 int ra = *(int *)a;
122 int rb = *(int *)b;
123 return ra - rb;
124 }
125
test_r_list_sort3(void)126 bool test_r_list_sort3(void) {
127 RList* list = r_list_new ();
128 int test1 = 33508;
129 int test2 = 33480;
130 int test3 = 33964;
131 // Put in not sorted order.
132 r_list_append (list, (void*)&test1);
133 r_list_append (list, (void*)&test3);
134 r_list_append (list, (void*)&test2);
135 // Sort.
136 r_list_merge_sort (list, (RListComparator)cmp_range);
137 // Check that the list is actually sorted.
138 mu_assert_eq (*(int*)list->head->data, 33480, "first value in sorted list");
139 mu_assert_eq (*(int*)list->head->n->data, 33508, "second value in sorted list");
140 mu_assert_eq (*(int*)list->head->n->n->data, 33964, "third value in sorted list");
141 r_list_free (list);
142 mu_end;
143 }
144
145
test_r_list_length(void)146 bool test_r_list_length(void) {
147 RList* list = r_list_new ();
148 RList* list2 = r_list_new ();
149 RListIter *iter;
150 int count = 0;
151 int test1 = 33508;
152 int test2 = 33480;
153 int test3 = 33964;
154 // Put in not sorted order.
155 r_list_append (list, (void*)&test1);
156 r_list_append (list, (void*)&test3);
157 r_list_append (list, (void*)&test2);
158 iter = list->head;
159 while (iter) {
160 count++;
161 iter = iter->n;
162 }
163 mu_assert_eq (list->length, 3, "First length check");
164
165 r_list_delete_data (list, (void*)&test1);
166 mu_assert_eq (list->length, 2, "Second length check");
167
168 r_list_append (list, (void*)&test1);
169 mu_assert_eq (list->length, 3, "Third length check");
170
171 r_list_pop (list);
172 mu_assert_eq (list->length, 2, "Fourth length check");
173
174 r_list_pop_head (list);
175 mu_assert_eq (list->length, 1, "Fifth length check");
176
177 r_list_insert (list, 2, (void*)&test2);
178 mu_assert_eq (list->length, 2, "Sixth length check");
179
180 r_list_prepend (list, (void*)&test3);
181 mu_assert_eq (list->length, 3, "Seventh length check");
182
183 r_list_del_n (list, 2);
184 mu_assert_eq (list->length, 2, "Eighth length check");
185
186 r_list_append (list2, (void*)&test1);
187 r_list_append (list2, (void*)&test3);
188 r_list_append (list2, (void*)&test2);
189 r_list_join (list, list2);
190 mu_assert_eq (list->length, 5, "Ninth length check");
191 iter = list->head;
192 count = 0;
193 while (iter) {
194 count++;
195 iter = iter->n;
196 }
197 mu_assert_eq (list->length, count, "Tenth length check");
198 r_list_free (list);
199 r_list_free (list2);
200 mu_end;
201 }
202
203
test_r_list_sort5(void)204 bool test_r_list_sort5(void) {
205 RList* list = r_list_new ();
206 int i = 0;
207 char *upper[] = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"};
208 char *lower[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
209 for (i = 0; i < 26; i++) {
210 r_list_append (list, (void *)lower[i]);
211 }
212 for (i = 0; i < 26; i++) {
213 r_list_append (list, (void *)upper[i]);
214 }
215 //add more than 43 elements to trigger merge sort
216 r_list_sort (list, (RListComparator)strcmp);
217 mu_assert_streq ((char *)list->head->data, upper[0], "First element");
218 mu_assert_streq ((char *)list->tail->data, lower[25], "Last element");
219 r_list_free (list);
220 mu_end;
221 }
222
223 // 3-valued comparator -> {LT,EQ,GT}.
pintcmp(int * a,int * b)224 static int pintcmp(int* a, int* b) {
225 return (int)(*a > *b) - (int)(*b > *a);
226 }
227
test_r_list_mergesort_pint()228 bool test_r_list_mergesort_pint() {
229 // 47 items
230 int data[] = {-440, -468, -444, -80, -568, -564, -396, -404, -436, -420,
231 -428, -388, -356, -324, -292, -464, -260, -252, -204, -196, -212, -76,
232 -160, -540, -216, -536, -532, -148, -116, -560, -556, -244, -460, -448,
233 -236, -156, -228, -456, -552, -548, -544, -220, -180, -188, -84, -172,
234 -164};
235 int expected[] = {-568, -564, -560, -556, -552, -548, -544, -540, -536,
236 -532, -468, -464, -460, -456, -448, -444, -440, -436, -428, -420, -404,
237 -396, -388, -356, -324, -292, -260, -252, -244, -236, -228, -220, -216,
238 -212, -204, -196, -188, -180, -172, -164, -160, -156, -148, -116, -84,
239 -80, -76};
240
241 RList* list = r_list_new();
242 size_t i;
243 for (i = 0; i < R_ARRAY_SIZE (data); i++) {
244 r_list_append (list, (void *)&data[i]);
245 }
246
247 // invoke sorting
248 r_list_sort (list, (RListComparator)pintcmp);
249
250 // assert the list is sorted as expected
251 RListIter* iter;
252 for (i = 0, iter = list->head; i < R_ARRAY_SIZE (expected); i++, iter = iter->n) {
253 mu_assert_eq (*(int *)iter->data, expected[i], "array content mismatch");
254 }
255
256 r_list_free(list);
257 mu_end;
258 }
259
260
test_r_list_sort4(void)261 bool test_r_list_sort4(void) {
262 RList* list = r_list_new ();
263 char* test1 = "AAAA";
264 char* test2 = "BBBB";
265 char* test3 = "CCCC";
266 char* test4 = "DDDD";
267 char* test5 = "EEEE";
268 char* test6_later = "FFFF";
269 char* test7 = "GGGG";
270 char* test8 = "HHHH";
271 char* test9 = "IIII";
272 char* test10 = "JJJJ";
273 char* ins_tests_odd[] = {test10, test1, test3, test7, test5, test9, test2,
274 test4, test8};
275 char* exp_tests_odd[] = {test1, test2, test3, test4, test5, test7,
276 test8, test9, test10};
277 int i;
278
279 // Put in not sorted order.
280 for (i = 0; i < R_ARRAY_SIZE (ins_tests_odd); ++i) {
281 r_list_append (list, (void*)ins_tests_odd[i]);
282 }
283 // Sort.
284 r_list_merge_sort (list, (RListComparator)strcmp);
285
286 // Check that the list (odd-length) is actually sorted.
287 RListIter *next = list->head;
288 for (i = 0; i < R_ARRAY_SIZE (exp_tests_odd); ++i) {
289 char buf[BUF_LENGTH];
290 snprintf(buf, BUF_LENGTH, "%d-th value in sorted list", i);
291 mu_assert_streq ((char*)next->data, exp_tests_odd[i], buf);
292 next = next->n;
293 }
294
295 #if 0 // Debug Print
296 char *data;
297
298 printf("after sorted 1 \n");
299 r_list_foreach (list, next, data) {
300 printf("l -> %s\n", data);
301 }
302 #endif
303
304 char* exp_tests_even[] = {test1, test2, test3, test4, test5,
305 test6_later, test7, test8, test9, test10};
306 // Add test6 to make the length even
307 r_list_append (list, (void*)test6_later);
308
309 #if 0 // Debug Printing
310 printf("after adding FFFF \n");
311 r_list_foreach (list, next, data) {
312 printf("l -> %s\n", data);
313 }
314 #endif
315
316 // Sort
317 r_list_merge_sort (list, (RListComparator)strcmp);
318
319 #if 0 // Debug Printing
320 printf("after sorting 2 \n");
321 r_list_foreach (list, next, data) {
322 printf("l -> %s\n", data);
323 }
324 #endif
325
326 // Check that the list (even-length) is actually sorted.
327 next = list->head;
328 for (i = 0; i < R_ARRAY_SIZE (exp_tests_even); ++i) {
329 char buf[BUF_LENGTH];
330 snprintf(buf, BUF_LENGTH, "%d-th value in sorted list", i);
331 mu_assert_streq ((char*)next->data, exp_tests_even[i], buf);
332 next = next->n;
333 }
334 r_list_free (list);
335 mu_end;
336 }
337
test_r_list_append_prepend(void)338 bool test_r_list_append_prepend(void) {
339
340 char *test[] = {
341 "HEAD 00",
342 "HEAD",
343 "foo",
344 "bar",
345 "cow",
346 "LAST"
347 };
348
349 RList *list = r_list_new ();
350 RListIter *iter;
351
352 r_list_append (list, test[2]);
353 r_list_append (list, test[3]);
354 r_list_append (list, test[4]);
355 r_list_prepend (list, test[1]);
356 r_list_prepend (list, test[0]);
357 r_list_append (list, test[5]);
358
359 char buf[BUF_LENGTH];
360 int i;
361 //Check that the next sequence is correct
362 iter = list->head;
363 for (i = 0; i < R_ARRAY_SIZE (test); ++i) {
364 snprintf (buf, BUF_LENGTH, "%d-th value in list from head", i);
365 mu_assert_streq ((char *)iter->data, test[i], buf);
366 iter = iter->n;
367 }
368
369 //Check that the previous sequence is correct
370 iter = list->tail;
371 for (i = (R_ARRAY_SIZE (test)) - 1; i > 0; --i) {
372 snprintf (buf, BUF_LENGTH, "%d-th value in list from tail", i);
373 mu_assert_streq ((char *)iter->data, test[i], buf);
374 iter = iter->p;
375 }
376
377 r_list_free (list);
378 mu_end;
379 }
380
test_r_list_set_get(void)381 bool test_r_list_set_get(void) {
382
383 char *test[] = { "aa", "bb", "cc", "dd", "ee", "ff" };
384
385 RList *list = r_list_new ();
386
387 int i;
388 for (i = 0; i < R_ARRAY_SIZE (test); ++i) {
389 r_list_append (list, test[i]);
390 }
391
392 char *str;
393 r_list_set_n (list, 2, "CC");
394 str = (char *)r_list_get_n (list, 2);
395 mu_assert_streq (str, "CC", "value after set");
396
397 r_list_prepend (list, "AA0");
398 str = (char *)r_list_get_n (list, 3);
399 mu_assert_streq (str, "CC", "value after prepend");
400
401 bool s;
402 s = r_list_set_n (list, 100, "ZZZZ");
403 mu_assert_eq (s, false, "set out of bound");
404 s = r_list_get_n (list, 100);
405 mu_assert_eq (s, false, "get out of bound");
406
407 r_list_free (list);
408 mu_end;
409 }
410
test_r_list_reverse(void)411 bool test_r_list_reverse(void) {
412
413 char *test[] = { "aa", "bb", "cc", "dd", "ee", "ff" };
414
415 RList *list = r_list_new ();
416
417 int i;
418 for (i = 0; i < R_ARRAY_SIZE (test); ++i) {
419 r_list_prepend (list, test[i]);
420 }
421
422 r_list_reverse (list);
423
424 char buf[BUF_LENGTH];
425 //Check that the sequence is correct
426 RListIter *iter = list->head;
427 for (i = 0; i < R_ARRAY_SIZE (test); ++i) {
428 snprintf (buf, BUF_LENGTH, "%d-th value in list after reverse", i);
429 mu_assert_streq ((char *)iter->data, test[i], buf);
430 iter = iter->n;
431 }
432
433 r_list_free (list);
434 mu_end;
435 }
436
test_r_list_clone(void)437 bool test_r_list_clone(void) {
438
439 char *test[] = { "aa", "bb", "cc", "dd", "ee", "ff" };
440
441 RList *list1 = r_list_new ();
442 RList *list2;
443
444 int i;
445 for (i = 0; i < R_ARRAY_SIZE (test); ++i) {
446 r_list_prepend (list1, test[i]);
447 }
448
449 list2 = r_list_clone (list1);
450
451 char buf[BUF_LENGTH];
452 RListIter *iter1 = list1->head;
453 RListIter *iter2 = list2->head;
454 for (i = 0; i < R_ARRAY_SIZE (test); ++i) {
455 snprintf (buf, BUF_LENGTH, "%d-th value after clone", i);
456 mu_assert_streq ((char *)iter2->data, (char *)iter1->data, buf);
457 iter1 = iter1->n;
458 iter2 = iter2->n;
459 }
460
461 r_list_free (list1);
462 r_list_free (list2);
463 mu_end;
464 }
465
all_tests()466 int all_tests() {
467 mu_run_test(test_r_list_size);
468 mu_run_test(test_r_list_values);
469 mu_run_test(test_r_list_join);
470 mu_run_test(test_r_list_free);
471 mu_run_test(test_r_list_del_n);
472 mu_run_test(test_r_list_sort);
473 mu_run_test(test_r_list_sort2);
474 mu_run_test(test_r_list_sort3);
475 mu_run_test(test_r_list_sort4);
476 mu_run_test(test_r_list_sort5);
477 mu_run_test(test_r_list_mergesort_pint);
478 mu_run_test(test_r_list_length);
479 mu_run_test(test_r_list_append_prepend);
480 mu_run_test(test_r_list_set_get);
481 mu_run_test(test_r_list_reverse);
482 mu_run_test(test_r_list_clone);
483 return tests_passed != tests_run;
484 }
485
main(int argc,char ** argv)486 int main(int argc, char **argv) {
487 return all_tests();
488 }
489