![[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 [Research Unix] / researchv9 / cmd|
Return to sort.c CVS log | Up to [Research Unix] / researchv9 / cmd |
1.1 root 1: #include <stdio.h>
2: #include <ctype.h>
3: #include <signal.h>
4: #include <sys/types.h>
5: #include <sys/stat.h>
6:
7: #define N 16
8: #define C 20
9: #define NF 10
10: #define TREEZ 32 /* no less than N and best if power of 2 */
11:
12: /*
13: * Memory administration
14: *
15: * Using a lot of memory is great when sorting a lot of data.
16: * Using a megabyte to sort the output of `who' loses big.
17: * MAXMEM, MINMEM and DEFMEM define the absolute maximum,
18: * minimum and default memory requirements. Administrators
19: * can override any or all of these via defines at compile time.
20: * Users can override the amount allocated (within the limits
21: * of MAXMEM and MINMEM) on the command line.
22: */
23:
24: #ifndef MAXMEM
25: #define MAXMEM 1048576 /* Megabyte maximum */
26: #endif
27:
28: #ifndef MINMEM
29: #define MINMEM 16384 /* 16K minimum */
30: #endif
31:
32: #ifndef DEFMEM
33: #define DEFMEM 32768 /* Same as old sort */
34: #endif
35:
36: enum { ASC, NUM, MON, FLOAT };
37:
38: #define blank(c) ((c)==' ' || (c)=='\t')
39:
40: FILE *is, *os;
41: char *dirtry[] = {"/usr/tmp", "/tmp", NULL};
42: char **dirs;
43: char file1[100];
44: char *file = file1;
45: char *filep;
46: #define NAMEOHD 12 /* sizeof("/stm00000aa") */
47: int nfiles;
48: int *lspace;
49: unsigned alloc, tryfor;
50: char bufin[BUFSIZ], bufout[BUFSIZ]; /* Use setbuf's to avoid malloc calls.
51: ** malloc seems to get heartburn
52: ** when brk returns storage.
53: */
54: int maxrec;
55: int cmp(), cmpa();
56: int (*compare)() = cmpa;
57: char *eol();
58: int term();
59: double atof();
60: int mflg;
61: int nway;
62: int cflg;
63: int uflg;
64: char *outfil;
65: int unsafeout; /*kludge to assure -m -o works*/
66: char tabchar;
67: int eargc;
68: char **eargv;
69: struct btree {
70: char *rp;
71: int rn;
72: } tree[TREEZ], *treep[TREEZ];
73: int blkcnt[TREEZ];
74: char **blkcur[TREEZ];
75: long wasfirst = 0, notfirst = 0;
76: int bonus;
77:
78: char zero[256];
79:
80: char fold[256] = {
81: 0200,0201,0202,0203,0204,0205,0206,0207,
82: 0210,0211,0212,0213,0214,0215,0216,0217,
83: 0220,0221,0222,0223,0224,0225,0226,0227,
84: 0230,0231,0232,0233,0234,0235,0236,0237,
85: 0240,0241,0242,0243,0244,0245,0246,0247,
86: 0250,0251,0252,0253,0254,0255,0256,0257,
87: 0260,0261,0262,0263,0264,0265,0266,0267,
88: 0270,0271,0272,0273,0274,0275,0276,0277,
89: 0300,0301,0302,0303,0304,0305,0306,0307,
90: 0310,0311,0312,0313,0314,0315,0316,0317,
91: 0320,0321,0322,0323,0324,0325,0326,0327,
92: 0330,0331,0332,0333,0334,0335,0336,0337,
93: 0340,0341,0342,0343,0344,0345,0346,0347,
94: 0350,0351,0352,0353,0354,0355,0356,0357,
95: 0360,0361,0362,0363,0364,0365,0366,0367,
96: 0370,0371,0372,0373,0374,0375,0376,0377,
97: 0000,0001,0002,0003,0004,0005,0006,0007,
98: 0010,0011,0012,0013,0014,0015,0016,0017,
99: 0020,0021,0022,0023,0024,0025,0026,0027,
100: 0030,0031,0032,0033,0034,0035,0036,0037,
101: 0040,0041,0042,0043,0044,0045,0046,0047,
102: 0050,0051,0052,0053,0054,0055,0056,0057,
103: 0060,0061,0062,0063,0064,0065,0066,0067,
104: 0070,0071,0072,0073,0074,0075,0076,0077,
105: 0100,0101,0102,0103,0104,0105,0106,0107,
106: 0110,0111,0112,0113,0114,0115,0116,0117,
107: 0120,0121,0122,0123,0124,0125,0126,0127,
108: 0130,0131,0132,0133,0134,0135,0136,0137,
109: 0140,0101,0102,0103,0104,0105,0106,0107,
110: 0110,0111,0112,0113,0114,0115,0116,0117,
111: 0120,0121,0122,0123,0124,0125,0126,0127,
112: 0130,0131,0132,0173,0174,0175,0176,0177
113: };
114: char nofold[256] = {
115: 0200,0201,0202,0203,0204,0205,0206,0207,
116: 0210,0211,0212,0213,0214,0215,0216,0217,
117: 0220,0221,0222,0223,0224,0225,0226,0227,
118: 0230,0231,0232,0233,0234,0235,0236,0237,
119: 0240,0241,0242,0243,0244,0245,0246,0247,
120: 0250,0251,0252,0253,0254,0255,0256,0257,
121: 0260,0261,0262,0263,0264,0265,0266,0267,
122: 0270,0271,0272,0273,0274,0275,0276,0277,
123: 0300,0301,0302,0303,0304,0305,0306,0307,
124: 0310,0311,0312,0313,0314,0315,0316,0317,
125: 0320,0321,0322,0323,0324,0325,0326,0327,
126: 0330,0331,0332,0333,0334,0335,0336,0337,
127: 0340,0341,0342,0343,0344,0345,0346,0347,
128: 0350,0351,0352,0353,0354,0355,0356,0357,
129: 0360,0361,0362,0363,0364,0365,0366,0367,
130: 0370,0371,0372,0373,0374,0375,0376,0377,
131: 0000,0001,0002,0003,0004,0005,0006,0007,
132: 0010,0011,0012,0013,0014,0015,0016,0017,
133: 0020,0021,0022,0023,0024,0025,0026,0027,
134: 0030,0031,0032,0033,0034,0035,0036,0037,
135: 0040,0041,0042,0043,0044,0045,0046,0047,
136: 0050,0051,0052,0053,0054,0055,0056,0057,
137: 0060,0061,0062,0063,0064,0065,0066,0067,
138: 0070,0071,0072,0073,0074,0075,0076,0077,
139: 0100,0101,0102,0103,0104,0105,0106,0107,
140: 0110,0111,0112,0113,0114,0115,0116,0117,
141: 0120,0121,0122,0123,0124,0125,0126,0127,
142: 0130,0131,0132,0133,0134,0135,0136,0137,
143: 0140,0141,0142,0143,0144,0145,0146,0147,
144: 0150,0151,0152,0153,0154,0155,0156,0157,
145: 0160,0161,0162,0163,0164,0165,0166,0167,
146: 0170,0171,0172,0173,0174,0175,0176,0177
147: };
148:
149: char nonprint[256] = {
150: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
151: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
152: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
153: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
154: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
155: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
156: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
157: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
158: 1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
159: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
160: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
161: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
162: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
163: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
164: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
165: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
166: };
167:
168: char dict[256] = {
169: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
170: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
171: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
172: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
173: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
174: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
175: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
176: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
177: 1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
178: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
179: 0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
180: 0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
181: 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
182: 0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,
183: 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
184: 0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1
185: };
186:
187: struct field {
188: char *code;
189: char *ignore;
190: int fcmp;
191: int rflg;
192: int bflg[2];
193: int m[2];
194: int n[2];
195: } fields[NF];
196: struct field proto = {
197: nofold+128,
198: zero+128,
199: ASC,
200: 1,
201: 0,0,
202: 0,-1,
203: 0,0
204: };
205: int nfields;
206: int error = 1;
207: char *setfil();
208:
209: main(argc, argv)
210: char **argv;
211: {
212: register a;
213: char *arg;
214: struct field *p, *q;
215: int i;
216: long incr;
217: char *sbrk();
218: char *sp;
219:
220: copyproto();
221: initree();
222: eargv = argv;
223: tryfor = DEFMEM;
224: while (--argc > 0) {
225: if(**++argv == '-') for(arg = *argv;;) {
226: switch(*++arg) {
227: case '\0':
228: if(arg[-1] == '-')
229: eargv[eargc++] = "-";
230: break;
231:
232: case 'o':
233: if(--argc > 0)
234: outfil = *++argv;
235: continue;
236:
237: case 'T':
238: if (--argc > 0) {
239: if ((strlen(*++argv) + NAMEOHD) > sizeof(file1)) {
240: diag("path name too long:", *argv);
241: exit(1);
242: }
243: else dirtry[0] = *argv;
244: }
245: continue;
246:
247: default:
248: field(++*argv,nfields>0);
249: break;
250: }
251: break;
252: } else if (**argv == '+') {
253: if(++nfields>=NF) {
254: diag("too many keys","");
255: exit(1);
256: }
257: copyproto();
258: field(++*argv,0);
259: } else
260: eargv[eargc++] = *argv;
261: }
262: q = &fields[0];
263: for(a=1; a<=nfields; a++) {
264: p = &fields[a];
265: if(p->code != proto.code) continue;
266: if(p->ignore != proto.ignore) continue;
267: if(p->fcmp != proto.fcmp) continue;
268: if(p->rflg != proto.rflg) continue;
269: if(p->bflg[0] != proto.bflg[0]) continue;
270: if(p->bflg[1] != proto.bflg[1]) continue;
271: p->code = q->code;
272: p->ignore = q->ignore;
273: p->fcmp = q->fcmp;
274: p->rflg = q->rflg;
275: p->bflg[0] = p->bflg[1] = q->bflg[0];
276: }
277: if(eargc == 0)
278: eargv[eargc++] = "-";
279: if(cflg && eargc>1) {
280: diag("can check only 1 file","");
281: exit(1);
282: }
283:
284: safeoutfil();
285:
286: sp = sbrk(0);
287: lspace = (int *) sp;
288: if (!mflg && !cflg) {
289: if (tryfor < MINMEM) tryfor = MINMEM;
290: else if (tryfor > MAXMEM) tryfor = MAXMEM;
291: for (incr=tryfor; (sp + incr) <= sp; incr >>= 1);
292: do {
293: if ((long)alloc+incr <= tryfor && brk(sp+incr) == 0) {
294: sp += incr;
295: alloc += incr;
296: }
297: } while ( ( incr >>= 1 ) >= 512L );
298: if ( brk((char *) lspace + alloc) != 0) {
299: diag("allocation error before sort", "");
300: exit(1);
301: }
302: }
303:
304: a = -1;
305: for(dirs=dirtry; *dirs; dirs++) {
306: (void) sprintf(filep=file1, "%s/stm%.5uaa", *dirs, getpid());
307: while (*filep)
308: filep++;
309: filep -= 2;
310: if ( (a=creat(file, 0600)) >=0)
311: break;
312: }
313: if(a < 0) {
314: diag("can't locate temp","");
315: exit(1);
316: }
317: for (i = 3; i <= 20; i++)
318: (void) close(i);
319: (void) unlink(file);
320: if (signal(SIGHUP, SIG_IGN) != SIG_IGN)
321: (void) signal(SIGHUP, term);
322: if (signal(SIGINT, SIG_IGN) != SIG_IGN)
323: (void) signal(SIGINT, term);
324: (void) signal(SIGPIPE,term);
325: if (signal(SIGTERM, SIG_IGN) != SIG_IGN)
326: (void) signal(SIGTERM,term);
327: nfiles = eargc;
328: if(!mflg && !cflg) {
329: sort();
330: if (ferror(stdin))
331: rderror("stdin");
332: (void) fclose(stdin);
333: }
334:
335: if (maxrec == 0) maxrec = 512;
336: alloc = (N + 1) * maxrec + N * BUFSIZ;
337: for (nway = N; nway >= 2; --nway) {
338: if (brk((char *)lspace + alloc) == 0) break;
339: alloc -= maxrec + BUFSIZ;
340: }
341: if (nway < 2) {
342: diag("allocation error before merge", "");
343: term();
344: }
345:
346: if (cflg) checksort();
347:
348: wasfirst = notfirst = 0;
349: a = mflg || cflg ? 0 : eargc;
350: if ((i = nfiles - a) > nway) { /* Do leftovers early */
351: if ((i %= (nway - 1)) == 0)
352: i = nway - 1;
353: if (i != 1) {
354: newfile();
355: (void) setbuf(os, bufout);
356: merge(a,a+i);
357: a += i;
358: }
359: }
360: for(; a+nway<nfiles || unsafeout&&a<eargc; a=i) {
361: i = a+nway;
362: if(i>=nfiles)
363: i = nfiles;
364: newfile();
365: (void) setbuf(os, bufout);
366: merge(a, i);
367: }
368: if(a != nfiles) {
369: oldfile();
370: (void) setbuf(os, bufout);
371: merge(a, nfiles);
372: }
373: error = 0;
374: term();
375: }
376:
377: sort()
378: {
379: register char *cp;
380: register c;
381: register char **lp;
382: register FILE *iop;
383: char *keep, *ekeep, **ep;
384: int done, i, recz;
385: char *f;
386:
387: /*
388: ** Records are read in from the front of the buffer area.
389: ** Pointers to the records are allocated from the back of the buffer.
390: ** If a partially read record exhausts the buffer, it is saved and
391: ** then copied to the start of the buffer for processing with the
392: ** next coreload.
393: */
394: done = 0;
395: keep = 0;
396: i = 0;
397: iop = NULL;
398: c = EOF;
399: ep = (char **) (((char *) lspace) + alloc);
400: do {
401: lp = ep - 1;
402: cp = (char *) lspace;
403: if (keep != 0) { /* part of record from previous coreload */
404: *lp-- = cp;
405: for(; keep < ekeep; *cp++ = *keep++);
406: }
407: while (cp < (char *) lp) {
408: if (keep == 0) *lp-- = cp;
409: while (cp < (char *) lp && c != '\n') {
410: if(c != EOF) {
411: *cp++ = c;
412: c = getc(iop);
413: continue;
414: } else if(iop != NULL) {
415: if ((cp > (char *) lspace) && (cp[-1] != '\n'))
416: *cp++ = '\n';
417: if(ferror(iop))
418: rderror(f);
419: (void) fclose(iop);
420: }
421: if(i < eargc) {
422: if((f = setfil(i++)) == 0)
423: iop = stdin;
424: else if((iop = fopen(f, "r")) == NULL)
425: cant(f);
426: (void) setbuf(iop, bufin);
427: c = getc(iop);
428: } else
429: break;
430: }
431: if (c == '\n') {
432: *cp++ = '\n';
433: keep = 0;
434: if ((recz = (cp - lp[1])) > maxrec)
435: maxrec = recz;
436: }
437: else if (c != EOF) { /* save partial record */
438: lp++;
439: if (keep != 0) {
440: diag("whopper record won't fit", "");
441: term();
442: }
443: keep = *lp;
444: ekeep = cp;
445: break;
446: }
447: if(c == EOF) {
448: if(ferror(iop))
449: rderror(f);
450: (void) fclose(iop);
451: done++;
452: lp++;
453: break;
454: }
455: c = getc(iop);
456: }
457: lp++;
458: if(done == 0 || nfiles != eargc)
459: newfile();
460: else
461: oldfile();
462: (void) setbuf(os, bufout);
463: msort(lp, ep);
464: if (ferror(os))
465: wterror("sorting");
466: (void) fclose(os);
467: } while(done == 0);
468: }
469:
470:
471: msort(a, b)
472: char **a, **b;
473: {
474: register struct btree **tp;
475: register int i, j, n;
476: char *save;
477:
478: i = (b - a);
479: if (i < 1) return;
480: else if (i >= TREEZ) n = TREEZ; /* number of blocks of records */
481: else n = i;
482:
483: /* break into n sorted subgroups of approximately equal size */
484: tp = &(treep[0]);
485: j = 0;
486: do {
487: (*tp++)->rn = j;
488: b = a + (blkcnt[j] = i / n);
489: qsort(a, b);
490: blkcur[j] = a = b;
491: i -= blkcnt[j++];
492: } while (--n > 0);
493: n = j;
494:
495: /* make a sorted binary tree using the first record in each group */
496: for (i = 0; i < n;) {
497: (*--tp)->rp = *(--blkcur[--j]);
498: insert(tp, ++i);
499: }
500: wasfirst = notfirst = 0;
501: bonus = cmpsave(n);
502:
503:
504: j = uflg;
505: tp = &(treep[0]);
506: while (n > 0) {
507: wline((*tp)->rp);
508: if (j) save = (*tp)->rp;
509:
510: /* Get another record and insert. Bypass repeats if uflg */
511:
512: do {
513: i = (*tp)->rn;
514: if (j) while((blkcnt[i] > 1) &&
515: (**(blkcur[i]-1) == '\0')) {
516: --blkcnt[i];
517: --blkcur[i];
518: }
519: if (--blkcnt[i] > 0) {
520: (*tp)->rp = *(--blkcur[i]);
521: insert(tp, n);
522: } else {
523: if (--n <= 0) break;
524: bonus = cmpsave(n);
525: tp++;
526: }
527: } while (j && (*compare)((*tp)->rp, save) == 0);
528: }
529: }
530:
531:
532: /* Insert the element at tp[0] into its proper place in the array of size n */
533: /* Pretty much Algorith B from 6.2.1 of Knuth, Sorting and Searching */
534: /* Special case for data that appears to be in correct order */
535:
536: insert(tp, n)
537: struct btree **tp;
538: int n;
539: {
540: register struct btree **lop, **hip, **midp;
541: register int c;
542: struct btree *hold;
543:
544: midp = lop = tp;
545: hip = lop++ + (n - 1);
546: if ((wasfirst > notfirst) && (n > 2) &&
547: ((*compare)((*tp)->rp, (*lop)->rp) >= 0)) {
548: wasfirst += bonus;
549: return;
550: }
551: while ((c = hip - lop) >= 0) { /* leave midp at the one tp is in front of */
552: midp = lop + c / 2;
553: if ((c = (*compare)((*tp)->rp, (*midp)->rp)) == 0) break; /* match */
554: if (c < 0) lop = ++midp; /* c < 0 => tp > midp */
555: else hip = midp - 1; /* c > 0 => tp < midp */
556: }
557: c = midp - tp;
558: if (--c > 0) { /* number of moves to get tp just before midp */
559: hip = tp;
560: lop = hip++;
561: hold = *lop;
562: do *lop++ = *hip++; while (--c > 0);
563: *lop = hold;
564: notfirst++;
565: } else wasfirst += bonus;
566: }
567:
568:
569: merge(a, b)
570: {
571: FILE *tfile[N];
572: char *buffer = (char *) lspace;
573: register int nf; /* number of merge files */
574: register struct btree **tp;
575: register int i, j;
576: char *t, *f;
577: char *save, *iobuf;
578:
579: save = (char *) lspace + (nway * maxrec);
580: iobuf = save + maxrec;
581: tp = &(treep[0]);
582: for (nf=0, i=a; i < b; i++) {
583: f = setfil(i);
584: if (f == 0)
585: tfile[nf] = stdin;
586: else if ((tfile[nf] = fopen(f, "r")) == NULL)
587: cant(f);
588: (*tp)->rp = buffer + (nf * maxrec);
589: (*tp)->rn = nf;
590: (void) setbuf(tfile[nf],iobuf);
591: iobuf += BUFSIZ;
592: if (rline(tfile[nf], (*tp)->rp)==0) {
593: nf++;
594: tp++;
595: } else {
596: if(ferror(tfile[nf]))
597: rderror(f);
598: (void) fclose(tfile[nf]);
599: }
600: }
601:
602:
603: /* make a sorted btree from the first record of each file */
604: for (--tp, i = 1; i++ < nf;) insert(--tp, i);
605:
606: bonus = cmpsave(nf);
607: tp = &(treep[0]);
608: j = uflg;
609: while (nf > 0) {
610: wline((*tp)->rp);
611: if (j) cline(save, (*tp)->rp);
612:
613: /* Get another record and insert. Bypass repeats if uflg */
614:
615: do {
616: i = (*tp)->rn;
617: if (rline(tfile[i], (*tp)->rp)) {
618: if (ferror(tfile[i]))
619: rderror(setfil(i+a));
620: (void) fclose(tfile[i]);
621: if (--nf <= 0) break;
622: ++tp;
623: bonus = cmpsave(nf);
624: } else insert(tp, nf);
625: } while (j && (*compare)((*tp)->rp, save) == 0 );
626: }
627:
628:
629: for (i=a; i < b; i++) {
630: if (i >= eargc)
631: (void) unlink(setfil(i));
632: }
633: if (ferror(os))
634: wterror("merging");
635: (void) fclose(os);
636: }
637:
638: wline(s)
639: register char *s;
640: {
641: register FILE *iop;
642:
643: iop = os;
644: do
645: putc(*s, iop);
646: while (*s++ != '\n');
647: }
648:
649: cline(tp, fp)
650: register char *tp, *fp;
651: {
652: while ((*tp++ = *fp++) != '\n');
653: }
654:
655: rline(iop, s)
656: FILE *iop;
657: register char *s;
658: {
659: register char *ce;
660: register int c;
661: register FILE *riop;
662:
663: riop = iop;
664: ce = s + maxrec;
665: do {
666: c = getc(riop);
667: if (c == EOF)
668: return(1);
669: if (s >= ce)
670: --s;
671: *s++ = c;
672: } while (c != '\n');
673: return(0);
674: }
675:
676:
677: checksort()
678: {
679: char *f;
680: char *s[2];
681: register int i, j, r;
682:
683: f = setfil(0);
684: if (f == 0)
685: is = stdin;
686: else if ((is = fopen(f, "r")) == NULL)
687: cant(f);
688: (void) setbuf(is, bufin);
689:
690: i = 0; j = 1;
691: s[0] = (char *) lspace;
692: s[1] = s[0] + maxrec;
693: if ( rline(is, s[0]) ) {
694: if (ferror(is)) {
695: rderror(f);
696: }
697: (void) fclose(is);
698: exit(0);
699: }
700: while ( !rline(is, s[j]) ) {
701: r = (*compare)(s[i], s[j]);
702: if (r < 0)
703: disorder("disorder: ", s[j]);
704: if (r == 0 && uflg)
705: disorder("non-unique: ", s[j]);
706: r = i; i = j; j = r;
707: }
708: if (ferror(is))
709: rderror(f);
710: (void) fclose(is);
711: exit(0);
712: }
713:
714:
715: disorder(s,t)
716: char *s, *t;
717: {
718: register char *u;
719: for(u=t; *u!='\n';u++) ;
720: *u = 0;
721: diag(s,t);
722: term();
723: }
724:
725: newfile()
726: {
727: register char *f;
728:
729: f = setfil(nfiles);
730: if((os=fopen(f, "w")) == NULL) {
731: diag("can't create ",f);
732: term();
733: }
734: nfiles++;
735: }
736:
737: char *
738: setfil(i)
739: {
740:
741: if(i < eargc)
742: if(eargv[i][0] == '-' && eargv[i][1] == '\0')
743: return(0);
744: else
745: return(eargv[i]);
746: i -= eargc;
747: filep[0] = i/26 + 'a';
748: filep[1] = i%26 + 'a';
749: return(file);
750: }
751:
752: oldfile()
753: {
754:
755: if(outfil) {
756: if((os=fopen(outfil, "w")) == NULL) {
757: diag("can't create ",outfil);
758: term();
759: }
760: } else
761: os = stdout;
762: }
763:
764: safeoutfil()
765: {
766: register int i;
767: struct stat ostat,istat;
768:
769: if(!mflg||outfil==0)
770: return;
771: if(stat(outfil,&ostat)==-1)
772: return;
773: if ((i = eargc - N) < 0) i = 0; /*-N is suff., not nec. */
774: for (; i < eargc; i++) {
775: if(stat(eargv[i],&istat)==-1)
776: continue;
777: if(ostat.st_dev==istat.st_dev&&
778: ostat.st_ino==istat.st_ino)
779: unsafeout++;
780: }
781: }
782:
783: cant(f)
784: char *f;
785: {
786:
787: diag("can't open ",f);
788: term();
789: }
790:
791: diag(s,t)
792: char *s, *t;
793: {
794: (void) fputs("sort: ",stderr);
795: (void) fputs(s,stderr);
796: (void) fputs(t,stderr);
797: (void) fputs("\n",stderr);
798: }
799:
800: term()
801: {
802: register i;
803:
804: (void) signal(SIGINT, SIG_IGN);
805: (void) signal(SIGHUP, SIG_IGN);
806: (void) signal(SIGTERM, SIG_IGN);
807: if(nfiles == eargc)
808: nfiles++;
809: for(i=eargc; i<=nfiles; i++) { /*<= in case of interrupt*/
810: (void) unlink(setfil(i)); /*with nfiles not updated*/
811: }
812: exit(error);
813: }
814:
815: cmp(i, j)
816: char *i, *j;
817: {
818: register char *pa, *pb;
819: char *skip();
820: char *code, *ignore;
821: int a, b;
822: int k;
823: char *la, *lb;
824: register int sa;
825: int sb;
826: char *ipa, *ipb, *jpa, *jpb;
827: struct field *fp;
828: double za, zb;
829:
830: for(k = nfields>0; k<=nfields; k++) {
831: fp = &fields[k];
832: pa = i;
833: pb = j;
834: if(k) {
835: la = skip(pa, fp, 1);
836: pa = skip(pa, fp, 0);
837: lb = skip(pb, fp, 1);
838: pb = skip(pb, fp, 0);
839: } else {
840: la = eol(pa);
841: lb = eol(pb);
842: }
843: switch(fp->fcmp) {
844: case NUM:
845: sa = sb = fp->rflg;
846: while(blank(*pa))
847: pa++;
848: while(blank(*pb))
849: pb++;
850: if(*pa == '-') {
851: pa++;
852: sa = -sa;
853: }
854: if(*pb == '-') {
855: pb++;
856: sb = -sb;
857: }
858: for(ipa = pa; ipa<la&&isdigit(*ipa); ipa++) ;
859: for(ipb = pb; ipb<lb&&isdigit(*ipb); ipb++) ;
860: jpa = ipa;
861: jpb = ipb;
862: a = 0;
863: if(sa==sb)
864: while(ipa > pa && ipb > pb)
865: if(b = *--ipb - *--ipa)
866: a = b;
867: while(ipa > pa)
868: if(*--ipa != '0')
869: return(-sa);
870: while(ipb > pb)
871: if(*--ipb != '0')
872: return(sb);
873: if(a) return(a*sa);
874: if(*(pa=jpa) == '.')
875: pa++;
876: if(*(pb=jpb) == '.')
877: pb++;
878: if(sa==sb)
879: while(pa<la && isdigit(*pa)
880: && pb<lb && isdigit(*pb))
881: if(a = *pb++ - *pa++)
882: return(a*sa);
883: while(pa<la && isdigit(*pa))
884: if(*pa++ != '0')
885: return(-sa);
886: while(pb<lb && isdigit(*pb))
887: if(*pb++ != '0')
888: return(sb);
889: continue;
890: case MON:
891: sa = fp->rflg*(month(pb)-month(pa));
892: if(sa)
893: return(sa);
894: else
895: continue;
896: case FLOAT:
897: zb = atof(pb);
898: za = atof(pa);
899: return (zb>za?fp->rflg:zb==za?0:-fp->rflg);
900: }
901: code = fp->code;
902: ignore = fp->ignore;
903: loop:
904: while(ignore[*pa])
905: pa++;
906: while(ignore[*pb])
907: pb++;
908: if(pa>=la || *pa=='\n')
909: if(pb<lb && *pb!='\n')
910: return(fp->rflg);
911: else continue;
912: if(pb>=lb || *pb=='\n')
913: return(-fp->rflg);
914: if((sa = code[*pb++]-code[*pa++]) == 0)
915: goto loop;
916: return(sa*fp->rflg);
917: }
918: if(uflg)
919: return(0);
920: return(cmpa(i, j));
921: }
922:
923: cmpa(pa, pb)
924: register char *pa, *pb;
925: {
926: while(*pa == *pb++)
927: if(*pa++ == '\n')
928: return(0);
929: return(
930: *pa == '\n' ? fields[0].rflg:
931: *--pb == '\n' ?-fields[0].rflg:
932: *pb > *pa ? fields[0].rflg:
933: -fields[0].rflg
934: );
935: }
936:
937: char *
938: skip(p, fp, j)
939: struct field *fp;
940: register char *p;
941: {
942: register i;
943: register char tbc;
944:
945: if( (i=fp->m[j]) < 0)
946: return(eol(p));
947: if (tbc = tabchar)
948: while (--i >= 0) {
949: while(*p != tbc)
950: if(*p != '\n')
951: p++;
952: else goto ret;
953: p++;
954: }
955: else while (--i >= 0) {
956: while(blank(*p))
957: p++;
958: while(!blank(*p))
959: if(*p != '\n')
960: p++;
961: else goto ret;
962: }
963: if(fp->bflg[j])
964: while(blank(*p))
965: p++;
966: i = fp->n[j];
967: if(i==0 && j!=0 && fp->m[j]>0 && p[-1]==tbc)
968: p--;
969: while((i-- > 0) && (*p != '\n'))
970: p++;
971: ret:
972: return(p);
973: }
974:
975: char *
976: eol(p)
977: register char *p;
978: {
979: while(*p != '\n') p++;
980: return(p);
981: }
982:
983: copyproto()
984: {
985: register i;
986: register int *p, *q;
987:
988: p = (int *)&proto;
989: q = (int *)&fields[nfields];
990: for(i=0; i<sizeof(proto)/sizeof(*p); i++)
991: *q++ = *p++;
992: }
993:
994: initree()
995: {
996: register struct btree **tpp, *tp;
997: register int i;
998:
999: for (tp = &(tree[0]), tpp = &(treep[0]), i = TREEZ; --i >= 0;)
1000: *tpp++ = tp++;
1001: }
1002:
1003: cmpsave(n)
1004: register int n;
1005: {
1006: register int award;
1007:
1008: if (n < 2) return (0);
1009: for (n++, award = 0; (n >>= 1) > 0; award++);
1010: return (award);
1011: }
1012:
1013:
1014: field(s,k)
1015: char *s;
1016: {
1017: register struct field *p;
1018: register d;
1019: p = &fields[nfields];
1020: d = 0;
1021: for(; *s!=0; s++) {
1022: switch(*s) {
1023: case '\0':
1024: return;
1025:
1026: case 'b':
1027: p->bflg[k]++;
1028: break;
1029:
1030: case 'd':
1031: p->ignore = dict+128;
1032: break;
1033:
1034: case 'f':
1035: p->code = fold+128;
1036: break;
1037: case 'i':
1038: p->ignore = nonprint+128;
1039: break;
1040:
1041: case 'c':
1042: cflg = 1;
1043: continue;
1044:
1045: case 'm':
1046: mflg = 1;
1047: continue;
1048:
1049: case 'M':
1050: p->fcmp = MON;
1051: break;
1052:
1053: case 'n':
1054: p->fcmp = NUM;
1055: break;
1056: case 'g':
1057: p->fcmp = FLOAT;
1058: break;
1059: case 't':
1060: tabchar = *++s;
1061: if(tabchar == 0) s--;
1062: continue;
1063:
1064: case 'r':
1065: p->rflg = -1;
1066: continue;
1067: case 'u':
1068: uflg = 1;
1069: continue;
1070:
1071: case 'y':
1072: if ( *++s ) tryfor = number(&s);
1073: else {
1074: --s;
1075: tryfor = MAXMEM;
1076: }
1077: continue;
1078:
1079: case 'z':
1080: if ( *++s )
1081: maxrec = number(&s);
1082: else --s;
1083: continue;
1084:
1085: case '.':
1086: if(p->m[k] == -1) /* -m.n with m missing */
1087: p->m[k] = 0;
1088: d = &fields[0].n[0]-&fields[0].m[0];
1089: if (*++s == '\0') {
1090: --s;
1091: p->m[k+d] = 0;
1092: continue;
1093: }
1094:
1095: default:
1096: p->m[k+d] = number(&s);
1097: }
1098: compare = cmp;
1099: }
1100: }
1101:
1102: number(ppa)
1103: char **ppa;
1104: {
1105: int n;
1106: register char *pa;
1107: pa = *ppa;
1108: n = 0;
1109: while(isdigit(*pa)) {
1110: n = n*10 + *pa - '0';
1111: *ppa = pa++;
1112: }
1113: return(n);
1114: }
1115:
1116: #define qsexc(p,q) t= *p;*p= *q;*q=t
1117: #define qstexc(p,q,r) t= *p;*p= *r;*r= *q;*q=t
1118:
1119: qsort(a,l)
1120: char **a, **l;
1121: {
1122: register char **i, **j;
1123: register char **lp, **hp;
1124: char **k;
1125: int c, d;
1126: char *t;
1127: unsigned n;
1128:
1129:
1130: start:
1131: if((n=l-a) <= 1)
1132: return;
1133:
1134: i = a;
1135: j = l - 1;
1136: if (n == 2) {
1137: if (c = (*compare)(*i, *j)) {
1138: if (c > 0) {
1139: qsexc(i, j);
1140: }
1141: } else if (uflg) **i = '\0';
1142: return;
1143: }
1144: n /= 2;
1145: lp = hp = a + n;
1146: c = (*compare)(*i, *lp);
1147: d = (*compare)(*lp, *j);
1148: if (c == 0) {
1149: if (d == 0) { /* x x x */
1150: --lp; qsexc(i, lp);
1151: hp++; qsexc(hp, j);
1152: } else if (d > 0) { /* x x w */
1153: qsexc(i, j);
1154: i++;
1155: hp++; qsexc(hp, j);
1156: } else { /* x x y */
1157: --j;
1158: --lp; qsexc(i, lp);
1159: }
1160: } else if (d == 0) {
1161: if (c < 0) { /* w x x */
1162: i++;
1163: hp++; qsexc(hp, j);
1164: } else { /* y x x */
1165: qsexc(i, j);
1166: --j;
1167: --lp; qsexc(i, lp);
1168: }
1169: } else if (c > 0) {
1170: if (d > 0) { /* z y x */
1171: qsexc(i, j);
1172: i++; --j;
1173: } else { /* z y z' */
1174: qsexc(i, lp);
1175: i++;
1176: if (c = (*compare)(*lp, *j)) {
1177: if (c > 0) {
1178: qsexc(lp, j);
1179: }
1180: --j;
1181: } else {
1182: hp++; qsexc(hp, j);
1183: }
1184: }
1185: } else {
1186: if (d > 0) { /* y z y' */
1187: qsexc(lp, j);
1188: --j;
1189: if (c = (*compare)(*i, *lp)) {
1190: if (c > 0) {
1191: qsexc(i, lp);
1192: }
1193: i++;
1194: } else {
1195: --lp;
1196: qsexc(i, lp);
1197: }
1198: } else { /* x y z */
1199: i++; --j;
1200: }
1201: }
1202:
1203:
1204: for(;;) {
1205: if(i < lp) {
1206: if((c = (*compare)(*i, *lp)) == 0) {
1207: --lp;
1208: qsexc(i, lp);
1209: continue;
1210: }
1211: if(c < 0) {
1212: ++i;
1213: continue;
1214: }
1215: }
1216:
1217: loop:
1218: if(j > hp) {
1219: if((c = (*compare)(*hp, *j)) == 0) {
1220: ++hp;
1221: qsexc(hp, j);
1222: goto loop;
1223: }
1224: if(c > 0) {
1225: if(i == lp) {
1226: ++hp;
1227: qstexc(i, hp, j);
1228: i = ++lp;
1229: goto loop;
1230: }
1231: qsexc(i, j);
1232: --j;
1233: ++i;
1234: continue;
1235: }
1236: --j;
1237: goto loop;
1238: }
1239:
1240:
1241: if(i == lp) {
1242: if(uflg)
1243: for(k=lp; k<hp;) **k++ = '\0';
1244: if(lp-a >= l-hp) {
1245: qsort(hp+1, l);
1246: l = lp;
1247: } else {
1248: qsort(a, lp);
1249: a = hp+1;
1250: }
1251: goto start;
1252: }
1253:
1254:
1255: --lp;
1256: qstexc(j, lp, i);
1257: j = --hp;
1258: }
1259: }
1260:
1261: char * months[] = {
1262: "jan",
1263: "feb",
1264: "mar",
1265: "apr",
1266: "may",
1267: "jun",
1268: "jul",
1269: "aug",
1270: "sep",
1271: "oct",
1272: "nov",
1273: "dec"
1274: };
1275: month(s)
1276: char *s;
1277: {
1278: register char *t, *u;
1279: register i;
1280: char *f = fold + 128;
1281:
1282: while(blank(*s))
1283: s++;
1284: for(i=0; i<sizeof(months)/sizeof(*months); i++) {
1285: for(t=s,u=months[i]; f[*t++]==f[*u++]; )
1286: if(*u==0)
1287: return(i);
1288: }
1289: return(-1);
1290: }
1291:
1292:
1293: rderror(s)
1294: char *s;
1295: {
1296: diag("read error on ", s == 0 ? "stdin" : s);
1297: term();
1298: }
1299:
1300: wterror(s)
1301: char *s;
1302: {
1303: diag("write error while ", s);
1304: term();
1305: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.