cups/array.c

   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 }