cups/array.c

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