src/cmd/sort.c

#include	<u.h>
#include	<libc.h>
#include	<bio.h>

/*
bugs:
	00/ff for end of file can conflict with 00/ff characters
*/

enum
{
	Nline	= 500000,		/* default max number of lines saved in memory */
	Nmerge	= 10,			/* max number of temporary files merged */
	Nfield	= 20,			/* max number of argument fields */

	Bflag	= 1<<0,			/* flags per field */
	B1flag	= 1<<1,

	Dflag	= 1<<2,
	Fflag	= 1<<3,
	Gflag	= 1<<4,
	Iflag	= 1<<5,
	Mflag	= 1<<6,
	Nflag	= 1<<7,
	Rflag	= 1<<8,
	Wflag	= 1<<9,

	NSstart	= 0,			/* states for number to key decoding */
	NSsign,
	NSzero,
	NSdigit,
	NSpoint,
	NSfract,
	NSzerofract,
	NSexp,
	NSexpsign,
	NSexpdigit
};

typedef	struct	Line	Line;
typedef	struct	Key	Key;
typedef	struct	Merge	Merge;
typedef	struct	Field	Field;

struct	Line
{
	Key*	key;
	int	llen;		/* always >= 1 */
	uchar	line[1];	/* always ends in '\n' */
};

struct	Merge
{
	Key*	key;		/* copy of line->key so (Line*) looks like (Merge*) */
	Line*	line;		/* line at the head of a merged temp file */
	int	fd;		/* file descriptor */
	Biobuf	b;		/* iobuf for reading a temp file */
};

struct	Key
{
	int	klen;
	uchar	key[1];
};

struct	Field
{
	int	beg1;
	int	beg2;
	int	end1;
	int	end2;

	long	flags;
	uchar	mapto[256];

	void	(*dokey)(Key*, uchar*, uchar*, Field*);
};

struct args
{
	char*	ofile;
	char*	tname;
	Rune	tabchar;
	char	cflag;
	char	uflag;
	char	vflag;
	int	nfield;
	int	nfile;
	Field	field[Nfield];

	Line**	linep;
	long	nline;			/* number of lines in this temp file */
	long	lineno;			/* overall ordinal for -s option */
	int	ntemp;
	long	mline;			/* max lines per file */
} args;

extern	int	latinmap[];
extern	Rune*	month[12];

void	buildkey(Line*);
void	doargs(int, char*[]);
void	dofield(char*, int*, int*, int, int);
void	dofile(Biobuf*);
void	dokey_(Key*, uchar*, uchar*, Field*);
void	dokey_dfi(Key*, uchar*, uchar*, Field*);
void	dokey_gn(Key*, uchar*, uchar*, Field*);
void	dokey_m(Key*, uchar*, uchar*, Field*);
void	dokey_r(Key*, uchar*, uchar*, Field*);
void	done(char*);
int	kcmp(Key*, Key*);
void	makemapd(Field*);
void	makemapm(Field*);
void	mergefiles(int, int, Biobuf*);
void	mergeout(Biobuf*);
void	newfield(void);
Line*	newline(Biobuf*);
void	nomem(void);
void	notifyf(void*, char*);
void	printargs(void);
void	printout(Biobuf*);
void	setfield(int, int);
uchar*	skip(uchar*, int, int, int, int);
void	sort4(void*, ulong);
char*	tempfile(int);
void	tempout(void);
void	lineout(Biobuf*, Line*);

void
main(int argc, char *argv[])
{
	int i, f;
	char *s;
	Biobuf bbuf;

	notify(notifyf);	/**/
	doargs(argc, argv);
	if(args.vflag)
		printargs();

	for(i=1; i<argc; i++) {
		s = argv[i];
		if(s == 0)
			continue;
		if(strcmp(s, "-") == 0) {
			Binit(&bbuf, 0, OREAD);
			dofile(&bbuf);
			Bterm(&bbuf);
			continue;
		}
		f = open(s, OREAD);
		if(f < 0) {
			fprint(2, "sort: open %s: %r\n", s);
			done("open");
		}
		Binit(&bbuf, f, OREAD);
		dofile(&bbuf);
		Bterm(&bbuf);
		close(f);
	}
	if(args.nfile == 0) {
		Binit(&bbuf, 0, OREAD);
		dofile(&bbuf);
		Bterm(&bbuf);
	}
	if(args.cflag)
		done(0);
	if(args.vflag)
		fprint(2, "=========\n");

	f = 1;
	if(args.ofile) {
		f = create(args.ofile, OWRITE, 0666);
		if(f < 0) {
			fprint(2, "sort: create %s: %r\n", args.ofile);
			done("create");
		}
	}

	Binit(&bbuf, f, OWRITE);
	if(args.ntemp) {
		tempout();
		mergeout(&bbuf);
	} else {
		printout(&bbuf);
	}
	Bterm(&bbuf);
	done(0);
}

void
dofile(Biobuf *b)
{
	Line *l, *ol;
	int n;

	if(args.cflag) {
		ol = newline(b);
		if(ol == 0)
			return;
		for(;;) {
			l = newline(b);
			if(l == 0)
				break;
			n = kcmp(ol->key, l->key);
			if(n > 0 || (n == 0 && args.uflag)) {
				fprint(2, "sort: -c file not in sort\n"); /**/
				done("order");
			}
			free(ol->key);
			free(ol);
			ol = l;
		}
		return;
	}

	if(args.linep == 0) {
		args.linep = malloc(args.mline * sizeof(args.linep));
		if(args.linep == 0)
			nomem();
	}
	for(;;) {
		l = newline(b);
		if(l == 0)
			break;
		if(args.nline >= args.mline)
			tempout();
		args.linep[args.nline] = l;
		args.nline++;
		args.lineno++;
	}
}

void
notifyf(void *a, char *s)
{
	USED(a);
	if(strcmp(s, "interrupt") == 0)
		done(0);
	if(strcmp(s, "hangup") == 0)
		done(0);
	if(strcmp(s, "kill") == 0)
		done(0);
	if(strncmp(s, "sys: write on closed pipe", 25) == 0)
		done(0);
	noted(NDFLT);
}

Line*
newline(Biobuf *b)
{
	Line *l;
	char *p;
	int n, c;

	p = Brdline(b, '\n');
	n = Blinelen(b);
	if(p == 0) {
		if(n == 0)
			return 0;
		l = 0;
		for(n=0;;) {
			if((n & 31) == 0) {
				l = realloc(l, sizeof(Line) +
					(n+31)*sizeof(l->line[0]));
				if(l == 0)
					nomem();
			}
			c = Bgetc(b);
			if(c < 0) {
				fprint(2, "sort: newline added\n");
				c = '\n';
			}
			l->line[n++] = c;
			if(c == '\n')
				break;
		}
		l->llen = n;
		buildkey(l);
		return l;
	}
	l = malloc(sizeof(Line) +
		(n-1)*sizeof(l->line[0]));
	if(l == 0)
		nomem();
	l->llen = n;
	memmove(l->line, p, n);
	buildkey(l);
	return l;
}

void
lineout(Biobuf *b, Line *l)
{
	int n, m;

	n = l->llen;
	m = Bwrite(b, l->line, n);
	if(n != m)
		exits("write");
}

void
tempout(void)
{
	long n;
	Line **lp, *l;
	char *tf;
	int f;
	Biobuf tb;

	sort4(args.linep, args.nline);
	tf = tempfile(args.ntemp);
	args.ntemp++;
	f = create(tf, OWRITE, 0666);
	if(f < 0) {
		fprint(2, "sort: create %s: %r\n", tf);
		done("create");
	}

	Binit(&tb, f, OWRITE);
	lp = args.linep;
	for(n=args.nline; n>0; n--) {
		l = *lp++;
		lineout(&tb, l);
		free(l->key);
		free(l);
	}
	args.nline = 0;
	Bterm(&tb);
	close(f);
}

void
done(char *xs)
{
	int i;

	for(i=0; i<args.ntemp; i++)
		remove(tempfile(i));
	exits(xs);
}

void
nomem(void)
{
	fprint(2, "sort: out of memory\n");
	done("mem");
}

char*
tempfile(int n)
{
	static char file[100];
	static uint pid;
	char *dir;

	dir = "/var/tmp";
	if(args.tname)
		dir = args.tname;
	if(strlen(dir) >= nelem(file)-20) {
		fprint(2, "temp file directory name is too long: %s\n", dir);
		done("tdir");
	}

	if(pid == 0) {
		pid = getpid();
		if(pid == 0) {
			pid = time(0);
			if(pid == 0)
				pid = 1;
		}
	}

	sprint(file, "%s/sort.%.4d.%.4d", dir, pid%10000, n);
	return file;
}

void
mergeout(Biobuf *b)
{
	int n, i, f;
	char *tf;
	Biobuf tb;

	for(i=0; i<args.ntemp; i+=n) {
		n = args.ntemp - i;
		if(n > Nmerge) {
			tf = tempfile(args.ntemp);
			args.ntemp++;
			f = create(tf, OWRITE, 0666);
			if(f < 0) {
				fprint(2, "sort: create %s: %r\n", tf);
				done("create");
			}
			Binit(&tb, f, OWRITE);

			n = Nmerge;
			mergefiles(i, n, &tb);

			Bterm(&tb);
			close(f);
		} else
			mergefiles(i, n, b);
	}
}

void
mergefiles(int t, int n, Biobuf *b)
{
	Merge *m, *mp, **mmp;
	Key *ok;
	Line *l;
	char *tf;
	int i, f, nn;

	mmp = malloc(n*sizeof(*mmp));
	mp = malloc(n*sizeof(*mp));
	if(mmp == 0 || mp == 0)
		nomem();

	nn = 0;
	m = mp;
	for(i=0; i<n; i++,m++) {
		tf = tempfile(t+i);
		f = open(tf, OREAD);
		if(f < 0) {
			fprint(2, "sort: reopen %s: %r\n", tf);
			done("open");
		}
		m->fd = f;
		Binit(&m->b, f, OREAD);
		mmp[nn] = m;

		l = newline(&m->b);
		if(l == 0)
			continue;
		nn++;
		m->line = l;
		m->key = l->key;
	}

	ok = 0;
	for(;;) {
		sort4(mmp, nn);
		m = *mmp;
		if(nn == 0)
			break;
		for(;;) {
			l = m->line;
			if(args.uflag && ok && kcmp(ok, l->key) == 0) {
				free(l->key);
				free(l);
			} else {
				lineout(b, l);
				if(ok)
					free(ok);
				ok = l->key;
				free(l);
			}

			l = newline(&m->b);
			if(l == 0) {
				nn--;
				mmp[0] = mmp[nn];
				break;
			}
			m->line = l;
			m->key = l->key;
			if(nn > 1 && kcmp(mmp[0]->key, mmp[1]->key) > 0)
				break;
		}
	}
	if(ok)
		free(ok);

	m = mp;
	for(i=0; i<n; i++,m++) {
		Bterm(&m->b);
		close(m->fd);
	}

	free(mp);
	free(mmp);
}

int
kcmp(Key *ka, Key *kb)
{
	int n, m;

	/*
	 * set n to length of smaller key
	 */
	n = ka->klen;
	m = kb->klen;
	if(n > m)
		n = m;
	return memcmp(ka->key, kb->key, n);
}

void
printout(Biobuf *b)
{
	long n;
	Line **lp, *l;
	Key *ok;

	sort4(args.linep, args.nline);
	lp = args.linep;
	ok = 0;
	for(n=args.nline; n>0; n--) {
		l = *lp++;
		if(args.uflag && ok && kcmp(ok, l->key) == 0)
			continue;
		lineout(b, l);
		ok = l->key;
	}
}

void
setfield(int n, int c)
{
	Field *f;

	f = &args.field[n];
	switch(c) {
	default:
		fprint(2, "sort: unknown option: field.%C\n", c);
		done("option");
	case 'b':	/* skip blanks */
		f->flags |= Bflag;
		break;
	case 'd':	/* directory order */
		f->flags |= Dflag;
		break;
	case 'f':	/* fold case */
		f->flags |= Fflag;
		break;
	case 'g':	/* floating point -n case */
		f->flags |= Gflag;
		break;
	case 'i':	/* ignore non-ascii */
		f->flags |= Iflag;
		break;
	case 'M':	/* month */
		f->flags |= Mflag;
		break;
	case 'n':	/* numbers */
		f->flags |= Nflag;
		break;
	case 'r':	/* reverse */
		f->flags |= Rflag;
		break;
	case 'w':	/* ignore white */
		f->flags |= Wflag;
		break;
	}
}

void
dofield(char *s, int *n1, int *n2, int off1, int off2)
{
	int c, n;

	c = *s++;
	if(c >= '0' && c <= '9') {
		n = 0;
		while(c >= '0' && c <= '9') {
			n = n*10 + (c-'0');
			c = *s++;
		}
		n -= off1;	/* posix committee: rot in hell */
		if(n < 0) {
			fprint(2, "sort: field offset must be positive\n");
			done("option");
		}
		*n1 = n;
	}
	if(c == '.') {
		c = *s++;
		if(c >= '0' && c <= '9') {
			n = 0;
			while(c >= '0' && c <= '9') {
				n = n*10 + (c-'0');
				c = *s++;
			}
			n -= off2;
			if(n < 0) {
				fprint(2, "sort: character offset must be positive\n");
				done("option");
			}
			*n2 = n;
		}
	}
	while(c != 0) {
		setfield(args.nfield, c);
		c = *s++;
	}
}

void
printargs(void)
{
	int i, n;
	Field *f;
	char *prefix;

	fprint(2, "sort");
	for(i=0; i<=args.nfield; i++) {
		f = &args.field[i];
		prefix = " -";
		if(i) {
			n = f->beg1;
			if(n >= 0)
				fprint(2, " +%d", n);
			else
				fprint(2, " +*");
			n = f->beg2;
			if(n >= 0)
				fprint(2, ".%d", n);
			else
				fprint(2, ".*");

			if(f->flags & B1flag)
				fprint(2, "b");

			n = f->end1;
			if(n >= 0)
				fprint(2, " -%d", n);
			else
				fprint(2, " -*");
			n = f->end2;
			if(n >= 0)
				fprint(2, ".%d", n);
			else
				fprint(2, ".*");
			prefix = "";
		}
		if(f->flags & Bflag)
			fprint(2, "%sb", prefix);
		if(f->flags & Dflag)
			fprint(2, "%sd", prefix);
		if(f->flags & Fflag)
			fprint(2, "%sf", prefix);
		if(f->flags & Gflag)
			fprint(2, "%sg", prefix);
		if(f->flags & Iflag)
			fprint(2, "%si", prefix);
		if(f->flags & Mflag)
			fprint(2, "%sM", prefix);
		if(f->flags & Nflag)
			fprint(2, "%sn", prefix);
		if(f->flags & Rflag)
			fprint(2, "%sr", prefix);
		if(f->flags & Wflag)
			fprint(2, "%sw", prefix);
	}
	if(args.cflag)
		fprint(2, " -c");
	if(args.uflag)
		fprint(2, " -u");
	if(args.ofile)
		fprint(2, " -o %s", args.ofile);
	if(args.mline != Nline)
		fprint(2, " -l %ld", args.mline);
	fprint(2, "\n");
}

void
newfield(void)
{
	int n;
	Field *f;

	n = args.nfield + 1;
	if(n >= Nfield) {
		fprint(2, "sort: too many fields specified\n");
		done("option");
	}
	args.nfield = n;
	f = &args.field[n];
	f->beg1 = -1;
	f->beg2 = -1;
	f->end1 = -1;
	f->end2 = -1;
}

void
doargs(int argc, char *argv[])
{
	int i, c, hadplus;
	char *s, *p, *q;
	Field *f;

	hadplus = 0;
	args.mline = Nline;
	for(i=1; i<argc; i++) {
		s = argv[i];
		c = *s++;
		if(c == '-') {
			c = *s;
			if(c == 0)		/* forced end of arg marker */
				break;
			argv[i] = 0;		/* clobber args processed */
			if(c == '.' || (c >= '0' && c <= '9')) {
				if(!hadplus)
					newfield();
				f = &args.field[args.nfield];
				dofield(s, &f->end1, &f->end2, 0, 0);
				hadplus = 0;
				continue;
			}

			while(c = *s++)
			switch(c) {
			case '-':	/* end of options */
				i = argc;
				continue;
			case 'T':	/* temp directory */
				if(*s == 0) {
					i++;
					if(i < argc) {
						args.tname = argv[i];
						argv[i] = 0;
					}
				} else
					args.tname = s;
				s = strchr(s, 0);
				break;
			case 'o':	/* output file */
				if(*s == 0) {
					i++;
					if(i < argc) {
						args.ofile = argv[i];
						argv[i] = 0;
					}
				} else
					args.ofile = s;
				s = strchr(s, 0);
				break;
			case 'k':	/* posix key (what were they thinking?) */
				p = 0;
				if(*s == 0) {
					i++;
					if(i < argc) {
						p = argv[i];
						argv[i] = 0;
					}
				} else
					p = s;
				s = strchr(s, 0);
				if(p == 0)
					break;

				newfield();
				q = strchr(p, ',');
				if(q)
					*q++ = 0;
				f = &args.field[args.nfield];
				dofield(p, &f->beg1, &f->beg2, 1, 1);
				if(f->flags & Bflag) {
					f->flags |= B1flag;
					f->flags &= ~Bflag;
				}
				if(q) {
					dofield(q, &f->end1, &f->end2, 1, 0);
					if(f->end2 <= 0)
						f->end1++;
				}
				hadplus = 0;
				break;
			case 't':	/* tab character */
				if(*s == 0) {
					i++;
					if(i < argc) {
						chartorune(&args.tabchar, argv[i]);
						argv[i] = 0;
					}
				} else
					s += chartorune(&args.tabchar, s);
				if(args.tabchar == '\n') {
					fprint(2, "aw come on, rob\n");
					done("rob");
				}
				break;
			case 'c':	/* check order */
				args.cflag = 1;
				break;
			case 'u':	/* unique */
				args.uflag = 1;
				break;
			case 'v':	/* debugging noise */
				args.vflag = 1;
				break;
			case 'l':
				if(*s == 0) {
					i++;
					if(i < argc) {
						args.mline = atol(argv[i]);
						argv[i] = 0;
					}
				} else
					args.mline = atol(s);
				s = strchr(s, 0);
				break;

			case 'M':	/* month */
			case 'b':	/* skip blanks */
			case 'd':	/* directory order */
			case 'f':	/* fold case */
			case 'g':	/* floating numbers */
			case 'i':	/* ignore non-ascii */
			case 'n':	/* numbers */
			case 'r':	/* reverse */
			case 'w':	/* ignore white */
				if(args.nfield > 0)
					fprint(2, "sort: global field set after -k\n");
				setfield(0, c);
				break;
			case 'm':
				/* option m silently ignored but required by posix */
				break;
			default:
				fprint(2, "sort: unknown option: -%C\n", c);
				done("option");
			}
			continue;
		}
		if(c == '+') {
			argv[i] = 0;		/* clobber args processed */
			c = *s;
			if(c == '.' || (c >= '0' && c <= '9')) {
				newfield();
				f = &args.field[args.nfield];
				dofield(s, &f->beg1, &f->beg2, 0, 0);
				if(f->flags & Bflag) {
					f->flags |= B1flag;
					f->flags &= ~Bflag;
				}
				hadplus = 1;
				continue;
			}
			fprint(2, "sort: unknown option: +%C\n", c);
			done("option");
		}
		args.nfile++;
	}

	for(i=0; i<=args.nfield; i++) {
		f = &args.field[i];

		/*
		 * global options apply to fields that
		 * specify no options
		 */
		if(f->flags == 0) {
			f->flags = args.field[0].flags;
			if(args.field[0].flags & Bflag)
				f->flags |= B1flag;
		}


		/*
		 * build buildkey specification
		 */
		switch(f->flags & ~(Bflag|B1flag)) {
		default:
			fprint(2, "sort: illegal combination of flags: %lx\n", f->flags);
			done("option");
		case 0:
			f->dokey = dokey_;
			break;
		case Rflag:
			f->dokey = dokey_r;
			break;
		case Gflag:
		case Nflag:
		case Gflag|Nflag:
		case Gflag|Rflag:
		case Nflag|Rflag:
		case Gflag|Nflag|Rflag:
			f->dokey = dokey_gn;
			break;
		case Mflag:
		case Mflag|Rflag:
			f->dokey = dokey_m;
			makemapm(f);
			break;
		case Dflag:
		case Dflag|Fflag:
		case Dflag|Fflag|Iflag:
		case Dflag|Fflag|Iflag|Rflag:
		case Dflag|Fflag|Iflag|Rflag|Wflag:
		case Dflag|Fflag|Iflag|Wflag:
		case Dflag|Fflag|Rflag:
		case Dflag|Fflag|Rflag|Wflag:
		case Dflag|Fflag|Wflag:
		case Dflag|Iflag:
		case Dflag|Iflag|Rflag:
		case Dflag|Iflag|Rflag|Wflag:
		case Dflag|Iflag|Wflag:
		case Dflag|Rflag:
		case Dflag|Rflag|Wflag:
		case Dflag|Wflag:
		case Fflag:
		case Fflag|Iflag:
		case Fflag|Iflag|Rflag:
		case Fflag|Iflag|Rflag|Wflag:
		case Fflag|Iflag|Wflag:
		case Fflag|Rflag:
		case Fflag|Rflag|Wflag:
		case Fflag|Wflag:
		case Iflag:
		case Iflag|Rflag:
		case Iflag|Rflag|Wflag:
		case Iflag|Wflag:
		case Wflag:
			f->dokey = dokey_dfi;
			makemapd(f);
			break;
		}
	}

	/*
	 * random spot checks
	 */
	if(args.nfile > 1 && args.cflag) {
		fprint(2, "sort: -c can have at most one input file\n");
		done("option");
	}
	return;
}

uchar*
skip(uchar *l, int n1, int n2, int bflag, int endfield)
{
	int i, c, tc;
	Rune r;

	if(endfield && n1 < 0)
		return 0;

	c = *l++;
	tc = args.tabchar;
	if(tc) {
		if(tc < Runeself) {
			for(i=n1; i>0; i--) {
				while(c != tc) {
					if(c == '\n')
						return 0;
					c = *l++;
				}
				if(!(endfield && i == 1))
					c = *l++;
			}
		} else {
			l--;
			l += chartorune(&r, (char*)l);
			for(i=n1; i>0; i--) {
				while(r != tc) {
					if(r == '\n')
						return 0;
					l += chartorune(&r, (char*)l);
				}
				if(!(endfield && i == 1))
					l += chartorune(&r, (char*)l);
			}
			c = r;
		}
	} else {
		for(i=n1; i>0; i--) {
			while(c == ' ' || c == '\t')
				c = *l++;
			while(c != ' ' && c != '\t') {
				if(c == '\n')
					return 0;
				c = *l++;
			}
		}
	}

	if(bflag)
		while(c == ' ' || c == '\t')
			c = *l++;

	l--;
	for(i=n2; i>0; i--) {
		c = *l;
		if(c < Runeself) {
			if(c == '\n')
				return 0;
			l++;
			continue;
		}
		l += chartorune(&r, (char*)l);
	}
	return l;
}

void
dokey_gn(Key *k, uchar *lp, uchar *lpe, Field *f)
{
	uchar *kp;
	int c, cl, dp;
	int state, nzero, exp, expsign, rflag;

	cl = k->klen + 3;
	kp = k->key + cl;	/* skip place for sign, exponent[2] */

	nzero = 0;		/* number of trailing zeros */
	exp = 0;		/* value of the exponent */
	expsign = 0;		/* sign of the exponent */
	dp = 0x4040;		/* location of decimal point */
	rflag = f->flags&Rflag;	/* xor of rflag and - sign */
	state = NSstart;

	for(;; lp++) {
		if(lp >= lpe)
			break;
		c = *lp;

		if(c == ' ' || c == '\t') {
			switch(state) {
			case NSstart:
			case NSsign:
				continue;
			}
			break;
		}
		if(c == '+' || c == '-') {
			switch(state) {
			case NSstart:
				state = NSsign;
				if(c == '-')
					rflag = !rflag;
				continue;
			case NSexp:
				state = NSexpsign;
				if(c == '-')
					expsign = 1;
				continue;
			}
			break;
		}
		if(c == '0') {
			switch(state) {
			case NSdigit:
				if(rflag)
					c = ~c;
				*kp++ = c;
				cl++;
				nzero++;
				dp++;
				state = NSdigit;
				continue;
			case NSfract:
				if(rflag)
					c = ~c;
				*kp++ = c;
				cl++;
				nzero++;
				state = NSfract;
				continue;
			case NSstart:
			case NSsign:
			case NSzero:
				state = NSzero;
				continue;
			case NSzerofract:
			case NSpoint:
				dp--;
				state = NSzerofract;
				continue;
			case NSexpsign:
			case NSexp:
			case NSexpdigit:
				exp = exp*10 + (c - '0');
				state = NSexpdigit;
				continue;
			}
			break;
		}
		if(c >= '1' && c <= '9') {
			switch(state) {
			case NSzero:
			case NSstart:
			case NSsign:
			case NSdigit:
				if(rflag)
					c = ~c;
				*kp++ = c;
				cl++;
				nzero = 0;
				dp++;
				state = NSdigit;
				continue;
			case NSzerofract:
			case NSpoint:
			case NSfract:
				if(rflag)
					c = ~c;
				*kp++ = c;
				cl++;
				nzero = 0;
				state = NSfract;
				continue;
			case NSexpsign:
			case NSexp:
			case NSexpdigit:
				exp = exp*10 + (c - '0');
				state = NSexpdigit;
				continue;
			}
			break;
		}
		if(c == '.') {
			switch(state) {
			case NSstart:
			case NSsign:
				state = NSpoint;
				continue;
			case NSzero:
				state = NSzerofract;
				continue;
			case NSdigit:
				state = NSfract;
				continue;
			}
			break;
		}
		if((f->flags & Gflag) && (c == 'e' || c == 'E')) {
			switch(state) {
			case NSdigit:
			case NSfract:
				state = NSexp;
				continue;
			}
			break;
		}
		break;
	}

	switch(state) {
	/*
	 * result is zero
	 */
	case NSstart:
	case NSsign:
	case NSzero:
	case NSzerofract:
	case NSpoint:
		kp = k->key + k->klen;
		k->klen += 2;
		kp[0] = 0x20;	/* between + and - */
		kp[1] = 0;
		return;
	/*
	 * result has exponent
	 */
	case NSexpsign:
	case NSexp:
	case NSexpdigit:
		if(expsign)
			exp = -exp;
		dp += exp;

	/*
	 * result is fixed point number
	 */
	case NSdigit:
	case NSfract:
		kp -= nzero;
		cl -= nzero;
		break;
	}

	/*
	 * end of number
	 */
	c = 0;
	if(rflag)
		c = ~c;
	*kp = c;

	/*
	 * sign and exponent
	 */
	c = 0x30;
	if(rflag) {
		c = 0x10;
		dp = ~dp;
	}
	kp = k->key + k->klen;
	kp[0] = c;
	kp[1] = (dp >> 8);
	kp[2] = dp;
	k->klen = cl+1;
}

void
dokey_m(Key *k, uchar *lp, uchar *lpe, Field *f)
{
	uchar *kp;
	Rune r, place[3];
	int c, cl, pc;
	int rflag;

	rflag = f->flags&Rflag;
	pc = 0;

	cl = k->klen;
	kp = k->key + cl;

	for(;;) {
		/*
		 * get the character
		 */
		if(lp >= lpe)
			break;
		c = *lp;
		if(c >= Runeself) {
			lp += chartorune(&r, (char*)lp);
			c = r;
		} else
			lp++;

		if(c < nelem(f->mapto)) {
			c = f->mapto[c];
			if(c == 0)
				continue;
		}
		place[pc++] = c;
		if(pc < 3)
			continue;
		for(c=11; c>=0; c--)
			if(memcmp(month[c], place, sizeof(place)) == 0)
				break;
		c += 10;
		if(rflag)
			c = ~c;
		*kp++ = c;
		cl++;
		break;
	}

	c = 0;
	if(rflag)
		c = ~c;
	*kp = c;
	k->klen = cl+1;
}

void
dokey_dfi(Key *k, uchar *lp, uchar *lpe, Field *f)
{
	uchar *kp;
	Rune r;
	int c, cl, n, rflag;

	cl = k->klen;
	kp = k->key + cl;
	rflag = f->flags & Rflag;

	for(;;) {
		/*
		 * get the character
		 */
		if(lp >= lpe)
			break;
		c = *lp;
		if(c >= Runeself) {
			lp += chartorune(&r, (char*)lp);
			c = r;
		} else
			lp++;

		/*
		 * do the various mappings.
		 * the common case is handled
		 * completely by the table.
		 */
		if(c != 0 && c < Runeself) {
			c = f->mapto[c];
			if(c) {
				*kp++ = c;
				cl++;
			}
			continue;
		}

		/*
		 * for characters out of range,
		 * the table does not do Rflag.
		 * ignore is based on mapto[255]
		 */
		if(c != 0 && c < nelem(f->mapto)) {
			c = f->mapto[c];
			if(c == 0)
				continue;
		} else
			if(f->mapto[nelem(f->mapto)-1] == 0)
				continue;

		/*
		 * put it in the key
		 */
		r = c;
		n = runetochar((char*)kp, &r);
		kp += n;
		cl += n;
		if(rflag)
			while(n > 0) {
				kp[-n] = ~kp[-n];
				n--;
			}
	}

	/*
	 * end of key
	 */
	k->klen = cl+1;
	if(rflag) {
		*kp = ~0;
		return;
	}
	*kp = 0;
}

void
dokey_r(Key *k, uchar *lp, uchar *lpe, Field *f)
{
	int cl, n;
	uchar *kp;

	USED(f);
	n = lpe - lp;
	if(n < 0)
		n = 0;
	cl = k->klen;
	kp = k->key + cl;
	k->klen = cl+n+1;

	lpe -= 3;
	while(lp < lpe) {
		kp[0] = ~lp[0];
		kp[1] = ~lp[1];
		kp[2] = ~lp[2];
		kp[3] = ~lp[3];
		kp += 4;
		lp += 4;
	}

	lpe += 3;
	while(lp < lpe)
		*kp++ = ~*lp++;
	*kp = ~0;
}

void
dokey_(Key *k, uchar *lp, uchar *lpe, Field *f)
{
	int n, cl;
	uchar *kp;

	USED(f);
	n = lpe - lp;
	if(n < 0)
		n = 0;
	cl = k->klen;
	kp = k->key + cl;
	k->klen = cl+n+1;
	memmove(kp, lp, n);
	kp[n] = 0;
}

void
buildkey(Line *l)
{
	Key *k;
	uchar *lp, *lpe;
	int ll, kl, cl, i, n;
	Field *f;

	ll = l->llen - 1;
	kl = 0;			/* allocated length */
	cl = 0;			/* current length */
	k = 0;

	for(i=1; i<=args.nfield; i++) {
		f = &args.field[i];
		lp = skip(l->line, f->beg1, f->beg2, f->flags&B1flag, 0);
		if(lp == 0)
			lp = l->line + ll;
		lpe = skip(l->line, f->end1, f->end2, f->flags&Bflag, 1);
		if(lpe == 0)
			lpe = l->line + ll;
		n = (lpe - lp) + 1;
		if(n <= 0)
			n = 1;
		if(cl+(n+4) > kl) {
			kl = cl+(n+4);
			k = realloc(k, sizeof(Key) +
				(kl-1)*sizeof(k->key[0]));
			if(k == 0)
				nomem();
		}
		k->klen = cl;
		(*f->dokey)(k, lp, lpe, f);
		cl = k->klen;
	}

	/*
	 * global comparisons
	 */
	if(!(args.uflag && cl > 0)) {
		f = &args.field[0];
		if(cl+(ll+4) > kl) {
			kl = cl+(ll+4);
			k = realloc(k, sizeof(Key) +
				(kl-1)*sizeof(k->key[0]));
			if(k == 0)
				nomem();
		}
		k->klen = cl;
		(*f->dokey)(k, l->line, l->line+ll, f);
		cl = k->klen;
	}

	l->key = k;
	k->klen = cl;

	if(args.vflag) {
		write(2, l->line, l->llen);
		for(i=0; i<k->klen; i++) {
			fprint(2, " %.2x", k->key[i]);
			if(k->key[i] == 0x00 || k->key[i] == 0xff)
				fprint(2, "\n");
		}
	}
}

void
makemapm(Field *f)
{
	int i, c;

	for(i=0; i<nelem(f->mapto); i++) {
		c = 1;
		if(i == ' ' || i == '\t')
			c = 0;
		if(i >= 'a' && i <= 'z')
			c = i + ('A' - 'a');
		if(i >= 'A' && i <= 'Z')
			c = i;
		f->mapto[i] = c;
		if(args.vflag) {
			if((i & 15) == 0)
				fprint(2, "	");
			fprint(2, " %.2x", c);
			if((i & 15) == 15)
				fprint(2, "\n");
		}
	}
}

void
makemapd(Field *f)
{
	int i, j, c;

	for(i=0; i<nelem(f->mapto); i++) {
		c = i;
		if(f->flags & Iflag)
			if(c < 040 || c > 0176)
				c = -1;
		if((f->flags & Wflag) && c >= 0)
			if(c == ' ' || c == '\t')
				c = -1;
		if((f->flags & Dflag) && c >= 0)
			if(!(c == ' ' || c == '\t' ||
			    (c >= 'a' && c <= 'z') ||
			    (c >= 'A' && c <= 'Z') ||
			    (c >= '0' && c <= '9'))) {
				for(j=0; latinmap[j]; j+=3)
					if(c == latinmap[j+0] ||
					   c == latinmap[j+1])
						break;
				if(latinmap[j] == 0)
					c = -1;
			}
		if((f->flags & Fflag) && c >= 0) {
			if(c >= 'a' && c <= 'z')
				c += 'A' - 'a';
			for(j=0; latinmap[j]; j+=3)
				if(c == latinmap[j+0] ||
				   c == latinmap[j+1]) {
					c = latinmap[j+2];
					break;
				}
		}
		if((f->flags & Rflag) && c >= 0 && i > 0 && i < Runeself)
			c = ~c & 0xff;
		if(c < 0)
			c = 0;
		f->mapto[i] = c;
		if(args.vflag) {
			if((i & 15) == 0)
				fprint(2, "	");
			fprint(2, " %.2x", c);
			if((i & 15) == 15)
				fprint(2, "\n");
		}
	}
}

int	latinmap[] =
{
/*	lcase	ucase	fold	*/
	0xe0,	0xc0,	0x41,		/*	 L'à',	L'À',	L'A',	 */
	0xe1,	0xc1,	0x41,		/*	 L'á',	L'Á',	L'A',	 */
	0xe2,	0xc2,	0x41,		/*	 L'â',	L'Â',	L'A',	 */
	0xe4,	0xc4,	0x41,		/*	 L'ä',	L'Ä',	L'A',	 */
	0xe3,	0xc3,	0x41,		/*	 L'ã',	L'Ã',	L'A',	 */
	0xe5,	0xc5,	0x41,		/*	 L'å',	L'Å',	L'A',	 */
	0xe8,	0xc8,	0x45,		/*	 L'è',	L'È',	L'E',	 */
	0xe9,	0xc9,	0x45,		/*	 L'é',	L'É',	L'E',	 */
	0xea,	0xca,	0x45,		/*	 L'ê',	L'Ê',	L'E',	 */
	0xeb,	0xcb,	0x45,		/*	 L'ë',	L'Ë',	L'E',	 */
	0xec,	0xcc,	0x49,		/*	 L'ì',	L'Ì',	L'I',	 */
	0xed,	0xcd,	0x49,		/*	 L'í',	L'Í',	L'I',	 */
	0xee,	0xce,	0x49,		/*	 L'î',	L'Î',	L'I',	 */
	0xef,	0xcf,	0x49,		/*	 L'ï',	L'Ï',	L'I',	 */
	0xf2,	0xd2,	0x4f,		/*	 L'ò',	L'Ò',	L'O',	 */
	0xf3,	0xd3,	0x4f,		/*	 L'ó',	L'Ó',	L'O',	 */
	0xf4,	0xd4,	0x4f,		/*	 L'ô',	L'Ô',	L'O',	 */
	0xf6,	0xd6,	0x4f,		/*	 L'ö',	L'Ö',	L'O',	 */
	0xf5,	0xd5,	0x4f,		/*	 L'õ',	L'Õ',	L'O',	 */
	0xf8,	0xd8,	0x4f,		/*	 L'ø',	L'Ø',	L'O',	 */
	0xf9,	0xd9,	0x55,		/*	 L'ù',	L'Ù',	L'U',	 */
	0xfa,	0xda,	0x55,		/*	 L'ú',	L'Ú',	L'U',	 */
	0xfb,	0xdb,	0x55,		/*	 L'û',	L'Û',	L'U',	 */
	0xfc,	0xdc,	0x55,		/*	 L'ü',	L'Ü',	L'U',	 */
	0xe6,	0xc6,	0x41,		/*	 L'æ',	L'Æ',	L'A',	 */
	0xf0,	0xd0,	0x44,		/*	 L'ð',	L'Ð',	L'D',	 */
	0xf1,	0xd1,	0x4e,		/*	 L'ñ',	L'Ñ',	L'N',	 */
	0xfd,	0xdd,	0x59,		/*	 L'ý',	L'Ý',	L'Y',	 */
	0xe7,	0xc7,	0x43,		/*	 L'ç',	L'Ç',	L'C',	 */
	0,
};

Rune LJAN[] = { 'J', 'A', 'N', 0 };
Rune LFEB[] = { 'F', 'E', 'B', 0 };
Rune LMAR[] = { 'M', 'A', 'R', 0 };
Rune LAPR[] = { 'A', 'P', 'R', 0 };
Rune LMAY[] = { 'M', 'A', 'Y', 0 };
Rune LJUN[] = { 'J', 'U', 'N', 0 };
Rune LJUL[] = { 'J', 'U', 'L', 0 };
Rune LAUG[] = { 'A', 'U', 'G', 0 };
Rune LSEP[] = { 'S', 'E', 'P', 0 };
Rune LOCT[] = { 'O', 'C', 'T', 0 };
Rune LNOV[] = { 'N', 'O', 'V', 0 };
Rune LDEC[] = { 'D', 'E', 'C', 0 };

Rune*	month[12] =
{
	LJAN,
	LFEB,
	LMAR,
	LAPR,
	LMAY,
	LJUN,
	LJUL,
	LAUG,
	LSEP,
	LOCT,
	LNOV,
	LDEC,
};

/************** radix sort ***********/

enum
{
	Threshold	= 14
};

void	rsort4(Key***, ulong, int);
void	bsort4(Key***, ulong, int);

void
sort4(void *a, ulong n)
{
	if(n > Threshold)
		rsort4((Key***)a, n, 0);
	else
		bsort4((Key***)a, n, 0);
}

void
rsort4(Key ***a, ulong n, int b)
{
	Key ***ea, ***t, ***u, **t1, **u1, *k;
	Key ***part[257];
	static long count[257];
	long clist[257+257], *cp, *cp1;
	int c, lowc, higc;

	/*
	 * pass 1 over all keys,
	 * count the number of each key[b].
	 * find low count and high count.
	 */
	lowc = 256;
	higc = 0;
	ea = a+n;
	for(t=a; t<ea; t++) {
		k = **t;
		n = k->klen;
		if(b >= n) {
			count[256]++;
			continue;
		}
		c = k->key[b];
		n = count[c]++;
		if(n == 0) {
			if(c < lowc)
				lowc = c;
			if(c > higc)
				higc = c;
		}
	}

	/*
	 * pass 2 over all counts,
	 * put partition pointers in part[c].
	 * save compacted indexes and counts
	 * in clist[].
	 */
	t = a;
	n = count[256];
	clist[0] = n;
	part[256] = t;
	t += n;

	cp1 = clist+1;
	cp = count+lowc;
	for(c=lowc; c<=higc; c++,cp++) {
		n = *cp;
		if(n) {
			cp1[0] = n;
			cp1[1] = c;
			cp1 += 2;
			part[c] = t;
			t += n;
		}
	}
	*cp1 = 0;

	/*
	 * pass 3 over all counts.
	 * chase lowest pointer in each partition
	 * around a permutation until it comes
	 * back and is stored where it started.
	 * static array, count[], should be
	 * reduced to zero entries except maybe
	 * count[256].
	 */
	for(cp1=clist+1; cp1[0]; cp1+=2) {
		c = cp1[1];
		cp = count+c;
		while(*cp) {
			t1 = *part[c];
			for(;;) {
				k = *t1;
				n = 256;
				if(b < k->klen)
					n = k->key[b];
				u = part[n]++;
				count[n]--;
				u1 = *u;
				*u = t1;
				if(n == c)
					break;
				t1 = u1;
			}
		}
	}

	/*
	 * pass 4 over all partitions.
	 * call recursively.
	 */
	b++;
	t = a + clist[0];
	count[256] = 0;
	for(cp1=clist+1; n=cp1[0]; cp1+=2) {
		if(n > Threshold)
			rsort4(t, n, b);
		else
		if(n > 1)
			bsort4(t, n, b);
		t += n;
	}
}

/*
 * bubble sort to pick up
 * the pieces.
 */
void
bsort4(Key ***a, ulong n, int b)
{
	Key ***i, ***j, ***k, ***l, **t;
	Key *ka, *kb;
	int n1, n2;

	l = a+n;
	j = a;

loop:
	i = j;
	j++;
	if(j >= l)
		return;

	ka = **i;
	kb = **j;
	n1 = ka->klen - b;
	n2 = kb->klen - b;
	if(n1 > n2)
		n1 = n2;
	if(n1 <= 0)
		goto loop;
	n2 = ka->key[b] - kb->key[b];
	if(n2 == 0)
		n2 = memcmp(ka->key+b, kb->key+b, n1);
	if(n2 <= 0)
		goto loop;

	for(;;) {
		k = i+1;

		t = *k;
		*k = *i;
		*i = t;

		if(i <= a)
			goto loop;

		i--;
		ka = **i;
		kb = *t;
		n1 = ka->klen - b;
		n2 = kb->klen - b;
		if(n1 > n2)
			n1 = n2;
		if(n1 <= 0)
			goto loop;
		n2 = ka->key[b] - kb->key[b];
		if(n2 == 0)
			n2 = memcmp(ka->key+b, kb->key+b, n1);
		if(n2 <= 0)
			goto loop;
	}
}