cups/array.c

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