1 /******************************************************** 2 Array Library, a simple module for handling arrays of data 3 4 Copyright (C) 2007-2014 Brian Langenberger 5 6 The Array Library is free software; you can redistribute it and/or modify 7 it under the terms of either: 8 9 * the GNU Lesser General Public License as published by the Free 10 Software Foundation; either version 3 of the License, or (at your 11 option) any later version. 12 13 or 14 15 * the GNU General Public License as published by the Free Software 16 Foundation; either version 2 of the License, or (at your option) any 17 later version. 18 19 or both in parallel, as here. 20 21 The Array Library is distributed in the hope that it will be useful, but 22 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 23 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 24 for more details. 25 26 You should have received copies of the GNU General Public License and the 27 GNU Lesser General Public License along with the GNU MP Library. If not, 28 see https://www.gnu.org/licenses/. 29 *******************************************************/ 30 31 #include "array.h" 32 #include <stdlib.h> 33 #include <string.h> 34 #include <limits.h> 35 #include <float.h> 36 #include <assert.h> 37 38 39 #ifndef MIN 40 #define MIN(x, y) ((x) < (y) ? (x) : (y)) 41 #endif 42 #ifndef MAX 43 #define MAX(x, y) ((x) > (y) ? (x) : (y)) 44 #endif 45 46 typedef int(*qsort_cmp)(const void *x, const void *y); 47 48 #define ARRAY_FUNC_DEFINITION(TYPE, CONTENT_TYPE, LINK_TYPE, CONTENT_TYPE_MIN, CONTENT_TYPE_MAX, CONTENT_TYPE_ACCUMULATOR, FORMAT_STRING) \ 49 \ 50 static void \ 51 TYPE##_del(TYPE *self); \ 52 \ 53 static void \ 54 TYPE##_resize(TYPE *self, unsigned minimum); \ 55 \ 56 static void \ 57 TYPE##_resize_for(TYPE *self, unsigned additional_items); \ 58 \ 59 static void \ 60 TYPE##_reset(TYPE *self); \ 61 \ 62 static void \ 63 TYPE##_reset_for(TYPE *self, unsigned minimum); \ 64 \ 65 static void \ 66 TYPE##_append(TYPE *self, CONTENT_TYPE value); \ 67 \ 68 static void \ 69 TYPE##_vappend(TYPE *self, unsigned count, ...); \ 70 \ 71 static void \ 72 TYPE##_mappend(TYPE *self, unsigned count, \ 73 CONTENT_TYPE value); \ 74 \ 75 static void \ 76 TYPE##_insert(TYPE *self, unsigned index, \ 77 CONTENT_TYPE value); \ 78 \ 79 static void \ 80 TYPE##_vset(TYPE *self, unsigned count, ...); \ 81 \ 82 static void \ 83 TYPE##_mset(TYPE *self, unsigned count, \ 84 CONTENT_TYPE value); \ 85 \ 86 static void \ 87 TYPE##_extend(TYPE *self, \ 88 const TYPE *to_add); \ 89 \ 90 static int \ 91 TYPE##_equals(const TYPE *self, \ 92 const TYPE *compare); \ 93 \ 94 static CONTENT_TYPE \ 95 TYPE##_min(const TYPE *self); \ 96 \ 97 static CONTENT_TYPE \ 98 TYPE##_max(const TYPE *self); \ 99 \ 100 static CONTENT_TYPE \ 101 TYPE##_sum(const TYPE *self); \ 102 \ 103 static void \ 104 TYPE##_copy(const TYPE *self, \ 105 TYPE *copy); \ 106 \ 107 static void \ 108 TYPE##_link(const TYPE *self, \ 109 struct LINK_TYPE##_s *link); \ 110 \ 111 static void \ 112 TYPE##_swap(TYPE *self, TYPE *swap); \ 113 \ 114 static void \ 115 TYPE##_head(const TYPE *self, unsigned count, \ 116 TYPE *head); \ 117 \ 118 static void \ 119 TYPE##_tail(const TYPE *self, unsigned count, \ 120 TYPE *tail); \ 121 \ 122 static void \ 123 TYPE##_de_head(const TYPE *self, unsigned count, \ 124 TYPE *tail); \ 125 \ 126 static void \ 127 TYPE##_de_tail(const TYPE *self, unsigned count, \ 128 TYPE *head); \ 129 \ 130 static void \ 131 TYPE##_split(const TYPE *self, unsigned count, \ 132 TYPE *head, TYPE *tail); \ 133 \ 134 static void \ 135 TYPE##_concat(const TYPE *self, \ 136 const TYPE *tail, \ 137 TYPE *combined); \ 138 \ 139 static void \ 140 TYPE##_reverse(TYPE *self); \ 141 \ 142 static void \ 143 TYPE##_sort(TYPE *self); \ 144 \ 145 static void \ 146 TYPE##_print(const TYPE *self, FILE* output); \ 147 \ 148 struct TYPE##_s* \ 149 TYPE##_new(void) \ 150 { \ 151 struct TYPE##_s* a = malloc(sizeof(struct TYPE##_s)); \ 152 a->_ = malloc(sizeof(CONTENT_TYPE) * 1); \ 153 a->len = 0; \ 154 a->total_size = 1; \ 155 \ 156 a->del = TYPE##_del; \ 157 a->resize = TYPE##_resize; \ 158 a->resize_for = TYPE##_resize_for; \ 159 a->reset = TYPE##_reset; \ 160 a->reset_for = TYPE##_reset_for; \ 161 a->append = TYPE##_append; \ 162 a->vappend = TYPE##_vappend; \ 163 a->mappend = TYPE##_mappend; \ 164 a->insert = TYPE##_insert; \ 165 a->vset = TYPE##_vset; \ 166 a->mset = TYPE##_mset; \ 167 a->extend = TYPE##_extend; \ 168 a->equals = TYPE##_equals; \ 169 a->min = TYPE##_min; \ 170 a->max = TYPE##_max; \ 171 a->sum = TYPE##_sum; \ 172 a->copy = TYPE##_copy; \ 173 a->link = TYPE##_link; \ 174 a->swap = TYPE##_swap; \ 175 a->head = TYPE##_head; \ 176 a->tail = TYPE##_tail; \ 177 a->de_head = TYPE##_de_head; \ 178 a->de_tail = TYPE##_de_tail; \ 179 a->split = TYPE##_split; \ 180 a->concat = TYPE##_concat; \ 181 a->reverse = TYPE##_reverse; \ 182 a->sort = TYPE##_sort; \ 183 a->print = TYPE##_print; \ 184 \ 185 return a; \ 186 } \ 187 \ 188 static void \ 189 TYPE##_del(TYPE *self) \ 190 { \ 191 free(self->_); \ 192 free(self); \ 193 } \ 194 \ 195 static void \ 196 TYPE##_resize(TYPE *self, unsigned minimum) \ 197 { \ 198 if (minimum > self->total_size) { \ 199 self->total_size = minimum; \ 200 self->_ = realloc(self->_, \ 201 sizeof(CONTENT_TYPE) * minimum); \ 202 } \ 203 } \ 204 \ 205 static void \ 206 TYPE##_resize_for(TYPE *self, unsigned additional_items) \ 207 { \ 208 self->resize(self, self->len + additional_items); \ 209 } \ 210 \ 211 static void \ 212 TYPE##_reset(TYPE *self) \ 213 { \ 214 self->len = 0; \ 215 } \ 216 \ 217 static void \ 218 TYPE##_reset_for(TYPE *self, unsigned minimum) \ 219 { \ 220 self->reset(self); \ 221 self->resize(self, minimum); \ 222 } \ 223 \ 224 static void \ 225 TYPE##_append(TYPE *self, CONTENT_TYPE value) \ 226 { \ 227 if (self->len == self->total_size) \ 228 self->resize(self, self->total_size * 2); \ 229 \ 230 self->_[self->len++] = value; \ 231 } \ 232 \ 233 static void \ 234 TYPE##_vappend(TYPE *self, unsigned count, ...) \ 235 { \ 236 va_list ap; \ 237 \ 238 self->resize(self, self->len + count); \ 239 va_start(ap, count); \ 240 for (; count > 0; count--) { \ 241 const CONTENT_TYPE i = va_arg(ap, CONTENT_TYPE); \ 242 self->_[self->len++] = i; \ 243 } \ 244 va_end(ap); \ 245 } \ 246 \ 247 static void \ 248 TYPE##_mappend(TYPE *self, unsigned count, CONTENT_TYPE value) \ 249 { \ 250 self->resize(self, self->len + count); \ 251 for (; count > 0; count--) { \ 252 self->_[self->len++] = value; \ 253 } \ 254 } \ 255 \ 256 static void \ 257 TYPE##_insert(TYPE *self, unsigned index, CONTENT_TYPE value) \ 258 { \ 259 index = MIN(index, self->len); \ 260 \ 261 if (self->len == self->total_size) \ 262 self->resize(self, self->total_size * 2); \ 263 \ 264 memmove(self->_ + index + 1, \ 265 self->_ + index, \ 266 (self->len - index) * sizeof(CONTENT_TYPE)); \ 267 self->_[index] = value; \ 268 self->len += 1; \ 269 } \ 270 \ 271 static void \ 272 TYPE##_vset(TYPE *self, unsigned count, ...) \ 273 { \ 274 va_list ap; \ 275 \ 276 self->reset_for(self, count); \ 277 va_start(ap, count); \ 278 for (; count > 0; count--) { \ 279 const CONTENT_TYPE i = va_arg(ap, CONTENT_TYPE); \ 280 self->_[self->len++] = i; \ 281 } \ 282 va_end(ap); \ 283 } \ 284 \ 285 static void \ 286 TYPE##_mset(TYPE *self, unsigned count, \ 287 CONTENT_TYPE value) \ 288 { \ 289 self->reset_for(self, count); \ 290 for (; count > 0; count--) { \ 291 self->_[self->len++] = value; \ 292 } \ 293 } \ 294 \ 295 static void \ 296 TYPE##_extend(TYPE *self, \ 297 const TYPE *to_add) \ 298 { \ 299 self->concat(self, to_add, self); \ 300 } \ 301 \ 302 static int \ 303 TYPE##_equals(const TYPE *self, \ 304 const TYPE *compare) \ 305 { \ 306 assert(self->_); \ 307 assert(compare->_); \ 308 if (self->len == compare->len) { \ 309 return (memcmp(self->_, compare->_, \ 310 sizeof(CONTENT_TYPE) * self->len) == 0); \ 311 } else { \ 312 return 0; \ 313 } \ 314 } \ 315 \ 316 static CONTENT_TYPE \ 317 TYPE##_min(const TYPE *self) \ 318 { \ 319 CONTENT_TYPE min = CONTENT_TYPE_MAX; \ 320 unsigned i; \ 321 \ 322 assert(self->_); \ 323 for (i = 0; i < self->len; i++) \ 324 if (self->_[i] < min) \ 325 min = self->_[i]; \ 326 \ 327 return min; \ 328 } \ 329 \ 330 static CONTENT_TYPE \ 331 TYPE##_max(const TYPE *self) \ 332 { \ 333 CONTENT_TYPE max = CONTENT_TYPE_MIN; \ 334 unsigned i; \ 335 \ 336 assert(self->_); \ 337 for (i = 0; i < self->len; i++) \ 338 if (self->_[i] > max) \ 339 max = self->_[i]; \ 340 \ 341 return max; \ 342 } \ 343 \ 344 static CONTENT_TYPE \ 345 TYPE##_sum(const TYPE *self) \ 346 { \ 347 CONTENT_TYPE accumulator = CONTENT_TYPE_ACCUMULATOR; \ 348 const CONTENT_TYPE *data = self->_; \ 349 unsigned size = self->len; \ 350 unsigned i; \ 351 \ 352 assert(self->_); \ 353 for (i = 0; i < size; i++) \ 354 accumulator += data[i]; \ 355 \ 356 return accumulator; \ 357 } \ 358 \ 359 static void \ 360 TYPE##_copy(const TYPE *self, \ 361 TYPE *copy) \ 362 { \ 363 if (self != copy) { \ 364 copy->resize(copy, self->len); \ 365 memcpy(copy->_, self->_, \ 366 self->len * sizeof(CONTENT_TYPE)); \ 367 copy->len = self->len; \ 368 } \ 369 } \ 370 \ 371 static void \ 372 TYPE##_link(const TYPE *self, \ 373 LINK_TYPE *link) \ 374 { \ 375 link->_ = self->_; \ 376 link->len = self->len; \ 377 } \ 378 \ 379 static void \ 380 TYPE##_swap(TYPE *self, TYPE *swap) \ 381 { \ 382 TYPE temp; \ 383 temp._ = self->_; \ 384 temp.len = self->len; \ 385 temp.total_size = self->total_size; \ 386 self->_ = swap->_; \ 387 self->len = swap->len; \ 388 self->total_size = swap->total_size; \ 389 swap->_ = temp._; \ 390 swap->len = temp.len; \ 391 swap->total_size = temp.total_size; \ 392 } \ 393 \ 394 static void \ 395 TYPE##_head(const TYPE *self, unsigned count, \ 396 TYPE *head) \ 397 { \ 398 const unsigned to_copy = MIN(count, self->len); \ 399 \ 400 if (head != self) { \ 401 head->resize(head, to_copy); \ 402 memcpy(head->_, self->_, sizeof(CONTENT_TYPE) * to_copy); \ 403 head->len = to_copy; \ 404 } else { \ 405 head->len = to_copy; \ 406 } \ 407 } \ 408 \ 409 static void \ 410 TYPE##_tail(const TYPE *self, unsigned count, \ 411 TYPE *tail) \ 412 { \ 413 const unsigned to_copy = MIN(count, self->len); \ 414 \ 415 if (tail != self) { \ 416 tail->resize(tail, to_copy); \ 417 memcpy(tail->_, self->_ + (self->len - to_copy), \ 418 sizeof(CONTENT_TYPE) * to_copy); \ 419 tail->len = to_copy; \ 420 } else { \ 421 memmove(tail->_, self->_ + (self->len - to_copy), \ 422 sizeof(CONTENT_TYPE) * to_copy); \ 423 tail->len = to_copy; \ 424 } \ 425 } \ 426 \ 427 static void \ 428 TYPE##_de_head(const TYPE *self, unsigned count, \ 429 TYPE *tail) \ 430 { \ 431 unsigned to_copy; \ 432 count = MIN(count, self->len); \ 433 to_copy = self->len - count; \ 434 \ 435 if (tail != self) { \ 436 tail->resize(tail, to_copy); \ 437 memcpy(tail->_, self->_ + count, \ 438 sizeof(CONTENT_TYPE) * to_copy); \ 439 tail->len = to_copy; \ 440 } else { \ 441 memmove(tail->_, self->_ + count, \ 442 sizeof(CONTENT_TYPE) * to_copy); \ 443 tail->len = to_copy; \ 444 } \ 445 } \ 446 \ 447 static void \ 448 TYPE##_de_tail(const TYPE *self, unsigned count, \ 449 TYPE *head) \ 450 { \ 451 unsigned to_copy; \ 452 count = MIN(count, self->len); \ 453 to_copy = self->len - count; \ 454 \ 455 if (head != self) { \ 456 head->resize(head, to_copy); \ 457 memcpy(head->_, self->_, \ 458 sizeof(CONTENT_TYPE) * to_copy); \ 459 head->len = to_copy; \ 460 } else { \ 461 head->len = to_copy; \ 462 } \ 463 } \ 464 \ 465 static void \ 466 TYPE##_split(const TYPE *self, unsigned count, \ 467 TYPE *head, TYPE *tail) \ 468 { \ 469 /*ensure we don't try to move too many items*/ \ 470 const unsigned to_head = MIN(count, self->len); \ 471 const unsigned to_tail = self->len - to_head; \ 472 \ 473 if ((head == self) && (tail == self)) { \ 474 /*do nothing*/ \ 475 return; \ 476 } else if (head == tail) { \ 477 /*copy all data to head*/ \ 478 self->copy(self, head); \ 479 } else if ((head != self) && (tail == self)) { \ 480 /*move "count" values to head and shift the rest down*/ \ 481 head->resize(head, to_head); \ 482 memcpy(head->_, self->_, sizeof(CONTENT_TYPE) * to_head); \ 483 head->len = to_head; \ 484 \ 485 memmove(tail->_, self->_ + to_head, \ 486 sizeof(CONTENT_TYPE) * to_tail); \ 487 tail->len = to_tail; \ 488 } else if ((head == self) && (tail != self)) { \ 489 /*move "count" values from our end to tail and reduce our size*/ \ 490 tail->resize(tail, to_tail); \ 491 memcpy(tail->_, self->_ + to_head, \ 492 sizeof(CONTENT_TYPE) * to_tail); \ 493 tail->len = to_tail; \ 494 \ 495 head->len = to_head; \ 496 } else { \ 497 /*copy "count" values to "head" and the remainder to "tail"*/ \ 498 head->resize(head, to_head); \ 499 memcpy(head->_, self->_, \ 500 sizeof(CONTENT_TYPE) * to_head); \ 501 head->len = to_head; \ 502 \ 503 tail->resize(tail, to_tail); \ 504 memcpy(tail->_, self->_ + to_head, \ 505 sizeof(CONTENT_TYPE) * to_tail); \ 506 tail->len = to_tail; \ 507 } \ 508 } \ 509 \ 510 static void \ 511 TYPE##_concat(const struct TYPE##_s *self, \ 512 const struct TYPE##_s *tail, \ 513 struct TYPE##_s *combined) \ 514 { \ 515 if (self == combined) { \ 516 /*extend array with values from tail*/ \ 517 combined->resize_for(combined, tail->len); \ 518 memcpy(combined->_ + combined->len, \ 519 tail->_, \ 520 sizeof(CONTENT_TYPE) * tail->len); \ 521 combined->len += tail->len; \ 522 } else { \ 523 /*concatenate array and tail to combined*/ \ 524 combined->reset_for(combined, self->len + tail->len); \ 525 memcpy(combined->_, \ 526 self->_, \ 527 sizeof(CONTENT_TYPE) * self->len); \ 528 memcpy(combined->_ + self->len, \ 529 tail->_, \ 530 sizeof(CONTENT_TYPE) * tail->len); \ 531 combined->len = self->len + tail->len; \ 532 } \ 533 } \ 534 \ 535 static void \ 536 TYPE##_reverse(TYPE *self) \ 537 { \ 538 unsigned i; \ 539 unsigned j; \ 540 CONTENT_TYPE *data = self->_; \ 541 \ 542 if (self->len > 0) { \ 543 for (i = 0, j = self->len - 1; i < j; i++, j--) { \ 544 const CONTENT_TYPE x = data[i]; \ 545 data[i] = data[j]; \ 546 data[j] = x; \ 547 } \ 548 } \ 549 } \ 550 \ 551 static int \ 552 TYPE##_cmp(const CONTENT_TYPE *x, const CONTENT_TYPE *y) \ 553 { \ 554 return *x - *y; \ 555 } \ 556 \ 557 static void \ 558 TYPE##_sort(TYPE *self) \ 559 { \ 560 qsort(self->_, (size_t)(self->len), \ 561 sizeof(CONTENT_TYPE), (qsort_cmp)TYPE##_cmp); \ 562 } \ 563 \ 564 static void \ 565 TYPE##_print(const TYPE *self, FILE *output) \ 566 { \ 567 unsigned i; \ 568 \ 569 putc('[', output); \ 570 if (self->len == 1) { \ 571 fprintf(output, FORMAT_STRING, self->_[0]); \ 572 } else if (self->len > 1) { \ 573 for (i = 0; i < self->len - 1; i++) \ 574 fprintf(output, FORMAT_STRING ", ", self->_[i]); \ 575 fprintf(output, FORMAT_STRING, self->_[i]); \ 576 } \ 577 putc(']', output); \ 578 } \ 579 \ 580 static void \ 581 LINK_TYPE##_del(LINK_TYPE *self); \ 582 \ 583 static void \ 584 LINK_TYPE##_reset(LINK_TYPE *self); \ 585 \ 586 static int \ 587 LINK_TYPE##_equals(const LINK_TYPE *self, \ 588 const LINK_TYPE *compare); \ 589 \ 590 static CONTENT_TYPE \ 591 LINK_TYPE##_min(const LINK_TYPE *self); \ 592 \ 593 static CONTENT_TYPE \ 594 LINK_TYPE##_max(const LINK_TYPE *self); \ 595 \ 596 static CONTENT_TYPE \ 597 LINK_TYPE##_sum(const LINK_TYPE *self); \ 598 \ 599 static void \ 600 LINK_TYPE##_copy(const LINK_TYPE *self, \ 601 struct TYPE##_s *copy); \ 602 \ 603 static void \ 604 LINK_TYPE##_link(const LINK_TYPE *self, \ 605 LINK_TYPE *link); \ 606 \ 607 static void \ 608 LINK_TYPE##_swap(LINK_TYPE *self, \ 609 LINK_TYPE *swap); \ 610 \ 611 static void \ 612 LINK_TYPE##_head(const LINK_TYPE *self, unsigned count, \ 613 LINK_TYPE *head); \ 614 \ 615 static void \ 616 LINK_TYPE##_tail(const LINK_TYPE *self, unsigned count, \ 617 LINK_TYPE *tail); \ 618 \ 619 static void \ 620 LINK_TYPE##_de_head(const LINK_TYPE *self, unsigned count, \ 621 LINK_TYPE *tail); \ 622 \ 623 static void \ 624 LINK_TYPE##_de_tail(const LINK_TYPE *self, unsigned count, \ 625 LINK_TYPE *head); \ 626 \ 627 static void \ 628 LINK_TYPE##_split(const LINK_TYPE *self, unsigned count, \ 629 LINK_TYPE *head, LINK_TYPE *tail); \ 630 \ 631 static void \ 632 LINK_TYPE##_print(const LINK_TYPE *self, FILE* output); \ 633 \ 634 LINK_TYPE* \ 635 LINK_TYPE##_new(void) \ 636 { \ 637 struct LINK_TYPE##_s* array = \ 638 malloc(sizeof(struct LINK_TYPE##_s)); \ 639 array->_ = NULL; \ 640 array->len = 0; \ 641 \ 642 array->del = LINK_TYPE##_del; \ 643 array->reset = LINK_TYPE##_reset; \ 644 array->equals = LINK_TYPE##_equals; \ 645 array->min = LINK_TYPE##_min; \ 646 array->max = LINK_TYPE##_max; \ 647 array->sum = LINK_TYPE##_sum; \ 648 array->copy = LINK_TYPE##_copy; \ 649 array->link = LINK_TYPE##_link; \ 650 array->swap = LINK_TYPE##_swap; \ 651 array->head = LINK_TYPE##_head; \ 652 array->tail = LINK_TYPE##_tail; \ 653 array->de_head = LINK_TYPE##_de_head; \ 654 array->de_tail = LINK_TYPE##_de_tail; \ 655 array->split = LINK_TYPE##_split; \ 656 array->print = LINK_TYPE##_print; \ 657 \ 658 return array; \ 659 } \ 660 \ 661 static void \ 662 LINK_TYPE##_del(LINK_TYPE *self) \ 663 { \ 664 free(self); \ 665 } \ 666 \ 667 static void \ 668 LINK_TYPE##_reset(LINK_TYPE *self) \ 669 { \ 670 self->len = 0; \ 671 } \ 672 \ 673 static int \ 674 LINK_TYPE##_equals(const LINK_TYPE *self, \ 675 const LINK_TYPE *compare) \ 676 { \ 677 assert(self->_); \ 678 assert(compare->_); \ 679 if (self->len == compare->len) { \ 680 return (memcmp(self->_, compare->_, \ 681 sizeof(CONTENT_TYPE) * self->len) == 0); \ 682 } else { \ 683 return 0; \ 684 } \ 685 } \ 686 \ 687 static CONTENT_TYPE \ 688 LINK_TYPE##_min(const LINK_TYPE *self) \ 689 { \ 690 CONTENT_TYPE min = CONTENT_TYPE_MAX; \ 691 unsigned i; \ 692 \ 693 assert(self->_); \ 694 for (i = 0; i < self->len; i++) \ 695 if (self->_[i] < min) \ 696 min = self->_[i]; \ 697 \ 698 return min; \ 699 } \ 700 \ 701 static CONTENT_TYPE \ 702 LINK_TYPE##_max(const LINK_TYPE *self) \ 703 { \ 704 CONTENT_TYPE max = CONTENT_TYPE_MIN; \ 705 unsigned i; \ 706 \ 707 assert(self->_); \ 708 for (i = 0; i < self->len; i++) \ 709 if (self->_[i] > max) \ 710 max = self->_[i]; \ 711 \ 712 return max; \ 713 } \ 714 \ 715 static CONTENT_TYPE \ 716 LINK_TYPE##_sum(const LINK_TYPE *self) \ 717 { \ 718 CONTENT_TYPE accumulator = CONTENT_TYPE_ACCUMULATOR; \ 719 const CONTENT_TYPE *data = self->_; \ 720 unsigned size = self->len; \ 721 unsigned i; \ 722 \ 723 assert(self->_); \ 724 for (i = 0; i < size; i++) \ 725 accumulator += data[i]; \ 726 \ 727 return accumulator; \ 728 } \ 729 \ 730 static void \ 731 LINK_TYPE##_copy(const LINK_TYPE *self, \ 732 TYPE *copy) \ 733 { \ 734 copy->resize(copy, self->len); \ 735 memcpy(copy->_, self->_, self->len * sizeof(CONTENT_TYPE)); \ 736 copy->len = self->len; \ 737 } \ 738 \ 739 static void \ 740 LINK_TYPE##_link(const LINK_TYPE *self, \ 741 LINK_TYPE *link) \ 742 { \ 743 link->_ = self->_; \ 744 link->len = self->len; \ 745 } \ 746 \ 747 static void \ 748 LINK_TYPE##_swap(LINK_TYPE *self, \ 749 LINK_TYPE *swap) \ 750 { \ 751 LINK_TYPE temp; \ 752 temp._ = self->_; \ 753 temp.len = self->len; \ 754 self->_ = swap->_; \ 755 self->len = swap->len; \ 756 swap->_ = temp._; \ 757 swap->len = temp.len; \ 758 } \ 759 \ 760 static void \ 761 LINK_TYPE##_head(const LINK_TYPE *self, unsigned count, \ 762 LINK_TYPE *head) \ 763 { \ 764 const unsigned to_copy = MIN(count, self->len); \ 765 assert(self->_); \ 766 head->_ = self->_; \ 767 head->len = to_copy; \ 768 } \ 769 \ 770 static void \ 771 LINK_TYPE##_tail(const LINK_TYPE *self, unsigned count, \ 772 LINK_TYPE *tail) \ 773 { \ 774 const unsigned to_copy = MIN(count, self->len); \ 775 assert(self->_); \ 776 tail->_ = self->_ + (self->len - to_copy); \ 777 tail->len = to_copy; \ 778 } \ 779 \ 780 static void \ 781 LINK_TYPE##_de_head(const LINK_TYPE *self, unsigned count, \ 782 LINK_TYPE *tail) \ 783 { \ 784 unsigned to_copy; \ 785 assert(self->_); \ 786 count = MIN(count, self->len); \ 787 to_copy = self->len - count; \ 788 \ 789 tail->_ = self->_ + count; \ 790 tail->len = to_copy; \ 791 } \ 792 \ 793 static void \ 794 LINK_TYPE##_de_tail(const LINK_TYPE *self, unsigned count, \ 795 LINK_TYPE *head) \ 796 { \ 797 head->_ = self->_; \ 798 head->len = self->len - MIN(count, self->len); \ 799 } \ 800 \ 801 static void \ 802 LINK_TYPE##_split(const LINK_TYPE *self, unsigned count, \ 803 LINK_TYPE *head, LINK_TYPE *tail) \ 804 { \ 805 /*ensure we don't try to move too many items*/ \ 806 const unsigned to_head = MIN(count, self->len); \ 807 const unsigned to_tail = self->len - to_head; \ 808 assert(self->_); \ 809 \ 810 if ((head == self) && (tail == self)) { \ 811 /*do nothing*/ \ 812 return; \ 813 } else if (head == tail) { \ 814 /*copy all data to head*/ \ 815 head->_ = self->_; \ 816 head->len = self->len; \ 817 } else { \ 818 head->_ = self->_; \ 819 head->len = to_head; \ 820 tail->_ = self->_ + to_head; \ 821 tail->len = to_tail; \ 822 } \ 823 } \ 824 \ 825 static void \ 826 LINK_TYPE##_print(const LINK_TYPE *self, FILE *output) \ 827 { \ 828 unsigned i; \ 829 \ 830 putc('[', output); \ 831 if (self->len == 1) { \ 832 fprintf(output, FORMAT_STRING, self->_[0]); \ 833 } else if (self->len > 1) { \ 834 for (i = 0; i < self->len - 1; i++) \ 835 fprintf(output, FORMAT_STRING ", ", self->_[i]); \ 836 fprintf(output, FORMAT_STRING, self->_[i]); \ 837 } \ 838 putc(']', output); \ 839 } 840 841 ARRAY_FUNC_DEFINITION(a_int, int, l_int, INT_MIN, INT_MAX, 0, "%d") 842 ARRAY_FUNC_DEFINITION(a_double, double, l_double, DBL_MIN, DBL_MAX, 0.0, "%f") 843 ARRAY_FUNC_DEFINITION(a_unsigned, unsigned, l_unsigned, 0, UINT_MAX, 0, "%u") 844 845 846 #define ARRAY_A_FUNC_DEFINITION(TYPE, ARRAY_TYPE, COPY_METH) \ 847 \ 848 static void \ 849 TYPE##_del(TYPE *self); \ 850 \ 851 static void \ 852 TYPE##_resize(TYPE *self, unsigned minimum); \ 853 \ 854 static void \ 855 TYPE##_reset(TYPE *self); \ 856 \ 857 static ARRAY_TYPE* \ 858 TYPE##_append(TYPE *self); \ 859 \ 860 static void \ 861 TYPE##_extend(TYPE *self, \ 862 const TYPE *to_add); \ 863 \ 864 static int \ 865 TYPE##_equals(const TYPE *self, \ 866 const TYPE *compare); \ 867 \ 868 static void \ 869 TYPE##_copy(const TYPE *self, TYPE *copy); \ 870 \ 871 static void \ 872 TYPE##_swap(TYPE *self, TYPE *swap); \ 873 \ 874 static void \ 875 TYPE##_split(const TYPE *self, unsigned count, \ 876 TYPE *head, TYPE *tail); \ 877 \ 878 static void \ 879 TYPE##_cross_split(const TYPE *self, unsigned count, \ 880 TYPE *head, TYPE *tail); \ 881 \ 882 static void \ 883 TYPE##_reverse(TYPE *self); \ 884 \ 885 static void \ 886 TYPE##_print(const TYPE *self, FILE* output); \ 887 \ 888 struct TYPE##_s* TYPE##_new(void) \ 889 { \ 890 struct TYPE##_s* a = malloc(sizeof(struct TYPE##_s)); \ 891 unsigned i; \ 892 \ 893 a->_ = malloc(sizeof(struct ARRAY_TYPE##_s*) * 1); \ 894 a->len = 0; \ 895 a->total_size = 1; \ 896 \ 897 for (i = 0; i < 1; i++) { \ 898 a->_[i] = ARRAY_TYPE##_new(); \ 899 } \ 900 \ 901 a->del = TYPE##_del; \ 902 a->resize = TYPE##_resize; \ 903 a->reset = TYPE##_reset; \ 904 a->append = TYPE##_append; \ 905 a->extend = TYPE##_extend; \ 906 a->equals = TYPE##_equals; \ 907 a->copy = TYPE##_copy; \ 908 a->swap = TYPE##_swap; \ 909 a->split = TYPE##_split; \ 910 a->cross_split = TYPE##_cross_split; \ 911 a->reverse = TYPE##_reverse; \ 912 a->print = TYPE##_print; \ 913 \ 914 return a; \ 915 } \ 916 \ 917 static void \ 918 TYPE##_del(TYPE *self) \ 919 { \ 920 unsigned i; \ 921 \ 922 for (i = 0; i < self->total_size; i++) \ 923 self->_[i]->del(self->_[i]); \ 924 \ 925 free(self->_); \ 926 free(self); \ 927 } \ 928 \ 929 static void \ 930 TYPE##_resize(TYPE *self, unsigned minimum) \ 931 { \ 932 if (minimum > self->total_size) { \ 933 self->_ = realloc(self->_, \ 934 sizeof(ARRAY_TYPE*) * minimum); \ 935 while (self->total_size < minimum) { \ 936 self->_[self->total_size++] = ARRAY_TYPE##_new(); \ 937 } \ 938 } \ 939 } \ 940 \ 941 static void \ 942 TYPE##_reset(TYPE *self) \ 943 { \ 944 unsigned i; \ 945 for (i = 0; i < self->total_size; i++) \ 946 self->_[i]->reset(self->_[i]); \ 947 self->len = 0; \ 948 } \ 949 \ 950 static ARRAY_TYPE* \ 951 TYPE##_append(TYPE *self) \ 952 { \ 953 if (self->len == self->total_size) \ 954 self->resize(self, self->total_size * 2); \ 955 \ 956 return self->_[self->len++]; \ 957 } \ 958 \ 959 static void \ 960 TYPE##_extend(TYPE *self, \ 961 const TYPE *to_add) \ 962 { \ 963 unsigned i; \ 964 const unsigned len = to_add->len; \ 965 for (i = 0; i < len; i++) { \ 966 to_add->_[i]->COPY_METH(to_add->_[i], \ 967 self->append(self)); \ 968 } \ 969 } \ 970 \ 971 static int \ 972 TYPE##_equals(const TYPE *self, \ 973 const TYPE *compare) \ 974 { \ 975 unsigned i; \ 976 \ 977 if (self->len == compare->len) { \ 978 for (i = 0; i < self->len; i++) \ 979 if (!self->_[i]->equals(self->_[i], compare->_[i])) \ 980 return 0; \ 981 \ 982 return 1; \ 983 } else \ 984 return 0; \ 985 } \ 986 \ 987 static void \ 988 TYPE##_copy(const TYPE *self, TYPE *copy) \ 989 { \ 990 unsigned i; \ 991 \ 992 if (self != copy) { \ 993 copy->reset(copy); \ 994 for (i = 0; i < self->len; i++) \ 995 self->_[i]->COPY_METH(self->_[i], \ 996 copy->append(copy)); \ 997 } \ 998 } \ 999 \ 1000 static void \ 1001 TYPE##_swap(TYPE *self, TYPE *swap) \ 1002 { \ 1003 TYPE temp; \ 1004 temp._ = self->_; \ 1005 temp.len = self->len; \ 1006 temp.total_size = self->total_size; \ 1007 self->_ = swap->_; \ 1008 self->len = swap->len; \ 1009 self->total_size = swap->total_size; \ 1010 swap->_ = temp._; \ 1011 swap->len = temp.len; \ 1012 swap->total_size = temp.total_size; \ 1013 } \ 1014 \ 1015 static void \ 1016 TYPE##_split(const TYPE *self, unsigned count, \ 1017 TYPE *head, TYPE *tail) \ 1018 { \ 1019 /*ensure we don't try to move too many items*/ \ 1020 unsigned to_head = MIN(count, self->len); \ 1021 unsigned i; \ 1022 \ 1023 if ((head == self) && (tail == self)) { \ 1024 /*do nothing*/ \ 1025 return; \ 1026 } else if ((head != self) && (tail == self)) { \ 1027 TYPE *temp; \ 1028 /*move "count" values to head and shift the rest down*/ \ 1029 \ 1030 head->reset(head); \ 1031 for (i = 0; i < to_head; i++) \ 1032 self->_[i]->swap(self->_[i], head->append(head)); \ 1033 \ 1034 temp = TYPE##_new(); \ 1035 for (; i < self->len; i++) \ 1036 self->_[i]->swap(self->_[i], temp->append(temp)); \ 1037 \ 1038 temp->swap(temp, tail); \ 1039 temp->del(temp); \ 1040 } else if ((head == self) && (tail != self)) { \ 1041 /*move "count" values from our end to tail and reduce our size*/ \ 1042 \ 1043 tail->reset(tail); \ 1044 for (i = to_head; i < self->len; i++) { \ 1045 self->_[i]->swap(self->_[i], tail->append(tail)); \ 1046 self->_[i]->reset(self->_[i]); \ 1047 } \ 1048 head->len = to_head; \ 1049 } else { \ 1050 /*copy "count" values to "head" and the remainder to "tail"*/ \ 1051 \ 1052 head->reset(head); \ 1053 tail->reset(tail); \ 1054 for (i = 0; i < to_head; i++) \ 1055 self->_[i]->COPY_METH(self->_[i], head->append(head)); \ 1056 \ 1057 for (; i < self->len; i++) \ 1058 self->_[i]->COPY_METH(self->_[i], tail->append(tail)); \ 1059 } \ 1060 } \ 1061 \ 1062 static void \ 1063 TYPE##_cross_split(const TYPE *self, unsigned count, \ 1064 TYPE *head, TYPE *tail) \ 1065 { \ 1066 unsigned i; \ 1067 \ 1068 if ((head == self) && (tail == self)) { \ 1069 /*do nothing*/ \ 1070 } else if (head == tail) { \ 1071 self->copy(self, head); \ 1072 } else if ((head != self) && (tail == self)) { \ 1073 head->reset(head); \ 1074 for (i = 0; i < self->len; i++) { \ 1075 self->_[i]->split(self->_[i], \ 1076 count, \ 1077 head->append(head), \ 1078 tail->_[i]); \ 1079 } \ 1080 } else if ((head == self) && (tail != self)) { \ 1081 tail->reset(tail); \ 1082 for (i = 0; i < self->len; i++) { \ 1083 self->_[i]->split(self->_[i], \ 1084 count, \ 1085 head->_[i], \ 1086 tail->append(tail)); \ 1087 } \ 1088 } else { \ 1089 head->reset(head); \ 1090 tail->reset(tail); \ 1091 for (i = 0; i < self->len; i++) { \ 1092 self->_[i]->split(self->_[i], \ 1093 count, \ 1094 head->append(head), \ 1095 tail->append(tail)); \ 1096 } \ 1097 } \ 1098 } \ 1099 \ 1100 static void \ 1101 TYPE##_reverse(TYPE *self) \ 1102 { \ 1103 unsigned i; \ 1104 unsigned j; \ 1105 ARRAY_TYPE **data = self->_; \ 1106 \ 1107 if (self->len > 0) { \ 1108 for (i = 0, j = self->len - 1; i < j; i++, j--) { \ 1109 ARRAY_TYPE *x = data[i]; \ 1110 data[i] = data[j]; \ 1111 data[j] = x; \ 1112 } \ 1113 } \ 1114 } \ 1115 \ 1116 static void \ 1117 TYPE##_print(const TYPE *self, FILE *output) \ 1118 { \ 1119 unsigned i; \ 1120 \ 1121 putc('[', output); \ 1122 if (self->len == 1) { \ 1123 self->_[0]->print(self->_[0], output); \ 1124 } else if (self->len > 1) { \ 1125 for (i = 0; i < self->len - 1; i++) { \ 1126 self->_[i]->print(self->_[i], output); \ 1127 fprintf(output, ", "); \ 1128 } \ 1129 self->_[i]->print(self->_[i], output); \ 1130 } \ 1131 putc(']', output); \ 1132 } 1133 1134 ARRAY_A_FUNC_DEFINITION(aa_int, a_int, copy) 1135 ARRAY_A_FUNC_DEFINITION(aa_double, a_double, copy) 1136 ARRAY_A_FUNC_DEFINITION(al_int, l_int, link) 1137 ARRAY_A_FUNC_DEFINITION(al_double, l_double, link) 1138 1139 #define ARRAY_AA_FUNC_DEFINITION(TYPE, ARRAY_TYPE, COPY_METH) \ 1140 \ 1141 static void \ 1142 TYPE##_del(TYPE *self); \ 1143 \ 1144 static void \ 1145 TYPE##_resize(TYPE *self, unsigned minimum); \ 1146 \ 1147 static void \ 1148 TYPE##_reset(TYPE *self); \ 1149 \ 1150 static ARRAY_TYPE* \ 1151 TYPE##_append(TYPE *self); \ 1152 \ 1153 static void \ 1154 TYPE##_extend(TYPE *self, \ 1155 const TYPE *to_add); \ 1156 \ 1157 static int \ 1158 TYPE##_equals(const TYPE *self, \ 1159 const TYPE *compare); \ 1160 \ 1161 static void \ 1162 TYPE##_copy(const TYPE *self, \ 1163 TYPE *copy); \ 1164 \ 1165 static void \ 1166 TYPE##_swap(TYPE *self, TYPE *swap); \ 1167 \ 1168 static void \ 1169 TYPE##_split(const TYPE *self, unsigned count, \ 1170 TYPE *head, TYPE *tail); \ 1171 \ 1172 static void \ 1173 TYPE##_reverse(TYPE *self); \ 1174 \ 1175 static void \ 1176 TYPE##_print(const TYPE *self, FILE* output); \ 1177 \ 1178 struct TYPE##_s* \ 1179 TYPE##_new(void) \ 1180 { \ 1181 struct TYPE##_s* a = malloc(sizeof(struct TYPE##_s)); \ 1182 unsigned i; \ 1183 \ 1184 a->_ = malloc(sizeof(struct ARRAY_TYPE##_s*) * 1); \ 1185 a->len = 0; \ 1186 a->total_size = 1; \ 1187 \ 1188 for (i = 0; i < 1; i++) { \ 1189 a->_[i] = ARRAY_TYPE##_new(); \ 1190 } \ 1191 \ 1192 a->del = TYPE##_del; \ 1193 a->resize = TYPE##_resize; \ 1194 a->reset = TYPE##_reset; \ 1195 a->append = TYPE##_append; \ 1196 a->extend = TYPE##_extend; \ 1197 a->equals = TYPE##_equals; \ 1198 a->copy = TYPE##_copy; \ 1199 a->swap = TYPE##_swap; \ 1200 a->split = TYPE##_split; \ 1201 a->reverse = TYPE##_reverse; \ 1202 a->print = TYPE##_print; \ 1203 \ 1204 return a; \ 1205 } \ 1206 \ 1207 static void \ 1208 TYPE##_del(TYPE *self) \ 1209 { \ 1210 unsigned i; \ 1211 \ 1212 for (i = 0; i < self->total_size; i++) \ 1213 self->_[i]->del(self->_[i]); \ 1214 \ 1215 free(self->_); \ 1216 free(self); \ 1217 } \ 1218 \ 1219 static void \ 1220 TYPE##_resize(TYPE *self, unsigned minimum) \ 1221 { \ 1222 if (minimum > self->total_size) { \ 1223 self->_ = realloc(self->_, \ 1224 sizeof(ARRAY_TYPE*) * minimum); \ 1225 while (self->total_size < minimum) { \ 1226 self->_[self->total_size++] = ARRAY_TYPE##_new(); \ 1227 } \ 1228 } \ 1229 } \ 1230 \ 1231 static void \ 1232 TYPE##_reset(TYPE *self) \ 1233 { \ 1234 unsigned i; \ 1235 for (i = 0; i < self->total_size; i++) \ 1236 self->_[i]->reset(self->_[i]); \ 1237 self->len = 0; \ 1238 } \ 1239 \ 1240 static ARRAY_TYPE* \ 1241 TYPE##_append(TYPE *self) \ 1242 { \ 1243 if (self->len == self->total_size) \ 1244 self->resize(self, self->total_size * 2); \ 1245 \ 1246 return self->_[self->len++]; \ 1247 } \ 1248 \ 1249 static void \ 1250 TYPE##_extend(TYPE *self, const TYPE *to_add) \ 1251 { \ 1252 unsigned i; \ 1253 const unsigned len = to_add->len; \ 1254 for (i = 0; i < len; i++) { \ 1255 to_add->_[i]->COPY_METH(to_add->_[i], self->append(self)); \ 1256 } \ 1257 } \ 1258 \ 1259 static int \ 1260 TYPE##_equals(const TYPE *self, const TYPE *compare) \ 1261 { \ 1262 unsigned i; \ 1263 \ 1264 if (self->len == compare->len) { \ 1265 for (i = 0; i < self->len; i++) \ 1266 if (!self->_[i]->equals(self->_[i], compare->_[i])) \ 1267 return 0; \ 1268 \ 1269 return 1; \ 1270 } else \ 1271 return 0; \ 1272 } \ 1273 \ 1274 static void \ 1275 TYPE##_copy(const TYPE *self, \ 1276 TYPE *copy) \ 1277 { \ 1278 unsigned i; \ 1279 \ 1280 if (self != copy) { \ 1281 copy->reset(copy); \ 1282 for (i = 0; i < self->len; i++) \ 1283 self->_[i]->COPY_METH(self->_[i], \ 1284 copy->append(copy)); \ 1285 } \ 1286 } \ 1287 \ 1288 static void \ 1289 TYPE##_swap(TYPE *self, TYPE *swap) \ 1290 { \ 1291 TYPE temp; \ 1292 temp._ = self->_; \ 1293 temp.len = self->len; \ 1294 temp.total_size = self->total_size; \ 1295 self->_ = swap->_; \ 1296 self->len = swap->len; \ 1297 self->total_size = swap->total_size; \ 1298 swap->_ = temp._; \ 1299 swap->len = temp.len; \ 1300 swap->total_size = temp.total_size; \ 1301 } \ 1302 \ 1303 static void \ 1304 TYPE##_split(const TYPE *self, unsigned count, \ 1305 TYPE *head, TYPE *tail) \ 1306 { \ 1307 /*ensure we don't try to move too many items*/ \ 1308 unsigned to_head = MIN(count, self->len); \ 1309 unsigned i; \ 1310 \ 1311 if ((head == self) && (tail == self)) { \ 1312 /*do nothing*/ \ 1313 return; \ 1314 } else if ((head != self) && (tail == self)) { \ 1315 TYPE *temp; \ 1316 /*move "count" values to head and shift the rest down*/ \ 1317 \ 1318 head->reset(head); \ 1319 for (i = 0; i < to_head; i++) \ 1320 self->_[i]->swap(self->_[i], head->append(head)); \ 1321 \ 1322 temp = TYPE##_new(); \ 1323 for (; i < self->len; i++) \ 1324 self->_[i]->swap(self->_[i], temp->append(temp)); \ 1325 \ 1326 temp->swap(temp, tail); \ 1327 temp->del(temp); \ 1328 } else if ((head == self) && (tail != self)) { \ 1329 /*move "count" values from our end to tail and reduce our size*/ \ 1330 \ 1331 tail->reset(tail); \ 1332 for (i = to_head; i < self->len; i++) { \ 1333 self->_[i]->swap(self->_[i], tail->append(tail)); \ 1334 self->_[i]->reset(self->_[i]); \ 1335 } \ 1336 head->len = to_head; \ 1337 } else { \ 1338 /*copy "count" values to "head" and the remainder to "tail"*/ \ 1339 \ 1340 head->reset(head); \ 1341 tail->reset(tail); \ 1342 for (i = 0; i < to_head; i++) \ 1343 self->_[i]->COPY_METH(self->_[i], head->append(head)); \ 1344 \ 1345 for (; i < self->len; i++) \ 1346 self->_[i]->COPY_METH(self->_[i], tail->append(tail)); \ 1347 } \ 1348 } \ 1349 \ 1350 static void \ 1351 TYPE##_reverse(TYPE *self) \ 1352 { \ 1353 unsigned i; \ 1354 unsigned j; \ 1355 ARRAY_TYPE **data = self->_; \ 1356 \ 1357 if (self->len > 0) { \ 1358 for (i = 0, j = self->len - 1; i < j; i++, j--) { \ 1359 ARRAY_TYPE *x = data[i]; \ 1360 data[i] = data[j]; \ 1361 data[j] = x; \ 1362 } \ 1363 } \ 1364 } \ 1365 \ 1366 static void \ 1367 TYPE##_print(const TYPE *self, FILE *output) \ 1368 { \ 1369 unsigned i; \ 1370 \ 1371 putc('[', output); \ 1372 if (self->len == 1) { \ 1373 self->_[0]->print(self->_[0], output); \ 1374 } else if (self->len > 1) { \ 1375 for (i = 0; i < self->len - 1; i++) { \ 1376 self->_[i]->print(self->_[i], output); \ 1377 fprintf(output, ", "); \ 1378 } \ 1379 self->_[i]->print(self->_[i], output); \ 1380 } \ 1381 putc(']', output); \ 1382 } 1383 1384 ARRAY_AA_FUNC_DEFINITION(aaa_int, aa_int, copy) 1385 ARRAY_AA_FUNC_DEFINITION(aaa_double, aa_double, copy) 1386 1387 1388 void* 1389 a_obj_dummy_copy(void* obj) 1390 { 1391 return obj; /*does nothing*/ 1392 } 1393 1394 void 1395 a_obj_dummy_free(void* obj) 1396 { 1397 return; /*does nothing*/ 1398 } 1399 1400 void 1401 a_obj_dummy_print(void* obj, FILE* output) 1402 { 1403 fprintf(output, "<OBJECT>"); 1404 } 1405 1406 static void 1407 a_obj_del(a_obj *self); 1408 1409 static void 1410 a_obj_resize(a_obj *self, unsigned minimum); 1411 1412 static void 1413 a_obj_resize_for(a_obj *self, unsigned additional_items); 1414 1415 static void 1416 a_obj_reset(a_obj *self); 1417 1418 static void 1419 a_obj_reset_for(a_obj *self, unsigned minimum); 1420 1421 static void 1422 a_obj_append(a_obj *self, void* value); 1423 1424 static void 1425 a_obj_vappend(a_obj *self, unsigned count, ...); 1426 1427 static void 1428 a_obj_mappend(a_obj *self, unsigned count, void* value); 1429 1430 static void 1431 a_obj_set(a_obj *self, unsigned index, void* value); 1432 1433 static void 1434 a_obj_vset(a_obj *self, unsigned count, ...); 1435 1436 static void 1437 a_obj_mset(a_obj *self, unsigned count, void* value); 1438 1439 static void 1440 a_obj_extend(a_obj *self, const a_obj *to_add); 1441 1442 static void 1443 a_obj_copy(const a_obj *self, a_obj *copy); 1444 1445 static void 1446 a_obj_swap(a_obj *self, a_obj *swap); 1447 1448 static void 1449 a_obj_head(const a_obj *self, unsigned count, 1450 a_obj *head); 1451 1452 static void 1453 a_obj_tail(const a_obj *self, unsigned count, 1454 a_obj *tail); 1455 1456 static void 1457 a_obj_de_head(const a_obj *self, unsigned count, 1458 a_obj *tail); 1459 1460 static void 1461 a_obj_de_tail(const a_obj *self, unsigned count, 1462 a_obj *head); 1463 1464 static void 1465 a_obj_split(const a_obj *self, unsigned count, 1466 a_obj *head, a_obj *tail); 1467 1468 static void 1469 a_obj_concat(const a_obj *self, 1470 const a_obj *tail, 1471 a_obj *combined); 1472 1473 static void 1474 a_obj_print(const a_obj *self, FILE* output); 1475 1476 struct a_obj_s* 1477 a_obj_new(void* (*copy)(void* obj), 1478 void (*free)(void* obj), 1479 void (*print)(void* obj, FILE* output)) 1480 { 1481 struct a_obj_s* a = malloc(sizeof(struct a_obj_s)); 1482 a->len = 0; 1483 a->total_size = 1; 1484 a->_ = malloc(sizeof(void*) * a->total_size); 1485 1486 if (copy != NULL) 1487 a->copy_obj = copy; 1488 else 1489 a->copy_obj = a_obj_dummy_copy; 1490 1491 if (free != NULL) 1492 a->free_obj = free; 1493 else 1494 a->free_obj = a_obj_dummy_free; 1495 1496 if (print != NULL) 1497 a->print_obj = print; 1498 else 1499 a->print_obj = a_obj_dummy_print; 1500 1501 a->del = a_obj_del; 1502 a->resize = a_obj_resize; 1503 a->resize_for = a_obj_resize_for; 1504 a->reset = a_obj_reset; 1505 a->reset_for = a_obj_reset_for; 1506 a->append = a_obj_append; 1507 a->vappend = a_obj_vappend; 1508 a->mappend = a_obj_mappend; 1509 a->set = a_obj_set; 1510 a->vset = a_obj_vset; 1511 a->mset = a_obj_mset; 1512 a->extend = a_obj_extend; 1513 a->copy = a_obj_copy; 1514 a->swap = a_obj_swap; 1515 a->head = a_obj_head; 1516 a->tail = a_obj_tail; 1517 a->de_head = a_obj_de_head; 1518 a->de_tail = a_obj_de_tail; 1519 a->split = a_obj_split; 1520 a->concat = a_obj_concat; 1521 a->concat = a_obj_concat; 1522 a->print = a_obj_print; 1523 1524 return a; 1525 } 1526 1527 static void 1528 a_obj_del(a_obj *self) 1529 { 1530 while (self->len) { 1531 self->free_obj(self->_[--self->len]); 1532 } 1533 free(self->_); 1534 free(self); 1535 } 1536 1537 static void 1538 a_obj_resize(a_obj *self, unsigned minimum) 1539 { 1540 if (minimum > self->total_size) { 1541 self->total_size = minimum; 1542 self->_ = realloc(self->_, sizeof(void*) * minimum); 1543 } 1544 } 1545 1546 static void 1547 a_obj_resize_for(a_obj *self, unsigned additional_items) 1548 { 1549 self->resize(self, self->len + additional_items); 1550 } 1551 1552 static void 1553 a_obj_reset(a_obj *self) 1554 { 1555 while (self->len) { 1556 self->free_obj(self->_[--self->len]); 1557 } 1558 } 1559 1560 static void 1561 a_obj_reset_for(a_obj *self, unsigned minimum) 1562 { 1563 self->reset(self); 1564 self->resize(self, minimum); 1565 } 1566 1567 static void 1568 a_obj_append(a_obj *self, void* value) 1569 { 1570 if (self->len == self->total_size) 1571 self->resize(self, self->total_size * 2); 1572 1573 self->_[self->len++] = self->copy_obj(value); 1574 } 1575 1576 static void 1577 a_obj_vappend(a_obj *self, unsigned count, ...) 1578 { 1579 void* i; 1580 va_list ap; 1581 1582 self->resize(self, self->len + count); 1583 va_start(ap, count); 1584 for (; count > 0; count--) { 1585 i = va_arg(ap, void*); 1586 self->_[self->len++] = self->copy_obj(i); 1587 } 1588 va_end(ap); 1589 } 1590 1591 static void 1592 a_obj_mappend(a_obj *self, unsigned count, void* value) 1593 { 1594 self->resize(self, self->len + count); 1595 for (; count > 0; count--) { 1596 self->_[self->len++] = self->copy_obj(value); 1597 } 1598 } 1599 1600 static void 1601 a_obj_set(a_obj *self, unsigned index, void* value) 1602 { 1603 assert(index < self->len); 1604 self->free_obj(self->_[index]); 1605 self->_[index] = self->copy_obj(value); 1606 } 1607 1608 static void 1609 a_obj_vset(a_obj *self, unsigned count, ...) 1610 { 1611 void* i; 1612 va_list ap; 1613 1614 self->reset_for(self, count); 1615 va_start(ap, count); 1616 for (; count > 0; count--) { 1617 i = va_arg(ap, void*); 1618 self->_[self->len++] = self->copy_obj(i); 1619 } 1620 va_end(ap); 1621 } 1622 1623 static void 1624 a_obj_mset(a_obj *self, unsigned count, void* value) 1625 { 1626 self->reset_for(self, count); 1627 for (; count > 0; count--) { 1628 self->_[self->len++] = self->copy_obj(value); 1629 } 1630 } 1631 1632 static void 1633 a_obj_extend(a_obj *self, const a_obj *to_add) 1634 { 1635 self->concat(self, to_add, self); 1636 } 1637 1638 static void 1639 a_obj_copy(const a_obj *self, a_obj *copy) 1640 { 1641 if (self != copy) { 1642 unsigned i; 1643 1644 copy->reset_for(copy, self->len); 1645 for (i = 0; i < self->len; i++) { 1646 copy->_[copy->len++] = self->copy_obj(self->_[i]); 1647 } 1648 } 1649 } 1650 1651 static void 1652 a_obj_swap(a_obj *self, a_obj *swap) 1653 { 1654 a_obj temp; 1655 temp._ = self->_; 1656 temp.len = self->len; 1657 temp.total_size = self->total_size; 1658 self->_ = swap->_; 1659 self->len = swap->len; 1660 self->total_size = swap->total_size; 1661 swap->_ = temp._; 1662 swap->len = temp.len; 1663 swap->total_size = temp.total_size; 1664 } 1665 1666 static void 1667 a_obj_head(const a_obj *self, unsigned count, 1668 a_obj *head) 1669 { 1670 const unsigned to_copy = MIN(count, self->len); 1671 1672 if (head != self) { 1673 unsigned i; 1674 head->reset_for(head, to_copy); 1675 for (i = 0; i < to_copy; i++) { 1676 head->_[head->len++] = self->copy_obj(self->_[i]); 1677 } 1678 } else { 1679 while (head->len > to_copy) { 1680 self->free_obj(head->_[--head->len]); 1681 } 1682 } 1683 } 1684 1685 static void 1686 a_obj_tail(const a_obj *self, unsigned count, 1687 a_obj *tail) 1688 { 1689 const unsigned to_copy = MIN(count, self->len); 1690 1691 if (tail != self) { 1692 unsigned i; 1693 1694 tail->reset_for(tail, to_copy); 1695 for (i = self->len - to_copy; i < self->len; i++) { 1696 tail->_[tail->len++] = self->copy_obj(self->_[i]); 1697 } 1698 } else { 1699 a_obj* temp = a_obj_new(self->copy_obj, 1700 self->free_obj, 1701 self->print_obj); 1702 unsigned i; 1703 temp->resize(temp, to_copy); 1704 for (i = self->len - to_copy; i < self->len; i++) { 1705 temp->_[temp->len++] = self->copy_obj(self->_[i]); 1706 } 1707 temp->swap(temp, tail); 1708 temp->del(temp); 1709 } 1710 } 1711 1712 static void 1713 a_obj_de_head(const a_obj *self, unsigned count, 1714 a_obj *tail) 1715 { 1716 self->tail(self, self->len - MIN(count, self->len), tail); 1717 } 1718 1719 static void 1720 a_obj_de_tail(const a_obj *self, unsigned count, 1721 a_obj *head) 1722 { 1723 self->head(self, self->len - MIN(count, self->len), head); 1724 } 1725 1726 static void 1727 a_obj_split(const a_obj *self, unsigned count, 1728 a_obj *head, a_obj *tail) 1729 { 1730 const unsigned to_head = MIN(count, self->len); 1731 const unsigned to_tail = self->len - to_head; 1732 1733 if ((head == self) && (tail == self)) { 1734 /*do nothing*/ 1735 return; 1736 } else if (head == tail) { 1737 /*copy all data to head*/ 1738 self->copy(self, head); 1739 } else if ((head == self) && (tail != self)) { 1740 self->tail(self, to_tail, tail); 1741 self->head(self, to_head, head); 1742 } else { 1743 self->head(self, to_head, head); 1744 self->tail(self, to_tail, tail); 1745 } 1746 } 1747 1748 static void 1749 a_obj_concat(const a_obj *self, 1750 const a_obj *tail, 1751 a_obj *combined) 1752 { 1753 unsigned i; 1754 1755 if (self == combined) { 1756 /*extend self with values from tail*/ 1757 1758 combined->resize_for(combined, tail->len); 1759 1760 for (i = 0; i < tail->len; i++) { 1761 combined->_[combined->len++] = combined->copy_obj(tail->_[i]); 1762 } 1763 } else { 1764 /*concatenate self and tail to combined*/ 1765 1766 combined->reset_for(combined, self->len + tail->len); 1767 1768 for (i = 0; i < self->len; i++) { 1769 combined->_[combined->len++] = combined->copy_obj(self->_[i]); 1770 } 1771 for (i = 0; i < tail->len; i++) { 1772 combined->_[combined->len++] = combined->copy_obj(tail->_[i]); 1773 } 1774 } 1775 } 1776 1777 static void 1778 a_obj_print(const a_obj *self, FILE* output) 1779 { 1780 unsigned i; 1781 putc('[', output); 1782 if (self->len == 1) { 1783 self->print_obj(self->_[0], output); 1784 } else if (self->len > 1) { 1785 for (i = 0; i < self->len - 1; i++) { 1786 self->print_obj(self->_[i], output); 1787 fprintf(output, ", "); 1788 } 1789 self->print_obj(self->_[i], output); 1790 } 1791 putc(']', output); 1792 } 1793 1794 /***************************************************************** 1795 BEGIN UNIT TESTS 1796 *****************************************************************/ 1797 1798 #ifdef EXECUTABLE 1799 1800 #define ARRAY_TYPE_TEST_DEFINITION(TYPE, CONTENT_TYPE, LINK_TYPE) \ 1801 void test_##TYPE(const CONTENT_TYPE *data, unsigned data_len, \ 1802 CONTENT_TYPE data_min, \ 1803 CONTENT_TYPE data_max, \ 1804 CONTENT_TYPE data_sum, \ 1805 const CONTENT_TYPE *sorted_data); \ 1806 \ 1807 void test_##LINK_TYPE(const TYPE *parent, \ 1808 CONTENT_TYPE data_min, \ 1809 CONTENT_TYPE data_max, \ 1810 CONTENT_TYPE data_sum); 1811 1812 ARRAY_TYPE_TEST_DEFINITION(a_int, int, l_int) 1813 ARRAY_TYPE_TEST_DEFINITION(a_double, double, l_double) 1814 ARRAY_TYPE_TEST_DEFINITION(a_unsigned, unsigned, l_unsigned) 1815 1816 #define ARRAY_A_TYPE_TEST_DEFINITION(TYPE, CONTENT_TYPE) \ 1817 void test_##TYPE(unsigned arrays, \ 1818 CONTENT_TYPE start, \ 1819 CONTENT_TYPE increment, \ 1820 unsigned total); 1821 1822 ARRAY_A_TYPE_TEST_DEFINITION(aa_int, int) 1823 ARRAY_A_TYPE_TEST_DEFINITION(aa_double, double) 1824 1825 #define ARRAY_AA_TYPE_TEST_DEFINITION(TYPE, CONTENT_TYPE) \ 1826 void test_##TYPE(unsigned arrays, \ 1827 unsigned sub_arrays, \ 1828 CONTENT_TYPE start, \ 1829 CONTENT_TYPE increment, \ 1830 unsigned total); 1831 1832 ARRAY_AA_TYPE_TEST_DEFINITION(aaa_int, int) 1833 ARRAY_AA_TYPE_TEST_DEFINITION(aaa_double, double) 1834 1835 int main(int argc, char *argv[]) { 1836 { 1837 int data[] = {5, 4, 3, 2, 1}; 1838 int sorted_data[] = {1, 2, 3, 4, 5}; 1839 1840 test_a_int(data, 5, 1, 5, 15, sorted_data); 1841 test_aa_int(5, 0, 1, 20); 1842 test_aaa_int(2, 3, 0, 1, 4); 1843 } 1844 { 1845 double data[] = {10.0, 8.0, 6.0, 4.0, 2.0}; 1846 double sorted_data[] = {2.0, 4.0, 6.0, 8.0, 10.0}; 1847 1848 test_a_double(data, 5, 2.0, 10.0, 30.0, sorted_data); 1849 test_aa_double(5, 0.0, 2.0, 20); 1850 test_aaa_double(2, 3, 0.0, 2.0, 4); 1851 } 1852 { 1853 unsigned data[] = {50, 40, 30, 20, 10}; 1854 unsigned sorted_data[] = {10, 20, 30, 40, 50}; 1855 test_a_unsigned(data, 5, 10, 50, 150, sorted_data); 1856 } 1857 1858 return 0; 1859 } 1860 1861 #define ARRAY_TYPE_TEST(TYPE, CONTENT_TYPE, LINK_TYPE) \ 1862 void test_##TYPE(const CONTENT_TYPE *data, unsigned data_len, \ 1863 CONTENT_TYPE data_min, \ 1864 CONTENT_TYPE data_max, \ 1865 CONTENT_TYPE data_sum, \ 1866 const CONTENT_TYPE *sorted_data) \ 1867 { \ 1868 TYPE *a; \ 1869 TYPE *b; \ 1870 unsigned i; \ 1871 \ 1872 assert(data_len >= 3); \ 1873 \ 1874 /*test resize*/ \ 1875 a = TYPE##_new(); \ 1876 assert(a->len == 0); \ 1877 assert(a->total_size > 0); \ 1878 a->resize(a, 10); \ 1879 assert(a->len == 0); \ 1880 assert(a->total_size >= 10); \ 1881 a->resize(a, 20); \ 1882 assert(a->len == 0); \ 1883 assert(a->total_size >= 20); \ 1884 a->del(a); \ 1885 \ 1886 /*test resize_for*/ \ 1887 a = TYPE##_new(); \ 1888 assert(a->len == 0); \ 1889 assert(a->total_size > 0); \ 1890 a->resize_for(a, 10); \ 1891 assert(a->len == 0); \ 1892 assert(a->total_size >= 10); \ 1893 for (i = 0; i < 10; i++) \ 1894 a_append(a, data[0]); \ 1895 a->resize_for(a, 10); \ 1896 assert(a->len == 10); \ 1897 assert(a->total_size >= 20); \ 1898 a->del(a); \ 1899 \ 1900 /*test reset*/ \ 1901 a = TYPE##_new(); \ 1902 a->resize(a, 10); \ 1903 for (i = 0; i < 10; i++) \ 1904 a_append(a, data[0]); \ 1905 assert(a->len == 10); \ 1906 a->reset(a); \ 1907 assert(a->len == 0); \ 1908 a->del(a); \ 1909 \ 1910 /*test reset_for*/ \ 1911 a = TYPE##_new(); \ 1912 a->resize(a, 10); \ 1913 for (i = 0; i < 10; i++) \ 1914 a_append(a, data[0]); \ 1915 assert(a->len == 10); \ 1916 assert(a->total_size >= 10); \ 1917 a->reset_for(a, 20); \ 1918 assert(a->len == 0); \ 1919 assert(a->total_size >= 20); \ 1920 a->del(a); \ 1921 \ 1922 /*test append*/ \ 1923 a = TYPE##_new(); \ 1924 for (i = 0; i < data_len; i++) \ 1925 a->append(a, data[i]); \ 1926 for (i = 0; i < data_len; i++) \ 1927 assert(a->_[i] == data[i]); \ 1928 a->del(a); \ 1929 \ 1930 /*test vappend*/ \ 1931 a = TYPE##_new(); \ 1932 a->vappend(a, 1, data[0]); \ 1933 assert(a->_[0] == data[0]); \ 1934 a->vappend(a, 2, data[0], data[1]); \ 1935 assert(a->_[0] == data[0]); \ 1936 for (i = 0; i < 2; i++) \ 1937 assert(a->_[i + 1] == data[i]); \ 1938 a->vappend(a, 3, data[0], data[1], data[2]); \ 1939 assert(a->_[0] == data[0]); \ 1940 for (i = 0; i < 2; i++) \ 1941 assert(a->_[i + 1] == data[i]); \ 1942 for (i = 0; i < 3; i++) \ 1943 assert(a->_[i + 3] == data[i]); \ 1944 a->del(a); \ 1945 \ 1946 /*test mappend*/ \ 1947 a = TYPE##_new(); \ 1948 a->mappend(a, 100, data[0]); \ 1949 for (i = 0; i < 100; i++) \ 1950 assert(a->_[i] == data[0]); \ 1951 a->mappend(a, 200, data[1]); \ 1952 for (i = 0; i < 100; i++) \ 1953 assert(a->_[i] == data[0]); \ 1954 for (i = 0; i < 200; i++) \ 1955 assert(a->_[i + 100] == data[1]); \ 1956 a->mappend(a, 300, data[2]); \ 1957 for (i = 0; i < 100; i++) \ 1958 assert(a->_[i] == data[0]); \ 1959 for (i = 0; i < 200; i++) \ 1960 assert(a->_[i + 100] == data[1]); \ 1961 for (i = 0; i < 300; i++) \ 1962 assert(a->_[i + 300] == data[2]); \ 1963 a->del(a); \ 1964 \ 1965 /*test insert*/ \ 1966 a = TYPE##_new(); \ 1967 for (i = 0; i < data_len; i++) \ 1968 a->insert(a, 0, data[i]); \ 1969 for (i = 0; i < data_len; i++) \ 1970 assert(a->_[a->len - i - 1] == data[i]); \ 1971 a->del(a); \ 1972 \ 1973 /*test vset*/ \ 1974 a = TYPE##_new(); \ 1975 a->vset(a, 1, data[0]); \ 1976 assert(a->_[0] == data[0]); \ 1977 a->vset(a, 2, data[0], data[1]); \ 1978 for (i = 0; i < 2; i++) \ 1979 assert(a->_[i] == data[i]); \ 1980 a->vset(a, 3, data[0], data[1], data[2]); \ 1981 for (i = 0; i < 3; i++) \ 1982 assert(a->_[i] == data[i]); \ 1983 a->del(a); \ 1984 \ 1985 /*test mset*/ \ 1986 a = TYPE##_new(); \ 1987 a->mset(a, 100, data[0]); \ 1988 for (i = 0; i < 100; i++) \ 1989 assert(a->_[i] == data[0]); \ 1990 a->mset(a, 200, data[1]); \ 1991 for (i = 0; i < 200; i++) \ 1992 assert(a->_[i] == data[1]); \ 1993 a->mset(a, 300, data[2]); \ 1994 for (i = 0; i < 300; i++) \ 1995 assert(a->_[i] == data[2]); \ 1996 a->del(a); \ 1997 \ 1998 /*test extend*/ \ 1999 a = TYPE##_new(); \ 2000 b = TYPE##_new(); \ 2001 \ 2002 for (i = 0; i < data_len; i++) \ 2003 a->append(a, data[i]); \ 2004 b->extend(b, a); \ 2005 for (i = 0; i < data_len; i++) \ 2006 assert(b->_[i] == data[i]); \ 2007 a->reset(a); \ 2008 for (i = 0; i < data_len; i++) \ 2009 a->append(a, sorted_data[i]); \ 2010 b->extend(b, a); \ 2011 for (i = 0; i < data_len; i++) \ 2012 assert(b->_[i] == data[i]); \ 2013 for (i = 0; i < data_len; i++) \ 2014 assert(b->_[i + data_len] == sorted_data[i]); \ 2015 a->del(a); \ 2016 b->del(b); \ 2017 \ 2018 /*test equals*/ \ 2019 a = TYPE##_new(); \ 2020 b = TYPE##_new(); \ 2021 \ 2022 for (i = 0; i < data_len; i++) { \ 2023 a->append(a, data[i]); \ 2024 b->append(b, data[i]); \ 2025 } \ 2026 assert(a->equals(a, a)); \ 2027 assert(a->equals(a, b)); \ 2028 b->reset(b); \ 2029 for (i = 0; i < data_len; i++) \ 2030 b->append(b, sorted_data[i]); \ 2031 assert(!a->equals(a, b)); \ 2032 assert(!b->equals(b, a)); \ 2033 a->del(a); \ 2034 b->del(b); \ 2035 \ 2036 /*test min*/ \ 2037 a = TYPE##_new(); \ 2038 for (i = 0; i < data_len; i++) \ 2039 a->append(a, data[i]); \ 2040 assert(a->min(a) == data_min); \ 2041 a->del(a); \ 2042 a = TYPE##_new(); \ 2043 for (i = 0; i < data_len; i++) \ 2044 a->append(a, sorted_data[i]); \ 2045 assert(a->min(a) == data_min); \ 2046 a->del(a); \ 2047 \ 2048 /*test max*/ \ 2049 a = TYPE##_new(); \ 2050 for (i = 0; i < data_len; i++) \ 2051 a->append(a, data[i]); \ 2052 assert(a->max(a) == data_max); \ 2053 a->del(a); \ 2054 a = TYPE##_new(); \ 2055 for (i = 0; i < data_len; i++) \ 2056 a->append(a, sorted_data[i]); \ 2057 assert(a->max(a) == data_max); \ 2058 a->del(a); \ 2059 \ 2060 /*test sum*/ \ 2061 a = TYPE##_new(); \ 2062 for (i = 0; i < data_len; i++) \ 2063 a->append(a, data[i]); \ 2064 assert(a->sum(a) == data_sum); \ 2065 a->del(a); \ 2066 a = TYPE##_new(); \ 2067 for (i = 0; i < data_len; i++) \ 2068 a->append(a, sorted_data[i]); \ 2069 assert(a->sum(a) == data_sum); \ 2070 a->del(a); \ 2071 \ 2072 /*test copy*/ \ 2073 a = TYPE##_new(); \ 2074 b = TYPE##_new(); \ 2075 for (i = 0; i < data_len; i++) { \ 2076 a->append(a, data[i]); \ 2077 b->append(b, sorted_data[i]); \ 2078 } \ 2079 assert(!a->equals(a, b)); \ 2080 a->copy(a, b); \ 2081 assert(a->equals(a, b)); \ 2082 a->del(a); \ 2083 b->del(b); \ 2084 \ 2085 /*test link*/ \ 2086 a = TYPE##_new(); \ 2087 for (i = 0; i < data_len; i++) \ 2088 a->append(a, data[i]); \ 2089 test_##LINK_TYPE(a, data_min, data_max, data_sum); \ 2090 a->del(a); \ 2091 \ 2092 /*test swap*/ \ 2093 a = TYPE##_new(); \ 2094 b = TYPE##_new(); \ 2095 for (i = 0; i < data_len; i++) { \ 2096 a->append(a, data[i]); \ 2097 b->append(b, sorted_data[i]); \ 2098 } \ 2099 for (i = 0; i < data_len; i++) { \ 2100 assert(a->_[i] == data[i]); \ 2101 assert(b->_[i] == sorted_data[i]); \ 2102 } \ 2103 a->swap(a, a); \ 2104 for (i = 0; i < data_len; i++) { \ 2105 assert(a->_[i] == data[i]); \ 2106 assert(b->_[i] == sorted_data[i]); \ 2107 } \ 2108 a->swap(a, b); \ 2109 for (i = 0; i < data_len; i++) { \ 2110 assert(a->_[i] == sorted_data[i]); \ 2111 assert(b->_[i] == data[i]); \ 2112 } \ 2113 b->swap(b, a); \ 2114 for (i = 0; i < data_len; i++) { \ 2115 assert(a->_[i] == data[i]); \ 2116 assert(b->_[i] == sorted_data[i]); \ 2117 } \ 2118 a->del(a); \ 2119 b->del(b); \ 2120 \ 2121 /*test head*/ \ 2122 for (i = 0; i < data_len; i++) { \ 2123 unsigned j; \ 2124 \ 2125 a = TYPE##_new(); \ 2126 for (j = 0; j < data_len; j++) \ 2127 a->append(a, data[j]); \ 2128 a->head(a, i, a); \ 2129 assert(a->len == i); \ 2130 for (j = 0; j < i; j++) \ 2131 assert(a->_[j] == data[j]); \ 2132 a->del(a); \ 2133 \ 2134 a = TYPE##_new(); \ 2135 for (j = 0; j < data_len; j++) \ 2136 a->append(a, data[j]); \ 2137 a->head(a, data_len + 1, a); \ 2138 assert(a->len == data_len); \ 2139 for (j = 0; j < data_len; j++) \ 2140 assert(a->_[j] == data[j]); \ 2141 a->del(a); \ 2142 \ 2143 a = TYPE##_new(); \ 2144 b = TYPE##_new(); \ 2145 for (j = 0; j < data_len; j++) \ 2146 a->append(a, data[j]); \ 2147 a->head(a, i, b); \ 2148 assert(a->len == data_len); \ 2149 assert(b->len == i); \ 2150 for (j = 0; j < data_len; j++) \ 2151 assert(a->_[j] == data[j]); \ 2152 for (j = 0; j < i; j++) \ 2153 assert(b->_[j] == data[j]); \ 2154 a->del(a); \ 2155 b->del(b); \ 2156 \ 2157 a = TYPE##_new(); \ 2158 b = TYPE##_new(); \ 2159 for (j = 0; j < data_len; j++) \ 2160 a->append(a, data[j]); \ 2161 a->head(a, data_len + 1, b); \ 2162 assert(a->equals(a, b)); \ 2163 a->del(a); \ 2164 b->del(b); \ 2165 } \ 2166 \ 2167 /*test tail*/ \ 2168 for (i = 0; i < data_len; i++) { \ 2169 unsigned j; \ 2170 \ 2171 a = TYPE##_new(); \ 2172 for (j = 0; j < data_len; j++) \ 2173 a->append(a, data[j]); \ 2174 a->tail(a, i, a); \ 2175 assert(a->len == i); \ 2176 for (j = 0; j < i; j++) \ 2177 assert(a->_[j] == data[j + (data_len - i)]); \ 2178 a->del(a); \ 2179 \ 2180 a = TYPE##_new(); \ 2181 for (j = 0; j < data_len; j++) \ 2182 a->append(a, data[j]); \ 2183 a->tail(a, data_len + 1, a); \ 2184 assert(a->len == data_len); \ 2185 for (j = 0; j < data_len; j++) \ 2186 assert(a->_[j] == data[j]); \ 2187 a->del(a); \ 2188 \ 2189 a = TYPE##_new(); \ 2190 b = TYPE##_new(); \ 2191 for (j = 0; j < data_len; j++) \ 2192 a->append(a, data[j]); \ 2193 a->tail(a, i, b); \ 2194 assert(a->len == data_len); \ 2195 assert(b->len == i); \ 2196 for (j = 0; j < data_len; j++) \ 2197 assert(a->_[j] == data[j]); \ 2198 for (j = 0; j < i; j++) \ 2199 assert(b->_[j] == data[j + (data_len - i)]); \ 2200 a->del(a); \ 2201 b->del(b); \ 2202 \ 2203 a = TYPE##_new(); \ 2204 b = TYPE##_new(); \ 2205 for (j = 0; j < data_len; j++) \ 2206 a->append(a, data[j]); \ 2207 a->tail(a, data_len + 1, b); \ 2208 assert(a->equals(a, b)); \ 2209 a->del(a); \ 2210 b->del(b); \ 2211 } \ 2212 \ 2213 /*test de_head*/ \ 2214 for (i = 0; i < data_len; i++) { \ 2215 unsigned j; \ 2216 \ 2217 a = TYPE##_new(); \ 2218 for (j = 0; j < data_len; j++) \ 2219 a->append(a, data[j]); \ 2220 a->de_head(a, i, a); \ 2221 assert(a->len == (data_len - i)); \ 2222 for (j = 0; j < (data_len - i); j++) \ 2223 assert(a->_[j] == data[j + i]); \ 2224 a->del(a); \ 2225 \ 2226 a = TYPE##_new(); \ 2227 for (j = 0; j < data_len; j++) \ 2228 a->append(a, data[j]); \ 2229 a->de_head(a, data_len + 1, a); \ 2230 assert(a->len == 0); \ 2231 a->del(a); \ 2232 \ 2233 a = TYPE##_new(); \ 2234 b = TYPE##_new(); \ 2235 for (j = 0; j < data_len; j++) \ 2236 a->append(a, data[j]); \ 2237 a->de_head(a, i, b); \ 2238 assert(a->len == data_len); \ 2239 assert(b->len == (data_len - i)); \ 2240 for (j = 0; j < data_len; j++) \ 2241 assert(a->_[j] == data[j]); \ 2242 for (j = 0; j < (data_len - i); j++) \ 2243 assert(b->_[j] == data[j + i]); \ 2244 a->del(a); \ 2245 b->del(b); \ 2246 \ 2247 a = TYPE##_new(); \ 2248 b = TYPE##_new(); \ 2249 for (j = 0; j < data_len; j++) \ 2250 a->append(a, data[j]); \ 2251 a->de_head(a, data_len + 1, b); \ 2252 assert(a->len == data_len); \ 2253 assert(b->len == 0); \ 2254 a->del(a); \ 2255 b->del(b); \ 2256 } \ 2257 \ 2258 /*test de_tail*/ \ 2259 for (i = 0; i < data_len; i++) { \ 2260 unsigned j; \ 2261 \ 2262 a = TYPE##_new(); \ 2263 for (j = 0; j < data_len; j++) \ 2264 a->append(a, data[j]); \ 2265 a->de_tail(a, i, a); \ 2266 assert(a->len == (data_len - i)); \ 2267 for (j = 0; j < (data_len - i); j++) \ 2268 assert(a->_[j] == data[j]); \ 2269 a->del(a); \ 2270 \ 2271 a = TYPE##_new(); \ 2272 for (j = 0; j < data_len; j++) \ 2273 a->append(a, data[j]); \ 2274 a->de_tail(a, data_len + 1, a); \ 2275 assert(a->len == 0); \ 2276 a->del(a); \ 2277 \ 2278 a = TYPE##_new(); \ 2279 b = TYPE##_new(); \ 2280 for (j = 0; j < data_len; j++) \ 2281 a->append(a, data[j]); \ 2282 a->de_tail(a, i, b); \ 2283 assert(a->len == data_len); \ 2284 assert(b->len == (data_len - i)); \ 2285 for (j = 0; j < data_len; j++) \ 2286 assert(a->_[j] == data[j]); \ 2287 for (j = 0; j < (data_len - i); j++) \ 2288 assert(b->_[j] == data[j]); \ 2289 a->del(a); \ 2290 b->del(b); \ 2291 \ 2292 a = TYPE##_new(); \ 2293 b = TYPE##_new(); \ 2294 for (j = 0; j < data_len; j++) \ 2295 a->append(a, data[j]); \ 2296 a->de_tail(a, data_len + 1, b); \ 2297 assert(a->len == data_len); \ 2298 assert(b->len == 0); \ 2299 a->del(a); \ 2300 b->del(b); \ 2301 } \ 2302 \ 2303 /*test split*/ \ 2304 for (i = 0; i < data_len; i++) { \ 2305 unsigned j; \ 2306 unsigned k; \ 2307 TYPE *c; \ 2308 \ 2309 a = TYPE##_new(); \ 2310 for (j = 0; j < data_len; j++) \ 2311 a->append(a, data[j]); \ 2312 \ 2313 a->split(a, i, a, a); \ 2314 for (j = 0; j < data_len; j++) \ 2315 assert(a->_[j] == data[j]); \ 2316 a->del(a); \ 2317 \ 2318 a = TYPE##_new(); \ 2319 b = TYPE##_new(); \ 2320 for (j = 0; j < data_len; j++) \ 2321 a->append(a, data[j]); \ 2322 a->split(a, i, a, b); \ 2323 assert(a->len == i); \ 2324 assert(b->len == (data_len - i)); \ 2325 for (j = 0; j < i; j++) \ 2326 assert(a->_[j] == data[j]); \ 2327 for (k = 0; j < data_len; j++,k++) \ 2328 assert(b->_[k] == data[j]); \ 2329 a->del(a); \ 2330 b->del(b); \ 2331 \ 2332 a = TYPE##_new(); \ 2333 b = TYPE##_new(); \ 2334 for (j = 0; j < data_len; j++) \ 2335 a->append(a, data[j]); \ 2336 a->split(a, i, b, a); \ 2337 assert(a->len == (data_len - i)); \ 2338 assert(b->len == i); \ 2339 for (j = 0; j < i; j++) \ 2340 assert(b->_[j] == data[j]); \ 2341 for (k = 0; j < data_len; j++,k++) \ 2342 assert(a->_[k] == data[j]); \ 2343 a->del(a); \ 2344 b->del(b); \ 2345 \ 2346 a = TYPE##_new(); \ 2347 b = TYPE##_new(); \ 2348 c = TYPE##_new(); \ 2349 for (j = 0; j < data_len; j++) \ 2350 a->append(a, data[j]); \ 2351 a->split(a, i, b, c); \ 2352 assert(a->len == data_len); \ 2353 for (j = 0; j < data_len; j++) \ 2354 assert(a->_[j] == data[j]); \ 2355 assert(b->len == i); \ 2356 assert(c->len == (data_len - i)); \ 2357 for (j = 0; j < i; j++) \ 2358 assert(b->_[j] == data[j]); \ 2359 for (k = 0; j < data_len; j++,k++) \ 2360 assert(c->_[k] == data[j]); \ 2361 a->del(a); \ 2362 b->del(b); \ 2363 c->del(c); \ 2364 } \ 2365 \ 2366 /*test concat*/ \ 2367 a = TYPE##_new(); \ 2368 for (i = 0; i < data_len; i++) \ 2369 a->append(a, data[i]); \ 2370 a->concat(a, a, a); \ 2371 for (i = 0; i < data_len; i++) \ 2372 assert(a->_[i] == data[i]); \ 2373 for (i = 0; i < data_len; i++) \ 2374 assert(a->_[i + data_len] == data[i]); \ 2375 a->del(a); \ 2376 \ 2377 a = TYPE##_new(); \ 2378 b = TYPE##_new(); \ 2379 for (i = 0; i < data_len; i++) \ 2380 a->append(a, data[i]); \ 2381 a->concat(a, a, b); \ 2382 for (i = 0; i < data_len; i++) \ 2383 assert(b->_[i] == data[i]); \ 2384 for (i = 0; i < data_len; i++) \ 2385 assert(b->_[i + data_len] == data[i]); \ 2386 a->del(a); \ 2387 b->del(b); \ 2388 \ 2389 a = TYPE##_new(); \ 2390 b = TYPE##_new(); \ 2391 for (i = 0; i < data_len; i++) { \ 2392 a->append(a, data[i]); \ 2393 b->append(b, sorted_data[i]); \ 2394 } \ 2395 a->concat(a, b, a); \ 2396 for (i = 0; i < data_len; i++) \ 2397 assert(a->_[i] == data[i]); \ 2398 for (i = 0; i < data_len; i++) \ 2399 assert(a->_[i + data_len] == sorted_data[i]); \ 2400 a->del(a); \ 2401 b->del(b); \ 2402 \ 2403 { \ 2404 TYPE *c; \ 2405 \ 2406 a = TYPE##_new(); \ 2407 b = TYPE##_new(); \ 2408 c = TYPE##_new(); \ 2409 for (i = 0; i < data_len; i++) { \ 2410 a->append(a, data[i]); \ 2411 b->append(b, sorted_data[i]); \ 2412 } \ 2413 a->concat(a, b, c); \ 2414 for (i = 0; i < data_len; i++) \ 2415 assert(c->_[i] == data[i]); \ 2416 for (i = 0; i < data_len; i++) \ 2417 assert(c->_[i + data_len] == sorted_data[i]); \ 2418 a->del(a); \ 2419 b->del(b); \ 2420 c->del(c); \ 2421 } \ 2422 \ 2423 /*test reverse*/ \ 2424 a = TYPE##_new(); \ 2425 for (i = 0; i < data_len; i++) \ 2426 a->append(a, data[i]); \ 2427 a->reverse(a); \ 2428 for (i = 0; i < data_len; i++) \ 2429 assert(a->_[i] == data[data_len - i - 1]); \ 2430 a->del(a); \ 2431 \ 2432 /*test sort*/ \ 2433 a = TYPE##_new(); \ 2434 for (i = 0; i < data_len; i++) \ 2435 a->append(a, data[i]); \ 2436 a->sort(a); \ 2437 for (i = 0; i < data_len; i++) \ 2438 assert(a->_[i] == sorted_data[i]); \ 2439 a->del(a); \ 2440 } \ 2441 \ 2442 void test_##LINK_TYPE(const TYPE *parent, \ 2443 CONTENT_TYPE data_min, \ 2444 CONTENT_TYPE data_max, \ 2445 CONTENT_TYPE data_sum) \ 2446 { \ 2447 unsigned i; \ 2448 LINK_TYPE* a; \ 2449 LINK_TYPE* b; \ 2450 TYPE *c; \ 2451 \ 2452 /*test internal data*/ \ 2453 a = LINK_TYPE##_new(); \ 2454 parent->link(parent, a); \ 2455 assert(a->len == parent->len); \ 2456 for (i = 0; i < parent->len; i++) \ 2457 assert(a->_[i] == parent->_[i]); \ 2458 a->del(a); \ 2459 \ 2460 /*test reset*/ \ 2461 a = LINK_TYPE##_new(); \ 2462 parent->link(parent, a); \ 2463 assert(a->len == parent->len); \ 2464 a->reset(a); \ 2465 assert(a->len == 0); \ 2466 a->del(a); \ 2467 \ 2468 /*test equals*/ \ 2469 a = LINK_TYPE##_new(); \ 2470 b = LINK_TYPE##_new(); \ 2471 parent->link(parent, a); \ 2472 parent->link(parent, b); \ 2473 assert(a->equals(a, b)); \ 2474 assert(b->equals(b, a)); \ 2475 a->del(a); \ 2476 b->del(b); \ 2477 \ 2478 /*test min*/ \ 2479 a = LINK_TYPE##_new(); \ 2480 parent->link(parent, a); \ 2481 assert(a->min(a) == data_min); \ 2482 a->del(a); \ 2483 \ 2484 /*test max*/ \ 2485 a = LINK_TYPE##_new(); \ 2486 parent->link(parent, a); \ 2487 assert(a->max(a) == data_max); \ 2488 a->del(a); \ 2489 \ 2490 /*test sum*/ \ 2491 a = LINK_TYPE##_new(); \ 2492 parent->link(parent, a); \ 2493 assert(a->sum(a) == data_sum); \ 2494 a->del(a); \ 2495 \ 2496 /*test copy*/ \ 2497 a = LINK_TYPE##_new(); \ 2498 c = TYPE##_new(); \ 2499 parent->link(parent, a); \ 2500 a->copy(a, c); \ 2501 assert(parent->equals(parent, c)); \ 2502 a->del(a); \ 2503 c->del(c); \ 2504 \ 2505 /*test swap*/ \ 2506 a = LINK_TYPE##_new(); \ 2507 b = LINK_TYPE##_new(); \ 2508 parent->link(parent, a); \ 2509 assert(a->len == parent->len); \ 2510 assert(b->len == 0); \ 2511 for (i = 0; i < parent->len; i++) \ 2512 assert(a->_[i] == parent->_[i]); \ 2513 a->swap(a, b); \ 2514 assert(a->len == 0); \ 2515 assert(b->len == parent->len); \ 2516 for (i = 0; i < parent->len; i++) \ 2517 assert(b->_[i] == parent->_[i]); \ 2518 b->swap(b, a); \ 2519 assert(a->len == parent->len); \ 2520 assert(b->len == 0); \ 2521 for (i = 0; i < parent->len; i++) \ 2522 assert(a->_[i] == parent->_[i]); \ 2523 a->del(a); \ 2524 b->del(b); \ 2525 \ 2526 /*test head*/ \ 2527 for (i = 0; i < parent->len; i++) { \ 2528 unsigned j; \ 2529 \ 2530 a = LINK_TYPE##_new(); \ 2531 parent->link(parent, a); \ 2532 a->head(a, i, a); \ 2533 assert(a->len == i); \ 2534 for (j = 0; j < i; j++) \ 2535 assert(a->_[j] == parent->_[j]); \ 2536 a->del(a); \ 2537 \ 2538 a = LINK_TYPE##_new(); \ 2539 parent->link(parent, a); \ 2540 a->head(a, parent->len + 1, a); \ 2541 assert(a->len == parent->len); \ 2542 for (j = 0; j < parent->len; j++) \ 2543 assert(a->_[j] == parent->_[j]); \ 2544 a->del(a); \ 2545 \ 2546 a = LINK_TYPE##_new(); \ 2547 b = LINK_TYPE##_new(); \ 2548 parent->link(parent, a); \ 2549 a->head(a, i, b); \ 2550 assert(a->len == parent->len); \ 2551 assert(b->len == i); \ 2552 for (j = 0; j < parent->len; j++) \ 2553 assert(a->_[j] == parent->_[j]); \ 2554 for (j = 0; j < i; j++) \ 2555 assert(b->_[j] == parent->_[j]); \ 2556 a->del(a); \ 2557 b->del(b); \ 2558 \ 2559 a = LINK_TYPE##_new(); \ 2560 b = LINK_TYPE##_new(); \ 2561 parent->link(parent, a); \ 2562 a->head(a, parent->len + 1, b); \ 2563 assert(a->equals(a, b)); \ 2564 a->del(a); \ 2565 b->del(b); \ 2566 } \ 2567 \ 2568 /*test tail*/ \ 2569 for (i = 0; i < parent->len; i++) { \ 2570 unsigned j; \ 2571 \ 2572 a = LINK_TYPE##_new(); \ 2573 parent->link(parent, a); \ 2574 a->tail(a, i, a); \ 2575 assert(a->len == i); \ 2576 for (j = 0; j < i; j++) \ 2577 assert(a->_[j] == parent->_[j + (parent->len - i)]); \ 2578 a->del(a); \ 2579 \ 2580 a = LINK_TYPE##_new(); \ 2581 parent->link(parent, a); \ 2582 a->tail(a, parent->len + 1, a); \ 2583 assert(a->len == parent->len); \ 2584 for (j = 0; j < parent->len; j++) \ 2585 assert(a->_[j] == parent->_[j]); \ 2586 a->del(a); \ 2587 \ 2588 a = LINK_TYPE##_new(); \ 2589 b = LINK_TYPE##_new(); \ 2590 parent->link(parent, a); \ 2591 a->tail(a, i, b); \ 2592 assert(a->len == parent->len); \ 2593 assert(b->len == i); \ 2594 for (j = 0; j < parent->len; j++) \ 2595 assert(a->_[j] == parent->_[j]); \ 2596 for (j = 0; j < i; j++) \ 2597 assert(b->_[j] == parent->_[j + (parent->len - i)]); \ 2598 a->del(a); \ 2599 b->del(b); \ 2600 \ 2601 a = LINK_TYPE##_new(); \ 2602 b = LINK_TYPE##_new(); \ 2603 parent->link(parent, a); \ 2604 a->tail(a, parent->len + 1, b); \ 2605 assert(a->equals(a, b)); \ 2606 a->del(a); \ 2607 b->del(b); \ 2608 } \ 2609 \ 2610 /*test de_head*/ \ 2611 for (i = 0; i < parent->len; i++) { \ 2612 unsigned j; \ 2613 \ 2614 a = LINK_TYPE##_new(); \ 2615 parent->link(parent, a); \ 2616 a->de_head(a, i, a); \ 2617 assert(a->len == (parent->len - i)); \ 2618 for (j = 0; j < (parent->len - i); j++) \ 2619 assert(a->_[j] == parent->_[j + i]); \ 2620 a->del(a); \ 2621 \ 2622 a = LINK_TYPE##_new(); \ 2623 parent->link(parent, a); \ 2624 a->de_head(a, parent->len + 1, a); \ 2625 assert(a->len == 0); \ 2626 a->del(a); \ 2627 \ 2628 a = LINK_TYPE##_new(); \ 2629 b = LINK_TYPE##_new(); \ 2630 parent->link(parent, a); \ 2631 a->de_head(a, i, b); \ 2632 assert(a->len == parent->len); \ 2633 assert(b->len == (parent->len - i)); \ 2634 for (j = 0; j < parent->len; j++) \ 2635 assert(a->_[j] == parent->_[j]); \ 2636 for (j = 0; j < (parent->len - i); j++) \ 2637 assert(b->_[j] == parent->_[j + i]); \ 2638 a->del(a); \ 2639 b->del(b); \ 2640 \ 2641 a = LINK_TYPE##_new(); \ 2642 b = LINK_TYPE##_new(); \ 2643 parent->link(parent, a); \ 2644 a->de_head(a, parent->len + 1, b); \ 2645 assert(a->len == parent->len); \ 2646 assert(b->len == 0); \ 2647 a->del(a); \ 2648 b->del(b); \ 2649 } \ 2650 \ 2651 /*test de_tail*/ \ 2652 for (i = 0; i < parent->len; i++) { \ 2653 unsigned j; \ 2654 \ 2655 a = LINK_TYPE##_new(); \ 2656 parent->link(parent, a); \ 2657 a->de_tail(a, i, a); \ 2658 assert(a->len == (parent->len - i)); \ 2659 for (j = 0; j < (parent->len - i); j++) \ 2660 assert(a->_[j] == parent->_[j]); \ 2661 a->del(a); \ 2662 \ 2663 a = LINK_TYPE##_new(); \ 2664 parent->link(parent, a); \ 2665 a->de_tail(a, parent->len + 1, a); \ 2666 assert(a->len == 0); \ 2667 a->del(a); \ 2668 \ 2669 a = LINK_TYPE##_new(); \ 2670 b = LINK_TYPE##_new(); \ 2671 parent->link(parent, a); \ 2672 a->de_tail(a, i, b); \ 2673 assert(a->len == parent->len); \ 2674 assert(b->len == (parent->len - i)); \ 2675 for (j = 0; j < parent->len; j++) \ 2676 assert(a->_[j] == parent->_[j]); \ 2677 for (j = 0; j < (parent->len - i); j++) \ 2678 assert(b->_[j] == parent->_[j]); \ 2679 a->del(a); \ 2680 b->del(b); \ 2681 \ 2682 a = LINK_TYPE##_new(); \ 2683 b = LINK_TYPE##_new(); \ 2684 parent->link(parent, a); \ 2685 a->de_tail(a, parent->len + 1, b); \ 2686 assert(a->len == parent->len); \ 2687 assert(b->len == 0); \ 2688 a->del(a); \ 2689 b->del(b); \ 2690 } \ 2691 \ 2692 /*test split*/ \ 2693 for (i = 0; i < parent->len; i++) { \ 2694 unsigned j; \ 2695 unsigned k; \ 2696 LINK_TYPE *c; \ 2697 \ 2698 a = LINK_TYPE##_new(); \ 2699 parent->link(parent, a); \ 2700 \ 2701 a->split(a, i, a, a); \ 2702 for (j = 0; j < parent->len; j++) \ 2703 assert(a->_[j] == parent->_[j]); \ 2704 a->del(a); \ 2705 \ 2706 a = LINK_TYPE##_new(); \ 2707 b = LINK_TYPE##_new(); \ 2708 parent->link(parent, a); \ 2709 a->split(a, i, a, b); \ 2710 assert(a->len == i); \ 2711 assert(b->len == (parent->len - i)); \ 2712 for (j = 0; j < i; j++) \ 2713 assert(a->_[j] == parent->_[j]); \ 2714 for (k = 0; j < parent->len; j++,k++) \ 2715 assert(b->_[k] == parent->_[j]); \ 2716 a->del(a); \ 2717 b->del(b); \ 2718 \ 2719 a = LINK_TYPE##_new(); \ 2720 b = LINK_TYPE##_new(); \ 2721 parent->link(parent, a); \ 2722 a->split(a, i, b, a); \ 2723 assert(a->len == (parent->len - i)); \ 2724 assert(b->len == i); \ 2725 for (j = 0; j < i; j++) \ 2726 assert(b->_[j] == parent->_[j]); \ 2727 for (k = 0; j < parent->len; j++,k++) \ 2728 assert(a->_[k] == parent->_[j]); \ 2729 a->del(a); \ 2730 b->del(b); \ 2731 \ 2732 a = LINK_TYPE##_new(); \ 2733 b = LINK_TYPE##_new(); \ 2734 c = LINK_TYPE##_new(); \ 2735 parent->link(parent, a); \ 2736 a->split(a, i, b, c); \ 2737 assert(a->len == parent->len); \ 2738 for (j = 0; j < parent->len; j++) \ 2739 assert(a->_[j] == parent->_[j]); \ 2740 assert(b->len == i); \ 2741 assert(c->len == (parent->len - i)); \ 2742 for (j = 0; j < i; j++) \ 2743 assert(b->_[j] == parent->_[j]); \ 2744 for (k = 0; j < parent->len; j++,k++) \ 2745 assert(c->_[k] == parent->_[j]); \ 2746 a->del(a); \ 2747 b->del(b); \ 2748 c->del(c); \ 2749 } \ 2750 } 2751 2752 ARRAY_TYPE_TEST(a_int, int, l_int) 2753 ARRAY_TYPE_TEST(a_double, double, l_double) 2754 ARRAY_TYPE_TEST(a_unsigned, unsigned, l_unsigned) 2755 2756 #define ARRAY_A_TYPE_TEST(TYPE, ARRAY_TYPE, CONTENT_TYPE) \ 2757 void test_##TYPE(unsigned arrays, \ 2758 CONTENT_TYPE start, \ 2759 CONTENT_TYPE increment, \ 2760 unsigned total) \ 2761 { \ 2762 TYPE *a; \ 2763 TYPE *b; \ 2764 unsigned i; \ 2765 CONTENT_TYPE old_start; \ 2766 \ 2767 /*test resize*/ \ 2768 a = TYPE##_new(); \ 2769 assert(a->len == 0); \ 2770 assert(a->total_size > 0); \ 2771 a->resize(a, 10); \ 2772 assert(a->len == 0); \ 2773 assert(a->total_size >= 10); \ 2774 a->resize(a, 20); \ 2775 assert(a->len == 0); \ 2776 assert(a->total_size >= 20); \ 2777 a->del(a); \ 2778 \ 2779 /*test reset*/ \ 2780 a = TYPE##_new(); \ 2781 a->resize(a, 10); \ 2782 for (i = 0; i < 10; i++) \ 2783 (void)a->append(a); \ 2784 assert(a->len == 10); \ 2785 a->reset(a); \ 2786 assert(a->len == 0); \ 2787 a->del(a); \ 2788 \ 2789 /*test append*/ \ 2790 /*note that we don't care about array contents, \ 2791 only that there are arrays*/ \ 2792 a = TYPE##_new(); \ 2793 for (i = 0; i < arrays; i++) { \ 2794 ARRAY_TYPE *c = a->append(a); \ 2795 unsigned j; \ 2796 for (j = 0; j < total; j++) { \ 2797 c->append(c, start); \ 2798 start += increment; \ 2799 } \ 2800 assert(c->len == total); \ 2801 } \ 2802 assert(a->len == arrays); \ 2803 a->del(a); \ 2804 \ 2805 /*test extend*/ \ 2806 old_start = start; \ 2807 a = TYPE##_new(); \ 2808 for (i = 0; i < arrays; i++) { \ 2809 ARRAY_TYPE *c = a->append(a); \ 2810 unsigned j; \ 2811 for (j = 0; j < total; j++) { \ 2812 c->append(c, start); \ 2813 start += increment; \ 2814 } \ 2815 } \ 2816 b = TYPE##_new(); \ 2817 for (i = 0; i < arrays; i++) { \ 2818 ARRAY_TYPE *c = b->append(b); \ 2819 unsigned j; \ 2820 for (j = 0; j < total; j++) { \ 2821 c->append(c, start); \ 2822 start += increment; \ 2823 } \ 2824 } \ 2825 a->extend(a, b); \ 2826 assert(a->len == (arrays * 2)); \ 2827 for (i = 0; i < arrays; i++) { \ 2828 unsigned j; \ 2829 for (j = 0; j < total; j++) { \ 2830 assert(a->_[i]->_[j] == old_start); \ 2831 old_start += increment; \ 2832 } \ 2833 } \ 2834 for (i = 0; i < arrays; i++) { \ 2835 unsigned j; \ 2836 for (j = 0; j < total; j++) { \ 2837 assert(a->_[i + arrays]->_[j] == old_start); \ 2838 old_start += increment; \ 2839 } \ 2840 } \ 2841 a->del(a); \ 2842 b->del(b); \ 2843 \ 2844 /*test equals*/ \ 2845 a = TYPE##_new(); \ 2846 b = TYPE##_new(); \ 2847 for (i = 0; i < arrays; i++) { \ 2848 ARRAY_TYPE *c = a->append(a); \ 2849 ARRAY_TYPE *d = b->append(b); \ 2850 unsigned j; \ 2851 for (j = 0; j < total; j++) { \ 2852 c->append(c, start); \ 2853 d->append(d, start); \ 2854 start += increment; \ 2855 } \ 2856 } \ 2857 assert(a->equals(a, b)); \ 2858 assert(b->equals(b, a)); \ 2859 b->reset(b); \ 2860 assert(!a->equals(a, b)); \ 2861 assert(!b->equals(b, a)); \ 2862 a->del(a); \ 2863 b->del(b); \ 2864 \ 2865 /*test copy*/ \ 2866 a = TYPE##_new(); \ 2867 b = TYPE##_new(); \ 2868 for (i = 0; i < arrays; i++) { \ 2869 ARRAY_TYPE *c = a->append(a); \ 2870 unsigned j; \ 2871 for (j = 0; j < total; j++) { \ 2872 c->append(c, start); \ 2873 start += increment; \ 2874 } \ 2875 } \ 2876 assert(!a->equals(a, b)); \ 2877 a->copy(a, b); \ 2878 assert(a->equals(a, b)); \ 2879 a->del(a); \ 2880 b->del(b); \ 2881 \ 2882 /*test swap*/ \ 2883 old_start = start; \ 2884 a = TYPE##_new(); \ 2885 b = TYPE##_new(); \ 2886 for (i = 0; i < arrays; i++) { \ 2887 ARRAY_TYPE *c = a->append(a); \ 2888 unsigned j; \ 2889 for (j = 0; j < total; j++) { \ 2890 c->append(c, start); \ 2891 start += increment; \ 2892 } \ 2893 } \ 2894 assert(a->len == arrays); \ 2895 assert(b->len == 0); \ 2896 a->swap(a, b); \ 2897 assert(a->len == 0); \ 2898 assert(b->len == arrays); \ 2899 for (i = 0; i < arrays; i++) { \ 2900 unsigned j; \ 2901 for (j = 0; j < total; j++) { \ 2902 assert(b->_[i]->_[j] == old_start); \ 2903 old_start += increment; \ 2904 } \ 2905 } \ 2906 a->del(a); \ 2907 b->del(b); \ 2908 \ 2909 /*test split*/ \ 2910 for (i = 0; i < arrays; i++) { \ 2911 TYPE *c; \ 2912 unsigned j; \ 2913 unsigned k; \ 2914 CONTENT_TYPE old_start2; \ 2915 \ 2916 /*split a to a,a*/ \ 2917 old_start = start; \ 2918 a = TYPE##_new(); \ 2919 \ 2920 for (j = 0; j < arrays; j++) { \ 2921 ARRAY_TYPE *d = a->append(a); \ 2922 for (k = 0; k < total; k++) { \ 2923 d->append(d, start); \ 2924 start += increment; \ 2925 } \ 2926 } \ 2927 a->split(a, i, a, a); \ 2928 for (j = 0; j < arrays; j++) { \ 2929 for (k = 0; k < total; k++) { \ 2930 assert(a->_[j]->_[k] == old_start); \ 2931 old_start += increment; \ 2932 } \ 2933 } \ 2934 a->del(a); \ 2935 \ 2936 /*split a to a,b*/ \ 2937 old_start = start; \ 2938 a = TYPE##_new(); \ 2939 b = TYPE##_new(); \ 2940 \ 2941 for (j = 0; j < arrays; j++) { \ 2942 ARRAY_TYPE *d = a->append(a); \ 2943 for (k = 0; k < total; k++) { \ 2944 d->append(d, start); \ 2945 start += increment; \ 2946 } \ 2947 } \ 2948 a->split(a, i, a, b); \ 2949 assert(a->len == i); \ 2950 assert(b->len == (arrays - i)); \ 2951 for (j = 0; j < i; j++) { \ 2952 for (k = 0; k < total; k++) { \ 2953 assert(a->_[j]->_[k] == old_start); \ 2954 old_start += increment; \ 2955 } \ 2956 } \ 2957 for (j = 0; j < (arrays - i); j++) { \ 2958 for (k = 0; k < total; k++) { \ 2959 assert(b->_[j]->_[k] == old_start); \ 2960 old_start += increment; \ 2961 } \ 2962 } \ 2963 a->del(a); \ 2964 b->del(b); \ 2965 \ 2966 /*split a to b,a*/ \ 2967 old_start = start; \ 2968 a = TYPE##_new(); \ 2969 b = TYPE##_new(); \ 2970 \ 2971 for (j = 0; j < arrays; j++) { \ 2972 ARRAY_TYPE *d = a->append(a); \ 2973 for (k = 0; k < total; k++) { \ 2974 d->append(d, start); \ 2975 start += increment; \ 2976 } \ 2977 } \ 2978 a->split(a, i, b, a); \ 2979 assert(a->len == (arrays - i)); \ 2980 assert(b->len == i); \ 2981 for (j = 0; j < i; j++) { \ 2982 for (k = 0; k < total; k++) { \ 2983 assert(b->_[j]->_[k] == old_start); \ 2984 old_start += increment; \ 2985 } \ 2986 } \ 2987 for (j = 0; j < (arrays - i); j++) { \ 2988 for (k = 0; k < total; k++) { \ 2989 assert(a->_[j]->_[k] == old_start); \ 2990 old_start += increment; \ 2991 } \ 2992 } \ 2993 a->del(a); \ 2994 b->del(b); \ 2995 \ 2996 /*split a to b,c*/ \ 2997 old_start = old_start2 = start; \ 2998 a = TYPE##_new(); \ 2999 b = TYPE##_new(); \ 3000 c = TYPE##_new(); \ 3001 \ 3002 for (j = 0; j < arrays; j++) { \ 3003 ARRAY_TYPE *d = a->append(a); \ 3004 for (k = 0; k < total; k++) { \ 3005 d->append(d, start); \ 3006 start += increment; \ 3007 } \ 3008 } \ 3009 a->split(a, i, b, c); \ 3010 assert(a->len == arrays); \ 3011 for (j = 0; j < arrays; j++) { \ 3012 for (k = 0; k < total; k++) { \ 3013 assert(a->_[j]->_[k] == old_start2); \ 3014 old_start2 += increment; \ 3015 } \ 3016 } \ 3017 assert(b->len == i); \ 3018 assert(c->len == (arrays - i)); \ 3019 for (j = 0; j < i; j++) { \ 3020 for (k = 0; k < total; k++) { \ 3021 assert(b->_[j]->_[k] == old_start); \ 3022 old_start += increment; \ 3023 } \ 3024 } \ 3025 for (j = 0; j < (arrays - i); j++) { \ 3026 for (k = 0; k < total; k++) { \ 3027 assert(c->_[j]->_[k] == old_start); \ 3028 old_start += increment; \ 3029 } \ 3030 } \ 3031 a->del(a); \ 3032 b->del(b); \ 3033 c->del(c); \ 3034 } \ 3035 \ 3036 /*test cross_split*/ \ 3037 for (i = 0; i < total; i++) { \ 3038 unsigned j; \ 3039 unsigned k; \ 3040 TYPE *c; \ 3041 CONTENT_TYPE old_start2; \ 3042 \ 3043 /*cross_split a to a,a*/ \ 3044 old_start = start; \ 3045 a = TYPE##_new(); \ 3046 for (j = 0; j < arrays; j++) { \ 3047 ARRAY_TYPE *d = a->append(a); \ 3048 for (k = 0; k < total; k++) { \ 3049 d->append(d, start); \ 3050 start += increment; \ 3051 } \ 3052 } \ 3053 a->cross_split(a, i, a, a); \ 3054 for (j = 0; j < arrays; j++) { \ 3055 for (k = 0; k < total; k++) { \ 3056 assert(a->_[j]->_[k] == old_start); \ 3057 old_start += increment; \ 3058 } \ 3059 } \ 3060 a->del(a); \ 3061 \ 3062 /*cross_split a to a,b*/ \ 3063 old_start = start; \ 3064 a = TYPE##_new(); \ 3065 b = TYPE##_new(); \ 3066 for (j = 0; j < arrays; j++) \ 3067 (void)a->append(a); \ 3068 for (j = 0; j < total; j++) { \ 3069 for (k = 0; k < arrays; k++) { \ 3070 a->_[k]->append(a->_[k], start); \ 3071 start += increment; \ 3072 } \ 3073 } \ 3074 a->cross_split(a, i, a, b); \ 3075 for (j = 0; j < i; j++) { \ 3076 for (k = 0; k < arrays; k++) { \ 3077 assert(a->_[k]->_[j] == old_start); \ 3078 old_start += increment; \ 3079 } \ 3080 } \ 3081 for (j = 0; j < (total - i); j++) { \ 3082 for (k = 0; k < arrays; k++) { \ 3083 assert(b->_[k]->_[j] == old_start); \ 3084 old_start += increment; \ 3085 } \ 3086 } \ 3087 a->del(a); \ 3088 b->del(b); \ 3089 \ 3090 /*cross_split a to b,a*/ \ 3091 old_start = start; \ 3092 a = TYPE##_new(); \ 3093 b = TYPE##_new(); \ 3094 for (j = 0; j < arrays; j++) \ 3095 (void)a->append(a); \ 3096 for (j = 0; j < total; j++) { \ 3097 for (k = 0; k < arrays; k++) { \ 3098 a->_[k]->append(a->_[k], start); \ 3099 start += increment; \ 3100 } \ 3101 } \ 3102 a->cross_split(a, i, b, a); \ 3103 for (j = 0; j < i; j++) { \ 3104 for (k = 0; k < arrays; k++) { \ 3105 assert(b->_[k]->_[j] == old_start); \ 3106 old_start += increment; \ 3107 } \ 3108 } \ 3109 for (j = 0; j < (total - i); j++) { \ 3110 for (k = 0; k < arrays; k++) { \ 3111 assert(a->_[k]->_[j] == old_start); \ 3112 old_start += increment; \ 3113 } \ 3114 } \ 3115 a->del(a); \ 3116 b->del(b); \ 3117 \ 3118 /*cross_split a to b,c*/ \ 3119 old_start = old_start2 = start; \ 3120 a = TYPE##_new(); \ 3121 b = TYPE##_new(); \ 3122 c = TYPE##_new(); \ 3123 for (j = 0; j < arrays; j++) \ 3124 (void)a->append(a); \ 3125 for (j = 0; j < total; j++) { \ 3126 for (k = 0; k < arrays; k++) { \ 3127 a->_[k]->append(a->_[k], start); \ 3128 start += increment; \ 3129 } \ 3130 } \ 3131 a->cross_split(a, i, b, c); \ 3132 for (j = 0; j < total; j++) { \ 3133 for (k = 0; k < arrays; k++) { \ 3134 assert(a->_[k]->_[j] == old_start2); \ 3135 old_start2 += increment; \ 3136 } \ 3137 } \ 3138 for (j = 0; j < i; j++) { \ 3139 for (k = 0; k < arrays; k++) { \ 3140 assert(b->_[k]->_[j] == old_start); \ 3141 old_start += increment; \ 3142 } \ 3143 } \ 3144 for (j = 0; j < (total - i); j++) { \ 3145 for (k = 0; k < arrays; k++) { \ 3146 assert(c->_[k]->_[j] == old_start); \ 3147 old_start += increment; \ 3148 } \ 3149 } \ 3150 a->del(a); \ 3151 b->del(b); \ 3152 c->del(c); \ 3153 } \ 3154 \ 3155 /*test reverse*/ \ 3156 a = TYPE##_new(); \ 3157 b = TYPE##_new(); \ 3158 for (i = 0; i < arrays; i++) { \ 3159 ARRAY_TYPE *c = a->append(a); \ 3160 unsigned j; \ 3161 for (j = 0; j < total; j++) { \ 3162 c->append(c, start); \ 3163 start += increment; \ 3164 } \ 3165 } \ 3166 a->copy(a, b); \ 3167 a->reverse(a); \ 3168 for (i = 0; i < arrays; i++) { \ 3169 assert(a->_[i]->equals(a->_[i], b->_[arrays - i - 1])); \ 3170 } \ 3171 a->del(a); \ 3172 b->del(b); \ 3173 } 3174 3175 ARRAY_A_TYPE_TEST(aa_int, a_int, int) 3176 ARRAY_A_TYPE_TEST(aa_double, a_double, double) 3177 3178 #define ARRAY_AA_TYPE_TEST(TYPE, A_TYPE, AA_TYPE, CONTENT_TYPE) \ 3179 void test_##TYPE(unsigned arrays, \ 3180 unsigned sub_arrays, \ 3181 CONTENT_TYPE start, \ 3182 CONTENT_TYPE increment, \ 3183 unsigned total) \ 3184 { \ 3185 TYPE *a; \ 3186 TYPE *b; \ 3187 unsigned i; \ 3188 CONTENT_TYPE old_start; \ 3189 \ 3190 /*test resize*/ \ 3191 a = TYPE##_new(); \ 3192 assert(a->len == 0); \ 3193 assert(a->total_size > 0); \ 3194 a->resize(a, 10); \ 3195 assert(a->len == 0); \ 3196 assert(a->total_size >= 10); \ 3197 a->resize(a, 20); \ 3198 assert(a->len == 0); \ 3199 assert(a->total_size >= 20); \ 3200 a->del(a); \ 3201 \ 3202 /*test reset*/ \ 3203 a = TYPE##_new(); \ 3204 a->resize(a, 10); \ 3205 for (i = 0; i < 10; i++) \ 3206 (void)a->append(a); \ 3207 assert(a->len == 10); \ 3208 a->reset(a); \ 3209 assert(a->len == 0); \ 3210 a->del(a); \ 3211 \ 3212 /*test append*/ \ 3213 a = TYPE##_new(); \ 3214 for (i = 0; i < arrays; i++) { \ 3215 A_TYPE *c = a->append(a); \ 3216 unsigned j; \ 3217 for (j = 0; j < sub_arrays; j++) { \ 3218 AA_TYPE* d = c->append(c); \ 3219 unsigned k; \ 3220 for (k = 0; k < total; k++) { \ 3221 d->append(d, start); \ 3222 start += increment; \ 3223 } \ 3224 assert(d->len == total); \ 3225 } \ 3226 assert(c->len == sub_arrays); \ 3227 } \ 3228 assert(a->len == arrays); \ 3229 a->del(a); \ 3230 \ 3231 /*test extend*/ \ 3232 old_start = start; \ 3233 a = TYPE##_new(); \ 3234 for (i = 0; i < arrays; i++) { \ 3235 A_TYPE *c = a->append(a); \ 3236 unsigned j; \ 3237 for (j = 0; j < sub_arrays; j++) { \ 3238 AA_TYPE* d = c->append(c); \ 3239 unsigned k; \ 3240 for (k = 0; k < total; k++) { \ 3241 d->append(d, start); \ 3242 start += increment; \ 3243 } \ 3244 assert(d->len == total); \ 3245 } \ 3246 } \ 3247 b = TYPE##_new(); \ 3248 for (i = 0; i < arrays; i++) { \ 3249 A_TYPE *c = a->append(a); \ 3250 unsigned j; \ 3251 for (j = 0; j < sub_arrays; j++) { \ 3252 AA_TYPE* d = c->append(c); \ 3253 unsigned k; \ 3254 for (k = 0; k < total; k++) { \ 3255 d->append(d, start); \ 3256 start += increment; \ 3257 } \ 3258 assert(d->len == total); \ 3259 } \ 3260 } \ 3261 a->extend(a, b); \ 3262 assert(a->len == (arrays * 2)); \ 3263 for (i = 0; i < arrays; i++) { \ 3264 unsigned j; \ 3265 for (j = 0; j < sub_arrays; j++) { \ 3266 unsigned k; \ 3267 for (k = 0; k < total; k++) { \ 3268 assert(a->_[i]->_[j]->_[k] == old_start); \ 3269 old_start += increment; \ 3270 } \ 3271 } \ 3272 } \ 3273 for (i = 0; i < arrays; i++) { \ 3274 unsigned j; \ 3275 for (j = 0; j < sub_arrays; j++) { \ 3276 unsigned k; \ 3277 for (k = 0; k < total; k++) { \ 3278 assert(a->_[i + arrays]->_[j]->_[k] == old_start); \ 3279 old_start += increment; \ 3280 } \ 3281 } \ 3282 } \ 3283 a->del(a); \ 3284 b->del(b); \ 3285 \ 3286 /*test equals*/ \ 3287 a = TYPE##_new(); \ 3288 b = TYPE##_new(); \ 3289 for (i = 0; i < arrays; i++) { \ 3290 A_TYPE *c = a->append(a); \ 3291 A_TYPE *d = b->append(b); \ 3292 unsigned j; \ 3293 for (j = 0; j < sub_arrays; j++) { \ 3294 AA_TYPE* e = c->append(c); \ 3295 AA_TYPE* f = d->append(d); \ 3296 unsigned k; \ 3297 for (k = 0; k < total; k++) { \ 3298 e->append(e, start); \ 3299 f->append(f, start); \ 3300 start += increment; \ 3301 } \ 3302 } \ 3303 } \ 3304 assert(a->equals(a, b)); \ 3305 assert(b->equals(b, a)); \ 3306 b->reset(b); \ 3307 assert(!a->equals(a, b)); \ 3308 assert(!b->equals(b, a)); \ 3309 a->del(a); \ 3310 b->del(b); \ 3311 \ 3312 /*test copy*/ \ 3313 a = TYPE##_new(); \ 3314 b = TYPE##_new(); \ 3315 for (i = 0; i < arrays; i++) { \ 3316 A_TYPE *c = a->append(a); \ 3317 unsigned j; \ 3318 for (j = 0; j < sub_arrays; j++) { \ 3319 AA_TYPE* d = c->append(c); \ 3320 unsigned k; \ 3321 for (k = 0; k < total; k++) { \ 3322 d->append(d, start); \ 3323 start += increment; \ 3324 } \ 3325 } \ 3326 } \ 3327 assert(!a->equals(a, b)); \ 3328 a->copy(a, b); \ 3329 assert(a->equals(a, b)); \ 3330 a->del(a); \ 3331 b->del(b); \ 3332 \ 3333 /*test swap*/ \ 3334 old_start = start; \ 3335 a = TYPE##_new(); \ 3336 b = TYPE##_new(); \ 3337 for (i = 0; i < arrays; i++) { \ 3338 A_TYPE *c = a->append(a); \ 3339 unsigned j; \ 3340 for (j = 0; j < sub_arrays; j++) { \ 3341 AA_TYPE* d = c->append(c); \ 3342 unsigned k; \ 3343 for (k = 0; k < total; k++) { \ 3344 d->append(d, start); \ 3345 start += increment; \ 3346 } \ 3347 } \ 3348 } \ 3349 assert(a->len == arrays); \ 3350 assert(b->len == 0); \ 3351 a->swap(a, b); \ 3352 assert(a->len == 0); \ 3353 assert(b->len == arrays); \ 3354 for (i = 0; i < arrays; i++) { \ 3355 unsigned j; \ 3356 for (j = 0; j < sub_arrays; j++) { \ 3357 unsigned k; \ 3358 for (k = 0; k < total; k++) { \ 3359 assert(b->_[i]->_[j]->_[k] == old_start); \ 3360 old_start += increment; \ 3361 } \ 3362 } \ 3363 } \ 3364 a->del(a); \ 3365 b->del(b); \ 3366 \ 3367 /*test split*/ \ 3368 for (i = 0; i < arrays; i++) { \ 3369 TYPE *base = TYPE##_new(); \ 3370 TYPE *c; \ 3371 unsigned j; \ 3372 \ 3373 for (j = 0; j < arrays; j++) { \ 3374 A_TYPE *c = base->append(base); \ 3375 unsigned k; \ 3376 \ 3377 for (k = 0; k < sub_arrays; k++) { \ 3378 AA_TYPE* d = c->append(c); \ 3379 unsigned l; \ 3380 for (l = 0; l < total; l++) { \ 3381 d->append(d, start); \ 3382 start += increment; \ 3383 } \ 3384 } \ 3385 } \ 3386 \ 3387 /*split a to a,a*/ \ 3388 a = TYPE##_new(); \ 3389 base->copy(base, a); \ 3390 a->split(a, i, a, a); \ 3391 for (j = 0; j < arrays; j++) \ 3392 assert(a->_[j]->equals(a->_[j], base->_[j])); \ 3393 a->del(a); \ 3394 \ 3395 /*split a to a,b*/ \ 3396 a = TYPE##_new(); \ 3397 b = TYPE##_new(); \ 3398 base->copy(base, a); \ 3399 a->split(a, i, a, b); \ 3400 for (j = 0; j < i; j++) \ 3401 assert(a->_[j]->equals(a->_[j], base->_[j])); \ 3402 for (j = 0; j < (arrays - i); j++) \ 3403 assert(b->_[j]->equals(b->_[j], base->_[j + i])); \ 3404 a->del(a); \ 3405 b->del(b); \ 3406 \ 3407 /*split a to b,a*/ \ 3408 a = TYPE##_new(); \ 3409 b = TYPE##_new(); \ 3410 base->copy(base, a); \ 3411 a->split(a, i, b, a); \ 3412 for (j = 0; j < i; j++) \ 3413 assert(b->_[j]->equals(b->_[j], base->_[j])); \ 3414 for (j = 0; j < (arrays - i); j++) \ 3415 assert(a->_[j]->equals(a->_[j], base->_[j + i])); \ 3416 a->del(a); \ 3417 b->del(b); \ 3418 \ 3419 /*split a to b,c*/ \ 3420 a = TYPE##_new(); \ 3421 b = TYPE##_new(); \ 3422 c = TYPE##_new(); \ 3423 base->copy(base, a); \ 3424 a->split(a, i, b, c); \ 3425 for (j = 0; j < i; j++) \ 3426 assert(b->_[j]->equals(b->_[j], base->_[j])); \ 3427 for (j = 0; j < (arrays - i); j++) \ 3428 assert(c->_[j]->equals(c->_[j], base->_[j + i])); \ 3429 a->del(a); \ 3430 b->del(b); \ 3431 c->del(c); \ 3432 \ 3433 base->del(base); \ 3434 } \ 3435 \ 3436 /*test reverse*/ \ 3437 a = TYPE##_new(); \ 3438 b = TYPE##_new(); \ 3439 for (i = 0; i < arrays; i++) { \ 3440 A_TYPE *c = a->append(a); \ 3441 unsigned j; \ 3442 \ 3443 for (j = 0; j < sub_arrays; j++) { \ 3444 AA_TYPE* d = c->append(c); \ 3445 unsigned k; \ 3446 for (k = 0; k < total; k++) { \ 3447 d->append(d, start); \ 3448 start += increment; \ 3449 } \ 3450 } \ 3451 } \ 3452 a->copy(a, b); \ 3453 a->reverse(a); \ 3454 for (i = 0; i < arrays; i++) { \ 3455 assert(a->_[i]->equals(a->_[i], b->_[arrays - i - 1])); \ 3456 } \ 3457 a->del(a); \ 3458 b->del(b); \ 3459 } 3460 3461 ARRAY_AA_TYPE_TEST(aaa_int, aa_int, a_int, int) 3462 ARRAY_AA_TYPE_TEST(aaa_double, aa_double, a_double, double) 3463 3464 #endif 3465