/* median-3 variant of quicksort - coded by John Garnett. using this quicksort rather than the builtin one because most builtin implementations choke on non-deterministic compare functions (and we can't control what compare function is used since it is at the mudlib level). Based on algorithm appearing in _Data Structures and Algorithm Analysis_ by Cawnthorpe. */ #ifdef __386BSD__ #include <sys/types.h> #include <string.h> #endif #include "config.h" #include "lint.h" #include "mudlib_stats.h" #include "interpret.h" #define LEN sizeof(struct svalue) #define MAX_LEN 1000 INLINE static void doSwap(one, two, size) void *one, *two; int size; { static char buf[MAX_LEN]; memcpy(buf, one, size); memcpy(one, two, size); memcpy(two, buf, size); } /* qsort adapted from page 87 of K&R 2nd edition */ void qSort(v, left, right, size, rightmost, compar) void *v; int left, right, size, rightmost; int (*compar) PROT((void *, void *)); { int i, last, szleft; if ((left >= right) || (left < 0) || (right > rightmost) || (right < 0)) { return; } szleft = size * left; doSwap((char *)v + szleft, (char *)v + (size * ((left + right) / 2)), size); last = left; for (i = left + 1; i <= right; i++) { if (compar((char *)v + (size * i), (char *)v + szleft) < 0) { doSwap((char *)v + (size * ++last), (char *)v + (size * i), size); } } doSwap((char *)v + szleft, (char *)v + (size * last), size); qSort(v, left, last - 1, size, rightmost, compar); qSort(v, last + 1, right, size, rightmost, compar); } void quickSort(a, nmemb, size, compar) void *a; int nmemb, size; int (*compar) PROT((void *, void *)); { if (nmemb < 2) { return; } qSort(a, 0, nmemb - 1, size, nmemb - 1, compar); }