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