Return to qsort.c CVS log

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

Annotation of 41BSD/libc/gen/qsort.c, revision 1.1.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.