xref: /original-bsd/usr.bin/sort/sort.c (revision 1e042fd4)
1 /*-
2  * Copyright (c) 1986, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * %sccs.include.proprietary.c%
6  */
7 
8 #ifndef lint
9 static char copyright[] =
10 "@(#) Copyright (c) 1986, 1993\n\
11 	The Regents of the University of California.  All rights reserved.\n";
12 #endif /* not lint */
13 
14 #ifndef lint
15 static char sccsid[] = "@(#)sort.c	8.1 (Berkeley) 06/10/93";
16 #endif /* not lint */
17 
18 #include <sys/param.h>
19 #include <sys/file.h>
20 #include <stdio.h>
21 #include <ctype.h>
22 #include <signal.h>
23 #include <sys/stat.h>
24 #include "pathnames.h"
25 
26 #define	L	4096
27 #define	N	7
28 #define	C	20
29 #ifndef pdp11
30 #define	MEM	(128*2048)
31 #else
32 #define	MEM	(16*2048)
33 #endif
34 #define NF	10
35 
36 #define rline(mp)	(fgets((mp)->l, L, (mp)->b) == NULL)
37 
38 FILE	*is, *os;
39 char	*dirtry[] = {_PATH_TMP1, _PATH_TMP2, NULL};
40 char	**dirs;
41 char	file1[MAXPATHLEN];
42 char	*file = file1;
43 char	*filep;
44 int	nfiles;
45 unsigned	nlines;
46 unsigned	ntext;
47 int	*lspace;
48 char	*tspace;
49 int	cmp(), cmpa();
50 int	(*compare)() = cmpa;
51 char	*eol();
52 void	term();
53 int 	mflg;
54 int	cflg;
55 int	uflg;
56 char	*outfil;
57 int unsafeout;	/*kludge to assure -m -o works*/
58 char	tabchar;
59 int 	eargc;
60 char	**eargv;
61 
62 char zero[256];
63 
64 char	fold[256] = {
65 	0200,0201,0202,0203,0204,0205,0206,0207,
66 	0210,0211,0212,0213,0214,0215,0216,0217,
67 	0220,0221,0222,0223,0224,0225,0226,0227,
68 	0230,0231,0232,0233,0234,0235,0236,0237,
69 	0240,0241,0242,0243,0244,0245,0246,0247,
70 	0250,0251,0252,0253,0254,0255,0256,0257,
71 	0260,0261,0262,0263,0264,0265,0266,0267,
72 	0270,0271,0272,0273,0274,0275,0276,0277,
73 	0300,0301,0302,0303,0304,0305,0306,0307,
74 	0310,0311,0312,0313,0314,0315,0316,0317,
75 	0320,0321,0322,0323,0324,0325,0326,0327,
76 	0330,0331,0332,0333,0334,0335,0336,0337,
77 	0340,0341,0342,0343,0344,0345,0346,0347,
78 	0350,0351,0352,0353,0354,0355,0356,0357,
79 	0360,0361,0362,0363,0364,0365,0366,0367,
80 	0370,0371,0372,0373,0374,0375,0376,0377,
81 	0000,0001,0002,0003,0004,0005,0006,0007,
82 	0010,0011,0012,0013,0014,0015,0016,0017,
83 	0020,0021,0022,0023,0024,0025,0026,0027,
84 	0030,0031,0032,0033,0034,0035,0036,0037,
85 	0040,0041,0042,0043,0044,0045,0046,0047,
86 	0050,0051,0052,0053,0054,0055,0056,0057,
87 	0060,0061,0062,0063,0064,0065,0066,0067,
88 	0070,0071,0072,0073,0074,0075,0076,0077,
89 	0100,0101,0102,0103,0104,0105,0106,0107,
90 	0110,0111,0112,0113,0114,0115,0116,0117,
91 	0120,0121,0122,0123,0124,0125,0126,0127,
92 	0130,0131,0132,0133,0134,0135,0136,0137,
93 	0140,0101,0102,0103,0104,0105,0106,0107,
94 	0110,0111,0112,0113,0114,0115,0116,0117,
95 	0120,0121,0122,0123,0124,0125,0126,0127,
96 	0130,0131,0132,0173,0174,0175,0176,0177
97 };
98 char nofold[256] = {
99 	0200,0201,0202,0203,0204,0205,0206,0207,
100 	0210,0211,0212,0213,0214,0215,0216,0217,
101 	0220,0221,0222,0223,0224,0225,0226,0227,
102 	0230,0231,0232,0233,0234,0235,0236,0237,
103 	0240,0241,0242,0243,0244,0245,0246,0247,
104 	0250,0251,0252,0253,0254,0255,0256,0257,
105 	0260,0261,0262,0263,0264,0265,0266,0267,
106 	0270,0271,0272,0273,0274,0275,0276,0277,
107 	0300,0301,0302,0303,0304,0305,0306,0307,
108 	0310,0311,0312,0313,0314,0315,0316,0317,
109 	0320,0321,0322,0323,0324,0325,0326,0327,
110 	0330,0331,0332,0333,0334,0335,0336,0337,
111 	0340,0341,0342,0343,0344,0345,0346,0347,
112 	0350,0351,0352,0353,0354,0355,0356,0357,
113 	0360,0361,0362,0363,0364,0365,0366,0367,
114 	0370,0371,0372,0373,0374,0375,0376,0377,
115 	0000,0001,0002,0003,0004,0005,0006,0007,
116 	0010,0011,0012,0013,0014,0015,0016,0017,
117 	0020,0021,0022,0023,0024,0025,0026,0027,
118 	0030,0031,0032,0033,0034,0035,0036,0037,
119 	0040,0041,0042,0043,0044,0045,0046,0047,
120 	0050,0051,0052,0053,0054,0055,0056,0057,
121 	0060,0061,0062,0063,0064,0065,0066,0067,
122 	0070,0071,0072,0073,0074,0075,0076,0077,
123 	0100,0101,0102,0103,0104,0105,0106,0107,
124 	0110,0111,0112,0113,0114,0115,0116,0117,
125 	0120,0121,0122,0123,0124,0125,0126,0127,
126 	0130,0131,0132,0133,0134,0135,0136,0137,
127 	0140,0141,0142,0143,0144,0145,0146,0147,
128 	0150,0151,0152,0153,0154,0155,0156,0157,
129 	0160,0161,0162,0163,0164,0165,0166,0167,
130 	0170,0171,0172,0173,0174,0175,0176,0177
131 };
132 
133 char	nonprint[256] = {
134 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
135 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
136 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
137 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
138 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
139 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
140 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
141 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
142 	1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
143 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
144 	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
145 	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
146 	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
147 	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
148 	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
149 	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
150 };
151 
152 char	dict[256] = {
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,1,1,1,1,1,1,1,
159 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
160 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
161 	1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
162 	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
163 	0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
164 	0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
165 	1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
166 	0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,
167 	1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
168 	0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1
169 };
170 
171 struct	field {
172 	char *code;
173 	char *ignore;
174 	int nflg;
175 	int rflg;
176 	int bflg[2];
177 	int m[2];
178 	int n[2];
179 }	fields[NF];
180 struct field proto = {
181 	nofold+128,
182 	zero+128,
183 	0,
184 	1,
185 	0,0,
186 	0,-1,
187 	0,0
188 };
189 int	nfields;
190 int 	error = 1;
191 char	*setfil();
192 char	*sbrk();
193 char	*brk();
194 
195 #define	blank(c)	((c) == ' ' || (c) == '\t')
196 
main(argc,argv)197 main(argc, argv)
198 char **argv;
199 {
200 	register a;
201 	extern char end[1];
202 	char *ep;
203 	char *arg;
204 	struct field *p, *q;
205 	int i;
206 
207 	copyproto();
208 	eargv = argv;
209 	while (--argc > 0) {
210 		if(**++argv == '-') for(arg = *argv;;) {
211 			switch(*++arg) {
212 			case '\0':
213 				if(arg[-1] == '-')
214 					eargv[eargc++] = "-";
215 				break;
216 
217 			case 'o':
218 				if(--argc > 0)
219 					outfil = *++argv;
220 				continue;
221 
222 			case 'T':
223 				if (--argc > 0)
224 					dirtry[0] = *++argv;
225 				continue;
226 
227 			default:
228 				field(++*argv,nfields>0);
229 				break;
230 			}
231 			break;
232 		} else if (**argv == '+') {
233 			if(++nfields>=NF) {
234 				diag("too many keys","");
235 				exit(1);
236 			}
237 			copyproto();
238 			field(++*argv,0);
239 		} else
240 			eargv[eargc++] = *argv;
241 	}
242 	q = &fields[0];
243 	for(a=1; a<=nfields; a++) {
244 		p = &fields[a];
245 		if(p->code != proto.code) continue;
246 		if(p->ignore != proto.ignore) continue;
247 		if(p->nflg != proto.nflg) continue;
248 		if(p->rflg != proto.rflg) continue;
249 		if(p->bflg[0] != proto.bflg[0]) continue;
250 		if(p->bflg[1] != proto.bflg[1]) continue;
251 		p->code = q->code;
252 		p->ignore = q->ignore;
253 		p->nflg = q->nflg;
254 		p->rflg = q->rflg;
255 		p->bflg[0] = p->bflg[1] = q->bflg[0];
256 	}
257 	if(eargc == 0)
258 		eargv[eargc++] = "-";
259 	if(cflg && eargc>1) {
260 		diag("can check only 1 file","");
261 		exit(1);
262 	}
263 	safeoutfil();
264 
265 	ep = end + MEM;
266 	lspace = (int *)sbrk(0);
267 	while((int)brk(ep) == -1)
268 		ep -= 512;
269 #ifndef	vax
270 	brk(ep -= 512);	/* for recursion */
271 #endif
272 	a = ep - (char*)lspace;
273 	nlines = (a-L);
274 	nlines /= (5*(sizeof(char *)/sizeof(char)));
275 	ntext = nlines * 4 * (sizeof(char *)/sizeof(char));
276 	tspace = (char *)(lspace + nlines);
277 	a = -1;
278 	for(dirs=dirtry; *dirs; dirs++) {
279 		sprintf(filep=file1, "%s/stm%05uaa", *dirs, getpid());
280 		while (*filep)
281 			filep++;
282 		filep -= 2;
283 		if ( (a=creat(file, 0600)) >=0)
284 			break;
285 	}
286 	if(a < 0) {
287 		diag("can't locate temp","");
288 		exit(1);
289 	}
290 	close(a);
291 	unlink(file);
292 	if (signal(SIGHUP, SIG_IGN) != SIG_IGN)
293 		signal(SIGHUP, term);
294 	if (signal(SIGINT, SIG_IGN) != SIG_IGN)
295 		signal(SIGINT, term);
296 	signal(SIGPIPE,term);
297 	if (signal(SIGTERM, SIG_IGN) != SIG_IGN)
298 		signal(SIGTERM,term);
299 	nfiles = eargc;
300 	if(!mflg && !cflg) {
301 		sort();
302 		fclose(stdin);
303 	}
304 	for(a = mflg|cflg?0:eargc; a+N<nfiles || unsafeout&&a<eargc; a=i) {
305 		i = a+N;
306 		if(i>=nfiles)
307 			i = nfiles;
308 		newfile();
309 		merge(a, i);
310 	}
311 	if(a != nfiles) {
312 		oldfile();
313 		merge(a, nfiles);
314 	}
315 	error = 0;
316 	term();
317 }
318 
sort()319 sort()
320 {
321 	register char *cp;
322 	register char **lp;
323 	register lines, text, len;
324 	int done = 0;
325 	int i = 0;
326 	char *f;
327 	char c;
328 
329 	if((f = setfil(i++)) == NULL)
330 		is = stdin;
331 	else if((is = fopen(f, "r")) == NULL)
332 		cant(f);
333 
334 	do {
335 		cp = tspace;
336 		lp = (char **)lspace;
337 		lines = nlines;
338 		text = ntext;
339 		while(lines > 0 && text > 0) {
340 			if(fgets(cp, L, is) == NULL) {
341 				if(i >= eargc) {
342 					++done;
343 					break;
344 				}
345 				fclose(is);
346 				if((f = setfil(i++)) == NULL)
347 					is = stdin;
348 				else if((is = fopen(f, "r")) == NULL)
349 					cant(f);
350 				continue;
351 			}
352 			*lp++ = cp;
353 			len = strlen(cp) + 1; /* null terminate */
354 			if(cp[len - 2] != '\n')
355 				if (len == L) {
356 					diag("line too long (skipped): ", cp);
357 					while((c=getc(is)) != EOF && c != '\n')
358 						/* throw it away */;
359 					--lp;
360 					continue;
361 				} else {
362 					diag("missing newline before EOF in ",
363 						f ? f : "standard input");
364 					/* be friendly, append a newline */
365 					++len;
366 					cp[len - 2] = '\n';
367 					cp[len - 1] = '\0';
368 				}
369 			cp += len;
370 			--lines;
371 			text -= len;
372 		}
373 		qsort((char **)lspace, lp);
374 		if(done == 0 || nfiles != eargc)
375 			newfile();
376 		else
377 			oldfile();
378 		clearerr(os);
379 		while(lp > (char **)lspace) {
380 			cp = *--lp;
381 			if(*cp)
382 				fputs(cp, os);
383 			if (ferror(os)) {
384 				error = 1;
385 				term();
386 			}
387 		}
388 		fclose(os);
389 	} while(done == 0);
390 }
391 
392 struct merg
393 {
394 	char	l[L];
395 	FILE	*b;
396 } *ibuf[256];
397 
merge(a,b)398 merge(a,b)
399 {
400 	struct	merg	*p;
401 	register char	*cp, *dp;
402 	register	i;
403 	struct merg **ip, *jp;
404 	char	*f;
405 	int	j;
406 	int	k, l;
407 	int	muflg;
408 
409 	p = (struct merg *)lspace;
410 	j = 0;
411 	for(i=a; i < b; i++) {
412 		f = setfil(i);
413 		if(f == 0)
414 			p->b = stdin;
415 		else if((p->b = fopen(f, "r")) == NULL)
416 			cant(f);
417 		ibuf[j] = p;
418 		if(!rline(p))	j++;
419 		p++;
420 	}
421 
422 	do {
423 		i = j;
424 		qsort((char **)ibuf, (char **)(ibuf+i));
425 		l = 0;
426 		while(i--) {
427 			cp = ibuf[i]->l;
428 			if(*cp == '\0') {
429 				l = 1;
430 				if(rline(ibuf[i])) {
431 					k = i;
432 					while(++k < j)
433 						ibuf[k-1] = ibuf[k];
434 					j--;
435 				}
436 			}
437 		}
438 	} while(l);
439 
440 	clearerr(os);
441 	muflg = mflg & uflg | cflg;
442 	i = j;
443 	while(i > 0) {
444 		cp = ibuf[i-1]->l;
445 		if (!cflg && (uflg == 0 || muflg || i == 1 ||
446 			(*compare)(ibuf[i-1]->l,ibuf[i-2]->l))) {
447 			fputs(cp, os);
448 			if (ferror(os)) {
449 				error = 1;
450 				term();
451 			}
452 		}
453 		if(muflg){
454 			cp = ibuf[i-1]->l;
455 			dp = p->l;
456 			do {
457 			} while((*dp++ = *cp++) != '\n');
458 		}
459 		for(;;) {
460 			if(rline(ibuf[i-1])) {
461 				i--;
462 				if(i == 0)
463 					break;
464 				if(i == 1)
465 					muflg = uflg;
466 			}
467 			ip = &ibuf[i];
468 			while(--ip>ibuf&&(*compare)(ip[0]->l,ip[-1]->l)<0){
469 				jp = *ip;
470 				*ip = *(ip-1);
471 				*(ip-1) = jp;
472 			}
473 			if(!muflg)
474 				break;
475 			j = (*compare)(ibuf[i-1]->l,p->l);
476 			if(cflg) {
477 				if(j > 0)
478 					disorder("disorder:",ibuf[i-1]->l);
479 				else if(uflg && j==0)
480 					disorder("nonunique:",ibuf[i-1]->l);
481 			} else if(j == 0)
482 				continue;
483 			break;
484 		}
485 	}
486 	p = (struct merg *)lspace;
487 	for(i=a; i<b; i++) {
488 		fclose(p->b);
489 		p++;
490 		if(i >= eargc)
491 			unlink(setfil(i));
492 	}
493 	fclose(os);
494 }
495 
disorder(s,t)496 disorder(s,t)
497 char *s, *t;
498 {
499 	register char *u;
500 	for(u=t; *u!='\n';u++) ;
501 	*u = 0;
502 	diag(s,t);
503 	term();
504 }
505 
newfile()506 newfile()
507 {
508 	int fd;
509 	char *f;
510 
511 	f = setfil(nfiles);
512 	if ((fd = open(f, O_WRONLY|O_CREAT, 0600)) < 0 ||
513 	    !(os = fdopen(fd, "w"))) {
514 		diag("can't create ", f);
515 		term();
516 	}
517 	++nfiles;
518 }
519 
520 char *
setfil(i)521 setfil(i)
522 {
523 
524 	if(i < eargc)
525 		if(eargv[i][0] == '-' && eargv[i][1] == '\0')
526 			return(0);
527 		else
528 			return(eargv[i]);
529 	i -= eargc;
530 	filep[0] = i/26 + 'a';
531 	filep[1] = i%26 + 'a';
532 	return(file);
533 }
534 
oldfile()535 oldfile()
536 {
537 
538 	if(outfil) {
539 		if((os=fopen(outfil, "w")) == NULL) {
540 			diag("can't create ",outfil);
541 			term();
542 		}
543 	} else
544 		os = stdout;
545 }
546 
safeoutfil()547 safeoutfil()
548 {
549 	register int i;
550 	struct stat obuf,ibuf;
551 
552 	if(!mflg||outfil==0)
553 		return;
554 	if(stat(outfil,&obuf)==-1)
555 		return;
556 	for(i=eargc-N;i<eargc;i++) {	/*-N is suff., not nec.*/
557 		if(stat(eargv[i],&ibuf)==-1)
558 			continue;
559 		if(obuf.st_dev==ibuf.st_dev&&
560 		   obuf.st_ino==ibuf.st_ino)
561 			unsafeout++;
562 	}
563 }
564 
cant(f)565 cant(f)
566 char *f;
567 {
568 
569 	perror(f);
570 	term();
571 }
572 
diag(s,t)573 diag(s,t)
574 char *s, *t;
575 {
576 	fputs("sort: ",stderr);
577 	fputs(s,stderr);
578 	fputs(t,stderr);
579 	fputs("\n",stderr);
580 }
581 
582 void
term()583 term()
584 {
585 	register i;
586 
587 	signal(SIGINT, SIG_IGN);
588 	signal(SIGHUP, SIG_IGN);
589 	signal(SIGTERM, SIG_IGN);
590 	if(nfiles == eargc)
591 		nfiles++;
592 	for(i=eargc; i<=nfiles; i++) {	/*<= in case of interrupt*/
593 		unlink(setfil(i));	/*with nfiles not updated*/
594 	}
595 	_exit(error);
596 }
597 
cmp(i,j)598 cmp(i, j)
599 char *i, *j;
600 {
601 	register char *pa, *pb;
602 	char *skip();
603 	char *code, *ignore;
604 	int a, b;
605 	int k;
606 	char *la, *lb;
607 	register int sa;
608 	int sb;
609 	char *ipa, *ipb, *jpa, *jpb;
610 	struct field *fp;
611 
612 	for(k = nfields>0; k<=nfields; k++) {
613 		fp = &fields[k];
614 		pa = i;
615 		pb = j;
616 		if(k) {
617 			la = skip(pa, fp, 1);
618 			pa = skip(pa, fp, 0);
619 			lb = skip(pb, fp, 1);
620 			pb = skip(pb, fp, 0);
621 		} else {
622 			la = eol(pa);
623 			lb = eol(pb);
624 		}
625 		if(fp->nflg) {
626 			if(tabchar) {
627 				if(pa<la&&*pa==tabchar)
628 					pa++;
629 				if(pb<lb&&*pb==tabchar)
630 					pb++;
631 			}
632 			while(blank(*pa))
633 				pa++;
634 			while(blank(*pb))
635 				pb++;
636 			sa = sb = fp->rflg;
637 			if(*pa == '-') {
638 				pa++;
639 				sa = -sa;
640 			}
641 			if(*pb == '-') {
642 				pb++;
643 				sb = -sb;
644 			}
645 			for(ipa = pa; ipa<la&&isdigit(*ipa); ipa++) ;
646 			for(ipb = pb; ipb<lb&&isdigit(*ipb); ipb++) ;
647 			jpa = ipa;
648 			jpb = ipb;
649 			a = 0;
650 			if(sa==sb)
651 				while(ipa > pa && ipb > pb)
652 					if(b = *--ipb - *--ipa)
653 						a = b;
654 			while(ipa > pa)
655 				if(*--ipa != '0')
656 					return(-sa);
657 			while(ipb > pb)
658 				if(*--ipb != '0')
659 					return(sb);
660 			if(a) return(a*sa);
661 			if(*(pa=jpa) == '.')
662 				pa++;
663 			if(*(pb=jpb) == '.')
664 				pb++;
665 			if(sa==sb)
666 				while(pa<la && isdigit(*pa)
667 				   && pb<lb && isdigit(*pb))
668 					if(a = *pb++ - *pa++)
669 						return(a*sa);
670 			while(pa<la && isdigit(*pa))
671 				if(*pa++ != '0')
672 					return(-sa);
673 			while(pb<lb && isdigit(*pb))
674 				if(*pb++ != '0')
675 					return(sb);
676 			continue;
677 		}
678 		code = fp->code;
679 		ignore = fp->ignore;
680 loop:
681 		while(ignore[*pa])
682 			pa++;
683 		while(ignore[*pb])
684 			pb++;
685 		if(pa>=la || *pa=='\n')
686 			if(pb<lb && *pb!='\n')
687 				return(fp->rflg);
688 			else continue;
689 		if(pb>=lb || *pb=='\n')
690 			return(-fp->rflg);
691 		if((sa = code[*pb++]-code[*pa++]) == 0)
692 			goto loop;
693 		return(sa*fp->rflg);
694 	}
695 	if(uflg)
696 		return(0);
697 	return(cmpa(i, j));
698 }
699 
cmpa(pa,pb)700 cmpa(pa, pb)
701 register char *pa, *pb;
702 {
703 	while(*pa == *pb) {
704 		if(*pa++ == '\n')
705 			return(0);
706 		pb++;
707 	}
708 	return(
709 		*pa == '\n' ? fields[0].rflg:
710 		*pb == '\n' ?-fields[0].rflg:
711 		*pb > *pa   ? fields[0].rflg:
712 		-fields[0].rflg
713 	);
714 }
715 
716 char *
skip(pp,fp,j)717 skip(pp, fp, j)
718 struct field *fp;
719 char *pp;
720 {
721 	register i;
722 	register char *p;
723 
724 	p = pp;
725 	if( (i=fp->m[j]) < 0)
726 		return(eol(p));
727 	while(i-- > 0) {
728 		if(tabchar != 0) {
729 			while(*p != tabchar)
730 				if(*p != '\n')
731 					p++;
732 				else goto ret;
733 			if(i>0||j==0)
734 				p++;
735 		} else {
736 			while(blank(*p))
737 				p++;
738 			while(!blank(*p))
739 				if(*p != '\n')
740 					p++;
741 				else goto ret;
742 		}
743 	}
744 	if(tabchar==0||fp->bflg[j])
745 		while(blank(*p))
746 			p++;
747 	i = fp->n[j];
748 	while(i-- > 0) {
749 		if(*p != '\n')
750 			p++;
751 		else goto ret;
752 	}
753 ret:
754 	return(p);
755 }
756 
757 char *
eol(p)758 eol(p)
759 register char *p;
760 {
761 	while(*p != '\n') p++;
762 	return(p);
763 }
764 
copyproto()765 copyproto()
766 {
767 	register i;
768 	register int *p, *q;
769 
770 	p = (int *)&proto;
771 	q = (int *)&fields[nfields];
772 	for(i=0; i<sizeof(proto)/sizeof(*p); i++)
773 		*q++ = *p++;
774 }
775 
field(s,k)776 field(s,k)
777 char *s;
778 {
779 	register struct field *p;
780 	register d;
781 	p = &fields[nfields];
782 	d = 0;
783 	for(; *s!=0; s++) {
784 		switch(*s) {
785 		case '\0':
786 			return;
787 
788 		case 'b':
789 			p->bflg[k]++;
790 			break;
791 
792 		case 'd':
793 			p->ignore = dict+128;
794 			break;
795 
796 		case 'f':
797 			p->code = fold+128;
798 			break;
799 		case 'i':
800 			p->ignore = nonprint+128;
801 			break;
802 
803 		case 'c':
804 			cflg = 1;
805 			continue;
806 
807 		case 'm':
808 			mflg = 1;
809 			continue;
810 
811 		case 'n':
812 			p->nflg++;
813 			break;
814 		case 't':
815 			tabchar = *++s;
816 			if(tabchar == 0) s--;
817 			continue;
818 
819 		case 'r':
820 			p->rflg = -1;
821 			continue;
822 		case 'u':
823 			uflg = 1;
824 			break;
825 
826 		case '.':
827 			if(p->m[k] == -1)	/* -m.n with m missing */
828 				p->m[k] = 0;
829 			d = &fields[0].n[0]-&fields[0].m[0];
830 
831 		default:
832 			p->m[k+d] = number(&s);
833 		}
834 		compare = cmp;
835 	}
836 }
837 
number(ppa)838 number(ppa)
839 char **ppa;
840 {
841 	int n;
842 	register char *pa;
843 	pa = *ppa;
844 	n = 0;
845 	while(isdigit(*pa)) {
846 		n = n*10 + *pa - '0';
847 		*ppa = pa++;
848 	}
849 	return(n);
850 }
851 
852 #define qsexc(p,q) t= *p;*p= *q;*q=t
853 #define qstexc(p,q,r) t= *p;*p= *r;*r= *q;*q=t
854 
qsort(a,l)855 qsort(a,l)
856 char **a, **l;
857 {
858 	register char **i, **j;
859 	char **k;
860 	char **lp, **hp;
861 	int c;
862 	char *t;
863 	unsigned n;
864 
865 
866 
867 start:
868 	if((n=l-a) <= 1)
869 		return;
870 
871 
872 	n /= 2;
873 	hp = lp = a+n;
874 	i = a;
875 	j = l-1;
876 
877 
878 	for(;;) {
879 		if(i < lp) {
880 			if((c = (*compare)(*i, *lp)) == 0) {
881 				--lp;
882 				qsexc(i, lp);
883 				continue;
884 			}
885 			if(c < 0) {
886 				++i;
887 				continue;
888 			}
889 		}
890 
891 loop:
892 		if(j > hp) {
893 			if((c = (*compare)(*hp, *j)) == 0) {
894 				++hp;
895 				qsexc(hp, j);
896 				goto loop;
897 			}
898 			if(c > 0) {
899 				if(i == lp) {
900 					++hp;
901 					qstexc(i, hp, j);
902 					i = ++lp;
903 					goto loop;
904 				}
905 				qsexc(i, j);
906 				--j;
907 				++i;
908 				continue;
909 			}
910 			--j;
911 			goto loop;
912 		}
913 
914 
915 		if(i == lp) {
916 			if(uflg)
917 				for(k=lp+1; k<=hp;) **k++ = '\0';
918 			if(lp-a >= l-hp) {
919 				qsort(hp+1, l);
920 				l = lp;
921 			} else {
922 				qsort(a, lp);
923 				a = hp+1;
924 			}
925 			goto start;
926 		}
927 
928 
929 		--lp;
930 		qstexc(j, lp, i);
931 		j = --hp;
932 	}
933 }
934 
935