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