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