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