4 * Sorted array routines for CUPS.
6 * Copyright 2007-2014 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 * Include necessary headers...
22 #include <cups/cups.h>
23 #include "string-private.h"
24 #include "debug-private.h"
25 #include "array-private.h"
32 #define _CUPS_MAXSAVE 32 /**** Maximum number of saves ****/
36 * Types and structures...
39 struct _cups_array_s
/**** CUPS array structure ****/
42 * The current implementation uses an insertion sort into an array of
43 * sorted pointers. We leave the array type private/opaque so that we
44 * can change the underlying implementation without affecting the users
48 int num_elements
, /* Number of array elements */
49 alloc_elements
, /* Allocated array elements */
50 current
, /* Current element */
51 insert
, /* Last inserted element */
52 unique
, /* Are all elements unique? */
53 num_saved
, /* Number of saved elements */
56 void **elements
; /* Array elements */
57 cups_array_func_t compare
; /* Element comparison function */
58 void *data
; /* User data passed to compare */
59 cups_ahash_func_t hashfunc
; /* Hash function */
60 int hashsize
, /* Size of hash */
61 *hash
; /* Hash array */
62 cups_acopy_func_t copyfunc
; /* Copy function */
63 cups_afree_func_t freefunc
; /* Free function */
71 static int cups_array_add(cups_array_t
*a
, void *e
, int insert
);
72 static int cups_array_find(cups_array_t
*a
, void *e
, int prev
, int *rdiff
);
76 * 'cupsArrayAdd()' - Add an element to the array.
78 * When adding an element to a sorted array, non-unique elements are
79 * appended at the end of the run of identical elements. For unsorted arrays,
80 * the element is appended to the end of the array.
82 * @since CUPS 1.2/OS X 10.5@
85 int /* O - 1 on success, 0 on failure */
86 cupsArrayAdd(cups_array_t
*a
, /* I - Array */
87 void *e
) /* I - Element */
89 DEBUG_printf(("2cupsArrayAdd(a=%p, e=%p)", a
, e
));
92 * Range check input...
97 DEBUG_puts("3cupsArrayAdd: returning 0");
102 * Append the element...
105 return (cups_array_add(a
, e
, 0));
110 * '_cupsArrayAddStrings()' - Add zero or more delimited strings to an array.
112 * Note: The array MUST be created using the @link _cupsArrayNewStrings@
113 * function. Duplicate strings are NOT added. If the string pointer "s" is NULL
114 * or the empty string, no strings are added to the array.
117 int /* O - 1 on success, 0 on failure */
118 _cupsArrayAddStrings(cups_array_t
*a
, /* I - Array */
119 const char *s
, /* I - Delimited strings or NULL */
120 char delim
)/* I - Delimiter character */
122 char *buffer
, /* Copy of string */
123 *start
, /* Start of string */
124 *end
; /* End of string */
125 int status
= 1; /* Status of add */
128 DEBUG_printf(("_cupsArrayAddStrings(a=%p, s=\"%s\", delim='%c')", a
, s
,
133 DEBUG_puts("1_cupsArrayAddStrings: Returning 0");
140 * Skip leading whitespace...
143 DEBUG_puts("1_cupsArrayAddStrings: Skipping leading whitespace.");
145 while (*s
&& isspace(*s
& 255))
148 DEBUG_printf(("1_cupsArrayAddStrings: Remaining string \"%s\".", s
));
151 if (!strchr(s
, delim
) &&
152 (delim
!= ' ' || (!strchr(s
, '\t') && !strchr(s
, '\n'))))
155 * String doesn't contain a delimiter, so add it as a single value...
158 DEBUG_puts("1_cupsArrayAddStrings: No delimiter seen, adding a single "
161 if (!cupsArrayFind(a
, (void *)s
))
162 status
= cupsArrayAdd(a
, (void *)s
);
164 else if ((buffer
= strdup(s
)) == NULL
)
166 DEBUG_puts("1_cupsArrayAddStrings: Unable to duplicate string.");
171 for (start
= end
= buffer
; *end
; start
= end
)
174 * Find the end of the current delimited string and see if we need to add
180 while (*end
&& !isspace(*end
& 255))
182 while (*end
&& isspace(*end
& 255))
185 else if ((end
= strchr(start
, delim
)) != NULL
)
188 end
= start
+ strlen(start
);
190 DEBUG_printf(("1_cupsArrayAddStrings: Adding \"%s\", end=\"%s\"", start
,
193 if (!cupsArrayFind(a
, start
))
194 status
&= cupsArrayAdd(a
, start
);
200 DEBUG_printf(("1_cupsArrayAddStrings: Returning %d.", status
));
207 * 'cupsArrayClear()' - Clear the array.
209 * This function is equivalent to removing all elements in the array.
210 * The caller is responsible for freeing the memory used by the
211 * elements themselves.
213 * @since CUPS 1.2/OS X 10.5@
217 cupsArrayClear(cups_array_t
*a
) /* I - Array */
220 * Range check input...
227 * Free the existing elements as needed..
232 int i
; /* Looping var */
233 void **e
; /* Current element */
235 for (i
= a
->num_elements
, e
= a
->elements
; i
> 0; i
--, e
++)
236 (a
->freefunc
)(*e
, a
->data
);
240 * Set the number of elements to 0; we don't actually free the memory
241 * here - that is done in cupsArrayDelete()...
253 * 'cupsArrayCount()' - Get the number of elements in the array.
255 * @since CUPS 1.2/OS X 10.5@
258 int /* O - Number of elements */
259 cupsArrayCount(cups_array_t
*a
) /* I - Array */
262 * Range check input...
269 * Return the number of elements...
272 return (a
->num_elements
);
277 * 'cupsArrayCurrent()' - Return the current element in the array.
279 * The current element is undefined until you call @link cupsArrayFind@,
280 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
282 * @since CUPS 1.2/OS X 10.5@
285 void * /* O - Element */
286 cupsArrayCurrent(cups_array_t
*a
) /* I - Array */
289 * Range check input...
296 * Return the current element...
299 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
300 return (a
->elements
[a
->current
]);
307 * 'cupsArrayDelete()' - Free all memory used by the array.
309 * The caller is responsible for freeing the memory used by the
310 * elements themselves.
312 * @since CUPS 1.2/OS X 10.5@
316 cupsArrayDelete(cups_array_t
*a
) /* I - Array */
319 * Range check input...
326 * Free the elements if we have a free function (otherwise the caller is
327 * responsible for doing the dirty work...)
332 int i
; /* Looping var */
333 void **e
; /* Current element */
335 for (i
= a
->num_elements
, e
= a
->elements
; i
> 0; i
--, e
++)
336 (a
->freefunc
)(*e
, a
->data
);
340 * Free the array of element pointers...
343 if (a
->alloc_elements
)
354 * 'cupsArrayDup()' - Duplicate the array.
356 * @since CUPS 1.2/OS X 10.5@
359 cups_array_t
* /* O - Duplicate array */
360 cupsArrayDup(cups_array_t
*a
) /* I - Array */
362 cups_array_t
*da
; /* Duplicate array */
366 * Range check input...
373 * Allocate memory for the array...
376 da
= calloc(1, sizeof(cups_array_t
));
380 da
->compare
= a
->compare
;
382 da
->current
= a
->current
;
383 da
->insert
= a
->insert
;
384 da
->unique
= a
->unique
;
385 da
->num_saved
= a
->num_saved
;
387 memcpy(da
->saved
, a
->saved
, sizeof(a
->saved
));
392 * Allocate memory for the elements...
395 da
->elements
= malloc((size_t)a
->num_elements
* sizeof(void *));
403 * Copy the element pointers...
409 * Use the copy function to make a copy of each element...
412 int i
; /* Looping var */
414 for (i
= 0; i
< a
->num_elements
; i
++)
415 da
->elements
[i
] = (a
->copyfunc
)(a
->elements
[i
], a
->data
);
420 * Just copy raw pointers...
423 memcpy(da
->elements
, a
->elements
, (size_t)a
->num_elements
* sizeof(void *));
426 da
->num_elements
= a
->num_elements
;
427 da
->alloc_elements
= a
->num_elements
;
431 * Return the new array...
439 * 'cupsArrayFind()' - Find an element in the array.
441 * @since CUPS 1.2/OS X 10.5@
444 void * /* O - Element found or @code NULL@ */
445 cupsArrayFind(cups_array_t
*a
, /* I - Array */
446 void *e
) /* I - Element */
448 int current
, /* Current element */
449 diff
, /* Difference */
450 hash
; /* Hash index */
454 * Range check input...
461 * See if we have any elements...
464 if (!a
->num_elements
)
468 * Yes, look for a match...
473 hash
= (*(a
->hashfunc
))(e
, a
->data
);
475 if (hash
< 0 || hash
>= a
->hashsize
)
477 current
= a
->current
;
482 current
= a
->hash
[hash
];
484 if (current
< 0 || current
>= a
->num_elements
)
485 current
= a
->current
;
490 current
= a
->current
;
494 current
= cups_array_find(a
, e
, current
, &diff
);
498 * Found a match! If the array does not contain unique values, find
499 * the first element that is the same...
502 if (!a
->unique
&& a
->compare
)
505 * The array is not unique, find the first match...
508 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
513 a
->current
= current
;
516 a
->hash
[hash
] = current
;
518 return (a
->elements
[current
]);
534 * 'cupsArrayFirst()' - Get the first element in the array.
536 * @since CUPS 1.2/OS X 10.5@
539 void * /* O - First element or @code NULL@ if the array is empty */
540 cupsArrayFirst(cups_array_t
*a
) /* I - Array */
543 * Range check input...
550 * Return the first element...
555 return (cupsArrayCurrent(a
));
560 * 'cupsArrayGetIndex()' - Get the index of the current element.
562 * The current element is undefined until you call @link cupsArrayFind@,
563 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
565 * @since CUPS 1.3/OS X 10.5@
568 int /* O - Index of the current element, starting at 0 */
569 cupsArrayGetIndex(cups_array_t
*a
) /* I - Array */
579 * 'cupsArrayGetInsert()' - Get the index of the last inserted element.
581 * @since CUPS 1.3/OS X 10.5@
584 int /* O - Index of the last inserted element, starting at 0 */
585 cupsArrayGetInsert(cups_array_t
*a
) /* I - Array */
595 * 'cupsArrayIndex()' - Get the N-th element in the array.
597 * @since CUPS 1.2/OS X 10.5@
600 void * /* O - N-th element or @code NULL@ */
601 cupsArrayIndex(cups_array_t
*a
, /* I - Array */
602 int n
) /* I - Index into array, starting at 0 */
609 return (cupsArrayCurrent(a
));
614 * 'cupsArrayInsert()' - Insert an element in the array.
616 * When inserting an element in a sorted array, non-unique elements are
617 * inserted at the beginning of the run of identical elements. For unsorted
618 * arrays, the element is inserted at the beginning of the array.
620 * @since CUPS 1.2/OS X 10.5@
623 int /* O - 0 on failure, 1 on success */
624 cupsArrayInsert(cups_array_t
*a
, /* I - Array */
625 void *e
) /* I - Element */
627 DEBUG_printf(("2cupsArrayInsert(a=%p, e=%p)", a
, e
));
630 * Range check input...
635 DEBUG_puts("3cupsArrayInsert: returning 0");
640 * Insert the element...
643 return (cups_array_add(a
, e
, 1));
648 * 'cupsArrayLast()' - Get the last element in the array.
650 * @since CUPS 1.2/OS X 10.5@
653 void * /* O - Last element or @code NULL@ if the array is empty */
654 cupsArrayLast(cups_array_t
*a
) /* I - Array */
657 * Range check input...
664 * Return the last element...
667 a
->current
= a
->num_elements
- 1;
669 return (cupsArrayCurrent(a
));
674 * 'cupsArrayNew()' - Create a new array.
676 * The comparison function ("f") is used to create a sorted array. The function
677 * receives pointers to two elements and the user data pointer ("d") - the user
678 * data pointer argument can safely be omitted when not required so functions
679 * like @code strcmp@ can be used for sorted string arrays.
681 * @since CUPS 1.2/OS X 10.5@
684 cups_array_t
* /* O - Array */
685 cupsArrayNew(cups_array_func_t f
, /* I - Comparison function or @code NULL@ for an unsorted array */
686 void *d
) /* I - User data pointer or @code NULL@ */
688 return (cupsArrayNew3(f
, d
, 0, 0, 0, 0));
693 * 'cupsArrayNew2()' - Create a new array with hash.
695 * The comparison function ("f") is used to create a sorted array. The function
696 * receives pointers to two elements and the user data pointer ("d") - the user
697 * data pointer argument can safely be omitted when not required so functions
698 * like @code strcmp@ can be used for sorted string arrays.
700 * The hash function ("h") is used to implement cached lookups with the
701 * specified hash size ("hsize").
703 * @since CUPS 1.3/OS X 10.5@
706 cups_array_t
* /* O - Array */
707 cupsArrayNew2(cups_array_func_t f
, /* I - Comparison function or @code NULL@ for an unsorted array */
708 void *d
, /* I - User data or @code NULL@ */
709 cups_ahash_func_t h
, /* I - Hash function or @code NULL@ for unhashed lookups */
710 int hsize
) /* I - Hash size (>= 0) */
712 return (cupsArrayNew3(f
, d
, h
, hsize
, 0, 0));
717 * 'cupsArrayNew3()' - Create a new array with hash and/or free function.
719 * The comparison function ("f") is used to create a sorted array. The function
720 * receives pointers to two elements and the user data pointer ("d") - the user
721 * data pointer argument can safely be omitted when not required so functions
722 * like @code strcmp@ can be used for sorted string arrays.
724 * The hash function ("h") is used to implement cached lookups with the
725 * specified hash size ("hsize").
727 * The copy function ("cf") is used to automatically copy/retain elements when
728 * added or the array is copied.
730 * The free function ("cf") is used to automatically free/release elements when
731 * removed or the array is deleted.
733 * @since CUPS 1.5/OS X 10.7@
736 cups_array_t
* /* O - Array */
737 cupsArrayNew3(cups_array_func_t f
, /* I - Comparison function or @code NULL@ for an unsorted array */
738 void *d
, /* I - User data or @code NULL@ */
739 cups_ahash_func_t h
, /* I - Hash function or @code NULL@ for unhashed lookups */
740 int hsize
, /* I - Hash size (>= 0) */
741 cups_acopy_func_t cf
, /* I - Copy function */
742 cups_afree_func_t ff
) /* I - Free function */
744 cups_array_t
*a
; /* Array */
748 * Allocate memory for the array...
751 a
= calloc(1, sizeof(cups_array_t
));
766 a
->hash
= malloc((size_t)hsize
* sizeof(int));
774 memset(a
->hash
, -1, (size_t)hsize
* sizeof(int));
785 * '_cupsArrayNewStrings()' - Create a new array of comma-delimited strings.
787 * Note: The array automatically manages copies of the strings passed. If the
788 * string pointer "s" is NULL or the empty string, no strings are added to the
789 * newly created array.
792 cups_array_t
* /* O - Array */
793 _cupsArrayNewStrings(const char *s
, /* I - Delimited strings or NULL */
794 char delim
) /* I - Delimiter character */
796 cups_array_t
*a
; /* Array */
799 if ((a
= cupsArrayNew3((cups_array_func_t
)strcmp
, NULL
, NULL
, 0,
800 (cups_acopy_func_t
)_cupsStrAlloc
,
801 (cups_afree_func_t
)_cupsStrFree
)) != NULL
)
802 _cupsArrayAddStrings(a
, s
, delim
);
809 * 'cupsArrayNext()' - Get the next element in the array.
811 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) + 1)".
813 * The next element is undefined until you call @link cupsArrayFind@,
814 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
815 * to set the current element.
817 * @since CUPS 1.2/OS X 10.5@
820 void * /* O - Next element or @code NULL@ */
821 cupsArrayNext(cups_array_t
*a
) /* I - Array */
824 * Range check input...
831 * Return the next element...
834 if (a
->current
< a
->num_elements
)
837 return (cupsArrayCurrent(a
));
842 * 'cupsArrayPrev()' - Get the previous element in the array.
844 * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) - 1)".
846 * The previous element is undefined until you call @link cupsArrayFind@,
847 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
848 * to set the current element.
850 * @since CUPS 1.2/OS X 10.5@
853 void * /* O - Previous element or @code NULL@ */
854 cupsArrayPrev(cups_array_t
*a
) /* I - Array */
857 * Range check input...
864 * Return the previous element...
870 return (cupsArrayCurrent(a
));
875 * 'cupsArrayRemove()' - Remove an element from the array.
877 * If more than one element matches "e", only the first matching element is
880 * The caller is responsible for freeing the memory used by the
883 * @since CUPS 1.2/OS X 10.5@
886 int /* O - 1 on success, 0 on failure */
887 cupsArrayRemove(cups_array_t
*a
, /* I - Array */
888 void *e
) /* I - Element */
890 ssize_t i
, /* Looping var */
891 current
; /* Current element */
892 int diff
; /* Difference */
896 * Range check input...
903 * See if the element is in the array...
906 if (!a
->num_elements
)
909 current
= cups_array_find(a
, e
, a
->current
, &diff
);
914 * Yes, now remove it...
920 (a
->freefunc
)(a
->elements
[current
], a
->data
);
922 if (current
< a
->num_elements
)
923 memmove(a
->elements
+ current
, a
->elements
+ current
+ 1,
924 (size_t)(a
->num_elements
- current
) * sizeof(void *));
926 if (current
<= a
->current
)
929 if (current
< a
->insert
)
931 else if (current
== a
->insert
)
934 for (i
= 0; i
< a
->num_saved
; i
++)
935 if (current
<= a
->saved
[i
])
938 if (a
->num_elements
<= 1)
946 * 'cupsArrayRestore()' - Reset the current element to the last @link cupsArraySave@.
948 * @since CUPS 1.2/OS X 10.5@
951 void * /* O - New current element */
952 cupsArrayRestore(cups_array_t
*a
) /* I - Array */
957 if (a
->num_saved
<= 0)
961 a
->current
= a
->saved
[a
->num_saved
];
963 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
964 return (a
->elements
[a
->current
]);
971 * 'cupsArraySave()' - Mark the current element for a later @link cupsArrayRestore@.
973 * The current element is undefined until you call @link cupsArrayFind@,
974 * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
975 * to set the current element.
977 * The save/restore stack is guaranteed to be at least 32 elements deep.
979 * @since CUPS 1.2/OS X 10.5@
982 int /* O - 1 on success, 0 on failure */
983 cupsArraySave(cups_array_t
*a
) /* I - Array */
988 if (a
->num_saved
>= _CUPS_MAXSAVE
)
991 a
->saved
[a
->num_saved
] = a
->current
;
999 * 'cupsArrayUserData()' - Return the user data for an array.
1001 * @since CUPS 1.2/OS X 10.5@
1004 void * /* O - User data */
1005 cupsArrayUserData(cups_array_t
*a
) /* I - Array */
1015 * 'cups_array_add()' - Insert or append an element to the array.
1017 * @since CUPS 1.2/OS X 10.5@
1020 static int /* O - 1 on success, 0 on failure */
1021 cups_array_add(cups_array_t
*a
, /* I - Array */
1022 void *e
, /* I - Element to add */
1023 int insert
) /* I - 1 = insert, 0 = append */
1025 int i
, /* Looping var */
1026 current
; /* Current element */
1027 int diff
; /* Comparison with current element */
1030 DEBUG_printf(("7cups_array_add(a=%p, e=%p, insert=%d)", a
, e
, insert
));
1033 * Verify we have room for the new element...
1036 if (a
->num_elements
>= a
->alloc_elements
)
1039 * Allocate additional elements; start with 16 elements, then
1040 * double the size until 1024 elements, then add 1024 elements
1044 void **temp
; /* New array elements */
1045 int count
; /* New allocation count */
1048 if (a
->alloc_elements
== 0)
1051 temp
= malloc((size_t)count
* sizeof(void *));
1055 if (a
->alloc_elements
< 1024)
1056 count
= a
->alloc_elements
* 2;
1058 count
= a
->alloc_elements
+ 1024;
1060 temp
= realloc(a
->elements
, (size_t)count
* sizeof(void *));
1063 DEBUG_printf(("9cups_array_add: count=" CUPS_LLFMT
, CUPS_LLCAST count
));
1067 DEBUG_puts("9cups_array_add: allocation failed, returning 0");
1071 a
->alloc_elements
= count
;
1076 * Find the insertion point for the new element; if there is no
1077 * compare function or elements, just add it to the beginning or end...
1080 if (!a
->num_elements
|| !a
->compare
)
1083 * No elements or comparison function, insert/append as needed...
1087 current
= 0; /* Insert at beginning */
1089 current
= a
->num_elements
; /* Append to the end */
1094 * Do a binary search for the insertion point...
1097 current
= cups_array_find(a
, e
, a
->insert
, &diff
);
1102 * Insert after the current element...
1110 * Compared equal, make sure we add to the begining or end of
1111 * the current run of equal elements...
1119 * Insert at beginning of run...
1122 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
1129 * Append at end of run...
1136 while (current
< a
->num_elements
&&
1137 !(*(a
->compare
))(e
, a
->elements
[current
], a
->data
));
1143 * Insert or append the element...
1146 if (current
< a
->num_elements
)
1149 * Shift other elements to the right...
1152 memmove(a
->elements
+ current
+ 1, a
->elements
+ current
,
1153 (size_t)(a
->num_elements
- current
) * sizeof(void *));
1155 if (a
->current
>= current
)
1158 for (i
= 0; i
< a
->num_saved
; i
++)
1159 if (a
->saved
[i
] >= current
)
1162 DEBUG_printf(("9cups_array_add: insert element at index " CUPS_LLFMT
, CUPS_LLCAST current
));
1166 DEBUG_printf(("9cups_array_add: append element at " CUPS_LLFMT
, CUPS_LLCAST current
));
1171 if ((a
->elements
[current
] = (a
->copyfunc
)(e
, a
->data
)) == NULL
)
1173 DEBUG_puts("8cups_array_add: Copy function returned NULL, returning 0");
1178 a
->elements
[current
] = e
;
1181 a
->insert
= current
;
1184 for (current
= 0; current
< a
->num_elements
; current
++)
1185 DEBUG_printf(("9cups_array_add: a->elements[" CUPS_LLFMT
"]=%p", CUPS_LLCAST current
, a
->elements
[current
]));
1188 DEBUG_puts("9cups_array_add: returning 1");
1195 * 'cups_array_find()' - Find an element in the array.
1198 static int /* O - Index of match */
1199 cups_array_find(cups_array_t
*a
, /* I - Array */
1200 void *e
, /* I - Element */
1201 int prev
, /* I - Previous index */
1202 int *rdiff
) /* O - Difference of match */
1204 int left
, /* Left side of search */
1205 right
, /* Right side of search */
1206 current
, /* Current element */
1207 diff
; /* Comparison with current element */
1210 DEBUG_printf(("7cups_array_find(a=%p, e=%p, prev=%d, rdiff=%p)", a
, e
, prev
,
1216 * Do a binary search for the element...
1219 DEBUG_puts("9cups_array_find: binary search");
1221 if (prev
>= 0 && prev
< a
->num_elements
)
1224 * Start search on either side of previous...
1227 if ((diff
= (*(a
->compare
))(e
, a
->elements
[prev
], a
->data
)) == 0 ||
1228 (diff
< 0 && prev
== 0) ||
1229 (diff
> 0 && prev
== (a
->num_elements
- 1)))
1232 * Exact or edge match, return it!
1235 DEBUG_printf(("9cups_array_find: Returning %d, diff=%d", prev
, diff
));
1244 * Start with previous on right side...
1253 * Start wih previous on left side...
1257 right
= a
->num_elements
- 1;
1263 * Start search in the middle...
1267 right
= a
->num_elements
- 1;
1272 current
= (left
+ right
) / 2;
1273 diff
= (*(a
->compare
))(e
, a
->elements
[current
], a
->data
);
1275 DEBUG_printf(("9cups_array_find: left=%d, right=%d, current=%d, diff=%d",
1276 left
, right
, current
, diff
));
1285 while ((right
- left
) > 1);
1290 * Check the last 1 or 2 elements...
1293 if ((diff
= (*(a
->compare
))(e
, a
->elements
[left
], a
->data
)) <= 0)
1297 diff
= (*(a
->compare
))(e
, a
->elements
[right
], a
->data
);
1305 * Do a linear pointer search...
1308 DEBUG_puts("9cups_array_find: linear search");
1312 for (current
= 0; current
< a
->num_elements
; current
++)
1313 if (a
->elements
[current
] == e
)
1321 * Return the closest element and the difference...
1324 DEBUG_printf(("8cups_array_find: Returning %d, diff=%d", current
, diff
));