cups/array.c

   1 /*
   2  * "$Id: array.c 4970 2006-01-24 14:05:45Z mike $"
   3  *
   4  *   Sorted array routines for the Common UNIX Printing System (CUPS).
   5  *
   6  *   Copyright 1997-2006 by Easy Software Products.
   7  *
   8  *   These coded instructions, statements, and computer programs are the
   9  *   property of Easy Software Products and are protected by Federal
  10  *   copyright law.  Distribution and use rights are outlined in the file
  11  *   "LICENSE.txt" which should have been included with this file.  If this
  12  *   file is missing or damaged please contact Easy Software Products
  13  *   at:
  14  *
  15  *       Attn: CUPS Licensing Information
  16  *       Easy Software Products
  17  *       44141 Airport View Drive, Suite 204
  18  *       Hollywood, Maryland 20636 USA
  19  *
  20  *       Voice: (301) 373-9600
  21  *       EMail: cups-info@cups.org
  22  *         WWW: http://www.cups.org
  23  *
  24  *   This file is subject to the Apple OS-Developed Software exception.
  25  *
  26  * Contents:
  27  *
  28  *   cupsArrayAdd()     - Add an element to the array.
  29  *   cupsArrayClear()   - Clear the array.
  30  *   cupsArrayCount()   - Get the number of elements in the array.
  31  *   cupsArrayCurrent() - Return the current element in the array.
  32  *   cupsArrayDelete()  - Free all memory used by the array.
  33  *   cupsArrayDup()     - Duplicate the array.
  34  *   cupsArrayFind()    - Find an element in the array.
  35  *   cupsArrayFirst()   - Get the first element in the array.
  36  *   cupsArrayIndex()   - Get the N-th element in the array.
  37  *   cupsArrayInsert()  - Insert an element in the array.
  38  *   cupsArrayLast()    - Get the last element in the array.
  39  *   cupsArrayNew()     - Create a new array.
  40  *   cupsArrayNext()    - Get the next element in the array.
  41  *   cupsArrayPrev()    - Get the previous element in the array.
  42  *   cupsArrayRemove()  - Remove an element from the array.
  43  *   cupsArrayRestore() - Reset the current element to the last cupsArraySave.
  44  *   cupsArraySave()    - Mark the current element for a later cupsArrayRestore.
  45  *   cups_find()        - Find an element in the array...
  46  */
  47
  48 /*
  49  * Include necessary headers...
  50  */
  51
  52 #include "array.h"
  53 #include "string.h"
  54 #include "debug.h"
  55
  56
  57 /*
  58  * Limits...
  59  */
  60
  61 #define _CUPS_MAXSAVE   32              /**** Maximum number of saves ****/
  62
  63
  64 /*
  65  * Types and structures...
  66  */
  67
  68 struct _cups_array_s                    /**** CUPS array structure ****/
  69 {
  70  /*
  71   * The current implementation uses an insertion sort into an array of
  72   * sorted pointers.  We leave the array type private/opaque so that we
  73   * can change the underlying implementation without affecting the users
  74   * of this API.
  75   */
  76
  77   int                   num_elements,   /* Number of array elements */
  78                         alloc_elements, /* Allocated array elements */
  79                         current,        /* Current element */
  80                         insert,         /* Last inserted element */
  81                         num_saved,      /* Number of saved elements */
  82                         saved[_CUPS_MAXSAVE];
  83                                         /* Saved elements */
  84   void                  **elements;     /* Array elements */
  85   cups_array_func_t     compare;        /* Element comparison function */
  86   void                  *data;          /* User data passed to compare */
  87 };
  88
  89
  90 /*
  91  * Local functions...
  92  */
  93
  94 static int      cups_find(cups_array_t *a, void *e, int prev, int *rdiff);
  95
  96
  97 /*
  98  * 'cupsArrayAdd()' - Add an element to the array.
  99  */
 100
 101 int                                     /* O - 1 on success, 0 on failure */
 102 cupsArrayAdd(cups_array_t *a,           /* I - Array */
 103              void         *e)           /* I - Element */
 104 {
 105   int   i,                              /* Looping var */
 106         current,                        /* Current element */
 107         diff;                           /* Comparison with current element */
 108
 109
 110   DEBUG_printf(("cupsArrayAdd(a=%p, e=%p)\n", a, e));
 111
 112  /*
 113   * Range check input...
 114   */
 115
 116   if (!a || !e)
 117   {
 118     DEBUG_puts("cupsArrayAdd: returning 0");
 119     return (0);
 120   }
 121
 122  /*
 123   * Verify we have room for the new element...
 124   */
 125
 126   if (a->num_elements >= a->alloc_elements)
 127   {
 128    /*
 129     * Allocate additional elements; start with 16 elements, then
 130     * double the size until 1024 elements, then add 1024 elements
 131     * thereafter...
 132     */
 133
 134     void        **temp;                 /* New array elements */
 135     int         count;                  /* New allocation count */
 136
 137
 138     if (a->alloc_elements == 0)
 139     {
 140       count = 16;
 141       temp  = malloc(count * sizeof(void *));
 142     }
 143     else
 144     {
 145       if (a->alloc_elements < 1024)
 146         count = a->alloc_elements * 2;
 147       else
 148         count = a->alloc_elements + 1024;
 149
 150       temp = realloc(a->elements, count * sizeof(void *));
 151     }
 152
 153     DEBUG_printf(("cupsArrayAdd: count=%d\n", count));
 154
 155     if (!temp)
 156     {
 157       DEBUG_puts("cupsAddAdd: allocation failed, returning 0");
 158       return (0);
 159     }
 160
 161     a->alloc_elements = count;
 162     a->elements       = temp;
 163   }
 164
 165  /*
 166   * Find the insertion point for the new element; if there is no
 167   * compare function or elements, just add it to the end...
 168   */
 169
 170   if (!a->num_elements || !a->compare)
 171   {
 172    /*
 173     * Append to the end...
 174     */
 175
 176     current = a->num_elements;
 177   }
 178   else
 179   {
 180    /*
 181     * Do a binary search for the insertion point...
 182     */
 183
 184     current = cups_find(a, e, a->insert, &diff);
 185
 186     if (diff > 0)
 187       current ++;
 188   }
 189
 190  /*
 191   * Insert or append the element...
 192   */
 193
 194   if (current < a->num_elements)
 195   {
 196    /*
 197     * Shift other elements to the right...
 198     */
 199
 200     memmove(a->elements + current + 1, a->elements + current,
 201             (a->num_elements - current) * sizeof(void *));
 202
 203     if (a->current >= current)
 204       a->current ++;
 205
 206     for (i = 0; i < a->num_saved; i ++)
 207       if (a->saved[i] >= current)
 208         a->saved[i] ++;
 209
 210     DEBUG_printf(("cupsArrayAdd: insert element at index %d...\n", current));
 211   }
 212 #ifdef DEBUG
 213   else
 214     printf("cupsArrayAdd: append element at %d...\n", current);
 215 #endif /* DEBUG */
 216
 217   a->elements[current] = e;
 218   a->num_elements ++;
 219   a->insert = current;
 220
 221 #ifdef DEBUG
 222   for (current = 0; current < a->num_elements; current ++)
 223     printf("cupsArrayAdd: a->elements[%d]=%p\n", current, a->elements[current]);
 224 #endif /* DEBUG */
 225
 226   DEBUG_puts("cupsArrayAdd: returning 1");
 227
 228   return (1);
 229 }
 230
 231
 232 /*
 233  * 'cupsArrayClear()' - Clear the array.
 234  */
 235
 236 void
 237 cupsArrayClear(cups_array_t *a)         /* I - Array */
 238 {
 239  /*
 240   * Range check input...
 241   */
 242
 243   if (!a)
 244     return;
 245
 246  /*
 247   * Set the number of elements to 0; we don't actually free the memory
 248   * here - that is done in cupsArrayDelete()...
 249   */
 250
 251   a->num_elements = 0;
 252   a->current      = -1;
 253   a->insert       = -1;
 254   a->num_saved    = 0;
 255 }
 256
 257
 258 /*
 259  * 'cupsArrayCount()' - Get the number of elements in the array.
 260  */
 261
 262 int                                     /* O - Number of elements */
 263 cupsArrayCount(cups_array_t *a)         /* I - Array */
 264 {
 265  /*
 266   * Range check input...
 267   */
 268
 269   if (!a)
 270     return (0);
 271
 272  /*
 273   * Return the number of elements...
 274   */
 275
 276   return (a->num_elements);
 277 }
 278
 279
 280 /*
 281  * 'cupsArrayCurrent()' - Return the current element in the array.
 282  */
 283
 284 void *                                  /* O - Element */
 285 cupsArrayCurrent(cups_array_t *a)       /* I - Array */
 286 {
 287  /*
 288   * Range check input...
 289   */
 290
 291   if (!a)
 292     return (NULL);
 293
 294  /*
 295   * Return the current element...
 296   */
 297
 298   if (a->current >= 0 && a->current < a->num_elements)
 299     return (a->elements[a->current]);
 300   else
 301     return (NULL);
 302 }
 303
 304
 305 /*
 306  * 'cupsArrayDelete()' - Free all memory used by the array.
 307  */
 308
 309 void
 310 cupsArrayDelete(cups_array_t *a)        /* I - Array */
 311 {
 312  /*
 313   * Range check input...
 314   */
 315
 316   if (!a)
 317     return;
 318
 319  /*
 320   * Free the array of element pointers - the caller is responsible
 321   * for freeing the elements themselves...
 322   */
 323
 324   if (a->alloc_elements)
 325     free(a->elements);
 326
 327   free(a);
 328 }
 329
 330
 331 /*
 332  * 'cupsArrayDup()' - Duplicate the array.
 333  */
 334
 335 cups_array_t *                          /* O - Duplicate array */
 336 cupsArrayDup(cups_array_t *a)           /* I - Array */
 337 {
 338   cups_array_t  *da;                    /* Duplicate array */
 339
 340
 341  /*
 342   * Range check input...
 343   */
 344
 345   if (!a)
 346     return (NULL);
 347
 348  /*
 349   * Allocate memory for the array...
 350   */
 351
 352   da = calloc(1, sizeof(cups_array_t));
 353   if (!da)
 354     return (NULL);
 355
 356   da->compare   = a->compare;
 357   da->data      = a->data;
 358   da->current   = a->current;
 359   da->insert    = a->insert;
 360   da->num_saved = a->num_saved;
 361
 362   memcpy(da->saved, a->saved, sizeof(a->saved));
 363
 364   if (a->num_elements)
 365   {
 366    /*
 367     * Allocate memory for the elements...
 368     */
 369
 370     da->elements = malloc(a->num_elements * sizeof(void *));
 371     if (!da->elements)
 372     {
 373       free(da);
 374       return (NULL);
 375     }
 376
 377    /*
 378     * Copy the element pointers...
 379     */
 380
 381     memcpy(da->elements, a->elements, a->num_elements * sizeof(void *));
 382     da->num_elements   = a->num_elements;
 383     da->alloc_elements = a->num_elements;
 384   }
 385
 386  /*
 387   * Return the new array...
 388   */
 389
 390   return (da);
 391 }
 392
 393
 394 /*
 395  * 'cupsArrayFind()' - Find an element in the array.
 396  */
 397
 398 void *                                  /* O - Element found or NULL */
 399 cupsArrayFind(cups_array_t *a,          /* I - Array */
 400               void         *e)          /* I - Element */
 401 {
 402   int   current,                        /* Current element */
 403         diff;                           /* Difference */
 404
 405
 406  /*
 407   * Range check input...
 408   */
 409
 410   if (!a || !e)
 411     return (NULL);
 412
 413  /*
 414   * See if we have any elements...
 415   */
 416
 417   if (!a->num_elements)
 418     return (NULL);
 419
 420  /*
 421   * Yes, look for a match...
 422   */
 423
 424   current = cups_find(a, e, a->current, &diff);
 425   if (!diff)
 426   {
 427    /*
 428     * Found a match...
 429     */
 430
 431     a->current = current;
 432
 433     return (a->elements[current]);
 434   }
 435   else
 436   {
 437    /*
 438     * No match...
 439     */
 440
 441     a->current = -1;
 442
 443     return (NULL);
 444   }
 445 }
 446
 447
 448 /*
 449  * 'cupsArrayFirst()' - Get the first element in the array.
 450  */
 451
 452 void *                                  /* O - First element or NULL */
 453 cupsArrayFirst(cups_array_t *a)         /* I - Array */
 454 {
 455  /*
 456   * Range check input...
 457   */
 458
 459   if (!a)
 460     return (NULL);
 461
 462  /*
 463   * Return the first element...
 464   */
 465
 466   a->current = 0;
 467
 468   return (cupsArrayCurrent(a));
 469 }
 470
 471
 472 /*
 473  * 'cupsArrayIndex()' - Get the N-th element in the array.
 474  */
 475
 476 void *                                  /* O - N-th element or NULL */
 477 cupsArrayIndex(cups_array_t *a,         /* I - Array */
 478                int          n)          /* I - Index into array, starting at 0 */
 479 {
 480   if (!a)
 481     return (NULL);
 482
 483   a->current = n;
 484
 485   return (cupsArrayCurrent(a));
 486 }
 487
 488
 489 /*
 490  * 'cupsArrayInsert()' - Insert an element in the array.
 491  *
 492  * When inserting an element in a sorted array, this function works
 493  * just like cupsArrayAdd().  For unsorted arrays, the element is
 494  * inserted at the beginning of the array.
 495  */
 496
 497 int                                     /* O - 0 on failure, 1 on success */
 498 cupsArrayInsert(cups_array_t *a,        /* I - Array */
 499                 void         *e)        /* I - Element */
 500 {
 501   int   i;                              /* Looping var */
 502
 503
 504   DEBUG_printf(("cupsArrayInsert(a=%p, e=%p)\n", a, e));
 505
 506  /*
 507   * Range check input...
 508   */
 509
 510   if (!a || !e)
 511   {
 512     DEBUG_puts("cupsArrayInsert: returning 0");
 513     return (0);
 514   }
 515
 516  /*
 517   * Inserting into a sorted array is the same as adding...
 518   */
 519
 520   if (a->compare)
 521     return (cupsArrayAdd(a, e));
 522
 523  /*
 524   * Verify we have room for the new element...
 525   */
 526
 527   if (a->num_elements >= a->alloc_elements)
 528   {
 529    /*
 530     * Allocate additional elements; start with 16 elements, then
 531     * double the size until 1024 elements, then add 1024 elements
 532     * thereafter...
 533     */
 534
 535     void        **temp;                 /* New array elements */
 536     int         count;                  /* New allocation count */
 537
 538
 539     if (a->alloc_elements == 0)
 540     {
 541       count = 16;
 542       temp  = malloc(count * sizeof(void *));
 543     }
 544     else
 545     {
 546       if (a->alloc_elements < 1024)
 547         count = a->alloc_elements * 2;
 548       else
 549         count = a->alloc_elements + 1024;
 550
 551       temp = realloc(a->elements, count * sizeof(void *));
 552     }
 553
 554     DEBUG_printf(("cupsArrayInsert: count=%d\n", count));
 555
 556     if (!temp)
 557     {
 558       DEBUG_puts("cupsAddInsert: allocation failed, returning 0");
 559       return (0);
 560     }
 561
 562     a->alloc_elements = count;
 563     a->elements       = temp;
 564   }
 565
 566  /*
 567   * Insert the element...
 568   */
 569
 570   memmove(a->elements + 1, a->elements, a->num_elements * sizeof(void *));
 571
 572   if (a->current >= 0)
 573     a->current ++;
 574
 575   for (i = 0; i < a->num_saved; i ++)
 576     if (a->saved[i] >= 0)
 577       a->saved[i] ++;
 578
 579   a->elements[0] = e;
 580   a->num_elements ++;
 581   a->insert = 0;
 582
 583 #ifdef DEBUG
 584   for (i = 0; i < a->num_elements; i ++)
 585     printf("cupsArrayInsert: a->elements[%d]=%p\n", i, a->elements[i]);
 586 #endif /* DEBUG */
 587
 588   DEBUG_puts("cupsArrayInsert: returning 1");
 589
 590   return (1);
 591 }
 592
 593
 594 /*
 595  * 'cupsArrayLast()' - Get the last element in the array.
 596  */
 597
 598 void *                                  /* O - Last element or NULL */
 599 cupsArrayLast(cups_array_t *a)          /* I - Array */
 600 {
 601  /*
 602   * Range check input...
 603   */
 604
 605   if (!a)
 606     return (NULL);
 607
 608  /*
 609   * Return the last element...
 610   */
 611
 612   a->current = a->num_elements - 1;
 613
 614   return (cupsArrayCurrent(a));
 615 }
 616
 617
 618 /*
 619  * 'cupsArrayNew()' - Create a new array.
 620  */
 621
 622 cups_array_t *                          /* O - Array */
 623 cupsArrayNew(cups_array_func_t f,       /* I - Comparison function */
 624              void              *d)      /* I - User data */
 625 {
 626   cups_array_t  *a;                     /* Array  */
 627
 628
 629  /*
 630   * Allocate memory for the array...
 631   */
 632
 633   a = calloc(1, sizeof(cups_array_t));
 634   if (!a)
 635     return (NULL);
 636
 637   a->compare   = f;
 638   a->data      = d;
 639   a->current   = -1;
 640   a->insert    = -1;
 641   a->num_saved = 0;
 642
 643   return (a);
 644 }
 645
 646
 647 /*
 648  * 'cupsArrayNext()' - Get the next element in the array.
 649  */
 650
 651 void *                                  /* O - Next element or NULL */
 652 cupsArrayNext(cups_array_t *a)          /* I - Array */
 653 {
 654  /*
 655   * Range check input...
 656   */
 657
 658   if (!a)
 659     return (NULL);
 660
 661  /*
 662   * Return the next element...
 663   */
 664
 665   if (a->current < a->num_elements)
 666     a->current ++;
 667
 668   return (cupsArrayCurrent(a));
 669 }
 670
 671
 672 /*
 673  * 'cupsArrayPrev()' - Get the previous element in the array.
 674  */
 675
 676 void *                                  /* O - Previous element or NULL */
 677 cupsArrayPrev(cups_array_t *a)          /* I - Array */
 678 {
 679  /*
 680   * Range check input...
 681   */
 682
 683   if (!a)
 684     return (NULL);
 685
 686  /*
 687   * Return the previous element...
 688   */
 689
 690   if (a->current >= 0)
 691     a->current --;
 692
 693   return (cupsArrayCurrent(a));
 694 }
 695
 696
 697 /*
 698  * 'cupsArrayRemove()' - Remove an element from the array.
 699  */
 700
 701 int                                     /* O - 1 on success, 0 on failure */
 702 cupsArrayRemove(cups_array_t *a,        /* I - Array */
 703                 void         *e)        /* I - Element */
 704 {
 705   int   i,                              /* Looping var */
 706         current,                        /* Current element */
 707         diff;                           /* Difference */
 708
 709
 710  /*
 711   * Range check input...
 712   */
 713
 714   if (!a || !e)
 715     return (0);
 716
 717  /*
 718   * See if the element is in the array...
 719   */
 720
 721   if (!a->num_elements)
 722     return (0);
 723
 724   current = cups_find(a, e, a->current, &diff);
 725   if (diff)
 726     return (0);
 727
 728  /*
 729   * Yes, now remove it...
 730   */
 731
 732   a->num_elements --;
 733
 734   if (current < a->num_elements)
 735     memmove(a->elements + current, a->elements + current + 1,
 736             (a->num_elements - current) * sizeof(void *));
 737
 738   if (current <= a->current)
 739     a->current --;
 740
 741   if (current <= a->insert)
 742     a->insert --;
 743
 744   for (i = 0; i < a->num_saved; i ++)
 745     if (current <= a->saved[i])
 746       a->saved[i] --;
 747
 748   return (1);
 749 }
 750
 751
 752 /*
 753  * 'cupsArrayRestore()' - Reset the current element to the last cupsArraySave.
 754  */
 755
 756 void *                                  /* O - New current element */
 757 cupsArrayRestore(cups_array_t *a)       /* I - Array */
 758 {
 759   if (!a)
 760     return (NULL);
 761
 762   if (a->num_saved <= 0)
 763     return (NULL);
 764
 765   a->num_saved --;
 766   a->current = a->saved[a->num_saved];
 767
 768   if (a->current >= 0 && a->current < a->num_elements)
 769     return (a->elements[a->current]);
 770   else
 771     return (NULL);
 772 }
 773
 774
 775 /*
 776  * 'cupsArraySave()' - Mark the current element for a later cupsArrayRestore.
 777  *
 778  * The save/restore stack is guaranteed to be at least 32 elements deep.
 779  */
 780
 781 int                                     /* O - 1 on success, 0 on failure */
 782 cupsArraySave(cups_array_t *a)          /* I - Array */
 783 {
 784   if (!a)
 785     return (0);
 786
 787   if (a->num_saved >= _CUPS_MAXSAVE)
 788     return (0);
 789
 790   a->saved[a->num_saved] = a->current;
 791   a->num_saved ++;
 792
 793   return (1);
 794 }
 795
 796
 797 /*
 798  * 'cups_find()' - Find an element in the array...
 799  */
 800
 801 static int                              /* O - Index of match */
 802 cups_find(cups_array_t *a,              /* I - Array */
 803           void         *e,              /* I - Element */
 804           int          prev,            /* I - Previous index */
 805           int          *rdiff)          /* O - Difference of match */
 806 {
 807   int   left,                           /* Left side of search */
 808         right,                          /* Right side of search */
 809         current,                        /* Current element */
 810         diff;                           /* Comparison with current element */
 811
 812
 813   DEBUG_printf(("cups_find(a=%p, e=%p, prev=%d, rdiff=%p)\n", a, e, prev,
 814                 rdiff));
 815
 816   if (a->compare)
 817   {
 818    /*
 819     * Do a binary search for the element...
 820     */
 821
 822     DEBUG_puts("cups_find: binary search");
 823
 824     if (prev >= 0 && prev < a->num_elements)
 825     {
 826      /*
 827       * Start search on either side of previous...
 828       */
 829
 830       if ((diff = (*(a->compare))(e, a->elements[prev], a->data)) == 0 ||
 831           (diff < 0 && prev == 0) ||
 832           (diff > 0 && prev == (a->num_elements - 1)))
 833       {
 834        /*
 835         * Exact or edge match, return it!
 836         */
 837
 838         DEBUG_printf(("cups_find: Returning %d, diff=%d\n", prev, diff));
 839
 840         *rdiff = diff;
 841
 842         return (prev);
 843       }
 844       else if (diff < 0)
 845       {
 846        /*
 847         * Start with previous on right side...
 848         */
 849
 850         left  = 0;
 851         right = prev;
 852       }
 853       else
 854       {
 855        /*
 856         * Start wih previous on left side...
 857         */
 858
 859         left  = prev;
 860         right = a->num_elements - 1;
 861       }
 862     }
 863     else
 864     {
 865      /*
 866       * Start search in the middle...
 867       */
 868
 869       left  = 0;
 870       right = a->num_elements - 1;
 871     }
 872
 873     do
 874     {
 875       current = (left + right) / 2;
 876       diff    = (*(a->compare))(e, a->elements[current], a->data);
 877
 878       DEBUG_printf(("cups_find: left=%d, right=%d, current=%d, diff=%d\n",
 879                     left, right, current, diff));
 880
 881       if (diff == 0)
 882         break;
 883       else if (diff < 0)
 884         right = current;
 885       else
 886         left = current;
 887     }
 888     while ((right - left) > 1);
 889
 890     if (diff != 0)
 891     {
 892      /*
 893       * Check the last 1 or 2 elements...
 894       */
 895
 896       if ((diff = (*(a->compare))(e, a->elements[left], a->data)) <= 0)
 897         current = left;
 898       else
 899       {
 900         diff    = (*(a->compare))(e, a->elements[right], a->data);
 901         current = right;
 902       }
 903     }
 904   }
 905   else
 906   {
 907    /*
 908     * Do a linear pointer search...
 909     */
 910
 911     DEBUG_puts("cups_find: linear search");
 912
 913     diff = 0;
 914
 915     for (current = 0; current < a->num_elements; current ++)
 916       if (a->elements[current] == e)
 917         break;
 918   }
 919
 920  /*
 921   * Return the closest element and the difference...
 922   */
 923
 924   DEBUG_printf(("cups_find: Returning %d, diff=%d\n", current, diff));
 925
 926   *rdiff = diff;
 927
 928   return (current);
 929 }
 930
 931
 932 /*
 933  * End of "$Id: array.c 4970 2006-01-24 14:05:45Z mike $".
 934  */