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