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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 571 test_12_compar(const void *a, const void *b) 572 { 573 return (int)a - (int)b; 574 } 575 576 static void 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 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 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