cups/array.c

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