[unix-history] / usr / src / usr.bin / sort / sort.c

/*-
 * Copyright (c) 1986, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This module is believed to contain source code proprietary to AT&T.
 * Use and redistribution is subject to the Berkeley Software License
 * Agreement and your Software Agreement with AT&T (Western Electric).
 */

#ifndef lint
static char copyright[] =
"@(#) Copyright (c) 1986, 1993\n\
	The Regents of the University of California.  All rights reserved.\n";
#endif /* not lint */

#ifndef lint
static char sccsid[] = "@(#)sort.c	8.1 (Berkeley) 6/10/93";
#endif /* not lint */

#include <sys/param.h>
#include <sys/file.h>
#include <stdio.h>
#include <ctype.h>
#include <signal.h>
#include <sys/stat.h>
#include "pathnames.h"

#define	L	4096
#define	N	7
#define	C	20
#ifndef pdp11
#define	MEM	(128*2048)
#else
#define	MEM	(16*2048)
#endif
#define NF	10

#define rline(mp)	(fgets((mp)->l, L, (mp)->b) == NULL)

FILE	*is, *os;
char	*dirtry[] = {_PATH_TMP1, _PATH_TMP2, NULL};
char	**dirs;
char	file1[MAXPATHLEN];
char	*file = file1;
char	*filep;
int	nfiles;
unsigned	nlines;
unsigned	ntext;
int	*lspace;
char	*tspace;
int	cmp(), cmpa();
int	(*compare)() = cmpa;
char	*eol();
void	term();
int 	mflg;
int	cflg;
int	uflg;
char	*outfil;
int unsafeout;	/*kludge to assure -m -o works*/
char	tabchar;
int 	eargc;
char	**eargv;

char zero[256];

char	fold[256] = {
	0200,0201,0202,0203,0204,0205,0206,0207,
	0210,0211,0212,0213,0214,0215,0216,0217,
	0220,0221,0222,0223,0224,0225,0226,0227,
	0230,0231,0232,0233,0234,0235,0236,0237,
	0240,0241,0242,0243,0244,0245,0246,0247,
	0250,0251,0252,0253,0254,0255,0256,0257,
	0260,0261,0262,0263,0264,0265,0266,0267,
	0270,0271,0272,0273,0274,0275,0276,0277,
	0300,0301,0302,0303,0304,0305,0306,0307,
	0310,0311,0312,0313,0314,0315,0316,0317,
	0320,0321,0322,0323,0324,0325,0326,0327,
	0330,0331,0332,0333,0334,0335,0336,0337,
	0340,0341,0342,0343,0344,0345,0346,0347,
	0350,0351,0352,0353,0354,0355,0356,0357,
	0360,0361,0362,0363,0364,0365,0366,0367,
	0370,0371,0372,0373,0374,0375,0376,0377,
	0000,0001,0002,0003,0004,0005,0006,0007,
	0010,0011,0012,0013,0014,0015,0016,0017,
	0020,0021,0022,0023,0024,0025,0026,0027,
	0030,0031,0032,0033,0034,0035,0036,0037,
	0040,0041,0042,0043,0044,0045,0046,0047,
	0050,0051,0052,0053,0054,0055,0056,0057,
	0060,0061,0062,0063,0064,0065,0066,0067,
	0070,0071,0072,0073,0074,0075,0076,0077,
	0100,0101,0102,0103,0104,0105,0106,0107,
	0110,0111,0112,0113,0114,0115,0116,0117,
	0120,0121,0122,0123,0124,0125,0126,0127,
	0130,0131,0132,0133,0134,0135,0136,0137,
	0140,0101,0102,0103,0104,0105,0106,0107,
	0110,0111,0112,0113,0114,0115,0116,0117,
	0120,0121,0122,0123,0124,0125,0126,0127,
	0130,0131,0132,0173,0174,0175,0176,0177
};
char nofold[256] = {
	0200,0201,0202,0203,0204,0205,0206,0207,
	0210,0211,0212,0213,0214,0215,0216,0217,
	0220,0221,0222,0223,0224,0225,0226,0227,
	0230,0231,0232,0233,0234,0235,0236,0237,
	0240,0241,0242,0243,0244,0245,0246,0247,
	0250,0251,0252,0253,0254,0255,0256,0257,
	0260,0261,0262,0263,0264,0265,0266,0267,
	0270,0271,0272,0273,0274,0275,0276,0277,
	0300,0301,0302,0303,0304,0305,0306,0307,
	0310,0311,0312,0313,0314,0315,0316,0317,
	0320,0321,0322,0323,0324,0325,0326,0327,
	0330,0331,0332,0333,0334,0335,0336,0337,
	0340,0341,0342,0343,0344,0345,0346,0347,
	0350,0351,0352,0353,0354,0355,0356,0357,
	0360,0361,0362,0363,0364,0365,0366,0367,
	0370,0371,0372,0373,0374,0375,0376,0377,
	0000,0001,0002,0003,0004,0005,0006,0007,
	0010,0011,0012,0013,0014,0015,0016,0017,
	0020,0021,0022,0023,0024,0025,0026,0027,
	0030,0031,0032,0033,0034,0035,0036,0037,
	0040,0041,0042,0043,0044,0045,0046,0047,
	0050,0051,0052,0053,0054,0055,0056,0057,
	0060,0061,0062,0063,0064,0065,0066,0067,
	0070,0071,0072,0073,0074,0075,0076,0077,
	0100,0101,0102,0103,0104,0105,0106,0107,
	0110,0111,0112,0113,0114,0115,0116,0117,
	0120,0121,0122,0123,0124,0125,0126,0127,
	0130,0131,0132,0133,0134,0135,0136,0137,
	0140,0141,0142,0143,0144,0145,0146,0147,
	0150,0151,0152,0153,0154,0155,0156,0157,
	0160,0161,0162,0163,0164,0165,0166,0167,
	0170,0171,0172,0173,0174,0175,0176,0177
};

char	nonprint[256] = {
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
};

char	dict[256] = {
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
	1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,
	1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1
};

struct	field {
	char *code;
	char *ignore;
	int nflg;
	int rflg;
	int bflg[2];
	int m[2];
	int n[2];
}	fields[NF];
struct field proto = {
	nofold+128,
	zero+128,
	0,
	1,
	0,0,
	0,-1,
	0,0
};
int	nfields;
int 	error = 1;
char	*setfil();
char	*sbrk();
char	*brk();

#define	blank(c)	((c) == ' ' || (c) == '\t')

main(argc, argv)
char **argv;
{
	register a;
	extern char end[1];
	char *ep;
	char *arg;
	struct field *p, *q;
	int i;

	copyproto();
	eargv = argv;
	while (--argc > 0) {
		if(**++argv == '-') for(arg = *argv;;) {
			switch(*++arg) {
			case '\0':
				if(arg[-1] == '-')
					eargv[eargc++] = "-";
				break;

			case 'o':
				if(--argc > 0)
					outfil = *++argv;
				continue;

			case 'T':
				if (--argc > 0)
					dirtry[0] = *++argv;
				continue;

			default:
				field(++*argv,nfields>0);
				break;
			}
			break;
		} else if (**argv == '+') {
			if(++nfields>=NF) {
				diag("too many keys","");
				exit(1);
			}
			copyproto();
			field(++*argv,0);
		} else
			eargv[eargc++] = *argv;
	}
	q = &fields[0];
	for(a=1; a<=nfields; a++) {
		p = &fields[a];
		if(p->code != proto.code) continue;
		if(p->ignore != proto.ignore) continue;
		if(p->nflg != proto.nflg) continue;
		if(p->rflg != proto.rflg) continue;
		if(p->bflg[0] != proto.bflg[0]) continue;
		if(p->bflg[1] != proto.bflg[1]) continue;
		p->code = q->code;
		p->ignore = q->ignore;
		p->nflg = q->nflg;
		p->rflg = q->rflg;
		p->bflg[0] = p->bflg[1] = q->bflg[0];
	}
	if(eargc == 0)
		eargv[eargc++] = "-";
	if(cflg && eargc>1) {
		diag("can check only 1 file","");
		exit(1);
	}
	safeoutfil();

	ep = end + MEM;
	lspace = (int *)sbrk(0);
	while((int)brk(ep) == -1)
		ep -= 512;
#ifndef	vax
	brk(ep -= 512);	/* for recursion */
#endif
	a = ep - (char*)lspace;
	nlines = (a-L);
	nlines /= (5*(sizeof(char *)/sizeof(char)));
	ntext = nlines * 4 * (sizeof(char *)/sizeof(char));
	tspace = (char *)(lspace + nlines);
	a = -1;
	for(dirs=dirtry; *dirs; dirs++) {
		sprintf(filep=file1, "%s/stm%05uaa", *dirs, getpid());
		while (*filep)
			filep++;
		filep -= 2;
		if ( (a=creat(file, 0600)) >=0)
			break;
	}
	if(a < 0) {
		diag("can't locate temp","");
		exit(1);
	}
	close(a);
	unlink(file);
	if (signal(SIGHUP, SIG_IGN) != SIG_IGN)
		signal(SIGHUP, term);
	if (signal(SIGINT, SIG_IGN) != SIG_IGN)
		signal(SIGINT, term);
	signal(SIGPIPE,term);
	if (signal(SIGTERM, SIG_IGN) != SIG_IGN)
		signal(SIGTERM,term);
	nfiles = eargc;
	if(!mflg && !cflg) {
		sort();
		fclose(stdin);
	}
	for(a = mflg|cflg?0:eargc; a+N<nfiles || unsafeout&&a<eargc; a=i) {
		i = a+N;
		if(i>=nfiles)
			i = nfiles;
		newfile();
		merge(a, i);
	}
	if(a != nfiles) {
		oldfile();
		merge(a, nfiles);
	}
	error = 0;
	term();
}

sort()
{
	register char *cp;
	register char **lp;
	register lines, text, len;
	int done = 0;
	int i = 0;
	char *f;
	char c;

	if((f = setfil(i++)) == NULL)
		is = stdin;
	else if((is = fopen(f, "r")) == NULL)
		cant(f);

	do {
		cp = tspace;
		lp = (char **)lspace;
		lines = nlines;
		text = ntext;
		while(lines > 0 && text > 0) {
			if(fgets(cp, L, is) == NULL) {
				if(i >= eargc) {
					++done;
					break;
				}
				fclose(is);
				if((f = setfil(i++)) == NULL)
					is = stdin;
				else if((is = fopen(f, "r")) == NULL)
					cant(f);
				continue;
			}
			*lp++ = cp;
			len = strlen(cp) + 1; /* null terminate */
			if(cp[len - 2] != '\n')
				if (len == L) {
					diag("line too long (skipped): ", cp);
					while((c=getc(is)) != EOF && c != '\n')
						/* throw it away */;
					--lp;
					continue;
				} else {
					diag("missing newline before EOF in ",
						f ? f : "standard input");
					/* be friendly, append a newline */
					++len;
					cp[len - 2] = '\n';
					cp[len - 1] = '\0';
				}
			cp += len;
			--lines;
			text -= len;
		}
		qsort((char **)lspace, lp);
		if(done == 0 || nfiles != eargc)
			newfile();
		else
			oldfile();
		clearerr(os);
		while(lp > (char **)lspace) {
			cp = *--lp;
			if(*cp)
				fputs(cp, os);
			if (ferror(os)) {
				error = 1;
				term();
			}
		}
		fclose(os);
	} while(done == 0);
}

struct merg
{
	char	l[L];
	FILE	*b;
} *ibuf[256];

merge(a,b)
{
	struct	merg	*p;
	register char	*cp, *dp;
	register	i;
	struct merg **ip, *jp;
	char	*f;
	int	j;
	int	k, l;
	int	muflg;

	p = (struct merg *)lspace;
	j = 0;
	for(i=a; i < b; i++) {
		f = setfil(i);
		if(f == 0)
			p->b = stdin;
		else if((p->b = fopen(f, "r")) == NULL)
			cant(f);
		ibuf[j] = p;
		if(!rline(p))	j++;
		p++;
	}

	do {
		i = j;
		qsort((char **)ibuf, (char **)(ibuf+i));
		l = 0;
		while(i--) {
			cp = ibuf[i]->l;
			if(*cp == '\0') {
				l = 1;
				if(rline(ibuf[i])) {
					k = i;
					while(++k < j)
						ibuf[k-1] = ibuf[k];
					j--;
				}
			}
		}
	} while(l);

	clearerr(os);
	muflg = mflg & uflg | cflg;
	i = j;
	while(i > 0) {
		cp = ibuf[i-1]->l;
		if (!cflg && (uflg == 0 || muflg || i == 1 ||
			(*compare)(ibuf[i-1]->l,ibuf[i-2]->l))) {
			fputs(cp, os);
			if (ferror(os)) {
				error = 1;
				term();
			}
		}
		if(muflg){
			cp = ibuf[i-1]->l;
			dp = p->l;
			do {
			} while((*dp++ = *cp++) != '\n');
		}
		for(;;) {
			if(rline(ibuf[i-1])) {
				i--;
				if(i == 0)
					break;
				if(i == 1)
					muflg = uflg;
			}
			ip = &ibuf[i];
			while(--ip>ibuf&&(*compare)(ip[0]->l,ip[-1]->l)<0){
				jp = *ip;
				*ip = *(ip-1);
				*(ip-1) = jp;
			}
			if(!muflg)
				break;
			j = (*compare)(ibuf[i-1]->l,p->l);
			if(cflg) {
				if(j > 0)
					disorder("disorder:",ibuf[i-1]->l);
				else if(uflg && j==0)
					disorder("nonunique:",ibuf[i-1]->l);
			} else if(j == 0)
				continue;
			break;
		}
	}
	p = (struct merg *)lspace;
	for(i=a; i<b; i++) {
		fclose(p->b);
		p++;
		if(i >= eargc)
			unlink(setfil(i));
	}
	fclose(os);
}

disorder(s,t)
char *s, *t;
{
	register char *u;
	for(u=t; *u!='\n';u++) ;
	*u = 0;
	diag(s,t);
	term();
}

newfile()
{
	int fd;
	char *f;

	f = setfil(nfiles);
	if ((fd = open(f, O_WRONLY|O_CREAT, 0600)) < 0 ||
	    !(os = fdopen(fd, "w"))) {
		diag("can't create ", f);
		term();
	}
	++nfiles;
}

char *
setfil(i)
{

	if(i < eargc)
		if(eargv[i][0] == '-' && eargv[i][1] == '\0')
			return(0);
		else
			return(eargv[i]);
	i -= eargc;
	filep[0] = i/26 + 'a';
	filep[1] = i%26 + 'a';
	return(file);
}

oldfile()
{

	if(outfil) {
		if((os=fopen(outfil, "w")) == NULL) {
			diag("can't create ",outfil);
			term();
		}
	} else
		os = stdout;
}

safeoutfil()
{
	register int i;
	struct stat obuf,ibuf;

	if(!mflg||outfil==0)
		return;
	if(stat(outfil,&obuf)==-1)
		return;
	for(i=eargc-N;i<eargc;i++) {	/*-N is suff., not nec.*/
		if(stat(eargv[i],&ibuf)==-1)
			continue;
		if(obuf.st_dev==ibuf.st_dev&&
		   obuf.st_ino==ibuf.st_ino)
			unsafeout++;
	}
}

cant(f)
char *f;
{

	perror(f);
	term();
}

diag(s,t)
char *s, *t;
{
	fputs("sort: ",stderr);
	fputs(s,stderr);
	fputs(t,stderr);
	fputs("\n",stderr);
}

void
term()
{
	register i;

	signal(SIGINT, SIG_IGN);
	signal(SIGHUP, SIG_IGN);
	signal(SIGTERM, SIG_IGN);
	if(nfiles == eargc)
		nfiles++;
	for(i=eargc; i<=nfiles; i++) {	/*<= in case of interrupt*/
		unlink(setfil(i));	/*with nfiles not updated*/
	}
	_exit(error);
}

cmp(i, j)
char *i, *j;
{
	register char *pa, *pb;
	char *skip();
	char *code, *ignore;
	int a, b;
	int k;
	char *la, *lb;
	register int sa;
	int sb;
	char *ipa, *ipb, *jpa, *jpb;
	struct field *fp;

	for(k = nfields>0; k<=nfields; k++) {
		fp = &fields[k];
		pa = i;
		pb = j;
		if(k) {
			la = skip(pa, fp, 1);
			pa = skip(pa, fp, 0);
			lb = skip(pb, fp, 1);
			pb = skip(pb, fp, 0);
		} else {
			la = eol(pa);
			lb = eol(pb);
		}
		if(fp->nflg) {
			if(tabchar) {
				if(pa<la&&*pa==tabchar)
					pa++;
				if(pb<lb&&*pb==tabchar)
					pb++;
			}
			while(blank(*pa))
				pa++;
			while(blank(*pb))
				pb++;
			sa = sb = fp->rflg;
			if(*pa == '-') {
				pa++;
				sa = -sa;
			}
			if(*pb == '-') {
				pb++;
				sb = -sb;
			}
			for(ipa = pa; ipa<la&&isdigit(*ipa); ipa++) ;
			for(ipb = pb; ipb<lb&&isdigit(*ipb); ipb++) ;
			jpa = ipa;
			jpb = ipb;
			a = 0;
			if(sa==sb)
				while(ipa > pa && ipb > pb)
					if(b = *--ipb - *--ipa)
						a = b;
			while(ipa > pa)
				if(*--ipa != '0')
					return(-sa);
			while(ipb > pb)
				if(*--ipb != '0')
					return(sb);
			if(a) return(a*sa);
			if(*(pa=jpa) == '.')
				pa++;
			if(*(pb=jpb) == '.')
				pb++;
			if(sa==sb)
				while(pa<la && isdigit(*pa)
				   && pb<lb && isdigit(*pb))
					if(a = *pb++ - *pa++)
						return(a*sa);
			while(pa<la && isdigit(*pa))
				if(*pa++ != '0')
					return(-sa);
			while(pb<lb && isdigit(*pb))
				if(*pb++ != '0')
					return(sb);
			continue;
		}
		code = fp->code;
		ignore = fp->ignore;
loop: 
		while(ignore[*pa])
			pa++;
		while(ignore[*pb])
			pb++;
		if(pa>=la || *pa=='\n')
			if(pb<lb && *pb!='\n')
				return(fp->rflg);
			else continue;
		if(pb>=lb || *pb=='\n')
			return(-fp->rflg);
		if((sa = code[*pb++]-code[*pa++]) == 0)
			goto loop;
		return(sa*fp->rflg);
	}
	if(uflg)
		return(0);
	return(cmpa(i, j));
}

cmpa(pa, pb)
register char *pa, *pb;
{
	while(*pa == *pb) {
		if(*pa++ == '\n')
			return(0);
		pb++;
	}
	return(
		*pa == '\n' ? fields[0].rflg:
		*pb == '\n' ?-fields[0].rflg:
		*pb > *pa   ? fields[0].rflg:
		-fields[0].rflg
	);
}

char *
skip(pp, fp, j)
struct field *fp;
char *pp;
{
	register i;
	register char *p;

	p = pp;
	if( (i=fp->m[j]) < 0)
		return(eol(p));
	while(i-- > 0) {
		if(tabchar != 0) {
			while(*p != tabchar)
				if(*p != '\n')
					p++;
				else goto ret;
			if(i>0||j==0)
				p++;
		} else {
			while(blank(*p))
				p++;
			while(!blank(*p))
				if(*p != '\n')
					p++;
				else goto ret;
		}
	}
	if(tabchar==0||fp->bflg[j])
		while(blank(*p))
			p++;
	i = fp->n[j];
	while(i-- > 0) {
		if(*p != '\n')
			p++;
		else goto ret;
	} 
ret:
	return(p);
}

char *
eol(p)
register char *p;
{
	while(*p != '\n') p++;
	return(p);
}

copyproto()
{
	register i;
	register int *p, *q;

	p = (int *)&proto;
	q = (int *)&fields[nfields];
	for(i=0; i<sizeof(proto)/sizeof(*p); i++)
		*q++ = *p++;
}

field(s,k)
char *s;
{
	register struct field *p;
	register d;
	p = &fields[nfields];
	d = 0;
	for(; *s!=0; s++) {
		switch(*s) {
		case '\0':
			return;

		case 'b':
			p->bflg[k]++;
			break;

		case 'd':
			p->ignore = dict+128;
			break;

		case 'f':
			p->code = fold+128;
			break;
		case 'i':
			p->ignore = nonprint+128;
			break;

		case 'c':
			cflg = 1;
			continue;

		case 'm':
			mflg = 1;
			continue;

		case 'n':
			p->nflg++;
			break;
		case 't':
			tabchar = *++s;
			if(tabchar == 0) s--;
			continue;

		case 'r':
			p->rflg = -1;
			continue;
		case 'u':
			uflg = 1;
			break;

		case '.':
			if(p->m[k] == -1)	/* -m.n with m missing */
				p->m[k] = 0;
			d = &fields[0].n[0]-&fields[0].m[0];

		default:
			p->m[k+d] = number(&s);
		}
		compare = cmp;
	}
}

number(ppa)
char **ppa;
{
	int n;
	register char *pa;
	pa = *ppa;
	n = 0;
	while(isdigit(*pa)) {
		n = n*10 + *pa - '0';
		*ppa = pa++;
	}
	return(n);
}

#define qsexc(p,q) t= *p;*p= *q;*q=t
#define qstexc(p,q,r) t= *p;*p= *r;*r= *q;*q=t

qsort(a,l)
char **a, **l;
{
	register char **i, **j;
	char **k;
	char **lp, **hp;
	int c;
	char *t;
	unsigned n;


start:
	if((n=l-a) <= 1)
		return;


	n /= 2;
	hp = lp = a+n;
	i = a;
	j = l-1;


	for(;;) {
		if(i < lp) {
			if((c = (*compare)(*i, *lp)) == 0) {
				--lp;
				qsexc(i, lp);
				continue;
			}
			if(c < 0) {
				++i;
				continue;
			}
		}

loop:
		if(j > hp) {
			if((c = (*compare)(*hp, *j)) == 0) {
				++hp;
				qsexc(hp, j);
				goto loop;
			}
			if(c > 0) {
				if(i == lp) {
					++hp;
					qstexc(i, hp, j);
					i = ++lp;
					goto loop;
				}
				qsexc(i, j);
				--j;
				++i;
				continue;
			}
			--j;
			goto loop;
		}


		if(i == lp) {
			if(uflg)
				for(k=lp+1; k<=hp;) **k++ = '\0';
			if(lp-a >= l-hp) {
				qsort(hp+1, l);
				l = lp;
			} else {
				qsort(a, lp);
				a = hp+1;
			}
			goto start;
		}


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