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) 87 _quicksort (
void *
const pbase,
size_t total_elems,
size_t size,
88 int (*cmp)(
const void *,
const void *,
void *),
void *
arg)
90 char *base_ptr = (
char *) pbase;
101 char *hi = &lo[size * (total_elems - 1)];
118 char *mid = lo + size * ((hi - lo) / size >> 1);
120 if ((*cmp) ((
void *) mid, (
void *) lo, arg) < 0)
121 SWAP (mid, lo, size);
122 if ((*cmp) ((
void *) hi, (
void *) mid, arg) < 0)
123 SWAP (mid, hi, size);
126 if ((*cmp) ((
void *) mid, (
void *) lo, arg) < 0)
127 SWAP (mid, lo, size);
130 left_ptr = lo + size;
131 right_ptr = hi - size;
138 while ((*cmp) ((
void *) left_ptr, (
void *) mid, arg) < 0)
141 while ((*cmp) ((
void *) mid, (
void *) right_ptr, arg) < 0)
144 if (left_ptr < right_ptr)
146 SWAP (left_ptr, right_ptr, size);
149 else if (mid == right_ptr)
154 else if (left_ptr == right_ptr)
161 while (left_ptr <= right_ptr);
168 if ((
size_t) (right_ptr - lo) <= max_thresh)
170 if ((
size_t) (hi - left_ptr) <= max_thresh)
177 else if ((
size_t) (hi - left_ptr) <= max_thresh)
180 else if ((right_ptr - lo) > (hi - left_ptr))
183 PUSH (lo, right_ptr);
201 #define min(x, y) ((x) < (y) ? (x) : (y)) 204 char *
const end_ptr = &base_ptr[size * (total_elems - 1)];
205 char *tmp_ptr = base_ptr;
206 char *thresh =
min(end_ptr, base_ptr + max_thresh);
213 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
214 if ((*cmp) ((
void *) run_ptr, (
void *) tmp_ptr, arg) < 0)
217 if (tmp_ptr != base_ptr)
218 SWAP (tmp_ptr, base_ptr, size);
222 run_ptr = base_ptr + size;
223 while ((run_ptr += size) <= end_ptr)
225 tmp_ptr = run_ptr - size;
226 while ((*cmp) ((
void *) run_ptr, (
void *) tmp_ptr, arg) < 0)
230 if (tmp_ptr != run_ptr)
234 trav = run_ptr + size;
235 while (--trav >= run_ptr)
240 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)