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

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

#define	L	1024
#define	N	7
#define	C	20
#ifdef	vax
#define	MEM	(64*2048)
#else
#define	MEM	(16*2048)
#endif
#define NF	10

FILE	*is, *os;
char	*dirtry[] = {"/usr/tmp", "/tmp", NULL};
char	**dirs;
char	file1[30];
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 c;
	int done;
	int i;
	char *f;

	done = 0;
	i = 0;
	c = EOF;
	do {
		cp = tspace;
		lp = (char **)lspace;
		while(lp < (char **)lspace+nlines && cp < tspace+ntext) {
			*lp++ = cp;
			while(c != '\n') {
				if(c != EOF) {
					*cp++ = c;
					c = getc(is);
					continue;
				} else if(is)
					fclose(is);
				if(i < eargc) {
					if((f = setfil(i++)) == 0)
						is = stdin;
					else if((is = fopen(f, "r")) == NULL)
						cant(f);
					c = getc(is);
				} else
					break;
			}
			*cp++ = '\n';
			if(c == EOF) {
				done++;
				lp--;
				break;
			}
			c = getc(is);
		}
		qsort((char **)lspace, lp);
		if(done == 0 || nfiles != eargc)
			newfile();
		else
			oldfile();
		while(lp > (char **)lspace) {
			cp = *--lp;
			if(*cp)
				do
				putc(*cp, os);
				while(*cp++ != '\n');
		}
		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);

	muflg = mflg & uflg | cflg;
	i = j;
	while(i > 0) {
		cp = ibuf[i-1]->l;
		if(!cflg && (uflg == 0 || muflg ||
			(*compare)(ibuf[i-1]->l,ibuf[i-2]->l)))
			do
				putc(*cp, os);
			while(*cp++ != '\n');
		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);
}

rline(mp)
struct merg *mp;
{
	register char *cp;
	register char *ce;
	FILE *bp;
	register c;

	bp = mp->b;
	cp = mp->l;
	ce = cp+L;
	do {
		c = getc(bp);
		if(c == EOF)
			return(1);
		if(cp>=ce)
			cp--;
		*cp++ = c;
	} while(c!='\n');
	return(0);
}

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;
{

	diag("can't open ",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);
}

#ifndef	blank
blank(c)
{
	if(c==' ' || c=='\t')
		return(1);
	return(0);
}
#endif

#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
97be3be5	1	static char *sccsid = "@(#)sort.c 4.4 (Berkeley) %G%";
88ab53e6 BJ	2	#include <stdio.h>
	3	#include <ctype.h>
	4	#include <signal.h>
	5	#include <sys/types.h>
	6	#include <sys/stat.h>
	7
2f164ac0	8	#define L 1024
88ab53e6 BJ	9	#define N 7
88ab53e6 BJ	10	#define C 20
2f164ac0 RE	11	#ifdef vax
	12	#define MEM (64*2048)
	13	#else
88ab53e6	14	#define MEM (16*2048)
2f164ac0	15	#endif
88ab53e6 BJ	16	#define NF 10
	17
	18	FILE is, os;
	19	char *dirtry[] = {"/usr/tmp", "/tmp", NULL};
	20	char **dirs;
	21	char file1[30];
	22	char *file = file1;
	23	char *filep;
	24	int nfiles;
	25	unsigned nlines;
	26	unsigned ntext;
	27	int *lspace;
	28	char *tspace;
	29	int cmp(), cmpa();
	30	int (*compare)() = cmpa;
	31	char *eol();
	32	int term();
	33	int mflg;
	34	int cflg;
	35	int uflg;
	36	char *outfil;
	37	int unsafeout; /kludge to assure -m -o works/
	38	char tabchar;
	39	int eargc;
	40	char **eargv;
	41
	42	char zero[256];
	43
	44	char fold[256] = {
	45	0200,0201,0202,0203,0204,0205,0206,0207,
	46	0210,0211,0212,0213,0214,0215,0216,0217,
	47	0220,0221,0222,0223,0224,0225,0226,0227,
	48	0230,0231,0232,0233,0234,0235,0236,0237,
	49	0240,0241,0242,0243,0244,0245,0246,0247,
	50	0250,0251,0252,0253,0254,0255,0256,0257,
	51	0260,0261,0262,0263,0264,0265,0266,0267,
	52	0270,0271,0272,0273,0274,0275,0276,0277,
	53	0300,0301,0302,0303,0304,0305,0306,0307,
	54	0310,0311,0312,0313,0314,0315,0316,0317,
	55	0320,0321,0322,0323,0324,0325,0326,0327,
	56	0330,0331,0332,0333,0334,0335,0336,0337,
	57	0340,0341,0342,0343,0344,0345,0346,0347,
	58	0350,0351,0352,0353,0354,0355,0356,0357,
	59	0360,0361,0362,0363,0364,0365,0366,0367,
	60	0370,0371,0372,0373,0374,0375,0376,0377,
	61	0000,0001,0002,0003,0004,0005,0006,0007,
	62	0010,0011,0012,0013,0014,0015,0016,0017,
	63	0020,0021,0022,0023,0024,0025,0026,0027,
	64	0030,0031,0032,0033,0034,0035,0036,0037,
	65	0040,0041,0042,0043,0044,0045,0046,0047,
	66	0050,0051,0052,0053,0054,0055,0056,0057,
	67	0060,0061,0062,0063,0064,0065,0066,0067,
	68	0070,0071,0072,0073,0074,0075,0076,0077,
	69	0100,0101,0102,0103,0104,0105,0106,0107,
	70	0110,0111,0112,0113,0114,0115,0116,0117,
	71	0120,0121,0122,0123,0124,0125,0126,0127,
97be3be5	72	0130,0131,0132,0133,0134,0135,0136,0137,
88ab53e6 BJ	73	0140,0101,0102,0103,0104,0105,0106,0107,
	74	0110,0111,0112,0113,0114,0115,0116,0117,
	75	0120,0121,0122,0123,0124,0125,0126,0127,
	76	0130,0131,0132,0173,0174,0175,0176,0177
	77	};
	78	char nofold[256] = {
	79	0200,0201,0202,0203,0204,0205,0206,0207,
	80	0210,0211,0212,0213,0214,0215,0216,0217,
	81	0220,0221,0222,0223,0224,0225,0226,0227,
	82	0230,0231,0232,0233,0234,0235,0236,0237,
	83	0240,0241,0242,0243,0244,0245,0246,0247,
	84	0250,0251,0252,0253,0254,0255,0256,0257,
	85	0260,0261,0262,0263,0264,0265,0266,0267,
	86	0270,0271,0272,0273,0274,0275,0276,0277,
	87	0300,0301,0302,0303,0304,0305,0306,0307,
	88	0310,0311,0312,0313,0314,0315,0316,0317,
	89	0320,0321,0322,0323,0324,0325,0326,0327,
	90	0330,0331,0332,0333,0334,0335,0336,0337,
	91	0340,0341,0342,0343,0344,0345,0346,0347,
	92	0350,0351,0352,0353,0354,0355,0356,0357,
	93	0360,0361,0362,0363,0364,0365,0366,0367,
	94	0370,0371,0372,0373,0374,0375,0376,0377,
	95	0000,0001,0002,0003,0004,0005,0006,0007,
	96	0010,0011,0012,0013,0014,0015,0016,0017,
	97	0020,0021,0022,0023,0024,0025,0026,0027,
	98	0030,0031,0032,0033,0034,0035,0036,0037,
	99	0040,0041,0042,0043,0044,0045,0046,0047,
	100	0050,0051,0052,0053,0054,0055,0056,0057,
	101	0060,0061,0062,0063,0064,0065,0066,0067,
	102	0070,0071,0072,0073,0074,0075,0076,0077,
	103	0100,0101,0102,0103,0104,0105,0106,0107,
	104	0110,0111,0112,0113,0114,0115,0116,0117,
	105	0120,0121,0122,0123,0124,0125,0126,0127,
	106	0130,0131,0132,0133,0134,0135,0136,0137,
	107	0140,0141,0142,0143,0144,0145,0146,0147,
	108	0150,0151,0152,0153,0154,0155,0156,0157,
	109	0160,0161,0162,0163,0164,0165,0166,0167,
	110	0170,0171,0172,0173,0174,0175,0176,0177
	111	};
	112
	113	char nonprint[256] = {
	114	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	115	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	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,0,0,1,1,1,1,1,
	123	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	124	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	125	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	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,1
	130	};
	131
	132	char dict[256] = {
	133	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	134	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	135	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	136	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
137	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
138	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
139	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
140	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
141	1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,
142	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
143	0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
144	0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,
145	1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
146	0,0,0,0,0,0,0,0,0,0,0,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	};
150
151	struct field {
152	char *code;
153	char *ignore;
154	int nflg;
155	int rflg;
156	int bflg[2];
157	int m[2];
158	int n[2];
159	} fields[NF];
160	struct field proto = {
161	nofold+128,
162	zero+128,
163	0,
164	1,
165	0,0,
166	0,-1,
167	0,0
168	};
169	int nfields;
170	int error = 1;
171	char *setfil();
172	char *sbrk();
173	char *brk();
174
2f164ac0 RE	175	#define blank(c) ((c) == ' ' \|\| (c) == '\t')
2f164ac0 RE	176
88ab53e6 BJ	177	main(argc, argv)
	178	char **argv;
	179	{
	180	register a;
	181	extern char end[1];
	182	char *ep;
	183	char *arg;
	184	struct field p, q;
	185	int i;
88ab53e6	186
88ab53e6 BJ	187	copyproto();
	188	eargv = argv;
	189	while (--argc > 0) {
	190	if(*++argv == '-') for(arg = argv;;) {
	191	switch(*++arg) {
	192	case '\0':
	193	if(arg[-1] == '-')
	194	eargv[eargc++] = "-";
	195	break;
	196
	197	case 'o':
	198	if(--argc > 0)
	199	outfil = *++argv;
	200	continue;
	201
	202	case 'T':
	203	if (--argc > 0)
	204	dirtry[0] = *++argv;
	205	continue;
	206
	207	default:
	208	field(++*argv,nfields>0);
	209	break;
	210	}
	211	break;
	212	} else if (**argv == '+') {
	213	if(++nfields>=NF) {
	214	diag("too many keys","");
	215	exit(1);
	216	}
	217	copyproto();
	218	field(++*argv,0);
	219	} else
	220	eargv[eargc++] = *argv;
	221	}
	222	q = &fields[0];
	223	for(a=1; a<=nfields; a++) {
	224	p = &fields[a];
	225	if(p->code != proto.code) continue;
	226	if(p->ignore != proto.ignore) continue;
	227	if(p->nflg != proto.nflg) continue;
	228	if(p->rflg != proto.rflg) continue;
	229	if(p->bflg[0] != proto.bflg[0]) continue;
	230	if(p->bflg[1] != proto.bflg[1]) continue;
	231	p->code = q->code;
	232	p->ignore = q->ignore;
	233	p->nflg = q->nflg;
	234	p->rflg = q->rflg;
	235	p->bflg[0] = p->bflg[1] = q->bflg[0];
	236	}
	237	if(eargc == 0)
	238	eargv[eargc++] = "-";
	239	if(cflg && eargc>1) {
	240	diag("can check only 1 file","");
	241	exit(1);
	242	}
	243	safeoutfil();
	244
	245	ep = end + MEM;
	246	lspace = (int *)sbrk(0);
	247	while((int)brk(ep) == -1)
	248	ep -= 512;
2f164ac0	249	#ifndef vax
88ab53e6	250	brk(ep -= 512); /* for recursion */
2f164ac0	251	#endif
88ab53e6 BJ	252	a = ep - (char*)lspace;
	253	nlines = (a-L);
	254	nlines /= (5(sizeof(char )/sizeof(char)));
2f164ac0	255	ntext = nlines * 4 * (sizeof(char *)/sizeof(char));
88ab53e6 BJ	256	tspace = (char *)(lspace + nlines);
	257	a = -1;
	258	for(dirs=dirtry; *dirs; dirs++) {
	259	sprintf(filep=file1, "%s/stm%05uaa", *dirs, getpid());
	260	while (*filep)
	261	filep++;
	262	filep -= 2;
	263	if ( (a=creat(file, 0600)) >=0)
	264	break;
	265	}
	266	if(a < 0) {
	267	diag("can't locate temp","");
	268	exit(1);
	269	}
	270	close(a);
3acd6e45 BJ	271	unlink(file);
	272	if (signal(SIGHUP, SIG_IGN) != SIG_IGN)
	273	signal(SIGHUP, term);
88ab53e6 BJ	274	if (signal(SIGINT, SIG_IGN) != SIG_IGN)
	275	signal(SIGINT, term);
	276	signal(SIGPIPE,term);
3acd6e45 BJ	277	if (signal(SIGTERM, SIG_IGN) != SIG_IGN)
3acd6e45 BJ	278	signal(SIGTERM,term);
88ab53e6 BJ	279	nfiles = eargc;
	280	if(!mflg && !cflg) {
	281	sort();
	282	fclose(stdin);
	283	}
	284	for(a = mflg\|cflg?0:eargc; a+N<nfiles \|\| unsafeout&&a<eargc; a=i) {
	285	i = a+N;
	286	if(i>=nfiles)
	287	i = nfiles;
	288	newfile();
	289	merge(a, i);
	290	}
	291	if(a != nfiles) {
	292	oldfile();
	293	merge(a, nfiles);
	294	}
	295	error = 0;
	296	term();
	297	}
	298
	299	sort()
	300	{
	301	register char *cp;
	302	register char **lp;
	303	register c;
	304	int done;
	305	int i;
	306	char *f;
	307
	308	done = 0;
	309	i = 0;
	310	c = EOF;
	311	do {
	312	cp = tspace;
	313	lp = (char **)lspace;
	314	while(lp < (char **)lspace+nlines && cp < tspace+ntext) {
	315	*lp++ = cp;
	316	while(c != '\n') {
	317	if(c != EOF) {
	318	*cp++ = c;
	319	c = getc(is);
	320	continue;
	321	} else if(is)
	322	fclose(is);
	323	if(i < eargc) {
	324	if((f = setfil(i++)) == 0)
	325	is = stdin;
	326	else if((is = fopen(f, "r")) == NULL)
	327	cant(f);
	328	c = getc(is);
	329	} else
	330	break;
	331	}
	332	*cp++ = '\n';
	333	if(c == EOF) {
	334	done++;
	335	lp--;
	336	break;
	337	}
	338	c = getc(is);
	339	}
	340	qsort((char **)lspace, lp);
	341	if(done == 0 \|\| nfiles != eargc)
	342	newfile();
343	else
344	oldfile();
345	while(lp > (char **)lspace) {
346	cp = *--lp;
347	if(*cp)
348	do
349	putc(*cp, os);
350	while(*cp++ != '\n');
351	}
352	fclose(os);
353	} while(done == 0);
354	}
355
356	struct merg
357	{
358	char l[L];
359	FILE *b;
360	} *ibuf[256];
361
362	merge(a,b)
363	{
364	struct merg *p;
365	register char cp, dp;
366	register i;
367	struct merg *ip, jp;
368	char *f;
369	int j;
370	int k, l;
371	int muflg;
372
373	p = (struct merg *)lspace;
374	j = 0;
375	for(i=a; i < b; i++) {
376	f = setfil(i);
377	if(f == 0)
378	p->b = stdin;
379	else if((p->b = fopen(f, "r")) == NULL)
380	cant(f);
381	ibuf[j] = p;
382	if(!rline(p)) j++;
383	p++;
384	}
385
386	do {
387	i = j;
388	qsort((char )ibuf, (char )(ibuf+i));
389	l = 0;
390	while(i--) {
391	cp = ibuf[i]->l;
392	if(*cp == '\0') {
393	l = 1;
394	if(rline(ibuf[i])) {
395	k = i;
396	while(++k < j)
397	ibuf[k-1] = ibuf[k];
398	j--;
399	}
400	}
401	}
402	} while(l);
403
404	muflg = mflg & uflg \| cflg;
405	i = j;
406	while(i > 0) {
407	cp = ibuf[i-1]->l;
408	if(!cflg && (uflg == 0 \|\| muflg \|\|
409	(*compare)(ibuf[i-1]->l,ibuf[i-2]->l)))
410	do
411	putc(*cp, os);
412	while(*cp++ != '\n');
413	if(muflg){
414	cp = ibuf[i-1]->l;
415	dp = p->l;
416	do {
417	} while((dp++ = cp++) != '\n');
418	}
419	for(;;) {
420	if(rline(ibuf[i-1])) {
421	i--;
422	if(i == 0)
423	break;
424	if(i == 1)
425	muflg = uflg;
426	}
427	ip = &ibuf[i];
428	while(--ip>ibuf&&(*compare)(ip[0]->l,ip[-1]->l)<0){
429	jp = *ip;
430	ip = (ip-1);
431	*(ip-1) = jp;
432	}
433	if(!muflg)
434	break;
435	j = (*compare)(ibuf[i-1]->l,p->l);
436	if(cflg) {
437	if(j > 0)
438	disorder("disorder:",ibuf[i-1]->l);
439	else if(uflg && j==0)
440	disorder("nonunique:",ibuf[i-1]->l);
441	} else if(j == 0)
442	continue;
443	break;
444	}
445	}
446	p = (struct merg *)lspace;
447	for(i=a; i<b; i++) {
448	fclose(p->b);
449	p++;
450	if(i >= eargc)
451	unlink(setfil(i));
452	}
453	fclose(os);
454	}
455
456	rline(mp)
457	struct merg *mp;
458	{
459	register char *cp;
460	register char *ce;
461	FILE *bp;
462	register c;
463
464	bp = mp->b;
465	cp = mp->l;
466	ce = cp+L;
467	do {
468	c = getc(bp);
469	if(c == EOF)
470	return(1);
471	if(cp>=ce)
472	cp--;
473	*cp++ = c;
474	} while(c!='\n');
475	return(0);
476	}
477
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
549	diag("can't open ",f);
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	}
3acd6e45	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
2f164ac0	831	#ifndef blank
88ab53e6 BJ	832	blank(c)
	833	{
	834	if(c==' ' \|\| c=='\t')
	835	return(1);
	836	return(0);
	837	}
2f164ac0	838	#endif
88ab53e6 BJ	839
	840	#define qsexc(p,q) t= p;p= q;q=t
	841	#define qstexc(p,q,r) t= p;p= r;r= q;q=t
	842
	843	qsort(a,l)
	844	char a, l;
	845	{
	846	register char i, j;
	847	char **k;
	848	char lp, hp;
	849	int c;
	850	char *t;
	851	unsigned n;
	852
	853
	854
	855	start:
	856	if((n=l-a) <= 1)
	857	return;
	858
	859
	860	n /= 2;
	861	hp = lp = a+n;
	862	i = a;
	863	j = l-1;
	864
	865
	866	for(;;) {
	867	if(i < lp) {
	868	if((c = (compare)(i, *lp)) == 0) {
	869	--lp;
	870	qsexc(i, lp);
	871	continue;
	872	}
	873	if(c < 0) {
	874	++i;
	875	continue;
	876	}
	877	}
	878
	879	loop:
	880	if(j > hp) {
	881	if((c = (compare)(hp, *j)) == 0) {
	882	++hp;
	883	qsexc(hp, j);
	884	goto loop;
	885	}
	886	if(c > 0) {
	887	if(i == lp) {
	888	++hp;
	889	qstexc(i, hp, j);
	890	i = ++lp;
	891	goto loop;
	892	}
	893	qsexc(i, j);
	894	--j;
	895	++i;
	896	continue;
	897	}
	898	--j;
	899	goto loop;
	900	}
	901
	902
903	if(i == lp) {
904	if(uflg)
905	for(k=lp+1; k<=hp;) **k++ = '\0';
906	if(lp-a >= l-hp) {
907	qsort(hp+1, l);
908	l = lp;
909	} else {
910	qsort(a, lp);
911	a = hp+1;
912	}
913	goto start;
914	}
915
916
917	--lp;
918	qstexc(j, lp, i);
919	j = --hp;
920	}
921	}
922