ref: 3b7e03a30ed29ee0666c00568bf67b8179c28d12
dir: /sys/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 = 100000, /* 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*);
void* emalloc(ulong);
void* erealloc(void*, ulong);
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 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++) {
if((s = argv[i]) == nil)
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(nil);
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(nil);
}
void
dofile(Biobuf *b)
{
Line *l, *ol;
int n;
if(args.cflag) {
if((ol = newline(b)) == nil)
return;
for(;;) {
if((l = newline(b)) == nil)
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 == nil)
args.linep = emalloc(args.mline * sizeof(args.linep));
for(;;) {
if((l = newline(b)) == nil)
break;
if(args.nline >= args.mline)
tempout();
args.linep[args.nline] = l;
args.nline++;
args.lineno++;
}
}
void
notifyf(void*, char *s)
{
if(strcmp(s, "interrupt") == 0)
done(nil);
if(strcmp(s, "hangup") == 0)
done(nil);
if(strcmp(s, "kill") == 0)
done(nil);
if(strncmp(s, "sys: write on closed pipe", 25) == 0)
done(nil);
fprint(2, "sort: note: %s\n", s);
abort();
}
Line*
newline(Biobuf *b)
{
Line *l;
char *p;
int n, c;
p = Brdline(b, '\n');
n = Blinelen(b);
if(p == nil) {
if(n == 0)
return 0;
l = nil;
for(n=0;;) {
if((n & 31) == 0)
l = erealloc(l, sizeof(Line) +
(n+31)*sizeof(l->line[0]));
c = Bgetc(b);
if(c < 0) {
fprint(2, "sort: newline added\n");
c = '\n';
}
if(l == nil)
sysfatal("bug: l == nil");
l->line[n++] = c;
if(c == '\n')
break;
}
l->llen = n;
buildkey(l);
return l;
}
l = emalloc(sizeof(Line) + (n-1)*sizeof(l->line[0]));
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*
erealloc(void *v, ulong n)
{
if((v = realloc(v, n)) == nil && n != 0){
fprint(2, "realloc: %r\n");
done("realloc");
}
return v;
}
void*
emalloc(ulong n)
{
void *v;
if((v = malloc(n)) == nil){
fprint(2, "malloc: %r\n");
done("malloc");
}
memset(v, 0, n);
return v;
}
char*
tempfile(int n)
{
static char file[100];
static uint pid;
char *dir;
dir = "/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;
}
}
snprint(file, sizeof(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 = emalloc(n*sizeof(*mmp));
mp = emalloc(n*sizeof(*mp));
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;
if((l = newline(&m->b)) == nil)
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 == nil) {
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 = nil;
if(*s == 0) {
i++;
if(i < argc) {
p = argv[i];
argv[i] = 0;
}
} else
p = s;
s = strchr(s, 0);
if(p == nil)
break;
newfield();
q = strchr(p, ',');
if(q != nil)
*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 != nil) {
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, ln, tc;
Rune r;
if(endfield && n1 < 0)
return 0;
c = *l++;
ln = 1;
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 += ln = chartorune(&r, (char*)l);
for(i=n1; i>0; i--) {
while(r != tc) {
if(r == '\n')
return 0;
l += ln = chartorune(&r, (char*)l);
}
if(!(endfield && i == 1))
l += ln = 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++;
ln = 1;
}
l -= ln;
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*)
{
int cl, n;
uchar *kp;
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*)
{
int n, cl;
uchar *kp;
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];
if((lp = skip(l->line, f->beg1, f->beg2, f->flags&B1flag, 0)) == nil)
lp = l->line + ll;
if((lpe = skip(l->line, f->end1, f->end2, f->flags&Bflag, 1)) == nil)
lpe = l->line + ll;
n = (lpe - lp) + 1;
if(n <= 0)
n = 1;
if(cl+(n+4) > kl) {
kl = cl+(n+4);
k = erealloc(k, sizeof(Key) +
(kl-1)*sizeof(k->key[0]));
}
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 = erealloc(k, sizeof(Key) +
(kl-1)*sizeof(k->key[0]));
}
k->klen = cl;
(*f->dokey)(k, l->line, l->line+ll, f);
cl = k->klen;
}
l->key = k;
k->klen = cl;
if(args.vflag) {
if(write(2, l->line, l->llen) != l->llen)
exits("write");
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 */
L'à', L'À', L'A',
L'á', L'Á', L'A',
L'â', L'Â', L'A',
L'ä', L'Ä', L'A',
L'ã', L'Ã', L'A',
L'å', L'Å', L'A',
L'è', L'È', L'E',
L'é', L'É', L'E',
L'ê', L'Ê', L'E',
L'ë', L'Ë', L'E',
L'ì', L'Ì', L'I',
L'í', L'Í', L'I',
L'î', L'Î', L'I',
L'ï', L'Ï', L'I',
L'ò', L'Ò', L'O',
L'ó', L'Ó', L'O',
L'ô', L'Ô', L'O',
L'ö', L'Ö', L'O',
L'õ', L'Õ', L'O',
L'ø', L'Ø', L'O',
L'ù', L'Ù', L'U',
L'ú', L'Ú', L'U',
L'û', L'Û', L'U',
L'ü', L'Ü', L'U',
L'æ', L'Æ', L'A',
L'ð', L'Ð', L'D',
L'ñ', L'Ñ', L'N',
L'ý', L'Ý', L'Y',
L'ç', L'Ç', L'C',
0,
};
Rune* month[12] =
{
L"JAN",
L"FEB",
L"MAR",
L"APR",
L"MAY",
L"JUN",
L"JUL",
L"AUG",
L"SEP",
L"OCT",
L"NOV",
L"DEC",
};
/************** 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;
}
}