Return to qsort.c CVS log

Up to [Research Unix] / researchv10no / libc / gen

Annotation of researchv10no/libc/gen/qsort.c, revision 1.1.1.1

1.1       root        1: /* qsort -- qsort interface implemented by faster quicksort */
                      2: 
                      3: #define SWAPINIT(a, es) swaptype =         \
                      4:     (a-(char*)0 | es) % sizeof(long) ? 2 : es > sizeof(long) ? 1 : 0;
                      5: #define swapcode(TYPE, parmi, parmj, n) {  \
                      6:     register TYPE *pi = (TYPE *) (parmi);  \
                      7:     register TYPE *pj = (TYPE *) (parmj);  \
                      8:     do {                                   \
                      9:         register TYPE t = *pi;             \
                     10:         *pi++ = *pj;                       \
                     11:         *pj++ = t;                         \
                     12:     } while ((n -= sizeof(TYPE)) > 0);     \
                     13: }
                     14: #include <stddef.h>
                     15: static void swapfunc(char *a, char *b, size_t n, int swaptype)
                     16: {   if (swaptype <= 1) swapcode(long, a, b, n)
                     17:     else swapcode(char, a, b, n)
                     18: }
                     19: #define swap(a, b)                         \
                     20:     if (swaptype == 0) {                   \
                     21:         t = *(long*)(a);                   \
                     22:         *(long*)(a) = *(long*)(b);         \
                     23:         *(long*)(b) = t;                   \
                     24:     } else                                 \
                     25:         swapfunc(a, b, es, swaptype)
                     26: 
                     27: #define PVINIT(pv, pm)                                \
                     28:     if (swaptype != 0) { pv = a; swap(pv, pm); }      \
                     29:     else { pv = (char*)&v; *(long*)pv = *(long*)pm; }
                     30: 
                     31: #define vecswap(a, b, n) if (n > 0) swapfunc(a, b, n, swaptype)
                     32: 
                     33: #define min(x, y) ((x)<=(y) ? (x) : (y))
                     34: 
                     35: static char *med3(char *a, char *b, char *c, int (*cmp)())
                     36: {      return cmp(a, b) < 0 ?
                     37:                  (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a)
                     38:                : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a);
                     39: }
                     40: 
                     41: void qsort(char *a, size_t n, size_t es, int (*cmp)())
                     42: {
                     43:        char *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv;
                     44:        int r, swaptype;
                     45:        long s, t, v;
                     46: 
                     47:        SWAPINIT(a, es);
                     48:        if (n < 7) {     /* Insertion sort on smallest arrays */
                     49:                for (pm = a + es; pm < a + n*es; pm += es)
                     50:                        for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
                     51:                                swap(pl, pl-es);
                     52:                return;
                     53:        }
                     54:        pm = a + (n/2)*es;    /* Small arrays, middle element */
                     55:        if (n > 7) {
                     56:                pl = a;
                     57:                pn = a + (n-1)*es;
                     58:                if (n > 40) {    /* Big arrays, pseudomedian of 9 */
                     59:                        s = (n/8)*es;
                     60:                        pl = med3(pl, pl+s, pl+2*s, cmp);
                     61:                        pm = med3(pm-s, pm, pm+s, cmp);
                     62:                        pn = med3(pn-2*s, pn-s, pn, cmp);
                     63:                }
                     64:                pm = med3(pl, pm, pn, cmp); /* Mid-size, med of 3 */
                     65:        }
                     66:        PVINIT(pv, pm);
                     67:        pa = pb = a;
                     68:        pc = pd = a + (n-1)*es;
                     69:        for (;;) {
                     70:                while (pb <= pc && (r = cmp(pb, pv)) <= 0) {
                     71:                        if (r == 0) { swap(pa, pb); pa += es; }
                     72:                        pb += es;
                     73:                }
                     74:                while (pb <= pc && (r = cmp(pc, pv)) >= 0) {
                     75:                        if (r == 0) { swap(pc, pd); pd -= es; }
                     76:                        pc -= es;
                     77:                }
                     78:                if (pb > pc) break;
                     79:                swap(pb, pc);
                     80:                pb += es;
                     81:                pc -= es;
                     82:        }
                     83:        pn = a + n*es;
                     84:        s = min(pa-a,  pb-pa   ); vecswap(a,  pb-s, s);
                     85:        s = min(pd-pc, pn-pd-es); vecswap(pb, pn-s, s);
                     86:        if ((s = pb-pa) > es) qsort(a,    s/es, es, cmp);
                     87:        if ((s = pd-pc) > es) qsort(pn-s, s/es, es, cmp);
                     88: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.