Return to qsort.c CVS log

Up to [CSRG BSD Unix] / 40BSD / libc / gen

Annotation of 40BSD/libc/gen/qsort.c, revision 1.1

1.1     ! root        1: 
        !             2: static int     (*qscmp)();
        !             3: static int     qses;
        !             4: 
        !             5: qsort(a, n, es, fc)
        !             6: char *a;
        !             7: unsigned n;
        !             8: int es;
        !             9: int (*fc)();
        !            10: {
        !            11:        qscmp = fc;
        !            12:        qses = es;
        !            13:        qs1(a, a+n*es);
        !            14: }
        !            15: 
        !            16: static qs1(a, l)
        !            17: char *a, *l;
        !            18: {
        !            19:        register char *i, *j;
        !            20:        register es;
        !            21:        char **k;
        !            22:        char *lp, *hp;
        !            23:        int c;
        !            24:        unsigned n;
        !            25: 
        !            26: 
        !            27:        es = qses;
        !            28: 
        !            29: start:
        !            30:        if((n=l-a) <= es)
        !            31:                return;
        !            32:        n = es * (n / (2*es));
        !            33:        hp = lp = a+n;
        !            34:        i = a;
        !            35:        j = l-es;
        !            36:        for(;;) {
        !            37:                if(i < lp) {
        !            38:                        if((c = (*qscmp)(i, lp)) == 0) {
        !            39:                                qsexc(i, lp -= es);
        !            40:                                continue;
        !            41:                        }
        !            42:                        if(c < 0) {
        !            43:                                i += es;
        !            44:                                continue;
        !            45:                        }
        !            46:                }
        !            47: 
        !            48: loop:
        !            49:                if(j > hp) {
        !            50:                        if((c = (*qscmp)(hp, j)) == 0) {
        !            51:                                qsexc(hp += es, j);
        !            52:                                goto loop;
        !            53:                        }
        !            54:                        if(c > 0) {
        !            55:                                if(i == lp) {
        !            56:                                        qstexc(i, hp += es, j);
        !            57:                                        i = lp += es;
        !            58:                                        goto loop;
        !            59:                                }
        !            60:                                qsexc(i, j);
        !            61:                                j -= es;
        !            62:                                i += es;
        !            63:                                continue;
        !            64:                        }
        !            65:                        j -= es;
        !            66:                        goto loop;
        !            67:                }
        !            68: 
        !            69: 
        !            70:                if(i == lp) {
        !            71:                        if(lp-a >= l-hp) {
        !            72:                                qs1(hp+es, l);
        !            73:                                l = lp;
        !            74:                        } else {
        !            75:                                qs1(a, lp);
        !            76:                                a = hp+es;
        !            77:                        }
        !            78:                        goto start;
        !            79:                }
        !            80: 
        !            81: 
        !            82:                qstexc(j, lp -= es, i);
        !            83:                j = hp -= es;
        !            84:        }
        !            85: }
        !            86: 
        !            87: static qsexc(i, j)
        !            88: char *i, *j;
        !            89: {
        !            90:        register char *ri, *rj, c;
        !            91:        int n;
        !            92: 
        !            93:        n = qses;
        !            94:        ri = i;
        !            95:        rj = j;
        !            96:        do {
        !            97:                c = *ri;
        !            98:                *ri++ = *rj;
        !            99:                *rj++ = c;
        !           100:        } while(--n);
        !           101: }
        !           102: 
        !           103: static qstexc(i, j, k)
        !           104: char *i, *j, *k;
        !           105: {
        !           106:        register char *ri, *rj, *rk;
        !           107:        int c;
        !           108:        int n;
        !           109: 
        !           110:        n = qses;
        !           111:        ri = i;
        !           112:        rj = j;
        !           113:        rk = k;
        !           114:        do {
        !           115:                c = *ri;
        !           116:                *ri++ = *rk;
        !           117:                *rk++ = *rj;
        !           118:                *rj++ = c;
        !           119:        } while(--n);
        !           120: }

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