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     ! 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.