![[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] / researchv10no / cmd|
Return to sort.c CVS log | Up to [Research Unix] / researchv10no / 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 16777216 /* 2^24 maximum */
26: #endif
27:
28: #ifndef MINMEM
29: #define MINMEM 16384 /* 16K minimum */
30: #endif
31:
32: #ifndef DEFMEM
33: #define DEFMEM 262144 /* old sort was 32768 */
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:
331: if (maxrec == 0) maxrec = 512;
332: alloc = (N + 1) * maxrec + N * BUFSIZ;
333: for (nway = N; nway >= 2; --nway) {
334: if (brk((char *)lspace + alloc) == 0) break;
335: alloc -= maxrec + BUFSIZ;
336: }
337: if (nway < 2) {
338: diag("allocation error before merge", "");
339: term();
340: }
341:
342: if (cflg) checksort();
343:
344: wasfirst = notfirst = 0;
345: a = mflg || cflg ? 0 : eargc;
346: if ((i = nfiles - a) > nway) { /* Do leftovers early */
347: if ((i %= (nway - 1)) == 0)
348: i = nway - 1;
349: if (i != 1) {
350: newfile();
351: (void) setbuf(os, bufout);
352: merge(a,a+i);
353: a += i;
354: }
355: }
356: for(; a+nway<nfiles || unsafeout&&a<eargc; a=i) {
357: i = a+nway;
358: if(i>=nfiles)
359: i = nfiles;
360: newfile();
361: (void) setbuf(os, bufout);
362: merge(a, i);
363: }
364: if(a != nfiles) {
365: oldfile();
366: (void) setbuf(os, bufout);
367: merge(a, nfiles);
368: }
369: error = 0;
370: term();
371: }
372:
373: #define OPEN(i) do{\
374: if((f=setfil(i++))==0)iop=stdin; \
375: else if((iop=fopen(f,"r"))==NULL)cant(f); \
376: (void)setbuf(iop,bufin);}while(0)
377:
378: #define GETC(c) \
379: while((c=getc(iop))==EOF) { \
380: if(!checkclose(iop))\
381: rderror(f); \
382: if(i<eargc) \
383: OPEN(i); \
384: else break; \
385: }
386: sort()
387: {
388: register FILE *iop;
389: register int c;
390: register char *cp,**lp;
391: int i;
392: char **ep;
393: char *f=0;
394: /*
395: lp[2] points to char after last \n or to beginning.
396: lp[3] points to second previous, etc.
397: (lp kept 2 below active cell in case machines
398: address char** by high byte)
399: cp grows toward lp; buffer is full when they meet.
400: */
401:
402: cp=(char*)lspace;
403: ep=(char**)((char*)lspace+alloc);
404: lp=ep-2;
405: (--lp)[2]=cp;
406: i=0;
407: OPEN(i);
408: GETC(c);
409: for(;;) {
410: while(c!=EOF&&cp<(char*)lp) {
411: *cp++=c;
412: if(c=='\n') {
413: (--lp)[2]=cp;
414: if(cp-lp[3]>maxrec)maxrec=cp-lp[3];
415: }
416: GETC(c);
417: }
418: /* buffer full or end of input files */
419: if(c==EOF)
420: break;
421: if((char*)lp[2]==(char*)lspace) {
422: diag("whopper record won't fit","");
423: term();
424: }
425: newfile();
426: (void)setbuf(os,bufout);
427: msort(lp+3,ep);
428: if(cp[-1]!='\n') {
429: (void) memcpy((char*)lspace,lp[2],cp-lp[2]);
430: cp-=lp[2]-(char*)lspace;
431: }
432: else
433: cp=(char*)lspace;
434: if(!checkclose(os))
435: wterror("sorting");
436: lp=ep-2;
437: (--lp)[2]=(char*)lspace;
438: }
439: /* end of input files */
440: if(cp>(char*)lspace&&cp[-1]!='\n') {
441: *cp++='\n';
442: (--lp);
443: if(cp-lp[3]>maxrec)maxrec=cp-lp[3];
444: }
445: if(nfiles==eargc)oldfile();
446: else newfile();
447: (void)setbuf(os,bufout);
448: msort(lp+3,ep);
449: if(!checkclose(os))
450: wterror("sorting");
451: }
452:
453: msort(a, b)
454: char **a, **b;
455: {
456: register struct btree **tp;
457: register int i, j, n;
458: char *save;
459:
460: i = (b - a);
461: if (i < 1) return;
462: else if (i >= TREEZ) n = TREEZ; /* number of blocks of records */
463: else n = i;
464:
465: /* break into n sorted subgroups of approximately equal size */
466: tp = &(treep[0]);
467: j = 0;
468: do {
469: (*tp++)->rn = j;
470: b = a + (blkcnt[j] = i / n);
471: qsort(a, b);
472: blkcur[j] = a = b;
473: i -= blkcnt[j++];
474: } while (--n > 0);
475: n = j;
476:
477: /* make a sorted binary tree using the first record in each group */
478: for (i = 0; i < n;) {
479: (*--tp)->rp = *(--blkcur[--j]);
480: insert(tp, ++i);
481: }
482: wasfirst = notfirst = 0;
483: bonus = cmpsave(n);
484:
485:
486: j = uflg;
487: tp = &(treep[0]);
488: while (n > 0) {
489: wline((*tp)->rp);
490: if (j) save = (*tp)->rp;
491:
492: /* Get another record and insert. Bypass repeats if uflg */
493:
494: do {
495: i = (*tp)->rn;
496: if (j) while((blkcnt[i] > 1) &&
497: (**(blkcur[i]-1) == '\0')) {
498: --blkcnt[i];
499: --blkcur[i];
500: }
501: if (--blkcnt[i] > 0) {
502: (*tp)->rp = *(--blkcur[i]);
503: insert(tp, n);
504: } else {
505: if (--n <= 0) break;
506: bonus = cmpsave(n);
507: tp++;
508: }
509: } while (j && (*compare)((*tp)->rp, save) == 0);
510: }
511: }
512:
513:
514: /* Insert the element at tp[0] into its proper place in the array of size n */
515: /* Pretty much Algorith B from 6.2.1 of Knuth, Sorting and Searching */
516: /* Special case for data that appears to be in correct order */
517:
518: insert(tp, n)
519: struct btree **tp;
520: int n;
521: {
522: register struct btree **lop, **hip, **midp;
523: register int c;
524: struct btree *hold;
525:
526: midp = lop = tp;
527: hip = lop++ + (n - 1);
528: if ((wasfirst > notfirst) && (n > 2) &&
529: ((*compare)((*tp)->rp, (*lop)->rp) >= 0)) {
530: wasfirst += bonus;
531: return;
532: }
533: while ((c = hip - lop) >= 0) { /* leave midp at the one tp is in front of */
534: midp = lop + c / 2;
535: if ((c = (*compare)((*tp)->rp, (*midp)->rp)) == 0) break; /* match */
536: if (c < 0) lop = ++midp; /* c < 0 => tp > midp */
537: else hip = midp - 1; /* c > 0 => tp < midp */
538: }
539: c = midp - tp;
540: if (--c > 0) { /* number of moves to get tp just before midp */
541: hip = tp;
542: lop = hip++;
543: hold = *lop;
544: do *lop++ = *hip++; while (--c > 0);
545: *lop = hold;
546: notfirst++;
547: } else wasfirst += bonus;
548: }
549:
550:
551: merge(a, b)
552: {
553: FILE *tfile[N];
554: char *buffer = (char *) lspace;
555: register int nf; /* number of merge files */
556: register struct btree **tp;
557: register int i, j;
558: char *t, *f;
559: char *save, *iobuf;
560:
561: save = (char *) lspace + (nway * maxrec);
562: iobuf = save + maxrec;
563: tp = &(treep[0]);
564: for (nf=0, i=a; i < b; i++) {
565: f = setfil(i);
566: if (f == 0)
567: tfile[nf] = stdin;
568: else if ((tfile[nf] = fopen(f, "r")) == NULL)
569: cant(f);
570: (*tp)->rp = buffer + (nf * maxrec);
571: (*tp)->rn = nf;
572: (void) setbuf(tfile[nf],iobuf);
573: iobuf += BUFSIZ;
574: if (rline(tfile[nf], (*tp)->rp)==0) {
575: nf++;
576: tp++;
577: } else if(!checkclose(tfile[nf]))
578: rderror(f);
579: }
580:
581:
582: /* make a sorted btree from the first record of each file */
583: for (--tp, i = 1; i++ < nf;) insert(--tp, i);
584:
585: bonus = cmpsave(nf);
586: tp = &(treep[0]);
587: j = uflg;
588: while (nf > 0) {
589: wline((*tp)->rp);
590: if (j) cline(save, (*tp)->rp);
591:
592: /* Get another record and insert. Bypass repeats if uflg */
593:
594: do {
595: i = (*tp)->rn;
596: if (rline(tfile[i], (*tp)->rp)) {
597: if (!checkclose(tfile[i]))
598: rderror(setfil(i+a));
599: if (--nf <= 0) break;
600: ++tp;
601: bonus = cmpsave(nf);
602: } else insert(tp, nf);
603: } while (j && (*compare)((*tp)->rp, save) == 0 );
604: }
605:
606:
607: for (i=a; i < b; i++) {
608: if (i >= eargc)
609: (void) unlink(setfil(i));
610: }
611: if (!checkclose(os))
612: wterror("merging");
613: }
614:
615: wline(s)
616: register char *s;
617: {
618: register FILE *iop;
619:
620: iop = os;
621: do
622: putc(*s, iop);
623: while (*s++ != '\n');
624: }
625:
626: cline(tp, fp)
627: register char *tp, *fp;
628: {
629: while ((*tp++ = *fp++) != '\n');
630: }
631:
632: rline(iop, s)
633: FILE *iop;
634: register char *s;
635: {
636: register char *ce;
637: register int c;
638: register FILE *riop;
639:
640: riop = iop;
641: ce = s + maxrec;
642: do {
643: c = getc(riop);
644: if (c == EOF)
645: return(1);
646: if (s >= ce)
647: --s;
648: *s++ = c;
649: } while (c != '\n');
650: return(0);
651: }
652:
653:
654: checksort()
655: {
656: char *f;
657: char *s[2];
658: register int i, j, r;
659:
660: f = setfil(0);
661: if (f == 0)
662: is = stdin;
663: else if ((is = fopen(f, "r")) == NULL)
664: cant(f);
665: (void) setbuf(is, bufin);
666:
667: i = 0; j = 1;
668: s[0] = (char *) lspace;
669: s[1] = s[0] + maxrec;
670: if ( rline(is, s[0]) ) {
671: if (!checkclose(is))
672: rderror(f);
673: exit(0);
674: }
675: while ( !rline(is, s[j]) ) {
676: r = (*compare)(s[i], s[j]);
677: if (r < 0)
678: disorder("disorder: ", s[j]);
679: if (r == 0 && uflg)
680: disorder("non-unique: ", s[j]);
681: r = i; i = j; j = r;
682: }
683: if (!checkclose(is))
684: rderror(f);
685: exit(0);
686: }
687:
688:
689: disorder(s,t)
690: char *s, *t;
691: {
692: register char *u;
693: for(u=t; *u!='\n';u++) ;
694: *u = 0;
695: diag(s,t);
696: term();
697: }
698:
699: newfile()
700: {
701: register char *f;
702:
703: f = setfil(nfiles);
704: if((os=fopen(f, "w")) == NULL) {
705: diag("can't create ",f);
706: term();
707: }
708: nfiles++;
709: }
710:
711: char *
712: setfil(i)
713: {
714:
715: if(i < eargc)
716: if(eargv[i][0] == '-' && eargv[i][1] == '\0')
717: return(0);
718: else
719: return(eargv[i]);
720: i -= eargc;
721: filep[0] = i/26 + 'a';
722: filep[1] = i%26 + 'a';
723: return(file);
724: }
725:
726: oldfile()
727: {
728:
729: if(outfil) {
730: if((os=fopen(outfil, "w")) == NULL) {
731: diag("can't create ",outfil);
732: term();
733: }
734: } else
735: os = stdout;
736: }
737:
738: safeoutfil()
739: {
740: register int i;
741: struct stat ostat,istat;
742:
743: if(!mflg||outfil==0)
744: return;
745: if(stat(outfil,&ostat)==-1)
746: return;
747: if ((i = eargc - N) < 0) i = 0; /*-N is suff., not nec. */
748: for (; i < eargc; i++) {
749: if(stat(eargv[i],&istat)==-1)
750: continue;
751: if(ostat.st_dev==istat.st_dev&&
752: ostat.st_ino==istat.st_ino)
753: unsafeout++;
754: }
755: }
756:
757: cant(f)
758: char *f;
759: {
760:
761: diag("can't open ",f);
762: term();
763: }
764:
765: diag(s,t)
766: char *s, *t;
767: {
768: (void) fputs("sort: ",stderr);
769: (void) fputs(s,stderr);
770: (void) fputs(t,stderr);
771: (void) fputs("\n",stderr);
772: }
773:
774: term()
775: {
776: register i;
777:
778: (void) signal(SIGINT, SIG_IGN);
779: (void) signal(SIGHUP, SIG_IGN);
780: (void) signal(SIGTERM, SIG_IGN);
781: if(nfiles == eargc)
782: nfiles++;
783: for(i=eargc; i<=nfiles; i++) { /*<= in case of interrupt*/
784: (void) unlink(setfil(i)); /*with nfiles not updated*/
785: }
786: exit(error);
787: }
788:
789: cmp(i, j)
790: char *i, *j;
791: {
792: register char *pa, *pb;
793: char *skip();
794: char *code, *ignore;
795: int a, b;
796: int k;
797: char *la, *lb;
798: register int sa;
799: int sb;
800: char *ipa, *ipb, *jpa, *jpb;
801: struct field *fp;
802: double za, zb;
803:
804: for(k = nfields>0; k<=nfields; k++) {
805: fp = &fields[k];
806: pa = i;
807: pb = j;
808: if(k) {
809: la = skip(pa, fp, 1);
810: pa = skip(pa, fp, 0);
811: lb = skip(pb, fp, 1);
812: pb = skip(pb, fp, 0);
813: } else {
814: la = eol(pa);
815: lb = eol(pb);
816: }
817: switch(fp->fcmp) {
818: case NUM:
819: sa = sb = fp->rflg;
820: while(blank(*pa))
821: pa++;
822: while(blank(*pb))
823: pb++;
824: if(*pa == '-') {
825: pa++;
826: sa = -sa;
827: }
828: if(*pb == '-') {
829: pb++;
830: sb = -sb;
831: }
832: for(ipa = pa; ipa<la&&isdigit(*ipa); ipa++) ;
833: for(ipb = pb; ipb<lb&&isdigit(*ipb); ipb++) ;
834: jpa = ipa;
835: jpb = ipb;
836: a = 0;
837: if(sa==sb)
838: while(ipa > pa && ipb > pb)
839: if(b = *--ipb - *--ipa)
840: a = b;
841: while(ipa > pa)
842: if(*--ipa != '0')
843: return(-sa);
844: while(ipb > pb)
845: if(*--ipb != '0')
846: return(sb);
847: if(a) return(a*sa);
848: if(*(pa=jpa) == '.')
849: pa++;
850: if(*(pb=jpb) == '.')
851: pb++;
852: if(sa==sb)
853: while(pa<la && isdigit(*pa)
854: && pb<lb && isdigit(*pb))
855: if(a = *pb++ - *pa++)
856: return(a*sa);
857: while(pa<la && isdigit(*pa))
858: if(*pa++ != '0')
859: return(-sa);
860: while(pb<lb && isdigit(*pb))
861: if(*pb++ != '0')
862: return(sb);
863: continue;
864: case MON:
865: sa = fp->rflg*(month(pb)-month(pa));
866: if(sa)
867: return(sa);
868: else
869: continue;
870: case FLOAT:
871: zb = atof(pb);
872: za = atof(pa);
873: if(zb > za)
874: return fp->rflg;
875: else if(zb < za)
876: return -fp->rflg;
877: else continue;
878: }
879: code = fp->code;
880: ignore = fp->ignore;
881: loop:
882: while(ignore[*pa])
883: pa++;
884: while(ignore[*pb])
885: pb++;
886: if(pa>=la || *pa=='\n')
887: if(pb<lb && *pb!='\n')
888: return(fp->rflg);
889: else continue;
890: if(pb>=lb || *pb=='\n')
891: return(-fp->rflg);
892: if((sa = code[*pb++]-code[*pa++]) == 0)
893: goto loop;
894: return(sa*fp->rflg);
895: }
896: if(uflg)
897: return(0);
898: return(cmpa(i, j));
899: }
900:
901: cmpa(pa, pb)
902: register char *pa, *pb;
903: {
904: while(*pa == *pb++)
905: if(*pa++ == '\n')
906: return(0);
907: return(
908: *pa == '\n' ? fields[0].rflg:
909: *--pb == '\n' ?-fields[0].rflg:
910: *pb > *pa ? fields[0].rflg:
911: -fields[0].rflg
912: );
913: }
914:
915: char *
916: skip(p, fp, j)
917: struct field *fp;
918: register char *p;
919: {
920: register i;
921: register char tbc;
922:
923: if( (i=fp->m[j]) < 0)
924: return(eol(p));
925: if (tbc = tabchar)
926: while (--i >= 0) {
927: while(*p != tbc)
928: if(*p != '\n')
929: p++;
930: else goto ret;
931: p++;
932: }
933: else while (--i >= 0) {
934: while(blank(*p))
935: p++;
936: while(!blank(*p))
937: if(*p != '\n')
938: p++;
939: else goto ret;
940: }
941: if(fp->bflg[j])
942: while(blank(*p))
943: p++;
944: i = fp->n[j];
945: if(i==0 && j!=0 && fp->m[j]>0 && p[-1]==tbc)
946: p--;
947: while((i-- > 0) && (*p != '\n'))
948: p++;
949: ret:
950: return(p);
951: }
952:
953: char *
954: eol(p)
955: register char *p;
956: {
957: while(*p != '\n') p++;
958: return(p);
959: }
960:
961: copyproto()
962: {
963: register i;
964: register int *p, *q;
965:
966: p = (int *)&proto;
967: q = (int *)&fields[nfields];
968: for(i=0; i<sizeof(proto)/sizeof(*p); i++)
969: *q++ = *p++;
970: }
971:
972: initree()
973: {
974: register struct btree **tpp, *tp;
975: register int i;
976:
977: for (tp = &(tree[0]), tpp = &(treep[0]), i = TREEZ; --i >= 0;)
978: *tpp++ = tp++;
979: }
980:
981: cmpsave(n)
982: register int n;
983: {
984: register int award;
985:
986: if (n < 2) return (0);
987: for (n++, award = 0; (n >>= 1) > 0; award++);
988: return (award);
989: }
990:
991:
992: field(s,k)
993: char *s;
994: {
995: register struct field *p;
996: register d;
997: p = &fields[nfields];
998: d = 0;
999: for(; *s!=0; s++) {
1000: switch(*s) {
1001: case '\0':
1002: return;
1003:
1004: case 'b':
1005: p->bflg[k]++;
1006: break;
1007:
1008: case 'd':
1009: p->ignore = dict+128;
1010: break;
1011:
1012: case 'f':
1013: p->code = fold+128;
1014: break;
1015: case 'i':
1016: p->ignore = nonprint+128;
1017: break;
1018:
1019: case 'c':
1020: cflg = 1;
1021: continue;
1022:
1023: case 'm':
1024: mflg = 1;
1025: continue;
1026:
1027: case 'M':
1028: p->fcmp = MON;
1029: break;
1030:
1031: case 'n':
1032: p->fcmp = NUM;
1033: break;
1034: case 'g':
1035: p->fcmp = FLOAT;
1036: break;
1037: case 't':
1038: tabchar = *++s;
1039: if(tabchar == 0) s--;
1040: continue;
1041:
1042: case 'r':
1043: p->rflg = -1;
1044: continue;
1045: case 'u':
1046: uflg = 1;
1047: continue;
1048:
1049: case 'y':
1050: if ( *++s ) tryfor = number(&s);
1051: else {
1052: --s;
1053: tryfor = MAXMEM;
1054: }
1055: continue;
1056:
1057: case 'z':
1058: if ( *++s )
1059: maxrec = number(&s);
1060: else --s;
1061: continue;
1062:
1063: case '.':
1064: if(p->m[k] == -1) /* -m.n with m missing */
1065: p->m[k] = 0;
1066: d = &fields[0].n[0]-&fields[0].m[0];
1067: if (*++s == '\0') {
1068: --s;
1069: p->m[k+d] = 0;
1070: continue;
1071: }
1072:
1073: default:
1074: p->m[k+d] = number(&s);
1075: }
1076: compare = cmp;
1077: }
1078: }
1079:
1080: number(ppa)
1081: char **ppa;
1082: {
1083: int n;
1084: register char *pa;
1085: pa = *ppa;
1086: n = 0;
1087: while(isdigit(*pa)) {
1088: n = n*10 + *pa - '0';
1089: *ppa = pa++;
1090: }
1091: return(n);
1092: }
1093:
1094: #define qsexc(p,q) t= *p;*p= *q;*q=t
1095: #define qstexc(p,q,r) t= *p;*p= *r;*r= *q;*q=t
1096:
1097: qsort(a,l)
1098: char **a, **l;
1099: {
1100: register char **i, **j;
1101: register char **lp, **hp;
1102: char **k;
1103: int c, d;
1104: char *t;
1105: unsigned n;
1106:
1107:
1108: start:
1109: if((n=l-a) <= 1)
1110: return;
1111:
1112: i = a;
1113: j = l - 1;
1114: if (n == 2) {
1115: if (c = (*compare)(*i, *j)) {
1116: if (c > 0) {
1117: qsexc(i, j);
1118: }
1119: } else if (uflg) **i = '\0';
1120: return;
1121: }
1122: n /= 2;
1123: lp = hp = a + n;
1124: c = (*compare)(*i, *lp);
1125: d = (*compare)(*lp, *j);
1126: if (c == 0) {
1127: if (d == 0) { /* x x x */
1128: --lp; qsexc(i, lp);
1129: hp++; qsexc(hp, j);
1130: } else if (d > 0) { /* x x w */
1131: qsexc(i, j);
1132: i++;
1133: hp++; qsexc(hp, j);
1134: } else { /* x x y */
1135: --j;
1136: --lp; qsexc(i, lp);
1137: }
1138: } else if (d == 0) {
1139: if (c < 0) { /* w x x */
1140: i++;
1141: hp++; qsexc(hp, j);
1142: } else { /* y x x */
1143: qsexc(i, j);
1144: --j;
1145: --lp; qsexc(i, lp);
1146: }
1147: } else if (c > 0) {
1148: if (d > 0) { /* z y x */
1149: qsexc(i, j);
1150: i++; --j;
1151: } else { /* z y z' */
1152: qsexc(i, lp);
1153: i++;
1154: if (c = (*compare)(*lp, *j)) {
1155: if (c > 0) {
1156: qsexc(lp, j);
1157: }
1158: --j;
1159: } else {
1160: hp++; qsexc(hp, j);
1161: }
1162: }
1163: } else {
1164: if (d > 0) { /* y z y' */
1165: qsexc(lp, j);
1166: --j;
1167: if (c = (*compare)(*i, *lp)) {
1168: if (c > 0) {
1169: qsexc(i, lp);
1170: }
1171: i++;
1172: } else {
1173: --lp;
1174: qsexc(i, lp);
1175: }
1176: } else { /* x y z */
1177: i++; --j;
1178: }
1179: }
1180:
1181:
1182: for(;;) {
1183: if(i < lp) {
1184: if((c = (*compare)(*i, *lp)) == 0) {
1185: --lp;
1186: qsexc(i, lp);
1187: continue;
1188: }
1189: if(c < 0) {
1190: ++i;
1191: continue;
1192: }
1193: }
1194:
1195: loop:
1196: if(j > hp) {
1197: if((c = (*compare)(*hp, *j)) == 0) {
1198: ++hp;
1199: qsexc(hp, j);
1200: goto loop;
1201: }
1202: if(c > 0) {
1203: if(i == lp) {
1204: ++hp;
1205: qstexc(i, hp, j);
1206: i = ++lp;
1207: goto loop;
1208: }
1209: qsexc(i, j);
1210: --j;
1211: ++i;
1212: continue;
1213: }
1214: --j;
1215: goto loop;
1216: }
1217:
1218:
1219: if(i == lp) {
1220: if(uflg)
1221: for(k=lp; k<hp;) **k++ = '\0';
1222: if(lp-a >= l-hp) {
1223: qsort(hp+1, l);
1224: l = lp;
1225: } else {
1226: qsort(a, lp);
1227: a = hp+1;
1228: }
1229: goto start;
1230: }
1231:
1232:
1233: --lp;
1234: qstexc(j, lp, i);
1235: j = --hp;
1236: }
1237: }
1238:
1239: char * months[] = {
1240: "jan",
1241: "feb",
1242: "mar",
1243: "apr",
1244: "may",
1245: "jun",
1246: "jul",
1247: "aug",
1248: "sep",
1249: "oct",
1250: "nov",
1251: "dec"
1252: };
1253: month(s)
1254: char *s;
1255: {
1256: register char *t, *u;
1257: register i;
1258: char *f = fold + 128;
1259:
1260: while(blank(*s))
1261: s++;
1262: for(i=0; i<sizeof(months)/sizeof(*months); i++) {
1263: for(t=s,u=months[i]; f[*t++]==f[*u++]; )
1264: if(*u==0)
1265: return(i);
1266: }
1267: return(-1);
1268: }
1269:
1270:
1271: rderror(s)
1272: char *s;
1273: {
1274: diag("read error on ", s == 0 ? "stdin" : s);
1275: term();
1276: }
1277:
1278: wterror(s)
1279: char *s;
1280: {
1281: diag("write error while ", s);
1282: term();
1283: }
1284:
1285: checkclose(f)
1286: FILE *f;
1287: {
1288: return !ferror(f) && fclose(f)==0;
1289: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.