27 #define SWAP(a, b, size) \ 30 size_t __size = (size); \ 31 char *__a = (a), *__b = (b); \ 37 } while (--__size > 0); \ 56 #define STACK_SIZE (CHAR_BIT * sizeof(size_t)) 57 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top)) 58 #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi))) 59 #define STACK_NOT_EMPTY (stack < top) 61 int less (
const void *,
const void *,
void *);
88 _quicksort (
void *
const pbase,
size_t total_elems,
size_t size,
89 int (*cmp)(
const void *,
const void *,
void *),
void *
arg)
91 char *base_ptr = (
char *) pbase;
102 char *hi = &lo[size * (total_elems - 1)];
119 char *mid = lo + size * ((hi - lo) / size >> 1);
121 if (
less ((
void *) mid, (
void *) lo, arg) < 0)
122 SWAP (mid, lo, size);
123 if (
less ((
void *) hi, (
void *) mid, arg) < 0)
124 SWAP (mid, hi, size);
127 if (
less ((
void *) mid, (
void *) lo, arg) < 0)
128 SWAP (mid, lo, size);
131 left_ptr = lo + size;
132 right_ptr = hi - size;
139 while (
less ((
void *) left_ptr, (
void *) mid, arg) < 0)
142 while (
less ((
void *) mid, (
void *) right_ptr, arg) < 0)
145 if (left_ptr < right_ptr)
147 SWAP (left_ptr, right_ptr, size);
150 else if (mid == right_ptr)
155 else if (left_ptr == right_ptr)
162 while (left_ptr <= right_ptr);
169 if ((
size_t) (right_ptr - lo) <= max_thresh)
171 if ((
size_t) (hi - left_ptr) <= max_thresh)
178 else if ((
size_t) (hi - left_ptr) <= max_thresh)
181 else if ((right_ptr - lo) > (hi - left_ptr))
184 PUSH (lo, right_ptr);
202 #define min(x, y) ((x) < (y) ? (x) : (y)) 205 char *
const end_ptr = &base_ptr[size * (total_elems - 1)];
206 char *tmp_ptr = base_ptr;
207 char *thresh =
min(end_ptr, base_ptr + max_thresh);
214 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
215 if (
less ((
void *) run_ptr, (
void *) tmp_ptr, arg) < 0)
218 if (tmp_ptr != base_ptr)
219 SWAP (tmp_ptr, base_ptr, size);
223 run_ptr = base_ptr + size;
224 while ((run_ptr += size) <= end_ptr)
226 tmp_ptr = run_ptr - size;
227 while (
less ((
void *) run_ptr, (
void *) tmp_ptr, arg) < 0)
231 if (tmp_ptr != run_ptr)
235 trav = run_ptr + size;
236 while (--trav >= run_ptr)
241 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
void * top(node_stack *head)
void _quicksort(void *const pbase, size_t total_elems, size_t size, int(*cmp)(const void *, const void *, void *), void *arg)
int less(const void *, const void *, void *)