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

static	char *sccsid = "@(#)sort.c	4.16 (Berkeley) %G%";

#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();
int	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);
}

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