Return to rsort.c CVS log

Up to [Research Unix] / researchv10no / cmd / sort

Annotation of researchv10no/cmd/sort/rsort.c, revision 1.1

1.1     ! root        1: /* Copyright 1990, AT&T Bell Labs */
        !             2: #include "fsort.h"
        !             3: 
        !             4: /* Radix sort by bytes.  Records are chained in a list.
        !             5:    There are up to 257 bins at each recursion level.
        !             6:    The "null bin" is for short strings that have run out;
        !             7:    the rest are for byte values 0-255 */
        !             8: 
        !             9: int aflag = 0;
        !            10: int uflag = 0;
        !            11: int rflag = 0;
        !            12: int sflag = 0;
        !            13: 
        !            14: /* Sort the list s by distributing according to
        !            15:    digit d into an array of bins, sorting the bins
        !            16:    recursively, and re-collecting them back into the list.
        !            17:    If uflag is nonzero return only 1 representative of
        !            18:    each equivalence class.  The squeeze step noted
        !            19:    below determines what bins are in use, and squeezes
        !            20:    those into a stack frame, which is contiguous to s.
        !            21:    The null bin is handled separately to cut the span
        !            22:    of the squeeze loop.
        !            23:    Precondition: length(s) > 1 */
        !            24: 
        !            25: #define tiebreak(t)                                    \
        !            26:        if(uflag) {                                     \
        !            27:                t->tail = !aflag? t->head:              \
        !            28:                          listaccum(t->head, t->tail);  \
        !            29:                t->tail->next = 0;                      \
        !            30:        } else if(keyed && !sflag && t->head->next) {   \
        !            31:                rflag = fields[0].rflag;                \
        !            32:                keyed = 0;                              \
        !            33:                sort(t, 0);                             \
        !            34:                keyed = 1;                              \
        !            35:                rflag = 0;                              \
        !            36:        } else
        !            37: 
        !            38: void
        !            39: sort(struct list *s, int d)
        !            40: {
        !            41:        extern int uflag;
        !            42:        struct list *t;
        !            43:        struct rec *r, *q;
        !            44:        struct list *frame = s + 1;     /* stack frame */
        !            45:        static struct list bins[257];
        !            46: #      define nullbin (bins+256)
        !            47:        int nbin;               /* number of filled bins */
        !            48:        struct list *low; /* lowest unsorted nonnull bin */
        !            49: loop:
        !            50:        r = s->head;
        !            51:        low = bins + 256;
        !            52:        nbin = 0;
        !            53:        while(r) {
        !            54:                if(keyed)
        !            55:                        if(r->klen > (len_t)d)
        !            56:                                t = bins + key(r)[d];
        !            57:                        else
        !            58:                                t = nullbin;
        !            59:                else
        !            60:                        if(r->dlen > (len_t)d)
        !            61:                                t = bins + data(r)[d];
        !            62:                        else
        !            63:                                t = nullbin;
        !            64:                if(t->head == 0) {
        !            65:                        if(low > t)
        !            66:                                low = t;
        !            67:                        t->head = r;
        !            68:                        nbin++;
        !            69:                } else
        !            70:                        t->tail->next = r;      /* stable sort */
        !            71:                t->tail = r;
        !            72:                r = r->next;
        !            73:        }
        !            74:        t = frame;                      /* t is stack top */
        !            75:        if(t+nbin > stackmax)
        !            76:                fatal("stack overflow", "", 0);
        !            77: #      define push(b)          /* onto stack */        \
        !            78:                *t = *b,                                \
        !            79:                t->tail->next = 0,                      \
        !            80:                t++,                                    \
        !            81:                b->head = 0,                            \
        !            82:                nbin--
        !            83:        if(nullbin->head)
        !            84:                push(nullbin);
        !            85:        for( ; nbin>0; low++)
        !            86:                if(low->head)
        !            87:                        push(low);
        !            88:        if(t == frame+1) {              /* tail recursion */
        !            89: /*             debug(frame, t, d);*/
        !            90:                r = frame->head;
        !            91:                if(r->len[keyed] <= d) {
        !            92:                        tiebreak(frame);
        !            93:                        *s = *frame;
        !            94:                        return;         /* string ran out */
        !            95:                }
        !            96:                d++;
        !            97:                goto loop;
        !            98:        }
        !            99: /*     debug(frame, t, d);*/
        !           100:        t--;
        !           101:        if(t->head->next)               /* skip 1-item list */
        !           102:                sort(t, d+1);
        !           103:        if(!rflag) {                    /* forward order */
        !           104:                r = t->tail;
        !           105:                while(t > frame) {      
        !           106:                        q = t->head;
        !           107:                        if((--t>frame || t->head->len[keyed]>d)
        !           108:                           && t->head->next)
        !           109:                                sort(t, d+1);
        !           110:                        else if(t==frame)
        !           111:                                tiebreak(t);
        !           112:                        t->tail->next = q;      /* concatenate */
        !           113:                }
        !           114:                s->head = frame->head;
        !           115:                s->tail = r;
        !           116:        } else {                        /* reverse order */
        !           117:                r = t->head;
        !           118:                while(t > frame) {      
        !           119:                        q = t->tail;
        !           120:                        if((--t>frame || t->head->len[keyed]>d)
        !           121:                           && t->head->next)
        !           122:                                sort(t, d+1);
        !           123:                        else if(t==frame)
        !           124:                                tiebreak(t);
        !           125:                        q->next = t->head;      /* concatenate */
        !           126:                }
        !           127:                s->head = r;
        !           128:                s->tail = frame->tail;
        !           129:        }
        !           130: /*     printf("return\n"); debug(s,s+1,d);*/
        !           131: }
        !           132: 
        !           133: /*
        !           134: debug(struct list *stack, struct list *top, int d)
        !           135: {
        !           136:        printf("----------------------level %d\n", d);
        !           137:        while(stack<top) {
        !           138:                printout(stack->head, stdout, "stdout");
        !           139:                printf("----------------------\n");
        !           140:                stack++;
        !           141:        }
        !           142: }
        !           143: */

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