1 /* $OpenBSD: slist_test.c,v 1.6 2016/03/16 15:41:11 krw Exp $ */
2 /*-
3 * Copyright (c) 2009 Internet Initiative Japan Inc.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 */
27 /*
28
29 cc -g -Wall -o slist_test slist_test.c slist.c
30 ./slist_test
31
32
33 */
34 #include <sys/types.h>
35 #include <stdlib.h>
36 #include <stdio.h>
37 #include "slist.h"
38
39 #define TEST(f) \
40 { \
41 printf("%-10s .. ", #f); \
42 f(); \
43 printf("ok\n"); \
44 }
45
46 #define ASSERT(x) \
47 if (!(x)) { \
48 fprintf(stderr, \
49 "\nASSERT(%s) failed on %s() at %s:%d.\n" \
50 , #x, __func__, __FILE__, __LINE__); \
51 dump(l); \
52 abort(); \
53 }
54
55 static void
dump(slist * l)56 dump(slist *l)
57 {
58 int i;
59
60 fprintf(stderr,
61 "\tl->itr_curr = %d\n"
62 "\tl->itr_next = %d\n"
63 "\tl->first_idx = %d\n"
64 "\tl->last_idx = %d\n"
65 "\tl->list_size = %d\n"
66 , l->itr_curr, l->itr_next, l->first_idx, l->last_idx
67 , l->list_size);
68 for (i = 0; i < slist_length(l); i++) {
69 if ((i % 16) == 0)
70 fprintf(stderr, "%08x ", i);
71 fprintf(stderr, " %3d", (int)slist_get(l, i));
72 if ((i % 16) == 7)
73 fprintf(stderr, " -");
74 if ((i % 16) == 15)
75 fprintf(stderr, "\n");
76 }
77 if ((i % 16) != 0)
78 fprintf(stderr, "\n");
79 }
80
81 /* Test code for removing of the first, last and middle item. */
82 static void
test_01a()83 test_01a()
84 {
85 int i, f;
86 slist sl;
87 slist *l = &sl;
88
89 slist_init(&sl);
90 slist_add(&sl, (void *)1);
91
92 ASSERT(sl.list_size == 256);
93
94 #define SETUP() \
95 { \
96 l->last_idx = 64; \
97 l->first_idx = 192; \
98 for (i = 0; i < slist_length(l); i++) { \
99 slist_set(l, i, (void *)i); \
100 } \
101 }
102
103 /* Remove the first item. */
104 SETUP();
105 f = 0;
106 while (slist_length(l) > 0) {
107 slist_remove(l, 0);
108 f++;
109 for (i = 0; i < slist_length(l); i++) {
110 ASSERT((int)slist_get(l, i) == i + f);
111 }
112 }
113
114 /* Remove the last item. */
115 SETUP();
116 while (slist_length(l) > 0) {
117 slist_remove(l, slist_length(l) - 1);
118 for (i = 0; i < slist_length(l); i++) {
119 ASSERT((int)slist_get(l, i) == i);
120 }
121 }
122 /* Remove the second item from the end. */
123 SETUP();
124 while (slist_length(l) > 1) {
125 slist_remove(l, slist_length(l) - 2);
126 for (i = 0; i < slist_length(l) - 1; i++) {
127 ASSERT((int)slist_get(l, i) == i);
128 }
129 if (slist_length(l) > 0) {
130 ASSERT((int)slist_get(l, slist_length(l) - 1) == 127);
131 }
132 }
133 slist_remove(l, slist_length(l) - 1);
134 ASSERT(slist_length(l) == 0);
135 }
136
137 static void
test_01()138 test_01()
139 {
140 int i;
141 slist sl;
142 slist *l = &sl;
143
144 slist_init(&sl);
145
146
147 for (i = 0; i < 255; i++) {
148 slist_add(&sl, (void *)i);
149 }
150 for (i = 0; i < 128; i++) {
151 slist_remove_first(&sl);
152 }
153 for (i = 0; i < 128; i++) {
154 slist_add(&sl, (void *)(i + 255));
155 }
156 ASSERT((int)slist_get(&sl, 127) == 255);
157 ASSERT((int)slist_get(&sl, 254) == 129 + 253);
158 ASSERT((int)slist_length(&sl) == 255);
159
160 /* dump(&sl); */
161 /* printf("==\n"); */
162 slist_add(&sl, (void *)(128 + 255));
163 ASSERT((int)slist_get(&sl, 127) == 255);
164 /* ASSERT((int)slist_get(&sl, 255) == 128 + 255); */
165 ASSERT((int)slist_length(&sl) == 256);
166 /* dump(&sl); */
167 }
168
169 static void
test_02()170 test_02()
171 {
172 int i;
173 slist sl;
174 slist *l = &sl;
175
176 slist_init(&sl);
177
178
179 /* Place 300 items for left side and 211 items for right side. */
180 for (i = 0; i < 511; i++)
181 slist_add(&sl, (void *)i);
182 for (i = 0; i <= 300; i++)
183 slist_remove_first(&sl);
184 for (i = 0; i <= 300; i++)
185 slist_add(&sl, (void *)i);
186
187
188 /* Set values to make index number and value the same. */
189 for (i = 0; i < slist_length(&sl); i++)
190 slist_set(&sl, i, (void *)(i + 1));
191
192 ASSERT(slist_length(&sl) == 511); /* The logical length is 511. */
193 ASSERT((int)sl.list[511] == 211); /* The most right is 211th. */
194 ASSERT((int)sl.list[0] == 212); /* The most left is 212th. */
195 ASSERT(sl.list_size == 512); /* The physical size is 512. */
196
197 slist_add(&sl, (void *)512); /* Add 512th item. */
198
199 ASSERT(sl.list_size == 768); /* The physical size is extended. */
200 ASSERT(slist_length(&sl) == 512); /* The logical length is 512. */
201 ASSERT((int)sl.list[511] == 211); /* boundary */
202 ASSERT((int)sl.list[512] == 212); /* boundary */
203 ASSERT((int)sl.list[767] == 467); /* The most right is 467th. */
204 ASSERT((int)sl.list[0] == 468); /* The most left is 468th. */
205
206 /* Check all items */
207 for (i = 0; i < slist_length(&sl); i++)
208 ASSERT((int)slist_get(&sl, i) == i + 1); /* check */
209 }
210
211 static void
test_03()212 test_03()
213 {
214 int i;
215 slist sl;
216 slist *l = &sl;
217
218 slist_init(&sl);
219 slist_add(&sl, (void *)1);
220
221 for (i = 0; i < 255; i++) {
222 slist_add(&sl, (void *)1);
223 ASSERT(sl.last_idx >= 0 && sl.last_idx < sl.list_size);
224 slist_remove_first(&sl);
225 ASSERT(sl.last_idx >= 0 && sl.last_idx < sl.list_size);
226 }
227 slist_remove(&sl, 0);
228 ASSERT(slist_length(&sl) == 0);
229 /* dump(&sl); */
230 /* TEST(test_02); */
231 }
232
233 static void
test_itr_subr_01(slist * l)234 test_itr_subr_01(slist *l)
235 {
236 int i;
237
238 for (i = 0; i < slist_length(l); i++)
239 slist_set(l, i, (void *)(i + 1));
240
241 slist_itr_first(l);
242 ASSERT((int)slist_itr_next(l) == 1); /* normal iterate */
243 ASSERT((int)slist_itr_next(l) == 2); /* normal iterate */
244 slist_remove(l, 2); /* remove next. "3" is removed */
245 ASSERT((int)slist_itr_next(l) == 4); /* removed item is skipped */
246 slist_remove(l, 1); /* remove past item. "2" is removed */
247 ASSERT((int)slist_itr_next(l) == 5); /* no influence */
248 ASSERT((int)slist_get(l, 0) == 1); /* checking for removing */
249 ASSERT((int)slist_get(l, 1) == 4); /* checking for removing */
250 ASSERT((int)slist_get(l, 2) == 5); /* checking for removing */
251
252 /*
253 * Total number was 255. We removed 2 items and iterated 4 times.
254 * 1 removing was past item, so the remaining is 250.
255 */
256
257 for (i = 0; i < 249; i++)
258 ASSERT(slist_itr_next(l) != NULL);
259 ASSERT(slist_itr_next(l) != NULL);
260 ASSERT(slist_itr_next(l) == NULL);
261
262 /*
263 * Same as above except removing before getting the last item.
264 */
265
266 /* Reset (253 items) */
267 for (i = 0; i < slist_length(l); i++)
268 slist_set(l, i, (void *)(i + 1));
269 slist_itr_first(l);
270
271 ASSERT(slist_length(l) == 253);
272
273 for (i = 0; i < 252; i++)
274 ASSERT(slist_itr_next(l) != NULL);
275
276 slist_remove(l, 252);
277 ASSERT(slist_itr_next(l) == NULL); /* The last item is NULL */
278
279 slist_itr_first(l);
280 while (slist_length(l) > 0)
281 slist_remove_first(l);
282 ASSERT(slist_length(l) == 0);
283 ASSERT(slist_itr_next(l) == NULL);
284 }
285
286 static void
test_04()287 test_04()
288 {
289 int i;
290 slist sl;
291 slist *l = &sl;
292
293 slist_init(&sl);
294 for (i = 0; i < 255; i++)
295 slist_add(&sl, (void *)(i + 1));
296
297 test_itr_subr_01(&sl);
298
299 for (i = 0; i < 256; i++) {
300 /* Verify any physical placements are OK by rotating. */
301 sl.first_idx = i;
302 sl.last_idx = sl.first_idx + 255;
303 sl.last_idx %= sl.list_size;
304 ASSERT(slist_length(&sl) == 255);
305 test_itr_subr_01(&sl);
306 }
307 }
308
309 /* Verify removing the last item on the physical location */
310 static void
test_05()311 test_05()
312 {
313 int i;
314 slist sl;
315 slist *l = &sl;
316
317 slist_init(&sl);
318 /* Fill */
319 for (i = 0; i < 255; i++) {
320 slist_add(&sl, (void *)i);
321 }
322 /* Remove 254 items */
323 for (i = 0; i < 254; i++) {
324 slist_remove_first(&sl);
325 }
326 slist_set(l, 0, NULL);
327 /* Add 7 items */
328 for (i = 0; i < 8; i++) {
329 slist_add(&sl, (void *)i + 1);
330 }
331 ASSERT(sl.first_idx == 254);
332 ASSERT(sl.last_idx == 7);
333
334 slist_remove(l, 0);
335 ASSERT((int)slist_get(l, 0) == 1);
336 ASSERT((int)slist_get(l, 1) == 2);
337 ASSERT((int)slist_get(l, 2) == 3);
338 ASSERT((int)slist_get(l, 3) == 4);
339 ASSERT((int)slist_get(l, 4) == 5);
340 ASSERT((int)slist_get(l, 5) == 6);
341 ASSERT((int)slist_get(l, 6) == 7);
342 ASSERT((int)slist_get(l, 7) == 8);
343 ASSERT(l->first_idx == 255);
344
345 slist_remove(l, 0);
346 ASSERT((int)slist_get(l, 0) == 2);
347 ASSERT((int)slist_get(l, 1) == 3);
348 ASSERT((int)slist_get(l, 2) == 4);
349 ASSERT((int)slist_get(l, 3) == 5);
350 ASSERT((int)slist_get(l, 4) == 6);
351 ASSERT((int)slist_get(l, 5) == 7);
352 ASSERT((int)slist_get(l, 6) == 8);
353 ASSERT(l->first_idx == 0);
354 }
355
356 static void
test_06()357 test_06()
358 {
359 int i, j;
360 slist sl;
361 slist *l = &sl;
362
363 slist_init(l);
364 for (i = 0; i < 255; i++)
365 slist_add(l, (void *)i);
366
367 i = 255;
368
369 for (slist_itr_first(l); slist_itr_has_next(l); ) {
370 ASSERT(slist_length(l) == i);
371 slist_itr_next(l);
372 ASSERT((int)slist_itr_remove(l) == 255 - i);
373 ASSERT(slist_length(l) == i - 1);
374 for (j = i; j < slist_length(l); j++)
375 ASSERT((int)slist_get(l, j) == i + j);
376 i--;
377 }
378 }
379
380 static void
test_07()381 test_07()
382 {
383 int i;
384 slist sl;
385 slist *l = &sl;
386
387 slist_init(l);
388 slist_add(l, (void *)1);
389 slist_remove_first(l);
390 l->first_idx = 120;
391 l->last_idx = 120;
392 for (i = 0; i < 255; i++)
393 slist_add(l, (void *)i);
394
395
396 for (i = 0, slist_itr_first(l); slist_itr_has_next(l); i++) {
397 ASSERT((int)slist_itr_next(l) == i);
398 if (i > 200)
399 ASSERT((int)slist_itr_remove(l) == i);
400 }
401 }
402
403 static void
test_08()404 test_08()
405 {
406 slist sl;
407 slist *l = &sl;
408
409 slist_init(l);
410 slist_set_size(l, 4);
411 slist_add(l, (void *)1);
412 slist_add(l, (void *)2);
413 slist_add(l, (void *)3);
414
415 /* [1, 2, 3] */
416
417 slist_itr_first(l);
418 slist_itr_has_next(l);
419 slist_itr_next(l);
420 slist_itr_remove(l);
421 /* [2, 3] */
422
423 slist_add(l, (void *)4);
424 /* [2, 3, 4] */
425 ASSERT((int)slist_get(l, 0) == 2);
426 ASSERT((int)slist_get(l, 1) == 3);
427 ASSERT((int)slist_get(l, 2) == 4);
428 slist_add(l, (void *)5);
429
430 /* [2, 3, 4, 5] */
431 ASSERT((int)slist_get(l, 0) == 2);
432 ASSERT((int)slist_get(l, 1) == 3);
433 ASSERT((int)slist_get(l, 2) == 4);
434 ASSERT((int)slist_get(l, 3) == 5);
435 }
436
437 static void
test_09()438 test_09()
439 {
440 slist sl;
441 slist *l = &sl;
442
443 /*
444 * #1
445 */
446 slist_init(l);
447 slist_set_size(l, 3);
448 slist_add(l, (void *)1);
449 slist_add(l, (void *)2);
450 slist_add(l, (void *)3);
451
452 slist_itr_first(l);
453 ASSERT((int)slist_itr_next(l) == 1); /* 1 */
454 ASSERT((int)slist_itr_next(l) == 2); /* 2 */
455 ASSERT((int)slist_itr_next(l) == 3); /* 3 */
456 /* reaches the last */
457 slist_add(l, (void *)4); /* add a new item */
458 ASSERT(slist_itr_has_next(l)); /* iterates the new */
459 ASSERT((int)slist_itr_next(l) == 4);
460 slist_fini(l);
461
462
463 /*
464 * #2
465 */
466 slist_init(l);
467 slist_set_size(l, 3);
468 slist_add(l, (void *)1);
469 slist_add(l, (void *)2);
470 slist_add(l, (void *)3);
471
472 slist_itr_first(l);
473 ASSERT((int)slist_itr_next(l) == 1); /* 1 */
474 ASSERT((int)slist_itr_next(l) == 2); /* 2 */
475 ASSERT((int)slist_itr_next(l) == 3); /* 3 */
476 /* reaches the last */
477 slist_itr_remove(l); /* and remove the last*/
478 slist_add(l, (void *)4); /* add 4 (new last)*/
479 ASSERT(slist_itr_has_next(l)); /* */
480 ASSERT((int)slist_itr_next(l) == 4); /* 4 */
481 slist_fini(l);
482
483 /*
484 * #3
485 */
486 slist_init(l);
487 slist_set_size(l, 3);
488 slist_add(l, (void *)1);
489 slist_add(l, (void *)2);
490 slist_add(l, (void *)3);
491
492 slist_itr_first(l);
493 ASSERT((int)slist_itr_next(l) == 1); /* 1 */
494 ASSERT((int)slist_itr_next(l) == 2); /* 2 */
495 ASSERT((int)slist_itr_next(l) == 3); /* 3 */
496 /* reaches the last */
497 slist_add(l, (void *)4); /* add a new */
498 slist_itr_remove(l);
499 ASSERT(slist_itr_has_next(l));
500 ASSERT((int)slist_itr_next(l) == 4); /* 4 */
501 slist_fini(l);
502
503 /*
504 * #4 - remove iterator's next and it is the last
505 */
506 slist_init(l);
507 slist_set_size(l, 3);
508 slist_add(l, (void *)1);
509 slist_add(l, (void *)2);
510 slist_add(l, (void *)3);
511
512 slist_itr_first(l);
513 ASSERT((int)slist_itr_next(l) == 1); /* 1 */
514 ASSERT((int)slist_itr_next(l) == 2); /* 2 */
515 slist_remove(l, 2); /* remove the next */
516 slist_add(l, (void *)4); /* add the new next */
517 ASSERT(slist_itr_has_next(l)); /* iterates the new */
518 ASSERT((int)slist_itr_next(l) == 4);
519 slist_fini(l);
520 }
521 static void
test_10()522 test_10()
523 {
524 int i;
525 slist sl;
526 slist *l = &sl;
527
528 slist_init(l);
529 slist_add(l, (void *)1);
530 slist_add(l, (void *)2);
531 slist_add(l, (void *)3);
532 slist_itr_first(l);
533 ASSERT((int)slist_itr_next(l) == 1);
534 ASSERT((int)slist_itr_next(l) == 2);
535 for (i = 4; i < 10000; i++) {
536 ASSERT(slist_itr_has_next(l));
537 ASSERT((int)slist_itr_next(l) == i - 1);
538 if (i % 3 == 1)
539 slist_add(l, (void *)i);
540 if (i % 3 == 0)
541 ASSERT((int)slist_itr_remove(l) == i - 1);
542 if (i % 3 != 1)
543 slist_add(l, (void *)i);
544 }
545 slist_itr_first(l);
546 while (slist_itr_has_next(l)) {
547 slist_itr_next(l);
548 slist_itr_remove(l);
549 }
550 ASSERT((int)slist_length(l) == 0);
551
552 slist_fini(l);
553 }
554
555 static void
test_11()556 test_11()
557 {
558 slist sl;
559 slist *l = &sl;
560
561 slist_init(l);
562 slist_add(l, (void *)1);
563 slist_add(l, (void *)2);
564 ASSERT((int)slist_remove_last(l) == 2);
565 ASSERT((int)slist_length(l) == 1);
566 ASSERT((int)slist_remove_last(l) == 1);
567 ASSERT((int)slist_length(l) == 0);
568 }
569
570 static int
test_12_compar(const void * a,const void * b)571 test_12_compar(const void *a, const void *b)
572 {
573 return (int)a - (int)b;
574 }
575
576 static void
test_12()577 test_12()
578 {
579 slist sl;
580 slist *l = &sl;
581
582 slist_init(l);
583 slist_add(l, (void *)42);
584 slist_add(l, (void *)15);
585 slist_add(l, (void *)14);
586 slist_add(l, (void *)13);
587 slist_add(l, (void *)29);
588 slist_add(l, (void *)15);
589 slist_add(l, (void *)25);
590 slist_add(l, (void *)55);
591 slist_add(l, (void *)66);
592 slist_add(l, (void *)23);
593 slist_qsort(l, test_12_compar);
594 ASSERT((int)slist_get(l, 0) == 13);
595 ASSERT((int)slist_get(l, 1) == 14);
596 ASSERT((int)slist_get(l, 2) == 15);
597 ASSERT((int)slist_get(l, 3) == 15);
598 ASSERT((int)slist_get(l, 4) == 23);
599 ASSERT((int)slist_get(l, 5) == 25);
600 ASSERT((int)slist_get(l, 6) == 29);
601 ASSERT((int)slist_get(l, 7) == 42);
602 ASSERT((int)slist_get(l, 8) == 55);
603 ASSERT((int)slist_get(l, 9) == 66);
604 }
605
606 static void
test_13()607 test_13()
608 {
609 slist sl;
610 slist *l = &sl;
611
612 slist_init(l);
613 slist_qsort(l, test_12_compar);
614 /* still alive without SIGFPE */
615 }
616
617 int
main(int argc,char * argv[])618 main(int argc, char *argv[])
619 {
620 TEST(test_01);
621 TEST(test_01a);
622 TEST(test_02);
623 TEST(test_03);
624 TEST(test_04);
625 TEST(test_05);
626 TEST(test_06);
627 TEST(test_07);
628 TEST(test_08);
629 TEST(test_09);
630 TEST(test_10);
631 TEST(test_11);
632 TEST(test_12);
633 TEST(test_13);
634 return 0;
635 }
636