4 * Sorted array routines for CUPS.
6 * Copyright 2007-2012 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 * _cupsArrayAddStrings() - Add zero or more comma-delimited strings to an
22 * cupsArrayClear() - Clear the array.
23 * cupsArrayCount() - Get the number of elements in the array.
24 * cupsArrayCurrent() - Return the current element in the array.
25 * cupsArrayDelete() - Free all memory used by the array.
26 * cupsArrayDup() - Duplicate the array.
27 * cupsArrayFind() - Find an element in the array.
28 * cupsArrayFirst() - Get the first element in the array.
29 * cupsArrayGetIndex() - Get the index of the current element.
30 * cupsArrayGetInsert() - Get the index of the last inserted element.
31 * cupsArrayIndex() - Get the N-th element in the array.
32 * cupsArrayInsert() - Insert an element in the array.
33 * cupsArrayLast() - Get the last element in the array.
34 * cupsArrayNew() - Create a new array.
35 * cupsArrayNew2() - Create a new array with hash.
36 * cupsArrayNew3() - Create a new array with hash and/or free function.
37 * _cupsArrayNewStrings() - Create a new array of comma-delimited strings.
38 * cupsArrayNext() - Get the next element in the array.
39 * cupsArrayPrev() - Get the previous element in the array.
40 * cupsArrayRemove() - Remove an element from the array.
41 * cupsArrayRestore() - Reset the current element to the last @link
43 * cupsArraySave() - Mark the current element for a later @link
45 * cupsArrayUserData() - Return the user data for an array.
46 * cups_array_add() - Insert or append an element to the array.
47 * cups_array_find() - Find an element in the array.
51 * Include necessary headers...
54 #include "string-private.h"
55 #include "debug-private.h"
56 #include "array-private.h"
63 #define _CUPS_MAXSAVE 32 /**** Maximum number of saves ****/
67 * Types and structures...
70 struct _cups_array_s
/**** CUPS array structure ****/
73 * The current implementation uses an insertion sort into an array of
74 * sorted pointers. We leave the array type private/opaque so that we
75 * can change the underlying implementation without affecting the users
79 int num_elements
, /* Number of array elements */
80 alloc_elements
, /* Allocated array elements */
81 current
, /* Current element */
82 insert
, /* Last inserted element */
83 unique
, /* Are all elements unique? */
84 num_saved
, /* Number of saved elements */
87 void **elements
; /* Array elements */
88 cups_array_func_t compare
; /* Element comparison function */
89 void *data
; /* User data passed to compare */
90 cups_ahash_func_t hashfunc
; /* Hash function */
91 int hashsize
, /* Size of hash */
92 *hash
; /* Hash array */
93 cups_acopy_func_t copyfunc
; /* Copy function */
94 cups_afree_func_t freefunc
; /* Free function */
102 static int cups_array_add(cups_array_t
*a
, void *e
, int insert
);
103 static int cups_array_find(cups_array_t
*a
, void *e
, int prev
, int *rdiff
);
107 * 'cupsArrayAdd()' - Add an element to the array.
109 * When adding an element to a sorted array, non-unique elements are
110 * appended at the end of the run of identical elements. For unsorted arrays,
111 * the element is appended to the end of the array.
113 * @since CUPS 1.2/OS X 10.5@
116 int /* O - 1 on success, 0 on failure */
117 cupsArrayAdd(cups_array_t
*a
, /* I - Array */
118 void *e
) /* I - Element */
120 DEBUG_printf(("2cupsArrayAdd(a=%p, e=%p)", a
, e
));
123 * Range check input...
128 DEBUG_puts("3cupsArrayAdd: returning 0");
133 * Append the element...
136 return (cups_array_add(a
, e
, 0));
141 * '_cupsArrayAddStrings()' - Add zero or more delimited strings to an array.
143 * Note: The array MUST be created using the @link _cupsArrayNewStrings@
144 * function. Duplicate strings are NOT added. If the string pointer "s" is NULL
145 * or the empty string, no strings are added to the array.
148 int /* O - 1 on success, 0 on failure */
149 _cupsArrayAddStrings(cups_array_t
*a
, /* I - Array */
150 const char *s
, /* I - Delimited strings or NULL */
151 char delim
)/* I - Delimiter character */
153 char *buffer
, /* Copy of string */
154 *start
, /* Start of string */
155 *end
; /* End of string */
156 int status
= 1; /* Status of add */
159 DEBUG_printf(("_cupsArrayAddStrings(a=%p, s=\"%s\", delim='%c')", a
, s
,
164 DEBUG_puts("1_cupsArrayAddStrings: Returning 0");
171 * Skip leading whitespace...
174 DEBUG_puts("1_cupsArrayAddStrings: Skipping leading whitespace.");
176 while (*s
&& isspace(*s
& 255))
179 DEBUG_printf(("1_cupsArrayAddStrings: Remaining string \"%s\".", s
));
182 if (!strchr(s
, delim
) &&
183 (delim
!= ' ' || (!strchr(s
, '\t') && !strchr(s
, '\n'))))
186 * String doesn't contain a delimiter, so add it as a single value...
189 DEBUG_puts("1_cupsArrayAddStrings: No delimiter seen, adding a single "
192 if (!cupsArrayFind(a
, (void *)s
))
193 status
= cupsArrayAdd(a
, (void *)s
);
195 else if ((buffer
= strdup(s
)) == NULL
)
197 DEBUG_puts("1_cupsArrayAddStrings: Unable to duplicate string.");
202 for (start
= end
= buffer
; *end
; start
= end
)
205 * Find the end of the current delimited string and see if we need to add
211 while (*end
&& !isspace(*end
& 255))
213 while (*end
&& isspace(*end
& 255))
216 else if ((end
= strchr(start
, delim
)) != NULL
)
219 end
= start
+ strlen(start
);
221 DEBUG_printf(("1_cupsArrayAddStrings: Adding \"%s\", end=\"%s\"", start
,
224 if (!cupsArrayFind(a
, start
))
225 status
&= cupsArrayAdd(a
, start
);
231 DEBUG_printf(("1_cupsArrayAddStrings: Returning %d.", status
));
238 * 'cupsArrayClear()' - Clear the array.
240 * This function is equivalent to removing all elements in the array.
241 * The caller is responsible for freeing the memory used by the
242 * elements themselves.
244 * @since CUPS 1.2/OS X 10.5@
248 cupsArrayClear(cups_array_t
*a
) /* I - Array */
251 * Range check input...
258 * Free the existing elements as needed..
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 * Set the number of elements to 0; we don't actually free the memory
272 * here - that is done in cupsArrayDelete()...
284 * 'cupsArrayCount()' - Get the number of elements in the array.
286 * @since CUPS 1.2/OS X 10.5@
289 int /* O - Number of elements */
290 cupsArrayCount(cups_array_t
*a
) /* I - Array */
293 * Range check input...
300 * Return the number of elements...
303 return (a
->num_elements
);
308 * 'cupsArrayCurrent()' - Return the current element in the array.
310 * The current element is undefined until you call @link cupsArrayFind@,
311 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
313 * @since CUPS 1.2/OS X 10.5@
316 void * /* O - Element */
317 cupsArrayCurrent(cups_array_t
*a
) /* I - Array */
320 * Range check input...
327 * Return the current element...
330 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
331 return (a
->elements
[a
->current
]);
338 * 'cupsArrayDelete()' - Free all memory used by the array.
340 * The caller is responsible for freeing the memory used by the
341 * elements themselves.
343 * @since CUPS 1.2/OS X 10.5@
347 cupsArrayDelete(cups_array_t
*a
) /* I - Array */
350 * Range check input...
357 * Free the elements if we have a free function (otherwise the caller is
358 * responsible for doing the dirty work...)
363 int i
; /* Looping var */
364 void **e
; /* Current element */
366 for (i
= a
->num_elements
, e
= a
->elements
; i
> 0; i
--, e
++)
367 (a
->freefunc
)(*e
, a
->data
);
371 * Free the array of element pointers...
374 if (a
->alloc_elements
)
385 * 'cupsArrayDup()' - Duplicate the array.
387 * @since CUPS 1.2/OS X 10.5@
390 cups_array_t
* /* O - Duplicate array */
391 cupsArrayDup(cups_array_t
*a
) /* I - Array */
393 cups_array_t
*da
; /* Duplicate array */
397 * Range check input...
404 * Allocate memory for the array...
407 da
= calloc(1, sizeof(cups_array_t
));
411 da
->compare
= a
->compare
;
413 da
->current
= a
->current
;
414 da
->insert
= a
->insert
;
415 da
->unique
= a
->unique
;
416 da
->num_saved
= a
->num_saved
;
418 memcpy(da
->saved
, a
->saved
, sizeof(a
->saved
));
423 * Allocate memory for the elements...
426 da
->elements
= malloc(a
->num_elements
* sizeof(void *));
434 * Copy the element pointers...
440 * Use the copy function to make a copy of each element...
443 int i
; /* Looping var */
445 for (i
= 0; i
< a
->num_elements
; i
++)
446 da
->elements
[i
] = (a
->copyfunc
)(a
->elements
[i
], a
->data
);
451 * Just copy raw pointers...
454 memcpy(da
->elements
, a
->elements
, a
->num_elements
* sizeof(void *));
457 da
->num_elements
= a
->num_elements
;
458 da
->alloc_elements
= a
->num_elements
;
462 * Return the new array...
470 * 'cupsArrayFind()' - Find an element in the array.
472 * @since CUPS 1.2/OS X 10.5@
475 void * /* O - Element found or @code NULL@ */
476 cupsArrayFind(cups_array_t
*a
, /* I - Array */
477 void *e
) /* I - Element */
479 int current
, /* Current element */
480 diff
, /* Difference */
481 hash
; /* Hash index */
485 * Range check input...
492 * See if we have any elements...
495 if (!a
->num_elements
)
499 * Yes, look for a match...
504 hash
= (*(a
->hashfunc
))(e
, a
->data
);
506 if (hash
< 0 || hash
>= a
->hashsize
)
508 current
= a
->current
;
513 current
= a
->hash
[hash
];
515 if (current
< 0 || current
>= a
->num_elements
)
516 current
= a
->current
;
521 current
= a
->current
;
525 current
= cups_array_find(a
, e
, current
, &diff
);
529 * Found a match! If the array does not contain unique values, find
530 * the first element that is the same...
533 if (!a
->unique
&& a
->compare
)
536 * The array is not unique, find the first match...
539 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
544 a
->current
= current
;
547 a
->hash
[hash
] = current
;
549 return (a
->elements
[current
]);
565 * 'cupsArrayFirst()' - Get the first element in the array.
567 * @since CUPS 1.2/OS X 10.5@
570 void * /* O - First element or @code NULL@ if the array is empty */
571 cupsArrayFirst(cups_array_t
*a
) /* I - Array */
574 * Range check input...
581 * Return the first element...
586 return (cupsArrayCurrent(a
));
591 * 'cupsArrayGetIndex()' - Get the index of the current element.
593 * The current element is undefined until you call @link cupsArrayFind@,
594 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
596 * @since CUPS 1.3/OS X 10.5@
599 int /* O - Index of the current element, starting at 0 */
600 cupsArrayGetIndex(cups_array_t
*a
) /* I - Array */
610 * 'cupsArrayGetInsert()' - Get the index of the last inserted element.
612 * @since CUPS 1.3/OS X 10.5@
615 int /* O - Index of the last inserted element, starting at 0 */
616 cupsArrayGetInsert(cups_array_t
*a
) /* I - Array */
626 * 'cupsArrayIndex()' - Get the N-th element in the array.
628 * @since CUPS 1.2/OS X 10.5@
631 void * /* O - N-th element or @code NULL@ */
632 cupsArrayIndex(cups_array_t
*a
, /* I - Array */
633 int n
) /* I - Index into array, starting at 0 */
640 return (cupsArrayCurrent(a
));
645 * 'cupsArrayInsert()' - Insert an element in the array.
647 * When inserting an element in a sorted array, non-unique elements are
648 * inserted at the beginning of the run of identical elements. For unsorted
649 * arrays, the element is inserted at the beginning of the array.
651 * @since CUPS 1.2/OS X 10.5@
654 int /* O - 0 on failure, 1 on success */
655 cupsArrayInsert(cups_array_t
*a
, /* I - Array */
656 void *e
) /* I - Element */
658 DEBUG_printf(("2cupsArrayInsert(a=%p, e=%p)", a
, e
));
661 * Range check input...
666 DEBUG_puts("3cupsArrayInsert: returning 0");
671 * Insert the element...
674 return (cups_array_add(a
, e
, 1));
679 * 'cupsArrayLast()' - Get the last element in the array.
681 * @since CUPS 1.2/OS X 10.5@
684 void * /* O - Last element or @code NULL@ if the array is empty */
685 cupsArrayLast(cups_array_t
*a
) /* I - Array */
688 * Range check input...
695 * Return the last element...
698 a
->current
= a
->num_elements
- 1;
700 return (cupsArrayCurrent(a
));
705 * 'cupsArrayNew()' - Create a new array.
707 * The comparison function ("f") is used to create a sorted array. The function
708 * receives pointers to two elements and the user data pointer ("d") - the user
709 * data pointer argument can safely be omitted when not required so functions
710 * like @code strcmp@ can be used for sorted string arrays.
712 * @since CUPS 1.2/OS X 10.5@
715 cups_array_t
* /* O - Array */
716 cupsArrayNew(cups_array_func_t f
, /* I - Comparison function or @code NULL@ for an unsorted array */
717 void *d
) /* I - User data pointer or @code NULL@ */
719 return (cupsArrayNew3(f
, d
, 0, 0, 0, 0));
724 * 'cupsArrayNew2()' - Create a new array with hash.
726 * The comparison function ("f") is used to create a sorted array. The function
727 * receives pointers to two elements and the user data pointer ("d") - the user
728 * data pointer argument can safely be omitted when not required so functions
729 * like @code strcmp@ can be used for sorted string arrays.
731 * The hash function ("h") is used to implement cached lookups with the
732 * specified hash size ("hsize").
734 * @since CUPS 1.3/OS X 10.5@
737 cups_array_t
* /* O - Array */
738 cupsArrayNew2(cups_array_func_t f
, /* I - Comparison function or @code NULL@ for an unsorted array */
739 void *d
, /* I - User data or @code NULL@ */
740 cups_ahash_func_t h
, /* I - Hash function or @code NULL@ for unhashed lookups */
741 int hsize
) /* I - Hash size (>= 0) */
743 return (cupsArrayNew3(f
, d
, h
, hsize
, 0, 0));
748 * 'cupsArrayNew3()' - Create a new array with hash and/or free function.
750 * The comparison function ("f") is used to create a sorted array. The function
751 * receives pointers to two elements and the user data pointer ("d") - the user
752 * data pointer argument can safely be omitted when not required so functions
753 * like @code strcmp@ can be used for sorted string arrays.
755 * The hash function ("h") is used to implement cached lookups with the
756 * specified hash size ("hsize").
758 * The copy function ("cf") is used to automatically copy/retain elements when
759 * added or the array is copied.
761 * The free function ("cf") is used to automatically free/release elements when
762 * removed or the array is deleted.
764 * @since CUPS 1.5/OS X 10.7@
767 cups_array_t
* /* O - Array */
768 cupsArrayNew3(cups_array_func_t f
, /* I - Comparison function or @code NULL@ for an unsorted array */
769 void *d
, /* I - User data or @code NULL@ */
770 cups_ahash_func_t h
, /* I - Hash function or @code NULL@ for unhashed lookups */
771 int hsize
, /* I - Hash size (>= 0) */
772 cups_acopy_func_t cf
, /* I - Copy function */
773 cups_afree_func_t ff
) /* I - Free function */
775 cups_array_t
*a
; /* Array */
779 * Allocate memory for the array...
782 a
= calloc(1, sizeof(cups_array_t
));
797 a
->hash
= malloc(hsize
* sizeof(int));
805 memset(a
->hash
, -1, hsize
* sizeof(int));
816 * '_cupsArrayNewStrings()' - Create a new array of comma-delimited strings.
818 * Note: The array automatically manages copies of the strings passed. If the
819 * string pointer "s" is NULL or the empty string, no strings are added to the
820 * newly created array.
823 cups_array_t
* /* O - Array */
824 _cupsArrayNewStrings(const char *s
, /* I - Delimited strings or NULL */
825 char delim
) /* I - Delimiter character */
827 cups_array_t
*a
; /* Array */
830 if ((a
= cupsArrayNew3((cups_array_func_t
)strcmp
, NULL
, NULL
, 0,
831 (cups_acopy_func_t
)_cupsStrAlloc
,
832 (cups_afree_func_t
)_cupsStrFree
)) != NULL
)
833 _cupsArrayAddStrings(a
, s
, delim
);
840 * 'cupsArrayNext()' - Get the next element in the array.
842 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) + 1)".
844 * The next element is undefined until you call @link cupsArrayFind@,
845 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
846 * to set the current element.
848 * @since CUPS 1.2/OS X 10.5@
851 void * /* O - Next element or @code NULL@ */
852 cupsArrayNext(cups_array_t
*a
) /* I - Array */
855 * Range check input...
862 * Return the next element...
865 if (a
->current
< a
->num_elements
)
868 return (cupsArrayCurrent(a
));
873 * 'cupsArrayPrev()' - Get the previous element in the array.
875 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) - 1)".
877 * The previous element is undefined until you call @link cupsArrayFind@,
878 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
879 * to set the current element.
881 * @since CUPS 1.2/OS X 10.5@
884 void * /* O - Previous element or @code NULL@ */
885 cupsArrayPrev(cups_array_t
*a
) /* I - Array */
888 * Range check input...
895 * Return the previous element...
901 return (cupsArrayCurrent(a
));
906 * 'cupsArrayRemove()' - Remove an element from the array.
908 * If more than one element matches "e", only the first matching element is
911 * The caller is responsible for freeing the memory used by the
914 * @since CUPS 1.2/OS X 10.5@
917 int /* O - 1 on success, 0 on failure */
918 cupsArrayRemove(cups_array_t
*a
, /* I - Array */
919 void *e
) /* I - Element */
921 int i
, /* Looping var */
922 current
, /* Current element */
923 diff
; /* Difference */
927 * Range check input...
934 * See if the element is in the array...
937 if (!a
->num_elements
)
940 current
= cups_array_find(a
, e
, a
->current
, &diff
);
945 * Yes, now remove it...
951 (a
->freefunc
)(a
->elements
[current
], a
->data
);
953 if (current
< a
->num_elements
)
954 memmove(a
->elements
+ current
, a
->elements
+ current
+ 1,
955 (a
->num_elements
- current
) * sizeof(void *));
957 if (current
<= a
->current
)
960 if (current
< a
->insert
)
962 else if (current
== a
->insert
)
965 for (i
= 0; i
< a
->num_saved
; i
++)
966 if (current
<= a
->saved
[i
])
969 if (a
->num_elements
<= 1)
977 * 'cupsArrayRestore()' - Reset the current element to the last @link cupsArraySave@.
979 * @since CUPS 1.2/OS X 10.5@
982 void * /* O - New current element */
983 cupsArrayRestore(cups_array_t
*a
) /* I - Array */
988 if (a
->num_saved
<= 0)
992 a
->current
= a
->saved
[a
->num_saved
];
994 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
995 return (a
->elements
[a
->current
]);
1002 * 'cupsArraySave()' - Mark the current element for a later @link cupsArrayRestore@.
1004 * The current element is undefined until you call @link cupsArrayFind@,
1005 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
1006 * to set the current element.
1008 * The save/restore stack is guaranteed to be at least 32 elements deep.
1010 * @since CUPS 1.2/OS X 10.5@
1013 int /* O - 1 on success, 0 on failure */
1014 cupsArraySave(cups_array_t
*a
) /* I - Array */
1019 if (a
->num_saved
>= _CUPS_MAXSAVE
)
1022 a
->saved
[a
->num_saved
] = a
->current
;
1030 * 'cupsArrayUserData()' - Return the user data for an array.
1032 * @since CUPS 1.2/OS X 10.5@
1035 void * /* O - User data */
1036 cupsArrayUserData(cups_array_t
*a
) /* I - Array */
1046 * 'cups_array_add()' - Insert or append an element to the array.
1048 * @since CUPS 1.2/OS X 10.5@
1051 static int /* O - 1 on success, 0 on failure */
1052 cups_array_add(cups_array_t
*a
, /* I - Array */
1053 void *e
, /* I - Element to add */
1054 int insert
) /* I - 1 = insert, 0 = append */
1056 int i
, /* Looping var */
1057 current
, /* Current element */
1058 diff
; /* Comparison with current element */
1061 DEBUG_printf(("7cups_array_add(a=%p, e=%p, insert=%d)", a
, e
, insert
));
1064 * Verify we have room for the new element...
1067 if (a
->num_elements
>= a
->alloc_elements
)
1070 * Allocate additional elements; start with 16 elements, then
1071 * double the size until 1024 elements, then add 1024 elements
1075 void **temp
; /* New array elements */
1076 int count
; /* New allocation count */
1079 if (a
->alloc_elements
== 0)
1082 temp
= malloc(count
* sizeof(void *));
1086 if (a
->alloc_elements
< 1024)
1087 count
= a
->alloc_elements
* 2;
1089 count
= a
->alloc_elements
+ 1024;
1091 temp
= realloc(a
->elements
, count
* sizeof(void *));
1094 DEBUG_printf(("9cups_array_add: count=%d", count
));
1098 DEBUG_puts("9cups_array_add: allocation failed, returning 0");
1102 a
->alloc_elements
= count
;
1107 * Find the insertion point for the new element; if there is no
1108 * compare function or elements, just add it to the beginning or end...
1111 if (!a
->num_elements
|| !a
->compare
)
1114 * No elements or comparison function, insert/append as needed...
1118 current
= 0; /* Insert at beginning */
1120 current
= a
->num_elements
; /* Append to the end */
1125 * Do a binary search for the insertion point...
1128 current
= cups_array_find(a
, e
, a
->insert
, &diff
);
1133 * Insert after the current element...
1141 * Compared equal, make sure we add to the begining or end of
1142 * the current run of equal elements...
1150 * Insert at beginning of run...
1153 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
1160 * Append at end of run...
1167 while (current
< a
->num_elements
&&
1168 !(*(a
->compare
))(e
, a
->elements
[current
], a
->data
));
1174 * Insert or append the element...
1177 if (current
< a
->num_elements
)
1180 * Shift other elements to the right...
1183 memmove(a
->elements
+ current
+ 1, a
->elements
+ current
,
1184 (a
->num_elements
- current
) * sizeof(void *));
1186 if (a
->current
>= current
)
1189 for (i
= 0; i
< a
->num_saved
; i
++)
1190 if (a
->saved
[i
] >= current
)
1193 DEBUG_printf(("9cups_array_add: insert element at index %d...", current
));
1197 DEBUG_printf(("9cups_array_add: append element at %d...", current
));
1202 if ((a
->elements
[current
] = (a
->copyfunc
)(e
, a
->data
)) == NULL
)
1204 DEBUG_puts("8cups_array_add: Copy function returned NULL, returning 0");
1209 a
->elements
[current
] = e
;
1212 a
->insert
= current
;
1215 for (current
= 0; current
< a
->num_elements
; current
++)
1216 DEBUG_printf(("9cups_array_add: a->elements[%d]=%p", current
,
1217 a
->elements
[current
]));
1220 DEBUG_puts("9cups_array_add: returning 1");
1227 * 'cups_array_find()' - Find an element in the array.
1230 static int /* O - Index of match */
1231 cups_array_find(cups_array_t
*a
, /* I - Array */
1232 void *e
, /* I - Element */
1233 int prev
, /* I - Previous index */
1234 int *rdiff
) /* O - Difference of match */
1236 int left
, /* Left side of search */
1237 right
, /* Right side of search */
1238 current
, /* Current element */
1239 diff
; /* Comparison with current element */
1242 DEBUG_printf(("7cups_array_find(a=%p, e=%p, prev=%d, rdiff=%p)", a
, e
, prev
,
1248 * Do a binary search for the element...
1251 DEBUG_puts("9cups_array_find: binary search");
1253 if (prev
>= 0 && prev
< a
->num_elements
)
1256 * Start search on either side of previous...
1259 if ((diff
= (*(a
->compare
))(e
, a
->elements
[prev
], a
->data
)) == 0 ||
1260 (diff
< 0 && prev
== 0) ||
1261 (diff
> 0 && prev
== (a
->num_elements
- 1)))
1264 * Exact or edge match, return it!
1267 DEBUG_printf(("9cups_array_find: Returning %d, diff=%d", prev
, diff
));
1276 * Start with previous on right side...
1285 * Start wih previous on left side...
1289 right
= a
->num_elements
- 1;
1295 * Start search in the middle...
1299 right
= a
->num_elements
- 1;
1304 current
= (left
+ right
) / 2;
1305 diff
= (*(a
->compare
))(e
, a
->elements
[current
], a
->data
);
1307 DEBUG_printf(("9cups_array_find: left=%d, right=%d, current=%d, diff=%d",
1308 left
, right
, current
, diff
));
1317 while ((right
- left
) > 1);
1322 * Check the last 1 or 2 elements...
1325 if ((diff
= (*(a
->compare
))(e
, a
->elements
[left
], a
->data
)) <= 0)
1329 diff
= (*(a
->compare
))(e
, a
->elements
[right
], a
->data
);
1337 * Do a linear pointer search...
1340 DEBUG_puts("9cups_array_find: linear search");
1344 for (current
= 0; current
< a
->num_elements
; current
++)
1345 if (a
->elements
[current
] == e
)
1353 * Return the closest element and the difference...
1356 DEBUG_printf(("8cups_array_find: Returning %d, diff=%d", current
, diff
));