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

static	char *sccsid = "@(#)sort.c	4.13 (Berkeley) %G%";
#include <sys/param.h>
#include <stdio.h>
#include <ctype.h>
#include <signal.h>
#include <sys/stat.h>

#define	L	2048
#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[] = {"/usr/tmp", "/tmp", 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()
{
	register char *f;

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