1 bc7cb1a1 2003-11-23 devnull #include <u.h>
2 bc7cb1a1 2003-11-23 devnull #include <libc.h>
3 bc7cb1a1 2003-11-23 devnull #include <bio.h>
7 bc7cb1a1 2003-11-23 devnull 00/ff for end of file can conflict with 00/ff characters
12 2e49032b 2005-01-18 devnull Nline = 500000, /* default max number of lines saved in memory */
13 bc7cb1a1 2003-11-23 devnull Nmerge = 10, /* max number of temporary files merged */
14 bc7cb1a1 2003-11-23 devnull Nfield = 20, /* max number of argument fields */
16 bc7cb1a1 2003-11-23 devnull Bflag = 1<<0, /* flags per field */
17 bc7cb1a1 2003-11-23 devnull B1flag = 1<<1,
19 bc7cb1a1 2003-11-23 devnull Dflag = 1<<2,
20 bc7cb1a1 2003-11-23 devnull Fflag = 1<<3,
21 bc7cb1a1 2003-11-23 devnull Gflag = 1<<4,
22 bc7cb1a1 2003-11-23 devnull Iflag = 1<<5,
23 bc7cb1a1 2003-11-23 devnull Mflag = 1<<6,
24 bc7cb1a1 2003-11-23 devnull Nflag = 1<<7,
25 bc7cb1a1 2003-11-23 devnull Rflag = 1<<8,
26 bc7cb1a1 2003-11-23 devnull Wflag = 1<<9,
28 bc7cb1a1 2003-11-23 devnull NSstart = 0, /* states for number to key decoding */
34 bc7cb1a1 2003-11-23 devnull NSzerofract,
36 bc7cb1a1 2003-11-23 devnull NSexpsign,
37 cbeb0b26 2006-04-01 devnull NSexpdigit
40 bc7cb1a1 2003-11-23 devnull typedef struct Line Line;
41 bc7cb1a1 2003-11-23 devnull typedef struct Key Key;
42 bc7cb1a1 2003-11-23 devnull typedef struct Merge Merge;
43 bc7cb1a1 2003-11-23 devnull typedef struct Field Field;
45 bc7cb1a1 2003-11-23 devnull struct Line
47 bc7cb1a1 2003-11-23 devnull Key* key;
48 bc7cb1a1 2003-11-23 devnull int llen; /* always >= 1 */
49 bc7cb1a1 2003-11-23 devnull uchar line[1]; /* always ends in '\n' */
52 bc7cb1a1 2003-11-23 devnull struct Merge
54 bc7cb1a1 2003-11-23 devnull Key* key; /* copy of line->key so (Line*) looks like (Merge*) */
55 bc7cb1a1 2003-11-23 devnull Line* line; /* line at the head of a merged temp file */
56 bc7cb1a1 2003-11-23 devnull int fd; /* file descriptor */
57 bc7cb1a1 2003-11-23 devnull Biobuf b; /* iobuf for reading a temp file */
60 bc7cb1a1 2003-11-23 devnull struct Key
62 bc7cb1a1 2003-11-23 devnull int klen;
63 bc7cb1a1 2003-11-23 devnull uchar key[1];
66 bc7cb1a1 2003-11-23 devnull struct Field
68 bc7cb1a1 2003-11-23 devnull int beg1;
69 bc7cb1a1 2003-11-23 devnull int beg2;
70 bc7cb1a1 2003-11-23 devnull int end1;
71 bc7cb1a1 2003-11-23 devnull int end2;
73 bc7cb1a1 2003-11-23 devnull long flags;
74 bc7cb1a1 2003-11-23 devnull uchar mapto[256];
76 bc7cb1a1 2003-11-23 devnull void (*dokey)(Key*, uchar*, uchar*, Field*);
79 bc7cb1a1 2003-11-23 devnull struct args
81 bc7cb1a1 2003-11-23 devnull char* ofile;
82 bc7cb1a1 2003-11-23 devnull char* tname;
83 bc7cb1a1 2003-11-23 devnull Rune tabchar;
84 bc7cb1a1 2003-11-23 devnull char cflag;
85 bc7cb1a1 2003-11-23 devnull char uflag;
86 bc7cb1a1 2003-11-23 devnull char vflag;
87 bc7cb1a1 2003-11-23 devnull int nfield;
88 bc7cb1a1 2003-11-23 devnull int nfile;
89 bc7cb1a1 2003-11-23 devnull Field field[Nfield];
91 bc7cb1a1 2003-11-23 devnull Line** linep;
92 bc7cb1a1 2003-11-23 devnull long nline; /* number of lines in this temp file */
93 bc7cb1a1 2003-11-23 devnull long lineno; /* overall ordinal for -s option */
94 bc7cb1a1 2003-11-23 devnull int ntemp;
95 bc7cb1a1 2003-11-23 devnull long mline; /* max lines per file */
98 bc7cb1a1 2003-11-23 devnull extern int latinmap[];
99 bc7cb1a1 2003-11-23 devnull extern Rune* month[12];
101 bc7cb1a1 2003-11-23 devnull void buildkey(Line*);
102 bc7cb1a1 2003-11-23 devnull void doargs(int, char*[]);
103 bc7cb1a1 2003-11-23 devnull void dofield(char*, int*, int*, int, int);
104 bc7cb1a1 2003-11-23 devnull void dofile(Biobuf*);
105 bc7cb1a1 2003-11-23 devnull void dokey_(Key*, uchar*, uchar*, Field*);
106 bc7cb1a1 2003-11-23 devnull void dokey_dfi(Key*, uchar*, uchar*, Field*);
107 bc7cb1a1 2003-11-23 devnull void dokey_gn(Key*, uchar*, uchar*, Field*);
108 bc7cb1a1 2003-11-23 devnull void dokey_m(Key*, uchar*, uchar*, Field*);
109 bc7cb1a1 2003-11-23 devnull void dokey_r(Key*, uchar*, uchar*, Field*);
110 bc7cb1a1 2003-11-23 devnull void done(char*);
111 bc7cb1a1 2003-11-23 devnull int kcmp(Key*, Key*);
112 bc7cb1a1 2003-11-23 devnull void makemapd(Field*);
113 bc7cb1a1 2003-11-23 devnull void makemapm(Field*);
114 bc7cb1a1 2003-11-23 devnull void mergefiles(int, int, Biobuf*);
115 bc7cb1a1 2003-11-23 devnull void mergeout(Biobuf*);
116 bc7cb1a1 2003-11-23 devnull void newfield(void);
117 bc7cb1a1 2003-11-23 devnull Line* newline(Biobuf*);
118 bc7cb1a1 2003-11-23 devnull void nomem(void);
119 bc7cb1a1 2003-11-23 devnull void notifyf(void*, char*);
120 bc7cb1a1 2003-11-23 devnull void printargs(void);
121 bc7cb1a1 2003-11-23 devnull void printout(Biobuf*);
122 bc7cb1a1 2003-11-23 devnull void setfield(int, int);
123 bc7cb1a1 2003-11-23 devnull uchar* skip(uchar*, int, int, int, int);
124 bc7cb1a1 2003-11-23 devnull void sort4(void*, ulong);
125 bc7cb1a1 2003-11-23 devnull char* tempfile(int);
126 bc7cb1a1 2003-11-23 devnull void tempout(void);
127 bc7cb1a1 2003-11-23 devnull void lineout(Biobuf*, Line*);
130 bc7cb1a1 2003-11-23 devnull main(int argc, char *argv[])
132 bc7cb1a1 2003-11-23 devnull int i, f;
133 bc7cb1a1 2003-11-23 devnull char *s;
134 bc7cb1a1 2003-11-23 devnull Biobuf bbuf;
136 bc7cb1a1 2003-11-23 devnull notify(notifyf); /**/
137 bc7cb1a1 2003-11-23 devnull doargs(argc, argv);
138 bc7cb1a1 2003-11-23 devnull if(args.vflag)
139 bc7cb1a1 2003-11-23 devnull printargs();
141 bc7cb1a1 2003-11-23 devnull for(i=1; i<argc; i++) {
142 bc7cb1a1 2003-11-23 devnull s = argv[i];
143 bc7cb1a1 2003-11-23 devnull if(s == 0)
144 bc7cb1a1 2003-11-23 devnull continue;
145 bc7cb1a1 2003-11-23 devnull if(strcmp(s, "-") == 0) {
146 bc7cb1a1 2003-11-23 devnull Binit(&bbuf, 0, OREAD);
147 bc7cb1a1 2003-11-23 devnull dofile(&bbuf);
148 bc7cb1a1 2003-11-23 devnull Bterm(&bbuf);
149 bc7cb1a1 2003-11-23 devnull continue;
151 bc7cb1a1 2003-11-23 devnull f = open(s, OREAD);
152 bc7cb1a1 2003-11-23 devnull if(f < 0) {
153 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: open %s: %r\n", s);
154 bc7cb1a1 2003-11-23 devnull done("open");
156 bc7cb1a1 2003-11-23 devnull Binit(&bbuf, f, OREAD);
157 bc7cb1a1 2003-11-23 devnull dofile(&bbuf);
158 bc7cb1a1 2003-11-23 devnull Bterm(&bbuf);
159 bc7cb1a1 2003-11-23 devnull close(f);
161 bc7cb1a1 2003-11-23 devnull if(args.nfile == 0) {
162 bc7cb1a1 2003-11-23 devnull Binit(&bbuf, 0, OREAD);
163 bc7cb1a1 2003-11-23 devnull dofile(&bbuf);
164 bc7cb1a1 2003-11-23 devnull Bterm(&bbuf);
166 bc7cb1a1 2003-11-23 devnull if(args.cflag)
167 bc7cb1a1 2003-11-23 devnull done(0);
168 bc7cb1a1 2003-11-23 devnull if(args.vflag)
169 bc7cb1a1 2003-11-23 devnull fprint(2, "=========\n");
172 bc7cb1a1 2003-11-23 devnull if(args.ofile) {
173 bc7cb1a1 2003-11-23 devnull f = create(args.ofile, OWRITE, 0666);
174 bc7cb1a1 2003-11-23 devnull if(f < 0) {
175 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: create %s: %r\n", args.ofile);
176 bc7cb1a1 2003-11-23 devnull done("create");
180 bc7cb1a1 2003-11-23 devnull Binit(&bbuf, f, OWRITE);
181 bc7cb1a1 2003-11-23 devnull if(args.ntemp) {
182 bc7cb1a1 2003-11-23 devnull tempout();
183 bc7cb1a1 2003-11-23 devnull mergeout(&bbuf);
184 bc7cb1a1 2003-11-23 devnull } else {
185 bc7cb1a1 2003-11-23 devnull printout(&bbuf);
187 bc7cb1a1 2003-11-23 devnull Bterm(&bbuf);
188 bc7cb1a1 2003-11-23 devnull done(0);
192 bc7cb1a1 2003-11-23 devnull dofile(Biobuf *b)
194 bc7cb1a1 2003-11-23 devnull Line *l, *ol;
197 bc7cb1a1 2003-11-23 devnull if(args.cflag) {
198 bc7cb1a1 2003-11-23 devnull ol = newline(b);
199 bc7cb1a1 2003-11-23 devnull if(ol == 0)
201 bc7cb1a1 2003-11-23 devnull for(;;) {
202 bc7cb1a1 2003-11-23 devnull l = newline(b);
203 bc7cb1a1 2003-11-23 devnull if(l == 0)
205 bc7cb1a1 2003-11-23 devnull n = kcmp(ol->key, l->key);
206 bc7cb1a1 2003-11-23 devnull if(n > 0 || (n == 0 && args.uflag)) {
207 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: -c file not in sort\n"); /**/
208 bc7cb1a1 2003-11-23 devnull done("order");
210 bc7cb1a1 2003-11-23 devnull free(ol->key);
211 bc7cb1a1 2003-11-23 devnull free(ol);
217 bc7cb1a1 2003-11-23 devnull if(args.linep == 0) {
218 bc7cb1a1 2003-11-23 devnull args.linep = malloc(args.mline * sizeof(args.linep));
219 bc7cb1a1 2003-11-23 devnull if(args.linep == 0)
220 bc7cb1a1 2003-11-23 devnull nomem();
222 bc7cb1a1 2003-11-23 devnull for(;;) {
223 bc7cb1a1 2003-11-23 devnull l = newline(b);
224 bc7cb1a1 2003-11-23 devnull if(l == 0)
226 bc7cb1a1 2003-11-23 devnull if(args.nline >= args.mline)
227 bc7cb1a1 2003-11-23 devnull tempout();
228 bc7cb1a1 2003-11-23 devnull args.linep[args.nline] = l;
229 bc7cb1a1 2003-11-23 devnull args.nline++;
230 bc7cb1a1 2003-11-23 devnull args.lineno++;
235 bc7cb1a1 2003-11-23 devnull notifyf(void *a, char *s)
237 bc7cb1a1 2003-11-23 devnull USED(a);
238 bc7cb1a1 2003-11-23 devnull if(strcmp(s, "interrupt") == 0)
239 bc7cb1a1 2003-11-23 devnull done(0);
240 bc7cb1a1 2003-11-23 devnull if(strcmp(s, "hangup") == 0)
241 bc7cb1a1 2003-11-23 devnull done(0);
242 bc7cb1a1 2003-11-23 devnull if(strcmp(s, "kill") == 0)
243 bc7cb1a1 2003-11-23 devnull done(0);
244 bc7cb1a1 2003-11-23 devnull if(strncmp(s, "sys: write on closed pipe", 25) == 0)
245 bc7cb1a1 2003-11-23 devnull done(0);
246 e22c0f6f 2008-06-01 rsc noted(NDFLT);
250 bc7cb1a1 2003-11-23 devnull newline(Biobuf *b)
252 bc7cb1a1 2003-11-23 devnull Line *l;
253 bc7cb1a1 2003-11-23 devnull char *p;
254 bc7cb1a1 2003-11-23 devnull int n, c;
256 bc7cb1a1 2003-11-23 devnull p = Brdline(b, '\n');
257 bc7cb1a1 2003-11-23 devnull n = Blinelen(b);
258 bc7cb1a1 2003-11-23 devnull if(p == 0) {
259 bc7cb1a1 2003-11-23 devnull if(n == 0)
260 bc7cb1a1 2003-11-23 devnull return 0;
262 bc7cb1a1 2003-11-23 devnull for(n=0;;) {
263 bc7cb1a1 2003-11-23 devnull if((n & 31) == 0) {
264 bc7cb1a1 2003-11-23 devnull l = realloc(l, sizeof(Line) +
265 bc7cb1a1 2003-11-23 devnull (n+31)*sizeof(l->line[0]));
266 bc7cb1a1 2003-11-23 devnull if(l == 0)
267 bc7cb1a1 2003-11-23 devnull nomem();
269 bc7cb1a1 2003-11-23 devnull c = Bgetc(b);
270 bc7cb1a1 2003-11-23 devnull if(c < 0) {
271 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: newline added\n");
272 bc7cb1a1 2003-11-23 devnull c = '\n';
274 bc7cb1a1 2003-11-23 devnull l->line[n++] = c;
275 bc7cb1a1 2003-11-23 devnull if(c == '\n')
278 bc7cb1a1 2003-11-23 devnull l->llen = n;
279 bc7cb1a1 2003-11-23 devnull buildkey(l);
280 bc7cb1a1 2003-11-23 devnull return l;
282 bc7cb1a1 2003-11-23 devnull l = malloc(sizeof(Line) +
283 bc7cb1a1 2003-11-23 devnull (n-1)*sizeof(l->line[0]));
284 bc7cb1a1 2003-11-23 devnull if(l == 0)
285 bc7cb1a1 2003-11-23 devnull nomem();
286 bc7cb1a1 2003-11-23 devnull l->llen = n;
287 bc7cb1a1 2003-11-23 devnull memmove(l->line, p, n);
288 bc7cb1a1 2003-11-23 devnull buildkey(l);
289 bc7cb1a1 2003-11-23 devnull return l;
293 bc7cb1a1 2003-11-23 devnull lineout(Biobuf *b, Line *l)
295 bc7cb1a1 2003-11-23 devnull int n, m;
297 bc7cb1a1 2003-11-23 devnull n = l->llen;
298 bc7cb1a1 2003-11-23 devnull m = Bwrite(b, l->line, n);
299 bc7cb1a1 2003-11-23 devnull if(n != m)
300 bc7cb1a1 2003-11-23 devnull exits("write");
304 bc7cb1a1 2003-11-23 devnull tempout(void)
307 bc7cb1a1 2003-11-23 devnull Line **lp, *l;
308 bc7cb1a1 2003-11-23 devnull char *tf;
310 bc7cb1a1 2003-11-23 devnull Biobuf tb;
312 bc7cb1a1 2003-11-23 devnull sort4(args.linep, args.nline);
313 bc7cb1a1 2003-11-23 devnull tf = tempfile(args.ntemp);
314 bc7cb1a1 2003-11-23 devnull args.ntemp++;
315 bc7cb1a1 2003-11-23 devnull f = create(tf, OWRITE, 0666);
316 bc7cb1a1 2003-11-23 devnull if(f < 0) {
317 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: create %s: %r\n", tf);
318 bc7cb1a1 2003-11-23 devnull done("create");
321 bc7cb1a1 2003-11-23 devnull Binit(&tb, f, OWRITE);
322 bc7cb1a1 2003-11-23 devnull lp = args.linep;
323 bc7cb1a1 2003-11-23 devnull for(n=args.nline; n>0; n--) {
324 bc7cb1a1 2003-11-23 devnull l = *lp++;
325 bc7cb1a1 2003-11-23 devnull lineout(&tb, l);
326 bc7cb1a1 2003-11-23 devnull free(l->key);
327 bc7cb1a1 2003-11-23 devnull free(l);
329 bc7cb1a1 2003-11-23 devnull args.nline = 0;
330 bc7cb1a1 2003-11-23 devnull Bterm(&tb);
331 bc7cb1a1 2003-11-23 devnull close(f);
335 bc7cb1a1 2003-11-23 devnull done(char *xs)
339 bc7cb1a1 2003-11-23 devnull for(i=0; i<args.ntemp; i++)
340 bc7cb1a1 2003-11-23 devnull remove(tempfile(i));
341 bc7cb1a1 2003-11-23 devnull exits(xs);
345 bc7cb1a1 2003-11-23 devnull nomem(void)
347 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: out of memory\n");
348 bc7cb1a1 2003-11-23 devnull done("mem");
352 bc7cb1a1 2003-11-23 devnull tempfile(int n)
354 bc7cb1a1 2003-11-23 devnull static char file[100];
355 bc7cb1a1 2003-11-23 devnull static uint pid;
356 bc7cb1a1 2003-11-23 devnull char *dir;
358 c8b6342d 2005-01-13 devnull dir = "/var/tmp";
359 bc7cb1a1 2003-11-23 devnull if(args.tname)
360 bc7cb1a1 2003-11-23 devnull dir = args.tname;
361 bc7cb1a1 2003-11-23 devnull if(strlen(dir) >= nelem(file)-20) {
362 bc7cb1a1 2003-11-23 devnull fprint(2, "temp file directory name is too long: %s\n", dir);
363 bc7cb1a1 2003-11-23 devnull done("tdir");
366 bc7cb1a1 2003-11-23 devnull if(pid == 0) {
367 bc7cb1a1 2003-11-23 devnull pid = getpid();
368 bc7cb1a1 2003-11-23 devnull if(pid == 0) {
369 bc7cb1a1 2003-11-23 devnull pid = time(0);
370 bc7cb1a1 2003-11-23 devnull if(pid == 0)
371 bc7cb1a1 2003-11-23 devnull pid = 1;
375 bc7cb1a1 2003-11-23 devnull sprint(file, "%s/sort.%.4d.%.4d", dir, pid%10000, n);
376 bc7cb1a1 2003-11-23 devnull return file;
380 bc7cb1a1 2003-11-23 devnull mergeout(Biobuf *b)
382 bc7cb1a1 2003-11-23 devnull int n, i, f;
383 bc7cb1a1 2003-11-23 devnull char *tf;
384 bc7cb1a1 2003-11-23 devnull Biobuf tb;
386 bc7cb1a1 2003-11-23 devnull for(i=0; i<args.ntemp; i+=n) {
387 bc7cb1a1 2003-11-23 devnull n = args.ntemp - i;
388 bc7cb1a1 2003-11-23 devnull if(n > Nmerge) {
389 bc7cb1a1 2003-11-23 devnull tf = tempfile(args.ntemp);
390 bc7cb1a1 2003-11-23 devnull args.ntemp++;
391 bc7cb1a1 2003-11-23 devnull f = create(tf, OWRITE, 0666);
392 bc7cb1a1 2003-11-23 devnull if(f < 0) {
393 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: create %s: %r\n", tf);
394 bc7cb1a1 2003-11-23 devnull done("create");
396 bc7cb1a1 2003-11-23 devnull Binit(&tb, f, OWRITE);
398 bc7cb1a1 2003-11-23 devnull n = Nmerge;
399 bc7cb1a1 2003-11-23 devnull mergefiles(i, n, &tb);
401 bc7cb1a1 2003-11-23 devnull Bterm(&tb);
402 bc7cb1a1 2003-11-23 devnull close(f);
404 bc7cb1a1 2003-11-23 devnull mergefiles(i, n, b);
409 bc7cb1a1 2003-11-23 devnull mergefiles(int t, int n, Biobuf *b)
411 bc7cb1a1 2003-11-23 devnull Merge *m, *mp, **mmp;
412 bc7cb1a1 2003-11-23 devnull Key *ok;
413 bc7cb1a1 2003-11-23 devnull Line *l;
414 bc7cb1a1 2003-11-23 devnull char *tf;
415 bc7cb1a1 2003-11-23 devnull int i, f, nn;
417 bc7cb1a1 2003-11-23 devnull mmp = malloc(n*sizeof(*mmp));
418 bc7cb1a1 2003-11-23 devnull mp = malloc(n*sizeof(*mp));
419 bc7cb1a1 2003-11-23 devnull if(mmp == 0 || mp == 0)
420 bc7cb1a1 2003-11-23 devnull nomem();
424 bc7cb1a1 2003-11-23 devnull for(i=0; i<n; i++,m++) {
425 bc7cb1a1 2003-11-23 devnull tf = tempfile(t+i);
426 bc7cb1a1 2003-11-23 devnull f = open(tf, OREAD);
427 bc7cb1a1 2003-11-23 devnull if(f < 0) {
428 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: reopen %s: %r\n", tf);
429 bc7cb1a1 2003-11-23 devnull done("open");
431 bc7cb1a1 2003-11-23 devnull m->fd = f;
432 bc7cb1a1 2003-11-23 devnull Binit(&m->b, f, OREAD);
433 bc7cb1a1 2003-11-23 devnull mmp[nn] = m;
435 bc7cb1a1 2003-11-23 devnull l = newline(&m->b);
436 bc7cb1a1 2003-11-23 devnull if(l == 0)
437 bc7cb1a1 2003-11-23 devnull continue;
439 bc7cb1a1 2003-11-23 devnull m->line = l;
440 bc7cb1a1 2003-11-23 devnull m->key = l->key;
444 bc7cb1a1 2003-11-23 devnull for(;;) {
445 bc7cb1a1 2003-11-23 devnull sort4(mmp, nn);
446 bc7cb1a1 2003-11-23 devnull m = *mmp;
447 bc7cb1a1 2003-11-23 devnull if(nn == 0)
449 bc7cb1a1 2003-11-23 devnull for(;;) {
450 bc7cb1a1 2003-11-23 devnull l = m->line;
451 bc7cb1a1 2003-11-23 devnull if(args.uflag && ok && kcmp(ok, l->key) == 0) {
452 bc7cb1a1 2003-11-23 devnull free(l->key);
453 bc7cb1a1 2003-11-23 devnull free(l);
454 bc7cb1a1 2003-11-23 devnull } else {
455 bc7cb1a1 2003-11-23 devnull lineout(b, l);
457 bc7cb1a1 2003-11-23 devnull free(ok);
458 bc7cb1a1 2003-11-23 devnull ok = l->key;
459 bc7cb1a1 2003-11-23 devnull free(l);
462 bc7cb1a1 2003-11-23 devnull l = newline(&m->b);
463 bc7cb1a1 2003-11-23 devnull if(l == 0) {
465 bc7cb1a1 2003-11-23 devnull mmp[0] = mmp[nn];
468 bc7cb1a1 2003-11-23 devnull m->line = l;
469 bc7cb1a1 2003-11-23 devnull m->key = l->key;
470 bc7cb1a1 2003-11-23 devnull if(nn > 1 && kcmp(mmp[0]->key, mmp[1]->key) > 0)
475 bc7cb1a1 2003-11-23 devnull free(ok);
478 bc7cb1a1 2003-11-23 devnull for(i=0; i<n; i++,m++) {
479 bc7cb1a1 2003-11-23 devnull Bterm(&m->b);
480 bc7cb1a1 2003-11-23 devnull close(m->fd);
483 bc7cb1a1 2003-11-23 devnull free(mp);
484 bc7cb1a1 2003-11-23 devnull free(mmp);
488 bc7cb1a1 2003-11-23 devnull kcmp(Key *ka, Key *kb)
490 bc7cb1a1 2003-11-23 devnull int n, m;
493 bc7cb1a1 2003-11-23 devnull * set n to length of smaller key
495 bc7cb1a1 2003-11-23 devnull n = ka->klen;
496 bc7cb1a1 2003-11-23 devnull m = kb->klen;
497 bc7cb1a1 2003-11-23 devnull if(n > m)
499 bc7cb1a1 2003-11-23 devnull return memcmp(ka->key, kb->key, n);
503 bc7cb1a1 2003-11-23 devnull printout(Biobuf *b)
506 bc7cb1a1 2003-11-23 devnull Line **lp, *l;
507 bc7cb1a1 2003-11-23 devnull Key *ok;
509 bc7cb1a1 2003-11-23 devnull sort4(args.linep, args.nline);
510 bc7cb1a1 2003-11-23 devnull lp = args.linep;
512 bc7cb1a1 2003-11-23 devnull for(n=args.nline; n>0; n--) {
513 bc7cb1a1 2003-11-23 devnull l = *lp++;
514 bc7cb1a1 2003-11-23 devnull if(args.uflag && ok && kcmp(ok, l->key) == 0)
515 bc7cb1a1 2003-11-23 devnull continue;
516 bc7cb1a1 2003-11-23 devnull lineout(b, l);
517 bc7cb1a1 2003-11-23 devnull ok = l->key;
522 bc7cb1a1 2003-11-23 devnull setfield(int n, int c)
524 bc7cb1a1 2003-11-23 devnull Field *f;
526 bc7cb1a1 2003-11-23 devnull f = &args.field[n];
527 bc7cb1a1 2003-11-23 devnull switch(c) {
528 bc7cb1a1 2003-11-23 devnull default:
529 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: unknown option: field.%C\n", c);
530 bc7cb1a1 2003-11-23 devnull done("option");
531 bc7cb1a1 2003-11-23 devnull case 'b': /* skip blanks */
532 bc7cb1a1 2003-11-23 devnull f->flags |= Bflag;
534 bc7cb1a1 2003-11-23 devnull case 'd': /* directory order */
535 bc7cb1a1 2003-11-23 devnull f->flags |= Dflag;
537 bc7cb1a1 2003-11-23 devnull case 'f': /* fold case */
538 bc7cb1a1 2003-11-23 devnull f->flags |= Fflag;
540 bc7cb1a1 2003-11-23 devnull case 'g': /* floating point -n case */
541 bc7cb1a1 2003-11-23 devnull f->flags |= Gflag;
543 bc7cb1a1 2003-11-23 devnull case 'i': /* ignore non-ascii */
544 bc7cb1a1 2003-11-23 devnull f->flags |= Iflag;
546 bc7cb1a1 2003-11-23 devnull case 'M': /* month */
547 bc7cb1a1 2003-11-23 devnull f->flags |= Mflag;
549 bc7cb1a1 2003-11-23 devnull case 'n': /* numbers */
550 bc7cb1a1 2003-11-23 devnull f->flags |= Nflag;
552 bc7cb1a1 2003-11-23 devnull case 'r': /* reverse */
553 bc7cb1a1 2003-11-23 devnull f->flags |= Rflag;
555 bc7cb1a1 2003-11-23 devnull case 'w': /* ignore white */
556 bc7cb1a1 2003-11-23 devnull f->flags |= Wflag;
562 bc7cb1a1 2003-11-23 devnull dofield(char *s, int *n1, int *n2, int off1, int off2)
564 bc7cb1a1 2003-11-23 devnull int c, n;
566 bc7cb1a1 2003-11-23 devnull c = *s++;
567 bc7cb1a1 2003-11-23 devnull if(c >= '0' && c <= '9') {
569 bc7cb1a1 2003-11-23 devnull while(c >= '0' && c <= '9') {
570 bc7cb1a1 2003-11-23 devnull n = n*10 + (c-'0');
571 bc7cb1a1 2003-11-23 devnull c = *s++;
573 bc7cb1a1 2003-11-23 devnull n -= off1; /* posix committee: rot in hell */
574 bc7cb1a1 2003-11-23 devnull if(n < 0) {
575 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: field offset must be positive\n");
576 bc7cb1a1 2003-11-23 devnull done("option");
578 bc7cb1a1 2003-11-23 devnull *n1 = n;
580 bc7cb1a1 2003-11-23 devnull if(c == '.') {
581 bc7cb1a1 2003-11-23 devnull c = *s++;
582 bc7cb1a1 2003-11-23 devnull if(c >= '0' && c <= '9') {
584 bc7cb1a1 2003-11-23 devnull while(c >= '0' && c <= '9') {
585 bc7cb1a1 2003-11-23 devnull n = n*10 + (c-'0');
586 bc7cb1a1 2003-11-23 devnull c = *s++;
588 bc7cb1a1 2003-11-23 devnull n -= off2;
589 bc7cb1a1 2003-11-23 devnull if(n < 0) {
590 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: character offset must be positive\n");
591 bc7cb1a1 2003-11-23 devnull done("option");
593 bc7cb1a1 2003-11-23 devnull *n2 = n;
596 bc7cb1a1 2003-11-23 devnull while(c != 0) {
597 bc7cb1a1 2003-11-23 devnull setfield(args.nfield, c);
598 bc7cb1a1 2003-11-23 devnull c = *s++;
603 bc7cb1a1 2003-11-23 devnull printargs(void)
605 bc7cb1a1 2003-11-23 devnull int i, n;
606 bc7cb1a1 2003-11-23 devnull Field *f;
607 bc7cb1a1 2003-11-23 devnull char *prefix;
609 bc7cb1a1 2003-11-23 devnull fprint(2, "sort");
610 bc7cb1a1 2003-11-23 devnull for(i=0; i<=args.nfield; i++) {
611 bc7cb1a1 2003-11-23 devnull f = &args.field[i];
612 bc7cb1a1 2003-11-23 devnull prefix = " -";
614 bc7cb1a1 2003-11-23 devnull n = f->beg1;
615 bc7cb1a1 2003-11-23 devnull if(n >= 0)
616 bc7cb1a1 2003-11-23 devnull fprint(2, " +%d", n);
618 bc7cb1a1 2003-11-23 devnull fprint(2, " +*");
619 bc7cb1a1 2003-11-23 devnull n = f->beg2;
620 bc7cb1a1 2003-11-23 devnull if(n >= 0)
621 bc7cb1a1 2003-11-23 devnull fprint(2, ".%d", n);
623 bc7cb1a1 2003-11-23 devnull fprint(2, ".*");
625 bc7cb1a1 2003-11-23 devnull if(f->flags & B1flag)
626 bc7cb1a1 2003-11-23 devnull fprint(2, "b");
628 bc7cb1a1 2003-11-23 devnull n = f->end1;
629 bc7cb1a1 2003-11-23 devnull if(n >= 0)
630 bc7cb1a1 2003-11-23 devnull fprint(2, " -%d", n);
632 bc7cb1a1 2003-11-23 devnull fprint(2, " -*");
633 bc7cb1a1 2003-11-23 devnull n = f->end2;
634 bc7cb1a1 2003-11-23 devnull if(n >= 0)
635 bc7cb1a1 2003-11-23 devnull fprint(2, ".%d", n);
637 bc7cb1a1 2003-11-23 devnull fprint(2, ".*");
638 bc7cb1a1 2003-11-23 devnull prefix = "";
640 bc7cb1a1 2003-11-23 devnull if(f->flags & Bflag)
641 bc7cb1a1 2003-11-23 devnull fprint(2, "%sb", prefix);
642 bc7cb1a1 2003-11-23 devnull if(f->flags & Dflag)
643 bc7cb1a1 2003-11-23 devnull fprint(2, "%sd", prefix);
644 bc7cb1a1 2003-11-23 devnull if(f->flags & Fflag)
645 bc7cb1a1 2003-11-23 devnull fprint(2, "%sf", prefix);
646 bc7cb1a1 2003-11-23 devnull if(f->flags & Gflag)
647 bc7cb1a1 2003-11-23 devnull fprint(2, "%sg", prefix);
648 bc7cb1a1 2003-11-23 devnull if(f->flags & Iflag)
649 bc7cb1a1 2003-11-23 devnull fprint(2, "%si", prefix);
650 bc7cb1a1 2003-11-23 devnull if(f->flags & Mflag)
651 bc7cb1a1 2003-11-23 devnull fprint(2, "%sM", prefix);
652 bc7cb1a1 2003-11-23 devnull if(f->flags & Nflag)
653 bc7cb1a1 2003-11-23 devnull fprint(2, "%sn", prefix);
654 bc7cb1a1 2003-11-23 devnull if(f->flags & Rflag)
655 bc7cb1a1 2003-11-23 devnull fprint(2, "%sr", prefix);
656 bc7cb1a1 2003-11-23 devnull if(f->flags & Wflag)
657 bc7cb1a1 2003-11-23 devnull fprint(2, "%sw", prefix);
659 bc7cb1a1 2003-11-23 devnull if(args.cflag)
660 bc7cb1a1 2003-11-23 devnull fprint(2, " -c");
661 bc7cb1a1 2003-11-23 devnull if(args.uflag)
662 bc7cb1a1 2003-11-23 devnull fprint(2, " -u");
663 bc7cb1a1 2003-11-23 devnull if(args.ofile)
664 bc7cb1a1 2003-11-23 devnull fprint(2, " -o %s", args.ofile);
665 bc7cb1a1 2003-11-23 devnull if(args.mline != Nline)
666 bc7cb1a1 2003-11-23 devnull fprint(2, " -l %ld", args.mline);
667 bc7cb1a1 2003-11-23 devnull fprint(2, "\n");
671 bc7cb1a1 2003-11-23 devnull newfield(void)
674 bc7cb1a1 2003-11-23 devnull Field *f;
676 bc7cb1a1 2003-11-23 devnull n = args.nfield + 1;
677 bc7cb1a1 2003-11-23 devnull if(n >= Nfield) {
678 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: too many fields specified\n");
679 bc7cb1a1 2003-11-23 devnull done("option");
681 bc7cb1a1 2003-11-23 devnull args.nfield = n;
682 bc7cb1a1 2003-11-23 devnull f = &args.field[n];
683 bc7cb1a1 2003-11-23 devnull f->beg1 = -1;
684 bc7cb1a1 2003-11-23 devnull f->beg2 = -1;
685 bc7cb1a1 2003-11-23 devnull f->end1 = -1;
686 bc7cb1a1 2003-11-23 devnull f->end2 = -1;
690 bc7cb1a1 2003-11-23 devnull doargs(int argc, char *argv[])
692 bc7cb1a1 2003-11-23 devnull int i, c, hadplus;
693 bc7cb1a1 2003-11-23 devnull char *s, *p, *q;
694 bc7cb1a1 2003-11-23 devnull Field *f;
696 bc7cb1a1 2003-11-23 devnull hadplus = 0;
697 bc7cb1a1 2003-11-23 devnull args.mline = Nline;
698 bc7cb1a1 2003-11-23 devnull for(i=1; i<argc; i++) {
699 bc7cb1a1 2003-11-23 devnull s = argv[i];
700 bc7cb1a1 2003-11-23 devnull c = *s++;
701 bc7cb1a1 2003-11-23 devnull if(c == '-') {
703 bc7cb1a1 2003-11-23 devnull if(c == 0) /* forced end of arg marker */
705 bc7cb1a1 2003-11-23 devnull argv[i] = 0; /* clobber args processed */
706 bc7cb1a1 2003-11-23 devnull if(c == '.' || (c >= '0' && c <= '9')) {
707 bc7cb1a1 2003-11-23 devnull if(!hadplus)
708 bc7cb1a1 2003-11-23 devnull newfield();
709 bc7cb1a1 2003-11-23 devnull f = &args.field[args.nfield];
710 bc7cb1a1 2003-11-23 devnull dofield(s, &f->end1, &f->end2, 0, 0);
711 bc7cb1a1 2003-11-23 devnull hadplus = 0;
712 bc7cb1a1 2003-11-23 devnull continue;
715 bc7cb1a1 2003-11-23 devnull while(c = *s++)
716 bc7cb1a1 2003-11-23 devnull switch(c) {
717 bc7cb1a1 2003-11-23 devnull case '-': /* end of options */
718 bc7cb1a1 2003-11-23 devnull i = argc;
719 bc7cb1a1 2003-11-23 devnull continue;
720 bc7cb1a1 2003-11-23 devnull case 'T': /* temp directory */
721 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
723 bc7cb1a1 2003-11-23 devnull if(i < argc) {
724 bc7cb1a1 2003-11-23 devnull args.tname = argv[i];
725 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
728 bc7cb1a1 2003-11-23 devnull args.tname = s;
729 bc7cb1a1 2003-11-23 devnull s = strchr(s, 0);
731 bc7cb1a1 2003-11-23 devnull case 'o': /* output file */
732 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
734 bc7cb1a1 2003-11-23 devnull if(i < argc) {
735 bc7cb1a1 2003-11-23 devnull args.ofile = argv[i];
736 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
739 bc7cb1a1 2003-11-23 devnull args.ofile = s;
740 bc7cb1a1 2003-11-23 devnull s = strchr(s, 0);
742 bc7cb1a1 2003-11-23 devnull case 'k': /* posix key (what were they thinking?) */
744 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
746 bc7cb1a1 2003-11-23 devnull if(i < argc) {
747 bc7cb1a1 2003-11-23 devnull p = argv[i];
748 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
752 bc7cb1a1 2003-11-23 devnull s = strchr(s, 0);
753 bc7cb1a1 2003-11-23 devnull if(p == 0)
756 bc7cb1a1 2003-11-23 devnull newfield();
757 bc7cb1a1 2003-11-23 devnull q = strchr(p, ',');
759 bc7cb1a1 2003-11-23 devnull *q++ = 0;
760 bc7cb1a1 2003-11-23 devnull f = &args.field[args.nfield];
761 bc7cb1a1 2003-11-23 devnull dofield(p, &f->beg1, &f->beg2, 1, 1);
762 bc7cb1a1 2003-11-23 devnull if(f->flags & Bflag) {
763 bc7cb1a1 2003-11-23 devnull f->flags |= B1flag;
764 bc7cb1a1 2003-11-23 devnull f->flags &= ~Bflag;
767 bc7cb1a1 2003-11-23 devnull dofield(q, &f->end1, &f->end2, 1, 0);
768 bc7cb1a1 2003-11-23 devnull if(f->end2 <= 0)
769 bc7cb1a1 2003-11-23 devnull f->end1++;
771 bc7cb1a1 2003-11-23 devnull hadplus = 0;
773 bc7cb1a1 2003-11-23 devnull case 't': /* tab character */
774 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
776 bc7cb1a1 2003-11-23 devnull if(i < argc) {
777 bc7cb1a1 2003-11-23 devnull chartorune(&args.tabchar, argv[i]);
778 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
781 bc7cb1a1 2003-11-23 devnull s += chartorune(&args.tabchar, s);
782 bc7cb1a1 2003-11-23 devnull if(args.tabchar == '\n') {
783 bc7cb1a1 2003-11-23 devnull fprint(2, "aw come on, rob\n");
784 bc7cb1a1 2003-11-23 devnull done("rob");
787 bc7cb1a1 2003-11-23 devnull case 'c': /* check order */
788 bc7cb1a1 2003-11-23 devnull args.cflag = 1;
790 bc7cb1a1 2003-11-23 devnull case 'u': /* unique */
791 bc7cb1a1 2003-11-23 devnull args.uflag = 1;
793 bc7cb1a1 2003-11-23 devnull case 'v': /* debugging noise */
794 bc7cb1a1 2003-11-23 devnull args.vflag = 1;
796 bc7cb1a1 2003-11-23 devnull case 'l':
797 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
799 bc7cb1a1 2003-11-23 devnull if(i < argc) {
800 bc7cb1a1 2003-11-23 devnull args.mline = atol(argv[i]);
801 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
804 bc7cb1a1 2003-11-23 devnull args.mline = atol(s);
805 bc7cb1a1 2003-11-23 devnull s = strchr(s, 0);
808 bc7cb1a1 2003-11-23 devnull case 'M': /* month */
809 bc7cb1a1 2003-11-23 devnull case 'b': /* skip blanks */
810 bc7cb1a1 2003-11-23 devnull case 'd': /* directory order */
811 bc7cb1a1 2003-11-23 devnull case 'f': /* fold case */
812 bc7cb1a1 2003-11-23 devnull case 'g': /* floating numbers */
813 bc7cb1a1 2003-11-23 devnull case 'i': /* ignore non-ascii */
814 bc7cb1a1 2003-11-23 devnull case 'n': /* numbers */
815 bc7cb1a1 2003-11-23 devnull case 'r': /* reverse */
816 bc7cb1a1 2003-11-23 devnull case 'w': /* ignore white */
817 bc7cb1a1 2003-11-23 devnull if(args.nfield > 0)
818 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: global field set after -k\n");
819 bc7cb1a1 2003-11-23 devnull setfield(0, c);
821 bc7cb1a1 2003-11-23 devnull case 'm':
822 bc7cb1a1 2003-11-23 devnull /* option m silently ignored but required by posix */
824 bc7cb1a1 2003-11-23 devnull default:
825 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: unknown option: -%C\n", c);
826 bc7cb1a1 2003-11-23 devnull done("option");
828 bc7cb1a1 2003-11-23 devnull continue;
830 bc7cb1a1 2003-11-23 devnull if(c == '+') {
831 bc7cb1a1 2003-11-23 devnull argv[i] = 0; /* clobber args processed */
833 bc7cb1a1 2003-11-23 devnull if(c == '.' || (c >= '0' && c <= '9')) {
834 bc7cb1a1 2003-11-23 devnull newfield();
835 bc7cb1a1 2003-11-23 devnull f = &args.field[args.nfield];
836 bc7cb1a1 2003-11-23 devnull dofield(s, &f->beg1, &f->beg2, 0, 0);
837 bc7cb1a1 2003-11-23 devnull if(f->flags & Bflag) {
838 bc7cb1a1 2003-11-23 devnull f->flags |= B1flag;
839 bc7cb1a1 2003-11-23 devnull f->flags &= ~Bflag;
841 bc7cb1a1 2003-11-23 devnull hadplus = 1;
842 bc7cb1a1 2003-11-23 devnull continue;
844 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: unknown option: +%C\n", c);
845 bc7cb1a1 2003-11-23 devnull done("option");
847 bc7cb1a1 2003-11-23 devnull args.nfile++;
850 bc7cb1a1 2003-11-23 devnull for(i=0; i<=args.nfield; i++) {
851 bc7cb1a1 2003-11-23 devnull f = &args.field[i];
854 bc7cb1a1 2003-11-23 devnull * global options apply to fields that
855 bc7cb1a1 2003-11-23 devnull * specify no options
857 bc7cb1a1 2003-11-23 devnull if(f->flags == 0) {
858 bc7cb1a1 2003-11-23 devnull f->flags = args.field[0].flags;
859 bc7cb1a1 2003-11-23 devnull if(args.field[0].flags & Bflag)
860 bc7cb1a1 2003-11-23 devnull f->flags |= B1flag;
865 bc7cb1a1 2003-11-23 devnull * build buildkey specification
867 bc7cb1a1 2003-11-23 devnull switch(f->flags & ~(Bflag|B1flag)) {
868 bc7cb1a1 2003-11-23 devnull default:
869 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: illegal combination of flags: %lx\n", f->flags);
870 bc7cb1a1 2003-11-23 devnull done("option");
872 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_;
874 bc7cb1a1 2003-11-23 devnull case Rflag:
875 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_r;
877 bc7cb1a1 2003-11-23 devnull case Gflag:
878 bc7cb1a1 2003-11-23 devnull case Nflag:
879 bc7cb1a1 2003-11-23 devnull case Gflag|Nflag:
880 bc7cb1a1 2003-11-23 devnull case Gflag|Rflag:
881 bc7cb1a1 2003-11-23 devnull case Nflag|Rflag:
882 bc7cb1a1 2003-11-23 devnull case Gflag|Nflag|Rflag:
883 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_gn;
885 bc7cb1a1 2003-11-23 devnull case Mflag:
886 bc7cb1a1 2003-11-23 devnull case Mflag|Rflag:
887 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_m;
888 bc7cb1a1 2003-11-23 devnull makemapm(f);
890 bc7cb1a1 2003-11-23 devnull case Dflag:
891 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag:
892 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Iflag:
893 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Iflag|Rflag:
894 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Iflag|Rflag|Wflag:
895 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Iflag|Wflag:
896 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Rflag:
897 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Rflag|Wflag:
898 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Wflag:
899 bc7cb1a1 2003-11-23 devnull case Dflag|Iflag:
900 bc7cb1a1 2003-11-23 devnull case Dflag|Iflag|Rflag:
901 bc7cb1a1 2003-11-23 devnull case Dflag|Iflag|Rflag|Wflag:
902 bc7cb1a1 2003-11-23 devnull case Dflag|Iflag|Wflag:
903 bc7cb1a1 2003-11-23 devnull case Dflag|Rflag:
904 bc7cb1a1 2003-11-23 devnull case Dflag|Rflag|Wflag:
905 bc7cb1a1 2003-11-23 devnull case Dflag|Wflag:
906 bc7cb1a1 2003-11-23 devnull case Fflag:
907 bc7cb1a1 2003-11-23 devnull case Fflag|Iflag:
908 bc7cb1a1 2003-11-23 devnull case Fflag|Iflag|Rflag:
909 bc7cb1a1 2003-11-23 devnull case Fflag|Iflag|Rflag|Wflag:
910 bc7cb1a1 2003-11-23 devnull case Fflag|Iflag|Wflag:
911 bc7cb1a1 2003-11-23 devnull case Fflag|Rflag:
912 bc7cb1a1 2003-11-23 devnull case Fflag|Rflag|Wflag:
913 bc7cb1a1 2003-11-23 devnull case Fflag|Wflag:
914 bc7cb1a1 2003-11-23 devnull case Iflag:
915 bc7cb1a1 2003-11-23 devnull case Iflag|Rflag:
916 bc7cb1a1 2003-11-23 devnull case Iflag|Rflag|Wflag:
917 bc7cb1a1 2003-11-23 devnull case Iflag|Wflag:
918 bc7cb1a1 2003-11-23 devnull case Wflag:
919 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_dfi;
920 bc7cb1a1 2003-11-23 devnull makemapd(f);
926 bc7cb1a1 2003-11-23 devnull * random spot checks
928 bc7cb1a1 2003-11-23 devnull if(args.nfile > 1 && args.cflag) {
929 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: -c can have at most one input file\n");
930 bc7cb1a1 2003-11-23 devnull done("option");
936 bc7cb1a1 2003-11-23 devnull skip(uchar *l, int n1, int n2, int bflag, int endfield)
938 bc7cb1a1 2003-11-23 devnull int i, c, tc;
941 bc7cb1a1 2003-11-23 devnull if(endfield && n1 < 0)
942 bc7cb1a1 2003-11-23 devnull return 0;
944 bc7cb1a1 2003-11-23 devnull c = *l++;
945 bc7cb1a1 2003-11-23 devnull tc = args.tabchar;
946 bc7cb1a1 2003-11-23 devnull if(tc) {
947 bc7cb1a1 2003-11-23 devnull if(tc < Runeself) {
948 bc7cb1a1 2003-11-23 devnull for(i=n1; i>0; i--) {
949 bc7cb1a1 2003-11-23 devnull while(c != tc) {
950 bc7cb1a1 2003-11-23 devnull if(c == '\n')
951 bc7cb1a1 2003-11-23 devnull return 0;
952 bc7cb1a1 2003-11-23 devnull c = *l++;
954 bc7cb1a1 2003-11-23 devnull if(!(endfield && i == 1))
955 bc7cb1a1 2003-11-23 devnull c = *l++;
957 bc7cb1a1 2003-11-23 devnull } else {
959 bc7cb1a1 2003-11-23 devnull l += chartorune(&r, (char*)l);
960 bc7cb1a1 2003-11-23 devnull for(i=n1; i>0; i--) {
961 bc7cb1a1 2003-11-23 devnull while(r != tc) {
962 bc7cb1a1 2003-11-23 devnull if(r == '\n')
963 bc7cb1a1 2003-11-23 devnull return 0;
964 bc7cb1a1 2003-11-23 devnull l += chartorune(&r, (char*)l);
966 bc7cb1a1 2003-11-23 devnull if(!(endfield && i == 1))
967 bc7cb1a1 2003-11-23 devnull l += chartorune(&r, (char*)l);
971 bc7cb1a1 2003-11-23 devnull } else {
972 bc7cb1a1 2003-11-23 devnull for(i=n1; i>0; i--) {
973 bc7cb1a1 2003-11-23 devnull while(c == ' ' || c == '\t')
974 bc7cb1a1 2003-11-23 devnull c = *l++;
975 bc7cb1a1 2003-11-23 devnull while(c != ' ' && c != '\t') {
976 bc7cb1a1 2003-11-23 devnull if(c == '\n')
977 bc7cb1a1 2003-11-23 devnull return 0;
978 bc7cb1a1 2003-11-23 devnull c = *l++;
983 bc7cb1a1 2003-11-23 devnull if(bflag)
984 bc7cb1a1 2003-11-23 devnull while(c == ' ' || c == '\t')
985 bc7cb1a1 2003-11-23 devnull c = *l++;
988 bc7cb1a1 2003-11-23 devnull for(i=n2; i>0; i--) {
990 bc7cb1a1 2003-11-23 devnull if(c < Runeself) {
991 bc7cb1a1 2003-11-23 devnull if(c == '\n')
992 bc7cb1a1 2003-11-23 devnull return 0;
994 bc7cb1a1 2003-11-23 devnull continue;
996 bc7cb1a1 2003-11-23 devnull l += chartorune(&r, (char*)l);
998 bc7cb1a1 2003-11-23 devnull return l;
1002 bc7cb1a1 2003-11-23 devnull dokey_gn(Key *k, uchar *lp, uchar *lpe, Field *f)
1004 bc7cb1a1 2003-11-23 devnull uchar *kp;
1005 bc7cb1a1 2003-11-23 devnull int c, cl, dp;
1006 bc7cb1a1 2003-11-23 devnull int state, nzero, exp, expsign, rflag;
1008 bc7cb1a1 2003-11-23 devnull cl = k->klen + 3;
1009 bc7cb1a1 2003-11-23 devnull kp = k->key + cl; /* skip place for sign, exponent[2] */
1011 bc7cb1a1 2003-11-23 devnull nzero = 0; /* number of trailing zeros */
1012 bc7cb1a1 2003-11-23 devnull exp = 0; /* value of the exponent */
1013 bc7cb1a1 2003-11-23 devnull expsign = 0; /* sign of the exponent */
1014 bc7cb1a1 2003-11-23 devnull dp = 0x4040; /* location of decimal point */
1015 bc7cb1a1 2003-11-23 devnull rflag = f->flags&Rflag; /* xor of rflag and - sign */
1016 bc7cb1a1 2003-11-23 devnull state = NSstart;
1018 bc7cb1a1 2003-11-23 devnull for(;; lp++) {
1019 bc7cb1a1 2003-11-23 devnull if(lp >= lpe)
1021 bc7cb1a1 2003-11-23 devnull c = *lp;
1023 bc7cb1a1 2003-11-23 devnull if(c == ' ' || c == '\t') {
1024 bc7cb1a1 2003-11-23 devnull switch(state) {
1025 bc7cb1a1 2003-11-23 devnull case NSstart:
1026 bc7cb1a1 2003-11-23 devnull case NSsign:
1027 bc7cb1a1 2003-11-23 devnull continue;
1031 bc7cb1a1 2003-11-23 devnull if(c == '+' || c == '-') {
1032 bc7cb1a1 2003-11-23 devnull switch(state) {
1033 bc7cb1a1 2003-11-23 devnull case NSstart:
1034 bc7cb1a1 2003-11-23 devnull state = NSsign;
1035 bc7cb1a1 2003-11-23 devnull if(c == '-')
1036 bc7cb1a1 2003-11-23 devnull rflag = !rflag;
1037 bc7cb1a1 2003-11-23 devnull continue;
1038 bc7cb1a1 2003-11-23 devnull case NSexp:
1039 bc7cb1a1 2003-11-23 devnull state = NSexpsign;
1040 bc7cb1a1 2003-11-23 devnull if(c == '-')
1041 bc7cb1a1 2003-11-23 devnull expsign = 1;
1042 bc7cb1a1 2003-11-23 devnull continue;
1046 bc7cb1a1 2003-11-23 devnull if(c == '0') {
1047 bc7cb1a1 2003-11-23 devnull switch(state) {
1048 bc7cb1a1 2003-11-23 devnull case NSdigit:
1049 bc7cb1a1 2003-11-23 devnull if(rflag)
1050 bc7cb1a1 2003-11-23 devnull c = ~c;
1051 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1053 bc7cb1a1 2003-11-23 devnull nzero++;
1055 bc7cb1a1 2003-11-23 devnull state = NSdigit;
1056 bc7cb1a1 2003-11-23 devnull continue;
1057 bc7cb1a1 2003-11-23 devnull case NSfract:
1058 bc7cb1a1 2003-11-23 devnull if(rflag)
1059 bc7cb1a1 2003-11-23 devnull c = ~c;
1060 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1062 bc7cb1a1 2003-11-23 devnull nzero++;
1063 bc7cb1a1 2003-11-23 devnull state = NSfract;
1064 bc7cb1a1 2003-11-23 devnull continue;
1065 bc7cb1a1 2003-11-23 devnull case NSstart:
1066 bc7cb1a1 2003-11-23 devnull case NSsign:
1067 bc7cb1a1 2003-11-23 devnull case NSzero:
1068 bc7cb1a1 2003-11-23 devnull state = NSzero;
1069 bc7cb1a1 2003-11-23 devnull continue;
1070 bc7cb1a1 2003-11-23 devnull case NSzerofract:
1071 bc7cb1a1 2003-11-23 devnull case NSpoint:
1073 bc7cb1a1 2003-11-23 devnull state = NSzerofract;
1074 bc7cb1a1 2003-11-23 devnull continue;
1075 bc7cb1a1 2003-11-23 devnull case NSexpsign:
1076 bc7cb1a1 2003-11-23 devnull case NSexp:
1077 bc7cb1a1 2003-11-23 devnull case NSexpdigit:
1078 bc7cb1a1 2003-11-23 devnull exp = exp*10 + (c - '0');
1079 bc7cb1a1 2003-11-23 devnull state = NSexpdigit;
1080 bc7cb1a1 2003-11-23 devnull continue;
1084 bc7cb1a1 2003-11-23 devnull if(c >= '1' && c <= '9') {
1085 bc7cb1a1 2003-11-23 devnull switch(state) {
1086 bc7cb1a1 2003-11-23 devnull case NSzero:
1087 bc7cb1a1 2003-11-23 devnull case NSstart:
1088 bc7cb1a1 2003-11-23 devnull case NSsign:
1089 bc7cb1a1 2003-11-23 devnull case NSdigit:
1090 bc7cb1a1 2003-11-23 devnull if(rflag)
1091 bc7cb1a1 2003-11-23 devnull c = ~c;
1092 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1094 bc7cb1a1 2003-11-23 devnull nzero = 0;
1096 bc7cb1a1 2003-11-23 devnull state = NSdigit;
1097 bc7cb1a1 2003-11-23 devnull continue;
1098 bc7cb1a1 2003-11-23 devnull case NSzerofract:
1099 bc7cb1a1 2003-11-23 devnull case NSpoint:
1100 bc7cb1a1 2003-11-23 devnull case NSfract:
1101 bc7cb1a1 2003-11-23 devnull if(rflag)
1102 bc7cb1a1 2003-11-23 devnull c = ~c;
1103 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1105 bc7cb1a1 2003-11-23 devnull nzero = 0;
1106 bc7cb1a1 2003-11-23 devnull state = NSfract;
1107 bc7cb1a1 2003-11-23 devnull continue;
1108 bc7cb1a1 2003-11-23 devnull case NSexpsign:
1109 bc7cb1a1 2003-11-23 devnull case NSexp:
1110 bc7cb1a1 2003-11-23 devnull case NSexpdigit:
1111 bc7cb1a1 2003-11-23 devnull exp = exp*10 + (c - '0');
1112 bc7cb1a1 2003-11-23 devnull state = NSexpdigit;
1113 bc7cb1a1 2003-11-23 devnull continue;
1117 bc7cb1a1 2003-11-23 devnull if(c == '.') {
1118 bc7cb1a1 2003-11-23 devnull switch(state) {
1119 bc7cb1a1 2003-11-23 devnull case NSstart:
1120 bc7cb1a1 2003-11-23 devnull case NSsign:
1121 bc7cb1a1 2003-11-23 devnull state = NSpoint;
1122 bc7cb1a1 2003-11-23 devnull continue;
1123 bc7cb1a1 2003-11-23 devnull case NSzero:
1124 bc7cb1a1 2003-11-23 devnull state = NSzerofract;
1125 bc7cb1a1 2003-11-23 devnull continue;
1126 bc7cb1a1 2003-11-23 devnull case NSdigit:
1127 bc7cb1a1 2003-11-23 devnull state = NSfract;
1128 bc7cb1a1 2003-11-23 devnull continue;
1132 bc7cb1a1 2003-11-23 devnull if((f->flags & Gflag) && (c == 'e' || c == 'E')) {
1133 bc7cb1a1 2003-11-23 devnull switch(state) {
1134 bc7cb1a1 2003-11-23 devnull case NSdigit:
1135 bc7cb1a1 2003-11-23 devnull case NSfract:
1136 bc7cb1a1 2003-11-23 devnull state = NSexp;
1137 bc7cb1a1 2003-11-23 devnull continue;
1144 bc7cb1a1 2003-11-23 devnull switch(state) {
1146 bc7cb1a1 2003-11-23 devnull * result is zero
1148 bc7cb1a1 2003-11-23 devnull case NSstart:
1149 bc7cb1a1 2003-11-23 devnull case NSsign:
1150 bc7cb1a1 2003-11-23 devnull case NSzero:
1151 bc7cb1a1 2003-11-23 devnull case NSzerofract:
1152 bc7cb1a1 2003-11-23 devnull case NSpoint:
1153 bc7cb1a1 2003-11-23 devnull kp = k->key + k->klen;
1154 bc7cb1a1 2003-11-23 devnull k->klen += 2;
1155 bc7cb1a1 2003-11-23 devnull kp[0] = 0x20; /* between + and - */
1156 bc7cb1a1 2003-11-23 devnull kp[1] = 0;
1157 bc7cb1a1 2003-11-23 devnull return;
1159 bc7cb1a1 2003-11-23 devnull * result has exponent
1161 bc7cb1a1 2003-11-23 devnull case NSexpsign:
1162 bc7cb1a1 2003-11-23 devnull case NSexp:
1163 bc7cb1a1 2003-11-23 devnull case NSexpdigit:
1164 bc7cb1a1 2003-11-23 devnull if(expsign)
1165 bc7cb1a1 2003-11-23 devnull exp = -exp;
1166 bc7cb1a1 2003-11-23 devnull dp += exp;
1169 bc7cb1a1 2003-11-23 devnull * result is fixed point number
1171 bc7cb1a1 2003-11-23 devnull case NSdigit:
1172 bc7cb1a1 2003-11-23 devnull case NSfract:
1173 bc7cb1a1 2003-11-23 devnull kp -= nzero;
1174 bc7cb1a1 2003-11-23 devnull cl -= nzero;
1179 bc7cb1a1 2003-11-23 devnull * end of number
1182 bc7cb1a1 2003-11-23 devnull if(rflag)
1183 bc7cb1a1 2003-11-23 devnull c = ~c;
1184 bc7cb1a1 2003-11-23 devnull *kp = c;
1187 bc7cb1a1 2003-11-23 devnull * sign and exponent
1189 bc7cb1a1 2003-11-23 devnull c = 0x30;
1190 bc7cb1a1 2003-11-23 devnull if(rflag) {
1191 bc7cb1a1 2003-11-23 devnull c = 0x10;
1192 bc7cb1a1 2003-11-23 devnull dp = ~dp;
1194 bc7cb1a1 2003-11-23 devnull kp = k->key + k->klen;
1195 bc7cb1a1 2003-11-23 devnull kp[0] = c;
1196 bc7cb1a1 2003-11-23 devnull kp[1] = (dp >> 8);
1197 bc7cb1a1 2003-11-23 devnull kp[2] = dp;
1198 bc7cb1a1 2003-11-23 devnull k->klen = cl+1;
1202 bc7cb1a1 2003-11-23 devnull dokey_m(Key *k, uchar *lp, uchar *lpe, Field *f)
1204 bc7cb1a1 2003-11-23 devnull uchar *kp;
1205 bc7cb1a1 2003-11-23 devnull Rune r, place[3];
1206 bc7cb1a1 2003-11-23 devnull int c, cl, pc;
1207 bc7cb1a1 2003-11-23 devnull int rflag;
1209 bc7cb1a1 2003-11-23 devnull rflag = f->flags&Rflag;
1210 bc7cb1a1 2003-11-23 devnull pc = 0;
1212 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1213 bc7cb1a1 2003-11-23 devnull kp = k->key + cl;
1215 bc7cb1a1 2003-11-23 devnull for(;;) {
1217 bc7cb1a1 2003-11-23 devnull * get the character
1219 bc7cb1a1 2003-11-23 devnull if(lp >= lpe)
1221 bc7cb1a1 2003-11-23 devnull c = *lp;
1222 bc7cb1a1 2003-11-23 devnull if(c >= Runeself) {
1223 bc7cb1a1 2003-11-23 devnull lp += chartorune(&r, (char*)lp);
1228 bc7cb1a1 2003-11-23 devnull if(c < nelem(f->mapto)) {
1229 bc7cb1a1 2003-11-23 devnull c = f->mapto[c];
1230 bc7cb1a1 2003-11-23 devnull if(c == 0)
1231 bc7cb1a1 2003-11-23 devnull continue;
1233 bc7cb1a1 2003-11-23 devnull place[pc++] = c;
1234 bc7cb1a1 2003-11-23 devnull if(pc < 3)
1235 bc7cb1a1 2003-11-23 devnull continue;
1236 bc7cb1a1 2003-11-23 devnull for(c=11; c>=0; c--)
1237 bc7cb1a1 2003-11-23 devnull if(memcmp(month[c], place, sizeof(place)) == 0)
1239 bc7cb1a1 2003-11-23 devnull c += 10;
1240 bc7cb1a1 2003-11-23 devnull if(rflag)
1241 bc7cb1a1 2003-11-23 devnull c = ~c;
1242 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1248 bc7cb1a1 2003-11-23 devnull if(rflag)
1249 bc7cb1a1 2003-11-23 devnull c = ~c;
1250 bc7cb1a1 2003-11-23 devnull *kp = c;
1251 bc7cb1a1 2003-11-23 devnull k->klen = cl+1;
1255 bc7cb1a1 2003-11-23 devnull dokey_dfi(Key *k, uchar *lp, uchar *lpe, Field *f)
1257 bc7cb1a1 2003-11-23 devnull uchar *kp;
1258 bc7cb1a1 2003-11-23 devnull Rune r;
1259 bc7cb1a1 2003-11-23 devnull int c, cl, n, rflag;
1261 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1262 bc7cb1a1 2003-11-23 devnull kp = k->key + cl;
1263 bc7cb1a1 2003-11-23 devnull rflag = f->flags & Rflag;
1265 bc7cb1a1 2003-11-23 devnull for(;;) {
1267 bc7cb1a1 2003-11-23 devnull * get the character
1269 bc7cb1a1 2003-11-23 devnull if(lp >= lpe)
1271 bc7cb1a1 2003-11-23 devnull c = *lp;
1272 bc7cb1a1 2003-11-23 devnull if(c >= Runeself) {
1273 bc7cb1a1 2003-11-23 devnull lp += chartorune(&r, (char*)lp);
1279 bc7cb1a1 2003-11-23 devnull * do the various mappings.
1280 bc7cb1a1 2003-11-23 devnull * the common case is handled
1281 bc7cb1a1 2003-11-23 devnull * completely by the table.
1283 bc7cb1a1 2003-11-23 devnull if(c != 0 && c < Runeself) {
1284 bc7cb1a1 2003-11-23 devnull c = f->mapto[c];
1285 bc7cb1a1 2003-11-23 devnull if(c) {
1286 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1289 bc7cb1a1 2003-11-23 devnull continue;
1293 bc7cb1a1 2003-11-23 devnull * for characters out of range,
1294 bc7cb1a1 2003-11-23 devnull * the table does not do Rflag.
1295 bc7cb1a1 2003-11-23 devnull * ignore is based on mapto[255]
1297 bc7cb1a1 2003-11-23 devnull if(c != 0 && c < nelem(f->mapto)) {
1298 bc7cb1a1 2003-11-23 devnull c = f->mapto[c];
1299 bc7cb1a1 2003-11-23 devnull if(c == 0)
1300 bc7cb1a1 2003-11-23 devnull continue;
1302 bc7cb1a1 2003-11-23 devnull if(f->mapto[nelem(f->mapto)-1] == 0)
1303 bc7cb1a1 2003-11-23 devnull continue;
1306 bc7cb1a1 2003-11-23 devnull * put it in the key
1309 bc7cb1a1 2003-11-23 devnull n = runetochar((char*)kp, &r);
1310 bc7cb1a1 2003-11-23 devnull kp += n;
1311 bc7cb1a1 2003-11-23 devnull cl += n;
1312 bc7cb1a1 2003-11-23 devnull if(rflag)
1313 bc7cb1a1 2003-11-23 devnull while(n > 0) {
1314 bc7cb1a1 2003-11-23 devnull kp[-n] = ~kp[-n];
1320 bc7cb1a1 2003-11-23 devnull * end of key
1322 bc7cb1a1 2003-11-23 devnull k->klen = cl+1;
1323 bc7cb1a1 2003-11-23 devnull if(rflag) {
1324 bc7cb1a1 2003-11-23 devnull *kp = ~0;
1325 bc7cb1a1 2003-11-23 devnull return;
1327 bc7cb1a1 2003-11-23 devnull *kp = 0;
1331 bc7cb1a1 2003-11-23 devnull dokey_r(Key *k, uchar *lp, uchar *lpe, Field *f)
1333 bc7cb1a1 2003-11-23 devnull int cl, n;
1334 bc7cb1a1 2003-11-23 devnull uchar *kp;
1336 bc7cb1a1 2003-11-23 devnull USED(f);
1337 bc7cb1a1 2003-11-23 devnull n = lpe - lp;
1338 bc7cb1a1 2003-11-23 devnull if(n < 0)
1340 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1341 bc7cb1a1 2003-11-23 devnull kp = k->key + cl;
1342 bc7cb1a1 2003-11-23 devnull k->klen = cl+n+1;
1344 bc7cb1a1 2003-11-23 devnull lpe -= 3;
1345 bc7cb1a1 2003-11-23 devnull while(lp < lpe) {
1346 bc7cb1a1 2003-11-23 devnull kp[0] = ~lp[0];
1347 bc7cb1a1 2003-11-23 devnull kp[1] = ~lp[1];
1348 bc7cb1a1 2003-11-23 devnull kp[2] = ~lp[2];
1349 bc7cb1a1 2003-11-23 devnull kp[3] = ~lp[3];
1350 bc7cb1a1 2003-11-23 devnull kp += 4;
1351 bc7cb1a1 2003-11-23 devnull lp += 4;
1354 bc7cb1a1 2003-11-23 devnull lpe += 3;
1355 bc7cb1a1 2003-11-23 devnull while(lp < lpe)
1356 bc7cb1a1 2003-11-23 devnull *kp++ = ~*lp++;
1357 bc7cb1a1 2003-11-23 devnull *kp = ~0;
1361 bc7cb1a1 2003-11-23 devnull dokey_(Key *k, uchar *lp, uchar *lpe, Field *f)
1363 bc7cb1a1 2003-11-23 devnull int n, cl;
1364 bc7cb1a1 2003-11-23 devnull uchar *kp;
1366 bc7cb1a1 2003-11-23 devnull USED(f);
1367 bc7cb1a1 2003-11-23 devnull n = lpe - lp;
1368 bc7cb1a1 2003-11-23 devnull if(n < 0)
1370 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1371 bc7cb1a1 2003-11-23 devnull kp = k->key + cl;
1372 bc7cb1a1 2003-11-23 devnull k->klen = cl+n+1;
1373 bc7cb1a1 2003-11-23 devnull memmove(kp, lp, n);
1374 bc7cb1a1 2003-11-23 devnull kp[n] = 0;
1378 bc7cb1a1 2003-11-23 devnull buildkey(Line *l)
1380 bc7cb1a1 2003-11-23 devnull Key *k;
1381 bc7cb1a1 2003-11-23 devnull uchar *lp, *lpe;
1382 bc7cb1a1 2003-11-23 devnull int ll, kl, cl, i, n;
1383 bc7cb1a1 2003-11-23 devnull Field *f;
1385 bc7cb1a1 2003-11-23 devnull ll = l->llen - 1;
1386 bc7cb1a1 2003-11-23 devnull kl = 0; /* allocated length */
1387 bc7cb1a1 2003-11-23 devnull cl = 0; /* current length */
1390 bc7cb1a1 2003-11-23 devnull for(i=1; i<=args.nfield; i++) {
1391 bc7cb1a1 2003-11-23 devnull f = &args.field[i];
1392 bc7cb1a1 2003-11-23 devnull lp = skip(l->line, f->beg1, f->beg2, f->flags&B1flag, 0);
1393 bc7cb1a1 2003-11-23 devnull if(lp == 0)
1394 bc7cb1a1 2003-11-23 devnull lp = l->line + ll;
1395 bc7cb1a1 2003-11-23 devnull lpe = skip(l->line, f->end1, f->end2, f->flags&Bflag, 1);
1396 bc7cb1a1 2003-11-23 devnull if(lpe == 0)
1397 bc7cb1a1 2003-11-23 devnull lpe = l->line + ll;
1398 bc7cb1a1 2003-11-23 devnull n = (lpe - lp) + 1;
1399 bc7cb1a1 2003-11-23 devnull if(n <= 0)
1401 bc7cb1a1 2003-11-23 devnull if(cl+(n+4) > kl) {
1402 bc7cb1a1 2003-11-23 devnull kl = cl+(n+4);
1403 bc7cb1a1 2003-11-23 devnull k = realloc(k, sizeof(Key) +
1404 bc7cb1a1 2003-11-23 devnull (kl-1)*sizeof(k->key[0]));
1405 bc7cb1a1 2003-11-23 devnull if(k == 0)
1406 bc7cb1a1 2003-11-23 devnull nomem();
1408 bc7cb1a1 2003-11-23 devnull k->klen = cl;
1409 bc7cb1a1 2003-11-23 devnull (*f->dokey)(k, lp, lpe, f);
1410 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1414 bc7cb1a1 2003-11-23 devnull * global comparisons
1416 bc7cb1a1 2003-11-23 devnull if(!(args.uflag && cl > 0)) {
1417 bc7cb1a1 2003-11-23 devnull f = &args.field[0];
1418 bc7cb1a1 2003-11-23 devnull if(cl+(ll+4) > kl) {
1419 bc7cb1a1 2003-11-23 devnull kl = cl+(ll+4);
1420 bc7cb1a1 2003-11-23 devnull k = realloc(k, sizeof(Key) +
1421 bc7cb1a1 2003-11-23 devnull (kl-1)*sizeof(k->key[0]));
1422 bc7cb1a1 2003-11-23 devnull if(k == 0)
1423 bc7cb1a1 2003-11-23 devnull nomem();
1425 bc7cb1a1 2003-11-23 devnull k->klen = cl;
1426 bc7cb1a1 2003-11-23 devnull (*f->dokey)(k, l->line, l->line+ll, f);
1427 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1430 bc7cb1a1 2003-11-23 devnull l->key = k;
1431 bc7cb1a1 2003-11-23 devnull k->klen = cl;
1433 bc7cb1a1 2003-11-23 devnull if(args.vflag) {
1434 bc7cb1a1 2003-11-23 devnull write(2, l->line, l->llen);
1435 bc7cb1a1 2003-11-23 devnull for(i=0; i<k->klen; i++) {
1436 bc7cb1a1 2003-11-23 devnull fprint(2, " %.2x", k->key[i]);
1437 bc7cb1a1 2003-11-23 devnull if(k->key[i] == 0x00 || k->key[i] == 0xff)
1438 bc7cb1a1 2003-11-23 devnull fprint(2, "\n");
1444 bc7cb1a1 2003-11-23 devnull makemapm(Field *f)
1446 bc7cb1a1 2003-11-23 devnull int i, c;
1448 bc7cb1a1 2003-11-23 devnull for(i=0; i<nelem(f->mapto); i++) {
1450 bc7cb1a1 2003-11-23 devnull if(i == ' ' || i == '\t')
1452 bc7cb1a1 2003-11-23 devnull if(i >= 'a' && i <= 'z')
1453 bc7cb1a1 2003-11-23 devnull c = i + ('A' - 'a');
1454 bc7cb1a1 2003-11-23 devnull if(i >= 'A' && i <= 'Z')
1456 bc7cb1a1 2003-11-23 devnull f->mapto[i] = c;
1457 bc7cb1a1 2003-11-23 devnull if(args.vflag) {
1458 bc7cb1a1 2003-11-23 devnull if((i & 15) == 0)
1459 bc7cb1a1 2003-11-23 devnull fprint(2, " ");
1460 bc7cb1a1 2003-11-23 devnull fprint(2, " %.2x", c);
1461 bc7cb1a1 2003-11-23 devnull if((i & 15) == 15)
1462 bc7cb1a1 2003-11-23 devnull fprint(2, "\n");
1468 bc7cb1a1 2003-11-23 devnull makemapd(Field *f)
1470 bc7cb1a1 2003-11-23 devnull int i, j, c;
1472 bc7cb1a1 2003-11-23 devnull for(i=0; i<nelem(f->mapto); i++) {
1474 bc7cb1a1 2003-11-23 devnull if(f->flags & Iflag)
1475 bc7cb1a1 2003-11-23 devnull if(c < 040 || c > 0176)
1476 bc7cb1a1 2003-11-23 devnull c = -1;
1477 bc7cb1a1 2003-11-23 devnull if((f->flags & Wflag) && c >= 0)
1478 bc7cb1a1 2003-11-23 devnull if(c == ' ' || c == '\t')
1479 bc7cb1a1 2003-11-23 devnull c = -1;
1480 bc7cb1a1 2003-11-23 devnull if((f->flags & Dflag) && c >= 0)
1481 bc7cb1a1 2003-11-23 devnull if(!(c == ' ' || c == '\t' ||
1482 bc7cb1a1 2003-11-23 devnull (c >= 'a' && c <= 'z') ||
1483 bc7cb1a1 2003-11-23 devnull (c >= 'A' && c <= 'Z') ||
1484 bc7cb1a1 2003-11-23 devnull (c >= '0' && c <= '9'))) {
1485 bc7cb1a1 2003-11-23 devnull for(j=0; latinmap[j]; j+=3)
1486 bc7cb1a1 2003-11-23 devnull if(c == latinmap[j+0] ||
1487 bc7cb1a1 2003-11-23 devnull c == latinmap[j+1])
1489 bc7cb1a1 2003-11-23 devnull if(latinmap[j] == 0)
1490 bc7cb1a1 2003-11-23 devnull c = -1;
1492 bc7cb1a1 2003-11-23 devnull if((f->flags & Fflag) && c >= 0) {
1493 bc7cb1a1 2003-11-23 devnull if(c >= 'a' && c <= 'z')
1494 bc7cb1a1 2003-11-23 devnull c += 'A' - 'a';
1495 bc7cb1a1 2003-11-23 devnull for(j=0; latinmap[j]; j+=3)
1496 bc7cb1a1 2003-11-23 devnull if(c == latinmap[j+0] ||
1497 bc7cb1a1 2003-11-23 devnull c == latinmap[j+1]) {
1498 bc7cb1a1 2003-11-23 devnull c = latinmap[j+2];
1502 bc7cb1a1 2003-11-23 devnull if((f->flags & Rflag) && c >= 0 && i > 0 && i < Runeself)
1503 bc7cb1a1 2003-11-23 devnull c = ~c & 0xff;
1504 bc7cb1a1 2003-11-23 devnull if(c < 0)
1506 bc7cb1a1 2003-11-23 devnull f->mapto[i] = c;
1507 bc7cb1a1 2003-11-23 devnull if(args.vflag) {
1508 bc7cb1a1 2003-11-23 devnull if((i & 15) == 0)
1509 bc7cb1a1 2003-11-23 devnull fprint(2, " ");
1510 bc7cb1a1 2003-11-23 devnull fprint(2, " %.2x", c);
1511 bc7cb1a1 2003-11-23 devnull if((i & 15) == 15)
1512 bc7cb1a1 2003-11-23 devnull fprint(2, "\n");
1517 bc7cb1a1 2003-11-23 devnull int latinmap[] =
1519 bc7cb1a1 2003-11-23 devnull /* lcase ucase fold */
1520 bc7cb1a1 2003-11-23 devnull 0xe0, 0xc0, 0x41, /* L'à', L'À', L'A', */
1521 bc7cb1a1 2003-11-23 devnull 0xe1, 0xc1, 0x41, /* L'á', L'Á', L'A', */
1522 bc7cb1a1 2003-11-23 devnull 0xe2, 0xc2, 0x41, /* L'â', L'Â', L'A', */
1523 bc7cb1a1 2003-11-23 devnull 0xe4, 0xc4, 0x41, /* L'ä', L'Ä', L'A', */
1524 bc7cb1a1 2003-11-23 devnull 0xe3, 0xc3, 0x41, /* L'ã', L'Ã', L'A', */
1525 bc7cb1a1 2003-11-23 devnull 0xe5, 0xc5, 0x41, /* L'å', L'Å', L'A', */
1526 bc7cb1a1 2003-11-23 devnull 0xe8, 0xc8, 0x45, /* L'è', L'È', L'E', */
1527 bc7cb1a1 2003-11-23 devnull 0xe9, 0xc9, 0x45, /* L'é', L'É', L'E', */
1528 bc7cb1a1 2003-11-23 devnull 0xea, 0xca, 0x45, /* L'ê', L'Ê', L'E', */
1529 bc7cb1a1 2003-11-23 devnull 0xeb, 0xcb, 0x45, /* L'ë', L'Ë', L'E', */
1530 bc7cb1a1 2003-11-23 devnull 0xec, 0xcc, 0x49, /* L'ì', L'Ì', L'I', */
1531 bc7cb1a1 2003-11-23 devnull 0xed, 0xcd, 0x49, /* L'í', L'Í', L'I', */
1532 bc7cb1a1 2003-11-23 devnull 0xee, 0xce, 0x49, /* L'î', L'Î', L'I', */
1533 bc7cb1a1 2003-11-23 devnull 0xef, 0xcf, 0x49, /* L'ï', L'Ï', L'I', */
1534 bc7cb1a1 2003-11-23 devnull 0xf2, 0xd2, 0x4f, /* L'ò', L'Ò', L'O', */
1535 bc7cb1a1 2003-11-23 devnull 0xf3, 0xd3, 0x4f, /* L'ó', L'Ó', L'O', */
1536 bc7cb1a1 2003-11-23 devnull 0xf4, 0xd4, 0x4f, /* L'ô', L'Ô', L'O', */
1537 bc7cb1a1 2003-11-23 devnull 0xf6, 0xd6, 0x4f, /* L'ö', L'Ö', L'O', */
1538 bc7cb1a1 2003-11-23 devnull 0xf5, 0xd5, 0x4f, /* L'õ', L'Õ', L'O', */
1539 bc7cb1a1 2003-11-23 devnull 0xf8, 0xd8, 0x4f, /* L'ø', L'Ø', L'O', */
1540 bc7cb1a1 2003-11-23 devnull 0xf9, 0xd9, 0x55, /* L'ù', L'Ù', L'U', */
1541 bc7cb1a1 2003-11-23 devnull 0xfa, 0xda, 0x55, /* L'ú', L'Ú', L'U', */
1542 bc7cb1a1 2003-11-23 devnull 0xfb, 0xdb, 0x55, /* L'û', L'Û', L'U', */
1543 bc7cb1a1 2003-11-23 devnull 0xfc, 0xdc, 0x55, /* L'ü', L'Ü', L'U', */
1544 bc7cb1a1 2003-11-23 devnull 0xe6, 0xc6, 0x41, /* L'æ', L'Æ', L'A', */
1545 bc7cb1a1 2003-11-23 devnull 0xf0, 0xd0, 0x44, /* L'ð', L'Ð', L'D', */
1546 bc7cb1a1 2003-11-23 devnull 0xf1, 0xd1, 0x4e, /* L'ñ', L'Ñ', L'N', */
1547 bc7cb1a1 2003-11-23 devnull 0xfd, 0xdd, 0x59, /* L'ý', L'Ý', L'Y', */
1548 bc7cb1a1 2003-11-23 devnull 0xe7, 0xc7, 0x43, /* L'ç', L'Ç', L'C', */
1552 bc7cb1a1 2003-11-23 devnull Rune LJAN[] = { 'J', 'A', 'N', 0 };
1553 bc7cb1a1 2003-11-23 devnull Rune LFEB[] = { 'F', 'E', 'B', 0 };
1554 bc7cb1a1 2003-11-23 devnull Rune LMAR[] = { 'M', 'A', 'R', 0 };
1555 bc7cb1a1 2003-11-23 devnull Rune LAPR[] = { 'A', 'P', 'R', 0 };
1556 bc7cb1a1 2003-11-23 devnull Rune LMAY[] = { 'M', 'A', 'Y', 0 };
1557 bc7cb1a1 2003-11-23 devnull Rune LJUN[] = { 'J', 'U', 'N', 0 };
1558 bc7cb1a1 2003-11-23 devnull Rune LJUL[] = { 'J', 'U', 'L', 0 };
1559 bc7cb1a1 2003-11-23 devnull Rune LAUG[] = { 'A', 'U', 'G', 0 };
1560 bc7cb1a1 2003-11-23 devnull Rune LSEP[] = { 'S', 'E', 'P', 0 };
1561 bc7cb1a1 2003-11-23 devnull Rune LOCT[] = { 'O', 'C', 'T', 0 };
1562 bc7cb1a1 2003-11-23 devnull Rune LNOV[] = { 'N', 'O', 'V', 0 };
1563 bc7cb1a1 2003-11-23 devnull Rune LDEC[] = { 'D', 'E', 'C', 0 };
1565 bc7cb1a1 2003-11-23 devnull Rune* month[12] =
1581 bc7cb1a1 2003-11-23 devnull /************** radix sort ***********/
1585 cbeb0b26 2006-04-01 devnull Threshold = 14
1588 bc7cb1a1 2003-11-23 devnull void rsort4(Key***, ulong, int);
1589 bc7cb1a1 2003-11-23 devnull void bsort4(Key***, ulong, int);
1592 bc7cb1a1 2003-11-23 devnull sort4(void *a, ulong n)
1594 bc7cb1a1 2003-11-23 devnull if(n > Threshold)
1595 bc7cb1a1 2003-11-23 devnull rsort4((Key***)a, n, 0);
1597 bc7cb1a1 2003-11-23 devnull bsort4((Key***)a, n, 0);
1601 bc7cb1a1 2003-11-23 devnull rsort4(Key ***a, ulong n, int b)
1603 bc7cb1a1 2003-11-23 devnull Key ***ea, ***t, ***u, **t1, **u1, *k;
1604 bc7cb1a1 2003-11-23 devnull Key ***part[257];
1605 bc7cb1a1 2003-11-23 devnull static long count[257];
1606 bc7cb1a1 2003-11-23 devnull long clist[257+257], *cp, *cp1;
1607 bc7cb1a1 2003-11-23 devnull int c, lowc, higc;
1610 bc7cb1a1 2003-11-23 devnull * pass 1 over all keys,
1611 bc7cb1a1 2003-11-23 devnull * count the number of each key[b].
1612 bc7cb1a1 2003-11-23 devnull * find low count and high count.
1614 bc7cb1a1 2003-11-23 devnull lowc = 256;
1615 bc7cb1a1 2003-11-23 devnull higc = 0;
1616 bc7cb1a1 2003-11-23 devnull ea = a+n;
1617 bc7cb1a1 2003-11-23 devnull for(t=a; t<ea; t++) {
1618 bc7cb1a1 2003-11-23 devnull k = **t;
1619 bc7cb1a1 2003-11-23 devnull n = k->klen;
1620 bc7cb1a1 2003-11-23 devnull if(b >= n) {
1621 bc7cb1a1 2003-11-23 devnull count[256]++;
1622 bc7cb1a1 2003-11-23 devnull continue;
1624 bc7cb1a1 2003-11-23 devnull c = k->key[b];
1625 bc7cb1a1 2003-11-23 devnull n = count[c]++;
1626 bc7cb1a1 2003-11-23 devnull if(n == 0) {
1627 bc7cb1a1 2003-11-23 devnull if(c < lowc)
1628 bc7cb1a1 2003-11-23 devnull lowc = c;
1629 bc7cb1a1 2003-11-23 devnull if(c > higc)
1630 bc7cb1a1 2003-11-23 devnull higc = c;
1635 bc7cb1a1 2003-11-23 devnull * pass 2 over all counts,
1636 bc7cb1a1 2003-11-23 devnull * put partition pointers in part[c].
1637 bc7cb1a1 2003-11-23 devnull * save compacted indexes and counts
1638 bc7cb1a1 2003-11-23 devnull * in clist[].
1641 bc7cb1a1 2003-11-23 devnull n = count[256];
1642 bc7cb1a1 2003-11-23 devnull clist[0] = n;
1643 bc7cb1a1 2003-11-23 devnull part[256] = t;
1644 bc7cb1a1 2003-11-23 devnull t += n;
1646 bc7cb1a1 2003-11-23 devnull cp1 = clist+1;
1647 bc7cb1a1 2003-11-23 devnull cp = count+lowc;
1648 bc7cb1a1 2003-11-23 devnull for(c=lowc; c<=higc; c++,cp++) {
1649 bc7cb1a1 2003-11-23 devnull n = *cp;
1650 bc7cb1a1 2003-11-23 devnull if(n) {
1651 bc7cb1a1 2003-11-23 devnull cp1[0] = n;
1652 bc7cb1a1 2003-11-23 devnull cp1[1] = c;
1653 bc7cb1a1 2003-11-23 devnull cp1 += 2;
1654 bc7cb1a1 2003-11-23 devnull part[c] = t;
1655 bc7cb1a1 2003-11-23 devnull t += n;
1658 bc7cb1a1 2003-11-23 devnull *cp1 = 0;
1661 bc7cb1a1 2003-11-23 devnull * pass 3 over all counts.
1662 bc7cb1a1 2003-11-23 devnull * chase lowest pointer in each partition
1663 bc7cb1a1 2003-11-23 devnull * around a permutation until it comes
1664 bc7cb1a1 2003-11-23 devnull * back and is stored where it started.
1665 bc7cb1a1 2003-11-23 devnull * static array, count[], should be
1666 bc7cb1a1 2003-11-23 devnull * reduced to zero entries except maybe
1667 bc7cb1a1 2003-11-23 devnull * count[256].
1669 bc7cb1a1 2003-11-23 devnull for(cp1=clist+1; cp1[0]; cp1+=2) {
1670 bc7cb1a1 2003-11-23 devnull c = cp1[1];
1671 bc7cb1a1 2003-11-23 devnull cp = count+c;
1672 bc7cb1a1 2003-11-23 devnull while(*cp) {
1673 bc7cb1a1 2003-11-23 devnull t1 = *part[c];
1674 bc7cb1a1 2003-11-23 devnull for(;;) {
1675 bc7cb1a1 2003-11-23 devnull k = *t1;
1676 bc7cb1a1 2003-11-23 devnull n = 256;
1677 bc7cb1a1 2003-11-23 devnull if(b < k->klen)
1678 bc7cb1a1 2003-11-23 devnull n = k->key[b];
1679 bc7cb1a1 2003-11-23 devnull u = part[n]++;
1680 bc7cb1a1 2003-11-23 devnull count[n]--;
1681 bc7cb1a1 2003-11-23 devnull u1 = *u;
1682 bc7cb1a1 2003-11-23 devnull *u = t1;
1683 bc7cb1a1 2003-11-23 devnull if(n == c)
1685 bc7cb1a1 2003-11-23 devnull t1 = u1;
1691 bc7cb1a1 2003-11-23 devnull * pass 4 over all partitions.
1692 bc7cb1a1 2003-11-23 devnull * call recursively.
1695 bc7cb1a1 2003-11-23 devnull t = a + clist[0];
1696 bc7cb1a1 2003-11-23 devnull count[256] = 0;
1697 bc7cb1a1 2003-11-23 devnull for(cp1=clist+1; n=cp1[0]; cp1+=2) {
1698 bc7cb1a1 2003-11-23 devnull if(n > Threshold)
1699 bc7cb1a1 2003-11-23 devnull rsort4(t, n, b);
1701 bc7cb1a1 2003-11-23 devnull if(n > 1)
1702 bc7cb1a1 2003-11-23 devnull bsort4(t, n, b);
1703 bc7cb1a1 2003-11-23 devnull t += n;
1708 bc7cb1a1 2003-11-23 devnull * bubble sort to pick up
1709 bc7cb1a1 2003-11-23 devnull * the pieces.
1712 bc7cb1a1 2003-11-23 devnull bsort4(Key ***a, ulong n, int b)
1714 bc7cb1a1 2003-11-23 devnull Key ***i, ***j, ***k, ***l, **t;
1715 bc7cb1a1 2003-11-23 devnull Key *ka, *kb;
1716 bc7cb1a1 2003-11-23 devnull int n1, n2;
1718 bc7cb1a1 2003-11-23 devnull l = a+n;
1724 bc7cb1a1 2003-11-23 devnull if(j >= l)
1725 bc7cb1a1 2003-11-23 devnull return;
1727 bc7cb1a1 2003-11-23 devnull ka = **i;
1728 bc7cb1a1 2003-11-23 devnull kb = **j;
1729 bc7cb1a1 2003-11-23 devnull n1 = ka->klen - b;
1730 bc7cb1a1 2003-11-23 devnull n2 = kb->klen - b;
1731 bc7cb1a1 2003-11-23 devnull if(n1 > n2)
1732 bc7cb1a1 2003-11-23 devnull n1 = n2;
1733 bc7cb1a1 2003-11-23 devnull if(n1 <= 0)
1734 bc7cb1a1 2003-11-23 devnull goto loop;
1735 bc7cb1a1 2003-11-23 devnull n2 = ka->key[b] - kb->key[b];
1736 bc7cb1a1 2003-11-23 devnull if(n2 == 0)
1737 bc7cb1a1 2003-11-23 devnull n2 = memcmp(ka->key+b, kb->key+b, n1);
1738 bc7cb1a1 2003-11-23 devnull if(n2 <= 0)
1739 bc7cb1a1 2003-11-23 devnull goto loop;
1741 bc7cb1a1 2003-11-23 devnull for(;;) {
1742 bc7cb1a1 2003-11-23 devnull k = i+1;
1744 bc7cb1a1 2003-11-23 devnull t = *k;
1745 bc7cb1a1 2003-11-23 devnull *k = *i;
1746 bc7cb1a1 2003-11-23 devnull *i = t;
1748 bc7cb1a1 2003-11-23 devnull if(i <= a)
1749 bc7cb1a1 2003-11-23 devnull goto loop;
1752 bc7cb1a1 2003-11-23 devnull ka = **i;
1753 bc7cb1a1 2003-11-23 devnull kb = *t;
1754 bc7cb1a1 2003-11-23 devnull n1 = ka->klen - b;
1755 bc7cb1a1 2003-11-23 devnull n2 = kb->klen - b;
1756 bc7cb1a1 2003-11-23 devnull if(n1 > n2)
1757 bc7cb1a1 2003-11-23 devnull n1 = n2;
1758 bc7cb1a1 2003-11-23 devnull if(n1 <= 0)
1759 bc7cb1a1 2003-11-23 devnull goto loop;
1760 bc7cb1a1 2003-11-23 devnull n2 = ka->key[b] - kb->key[b];
1761 bc7cb1a1 2003-11-23 devnull if(n2 == 0)
1762 bc7cb1a1 2003-11-23 devnull n2 = memcmp(ka->key+b, kb->key+b, n1);
1763 bc7cb1a1 2003-11-23 devnull if(n2 <= 0)
1764 bc7cb1a1 2003-11-23 devnull goto loop;