/* a-wada/qsortlib/ccg/qsortsk.c May 13, 2002 */ /* Copyright (c) 2000 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 #include #undef random() /* if borland bcc32 */ void srandom (unsigned long); /* if not in */ unsigned long random (void); /* if not in */ void radixspi (void *, size_t, size_t); static void swapw (char *, char *, size_t); static void rotatew (char *, char *, char *, size_t); static void swapc (char *, char *, size_t); static void rotatec (char *, char *, char *, 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 SWPWRK int al, t; swtp swapx; rttp rotatex #define SZI sizeof (int) #define CHKALIGN() do { \ if ((al = ((int) av | rl) & (SZI - 1)) == 0) { \ if ((int) rl == SZI) al = -1; \ swapx = swapw, rotatex = rotatew;} else \ swapx = swapc, rotatex = rotatec;} while (0) #define SWAP(i, j) do { \ if (al >= 0) (*swapx) (i, j, rl); else \ t = *((int *) i), *((int *) i) = *((int *) j), \ *((int *) j) = t;} while (0) #define ROTATE(i, j, k) do { \ if (al >= 0) (*rotatex) (i, j, k, rl); else \ t = *((int *) i), *((int *) i) = *((int *) j), \ *((int *) j) = *((int *) k), *((int *) k) = t;} while (0) #define DGT 128 /* <- 256 threshold of p-size for checking degeneration */ #define DGV 16 /* 16 degeneration assumed if the smaller < DGL */ #define DGM 0 /* 0 threshold for selecting no median */ #define DGS 1 /* <- 2 threshold for samples distributed uniformly */ #define DGU 2 /* <- 4 threshold for sampling at random */ #define DGL ((unsigned) psz / DGV) * rl #define DEFDGN int dgn = 0, nsp, itv #define CKDGNR(s, e) if (psz >= DGT && s + DGL > e) dgn++ #define NO_MED (psz > MDT && DGM < dgn && dgn <= DGS) #define SYMPTM (psz > MDT && dgn > DGS) #define XCSMPL() do { \ if (dgn <= DGU) { /* samples distributed uniformly */\ nsp = 3; while (psz > thr) thr *= MDM, nsp += 2; \ itv = ((unsigned) psz / (nsp - 1)) * rl; k = l, n = r; \ 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 (thr = (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;} while (0) #define RDMSMPL(x, s, e) if (x != (n = s + rl * ( \ random () % ((unsigned) (e - (s)) / rl + 1)))) SWAP (x, n) #define FINDXC(MIN, i, j, r, m) do { /* median to middle */\ n = i, k = j; do \ if (COMP (k, n) MIN##i 0) n = k; while ((k MIN##j rl) MIN##r r); \ if (n == i) SWAP (m, i); else ROTATE (m, n, i);} while (0) #define MINi < #define MAXj > #define MINj += #define MAXi -= #define MINr <= #define MAXl >= #define CKSRTD(l, r) if (psz > MDT) do { \ 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;} while (0) #define STACK ptrtyp s[STKSZ], *p = s #define STKSZ sizeof (size_t) * 8 * 2 #define PUSH(x, y) *(p++) = x, *(p++) = y #define EMPTY (s >= p) #define POP(y, x) y = *(--p), x = *(--p) #define DEFWRK SWPWRK; DEFDGN; STACK typedef int (*ftp) (const void *, const void *); typedef void (*swtp) (char *, char *, size_t); typedef void (*rttp) (char *, char *, char *, size_t); typedef char * ptrtyp; void qsort (void *av, size_t rn, size_t rl, ftp qcmp) { ptrtyp l, r, m, i, j, k, n; int psz, thr, cst, c; DEFWRK; if (qcmp == (ftp) 0) radixspi (av, rn, rl); else /* call RADIX SORT */ if (rn > 1 && rl > 0) { /* do QUICK SORT */ l = (char *) av, r = l + (rn - 1) * rl; CHKALIGN (); for ( ; ; ) { /* initialize for current partition */ m = l + ((unsigned) (psz = (r - l) / rl) / 2) * rl, i = l, j = r, thr = MDT, psz -= (MDA), cst = 1; if (!NO_MED) { if (SYMPTM) XCSMPL (); for ( ; ; ) { /* bring median of samples to middle */ if (COMP (m, j) <= 0) { if (i < m && COMP (i, m) > 0) { FINDXC (MIN, i, j, r, m); cst = 0;}} else { if (i >= m || COMP (i, m) > 0) SWAP (i, j); else FINDXC (MAX, j, i, l, m); cst = 0;} i += rl, j -= rl; if (psz > thr) thr *= MDM; else break;}} if (cst != 0) CKSRTD (l, r); if (i < j) { /* do partitioning by middle as pivot gathering */ for (k = l, n = r; ; ) { /* equal keys to both 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) { if (c == 0) { if (j < n) SWAP (j, n); n -= rl;} j -= rl;} if (i < j) SWAP (i, j); else break; 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 (m = l; m < k && k <= i; ) { SWAP (m, i); m += rl, i -= rl;} if (k > i) i = m - rl;} j += rl; if (n < r) { for (m = r; n < m && j <= n; ) { SWAP (j, m); j += rl, m -= rl;} if (j > n) j = m + rl;} if (i - l < r - j) { /* select for next iteration */ CKDGNR (l, j); if (l >= i) l = j; else { PUSH (j, r), r = i; continue;}} else { CKDGNR (i, r); if (j >= r) r = i; else { PUSH (l, i), l = j; continue;}} if (l < r) continue;} if (!EMPTY) POP (r, l); else break;}}} /* pop up next from stack */ /* a-wada/qsortlib/ccg/qsorts.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) { int t; char *e = j + rl; do t = *((int *) i), *((int *) i) = *((int *) j), i += SZI, *((int *) j) = t, j += SZI; while (j < e);} static void rotatew (char *i, char *j, char *k, size_t rl) { int t; char *e = k + rl; do t = *((int *) i), *((int *) i) = *((int *) j), i += SZI, *((int *) j) = *((int *) k), j += SZI, *((int *) k) = t, k += SZI; while (k < e);} static void swapc (char *i, char *j, size_t rl) { char t, *e = j + rl; do t = *i, *(i++) = *j, *(j++) = t; while (j < e);} static void rotatec (char *i, char *j, char *k, size_t rl) { char t, *e = k + rl; do t = *i, *(i++) = *j, *(j++) = *k, *(k++) = t; while (k < e);} /* a-wada/qsortlib/ccg/swaprot.c end */ /*----------------------------------------------------------------------------** *source codes on : 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 **----------------------------------------------------------------------------*/