1 /*-
2 * Copyright (c) 2002, 2020 Oracle and/or its affiliates. All rights reserved.
3 *
4 * See the file LICENSE for license information.
5 *
6 * A C test for the queue access method.
7 * TODO: Make this more consistent with the CuTest harness.
8 */
9
10 #include "db.h"
11 #include "CuTest.h"
12
13 #include <sys/types.h>
14
15 #include <assert.h>
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <string.h>
19
20 #ifndef _WINDOWS
21 #include <sys/time.h>
22 #include <unistd.h>
23 #endif
24
25 #include "dbinc/queue.h"
26 #include "dbinc/shqueue.h"
27
28 typedef enum {
29 FORWARD_WALK_FAILED = 1,
30 FOREACH_WALK_FAILED,
31 LIST_END_NOT_MARKED_FAILURE,
32 PREV_WALK_FAILED,
33 REVERSE_FOREACH_WALK_FAILED,
34 EXPECTED_HEAD_FAILED
35 } FAILURE_REASON;
36
37 const char *failure_reason_names[] = {
38 "",
39 "walking the list using the _NEXT forward failed",
40 "walking the list using the _FOREACH macro failed",
41 "what was expected to be the last element wasn't marked as such",
42 "walking the list using the _PREV macro failed",
43 "walking the list using the _REVERSE_FOREACH macro failed",
44 "expected to be at the head of the list"
45 };
46
47 SH_LIST_HEAD(sh_lq);
48 struct sh_le {
49 char content;
50 SH_LIST_ENTRY sh_les;
51 };
52
53 /* create a string from the content of a list queue */
54 char *
sh_l_as_string(l)55 sh_l_as_string(l)
56 struct sh_lq *l;
57 {
58 static char buf[1024];
59 struct sh_le *ele = SH_LIST_FIRST(l, sh_le);
60 int i = 1;
61
62 buf[0] = '"';
63 while (ele != NULL) {
64 buf[i] = ele->content;
65 ele = SH_LIST_NEXT(ele, sh_les, sh_le);
66 if (ele != NULL)
67 buf[++i] = ' ';
68 i++;
69 }
70 buf[i++] = '"';
71 buf[i] = '\0';
72 return buf;
73 }
74
75 /* init a list queue */
76 struct sh_lq *
sh_l_init(items)77 sh_l_init(items)
78 const char *items;
79 {
80 const char *c = items;
81 struct sh_le *ele = NULL, *last_ele = (struct sh_le*)-1;
82 struct sh_lq *l = calloc(1, sizeof(struct sh_lq));
83
84 SH_LIST_INIT(l);
85
86 while (*c != '\0') {
87 if (c[0] != ' ') {
88 last_ele = ele;
89 ele = calloc(1, sizeof(struct sh_le));
90 ele->content = c[0];
91 if (SH_LIST_EMPTY(l))
92 SH_LIST_INSERT_HEAD(l, ele, sh_les, sh_le);
93 else
94 SH_LIST_INSERT_AFTER(
95 last_ele, ele, sh_les, sh_le);
96 }
97 c++;
98 }
99 return (l);
100 }
101
102 struct sh_lq *
sh_l_remove_head(l)103 sh_l_remove_head(l)
104 struct sh_lq *l;
105 {
106 struct sh_le *ele = SH_LIST_FIRST(l, sh_le);
107
108 SH_LIST_REMOVE_HEAD(l, sh_les, sh_le);
109 if (ele != NULL)
110 free(ele);
111
112 return (l);
113 }
114
115 struct sh_lq *
sh_l_remove_tail(l)116 sh_l_remove_tail(l)
117 struct sh_lq *l;
118 {
119 struct sh_le *ele = SH_LIST_FIRST(l, sh_le);
120
121 if (SH_LIST_EMPTY(l))
122 return (l);
123
124 while (SH_LIST_NEXT(ele, sh_les, sh_le) != NULL)
125 ele = SH_LIST_NEXT(ele, sh_les, sh_le);
126
127 if (ele) {
128 SH_LIST_REMOVE(ele, sh_les, sh_le);
129 free(ele);
130 }
131 return (l);
132 }
133
134 struct sh_lq *
sh_l_remove_item(l,item)135 sh_l_remove_item(l, item)
136 struct sh_lq *l;
137 const char *item;
138 {
139 struct sh_le *ele = SH_LIST_FIRST(l, sh_le);
140
141 while (ele != NULL) {
142 if (ele->content == item[0])
143 break;
144 ele = SH_LIST_NEXT(ele, sh_les, sh_le);
145 }
146 if (ele)
147 SH_LIST_REMOVE(ele, sh_les, sh_le);
148 return (l);
149 }
150
151 struct sh_lq *
sh_l_insert_head(l,item)152 sh_l_insert_head(l, item)
153 struct sh_lq *l;
154 const char *item;
155 {
156 struct sh_le *ele = calloc(1, sizeof(struct sh_le));
157
158 ele->content = item[0];
159 SH_LIST_INSERT_HEAD(l, ele, sh_les, sh_le);
160
161 return (l);
162 }
163
164 struct sh_lq *
sh_l_insert_tail(l,item)165 sh_l_insert_tail(l, item)
166 struct sh_lq *l;
167 const char *item;
168 {
169 struct sh_le *ele = NULL;
170 struct sh_le *last_ele = SH_LIST_FIRST(l, sh_le);
171
172 if (last_ele != NULL)
173 while (SH_LIST_NEXT(last_ele, sh_les, sh_le) != NULL)
174 last_ele = SH_LIST_NEXT(last_ele, sh_les, sh_le);
175
176 if (last_ele == NULL) {
177 ele = calloc(1, sizeof(struct sh_le));
178 ele->content = item[0];
179 SH_LIST_INSERT_HEAD(l, ele, sh_les, sh_le);
180 } else {
181 ele = calloc(1, sizeof(struct sh_le));
182 ele->content = item[0];
183 SH_LIST_INSERT_AFTER(last_ele, ele, sh_les, sh_le);
184 }
185
186 return (l);
187 }
188
189 struct sh_lq *
sh_l_insert_before(l,item,before_item)190 sh_l_insert_before(l, item, before_item)
191 struct sh_lq *l;
192 const char *item;
193 const char *before_item;
194 {
195 struct sh_le *ele = NULL;
196 struct sh_le *before_ele = SH_LIST_FIRST(l, sh_le);
197
198 while (before_ele != NULL) {
199 if (before_ele->content == before_item[0])
200 break;
201 before_ele = SH_LIST_NEXT(before_ele, sh_les, sh_le);
202 }
203 if (before_ele != NULL) {
204 ele = calloc(1, sizeof(struct sh_le));
205 ele->content = item[0];
206 SH_LIST_INSERT_BEFORE(l, before_ele, ele, sh_les, sh_le);
207 }
208 return (l);
209 }
210
211 struct sh_lq *
sh_l_insert_after(l,item,after_item)212 sh_l_insert_after(l, item, after_item)
213 struct sh_lq *l;
214 const char *item;
215 const char *after_item;
216 {
217 struct sh_le *ele = NULL;
218 struct sh_le *after_ele = SH_LIST_FIRST(l, sh_le);
219
220 while (after_ele != NULL) {
221 if (after_ele->content == after_item[0])
222 break;
223 after_ele = SH_LIST_NEXT(after_ele, sh_les, sh_le);
224 }
225 if (after_ele != NULL) {
226 ele = calloc(1, sizeof(struct sh_le));
227 ele->content = item[0];
228 SH_LIST_INSERT_AFTER(after_ele, ele, sh_les, sh_le);
229 }
230 return (l);
231 }
232
233 void
sh_l_discard(l)234 sh_l_discard(l)
235 struct sh_lq *l;
236 {
237 struct sh_le *ele = NULL;
238
239 while ((ele = SH_LIST_FIRST(l, sh_le)) != NULL) {
240 SH_LIST_REMOVE(ele, sh_les, sh_le);
241 free(ele);
242 }
243
244 free(l);
245 }
246
247 int
sh_l_verify(l,items)248 sh_l_verify(l, items)
249 struct sh_lq *l;
250 const char *items;
251 {
252 const char *c = items;
253 struct sh_le *ele = NULL, *lele = NULL;
254 int i = 0, nele = 0;
255
256 while (*c != '\0') {
257 if (c[0] != ' ')
258 nele++;
259 c++;
260 }
261
262 /* use the FOREACH macro to walk the list */
263 c = items;
264 i = 0;
265 SH_LIST_FOREACH(ele, l, sh_les, sh_le) {
266 if (ele->content != c[0])
267 return (FOREACH_WALK_FAILED);
268 i++;
269 c +=2;
270 }
271 if (i != nele)
272 return (FOREACH_WALK_FAILED);
273 i = 0;
274 if (items[0] != '\0') {
275 /* walk the list forward */
276 c = items;
277 ele = SH_LIST_FIRST(l, sh_le);
278 while (*c != '\0') {
279 lele = ele;
280 if (c[0] != ' ') {
281 if (ele->content != c[0])
282 return (FORWARD_WALK_FAILED);
283 i++;
284 ele = SH_LIST_NEXT(ele, sh_les, sh_le);
285 }
286 c++;
287 }
288 ele = lele;
289
290 if (i != nele)
291 return (FOREACH_WALK_FAILED);
292
293 /* ele should be the last element in the list... */
294 /* ... so sle_next should be -1 */
295 if (ele->sh_les.sle_next != -1)
296 return (LIST_END_NOT_MARKED_FAILURE);
297
298 /* and NEXT needs to be NULL */
299 if (SH_LIST_NEXT(ele, sh_les, sh_le) != NULL)
300 return (LIST_END_NOT_MARKED_FAILURE);
301
302 /*
303 * walk the list backwards using PREV macro, first move c
304 * back a bit
305 */
306 c--;
307 i = 0;
308 while (c >= items) {
309 if (c[0] != ' ') {
310 lele = ele;
311 if (ele->content != c[0])
312 return (PREV_WALK_FAILED);
313 ele = SH_LIST_PREV(ele, sh_les, sh_le);
314 i++;
315 }
316 c--;
317 }
318 ele = lele;
319
320 if (i != nele)
321 return (PREV_WALK_FAILED);
322
323 if (ele != SH_LIST_FIRST(l, sh_le))
324 return (EXPECTED_HEAD_FAILED);
325 }
326 return (0);
327 }
328
329 SH_TAILQ_HEAD(sh_tq);
330 struct sh_te {
331 char content;
332 SH_TAILQ_ENTRY sh_tes;
333 };
334
335 /* create a string from the content of a list queue */
336 char *
sh_t_as_string(l)337 sh_t_as_string(l)
338 struct sh_tq *l;
339 {
340 static char buf[1024];
341 struct sh_te *ele = SH_TAILQ_FIRST(l, sh_te);
342 int i = 1;
343
344 buf[0] = '"';
345 while (ele != NULL) {
346 buf[i] = ele->content;
347 ele = SH_TAILQ_NEXT(ele, sh_tes, sh_te);
348 if (ele != NULL)
349 buf[++i] = ' ';
350 i++;
351 }
352 buf[i++] = '"';
353 buf[i] = '\0';
354 return (buf);
355 }
356
357 /* init a tail queue */
358 struct sh_tq *
sh_t_init(items)359 sh_t_init(items)
360 const char *items;
361 {
362 const char *c = items;
363 struct sh_te *ele = NULL, *last_ele = (struct sh_te*)-1;
364 struct sh_tq *l = calloc(1, sizeof(struct sh_tq));
365
366 SH_TAILQ_INIT(l);
367
368 while (*c != '\0') {
369 if (c[0] != ' ') {
370 ele = calloc(1, sizeof(struct sh_te));
371 ele->content = c[0];
372
373 if (SH_TAILQ_EMPTY(l))
374 SH_TAILQ_INSERT_HEAD(l, ele, sh_tes, sh_te);
375 else
376 SH_TAILQ_INSERT_AFTER(
377 l, last_ele, ele, sh_tes, sh_te);
378 last_ele = ele;
379 }
380 c++;
381 }
382 return (l);
383 }
384
385 struct sh_tq *
sh_t_remove_head(l)386 sh_t_remove_head(l)
387 struct sh_tq *l;
388 {
389 struct sh_te *ele = SH_TAILQ_FIRST(l, sh_te);
390
391 if (ele != NULL)
392 SH_TAILQ_REMOVE(l, ele, sh_tes, sh_te);
393
394 free(ele);
395
396 return (l);
397 }
398
399 struct sh_tq *
sh_t_remove_tail(l)400 sh_t_remove_tail(l)
401 struct sh_tq *l;
402 {
403 struct sh_te *ele = SH_TAILQ_FIRST(l, sh_te);
404
405 if (SH_TAILQ_EMPTY(l))
406 return (l);
407
408 while (SH_TAILQ_NEXT(ele, sh_tes, sh_te) != NULL)
409 ele = SH_TAILQ_NEXT(ele, sh_tes, sh_te);
410
411 if (ele != NULL) {
412 SH_TAILQ_REMOVE(l, ele, sh_tes, sh_te);
413 free(ele);
414 }
415
416 return (l);
417 }
418
419 struct sh_tq *
sh_t_remove_item(l,item)420 sh_t_remove_item(l, item)
421 struct sh_tq *l;
422 const char *item;
423 {
424 struct sh_te *ele = SH_TAILQ_FIRST(l, sh_te);
425
426 while (ele != NULL) {
427 if (ele->content == item[0])
428 break;
429 ele = SH_TAILQ_NEXT(ele, sh_tes, sh_te);
430 }
431 if (ele != NULL)
432 SH_TAILQ_REMOVE(l, ele, sh_tes, sh_te);
433
434 return (l);
435 }
436
437 struct sh_tq *
sh_t_insert_head(l,item)438 sh_t_insert_head(l, item)
439 struct sh_tq *l;
440 const char *item;
441 {
442 struct sh_te *ele = calloc(1, sizeof(struct sh_te));
443
444 ele->content = item[0];
445 SH_TAILQ_INSERT_HEAD(l, ele, sh_tes, sh_te);
446
447 return (l);
448 }
449
450 struct sh_tq *
sh_t_insert_tail(l,item)451 sh_t_insert_tail(l, item)
452 struct sh_tq *l;
453 const char *item;
454 {
455 struct sh_te *ele = 0;
456 ele = calloc(1, sizeof(struct sh_te));
457 ele->content = item[0];
458 SH_TAILQ_INSERT_TAIL(l, ele, sh_tes);
459 return l;
460 }
461
462 struct sh_tq *
sh_t_insert_before(l,item,before_item)463 sh_t_insert_before(l, item, before_item)
464 struct sh_tq *l;
465 const char *item;
466 const char *before_item;
467 {
468 struct sh_te *ele = NULL;
469 struct sh_te *before_ele = SH_TAILQ_FIRST(l, sh_te);
470
471 while (before_ele != NULL) {
472 if (before_ele->content == before_item[0])
473 break;
474 before_ele = SH_TAILQ_NEXT(before_ele, sh_tes, sh_te);
475 }
476
477 if (before_ele != NULL) {
478 ele = calloc(1, sizeof(struct sh_te));
479 ele->content = item[0];
480 SH_TAILQ_INSERT_BEFORE(l, before_ele, ele, sh_tes, sh_te);
481 }
482
483 return (l);
484 }
485
486 struct sh_tq *
sh_t_insert_after(l,item,after_item)487 sh_t_insert_after(l, item, after_item)
488 struct sh_tq *l;
489 const char *item;
490 const char *after_item;
491 {
492 struct sh_te *ele = NULL;
493 struct sh_te *after_ele = SH_TAILQ_FIRST(l, sh_te);
494
495 while (after_ele != NULL) {
496 if (after_ele->content == after_item[0])
497 break;
498 after_ele = SH_TAILQ_NEXT(after_ele, sh_tes, sh_te);
499 }
500
501 if (after_ele != NULL) {
502 ele = calloc(1, sizeof(struct sh_te));
503 ele->content = item[0];
504 SH_TAILQ_INSERT_AFTER(l, after_ele, ele, sh_tes, sh_te);
505 }
506
507 return (l);
508 }
509
510 void
sh_t_discard(l)511 sh_t_discard(l)
512 struct sh_tq *l;
513 {
514 struct sh_te *ele = NULL;
515
516 while ((ele = SH_TAILQ_FIRST(l, sh_te)) != NULL) {
517 SH_TAILQ_REMOVE(l, ele, sh_tes, sh_te);
518 free(ele);
519 }
520 free(l);
521 }
522
523 int
sh_t_verify(l,items)524 sh_t_verify(l, items)
525 struct sh_tq *l;
526 const char *items;
527 {
528 const char *c = items, *b = NULL;
529 struct sh_te *ele = NULL, *lele = NULL;
530 int i = 0, nele = 0;
531
532 while (*c != '\0') {
533 if (c[0] != ' ')
534 nele++;
535 c++;
536 }
537
538 /* use the FOREACH macro to walk the list */
539 c = items;
540 i = 0;
541 SH_TAILQ_FOREACH(ele, l, sh_tes, sh_te) {
542 if (ele->content != c[0])
543 return (FOREACH_WALK_FAILED);
544 i++;
545 c +=2;
546 }
547 if (i != nele)
548 return (FOREACH_WALK_FAILED);
549 i = 0;
550 if (items[0] != '\0') {
551 /* walk the list forward */
552 c = items;
553 ele = SH_TAILQ_FIRST(l, sh_te);
554 while (*c != '\0') {
555 lele = ele;
556 if (c[0] != ' ') {
557 if (ele->content != c[0])
558 return (FORWARD_WALK_FAILED);
559 i++;
560 ele = SH_TAILQ_NEXT(ele, sh_tes, sh_te);
561 }
562 c++;
563 }
564
565 if (i != nele)
566 return (FOREACH_WALK_FAILED);
567
568 if (lele != SH_TAILQ_LAST(l, sh_tes, sh_te))
569 return (LIST_END_NOT_MARKED_FAILURE);
570 ele = lele;
571
572 /* ele should be the last element in the list... */
573 /* ... so sle_next should be -1 */
574 if (ele->sh_tes.stqe_next != -1)
575 return (LIST_END_NOT_MARKED_FAILURE);
576
577 /* and NEXT needs to be NULL */
578 if (SH_TAILQ_NEXT(ele, sh_tes, sh_te) != NULL)
579 return (LIST_END_NOT_MARKED_FAILURE);
580
581 /* walk the list backwards using SH_LIST_PREV macro */
582 c--;
583 b = c;
584 i = 0;
585 while (c >= items) {
586 if (c[0] != ' ') {
587 lele = ele;
588 if (ele->content != c[0])
589 return (PREV_WALK_FAILED);
590 ele = SH_TAILQ_PREV(l, ele, sh_tes, sh_te);
591 i++;
592 }
593 c--;
594 }
595 ele = lele;
596
597 if (i != nele)
598 return (PREV_WALK_FAILED);
599
600 if (ele != SH_TAILQ_FIRST(l, sh_te))
601 return (-1);
602
603 /* c should be the last character in the array, walk backwards
604 from here using FOREACH_REVERSE and check the values again */
605 c = b;
606 i = 0;
607 ele = SH_TAILQ_LAST(l, sh_tes, sh_te);
608 SH_TAILQ_FOREACH_REVERSE(ele, l, sh_tes, sh_te) {
609 if (ele->content != c[0])
610 return (REVERSE_FOREACH_WALK_FAILED);
611 i++;
612 c -=2;
613 }
614 if (i != nele)
615 return (REVERSE_FOREACH_WALK_FAILED);
616 }
617 return (0);
618 }
619
620 int
sh_t_verify_TAILQ_LAST(l,items)621 sh_t_verify_TAILQ_LAST(l, items)
622 struct sh_tq *l;
623 const char *items;
624 {
625 const char *c = items;
626 struct sh_te *ele = NULL;
627
628 c = items;
629 while (*c != '\0') {
630 c++;
631 }
632 if (c == items) {
633 /* items is empty, so last should be NULL */
634 if (SH_TAILQ_LAST(l, sh_tes, sh_te) != NULL)
635 return (-1);
636 } else {
637 c--;
638 ele = SH_TAILQ_LAST(l, sh_tes, sh_te);
639 if (ele->content != c[0])
640 return (-1);
641 }
642 return (0);
643 }
644
645 typedef void *qds_t;
646 struct {
647 const char *name;
648 qds_t *(*f_init)(const char *);
649 qds_t *(*f_remove_head)(qds_t *);
650 qds_t *(*f_remove_tail)(qds_t *);
651 qds_t *(*f_remove_item)(qds_t *, const char *);
652 qds_t *(*f_insert_head)(qds_t *, const char *);
653 qds_t *(*f_insert_tail)(qds_t *, const char *);
654 qds_t *(*f_insert_before)(qds_t *, const char *, const char *);
655 qds_t *(*f_insert_after)(qds_t *, const char *, const char *);
656 qds_t *(*f_discard)(qds_t *);
657 char *(*f_as_string)(qds_t *);
658 int (*f_verify)(qds_t *, const char *);
659 } qfns[]= {
660 { "sh_list",
661 (qds_t*(*)(const char *))sh_l_init,
662 (qds_t*(*)(qds_t *))sh_l_remove_head,
663 (qds_t*(*)(qds_t *))sh_l_remove_tail,
664 (qds_t*(*)(qds_t *, const char *))sh_l_remove_item,
665 (qds_t*(*)(qds_t *, const char *))sh_l_insert_head,
666 (qds_t*(*)(qds_t *, const char *))sh_l_insert_tail,
667 (qds_t*(*)(qds_t *, const char *, const char *))sh_l_insert_before,
668 (qds_t*(*)(qds_t *, const char *, const char *))sh_l_insert_after,
669 (qds_t*(*)(qds_t *))sh_l_discard,
670 (char *(*)(qds_t *))sh_l_as_string,
671 (int(*)(qds_t *, const char *))sh_l_verify },
672 { "sh_tailq",
673 (qds_t*(*)(const char *))sh_t_init,
674 (qds_t*(*)(qds_t *))sh_t_remove_head,
675 (qds_t*(*)(qds_t *))sh_t_remove_tail,
676 (qds_t*(*)(qds_t *, const char *))sh_t_remove_item,
677 (qds_t*(*)(qds_t *, const char *))sh_t_insert_head,
678 (qds_t*(*)(qds_t *, const char *))sh_t_insert_tail,
679 (qds_t*(*)(qds_t *, const char *, const char *))sh_t_insert_before,
680 (qds_t*(*)(qds_t *, const char *, const char *))sh_t_insert_after,
681 (qds_t*(*)(qds_t *))sh_t_discard,
682 (char *(*)(qds_t *))sh_t_as_string,
683 (int(*)(qds_t *, const char *))sh_t_verify }
684 };
685
686 typedef enum {
687 INSERT_BEFORE,
688 INSERT_AFTER,
689 INSERT_HEAD,
690 INSERT_TAIL,
691 REMOVE_HEAD,
692 REMOVE_ITEM,
693 REMOVE_TAIL,
694 } OP;
695
696 const char *op_names[] = {
697 "INSERT_BEFORE",
698 "INSERT_AFTER",
699 "INSERT_HEAD",
700 "INSERT_TAIL",
701 "REMOVE_HEAD",
702 "REMOVE_ITEM",
703 "REMOVE_TAIL" };
704
705 struct {
706 char *init; /* initial state. */
707 char *final; /* final state. */
708 char *elem; /* element to operate on */
709 char *insert; /* element to insert */
710 OP op; /* operation. */
711 } ops[] = {
712
713 /* most operations on a empty list */
714 { "", "", NULL, NULL, REMOVE_HEAD },
715 { "", "", NULL, NULL, REMOVE_TAIL },
716 { "", "A", NULL, "A", INSERT_HEAD },
717 { "", "A", NULL, "A", INSERT_TAIL },
718
719 /* all operations on a one element list */
720 { "A", "", NULL, NULL, REMOVE_HEAD },
721 { "A", "", NULL, NULL, REMOVE_TAIL },
722 { "A", "", "A", NULL, REMOVE_ITEM },
723 { "B", "A B", NULL, "A", INSERT_HEAD },
724 { "A", "A B", NULL, "B", INSERT_TAIL },
725 { "B", "A B", "B", "A", INSERT_BEFORE },
726 { "A", "A B", "A", "B", INSERT_AFTER },
727
728 /* all operations on a two element list */
729 { "A B", "B", NULL, NULL, REMOVE_HEAD },
730 { "A B", "A", NULL, NULL, REMOVE_TAIL },
731 { "A B", "A", "B", NULL, REMOVE_ITEM },
732 { "A B", "B", "A", NULL, REMOVE_ITEM },
733 { "B C", "A B C", NULL, "A", INSERT_HEAD },
734 { "A B", "A B C", NULL, "C", INSERT_TAIL },
735 { "B C", "A B C", "B", "A", INSERT_BEFORE },
736 { "A C", "A B C", "C", "B", INSERT_BEFORE },
737 { "A C", "A B C", "A", "B", INSERT_AFTER },
738 { "A C", "A C B", "C", "B", INSERT_AFTER },
739
740 /* all operations on a three element list */
741
742 { "A B C", "B C", NULL, NULL, REMOVE_HEAD },
743 { "A B C", "A B", NULL, NULL, REMOVE_TAIL },
744 { "A B C", "A B", "C", NULL, REMOVE_ITEM },
745 { "A B C", "A C", "B", NULL, REMOVE_ITEM },
746 { "A B C", "B C", "A", NULL, REMOVE_ITEM },
747 { "B C D", "A B C D", NULL, "A", INSERT_HEAD },
748 { "A B C", "A B C D", NULL, "D", INSERT_TAIL },
749 { "A B C", "X A B C", "A", "X", INSERT_BEFORE },
750 { "A B C", "A X B C", "B", "X", INSERT_BEFORE },
751 { "A B C", "A B X C", "C", "X", INSERT_BEFORE },
752 { "A B C", "A X B C", "A", "X", INSERT_AFTER },
753 { "A B C", "A B X C", "B", "X", INSERT_AFTER },
754 { "A B C", "A B C X", "C", "X", INSERT_AFTER },
755 };
756
TestQueue(CuTest * ct)757 int TestQueue(CuTest *ct) {
758 void *list;
759 int fc, tc; /* tc is total count, fc is failed count */
760 int eval, i, t, result;
761
762 eval = 0;
763 for (t = 0; t < sizeof(qfns) / sizeof(qfns[0]); ++t) {
764 fc = tc = 0;
765 printf("TESTING: %s\n", qfns[t].name);
766
767 for (i = 0; i < sizeof(ops) / sizeof(ops[0]); i++) {
768 list = qfns[t].f_init(ops[i].init);
769 result = qfns[t].f_verify(list, ops[i].init);
770 if (result == 0) {
771 fc++;
772 putchar('.');
773 } else {
774 putchar('+'); /* + means failed before op */
775 printf("\nVerify failed: %s\n",
776 failure_reason_names[result]);
777 eval = 1;
778 }
779 if (!strcmp("sh_tailq", qfns[t].name)) {
780 result =
781 sh_t_verify_TAILQ_LAST(
782 (struct sh_tq *)list, ops[i].init);
783 }
784 #ifdef VERBOSE
785 printf("\ncase %d %s in %s init: \"%s\" desired: \"%s\" elem: \"%s\" insert: \"%s\"\n",
786 i, op_names[ops[i].op], qfns[t].name,
787 ops[i].init, ops[i].final,
788 ops[i].elem, ops[i].insert);
789 fflush(stdout);
790 #endif
791 tc++;
792 switch (ops[i].op) {
793 case REMOVE_HEAD:
794 qfns[t].f_remove_head(list);
795 break;
796 case REMOVE_TAIL:
797 qfns[t].f_remove_tail(list);
798 break;
799 case REMOVE_ITEM:
800 qfns[t].f_remove_item(list, ops[i].elem);
801 break;
802 case INSERT_HEAD:
803 qfns[t].f_insert_head(list, ops[i].insert);
804 break;
805 case INSERT_TAIL:
806 qfns[t].f_insert_tail(list, ops[i].insert);
807 break;
808 case INSERT_BEFORE:
809 qfns[t].f_insert_before(
810 list, ops[i].insert, ops[i].elem);
811 break;
812 case INSERT_AFTER:
813 qfns[t].f_insert_after(
814 list, ops[i].insert, ops[i].elem);
815 break;
816 }
817 if (!strcmp("sh_tailq", op_names[ops[i].op])) {
818 result = sh_t_verify_TAILQ_LAST(
819 (struct sh_tq *)list, ops[i].final);
820 }
821 if (result == 0)
822 result = qfns[t].f_verify(list, ops[i].final);
823 if (result == 0) {
824 fc++;
825 putchar('.');
826 } else {
827 putchar('*'); /* * means failed after op */
828 printf("\ncase %d %s in %s init: \"%s\" desired: \"%s\" elem: \"%s\" insert: \"%s\" got: %s - %s\n",
829 i, op_names[ops[i].op], qfns[t].name,
830 ops[i].init, ops[i].final,
831 ops[i].elem, ops[i].insert,
832 qfns[t].f_as_string(list),
833 failure_reason_names[result]);
834 fflush(stdout);
835 eval = 1;
836 }
837
838 tc++;
839 qfns[t].f_discard(list);
840 }
841
842 printf("\t%0.2f%% passed (%d/%d).\n",
843 (((double)fc/tc) * 100), fc, tc);
844 }
845 return (eval);
846 }
847