/* a-wada/qsortlib/ccg/qsortskb.c Oct. 16, 2006 */ /* Copyright (c) 2006 Akira Wada */ /* Quick sort compatible with "qsort (); in " */ /* efficiency by reducing the times of key comparisons and */ /* word_mode_swapping for word_aligned object */ /* prevention from the degeneration caused by peculiar input */ /* This qsort is not stable, but could avoid the bad behavior by many */ /* equal sort-keys. For stability, add a unique-key to compare-function. */ /* If the object to be sorted is an array of pointers to structs with */ /* an unsigned integer key, set the 4'th argument to NULL and the 3'rd */ /* to byte-position of the key in the struct, to call RADIX-SORT. */ /* For example : kps = 16; qsort (pv, n, kps, NULL); */ #include void srandom (unsigned long); unsigned long random (void); void radixspi (void *, size_t, size_t); #define MDT 16 /* threshold for median of the 5 or the more, MDT >= 8 */ #define MDA 2 /* adjusting threshold slightly, MDT + MDA >= 4 */ #define MDM 2 /* multiplier for threshold, MDM >= 2 */ #define COMP(i, j) (*qcmp)(i, j) #define SZI sizeof (int) #define SWAP(i, j) do { \ if (al < 0) \ t = *((int *) (i)), \ *((int *) (i)) = *((int *) (j)), \ *((int *) (j)) = t; \ else (*swapx) (i, j, rl);} while (0) #define ROTATE(i, j, k) do { \ if (al < 0) \ t = *((int *) (i)), \ *((int *) (i)) = *((int *) (j)), \ *((int *) (j)) = *((int *) (k)), \ *((int *) (k)) = t; \ else (*rottx) (i, j, k, rl);} while (0) #define PUSH(x, y) *p = x, *(p + 1) = y, p += 2 #define EMPTY (s >= p) #define POP(y, x) y = *(p - 1), x = *(p - 2), p -= 2 #define DGT 128 /* threshold of p-size for checking degeneration */ #define DGV 16 /* degeneration assumed if the smaller < DGL */ #define DGM 0 /* threshold for selecting no median */ #define DGS 1 /* threshold for samples distributed uniformly */ #define DGU 2 /* threshold for sampling at random */ #define DGL ((unsigned) psz / DGV) * rl #define RDMSMPL(m, i, j) if (m != (n = i + rl * ( \ random () % ((unsigned) (j - (i)) / rl + 1)))) SWAP (m, n) typedef int (*ftp) (const void *, const void *); typedef char * ptrtyp; typedef void (*swapt) (char *, char *, size_t); typedef void (*rottt) (char *, char *, char *, size_t); static void swapw (char *, char *, size_t); static void swapc (char *, char *, size_t); static void rotatew (char *, char *, char *, size_t); static void rotatec (char *, char *, char *, size_t); void qsort (void *av, size_t rn, size_t rl, ftp qcmp) { ptrtyp l, r, m, i, j, k, n, s[sizeof (size_t) * 8 * 2], *p = s; int psz, thr, cst, c, nsp, itv, dgn = 0, al, t; swapt swapx; rottt rottx; if (qcmp == (ftp) 0) radixspi (av, rn, rl); else /* call RADIX SORT */ if (rn > 1 && rl > 0) { /* do QUICK SORT */ if ((al =((int) av | rl) & (SZI - 1)) == 0) { if (rl == SZI) al = -1; swapx = swapw, rottx = rotatew;} else swapx = swapc, rottx = rotatec; l = i = (char *) av, r = j = i + (rn - 1) * rl; for ( ; ; ) { /* initialize for current partition */ m = i + ((unsigned) (psz = (j - i) / rl) / 2) * rl, thr = MDT, psz -= (MDA), cst = 1; if (psz <= MDT || dgn <= DGM || dgn > DGS) { /* if not No-Median */ if (psz > MDT && dgn > DGS) { /* if degeneration assumed */ if (dgn <= DGU) { /* samples distributed uniformly */ nsp = 3; while (psz > thr) thr *= MDM, nsp += 2; itv = ((unsigned) psz / (nsp - 1)) * rl; k = i, n = j; for (thr = MDT; psz > thr; thr *= MDM) { i += rl, k += itv; SWAP (i, k); j -= rl, n -= itv; SWAP (n, j);}} else { /* samples at random */ if (dgn == DGU + 1) dgn++, srandom (time (0)); for ((unsigned) thr /= MDM; psz > thr; thr *= MDM) { RDMSMPL (i, i, j); i += rl; RDMSMPL (j, i, j); j -= rl;} RDMSMPL (m, i, j);} i = l, j = r, thr = MDT;} for ( ; ; ) { /* bring median of samples to middle */ if (COMP (m, j) <= 0) { if (i < m && COMP (i, m) > 0) { n = i, k = j; do if (COMP (k, n) < 0) n = k; while ((k += rl) <= r); if (n == i) SWAP (m, i); else ROTATE (m, n, i); cst = 0;}} else { if (i >= m || COMP (i, m) > 0) SWAP (i, j); else { n = j, k = i; do if (COMP (k, n) > 0) n = k; while ((k -= rl) >= l); if (n == j) SWAP (m, j); else ROTATE (m, n, j);} cst = 0;} i += rl, j -= rl; if (psz > thr) thr *= MDM; else break;}} if (cst != 0 && psz > MDT) { /* check sorted already */ k = l, n = k + rl; while (k < r && COMP (k, n) <= 0) k = n, n += rl; if (k >= r) i = j; else if (k >= m) i = m;} if (i < j) { /* do partitioning by middle as pivot */ for (k = l; ; ) { /* gathering equal keys to left end */ while (i < m && (c = COMP (i, m)) <= 0) { if (c == 0) { if (k < i) SWAP (k, i); k += rl;} i += rl;} while (m < j && (c = COMP (m, j)) < 0) j -= rl; if (i >= j) break; if (c != 0) SWAP (i, j); else { if (k < i) ROTATE (k, j, i); else SWAP (i, j); k += rl;} if (m == j) m = i, j -= rl; else if (i == m) m = j, i += rl; else j -= rl, i += rl;} i -= rl; if (l < k) { /* move equal keys to where to be */ for (n = l; n < k && k <= i; n += rl, i -= rl) SWAP (n, i); if (k > i) i = n - rl;} if (i - l < r - (j += rl)) { /* select for next iteration */ if (psz >= DGT && l + DGL > j) dgn++; if (l >= i) l = j; else PUSH (j, r), r = i;} else { if (psz >= DGT && i + DGL > r) dgn++; if (j >= r) r = i; else PUSH (l, i), l = j;} if ((i = l) < (j = r)) continue;} /* pop up next from stack */ if (!EMPTY) POP (j, i), r = j, l = i; else break;}}} /* a-wada/qsortlib/ccg/qsortskb.c end */ /* a-wada/qsortlib/ccg/swaprot.c Sep. 20, 1997 */ /* Copyright (c) 1997 Akira Wada */ static void swapw (char *i, char *j, size_t rl) { register int t, w = rl; do w -= SZI, t = *((int *) (i + w)), *((int *) (i + w)) = *((int *) (j + w)), *((int *) (j + w)) = t; while (w > 0);} static void swapc (char *i, char *j, size_t rl) { register char s; int w = rl; do --w, s = *(i + w), *(i + w) = *(j + w), *(j + w) = s; while (w > 0);} static void rotatew (char *i, char *j, char *k, size_t rl) { register int t, w = rl; do w -= SZI, t = *((int *) (i + w)), *((int *) (i + w)) = *((int *) (j + w)), *((int *) (j + w)) = *((int *) (k + w)), *((int *) (k + w)) = t; while (w > 0);} static void rotatec (char *i, char *j, char *k, size_t rl) { register char s; int w = rl; do --w, s = *(i + w), *(i + w) = *(j + w), *(j + w) = *(k + w), *(k + w) = s; while (w > 0);} /* a-wada/qsortlib/ccg/swaprot.c end */ /*----------------------------------------------------------------------------** *source codes on : ** seed for fastest arrangement 1148455125 ** radixspi ; http://www.mars.dti.ne.jp/a-wada/qsortlib/ccn/radixspi-ar.c (modified for array of pointers to structs with u_int key), from http://www.cubic.org/~submissive/sourcerer/download/radix_ar.c (original for array of unsigned longs by Andre Reinald) srandom, random ; http://www.mars.dti.ne.jp/a-wada/qsortlib/ccn/random.c (modified for portability (type-definition)), from ftp://ftp.freebsd.org/pub/FreeBSD/FreeBSD-current/src/sys/libkern/random.c **----------------------------------------------------------------------------*/