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