7 /* Converts a string representation of a signed decimal integer
8 in S into an `int', which is returned. */
17 /* Skip white space. */
18 while (isspace ((unsigned char) *s))
31 /* Parse digits. We always initially parse the value as
32 negative, and then make it positive later, because the
33 negative range of an int is bigger than the positive range
34 on a 2's complement system. */
35 for (value = 0; isdigit (*s); s++)
36 value = value * 10 - (*s - '0');
43 /* Compares A and B by calling the AUX function. */
45 compare_thunk (const void *a, const void *b, void *aux)
47 int (**compare) (const void *, const void *) = aux;
48 return (*compare) (a, b);
51 /* Sorts ARRAY, which contains CNT elements of SIZE bytes each,
52 using COMPARE. When COMPARE is passed a pair of elements A
53 and B, respectively, it must return a strcmp()-type result,
54 i.e. less than zero if A < B, zero if A == B, greater than
55 zero if A > B. Runs in O(n lg n) time and O(1) space in
58 qsort (void *array, size_t cnt, size_t size,
59 int (*compare) (const void *, const void *))
61 sort (array, cnt, size, compare_thunk, &compare);
64 /* Swaps elements with 1-based indexes A_IDX and B_IDX in ARRAY
65 with elements of SIZE bytes each. */
67 do_swap (unsigned char *array, size_t a_idx, size_t b_idx, size_t size)
69 unsigned char *a = array + (a_idx - 1) * size;
70 unsigned char *b = array + (b_idx - 1) * size;
73 for (i = 0; i < size; i++)
75 unsigned char t = a[i];
81 /* Compares elements with 1-based indexes A_IDX and B_IDX in
82 ARRAY with elements of SIZE bytes each, using COMPARE to
83 compare elements, passing AUX as auxiliary data, and returns a
84 strcmp()-type result. */
86 do_compare (unsigned char *array, size_t a_idx, size_t b_idx, size_t size,
87 int (*compare) (const void *, const void *, void *aux),
90 return compare (array + (a_idx - 1) * size, array + (b_idx - 1) * size, aux);
93 /* "Float down" the element with 1-based index I in ARRAY of CNT
94 elements of SIZE bytes each, using COMPARE to compare
95 elements, passing AUX as auxiliary data. */
97 heapify (unsigned char *array, size_t i, size_t cnt, size_t size,
98 int (*compare) (const void *, const void *, void *aux),
103 /* Set `max' to the index of the largest element among I
104 and its children (if any). */
106 size_t right = 2 * i + 1;
108 if (left <= cnt && do_compare (array, left, max, size, compare, aux) > 0)
111 && do_compare (array, right, max, size, compare, aux) > 0)
114 /* If the maximum value is already in element I, we're
119 /* Swap and continue down the heap. */
120 do_swap (array, i, max, size);
125 /* Sorts ARRAY, which contains CNT elements of SIZE bytes each,
126 using COMPARE to compare elements, passing AUX as auxiliary
127 data. When COMPARE is passed a pair of elements A and B,
128 respectively, it must return a strcmp()-type result, i.e. less
129 than zero if A < B, zero if A == B, greater than zero if A >
130 B. Runs in O(n lg n) time and O(1) space in CNT. */
132 sort (void *array, size_t cnt, size_t size,
133 int (*compare) (const void *, const void *, void *aux),
138 ASSERT (array != NULL || cnt == 0);
139 ASSERT (compare != NULL);
143 for (i = cnt / 2; i > 0; i--)
144 heapify (array, i, cnt, size, compare, aux);
147 for (i = cnt; i > 1; i--)
149 do_swap (array, 1, i, size);
150 heapify (array, 1, i - 1, size, compare, aux);
154 /* Searches ARRAY, which contains CNT elements of SIZE bytes
155 each, for the given KEY. Returns a match is found, otherwise
156 a null pointer. If there are multiple matches, returns an
157 arbitrary one of them.
159 ARRAY must be sorted in order according to COMPARE.
161 Uses COMPARE to compare elements. When COMPARE is passed a
162 pair of elements A and B, respectively, it must return a
163 strcmp()-type result, i.e. less than zero if A < B, zero if A
164 == B, greater than zero if A > B. */
166 bsearch (const void *key, const void *array, size_t cnt,
167 size_t size, int (*compare) (const void *, const void *))
169 return binary_search (key, array, cnt, size, compare_thunk, &compare);
172 /* Searches ARRAY, which contains CNT elements of SIZE bytes
173 each, for the given KEY. Returns a match is found, otherwise
174 a null pointer. If there are multiple matches, returns an
175 arbitrary one of them.
177 ARRAY must be sorted in order according to COMPARE.
179 Uses COMPARE to compare elements, passing AUX as auxiliary
180 data. When COMPARE is passed a pair of elements A and B,
181 respectively, it must return a strcmp()-type result, i.e. less
182 than zero if A < B, zero if A == B, greater than zero if A >
185 binary_search (const void *key, const void *array, size_t cnt, size_t size,
186 int (*compare) (const void *, const void *, void *aux),
189 const unsigned char *first = array;
190 const unsigned char *last = array + size * cnt;
194 size_t range = (last - first) / size;
195 const unsigned char *middle = first + (range / 2) * size;
196 int cmp = compare (key, middle, aux);
201 first = middle + size;
203 return (void *) middle;