Return to sort.c CVS log

Up to [MW Coherent from dump] / coherent / d / bin

Annotation of coherent/d/bin/sort.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * The sort command.
        !             3:  * It does unique sorting, merges, and
        !             4:  * ordinary sorts with zillions of
        !             5:  * ways of specifying the sort keys.
        !             6:  */
        !             7: 
        !             8: #include <stdio.h>
        !             9: #include <ctype.h>
        !            10: #include <sys/mdata.h>
        !            11: #ifdef COHERENT
        !            12: #include <signal.h>
        !            13: #endif
        !            14: #include <sys/types.h>
        !            15: 
        !            16: #define        NREC    400             /* Longest key record */
        !            17: #define        NSEL    20              /* Number of records in selection list */
        !            18: #define        NPOS    20              /* Number of positionals */
        !            19: #define        NTFILE  6               /* Number of intermediate files */
        !            20: #define        MORDER          (NTFILE-1)      /* Order of polyphase merge */
        !            21: #define        NDIST   (sizeof(dists)/sizeof(dists[0]))
        !            22: #define        NCSET   (MAXUCHAR+1)    /* Size of char set */
        !            23: #define        NSBRK   1024            /* Amount to add at a time */
        !            24: #define BADSBRK ((char *) -1)   /* fail from sbrk() */
        !            25: 
        !            26: #define        rfree(p) {p->r_next=frlist;frlist=p;}           /* Free a run */
        !            27: 
        !            28: /* Key ordering flags (global and field skips) */
        !            29: #define        KBLANK  01              /* Ignore leading blanks */
        !            30: #define        KDICT   02              /* Dictionary order (letters, digits, blanks) */
        !            31: #define        KFOLD   04              /* Fold upper case onto lower case */
        !            32: #define        KIGNORE 010             /* Ignore non-ascii characters */
        !            33: #define        KNUM    020             /* Numeric sort - skip leading blanks */
        !            34: #define        KREV    040             /* Reverse order of sort */
        !            35: 
        !            36: /*
        !            37:  * Mapping table to speed up folding.
        !            38:  * Initialised by `sortinit'.
        !            39:  */
        !            40: char   tabfold[NCSET];
        !            41: 
        !            42: /*
        !            43:  * The temp file structure.  One for each file
        !            44:  * contains the list-head for the runs and
        !            45:  * the FILE stream pointer.
        !            46:  */
        !            47: typedef        struct  TFILE {
        !            48:        struct  RUN     *tf_runs;
        !            49:        FILE    *tf_fp;
        !            50:        int     tf_nrun;
        !            51:        fsize_t tf_start;
        !            52: }      TFILE;
        !            53: 
        !            54: TFILE  tfiles[NTFILE];
        !            55: 
        !            56: /*
        !            57:  * The structure of each run.  contains
        !            58:  * a pointer to the next and the start
        !            59:  * and length of the run.
        !            60:  */
        !            61: typedef        struct  RUN {
        !            62:        struct  RUN     *r_next;
        !            63:        int     r_length;               /* Number of records in run */
        !            64: }      RUN;
        !            65: 
        !            66: /*
        !            67:  * Entries in positional (+m.n-m.n) parameters
        !            68:  */
        !            69: typedef        struct  POS {
        !            70:        int     p_sflags;       /* Start flags */
        !            71:        int     p_sm;           /* fields */
        !            72:        int     p_sn;           /* chars */
        !            73:        int     p_eflags;       /* End flags */
        !            74:        int     p_em;           /* Ending fields */
        !            75:        int     p_en;           /* Ending chars */
        !            76: }      POS;
        !            77: 
        !            78: POS    pos[NPOS];
        !            79: POS    *posp = &pos[-1];
        !            80: 
        !            81: /*
        !            82:  * Numeric field breakout structure.
        !            83:  */
        !            84: typedef struct NUM {
        !            85:        int     n_sign;         /* Sign */
        !            86:        int     n_magn;         /* Integer magnitude */
        !            87:        int     n_fmagn;        /* Fractional magnitude */
        !            88:        char    *n_bgn;         /* beginning */
        !            89:        char    *n_end;         /* ending */
        !            90: } NUM;
        !            91: 
        !            92: char   **flist;
        !            93: char   *deflist[] = {
        !            94:        "-", NULL
        !            95: };
        !            96: 
        !            97: /*
        !            98:  * This is the best distribution of runs for
        !            99:  * the polyphase merge.  It is a sort of n-way
        !           100:  * distribution of the Fibonacci number sequence.
        !           101:  * Each level contains a total number of runs
        !           102:  * and a way to subdivide them to this.  Dummy
        !           103:  * runs are added to round out the initial distribution.
        !           104:  * Each successive distribution vector (m0,m1,m2,m3,m4)
        !           105:  * is obtained by cross product with this matrix:
        !           106:  *     1 1 1 1 1
        !           107:  *     1 0 0 0 0
        !           108:  *     0 1 0 0 0
        !           109:  *     0 0 1 0 0
        !           110:  *     0 0 0 1 0
        !           111:  * which can be generalised to any order of merge (other
        !           112:  * than 5-way).
        !           113:  * Also no more entries are given as this is
        !           114:  * likely already overkill for sorting during
        !           115:  * the lifetime of most machines.
        !           116:  */
        !           117: struct dists {
        !           118:        int     d_totruns;              /* Total of next 5 elements */
        !           119:        int     d_runs[MORDER]; /* initial distribution */
        !           120: }      dists[] = {
        !           121:        1,      1, 0, 0, 0, 0,
        !           122:        5,      1, 1, 1, 1, 1,
        !           123:        9,      2, 2, 2, 2, 1,
        !           124:        17,     4, 4, 4, 3, 2,
        !           125:        33,     8, 8, 7, 6, 4,
        !           126:        65,     16, 15, 14, 12, 8,
        !           127:        129,    31, 30, 28, 24, 16,
        !           128:        253,    61, 59, 55, 47, 31,
        !           129:        497,    120, 116, 108, 92, 61,
        !           130:        977,    236, 228, 212, 181, 120,
        !           131:        1921,   464, 448, 417, 356, 236,
        !           132:        3777,   912, 881, 820, 700, 464,
        !           133:        7425,   1793, 1732, 1612, 1376, 912,
        !           134:        14597,  3525, 3405, 3169, 2705, 1793,
        !           135:        28697,  6930, 6694, 6230, 5318, 3525
        !           136: };
        !           137: 
        !           138: struct dists   *savedsp;               /* Save current distribution level */
        !           139: 
        !           140: char   *outname;                       /* Output other than stdout */
        !           141: char   *tempdir;                       /* Other than default temp directory */
        !           142: char   template[100];
        !           143: char   obuf[BUFSIZ];
        !           144: char   ibuf[BUFSIZ];
        !           145: 
        !           146: /*
        !           147:  * Structure for each input record
        !           148:  * in natural selection.  First
        !           149:  * an insertion sort fills the
        !           150:  * tree and then all records
        !           151:  * are input and output until
        !           152:  * too many are out of order.
        !           153:  */
        !           154: typedef        struct  SEL {
        !           155:        char    *s_inb;         /* Input buffer pointer */
        !           156:        int     s_length;       /* Length of run in selection */
        !           157:        FILE    *s_fp;          /* File pointer of run */
        !           158: }      SEL;
        !           159: 
        !           160: RUN    *frlist;                /* Free run list */
        !           161: SEL    sel[NSEL];
        !           162: SEL    lastrec;
        !           163: char   inbuf[NSEL+1][NREC];
        !           164: #define        LASTREC lastrec.s_inb   /* Buffer pointer of last written record */
        !           165: long inline;           /* Record number of input line, for error recovery */
        !           166: char   temperr[] = "Temporary file open error";
        !           167: char   tmpwerr[] = "Temporary file write error";
        !           168: char   nomem[] = "Out of memory";
        !           169: int    pid;                            /* Current process ID */
        !           170: char   tabc;                           /* Tab character */
        !           171: int    cflag;                          /* Check ordering only */
        !           172: int    mflag;                          /* Merge only */
        !           173: int    uflag;                          /* Unique sort */
        !           174: int    kflags;                         /* Flags to control order to sort */
        !           175: 
        !           176: char   *sgets();
        !           177: RUN    *copyfile();
        !           178: RUN    *ralloc();
        !           179: char   *alloc();
        !           180: int    rmexit();
        !           181: int    kcompar();
        !           182: int    strcmp();
        !           183: int    rstrcmp();
        !           184: int    (*compar)() = kcompar;
        !           185: char   *sprintf();
        !           186: 
        !           187: main(argc, argv)
        !           188: int argc;
        !           189: char *argv[];
        !           190: {
        !           191:        register char *ap;
        !           192:        char dummyop[2];
        !           193: 
        !           194:        setbuf(stdin, ibuf);
        !           195:        setbuf(stdout, obuf);
        !           196:        setbuf(stderr, NULL);
        !           197: #ifdef COHERENT
        !           198:        protect(SIGINT);
        !           199:        protect(SIGHUP);
        !           200:        protect(SIGPIPE);
        !           201:        protect(SIGTERM);
        !           202: #endif
        !           203:        while (argc>1 && (*argv[1]=='-' || *argv[1]=='+')) {
        !           204:                if (*argv[1] == '+') {
        !           205:                        readskip(argv[1]);
        !           206:                        argv++;
        !           207:                        argc--;
        !           208:                        if (argc>1 && argv[1][0]=='-' && isdigit(argv[1][1])) {
        !           209:                                readskip(argv[1]);
        !           210:                                argv++;
        !           211:                                argc--;
        !           212:                        }
        !           213:                        continue;
        !           214:                }
        !           215:                for (ap = &argv[1][1]; *ap != '\0'; ap++)
        !           216:                switch (*ap) {
        !           217: 
        !           218:                /*
        !           219:                 * Non-ordering options.
        !           220:                 */
        !           221:                case 'c':               /* Check ordering only */
        !           222:                        cflag = 1;
        !           223:                        break;
        !           224: 
        !           225:                case 'm':               /* Merge only */
        !           226:                        mflag = 1;
        !           227:                        break;
        !           228: 
        !           229:                case 'o':               /* Output other than stdout */
        !           230:                        if (outname != NULL)
        !           231:                                serr("Only one output name allowed");
        !           232:                        if (--argc < 2)
        !           233:                                usage();
        !           234:                        argv++;
        !           235:                        outname = argv[1];
        !           236:                        break;
        !           237: 
        !           238:                case 'T':               /* Alternative temp directory */
        !           239:                        if (tempdir != NULL)
        !           240:                                serr("Only one `-T' allowed");
        !           241:                        if (--argc < 2)
        !           242:                                usage();
        !           243:                        argv++;
        !           244:                        tempdir = argv[1];
        !           245:                        break;
        !           246: 
        !           247:                case 'u':               /* Unique sort */
        !           248:                        uflag = 1;
        !           249:                        break;
        !           250: 
        !           251:                /*
        !           252:                 * Lexicographic ordering options.
        !           253:                 */
        !           254:                case 't':               /* Tab character */
        !           255:                        if ((tabc = *++ap) == '\0')
        !           256:                                usage();
        !           257:                        break;
        !           258: 
        !           259:                default:
        !           260:                        dummyop[0] = *ap;
        !           261:                        dummyop[1] = '\0';
        !           262:                        opts(dummyop, &kflags);
        !           263:                }
        !           264:                argc--;
        !           265:                argv++;
        !           266:        }
        !           267:        if (argc > 1)
        !           268:                flist = argv+1; else
        !           269:                flist = deflist;
        !           270:        sortinit();
        !           271:        rmexit(sort());
        !           272: }
        !           273: 
        !           274: /*
        !           275:  * Initialise tables that speed up
        !           276:  * special orderings.
        !           277:  */
        !           278: sortinit()
        !           279: {
        !           280:        register int c;
        !           281:        register char *cp;
        !           282: 
        !           283:        cp = tabfold;
        !           284:        for (c=0; c<NCSET; c++)
        !           285:                *cp++ = (isascii(c) && isupper(c)) ? tolower(c) : c;
        !           286: }
        !           287: 
        !           288: /*
        !           289:  * Read in the ordering options into
        !           290:  * the int that is referenced by `flagp'
        !           291:  * from the string `s'.  Used both for
        !           292:  * global options and with skip options.
        !           293:  */
        !           294: opts(s, flagp)
        !           295: register char *s;
        !           296: register int *flagp;
        !           297: {
        !           298:        while (*s)
        !           299:                switch (*s++) {
        !           300:                case 'b':
        !           301:                        *flagp |= KBLANK;
        !           302:                        break;
        !           303: 
        !           304:                case 'd':
        !           305:                        *flagp |= KDICT;
        !           306:                        break;
        !           307: 
        !           308:                case 'f':
        !           309:                        *flagp |= KFOLD;
        !           310:                        break;
        !           311: 
        !           312:                case 'i':
        !           313:                        *flagp |= KIGNORE;
        !           314:                        break;
        !           315: 
        !           316:                case 'n':
        !           317:                        *flagp |= KNUM;
        !           318:                        break;
        !           319: 
        !           320:                case 'r':
        !           321:                        *flagp |= KREV;
        !           322:                        break;
        !           323: 
        !           324:                default:
        !           325:                        usage();
        !           326:                }
        !           327: }
        !           328: 
        !           329: /*
        !           330:  * Read in the skip (either the `+' or
        !           331:  * the `-' kind).  Syntax check it and
        !           332:  * store it away.
        !           333:  */
        !           334: readskip(s)
        !           335: register char *s;
        !           336: {
        !           337:        register int n;
        !           338:        register int plusskip = 0;
        !           339: 
        !           340:        plusskip = *s++ == '+';
        !           341:        if (plusskip) {
        !           342:                if (++posp >= &pos[NPOS])
        !           343:                        serr("Too many positional parameters");
        !           344:                posp->p_em = MAXINT;
        !           345:        }
        !           346:        for (n=0; isdigit(*s); )
        !           347:                n = n*10 + *s++ - '0';
        !           348:        if (plusskip)
        !           349:                posp->p_sm = n; else
        !           350:                posp->p_em = n;
        !           351:        if (*s == '.') {
        !           352:                s++;
        !           353:                for (n=0; isdigit(*s); )
        !           354:                        n = n*10 + *s++ - '0';
        !           355:                if (plusskip)
        !           356:                        posp->p_sn = n; else
        !           357:                        posp->p_en = n;
        !           358:        }
        !           359:        opts(s, plusskip ? &posp->p_sflags : &posp->p_eflags);
        !           360: }
        !           361: 
        !           362: /*
        !           363:  * Actually figure out what kind of
        !           364:  * sorting we have to do.
        !           365:  */
        !           366: sort()
        !           367: {
        !           368:        register FILE *fp;
        !           369: 
        !           370:        /*
        !           371:         * Optimisation for simple sorts
        !           372:         * to cut compare time down.
        !           373:         */
        !           374:        if (posp<&pos[0] && (kflags&~KREV)==0) {
        !           375:                if (kflags & KREV)
        !           376:                        compar = rstrcmp; else
        !           377:                        compar = strcmp;
        !           378:        }
        !           379:        if (cflag) {
        !           380:                register char *b1, *b2;
        !           381: 
        !           382:                if (mflag || outname!=NULL || uflag)
        !           383:                        fprintf(stderr, "Checking only--some options ignored\n");
        !           384:                b1 = NULL;
        !           385:                b2 = inbuf[0];
        !           386:                while (sgets(b2) != NULL) {
        !           387:                        if (b1 == NULL) {
        !           388:                                b2 = inbuf[1];
        !           389:                                b1 = inbuf[0];
        !           390:                                continue;
        !           391:                        }
        !           392:                        if ((*compar)(b1, b2) > 0) {
        !           393:                                fprintf(stderr, "sort: out of order at:\n");
        !           394:                                fprintf(stderr, "%s", b2);
        !           395:                                return (1);
        !           396:                        }
        !           397:                        if (b2 == inbuf[1]) {
        !           398:                                b1 = inbuf[1];
        !           399:                                b2 = inbuf[0];
        !           400:                        } else {
        !           401:                                b1 = inbuf[0];
        !           402:                                b2 = inbuf[1];
        !           403:                        }
        !           404:                }
        !           405:                return (0);
        !           406:        }
        !           407:        if (mflag) {
        !           408:                if (copyruns())
        !           409:                        return (1);
        !           410:        } else {
        !           411:                if (selection())
        !           412:                        return (1);
        !           413:        }
        !           414:        dummyruns();
        !           415:        if (merge())
        !           416:                return (1);
        !           417:        if (outname != NULL) {
        !           418:                if (freopen(outname, "w", stdout) != stdout)
        !           419:                        serr("Cannot open output `%s'", outname);
        !           420:        }
        !           421:        fp = tfiles[MORDER].tf_fp;
        !           422:        rewind(fp);
        !           423:        LASTREC = NULL;
        !           424:        while (fgets(inbuf[0], NREC, fp) != NULL) {
        !           425:                if (uflag) {
        !           426:                        if (LASTREC == NULL)
        !           427:                                LASTREC = inbuf[1];
        !           428:                        else if ((*compar)(LASTREC, inbuf[0]) == 0)
        !           429:                                continue;
        !           430:                        strcpy(LASTREC, inbuf[0]);
        !           431:                }
        !           432:                fputs(inbuf[0], stdout);
        !           433:        }
        !           434:        fflush(stdout);
        !           435:        if (ferror(stdout))
        !           436:                serr("Write error on `%s'", outname==NULL ? "(stdout)":outname);
        !           437:        fclose(fp);
        !           438:        return (0);
        !           439: }
        !           440: 
        !           441: /*
        !           442:  * Copy the runs into the temp-files
        !           443:  * for already-sorted but not merged data.
        !           444:  */
        !           445: copyruns()
        !           446: {
        !           447:        register char **flp = flist;
        !           448:        register char *fn;
        !           449:        register FILE *fp;
        !           450:        register int s = 0;
        !           451: 
        !           452:        while ((fn = *flp++) != NULL) {
        !           453:                if (fn[0]=='-' && fn[1]=='\0')
        !           454:                        fp = stdin;
        !           455:                else if ((fp = fopen(fn, "r")) == NULL) {
        !           456:                        fprintf(stderr, "sort: cannot open `%s'\n", fn);
        !           457:                        s = 1;
        !           458:                        continue;
        !           459:                }
        !           460:                setbuf(fp, ibuf);
        !           461:                if (copyfile(fp, nextrun()) == NULL)
        !           462:                        return (1);
        !           463:                if (fp != stdin)
        !           464:                        fclose(fp);
        !           465:        }
        !           466:        return (s);
        !           467: }
        !           468: 
        !           469: /*
        !           470:  * Calculate the next run number to use,
        !           471:  * based on the number that we already have.
        !           472:  * The dummy runs go to the left (largest
        !           473:  * number so they are used the most often)
        !           474:  * Dummy runs are installed by another routine
        !           475:  * after all runs are entered.
        !           476:  */
        !           477: nextrun()
        !           478: {
        !           479:        register struct dists *dsp;
        !           480:        register int i;
        !           481: 
        !           482:        for (dsp = dists; dsp < &dists[NDIST]; dsp++) {
        !           483:                for (i=MORDER-1; i>=0; i--) {
        !           484:                        if (tfiles[i].tf_nrun < dsp->d_runs[i]) {
        !           485:                                savedsp = dsp;
        !           486:                                return (i);
        !           487:                        }
        !           488:                }
        !           489:        }
        !           490:        serr("Ridiculously many runs");
        !           491: }
        !           492: 
        !           493: /*
        !           494:  * Fill out the current distribution level
        !           495:  * with dummy runs.
        !           496:  */
        !           497: dummyruns()
        !           498: {
        !           499:        register struct dists *dsp;
        !           500:        register TFILE *tfp;
        !           501:        register int i;
        !           502: 
        !           503:        dsp = savedsp;
        !           504:        for (i=0; i<MORDER; i++)
        !           505:                for (tfp = &tfiles[i]; tfp->tf_nrun < dsp->d_runs[i]; )
        !           506:                        tfp->tf_nrun++;
        !           507: }
        !           508: 
        !           509: /*
        !           510:  * Copy each run file to the appropriate temp file
        !           511:  * given by the run number (`runno').
        !           512:  * Also, check during the input for the file's
        !           513:  * being sorted properly.
        !           514:  * If `ifp' is NULL, this creates an empty
        !           515:  * (distinguished from dummy) run.
        !           516:  */
        !           517: RUN *
        !           518: copyfile(ifp, runno)
        !           519: FILE *ifp;
        !           520: int runno;
        !           521: {
        !           522:        register RUN *arp, *rp;
        !           523:        register int c;
        !           524:        register TFILE *tfp;
        !           525:        register FILE *ofp;
        !           526: 
        !           527:        tfp = &tfiles[runno];
        !           528:        tfp->tf_nrun++;
        !           529:        if ((ofp = tfp->tf_fp) == NULL) {
        !           530:                maketemp(runno);
        !           531:                ofp = tfp->tf_fp;
        !           532:        }
        !           533:        arp = ralloc();
        !           534:        arp->r_next = NULL;
        !           535:        arp->r_length = 0;
        !           536:        if (tfp->tf_runs == NULL)
        !           537:                tfp->tf_runs = arp;
        !           538:        else {
        !           539:                for (rp = tfp->tf_runs; rp->r_next != NULL; rp = rp->r_next)
        !           540:                        ;
        !           541:                rp->r_next = arp;
        !           542:        }
        !           543:        if (ifp == NULL)
        !           544:                return (arp);
        !           545:        while ((c = getc(ifp)) != EOF) {
        !           546:                if (c == '\n')
        !           547:                        arp->r_length++;
        !           548:                putc(c, ofp);
        !           549:        }
        !           550:        fflush(ofp);
        !           551:        if (ferror(ofp))
        !           552:                serr(tmpwerr);
        !           553:        return (arp);
        !           554: }
        !           555: 
        !           556: /*
        !           557:  * Use selection to create the initial runs.
        !           558:  */
        !           559: selection()
        !           560: {
        !           561:        register TFILE *tfp;
        !           562:        register RUN *rp;
        !           563:        register int i;
        !           564:        register int nsel;
        !           565: 
        !           566:        for (;;) {
        !           567:                for (i=0; i<NSEL; i++)
        !           568:                        sel[i].s_inb = inbuf[i];
        !           569:                LASTREC = NULL;
        !           570:                rp = copyfile(NULL, i = nextrun());
        !           571:                tfp = &tfiles[i];
        !           572:                for (nsel = 0; sgets(inbuf[nsel])!=NULL; ) {
        !           573:                        insert(nsel);
        !           574:                        if (++nsel >= NSEL)
        !           575:                                break;
        !           576:                }
        !           577:                for (i=0; i<nsel; i++) {
        !           578:                        if (uflag) {
        !           579:                                if (LASTREC != NULL)
        !           580:                                        if ((*compar)(LASTREC, sel[i].s_inb)==0)
        !           581:                                                continue;
        !           582:                                LASTREC = sel[i].s_inb;
        !           583:                        }
        !           584:                        fputs(sel[i].s_inb, tfp->tf_fp);
        !           585:                        rp->r_length++;
        !           586:                }
        !           587:                if (nsel < NSEL)
        !           588:                        break;
        !           589:        }
        !           590:        return (0);
        !           591: }
        !           592: 
        !           593: /*
        !           594:  * Insert the item at position `n'
        !           595:  * into the sel table in sorted order.
        !           596:  */
        !           597: insert(n)
        !           598: int n;
        !           599: {
        !           600:        register SEL *sp1, *sp2;
        !           601:        register char *tmp;
        !           602: 
        !           603:        sp2 = &sel[n];
        !           604:        for (sp1 = &sel[0]; sp1 < sp2; sp1++)
        !           605:                if ((*compar)(sp1->s_inb, sp2->s_inb) > 0) {
        !           606:                        tmp = sp2->s_inb;
        !           607:                        for (; sp2 > sp1; sp2--)
        !           608:                                sp2->s_inb = (sp2-1)->s_inb;
        !           609:                        sp1->s_inb = tmp;
        !           610:                        break;
        !           611:                }
        !           612: }
        !           613: 
        !           614: /*
        !           615:  * Merge the data
        !           616:  * The algorithm is polyphase merge from
        !           617:  * Knuth.
        !           618:  */
        !           619: merge()
        !           620: {
        !           621:        register int i, j;
        !           622:        register int nr;
        !           623:        TFILE temptf;
        !           624: 
        !           625:        nr = 0;
        !           626:        j = 0;
        !           627:        for (i=0; i<MORDER; i++)
        !           628:                if (tfiles[i].tf_nrun) {
        !           629:                        j = i;
        !           630:                        nr += tfiles[i].tf_nrun;
        !           631:                }
        !           632:        if (nr <= 1) {
        !           633:                tfiles[NTFILE-1] = tfiles[j];
        !           634:                return (0);
        !           635:        }
        !           636:        for (i=0; i<NTFILE; i++)
        !           637:                if (tfiles[i].tf_fp == NULL)
        !           638:                        maketemp(i);
        !           639:        for (;;) {
        !           640:                mergestep();
        !           641:                nr = 0;
        !           642:                for (i=0; i<MORDER; i++) {
        !           643:                        nr += tfiles[i].tf_nrun;
        !           644:                        if (tfiles[i].tf_nrun == 0)
        !           645:                                j = i;
        !           646:                }
        !           647:                if (nr <= 1)
        !           648:                        break;
        !           649:                /*
        !           650:                 * Exchange output and
        !           651:                 * zeroed one so output
        !           652:                 * is always in a fixed place.
        !           653:                 */
        !           654:                temptf = tfiles[MORDER];
        !           655:                tfiles[MORDER] = tfiles[j];
        !           656:                tfiles[j] = temptf;
        !           657:        }
        !           658:        return (0);
        !           659: }
        !           660: 
        !           661: /*
        !           662:  * Do one step of the polyphase merge.  The calling
        !           663:  * routine has arranged that the output is
        !           664:  * position MORDER and the inputs are the first
        !           665:  * MORDER positions.
        !           666:  */
        !           667: mergestep()
        !           668: {
        !           669:        register int min;
        !           670:        register int i;
        !           671:        register RUN *rp;
        !           672:        register FILE *ofp;
        !           673:        register int len;
        !           674:        register RUN *orp;
        !           675: 
        !           676:        rewind(tfiles[MORDER].tf_fp);
        !           677:        tfiles[MORDER].tf_start = 0;
        !           678:        min = tfiles[0].tf_nrun;
        !           679:        fseek(tfiles[0].tf_fp, tfiles[0].tf_start, 0);
        !           680:        for (i=1; i<MORDER; i++) {
        !           681:                fseek(tfiles[i].tf_fp, tfiles[i].tf_start, 0);
        !           682:                if (tfiles[i].tf_nrun < min)
        !           683:                        min = tfiles[i].tf_nrun;
        !           684:        }
        !           685:        while (min-- > 0) {
        !           686:                orp = copyfile(NULL, MORDER);
        !           687:                ofp = tfiles[MORDER].tf_fp;
        !           688:                len = 0;
        !           689:                for (i=0; i<MORDER; i++) {
        !           690:                        if ((rp = tfiles[i].tf_runs) != NULL) {
        !           691:                                tfiles[i].tf_runs = rp->r_next;
        !           692:                                len += rp->r_length;
        !           693:                                sel[i].s_length = rp->r_length;
        !           694:                                rfree(rp);
        !           695:                        } else
        !           696:                                sel[i].s_length = 0;
        !           697:                        tfiles[i].tf_nrun--;
        !           698:                        sel[i].s_inb = inbuf[i];
        !           699:                        sel[i].s_fp = tfiles[i].tf_fp;
        !           700:                }
        !           701:                orp->r_length = len;
        !           702:                mergeread();
        !           703:        }
        !           704:        for (i=0; i<MORDER; i++)
        !           705:                tfiles[i].tf_start = ftell(tfiles[i].tf_fp);
        !           706: }
        !           707: 
        !           708: /*
        !           709:  * Do the 5-way (MORDER) merge on one set
        !           710:  * of runs which are described in the `sel'
        !           711:  * struct array.
        !           712:  */
        !           713: mergeread()
        !           714: {
        !           715:        register SEL *sp;
        !           716:        register SEL *minp;
        !           717:        register int neof = 0;
        !           718: 
        !           719:        for (sp = sel; sp < &sel[MORDER]; sp++) {
        !           720:                if (sp->s_length == 0) {
        !           721:                        neof++;
        !           722:                        sp->s_inb = NULL;
        !           723:                } else {
        !           724:                        fgets(sp->s_inb, NREC, sp->s_fp);
        !           725:                        sp->s_length--;
        !           726:                }
        !           727:        }
        !           728:        while (neof < MORDER) {
        !           729:                minp = NULL;
        !           730:                for (sp = sel; sp < &sel[MORDER]; sp++) {
        !           731:                        if (sp->s_inb == NULL)
        !           732:                                continue;
        !           733:                        if (minp == NULL) {
        !           734:                                minp = sp;
        !           735:                                continue;
        !           736:                        }
        !           737:                        if ((*compar)(sp->s_inb, minp->s_inb) <= 0)
        !           738:                                minp = sp;
        !           739:                }
        !           740:                fputs(minp->s_inb, tfiles[NTFILE-1].tf_fp);
        !           741:                if (minp->s_length-- == 0) {
        !           742:                        minp->s_inb = NULL;
        !           743:                        neof++;
        !           744:                } else
        !           745:                        fgets(minp->s_inb, NREC, minp->s_fp);
        !           746:        }
        !           747: }
        !           748: 
        !           749: /*
        !           750:  * Get the next input character.  This
        !           751:  * automatically goes from one file to the
        !           752:  * next on EOF and only returns EOF at real
        !           753:  * end of file.
        !           754:  */
        !           755: sgetc()
        !           756: {
        !           757:        static FILE *fp;
        !           758:        register int c;
        !           759: 
        !           760: again:
        !           761:        if (fp == NULL)
        !           762:                if (*flist == NULL)
        !           763:                        return (EOF);
        !           764:                else {
        !           765:                        if ((*flist)[0]=='-' && (*flist)[1]=='\0')
        !           766:                                fp = stdin;
        !           767:                        else if ((fp = fopen(*flist, "r")) == NULL)
        !           768:                                fprintf(stderr, "sort: cannot open %s\n", *flist);
        !           769:                        flist++;
        !           770:                        setbuf(fp, ibuf);
        !           771:                        goto again;
        !           772:                }
        !           773:        if ((c = getc(fp)) == EOF) {
        !           774:                if (fp != stdin)
        !           775:                        fclose(fp);
        !           776:                fp = NULL;
        !           777:                goto again;
        !           778:        }
        !           779:        return (c);
        !           780: }
        !           781: 
        !           782: /*
        !           783:  * Get a string from sort input.  NULL on EOF, leave
        !           784:  * trailing newlines on.
        !           785:  */
        !           786: char *
        !           787: sgets(as)
        !           788: char *as;
        !           789: {
        !           790:        register unsigned max = NREC;
        !           791:        register int c;
        !           792:        register char *s;
        !           793: 
        !           794:        s = as;
        !           795:        while (--max>0 && (c = sgetc()) != EOF)
        !           796:                if ((*s++ = c) == '\n') {
        !           797:                        inline += 1;
        !           798:                        break;
        !           799:                }
        !           800:        if (max == 0)
        !           801:                serr("input record #%ld exceeds maximum length %d",
        !           802:                    inline + 1, NREC);
        !           803:        *s = '\0';
        !           804:        return (c==EOF && s==as ? NULL : as);
        !           805: }
        !           806: 
        !           807: /*
        !           808:  * Compare keys in strings `s1' and `s2'
        !           809:  * taking into account all of the key selection
        !           810:  * options and positional fields.
        !           811:  * All comparison routines return -1 or <, 0 for equal,
        !           812:  * and 1 for >.
        !           813:  */
        !           814: kcompar(s1, s2)
        !           815: char *s1;
        !           816: char *s2;
        !           817: {
        !           818:        char *fskip();
        !           819:        register POS *pp;
        !           820:        register char *ep1, *ep2;
        !           821:        register int ret = 0;
        !           822:        register char *p1, *p2;
        !           823: 
        !           824:        if (posp < &pos[0]) {
        !           825:                for (ep1=s1; *ep1++ != '\0'; )
        !           826:                        ;
        !           827:                ep1--;
        !           828:                for (ep2 = s2; *ep2++ != '\0'; )
        !           829:                        ;
        !           830:                ep2--;
        !           831:                return (fcompar(s1, ep1, s2, ep2, kflags));
        !           832:        }
        !           833:        for (pp = &pos[0]; pp <= posp; pp++) {
        !           834:                register int sflags, eflags;
        !           835: 
        !           836:                if ((sflags = pp->p_sflags) == 0)
        !           837:                        sflags = kflags;
        !           838:                if ((eflags = pp->p_eflags) == 0)
        !           839:                        eflags = kflags;
        !           840:                p1 = fskip(s1, pp->p_sm, pp->p_sn, sflags);
        !           841:                p2 = fskip(s2, pp->p_sm, pp->p_sn, sflags);
        !           842:                ep1 = fskip(s1, pp->p_em, pp->p_en, eflags);
        !           843:                ep2 = fskip(s2, pp->p_em, pp->p_en, eflags);
        !           844:                ret = fcompar(p1, ep1, p2, ep2, sflags|eflags);
        !           845:                if (ret)
        !           846:                        break;
        !           847:        }
        !           848:        return (ret);
        !           849: }
        !           850: 
        !           851: /*
        !           852:  * Skip fields and space, returning the new pointer.
        !           853:  * Arguments are `s' for string start, `m' and `n' from
        !           854:  * the positional `m.n' format.
        !           855:  * `f' is the flags - only `b' is
        !           856:  * significant here.
        !           857:  */
        !           858: char *
        !           859: fskip(s, m, n, f)
        !           860: register char *s;
        !           861: register int m;
        !           862: register int n;
        !           863: register int f;
        !           864: {
        !           865:        while (m--) {
        !           866:                if (tabc) {
        !           867:                        while (*s!=tabc && *s!='\0')
        !           868:                                s++;
        !           869:                        if (*s != '\0')
        !           870:                                s++;
        !           871:                        else
        !           872:                                break;
        !           873:                } else {
        !           874:                        while (*s==' ' || *s=='\t')
        !           875:                                s++;
        !           876:                        while (*s!=' ' && *s!='\t' && *s!='\0')
        !           877:                                s++;
        !           878:                        if (*s == '\0')
        !           879:                                break;
        !           880:                        if (m == 0)
        !           881:                                while (*s==' ' || *s=='\t')
        !           882:                                        s++;
        !           883:                }
        !           884:        }
        !           885:        if (f & KBLANK)
        !           886:                while (*s==' ' || *s=='\t')
        !           887:                        s++;
        !           888:        while (n--) {
        !           889:                if (*s == '\0')
        !           890:                        break;
        !           891:                s++;
        !           892:        }
        !           893:        return (s);
        !           894: }
        !           895: 
        !           896: /*
        !           897:  * Compare for the finally found field.
        !           898:  * This takes into account all of the options
        !           899:  * and the end and start of each string.
        !           900:  */
        !           901: fcompar(s1, e1, s2, e2, flags)
        !           902: char *s1, *e1;
        !           903: char *s2, *e2;
        !           904: int flags;
        !           905: {
        !           906:        register char *p1, *p2;
        !           907:        register int ret = 0;
        !           908: 
        !           909:        p1 = s1;
        !           910:        p2 = s2;
        !           911:        if (flags & (KBLANK|KNUM)) {
        !           912:                while (*p1==' ' || *p1=='\t')
        !           913:                        p1++;
        !           914:                while (*p2==' ' || *p2=='\t')
        !           915:                        p2++;
        !           916:        }
        !           917:        if (flags & KNUM) {
        !           918:                NUM n1, n2;
        !           919: 
        !           920:                numpars(p1, e1, &n1);
        !           921:                numpars(p2, e2, &n2);
        !           922:                /* Compare integer magnitudes and signs */
        !           923:                ret = n1.n_sign*n1.n_magn - n2.n_sign*n2.n_magn;
        !           924:                if (ret != 0)
        !           925:                        ret = (ret < 0) ? -1 : 1;
        !           926:                else {
        !           927:                        /* Compare integer parts */
        !           928:                        p1 = n1.n_bgn;
        !           929:                        p2 = n2.n_bgn;
        !           930:                        while (--n1.n_magn >= 0 && ret == 0)
        !           931:                                if (*p1 > *p2)
        !           932:                                        ret = n1.n_sign;
        !           933:                                else if (*p1 < *p2)
        !           934:                                        ret = - n1.n_sign;
        !           935:                                else {
        !           936:                                        p1 += 1;
        !           937:                                        p2 += 1;
        !           938:                                }
        !           939:                }
        !           940:                if (ret == 0)
        !           941:                        /* Compare fractional magnitudes and signs */
        !           942:                        ret = n1.n_sign*n1.n_fmagn - n2.n_sign*n2.n_fmagn;
        !           943:                if (ret != 0)
        !           944:                        ret = ret < 0 ? -1 : 1;
        !           945:                else {
        !           946:                        /* Compare fractional parts */
        !           947:                        e1 = n1.n_end;
        !           948:                        e2 = n2.n_end;
        !           949:                        while (p1 < e1 && p2 < e2 && ret == 0)
        !           950:                                if (*p1 > *p2)
        !           951:                                        ret = n1.n_sign;
        !           952:                                else if (*p1 < *p2)
        !           953:                                        ret = -n1.n_sign;
        !           954:                                else {
        !           955:                                        p1 += 1;
        !           956:                                        p2 += 1;
        !           957:                                }
        !           958:                }
        !           959:                if (ret == 0) {
        !           960:                        if (p1 < e1)
        !           961:                                ret = n1.n_sign;
        !           962:                        else
        !           963:                                ret = - n1.n_sign;
        !           964:                }
        !           965:        } else {
        !           966:                register int c1, c2;
        !           967: 
        !           968:                if (flags & (KDICT|KIGNORE)) {
        !           969:                        for (;;) {
        !           970:                                for (; p1<e1; p1++) {
        !           971:                                        if (flags&KIGNORE && !isprint(*p1))
        !           972:                                                continue;
        !           973:                                        if (flags & KDICT)
        !           974:                                                if (!(isspace(*p1)
        !           975:                                                    || isalnum(*p1)))
        !           976:                                                        continue;
        !           977:                                        if (flags & KFOLD)
        !           978:                                                c1 = tabfold[*p1++]; else
        !           979:                                                c1 = *p1++;
        !           980:                                        break;
        !           981:                                }
        !           982:                                for (; p2<e2; p2++) {
        !           983:                                        if (flags&KIGNORE && !isprint(*p2))
        !           984:                                                continue;
        !           985:                                        if (flags & KDICT)
        !           986:                                                if (!(isalnum(*p2)
        !           987:                                                    || isspace(*p2)))
        !           988:                                                        continue;
        !           989:                                        if (flags & KFOLD)
        !           990:                                                c2 = tabfold[*p2++]; else
        !           991:                                                c2 = *p2++;
        !           992:                                        break;
        !           993:                                }
        !           994:                                if (p1>=e1 || p2>=e2)
        !           995:                                        break;
        !           996:                                if (c1 != c2)
        !           997:                                        break;
        !           998:                        }
        !           999:                } else if (flags & KFOLD) {
        !          1000:                        for (;;) {
        !          1001:                                c1 = tabfold[*p1++];
        !          1002:                                c2 = tabfold[*p2++];
        !          1003:                                if (p1>=e1 || p2>=e2)
        !          1004:                                        break;
        !          1005:                                if (c1 != c2)
        !          1006:                                        break;
        !          1007:                        }
        !          1008:                } else {
        !          1009:                        for (;;) {
        !          1010:                                c1 = *p1++;
        !          1011:                                c2 = *p2++;
        !          1012:                                if (p1>=e1 || p2>=e2)
        !          1013:                                        break;
        !          1014:                                if (c1 != c2)
        !          1015:                                        break;
        !          1016:                        }
        !          1017:                }
        !          1018:                if (p1<=e1 && p2<=e2) {
        !          1019:                        if (c1 < c2)
        !          1020:                                ret--;
        !          1021:                        else if (c1 > c2)
        !          1022:                                ret++;
        !          1023:                } else if (p1 > e1) {
        !          1024:                        ret++;
        !          1025:                } else
        !          1026:                        ret --;
        !          1027:        }
        !          1028:        if (flags & KREV)
        !          1029:                return (-ret);
        !          1030:        return (ret);
        !          1031: }
        !          1032: 
        !          1033: /*
        !          1034:  * Parse a numeric field into sign, magnitude, integer and fractional parts.
        !          1035:  */
        !          1036: numpars(p, ep, np)
        !          1037: register char *p;
        !          1038: register char *ep;
        !          1039: register NUM *np;
        !          1040: {
        !          1041:        char *bp;
        !          1042:        char *fbgn;
        !          1043:        int fsum;
        !          1044: 
        !          1045:        bp = p;
        !          1046:        fbgn = NULL;
        !          1047:        fsum = 0;
        !          1048:        np->n_sign = 1;
        !          1049:        np->n_magn = 0;
        !          1050:        np->n_fmagn = 16000;
        !          1051:        np->n_bgn = NULL;
        !          1052:        for ( ; p < ep; p += 1)
        !          1053:                if (*p == '0') {
        !          1054:                        if (fbgn != NULL) {
        !          1055:                                if (fsum == 0)
        !          1056:                                        np->n_fmagn -= 1;
        !          1057:                        } else if (np->n_magn != 0)
        !          1058:                                np->n_magn += 1;
        !          1059:                } else if (isdigit(*p)) {
        !          1060:                        if (fbgn != NULL)
        !          1061:                                fsum += 1;
        !          1062:                        else if (np->n_magn++ == 0)
        !          1063:                                np->n_bgn = p;
        !          1064:                } else if (*p == '-') {
        !          1065:                        if (p != bp)
        !          1066:                                break;
        !          1067:                        np->n_sign = -1;
        !          1068:                } else if (*p == '.') {
        !          1069:                        if (fbgn != NULL || p+1 == ep)
        !          1070:                                break;
        !          1071:                        fbgn = p+1;
        !          1072:                } else {
        !          1073:                        break;
        !          1074:                }
        !          1075:        np->n_end = p;
        !          1076:        if (fsum == 0) {
        !          1077:                np->n_fmagn = 0;
        !          1078:                fbgn = NULL;
        !          1079:        }
        !          1080:        if (np->n_bgn == NULL)
        !          1081:                np->n_bgn = fbgn;
        !          1082:        if (np->n_bgn == NULL)
        !          1083:                np->n_bgn = p;
        !          1084: }
        !          1085: 
        !          1086: 
        !          1087: /*
        !          1088:  * Reversed version of strcmp.  If this
        !          1089:  * were more common, it could be written
        !          1090:  * out in full to save the extra routine call.
        !          1091:  */
        !          1092: rstrcmp(s1, s2)
        !          1093: char *s1, *s2;
        !          1094: {
        !          1095:        return (-strcmp(s1, s2));
        !          1096: }
        !          1097: 
        !          1098: /*
        !          1099:  * Make temporary file `n'.
        !          1100:  * Called as they are first needed.
        !          1101:  */
        !          1102: maketemp(n)
        !          1103: {
        !          1104: #ifdef COHERENT
        !          1105:        static int first = 1;
        !          1106:        char tempname[120];
        !          1107:        register FILE *fp;
        !          1108: 
        !          1109:        if (pid == 0) {
        !          1110:                pid = getpid();
        !          1111:                sprintf(template, "%s/sort%d%%c",
        !          1112:                    tempdir==NULL ? "/tmp" : tempdir, pid);
        !          1113:        }
        !          1114:        sprintf(tempname, template, n+'a');
        !          1115:        if ((fp = fopen(tempname, "w")) == NULL) {
        !          1116:                if (first && tempdir==NULL) {
        !          1117:                        sprintf(template, "/usr/tmp/sort%d%%c", pid);
        !          1118:                        sprintf(tempname, template, n+'a');
        !          1119:                        if ((fp = fopen(tempname, "w")) == NULL)
        !          1120:                                serr(temperr);
        !          1121:                } else
        !          1122:                        serr(temperr);
        !          1123:        }
        !          1124:        fclose(fp);
        !          1125:        if ((tfiles[n].tf_fp = fopen(tempname, "r+w")) == NULL)
        !          1126:                serr(temperr);
        !          1127:        setbuf(tfiles[n].tf_fp, alloc(BUFSIZ));
        !          1128:        first = 0;
        !          1129: #else
        !          1130:        char tempname[120];
        !          1131: 
        !          1132:        sprintf(tempname, "%ssortwrk%c",
        !          1133:                tempdir==NULL ? "" : tempdir, n+'a');
        !          1134:        if((tfiles[n].tf_fp=fopen(tempname, "wr"))==NULL)
        !          1135:                serr(temperr);
        !          1136:        setbuf(tfiles[n].tf_fp, alloc(BUFSIZ));
        !          1137: #endif
        !          1138: }
        !          1139: 
        !          1140: /* Errors and usage messages */
        !          1141: usage()
        !          1142: {
        !          1143:        fprintf(stderr, "Usage: sort [options] [+pos1 [-pos2]] ... [file ...]\n");
        !          1144:        fprintf(stderr, "Options: [-mubdfinr] [-tx] [-T directory] [-o name]\n");
        !          1145:        exit(1);
        !          1146: }
        !          1147: 
        !          1148: /* VARARGS */
        !          1149: serr(x)
        !          1150: {
        !          1151:        fprintf(stderr, "sort: %r\n", &x);
        !          1152:        rmexit(1);
        !          1153: }
        !          1154: 
        !          1155: /*
        !          1156:  * Exit, removing the tempfiles.
        !          1157:  */
        !          1158: rmexit(s)
        !          1159: int s;
        !          1160: {
        !          1161:        register int c;
        !          1162:        char tempname[120];
        !          1163: 
        !          1164:        for (c='a'; c<'a'+NTFILE; c++) {
        !          1165: #ifdef COHERENT
        !          1166:                sprintf(tempname, template, c);
        !          1167: #else
        !          1168:                sprintf(tempname, "%ssortwrk%c",
        !          1169:                        tempdir==NULL ? "" : tempdir, c);
        !          1170: #endif
        !          1171:                unlink(tempname);
        !          1172:        }
        !          1173: #ifdef COHERENT
        !          1174:        _exit(s);
        !          1175: #else
        !          1176:        exit(s);
        !          1177: #endif
        !          1178: }
        !          1179: 
        !          1180: #if COHERENT
        !          1181: /*
        !          1182:  * Protect from the specified signal number.
        !          1183:  * This makes that signal call the cleanup
        !          1184:  * routine, unless that signal was already ignored.
        !          1185:  */
        !          1186: protect(signo)
        !          1187: register int signo;
        !          1188: {
        !          1189:        if (signal(signo, SIG_IGN) != SIG_IGN)
        !          1190:                signal(signo, rmexit);
        !          1191: }
        !          1192: #endif
        !          1193: 
        !          1194: /*
        !          1195:  * Allocate a new run.  Uses our own threaded free list
        !          1196:  * and sbrk-style alloc when none of these.
        !          1197:  */
        !          1198: RUN *
        !          1199: ralloc()
        !          1200: {
        !          1201:        register RUN *p;
        !          1202: 
        !          1203:        if ((p = frlist) != NULL) {
        !          1204:                frlist = p->r_next;
        !          1205:                return (p);
        !          1206:        }
        !          1207:        return ((RUN *)alloc(sizeof (RUN)));
        !          1208: }
        !          1209: 
        !          1210: /*
        !          1211:  * This allocator simply does sbrk calls so that
        !          1212:  * it can grow (easily) the space as it needs without
        !          1213:  * threading it.  It also checks and prints an error
        !          1214:  * if out of space.
        !          1215:  */
        !          1216: char *
        !          1217: alloc(nb)
        !          1218: register unsigned nb;
        !          1219: {
        !          1220:        static int *rp, *ep;
        !          1221:        register int *cp;
        !          1222: 
        !          1223:        if ((nb = (nb+sizeof(int)-1)/sizeof(int)) == 0)
        !          1224:                serr(nomem);
        !          1225:        if (rp==NULL || rp+nb>=ep) {
        !          1226:                if ((ep = (int *)sbrk(NSBRK)) == BADSBRK)
        !          1227:                        serr(nomem);
        !          1228:                if (rp == NULL)
        !          1229:                        rp = ep;
        !          1230:                ep += NSBRK/sizeof(int);
        !          1231:        }
        !          1232:        cp = rp;
        !          1233:        rp += nb;
        !          1234:        return (cp);
        !          1235: }

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