1 /* 2 * Sorted array routines for CUPS. 3 * 4 * Copyright 2007-2014 by Apple Inc. 5 * Copyright 1997-2007 by Easy Software Products. 6 * 7 * These coded instructions, statements, and computer programs are the 8 * property of Apple Inc. and are protected by Federal copyright 9 * law. Distribution and use rights are outlined in the file "LICENSE.txt" 10 * which should have been included with this file. If this file is 11 * missing or damaged, see the license at "http://www.cups.org/". 12 * 13 * This file is subject to the Apple OS-Developed Software exception. 14 */ 15 16 /* 17 * Include necessary headers... 18 */ 19 20 #include <cups/cups.h> 21 #include "string-private.h" 22 #include "debug-private.h" 23 #include "array-private.h" 24 25 26 /* 27 * Limits... 28 */ 29 30 #define _CUPS_MAXSAVE 32 /**** Maximum number of saves ****/ 31 32 33 /* 34 * Types and structures... 35 */ 36 37 struct _cups_array_s /**** CUPS array structure ****/ 38 { 39 /* 40 * The current implementation uses an insertion sort into an array of 41 * sorted pointers. We leave the array type private/opaque so that we 42 * can change the underlying implementation without affecting the users 43 * of this API. 44 */ 45 46 int num_elements, /* Number of array elements */ 47 alloc_elements, /* Allocated array elements */ 48 current, /* Current element */ 49 insert, /* Last inserted element */ 50 unique, /* Are all elements unique? */ 51 num_saved, /* Number of saved elements */ 52 saved[_CUPS_MAXSAVE]; 53 /* Saved elements */ 54 void **elements; /* Array elements */ 55 cups_array_func_t compare; /* Element comparison function */ 56 void *data; /* User data passed to compare */ 57 cups_ahash_func_t hashfunc; /* Hash function */ 58 int hashsize, /* Size of hash */ 59 *hash; /* Hash array */ 60 cups_acopy_func_t copyfunc; /* Copy function */ 61 cups_afree_func_t freefunc; /* Free function */ 62 }; 63 64 65 /* 66 * Local functions... 67 */ 68 69 static int cups_array_add(cups_array_t *a, void *e, int insert); 70 static int cups_array_find(cups_array_t *a, void *e, int prev, int *rdiff); 71 72 73 /* 74 * 'cupsArrayAdd()' - Add an element to the array. 75 * 76 * When adding an element to a sorted array, non-unique elements are 77 * appended at the end of the run of identical elements. For unsorted arrays, 78 * the element is appended to the end of the array. 79 * 80 * @since CUPS 1.2/macOS 10.5@ 81 */ 82 83 int /* O - 1 on success, 0 on failure */ 84 cupsArrayAdd(cups_array_t *a, /* I - Array */ 85 void *e) /* I - Element */ 86 { 87 DEBUG_printf(("2cupsArrayAdd(a=%p, e=%p)", (void *)a, e)); 88 89 /* 90 * Range check input... 91 */ 92 93 if (!a || !e) 94 { 95 DEBUG_puts("3cupsArrayAdd: returning 0"); 96 return (0); 97 } 98 99 /* 100 * Append the element... 101 */ 102 103 return (cups_array_add(a, e, 0)); 104 } 105 106 107 /* 108 * '_cupsArrayAddStrings()' - Add zero or more delimited strings to an array. 109 * 110 * Note: The array MUST be created using the @link _cupsArrayNewStrings@ 111 * function. Duplicate strings are NOT added. If the string pointer "s" is NULL 112 * or the empty string, no strings are added to the array. 113 */ 114 115 int /* O - 1 on success, 0 on failure */ 116 _cupsArrayAddStrings(cups_array_t *a, /* I - Array */ 117 const char *s, /* I - Delimited strings or NULL */ 118 char delim)/* I - Delimiter character */ 119 { 120 char *buffer, /* Copy of string */ 121 *start, /* Start of string */ 122 *end; /* End of string */ 123 int status = 1; /* Status of add */ 124 125 126 DEBUG_printf(("_cupsArrayAddStrings(a=%p, s=\"%s\", delim='%c')", (void *)a, s, delim)); 127 128 if (!a || !s || !*s) 129 { 130 DEBUG_puts("1_cupsArrayAddStrings: Returning 0"); 131 return (0); 132 } 133 134 if (delim == ' ') 135 { 136 /* 137 * Skip leading whitespace... 138 */ 139 140 DEBUG_puts("1_cupsArrayAddStrings: Skipping leading whitespace."); 141 142 while (*s && isspace(*s & 255)) 143 s ++; 144 145 DEBUG_printf(("1_cupsArrayAddStrings: Remaining string \"%s\".", s)); 146 } 147 148 if (!strchr(s, delim) && 149 (delim != ' ' || (!strchr(s, '\t') && !strchr(s, '\n')))) 150 { 151 /* 152 * String doesn't contain a delimiter, so add it as a single value... 153 */ 154 155 DEBUG_puts("1_cupsArrayAddStrings: No delimiter seen, adding a single " 156 "value."); 157 158 if (!cupsArrayFind(a, (void *)s)) 159 status = cupsArrayAdd(a, (void *)s); 160 } 161 else if ((buffer = strdup(s)) == NULL) 162 { 163 DEBUG_puts("1_cupsArrayAddStrings: Unable to duplicate string."); 164 status = 0; 165 } 166 else 167 { 168 for (start = end = buffer; *end; start = end) 169 { 170 /* 171 * Find the end of the current delimited string and see if we need to add 172 * it... 173 */ 174 175 if (delim == ' ') 176 { 177 while (*end && !isspace(*end & 255)) 178 end ++; 179 while (*end && isspace(*end & 255)) 180 *end++ = '\0'; 181 } 182 else if ((end = strchr(start, delim)) != NULL) 183 *end++ = '\0'; 184 else 185 end = start + strlen(start); 186 187 DEBUG_printf(("1_cupsArrayAddStrings: Adding \"%s\", end=\"%s\"", start, 188 end)); 189 190 if (!cupsArrayFind(a, start)) 191 status &= cupsArrayAdd(a, start); 192 } 193 194 free(buffer); 195 } 196 197 DEBUG_printf(("1_cupsArrayAddStrings: Returning %d.", status)); 198 199 return (status); 200 } 201 202 203 /* 204 * 'cupsArrayClear()' - Clear the array. 205 * 206 * This function is equivalent to removing all elements in the array. 207 * The caller is responsible for freeing the memory used by the 208 * elements themselves. 209 * 210 * @since CUPS 1.2/macOS 10.5@ 211 */ 212 213 void 214 cupsArrayClear(cups_array_t *a) /* I - Array */ 215 { 216 /* 217 * Range check input... 218 */ 219 220 if (!a) 221 return; 222 223 /* 224 * Free the existing elements as needed.. 225 */ 226 227 if (a->freefunc) 228 { 229 int i; /* Looping var */ 230 void **e; /* Current element */ 231 232 for (i = a->num_elements, e = a->elements; i > 0; i --, e ++) 233 (a->freefunc)(*e, a->data); 234 } 235 236 /* 237 * Set the number of elements to 0; we don't actually free the memory 238 * here - that is done in cupsArrayDelete()... 239 */ 240 241 a->num_elements = 0; 242 a->current = -1; 243 a->insert = -1; 244 a->unique = 1; 245 a->num_saved = 0; 246 } 247 248 249 /* 250 * 'cupsArrayCount()' - Get the number of elements in the array. 251 * 252 * @since CUPS 1.2/macOS 10.5@ 253 */ 254 255 int /* O - Number of elements */ 256 cupsArrayCount(cups_array_t *a) /* I - Array */ 257 { 258 /* 259 * Range check input... 260 */ 261 262 if (!a) 263 return (0); 264 265 /* 266 * Return the number of elements... 267 */ 268 269 return (a->num_elements); 270 } 271 272 273 /* 274 * 'cupsArrayCurrent()' - Return the current element in the array. 275 * 276 * The current element is undefined until you call @link cupsArrayFind@, 277 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@. 278 * 279 * @since CUPS 1.2/macOS 10.5@ 280 */ 281 282 void * /* O - Element */ 283 cupsArrayCurrent(cups_array_t *a) /* I - Array */ 284 { 285 /* 286 * Range check input... 287 */ 288 289 if (!a) 290 return (NULL); 291 292 /* 293 * Return the current element... 294 */ 295 296 if (a->current >= 0 && a->current < a->num_elements) 297 return (a->elements[a->current]); 298 else 299 return (NULL); 300 } 301 302 303 /* 304 * 'cupsArrayDelete()' - Free all memory used by the array. 305 * 306 * The caller is responsible for freeing the memory used by the 307 * elements themselves. 308 * 309 * @since CUPS 1.2/macOS 10.5@ 310 */ 311 312 void 313 cupsArrayDelete(cups_array_t *a) /* I - Array */ 314 { 315 /* 316 * Range check input... 317 */ 318 319 if (!a) 320 return; 321 322 /* 323 * Free the elements if we have a free function (otherwise the caller is 324 * responsible for doing the dirty work...) 325 */ 326 327 if (a->freefunc) 328 { 329 int i; /* Looping var */ 330 void **e; /* Current element */ 331 332 for (i = a->num_elements, e = a->elements; i > 0; i --, e ++) 333 (a->freefunc)(*e, a->data); 334 } 335 336 /* 337 * Free the array of element pointers... 338 */ 339 340 if (a->alloc_elements) 341 free(a->elements); 342 343 if (a->hashsize) 344 free(a->hash); 345 346 free(a); 347 } 348 349 350 /* 351 * 'cupsArrayDup()' - Duplicate the array. 352 * 353 * @since CUPS 1.2/macOS 10.5@ 354 */ 355 356 cups_array_t * /* O - Duplicate array */ 357 cupsArrayDup(cups_array_t *a) /* I - Array */ 358 { 359 cups_array_t *da; /* Duplicate array */ 360 361 362 /* 363 * Range check input... 364 */ 365 366 if (!a) 367 return (NULL); 368 369 /* 370 * Allocate memory for the array... 371 */ 372 373 da = calloc(1, sizeof(cups_array_t)); 374 if (!da) 375 return (NULL); 376 377 da->compare = a->compare; 378 da->data = a->data; 379 da->current = a->current; 380 da->insert = a->insert; 381 da->unique = a->unique; 382 da->num_saved = a->num_saved; 383 384 memcpy(da->saved, a->saved, sizeof(a->saved)); 385 386 if (a->num_elements) 387 { 388 /* 389 * Allocate memory for the elements... 390 */ 391 392 da->elements = malloc((size_t)a->num_elements * sizeof(void *)); 393 if (!da->elements) 394 { 395 free(da); 396 return (NULL); 397 } 398 399 /* 400 * Copy the element pointers... 401 */ 402 403 if (a->copyfunc) 404 { 405 /* 406 * Use the copy function to make a copy of each element... 407 */ 408 409 int i; /* Looping var */ 410 411 for (i = 0; i < a->num_elements; i ++) 412 da->elements[i] = (a->copyfunc)(a->elements[i], a->data); 413 } 414 else 415 { 416 /* 417 * Just copy raw pointers... 418 */ 419 420 memcpy(da->elements, a->elements, (size_t)a->num_elements * sizeof(void *)); 421 } 422 423 da->num_elements = a->num_elements; 424 da->alloc_elements = a->num_elements; 425 } 426 427 /* 428 * Return the new array... 429 */ 430 431 return (da); 432 } 433 434 435 /* 436 * 'cupsArrayFind()' - Find an element in the array. 437 * 438 * @since CUPS 1.2/macOS 10.5@ 439 */ 440 441 void * /* O - Element found or @code NULL@ */ 442 cupsArrayFind(cups_array_t *a, /* I - Array */ 443 void *e) /* I - Element */ 444 { 445 int current, /* Current element */ 446 diff, /* Difference */ 447 hash; /* Hash index */ 448 449 450 /* 451 * Range check input... 452 */ 453 454 if (!a || !e) 455 return (NULL); 456 457 /* 458 * See if we have any elements... 459 */ 460 461 if (!a->num_elements) 462 return (NULL); 463 464 /* 465 * Yes, look for a match... 466 */ 467 468 if (a->hash) 469 { 470 hash = (*(a->hashfunc))(e, a->data); 471 472 if (hash < 0 || hash >= a->hashsize) 473 { 474 current = a->current; 475 hash = -1; 476 } 477 else 478 { 479 current = a->hash[hash]; 480 481 if (current < 0 || current >= a->num_elements) 482 current = a->current; 483 } 484 } 485 else 486 { 487 current = a->current; 488 hash = -1; 489 } 490 491 current = cups_array_find(a, e, current, &diff); 492 if (!diff) 493 { 494 /* 495 * Found a match! If the array does not contain unique values, find 496 * the first element that is the same... 497 */ 498 499 if (!a->unique && a->compare) 500 { 501 /* 502 * The array is not unique, find the first match... 503 */ 504 505 while (current > 0 && !(*(a->compare))(e, a->elements[current - 1], 506 a->data)) 507 current --; 508 } 509 510 a->current = current; 511 512 if (hash >= 0) 513 a->hash[hash] = current; 514 515 return (a->elements[current]); 516 } 517 else 518 { 519 /* 520 * No match... 521 */ 522 523 a->current = -1; 524 525 return (NULL); 526 } 527 } 528 529 530 /* 531 * 'cupsArrayFirst()' - Get the first element in the array. 532 * 533 * @since CUPS 1.2/macOS 10.5@ 534 */ 535 536 void * /* O - First element or @code NULL@ if the array is empty */ 537 cupsArrayFirst(cups_array_t *a) /* I - Array */ 538 { 539 /* 540 * Range check input... 541 */ 542 543 if (!a) 544 return (NULL); 545 546 /* 547 * Return the first element... 548 */ 549 550 a->current = 0; 551 552 return (cupsArrayCurrent(a)); 553 } 554 555 556 /* 557 * 'cupsArrayGetIndex()' - Get the index of the current element. 558 * 559 * The current element is undefined until you call @link cupsArrayFind@, 560 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@. 561 * 562 * @since CUPS 1.3/macOS 10.5@ 563 */ 564 565 int /* O - Index of the current element, starting at 0 */ 566 cupsArrayGetIndex(cups_array_t *a) /* I - Array */ 567 { 568 if (!a) 569 return (-1); 570 else 571 return (a->current); 572 } 573 574 575 /* 576 * 'cupsArrayGetInsert()' - Get the index of the last inserted element. 577 * 578 * @since CUPS 1.3/macOS 10.5@ 579 */ 580 581 int /* O - Index of the last inserted element, starting at 0 */ 582 cupsArrayGetInsert(cups_array_t *a) /* I - Array */ 583 { 584 if (!a) 585 return (-1); 586 else 587 return (a->insert); 588 } 589 590 591 /* 592 * 'cupsArrayIndex()' - Get the N-th element in the array. 593 * 594 * @since CUPS 1.2/macOS 10.5@ 595 */ 596 597 void * /* O - N-th element or @code NULL@ */ 598 cupsArrayIndex(cups_array_t *a, /* I - Array */ 599 int n) /* I - Index into array, starting at 0 */ 600 { 601 if (!a) 602 return (NULL); 603 604 a->current = n; 605 606 return (cupsArrayCurrent(a)); 607 } 608 609 610 /* 611 * 'cupsArrayInsert()' - Insert an element in the array. 612 * 613 * When inserting an element in a sorted array, non-unique elements are 614 * inserted at the beginning of the run of identical elements. For unsorted 615 * arrays, the element is inserted at the beginning of the array. 616 * 617 * @since CUPS 1.2/macOS 10.5@ 618 */ 619 620 int /* O - 0 on failure, 1 on success */ 621 cupsArrayInsert(cups_array_t *a, /* I - Array */ 622 void *e) /* I - Element */ 623 { 624 DEBUG_printf(("2cupsArrayInsert(a=%p, e=%p)", (void *)a, e)); 625 626 /* 627 * Range check input... 628 */ 629 630 if (!a || !e) 631 { 632 DEBUG_puts("3cupsArrayInsert: returning 0"); 633 return (0); 634 } 635 636 /* 637 * Insert the element... 638 */ 639 640 return (cups_array_add(a, e, 1)); 641 } 642 643 644 /* 645 * 'cupsArrayLast()' - Get the last element in the array. 646 * 647 * @since CUPS 1.2/macOS 10.5@ 648 */ 649 650 void * /* O - Last element or @code NULL@ if the array is empty */ 651 cupsArrayLast(cups_array_t *a) /* I - Array */ 652 { 653 /* 654 * Range check input... 655 */ 656 657 if (!a) 658 return (NULL); 659 660 /* 661 * Return the last element... 662 */ 663 664 a->current = a->num_elements - 1; 665 666 return (cupsArrayCurrent(a)); 667 } 668 669 670 /* 671 * 'cupsArrayNew()' - Create a new array. 672 * 673 * The comparison function ("f") is used to create a sorted array. The function 674 * receives pointers to two elements and the user data pointer ("d") - the user 675 * data pointer argument can safely be omitted when not required so functions 676 * like @code strcmp@ can be used for sorted string arrays. 677 * 678 * @since CUPS 1.2/macOS 10.5@ 679 */ 680 681 cups_array_t * /* O - Array */ 682 cupsArrayNew(cups_array_func_t f, /* I - Comparison function or @code NULL@ for an unsorted array */ 683 void *d) /* I - User data pointer or @code NULL@ */ 684 { 685 return (cupsArrayNew3(f, d, 0, 0, 0, 0)); 686 } 687 688 689 /* 690 * 'cupsArrayNew2()' - Create a new array with hash. 691 * 692 * The comparison function ("f") is used to create a sorted array. The function 693 * receives pointers to two elements and the user data pointer ("d") - the user 694 * data pointer argument can safely be omitted when not required so functions 695 * like @code strcmp@ can be used for sorted string arrays. 696 * 697 * The hash function ("h") is used to implement cached lookups with the 698 * specified hash size ("hsize"). 699 * 700 * @since CUPS 1.3/macOS 10.5@ 701 */ 702 703 cups_array_t * /* O - Array */ 704 cupsArrayNew2(cups_array_func_t f, /* I - Comparison function or @code NULL@ for an unsorted array */ 705 void *d, /* I - User data or @code NULL@ */ 706 cups_ahash_func_t h, /* I - Hash function or @code NULL@ for unhashed lookups */ 707 int hsize) /* I - Hash size (>= 0) */ 708 { 709 return (cupsArrayNew3(f, d, h, hsize, 0, 0)); 710 } 711 712 713 /* 714 * 'cupsArrayNew3()' - Create a new array with hash and/or free function. 715 * 716 * The comparison function ("f") is used to create a sorted array. The function 717 * receives pointers to two elements and the user data pointer ("d") - the user 718 * data pointer argument can safely be omitted when not required so functions 719 * like @code strcmp@ can be used for sorted string arrays. 720 * 721 * The hash function ("h") is used to implement cached lookups with the 722 * specified hash size ("hsize"). 723 * 724 * The copy function ("cf") is used to automatically copy/retain elements when 725 * added or the array is copied. 726 * 727 * The free function ("cf") is used to automatically free/release elements when 728 * removed or the array is deleted. 729 * 730 * @since CUPS 1.5/macOS 10.7@ 731 */ 732 733 cups_array_t * /* O - Array */ 734 cupsArrayNew3(cups_array_func_t f, /* I - Comparison function or @code NULL@ for an unsorted array */ 735 void *d, /* I - User data or @code NULL@ */ 736 cups_ahash_func_t h, /* I - Hash function or @code NULL@ for unhashed lookups */ 737 int hsize, /* I - Hash size (>= 0) */ 738 cups_acopy_func_t cf, /* I - Copy function */ 739 cups_afree_func_t ff) /* I - Free function */ 740 { 741 cups_array_t *a; /* Array */ 742 743 744 /* 745 * Allocate memory for the array... 746 */ 747 748 a = calloc(1, sizeof(cups_array_t)); 749 if (!a) 750 return (NULL); 751 752 a->compare = f; 753 a->data = d; 754 a->current = -1; 755 a->insert = -1; 756 a->num_saved = 0; 757 a->unique = 1; 758 759 if (hsize > 0 && h) 760 { 761 a->hashfunc = h; 762 a->hashsize = hsize; 763 a->hash = malloc((size_t)hsize * sizeof(int)); 764 765 if (!a->hash) 766 { 767 free(a); 768 return (NULL); 769 } 770 771 memset(a->hash, -1, (size_t)hsize * sizeof(int)); 772 } 773 774 a->copyfunc = cf; 775 a->freefunc = ff; 776 777 return (a); 778 } 779 780 781 /* 782 * '_cupsArrayNewStrings()' - Create a new array of comma-delimited strings. 783 * 784 * Note: The array automatically manages copies of the strings passed. If the 785 * string pointer "s" is NULL or the empty string, no strings are added to the 786 * newly created array. 787 */ 788 789 cups_array_t * /* O - Array */ 790 _cupsArrayNewStrings(const char *s, /* I - Delimited strings or NULL */ 791 char delim) /* I - Delimiter character */ 792 { 793 cups_array_t *a; /* Array */ 794 795 796 if ((a = cupsArrayNew3((cups_array_func_t)strcmp, NULL, NULL, 0, 797 (cups_acopy_func_t)_cupsStrAlloc, 798 (cups_afree_func_t)_cupsStrFree)) != NULL) 799 _cupsArrayAddStrings(a, s, delim); 800 801 return (a); 802 } 803 804 805 /* 806 * 'cupsArrayNext()' - Get the next element in the array. 807 * 808 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) + 1)". 809 * 810 * The next element is undefined until you call @link cupsArrayFind@, 811 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@ 812 * to set the current element. 813 * 814 * @since CUPS 1.2/macOS 10.5@ 815 */ 816 817 void * /* O - Next element or @code NULL@ */ 818 cupsArrayNext(cups_array_t *a) /* I - Array */ 819 { 820 /* 821 * Range check input... 822 */ 823 824 if (!a) 825 return (NULL); 826 827 /* 828 * Return the next element... 829 */ 830 831 if (a->current < a->num_elements) 832 a->current ++; 833 834 return (cupsArrayCurrent(a)); 835 } 836 837 838 /* 839 * 'cupsArrayPrev()' - Get the previous element in the array. 840 * 841 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) - 1)". 842 * 843 * The previous element is undefined until you call @link cupsArrayFind@, 844 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@ 845 * to set the current element. 846 * 847 * @since CUPS 1.2/macOS 10.5@ 848 */ 849 850 void * /* O - Previous element or @code NULL@ */ 851 cupsArrayPrev(cups_array_t *a) /* I - Array */ 852 { 853 /* 854 * Range check input... 855 */ 856 857 if (!a) 858 return (NULL); 859 860 /* 861 * Return the previous element... 862 */ 863 864 if (a->current >= 0) 865 a->current --; 866 867 return (cupsArrayCurrent(a)); 868 } 869 870 871 /* 872 * 'cupsArrayRemove()' - Remove an element from the array. 873 * 874 * If more than one element matches "e", only the first matching element is 875 * removed. 876 * 877 * The caller is responsible for freeing the memory used by the 878 * removed element. 879 * 880 * @since CUPS 1.2/macOS 10.5@ 881 */ 882 883 int /* O - 1 on success, 0 on failure */ 884 cupsArrayRemove(cups_array_t *a, /* I - Array */ 885 void *e) /* I - Element */ 886 { 887 ssize_t i, /* Looping var */ 888 current; /* Current element */ 889 int diff; /* Difference */ 890 891 892 /* 893 * Range check input... 894 */ 895 896 if (!a || !e) 897 return (0); 898 899 /* 900 * See if the element is in the array... 901 */ 902 903 if (!a->num_elements) 904 return (0); 905 906 current = cups_array_find(a, e, a->current, &diff); 907 if (diff) 908 return (0); 909 910 /* 911 * Yes, now remove it... 912 */ 913 914 a->num_elements --; 915 916 if (a->freefunc) 917 (a->freefunc)(a->elements[current], a->data); 918 919 if (current < a->num_elements) 920 memmove(a->elements + current, a->elements + current + 1, 921 (size_t)(a->num_elements - current) * sizeof(void *)); 922 923 if (current <= a->current) 924 a->current --; 925 926 if (current < a->insert) 927 a->insert --; 928 else if (current == a->insert) 929 a->insert = -1; 930 931 for (i = 0; i < a->num_saved; i ++) 932 if (current <= a->saved[i]) 933 a->saved[i] --; 934 935 if (a->num_elements <= 1) 936 a->unique = 1; 937 938 return (1); 939 } 940 941 942 /* 943 * 'cupsArrayRestore()' - Reset the current element to the last @link cupsArraySave@. 944 * 945 * @since CUPS 1.2/macOS 10.5@ 946 */ 947 948 void * /* O - New current element */ 949 cupsArrayRestore(cups_array_t *a) /* I - Array */ 950 { 951 if (!a) 952 return (NULL); 953 954 if (a->num_saved <= 0) 955 return (NULL); 956 957 a->num_saved --; 958 a->current = a->saved[a->num_saved]; 959 960 if (a->current >= 0 && a->current < a->num_elements) 961 return (a->elements[a->current]); 962 else 963 return (NULL); 964 } 965 966 967 /* 968 * 'cupsArraySave()' - Mark the current element for a later @link cupsArrayRestore@. 969 * 970 * The current element is undefined until you call @link cupsArrayFind@, 971 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@ 972 * to set the current element. 973 * 974 * The save/restore stack is guaranteed to be at least 32 elements deep. 975 * 976 * @since CUPS 1.2/macOS 10.5@ 977 */ 978 979 int /* O - 1 on success, 0 on failure */ 980 cupsArraySave(cups_array_t *a) /* I - Array */ 981 { 982 if (!a) 983 return (0); 984 985 if (a->num_saved >= _CUPS_MAXSAVE) 986 return (0); 987 988 a->saved[a->num_saved] = a->current; 989 a->num_saved ++; 990 991 return (1); 992 } 993 994 995 /* 996 * 'cupsArrayUserData()' - Return the user data for an array. 997 * 998 * @since CUPS 1.2/macOS 10.5@ 999 */ 1000 1001 void * /* O - User data */ 1002 cupsArrayUserData(cups_array_t *a) /* I - Array */ 1003 { 1004 if (a) 1005 return (a->data); 1006 else 1007 return (NULL); 1008 } 1009 1010 1011 /* 1012 * 'cups_array_add()' - Insert or append an element to the array. 1013 * 1014 * @since CUPS 1.2/macOS 10.5@ 1015 */ 1016 1017 static int /* O - 1 on success, 0 on failure */ 1018 cups_array_add(cups_array_t *a, /* I - Array */ 1019 void *e, /* I - Element to add */ 1020 int insert) /* I - 1 = insert, 0 = append */ 1021 { 1022 int i, /* Looping var */ 1023 current; /* Current element */ 1024 int diff; /* Comparison with current element */ 1025 1026 1027 DEBUG_printf(("7cups_array_add(a=%p, e=%p, insert=%d)", (void *)a, e, insert)); 1028 1029 /* 1030 * Verify we have room for the new element... 1031 */ 1032 1033 if (a->num_elements >= a->alloc_elements) 1034 { 1035 /* 1036 * Allocate additional elements; start with 16 elements, then 1037 * double the size until 1024 elements, then add 1024 elements 1038 * thereafter... 1039 */ 1040 1041 void **temp; /* New array elements */ 1042 int count; /* New allocation count */ 1043 1044 1045 if (a->alloc_elements == 0) 1046 { 1047 count = 16; 1048 temp = malloc((size_t)count * sizeof(void *)); 1049 } 1050 else 1051 { 1052 if (a->alloc_elements < 1024) 1053 count = a->alloc_elements * 2; 1054 else 1055 count = a->alloc_elements + 1024; 1056 1057 temp = realloc(a->elements, (size_t)count * sizeof(void *)); 1058 } 1059 1060 DEBUG_printf(("9cups_array_add: count=" CUPS_LLFMT, CUPS_LLCAST count)); 1061 1062 if (!temp) 1063 { 1064 DEBUG_puts("9cups_array_add: allocation failed, returning 0"); 1065 return (0); 1066 } 1067 1068 a->alloc_elements = count; 1069 a->elements = temp; 1070 } 1071 1072 /* 1073 * Find the insertion point for the new element; if there is no 1074 * compare function or elements, just add it to the beginning or end... 1075 */ 1076 1077 if (!a->num_elements || !a->compare) 1078 { 1079 /* 1080 * No elements or comparison function, insert/append as needed... 1081 */ 1082 1083 if (insert) 1084 current = 0; /* Insert at beginning */ 1085 else 1086 current = a->num_elements; /* Append to the end */ 1087 } 1088 else 1089 { 1090 /* 1091 * Do a binary search for the insertion point... 1092 */ 1093 1094 current = cups_array_find(a, e, a->insert, &diff); 1095 1096 if (diff > 0) 1097 { 1098 /* 1099 * Insert after the current element... 1100 */ 1101 1102 current ++; 1103 } 1104 else if (!diff) 1105 { 1106 /* 1107 * Compared equal, make sure we add to the begining or end of 1108 * the current run of equal elements... 1109 */ 1110 1111 a->unique = 0; 1112 1113 if (insert) 1114 { 1115 /* 1116 * Insert at beginning of run... 1117 */ 1118 1119 while (current > 0 && !(*(a->compare))(e, a->elements[current - 1], 1120 a->data)) 1121 current --; 1122 } 1123 else 1124 { 1125 /* 1126 * Append at end of run... 1127 */ 1128 1129 do 1130 { 1131 current ++; 1132 } 1133 while (current < a->num_elements && 1134 !(*(a->compare))(e, a->elements[current], a->data)); 1135 } 1136 } 1137 } 1138 1139 /* 1140 * Insert or append the element... 1141 */ 1142 1143 if (current < a->num_elements) 1144 { 1145 /* 1146 * Shift other elements to the right... 1147 */ 1148 1149 memmove(a->elements + current + 1, a->elements + current, 1150 (size_t)(a->num_elements - current) * sizeof(void *)); 1151 1152 if (a->current >= current) 1153 a->current ++; 1154 1155 for (i = 0; i < a->num_saved; i ++) 1156 if (a->saved[i] >= current) 1157 a->saved[i] ++; 1158 1159 DEBUG_printf(("9cups_array_add: insert element at index " CUPS_LLFMT, CUPS_LLCAST current)); 1160 } 1161 #ifdef DEBUG 1162 else 1163 DEBUG_printf(("9cups_array_add: append element at " CUPS_LLFMT, CUPS_LLCAST current)); 1164 #endif /* DEBUG */ 1165 1166 if (a->copyfunc) 1167 { 1168 if ((a->elements[current] = (a->copyfunc)(e, a->data)) == NULL) 1169 { 1170 DEBUG_puts("8cups_array_add: Copy function returned NULL, returning 0"); 1171 return (0); 1172 } 1173 } 1174 else 1175 a->elements[current] = e; 1176 1177 a->num_elements ++; 1178 a->insert = current; 1179 1180 #ifdef DEBUG 1181 for (current = 0; current < a->num_elements; current ++) 1182 DEBUG_printf(("9cups_array_add: a->elements[" CUPS_LLFMT "]=%p", CUPS_LLCAST current, a->elements[current])); 1183 #endif /* DEBUG */ 1184 1185 DEBUG_puts("9cups_array_add: returning 1"); 1186 1187 return (1); 1188 } 1189 1190 1191 /* 1192 * 'cups_array_find()' - Find an element in the array. 1193 */ 1194 1195 static int /* O - Index of match */ 1196 cups_array_find(cups_array_t *a, /* I - Array */ 1197 void *e, /* I - Element */ 1198 int prev, /* I - Previous index */ 1199 int *rdiff) /* O - Difference of match */ 1200 { 1201 int left, /* Left side of search */ 1202 right, /* Right side of search */ 1203 current, /* Current element */ 1204 diff; /* Comparison with current element */ 1205 1206 1207 DEBUG_printf(("7cups_array_find(a=%p, e=%p, prev=%d, rdiff=%p)", (void *)a, e, prev, (void *)rdiff)); 1208 1209 if (a->compare) 1210 { 1211 /* 1212 * Do a binary search for the element... 1213 */ 1214 1215 DEBUG_puts("9cups_array_find: binary search"); 1216 1217 if (prev >= 0 && prev < a->num_elements) 1218 { 1219 /* 1220 * Start search on either side of previous... 1221 */ 1222 1223 if ((diff = (*(a->compare))(e, a->elements[prev], a->data)) == 0 || 1224 (diff < 0 && prev == 0) || 1225 (diff > 0 && prev == (a->num_elements - 1))) 1226 { 1227 /* 1228 * Exact or edge match, return it! 1229 */ 1230 1231 DEBUG_printf(("9cups_array_find: Returning %d, diff=%d", prev, diff)); 1232 1233 *rdiff = diff; 1234 1235 return (prev); 1236 } 1237 else if (diff < 0) 1238 { 1239 /* 1240 * Start with previous on right side... 1241 */ 1242 1243 left = 0; 1244 right = prev; 1245 } 1246 else 1247 { 1248 /* 1249 * Start wih previous on left side... 1250 */ 1251 1252 left = prev; 1253 right = a->num_elements - 1; 1254 } 1255 } 1256 else 1257 { 1258 /* 1259 * Start search in the middle... 1260 */ 1261 1262 left = 0; 1263 right = a->num_elements - 1; 1264 } 1265 1266 do 1267 { 1268 current = (left + right) / 2; 1269 diff = (*(a->compare))(e, a->elements[current], a->data); 1270 1271 DEBUG_printf(("9cups_array_find: left=%d, right=%d, current=%d, diff=%d", 1272 left, right, current, diff)); 1273 1274 if (diff == 0) 1275 break; 1276 else if (diff < 0) 1277 right = current; 1278 else 1279 left = current; 1280 } 1281 while ((right - left) > 1); 1282 1283 if (diff != 0) 1284 { 1285 /* 1286 * Check the last 1 or 2 elements... 1287 */ 1288 1289 if ((diff = (*(a->compare))(e, a->elements[left], a->data)) <= 0) 1290 current = left; 1291 else 1292 { 1293 diff = (*(a->compare))(e, a->elements[right], a->data); 1294 current = right; 1295 } 1296 } 1297 } 1298 else 1299 { 1300 /* 1301 * Do a linear pointer search... 1302 */ 1303 1304 DEBUG_puts("9cups_array_find: linear search"); 1305 1306 diff = 1; 1307 1308 for (current = 0; current < a->num_elements; current ++) 1309 if (a->elements[current] == e) 1310 { 1311 diff = 0; 1312 break; 1313 } 1314 } 1315 1316 /* 1317 * Return the closest element and the difference... 1318 */ 1319 1320 DEBUG_printf(("8cups_array_find: Returning %d, diff=%d", current, diff)); 1321 1322 *rdiff = diff; 1323 1324 return (current); 1325 } 1326
