2 * "$Id: array.c 7616 2008-05-28 00:34:13Z mike $"
4 * Sorted array routines for CUPS.
6 * Copyright 2007-2010 by Apple Inc.
7 * Copyright 1997-2007 by Easy Software Products.
9 * These coded instructions, statements, and computer programs are the
10 * property of Apple Inc. and are protected by Federal copyright
11 * law. Distribution and use rights are outlined in the file "LICENSE.txt"
12 * which should have been included with this file. If this file is
13 * file is missing or damaged, see the license at "http://www.cups.org/".
15 * This file is subject to the Apple OS-Developed Software exception.
19 * cupsArrayAdd() - Add an element to the array.
20 * cupsArrayClear() - Clear the array.
21 * cupsArrayCount() - Get the number of elements in the array.
22 * cupsArrayCurrent() - Return the current element in the array.
23 * cupsArrayDelete() - Free all memory used by the array.
24 * cupsArrayDup() - Duplicate the array.
25 * cupsArrayFind() - Find an element in the array.
26 * cupsArrayFirst() - Get the first element in the array.
27 * cupsArrayGetIndex() - Get the index of the current element.
28 * cupsArrayGetInsert() - Get the index of the last inserted element.
29 * cupsArrayIndex() - Get the N-th element in the array.
30 * cupsArrayInsert() - Insert an element in the array.
31 * cupsArrayLast() - Get the last element in the array.
32 * cupsArrayNew() - Create a new array.
33 * cupsArrayNew2() - Create a new array with hash.
34 * cupsArrayNew3() - Create a new array with hash and/or free function.
35 * cupsArrayNext() - Get the next element in the array.
36 * cupsArrayPrev() - Get the previous element in the array.
37 * cupsArrayRemove() - Remove an element from the array.
38 * cupsArrayRestore() - Reset the current element to the last @link
40 * cupsArraySave() - Mark the current element for a later @link
42 * cupsArrayUserData() - Return the user data for an array.
43 * cups_array_add() - Insert or append an element to the array...
44 * cups_array_find() - Find an element in the array...
48 * Include necessary headers...
51 #include "string-private.h"
52 #include "debug-private.h"
60 #define _CUPS_MAXSAVE 32 /**** Maximum number of saves ****/
64 * Types and structures...
67 struct _cups_array_s
/**** CUPS array structure ****/
70 * The current implementation uses an insertion sort into an array of
71 * sorted pointers. We leave the array type private/opaque so that we
72 * can change the underlying implementation without affecting the users
76 int num_elements
, /* Number of array elements */
77 alloc_elements
, /* Allocated array elements */
78 current
, /* Current element */
79 insert
, /* Last inserted element */
80 unique
, /* Are all elements unique? */
81 num_saved
, /* Number of saved elements */
84 void **elements
; /* Array elements */
85 cups_array_func_t compare
; /* Element comparison function */
86 void *data
; /* User data passed to compare */
87 cups_ahash_func_t hashfunc
; /* Hash function */
88 int hashsize
, /* Size of hash */
89 *hash
; /* Hash array */
90 cups_acopy_func_t copyfunc
; /* Copy function */
91 cups_afree_func_t freefunc
; /* Free function */
99 static int cups_array_add(cups_array_t
*a
, void *e
, int insert
);
100 static int cups_array_find(cups_array_t
*a
, void *e
, int prev
, int *rdiff
);
104 * 'cupsArrayAdd()' - Add an element to the array.
106 * When adding an element to a sorted array, non-unique elements are
107 * appended at the end of the run of identical elements. For unsorted arrays,
108 * the element is appended to the end of the array.
110 * @since CUPS 1.2/Mac OS X 10.5@
113 int /* O - 1 on success, 0 on failure */
114 cupsArrayAdd(cups_array_t
*a
, /* I - Array */
115 void *e
) /* I - Element */
117 DEBUG_printf(("2cupsArrayAdd(a=%p, e=%p)", a
, e
));
120 * Range check input...
125 DEBUG_puts("3cupsArrayAdd: returning 0");
130 * Append the element...
133 return (cups_array_add(a
, e
, 0));
138 * 'cupsArrayClear()' - Clear the array.
140 * This function is equivalent to removing all elements in the array.
141 * The caller is responsible for freeing the memory used by the
142 * elements themselves.
144 * @since CUPS 1.2/Mac OS X 10.5@
148 cupsArrayClear(cups_array_t
*a
) /* I - Array */
151 * Range check input...
158 * Free the existing elements as needed..
163 int i
; /* Looping var */
164 void **e
; /* Current element */
166 for (i
= a
->num_elements
, e
= a
->elements
; i
> 0; i
--, e
++)
167 (a
->freefunc
)(*e
, a
->data
);
171 * Set the number of elements to 0; we don't actually free the memory
172 * here - that is done in cupsArrayDelete()...
184 * 'cupsArrayCount()' - Get the number of elements in the array.
186 * @since CUPS 1.2/Mac OS X 10.5@
189 int /* O - Number of elements */
190 cupsArrayCount(cups_array_t
*a
) /* I - Array */
193 * Range check input...
200 * Return the number of elements...
203 return (a
->num_elements
);
208 * 'cupsArrayCurrent()' - Return the current element in the array.
210 * The current element is undefined until you call @link cupsArrayFind@,
211 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
213 * @since CUPS 1.2/Mac OS X 10.5@
216 void * /* O - Element */
217 cupsArrayCurrent(cups_array_t
*a
) /* I - Array */
220 * Range check input...
227 * Return the current element...
230 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
231 return (a
->elements
[a
->current
]);
238 * 'cupsArrayDelete()' - Free all memory used by the array.
240 * The caller is responsible for freeing the memory used by the
241 * elements themselves.
243 * @since CUPS 1.2/Mac OS X 10.5@
247 cupsArrayDelete(cups_array_t
*a
) /* I - Array */
250 * Range check input...
257 * Free the elements if we have a free function (otherwise the caller is
258 * responsible for doing the dirty work...)
263 int i
; /* Looping var */
264 void **e
; /* Current element */
266 for (i
= a
->num_elements
, e
= a
->elements
; i
> 0; i
--, e
++)
267 (a
->freefunc
)(*e
, a
->data
);
271 * Free the array of element pointers...
274 if (a
->alloc_elements
)
285 * 'cupsArrayDup()' - Duplicate the array.
287 * @since CUPS 1.2/Mac OS X 10.5@
290 cups_array_t
* /* O - Duplicate array */
291 cupsArrayDup(cups_array_t
*a
) /* I - Array */
293 cups_array_t
*da
; /* Duplicate array */
297 * Range check input...
304 * Allocate memory for the array...
307 da
= calloc(1, sizeof(cups_array_t
));
311 da
->compare
= a
->compare
;
313 da
->current
= a
->current
;
314 da
->insert
= a
->insert
;
315 da
->unique
= a
->unique
;
316 da
->num_saved
= a
->num_saved
;
318 memcpy(da
->saved
, a
->saved
, sizeof(a
->saved
));
323 * Allocate memory for the elements...
326 da
->elements
= malloc(a
->num_elements
* sizeof(void *));
334 * Copy the element pointers...
340 * Use the copy function to make a copy of each element...
343 int i
; /* Looping var */
345 for (i
= 0; i
< a
->num_elements
; i
++)
346 da
->elements
[i
] = (a
->copyfunc
)(a
->elements
[i
], a
->data
);
351 * Just copy raw pointers...
354 memcpy(da
->elements
, a
->elements
, a
->num_elements
* sizeof(void *));
357 da
->num_elements
= a
->num_elements
;
358 da
->alloc_elements
= a
->num_elements
;
362 * Return the new array...
370 * 'cupsArrayFind()' - Find an element in the array.
372 * @since CUPS 1.2/Mac OS X 10.5@
375 void * /* O - Element found or @code NULL@ */
376 cupsArrayFind(cups_array_t
*a
, /* I - Array */
377 void *e
) /* I - Element */
379 int current
, /* Current element */
380 diff
, /* Difference */
381 hash
; /* Hash index */
385 * Range check input...
392 * See if we have any elements...
395 if (!a
->num_elements
)
399 * Yes, look for a match...
404 hash
= (*(a
->hashfunc
))(e
, a
->data
);
406 if (hash
< 0 || hash
>= a
->hashsize
)
408 current
= a
->current
;
413 current
= a
->hash
[hash
];
415 if (current
< 0 || current
>= a
->num_elements
)
416 current
= a
->current
;
421 current
= a
->current
;
425 current
= cups_array_find(a
, e
, current
, &diff
);
429 * Found a match! If the array does not contain unique values, find
430 * the first element that is the same...
433 if (!a
->unique
&& a
->compare
)
436 * The array is not unique, find the first match...
439 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
444 a
->current
= current
;
447 a
->hash
[hash
] = current
;
449 return (a
->elements
[current
]);
465 * 'cupsArrayFirst()' - Get the first element in the array.
467 * @since CUPS 1.2/Mac OS X 10.5@
470 void * /* O - First element or @code NULL@ if the array is empty */
471 cupsArrayFirst(cups_array_t
*a
) /* I - Array */
474 * Range check input...
481 * Return the first element...
486 return (cupsArrayCurrent(a
));
491 * 'cupsArrayGetIndex()' - Get the index of the current element.
493 * The current element is undefined until you call @link cupsArrayFind@,
494 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
496 * @since CUPS 1.3/Mac OS X 10.5@
499 int /* O - Index of the current element, starting at 0 */
500 cupsArrayGetIndex(cups_array_t
*a
) /* I - Array */
510 * 'cupsArrayGetInsert()' - Get the index of the last inserted element.
512 * @since CUPS 1.3/Mac OS X 10.5@
515 int /* O - Index of the last inserted element, starting at 0 */
516 cupsArrayGetInsert(cups_array_t
*a
) /* I - Array */
526 * 'cupsArrayIndex()' - Get the N-th element in the array.
528 * @since CUPS 1.2/Mac OS X 10.5@
531 void * /* O - N-th element or @code NULL@ */
532 cupsArrayIndex(cups_array_t
*a
, /* I - Array */
533 int n
) /* I - Index into array, starting at 0 */
540 return (cupsArrayCurrent(a
));
545 * 'cupsArrayInsert()' - Insert an element in the array.
547 * When inserting an element in a sorted array, non-unique elements are
548 * inserted at the beginning of the run of identical elements. For unsorted
549 * arrays, the element is inserted at the beginning of the array.
551 * @since CUPS 1.2/Mac OS X 10.5@
554 int /* O - 0 on failure, 1 on success */
555 cupsArrayInsert(cups_array_t
*a
, /* I - Array */
556 void *e
) /* I - Element */
558 DEBUG_printf(("2cupsArrayInsert(a=%p, e=%p)", a
, e
));
561 * Range check input...
566 DEBUG_puts("3cupsArrayInsert: returning 0");
571 * Insert the element...
574 return (cups_array_add(a
, e
, 1));
579 * 'cupsArrayLast()' - Get the last element in the array.
581 * @since CUPS 1.2/Mac OS X 10.5@
584 void * /* O - Last element or @code NULL@ if the array is empty */
585 cupsArrayLast(cups_array_t
*a
) /* I - Array */
588 * Range check input...
595 * Return the last element...
598 a
->current
= a
->num_elements
- 1;
600 return (cupsArrayCurrent(a
));
605 * 'cupsArrayNew()' - Create a new array.
607 * The comparison function ("f") is used to create a sorted array. The function
608 * receives pointers to two elements and the user data pointer ("d") - the user
609 * data pointer argument can safely be omitted when not required so functions
610 * like @code strcmp@ can be used for sorted string arrays.
612 * @since CUPS 1.2/Mac OS X 10.5@
615 cups_array_t
* /* O - Array */
616 cupsArrayNew(cups_array_func_t f
, /* I - Comparison function or @code NULL@ for an unsorted array */
617 void *d
) /* I - User data pointer or @code NULL@ */
619 return (cupsArrayNew3(f
, d
, 0, 0, 0, 0));
624 * 'cupsArrayNew2()' - Create a new array with hash.
626 * The comparison function ("f") is used to create a sorted array. The function
627 * receives pointers to two elements and the user data pointer ("d") - the user
628 * data pointer argument can safely be omitted when not required so functions
629 * like @code strcmp@ can be used for sorted string arrays.
631 * The hash function ("h") is used to implement cached lookups with the
632 * specified hash size ("hsize").
634 * @since CUPS 1.3/Mac OS X 10.5@
637 cups_array_t
* /* O - Array */
638 cupsArrayNew2(cups_array_func_t f
, /* I - Comparison function or @code NULL@ for an unsorted array */
639 void *d
, /* I - User data or @code NULL@ */
640 cups_ahash_func_t h
, /* I - Hash function or @code NULL@ for unhashed lookups */
641 int hsize
) /* I - Hash size (>= 0) */
643 return (cupsArrayNew3(f
, d
, h
, hsize
, 0, 0));
648 * 'cupsArrayNew3()' - Create a new array with hash and/or free function.
650 * The comparison function ("f") is used to create a sorted array. The function
651 * receives pointers to two elements and the user data pointer ("d") - the user
652 * data pointer argument can safely be omitted when not required so functions
653 * like @code strcmp@ can be used for sorted string arrays.
655 * The hash function ("h") is used to implement cached lookups with the
656 * specified hash size ("hsize").
658 * The copy function ("cf") is used to automatically copy/retain elements when
659 * added or the array is copied.
661 * The free function ("cf") is used to automatically free/release elements when
662 * removed or the array is deleted.
667 cups_array_t
* /* O - Array */
668 cupsArrayNew3(cups_array_func_t f
, /* I - Comparison function or @code NULL@ for an unsorted array */
669 void *d
, /* I - User data or @code NULL@ */
670 cups_ahash_func_t h
, /* I - Hash function or @code NULL@ for unhashed lookups */
671 int hsize
, /* I - Hash size (>= 0) */
672 cups_acopy_func_t cf
, /* I - Copy function */
673 cups_afree_func_t ff
) /* I - Free function */
675 cups_array_t
*a
; /* Array */
679 * Allocate memory for the array...
682 a
= calloc(1, sizeof(cups_array_t
));
697 a
->hash
= malloc(hsize
* sizeof(int));
705 memset(a
->hash
, -1, hsize
* sizeof(int));
716 * 'cupsArrayNext()' - Get the next element in the array.
718 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) + 1)".
720 * The next element is undefined until you call @link cupsArrayFind@,
721 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
722 * to set the current element.
724 * @since CUPS 1.2/Mac OS X 10.5@
727 void * /* O - Next element or @code NULL@ */
728 cupsArrayNext(cups_array_t
*a
) /* I - Array */
731 * Range check input...
738 * Return the next element...
741 if (a
->current
< a
->num_elements
)
744 return (cupsArrayCurrent(a
));
749 * 'cupsArrayPrev()' - Get the previous element in the array.
751 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) - 1)".
753 * The previous element is undefined until you call @link cupsArrayFind@,
754 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
755 * to set the current element.
757 * @since CUPS 1.2/Mac OS X 10.5@
760 void * /* O - Previous element or @code NULL@ */
761 cupsArrayPrev(cups_array_t
*a
) /* I - Array */
764 * Range check input...
771 * Return the previous element...
777 return (cupsArrayCurrent(a
));
782 * 'cupsArrayRemove()' - Remove an element from the array.
784 * If more than one element matches "e", only the first matching element is
787 * The caller is responsible for freeing the memory used by the
790 * @since CUPS 1.2/Mac OS X 10.5@
793 int /* O - 1 on success, 0 on failure */
794 cupsArrayRemove(cups_array_t
*a
, /* I - Array */
795 void *e
) /* I - Element */
797 int i
, /* Looping var */
798 current
, /* Current element */
799 diff
; /* Difference */
803 * Range check input...
810 * See if the element is in the array...
813 if (!a
->num_elements
)
816 current
= cups_array_find(a
, e
, a
->current
, &diff
);
821 * Yes, now remove it...
827 (a
->freefunc
)(a
->elements
[current
], a
->data
);
829 if (current
< a
->num_elements
)
830 memmove(a
->elements
+ current
, a
->elements
+ current
+ 1,
831 (a
->num_elements
- current
) * sizeof(void *));
833 if (current
<= a
->current
)
836 if (current
< a
->insert
)
838 else if (current
== a
->insert
)
841 for (i
= 0; i
< a
->num_saved
; i
++)
842 if (current
<= a
->saved
[i
])
845 if (a
->num_elements
<= 1)
853 * 'cupsArrayRestore()' - Reset the current element to the last @link cupsArraySave@.
855 * @since CUPS 1.2/Mac OS X 10.5@
858 void * /* O - New current element */
859 cupsArrayRestore(cups_array_t
*a
) /* I - Array */
864 if (a
->num_saved
<= 0)
868 a
->current
= a
->saved
[a
->num_saved
];
870 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
871 return (a
->elements
[a
->current
]);
878 * 'cupsArraySave()' - Mark the current element for a later @link cupsArrayRestore@.
880 * The current element is undefined until you call @link cupsArrayFind@,
881 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
882 * to set the current element.
884 * The save/restore stack is guaranteed to be at least 32 elements deep.
886 * @since CUPS 1.2/Mac OS X 10.5@
889 int /* O - 1 on success, 0 on failure */
890 cupsArraySave(cups_array_t
*a
) /* I - Array */
895 if (a
->num_saved
>= _CUPS_MAXSAVE
)
898 a
->saved
[a
->num_saved
] = a
->current
;
906 * 'cupsArrayUserData()' - Return the user data for an array.
908 * @since CUPS 1.2/Mac OS X 10.5@
911 void * /* O - User data */
912 cupsArrayUserData(cups_array_t
*a
) /* I - Array */
922 * 'cups_array_add()' - Insert or append an element to the array...
924 * @since CUPS 1.2/Mac OS X 10.5@
927 static int /* O - 1 on success, 0 on failure */
928 cups_array_add(cups_array_t
*a
, /* I - Array */
929 void *e
, /* I - Element to add */
930 int insert
) /* I - 1 = insert, 0 = append */
932 int i
, /* Looping var */
933 current
, /* Current element */
934 diff
; /* Comparison with current element */
937 DEBUG_printf(("7cups_array_add(a=%p, e=%p, insert=%d)", a
, e
, insert
));
940 * Verify we have room for the new element...
943 if (a
->num_elements
>= a
->alloc_elements
)
946 * Allocate additional elements; start with 16 elements, then
947 * double the size until 1024 elements, then add 1024 elements
951 void **temp
; /* New array elements */
952 int count
; /* New allocation count */
955 if (a
->alloc_elements
== 0)
958 temp
= malloc(count
* sizeof(void *));
962 if (a
->alloc_elements
< 1024)
963 count
= a
->alloc_elements
* 2;
965 count
= a
->alloc_elements
+ 1024;
967 temp
= realloc(a
->elements
, count
* sizeof(void *));
970 DEBUG_printf(("9cups_array_add: count=%d", count
));
974 DEBUG_puts("9cups_array_add: allocation failed, returning 0");
978 a
->alloc_elements
= count
;
983 * Find the insertion point for the new element; if there is no
984 * compare function or elements, just add it to the beginning or end...
987 if (!a
->num_elements
|| !a
->compare
)
990 * No elements or comparison function, insert/append as needed...
994 current
= 0; /* Insert at beginning */
996 current
= a
->num_elements
; /* Append to the end */
1001 * Do a binary search for the insertion point...
1004 current
= cups_array_find(a
, e
, a
->insert
, &diff
);
1009 * Insert after the current element...
1017 * Compared equal, make sure we add to the begining or end of
1018 * the current run of equal elements...
1026 * Insert at beginning of run...
1029 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
1036 * Append at end of run...
1043 while (current
< a
->num_elements
&&
1044 !(*(a
->compare
))(e
, a
->elements
[current
], a
->data
));
1050 * Insert or append the element...
1053 if (current
< a
->num_elements
)
1056 * Shift other elements to the right...
1059 memmove(a
->elements
+ current
+ 1, a
->elements
+ current
,
1060 (a
->num_elements
- current
) * sizeof(void *));
1062 if (a
->current
>= current
)
1065 for (i
= 0; i
< a
->num_saved
; i
++)
1066 if (a
->saved
[i
] >= current
)
1069 DEBUG_printf(("9cups_array_add: insert element at index %d...", current
));
1073 DEBUG_printf(("9cups_array_add: append element at %d...", current
));
1078 if ((a
->elements
[current
] = (a
->copyfunc
)(e
, a
->data
)) == NULL
)
1080 DEBUG_puts("8cups_array_add: Copy function returned NULL, returning 0");
1085 a
->elements
[current
] = e
;
1088 a
->insert
= current
;
1091 for (current
= 0; current
< a
->num_elements
; current
++)
1092 DEBUG_printf(("9cups_array_add: a->elements[%d]=%p", current
,
1093 a
->elements
[current
]));
1096 DEBUG_puts("9cups_array_add: returning 1");
1103 * 'cups_array_find()' - Find an element in the array...
1106 static int /* O - Index of match */
1107 cups_array_find(cups_array_t
*a
, /* I - Array */
1108 void *e
, /* I - Element */
1109 int prev
, /* I - Previous index */
1110 int *rdiff
) /* O - Difference of match */
1112 int left
, /* Left side of search */
1113 right
, /* Right side of search */
1114 current
, /* Current element */
1115 diff
; /* Comparison with current element */
1118 DEBUG_printf(("7cups_array_find(a=%p, e=%p, prev=%d, rdiff=%p)", a
, e
, prev
,
1124 * Do a binary search for the element...
1127 DEBUG_puts("9cups_array_find: binary search");
1129 if (prev
>= 0 && prev
< a
->num_elements
)
1132 * Start search on either side of previous...
1135 if ((diff
= (*(a
->compare
))(e
, a
->elements
[prev
], a
->data
)) == 0 ||
1136 (diff
< 0 && prev
== 0) ||
1137 (diff
> 0 && prev
== (a
->num_elements
- 1)))
1140 * Exact or edge match, return it!
1143 DEBUG_printf(("9cups_array_find: Returning %d, diff=%d", prev
, diff
));
1152 * Start with previous on right side...
1161 * Start wih previous on left side...
1165 right
= a
->num_elements
- 1;
1171 * Start search in the middle...
1175 right
= a
->num_elements
- 1;
1180 current
= (left
+ right
) / 2;
1181 diff
= (*(a
->compare
))(e
, a
->elements
[current
], a
->data
);
1183 DEBUG_printf(("9cups_array_find: left=%d, right=%d, current=%d, diff=%d",
1184 left
, right
, current
, diff
));
1193 while ((right
- left
) > 1);
1198 * Check the last 1 or 2 elements...
1201 if ((diff
= (*(a
->compare
))(e
, a
->elements
[left
], a
->data
)) <= 0)
1205 diff
= (*(a
->compare
))(e
, a
->elements
[right
], a
->data
);
1213 * Do a linear pointer search...
1216 DEBUG_puts("9cups_array_find: linear search");
1220 for (current
= 0; current
< a
->num_elements
; current
++)
1221 if (a
->elements
[current
] == e
)
1229 * Return the closest element and the difference...
1232 DEBUG_printf(("8cups_array_find: Returning %d, diff=%d", current
, diff
));
1241 * End of "$Id: array.c 7616 2008-05-28 00:34:13Z mike $".