25#define Item(b) (base_char+(b)*width)
26#define IsBefore(x,y) ((cmp(Item(x),Item(y)))<0)
27#define Exchange(x,y) {\
28 memcpy(tmp,Item(x),width);\
29 memcpy(Item(x),Item(y),width);\
30 memcpy(Item(y),tmp,width);\
34void QuickSort(
void *base,
size_t nelem,
size_t width,
35 int (*cmp)(
const void *,
const void *))
37 struct __QuickSortStack
47 char * base_char = (
char *) base;
48 const size_t stackSize = 128;
50 __QuickSortStack * stack =
new __QuickSortStack[stackSize];
51 char * tmp =
new char [width];
53 if ((stack == NULL) || (tmp == NULL))
54 error(
"Out of memory in QuickSort routine");
59 const size_t Threshold = 7;
65 size_t scanl, scanr, pivot;
74 if (r - l > Threshold)
108 while ((scanl < r) && IsBefore(scanl, pivot))
111 while ((scanr > l) && IsBefore(pivot, scanr))
118 Exchange(scanl, scanr);
128 Exchange(pivot, scanl);
139 if (stackIdx == stackSize)
140 error(
"Out of Stack in QuickSort routine");
142 stack[stackIdx].left = l;
143 stack[stackIdx].right = scanl - 1;
155 if (stackIdx == stackSize)
156 error(
"Out of Stack in QuickSort routine");
158 stack[stackIdx].left = scanl + 1;
159 stack[stackIdx].right = r;
171 l = stack[stackIdx].left;
172 r = stack[stackIdx].right;
184#define Item2(b) (base_char2+(b)*width)
185#define Exchange2(x,y) {\
186 memcpy(tmp,Item(x),width);\
187 memcpy(Item(x),Item(y),width);\
188 memcpy(Item(y),tmp,width);\
189 memcpy(tmp,Item2(x),width);\
190 memcpy(Item2(x),Item2(y),width);\
191 memcpy(Item2(y),tmp,width);\
195void QuickSort2(
void *base,
void *base2,
size_t nelem,
size_t width,
196 int (*cmp)(
const void *,
const void *))
198 struct __QuickSortStack
208 char * base_char = (
char *) base;
209 char * base_char2 = (
char *) base2;
210 const size_t stackSize = 128;
212 __QuickSortStack * stack =
new __QuickSortStack[stackSize];
213 char * tmp =
new char [width];
215 if ((stack == NULL) || (tmp == NULL))
216 error(
"Out of memory in QuickSort routine");
221 const size_t Threshold = 7;
227 size_t scanl, scanr, pivot;
236 if (r - l > Threshold)
242 if (IsBefore(mid, l))
248 if (IsBefore(r, mid))
254 Exchange2(mid, pivot);
270 while ((scanl < r) && IsBefore(scanl, pivot))
273 while ((scanr > l) && IsBefore(pivot, scanr))
280 Exchange2(scanl, scanr);
290 Exchange2(pivot, scanl);
301 if (stackIdx == stackSize)
302 error(
"Out of Stack in QuickSort routine");
304 stack[stackIdx].left = l;
305 stack[stackIdx].right = scanl - 1;
317 if (stackIdx == stackSize)
318 error(
"Out of Stack in QuickSort routine");
320 stack[stackIdx].left = scanl + 1;
321 stack[stackIdx].right = r;
333 l = stack[stackIdx].left;
334 r = stack[stackIdx].right;
346void * BinarySearch(
const void *key,
const void *base,
347 size_t nelem,
size_t width,
348 int (*cmp)(
const void *,
const void *))
353 char * base_char = (
char *) base;
356 int right = nelem - 1;
358 while (right >= left)
360 int probe = (left + right) / 2;
361 int test = cmp(key, Item(probe));
364 return (
void *) Item(probe);