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

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.