2 * Sorted array routines for CUPS.
4 * Copyright 2007-2014 by Apple Inc.
5 * Copyright 1997-2007 by Easy Software Products.
7 * Licensed under Apache License v2.0. See the file "LICENSE" for more information.
11 * Include necessary headers...
14 #include <cups/cups.h>
15 #include "string-private.h"
16 #include "debug-private.h"
17 #include "array-private.h"
24 #define _CUPS_MAXSAVE 32 /**** Maximum number of saves ****/
28 * Types and structures...
31 struct _cups_array_s
/**** CUPS array structure ****/
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
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 */
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 */
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
);
68 * 'cupsArrayAdd()' - Add an element to the array.
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.
74 * @since CUPS 1.2/macOS 10.5@
77 int /* O - 1 on success, 0 on failure */
78 cupsArrayAdd(cups_array_t
*a
, /* I - Array */
79 void *e
) /* I - Element */
81 DEBUG_printf(("2cupsArrayAdd(a=%p, e=%p)", (void *)a
, e
));
84 * Range check input...
89 DEBUG_puts("3cupsArrayAdd: returning 0");
94 * Append the element...
97 return (cups_array_add(a
, e
, 0));
102 * '_cupsArrayAddStrings()' - Add zero or more delimited strings to an array.
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.
109 int /* O - 1 on success, 0 on failure */
110 _cupsArrayAddStrings(cups_array_t
*a
, /* I - Array */
111 const char *s
, /* I - Delimited strings or NULL */
112 char delim
)/* I - Delimiter character */
114 char *buffer
, /* Copy of string */
115 *start
, /* Start of string */
116 *end
; /* End of string */
117 int status
= 1; /* Status of add */
120 DEBUG_printf(("_cupsArrayAddStrings(a=%p, s=\"%s\", delim='%c')", (void *)a
, s
, delim
));
124 DEBUG_puts("1_cupsArrayAddStrings: Returning 0");
131 * Skip leading whitespace...
134 DEBUG_puts("1_cupsArrayAddStrings: Skipping leading whitespace.");
136 while (*s
&& isspace(*s
& 255))
139 DEBUG_printf(("1_cupsArrayAddStrings: Remaining string \"%s\".", s
));
142 if (!strchr(s
, delim
) &&
143 (delim
!= ' ' || (!strchr(s
, '\t') && !strchr(s
, '\n'))))
146 * String doesn't contain a delimiter, so add it as a single value...
149 DEBUG_puts("1_cupsArrayAddStrings: No delimiter seen, adding a single "
152 if (!cupsArrayFind(a
, (void *)s
))
153 status
= cupsArrayAdd(a
, (void *)s
);
155 else if ((buffer
= strdup(s
)) == NULL
)
157 DEBUG_puts("1_cupsArrayAddStrings: Unable to duplicate string.");
162 for (start
= end
= buffer
; *end
; start
= end
)
165 * Find the end of the current delimited string and see if we need to add
171 while (*end
&& !isspace(*end
& 255))
173 while (*end
&& isspace(*end
& 255))
176 else if ((end
= strchr(start
, delim
)) != NULL
)
179 end
= start
+ strlen(start
);
181 DEBUG_printf(("1_cupsArrayAddStrings: Adding \"%s\", end=\"%s\"", start
,
184 if (!cupsArrayFind(a
, start
))
185 status
&= cupsArrayAdd(a
, start
);
191 DEBUG_printf(("1_cupsArrayAddStrings: Returning %d.", status
));
198 * 'cupsArrayClear()' - Clear the array.
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.
204 * @since CUPS 1.2/macOS 10.5@
208 cupsArrayClear(cups_array_t
*a
) /* I - Array */
211 * Range check input...
218 * Free the existing elements as needed..
223 int i
; /* Looping var */
224 void **e
; /* Current element */
226 for (i
= a
->num_elements
, e
= a
->elements
; i
> 0; i
--, e
++)
227 (a
->freefunc
)(*e
, a
->data
);
231 * Set the number of elements to 0; we don't actually free the memory
232 * here - that is done in cupsArrayDelete()...
244 * 'cupsArrayCount()' - Get the number of elements in the array.
246 * @since CUPS 1.2/macOS 10.5@
249 int /* O - Number of elements */
250 cupsArrayCount(cups_array_t
*a
) /* I - Array */
253 * Range check input...
260 * Return the number of elements...
263 return (a
->num_elements
);
268 * 'cupsArrayCurrent()' - Return the current element in the array.
270 * The current element is undefined until you call @link cupsArrayFind@,
271 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
273 * @since CUPS 1.2/macOS 10.5@
276 void * /* O - Element */
277 cupsArrayCurrent(cups_array_t
*a
) /* I - Array */
280 * Range check input...
287 * Return the current element...
290 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
291 return (a
->elements
[a
->current
]);
298 * 'cupsArrayDelete()' - Free all memory used by the array.
300 * The caller is responsible for freeing the memory used by the
301 * elements themselves.
303 * @since CUPS 1.2/macOS 10.5@
307 cupsArrayDelete(cups_array_t
*a
) /* I - Array */
310 * Range check input...
317 * Free the elements if we have a free function (otherwise the caller is
318 * responsible for doing the dirty work...)
323 int i
; /* Looping var */
324 void **e
; /* Current element */
326 for (i
= a
->num_elements
, e
= a
->elements
; i
> 0; i
--, e
++)
327 (a
->freefunc
)(*e
, a
->data
);
331 * Free the array of element pointers...
334 if (a
->alloc_elements
)
345 * 'cupsArrayDup()' - Duplicate the array.
347 * @since CUPS 1.2/macOS 10.5@
350 cups_array_t
* /* O - Duplicate array */
351 cupsArrayDup(cups_array_t
*a
) /* I - Array */
353 cups_array_t
*da
; /* Duplicate array */
357 * Range check input...
364 * Allocate memory for the array...
367 da
= calloc(1, sizeof(cups_array_t
));
371 da
->compare
= a
->compare
;
373 da
->current
= a
->current
;
374 da
->insert
= a
->insert
;
375 da
->unique
= a
->unique
;
376 da
->num_saved
= a
->num_saved
;
378 memcpy(da
->saved
, a
->saved
, sizeof(a
->saved
));
383 * Allocate memory for the elements...
386 da
->elements
= malloc((size_t)a
->num_elements
* sizeof(void *));
394 * Copy the element pointers...
400 * Use the copy function to make a copy of each element...
403 int i
; /* Looping var */
405 for (i
= 0; i
< a
->num_elements
; i
++)
406 da
->elements
[i
] = (a
->copyfunc
)(a
->elements
[i
], a
->data
);
411 * Just copy raw pointers...
414 memcpy(da
->elements
, a
->elements
, (size_t)a
->num_elements
* sizeof(void *));
417 da
->num_elements
= a
->num_elements
;
418 da
->alloc_elements
= a
->num_elements
;
422 * Return the new array...
430 * 'cupsArrayFind()' - Find an element in the array.
432 * @since CUPS 1.2/macOS 10.5@
435 void * /* O - Element found or @code NULL@ */
436 cupsArrayFind(cups_array_t
*a
, /* I - Array */
437 void *e
) /* I - Element */
439 int current
, /* Current element */
440 diff
, /* Difference */
441 hash
; /* Hash index */
445 * Range check input...
452 * See if we have any elements...
455 if (!a
->num_elements
)
459 * Yes, look for a match...
464 hash
= (*(a
->hashfunc
))(e
, a
->data
);
466 if (hash
< 0 || hash
>= a
->hashsize
)
468 current
= a
->current
;
473 current
= a
->hash
[hash
];
475 if (current
< 0 || current
>= a
->num_elements
)
476 current
= a
->current
;
481 current
= a
->current
;
485 current
= cups_array_find(a
, e
, current
, &diff
);
489 * Found a match! If the array does not contain unique values, find
490 * the first element that is the same...
493 if (!a
->unique
&& a
->compare
)
496 * The array is not unique, find the first match...
499 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
504 a
->current
= current
;
507 a
->hash
[hash
] = current
;
509 return (a
->elements
[current
]);
525 * 'cupsArrayFirst()' - Get the first element in the array.
527 * @since CUPS 1.2/macOS 10.5@
530 void * /* O - First element or @code NULL@ if the array is empty */
531 cupsArrayFirst(cups_array_t
*a
) /* I - Array */
534 * Range check input...
541 * Return the first element...
546 return (cupsArrayCurrent(a
));
551 * 'cupsArrayGetIndex()' - Get the index of the current element.
553 * The current element is undefined until you call @link cupsArrayFind@,
554 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
556 * @since CUPS 1.3/macOS 10.5@
559 int /* O - Index of the current element, starting at 0 */
560 cupsArrayGetIndex(cups_array_t
*a
) /* I - Array */
570 * 'cupsArrayGetInsert()' - Get the index of the last inserted element.
572 * @since CUPS 1.3/macOS 10.5@
575 int /* O - Index of the last inserted element, starting at 0 */
576 cupsArrayGetInsert(cups_array_t
*a
) /* I - Array */
586 * 'cupsArrayIndex()' - Get the N-th element in the array.
588 * @since CUPS 1.2/macOS 10.5@
591 void * /* O - N-th element or @code NULL@ */
592 cupsArrayIndex(cups_array_t
*a
, /* I - Array */
593 int n
) /* I - Index into array, starting at 0 */
600 return (cupsArrayCurrent(a
));
605 * 'cupsArrayInsert()' - Insert an element in the array.
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.
611 * @since CUPS 1.2/macOS 10.5@
614 int /* O - 0 on failure, 1 on success */
615 cupsArrayInsert(cups_array_t
*a
, /* I - Array */
616 void *e
) /* I - Element */
618 DEBUG_printf(("2cupsArrayInsert(a=%p, e=%p)", (void *)a
, e
));
621 * Range check input...
626 DEBUG_puts("3cupsArrayInsert: returning 0");
631 * Insert the element...
634 return (cups_array_add(a
, e
, 1));
639 * 'cupsArrayLast()' - Get the last element in the array.
641 * @since CUPS 1.2/macOS 10.5@
644 void * /* O - Last element or @code NULL@ if the array is empty */
645 cupsArrayLast(cups_array_t
*a
) /* I - Array */
648 * Range check input...
655 * Return the last element...
658 a
->current
= a
->num_elements
- 1;
660 return (cupsArrayCurrent(a
));
665 * 'cupsArrayNew()' - Create a new array.
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.
672 * @since CUPS 1.2/macOS 10.5@
675 cups_array_t
* /* O - Array */
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@ */
679 return (cupsArrayNew3(f
, d
, 0, 0, 0, 0));
684 * 'cupsArrayNew2()' - Create a new array with hash.
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.
691 * The hash function ("h") is used to implement cached lookups with the
692 * specified hash size ("hsize").
694 * @since CUPS 1.3/macOS 10.5@
697 cups_array_t
* /* O - Array */
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) */
703 return (cupsArrayNew3(f
, d
, h
, hsize
, 0, 0));
708 * 'cupsArrayNew3()' - Create a new array with hash and/or free function.
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.
715 * The hash function ("h") is used to implement cached lookups with the
716 * specified hash size ("hsize").
718 * The copy function ("cf") is used to automatically copy/retain elements when
719 * added or the array is copied.
721 * The free function ("cf") is used to automatically free/release elements when
722 * removed or the array is deleted.
724 * @since CUPS 1.5/macOS 10.7@
727 cups_array_t
* /* O - Array */
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 */
735 cups_array_t
*a
; /* Array */
739 * Allocate memory for the array...
742 a
= calloc(1, sizeof(cups_array_t
));
757 a
->hash
= malloc((size_t)hsize
* sizeof(int));
765 memset(a
->hash
, -1, (size_t)hsize
* sizeof(int));
776 * '_cupsArrayNewStrings()' - Create a new array of comma-delimited strings.
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.
783 cups_array_t
* /* O - Array */
784 _cupsArrayNewStrings(const char *s
, /* I - Delimited strings or NULL */
785 char delim
) /* I - Delimiter character */
787 cups_array_t
*a
; /* Array */
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
);
800 * 'cupsArrayNext()' - Get the next element in the array.
802 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) + 1)".
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.
808 * @since CUPS 1.2/macOS 10.5@
811 void * /* O - Next element or @code NULL@ */
812 cupsArrayNext(cups_array_t
*a
) /* I - Array */
815 * Range check input...
822 * Return the next element...
825 if (a
->current
< a
->num_elements
)
828 return (cupsArrayCurrent(a
));
833 * 'cupsArrayPrev()' - Get the previous element in the array.
835 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) - 1)".
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.
841 * @since CUPS 1.2/macOS 10.5@
844 void * /* O - Previous element or @code NULL@ */
845 cupsArrayPrev(cups_array_t
*a
) /* I - Array */
848 * Range check input...
855 * Return the previous element...
861 return (cupsArrayCurrent(a
));
866 * 'cupsArrayRemove()' - Remove an element from the array.
868 * If more than one element matches "e", only the first matching element is
871 * The caller is responsible for freeing the memory used by the
874 * @since CUPS 1.2/macOS 10.5@
877 int /* O - 1 on success, 0 on failure */
878 cupsArrayRemove(cups_array_t
*a
, /* I - Array */
879 void *e
) /* I - Element */
881 ssize_t i
, /* Looping var */
882 current
; /* Current element */
883 int diff
; /* Difference */
887 * Range check input...
894 * See if the element is in the array...
897 if (!a
->num_elements
)
900 current
= cups_array_find(a
, e
, a
->current
, &diff
);
905 * Yes, now remove it...
911 (a
->freefunc
)(a
->elements
[current
], a
->data
);
913 if (current
< a
->num_elements
)
914 memmove(a
->elements
+ current
, a
->elements
+ current
+ 1,
915 (size_t)(a
->num_elements
- current
) * sizeof(void *));
917 if (current
<= a
->current
)
920 if (current
< a
->insert
)
922 else if (current
== a
->insert
)
925 for (i
= 0; i
< a
->num_saved
; i
++)
926 if (current
<= a
->saved
[i
])
929 if (a
->num_elements
<= 1)
937 * 'cupsArrayRestore()' - Reset the current element to the last @link cupsArraySave@.
939 * @since CUPS 1.2/macOS 10.5@
942 void * /* O - New current element */
943 cupsArrayRestore(cups_array_t
*a
) /* I - Array */
948 if (a
->num_saved
<= 0)
952 a
->current
= a
->saved
[a
->num_saved
];
954 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
955 return (a
->elements
[a
->current
]);
962 * 'cupsArraySave()' - Mark the current element for a later @link cupsArrayRestore@.
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.
968 * The save/restore stack is guaranteed to be at least 32 elements deep.
970 * @since CUPS 1.2/macOS 10.5@
973 int /* O - 1 on success, 0 on failure */
974 cupsArraySave(cups_array_t
*a
) /* I - Array */
979 if (a
->num_saved
>= _CUPS_MAXSAVE
)
982 a
->saved
[a
->num_saved
] = a
->current
;
990 * 'cupsArrayUserData()' - Return the user data for an array.
992 * @since CUPS 1.2/macOS 10.5@
995 void * /* O - User data */
996 cupsArrayUserData(cups_array_t
*a
) /* I - Array */
1006 * 'cups_array_add()' - Insert or append an element to the array.
1008 * @since CUPS 1.2/macOS 10.5@
1011 static int /* O - 1 on success, 0 on failure */
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 */
1016 int i
, /* Looping var */
1017 current
; /* Current element */
1018 int diff
; /* Comparison with current element */
1021 DEBUG_printf(("7cups_array_add(a=%p, e=%p, insert=%d)", (void *)a
, e
, insert
));
1024 * Verify we have room for the new element...
1027 if (a
->num_elements
>= a
->alloc_elements
)
1030 * Allocate additional elements; start with 16 elements, then
1031 * double the size until 1024 elements, then add 1024 elements
1035 void **temp
; /* New array elements */
1036 int count
; /* New allocation count */
1039 if (a
->alloc_elements
== 0)
1042 temp
= malloc((size_t)count
* sizeof(void *));
1046 if (a
->alloc_elements
< 1024)
1047 count
= a
->alloc_elements
* 2;
1049 count
= a
->alloc_elements
+ 1024;
1051 temp
= realloc(a
->elements
, (size_t)count
* sizeof(void *));
1054 DEBUG_printf(("9cups_array_add: count=" CUPS_LLFMT
, CUPS_LLCAST count
));
1058 DEBUG_puts("9cups_array_add: allocation failed, returning 0");
1062 a
->alloc_elements
= count
;
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...
1071 if (!a
->num_elements
|| !a
->compare
)
1074 * No elements or comparison function, insert/append as needed...
1078 current
= 0; /* Insert at beginning */
1080 current
= a
->num_elements
; /* Append to the end */
1085 * Do a binary search for the insertion point...
1088 current
= cups_array_find(a
, e
, a
->insert
, &diff
);
1093 * Insert after the current element...
1101 * Compared equal, make sure we add to the begining or end of
1102 * the current run of equal elements...
1110 * Insert at beginning of run...
1113 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
1120 * Append at end of run...
1127 while (current
< a
->num_elements
&&
1128 !(*(a
->compare
))(e
, a
->elements
[current
], a
->data
));
1134 * Insert or append the element...
1137 if (current
< a
->num_elements
)
1140 * Shift other elements to the right...
1143 memmove(a
->elements
+ current
+ 1, a
->elements
+ current
,
1144 (size_t)(a
->num_elements
- current
) * sizeof(void *));
1146 if (a
->current
>= current
)
1149 for (i
= 0; i
< a
->num_saved
; i
++)
1150 if (a
->saved
[i
] >= current
)
1153 DEBUG_printf(("9cups_array_add: insert element at index " CUPS_LLFMT
, CUPS_LLCAST current
));
1157 DEBUG_printf(("9cups_array_add: append element at " CUPS_LLFMT
, CUPS_LLCAST current
));
1162 if ((a
->elements
[current
] = (a
->copyfunc
)(e
, a
->data
)) == NULL
)
1164 DEBUG_puts("8cups_array_add: Copy function returned NULL, returning 0");
1169 a
->elements
[current
] = e
;
1172 a
->insert
= current
;
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
]));
1179 DEBUG_puts("9cups_array_add: returning 1");
1186 * 'cups_array_find()' - Find an element in the array.
1189 static int /* O - Index of match */
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 */
1195 int left
, /* Left side of search */
1196 right
, /* Right side of search */
1197 current
, /* Current element */
1198 diff
; /* Comparison with current element */
1201 DEBUG_printf(("7cups_array_find(a=%p, e=%p, prev=%d, rdiff=%p)", (void *)a
, e
, prev
, (void *)rdiff
));
1206 * Do a binary search for the element...
1209 DEBUG_puts("9cups_array_find: binary search");
1211 if (prev
>= 0 && prev
< a
->num_elements
)
1214 * Start search on either side of previous...
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)))
1222 * Exact or edge match, return it!
1225 DEBUG_printf(("9cups_array_find: Returning %d, diff=%d", prev
, diff
));
1234 * Start with previous on right side...
1243 * Start wih previous on left side...
1247 right
= a
->num_elements
- 1;
1253 * Start search in the middle...
1257 right
= a
->num_elements
- 1;
1262 current
= (left
+ right
) / 2;
1263 diff
= (*(a
->compare
))(e
, a
->elements
[current
], a
->data
);
1265 DEBUG_printf(("9cups_array_find: left=%d, right=%d, current=%d, diff=%d",
1266 left
, right
, current
, diff
));
1275 while ((right
- left
) > 1);
1280 * Check the last 1 or 2 elements...
1283 if ((diff
= (*(a
->compare
))(e
, a
->elements
[left
], a
->data
)) <= 0)
1287 diff
= (*(a
->compare
))(e
, a
->elements
[right
], a
->data
);
1295 * Do a linear pointer search...
1298 DEBUG_puts("9cups_array_find: linear search");
1302 for (current
= 0; current
< a
->num_elements
; current
++)
1303 if (a
->elements
[current
] == e
)
1311 * Return the closest element and the difference...
1314 DEBUG_printf(("8cups_array_find: Returning %d, diff=%d", current
, diff
));