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

/*-
 * Copyright (c) 1986 The Regents of the University of California.
 * All rights reserved.
 *
 * %sccs.include.proprietary.c%
 */

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

#ifndef lint
static char sccsid[] = "@(#)sort.c	4.18 (Berkeley) %G%";
#endif /* not lint */

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

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

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

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

char zero[256];

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

newfile()
{
	int fd;
	char *f;

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

char *
setfil(i)
{

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

oldfile()
{

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

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

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

cant(f)
char *f;
{

	perror(f);
	term();
}

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

void
term()
{
	register i;

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

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

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

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

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

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

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

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

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

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

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

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

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

		case 'c':
			cflg = 1;
			continue;

		case 'm':
			mflg = 1;
			continue;

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

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

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

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

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

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

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


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


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


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

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


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


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