cups/array.c

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