![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sort.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / bin|
Return to sort.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin |
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.