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 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: note: %s\n", s);
247 bc7cb1a1 2003-11-23 devnull abort();
251 bc7cb1a1 2003-11-23 devnull newline(Biobuf *b)
253 bc7cb1a1 2003-11-23 devnull Line *l;
254 bc7cb1a1 2003-11-23 devnull char *p;
255 bc7cb1a1 2003-11-23 devnull int n, c;
257 bc7cb1a1 2003-11-23 devnull p = Brdline(b, '\n');
258 bc7cb1a1 2003-11-23 devnull n = Blinelen(b);
259 bc7cb1a1 2003-11-23 devnull if(p == 0) {
260 bc7cb1a1 2003-11-23 devnull if(n == 0)
261 bc7cb1a1 2003-11-23 devnull return 0;
263 bc7cb1a1 2003-11-23 devnull for(n=0;;) {
264 bc7cb1a1 2003-11-23 devnull if((n & 31) == 0) {
265 bc7cb1a1 2003-11-23 devnull l = realloc(l, sizeof(Line) +
266 bc7cb1a1 2003-11-23 devnull (n+31)*sizeof(l->line[0]));
267 bc7cb1a1 2003-11-23 devnull if(l == 0)
268 bc7cb1a1 2003-11-23 devnull nomem();
270 bc7cb1a1 2003-11-23 devnull c = Bgetc(b);
271 bc7cb1a1 2003-11-23 devnull if(c < 0) {
272 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: newline added\n");
273 bc7cb1a1 2003-11-23 devnull c = '\n';
275 bc7cb1a1 2003-11-23 devnull l->line[n++] = c;
276 bc7cb1a1 2003-11-23 devnull if(c == '\n')
279 bc7cb1a1 2003-11-23 devnull l->llen = n;
280 bc7cb1a1 2003-11-23 devnull buildkey(l);
281 bc7cb1a1 2003-11-23 devnull return l;
283 bc7cb1a1 2003-11-23 devnull l = malloc(sizeof(Line) +
284 bc7cb1a1 2003-11-23 devnull (n-1)*sizeof(l->line[0]));
285 bc7cb1a1 2003-11-23 devnull if(l == 0)
286 bc7cb1a1 2003-11-23 devnull nomem();
287 bc7cb1a1 2003-11-23 devnull l->llen = n;
288 bc7cb1a1 2003-11-23 devnull memmove(l->line, p, n);
289 bc7cb1a1 2003-11-23 devnull buildkey(l);
290 bc7cb1a1 2003-11-23 devnull return l;
294 bc7cb1a1 2003-11-23 devnull lineout(Biobuf *b, Line *l)
296 bc7cb1a1 2003-11-23 devnull int n, m;
298 bc7cb1a1 2003-11-23 devnull n = l->llen;
299 bc7cb1a1 2003-11-23 devnull m = Bwrite(b, l->line, n);
300 bc7cb1a1 2003-11-23 devnull if(n != m)
301 bc7cb1a1 2003-11-23 devnull exits("write");
305 bc7cb1a1 2003-11-23 devnull tempout(void)
308 bc7cb1a1 2003-11-23 devnull Line **lp, *l;
309 bc7cb1a1 2003-11-23 devnull char *tf;
311 bc7cb1a1 2003-11-23 devnull Biobuf tb;
313 bc7cb1a1 2003-11-23 devnull sort4(args.linep, args.nline);
314 bc7cb1a1 2003-11-23 devnull tf = tempfile(args.ntemp);
315 bc7cb1a1 2003-11-23 devnull args.ntemp++;
316 bc7cb1a1 2003-11-23 devnull f = create(tf, OWRITE, 0666);
317 bc7cb1a1 2003-11-23 devnull if(f < 0) {
318 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: create %s: %r\n", tf);
319 bc7cb1a1 2003-11-23 devnull done("create");
322 bc7cb1a1 2003-11-23 devnull Binit(&tb, f, OWRITE);
323 bc7cb1a1 2003-11-23 devnull lp = args.linep;
324 bc7cb1a1 2003-11-23 devnull for(n=args.nline; n>0; n--) {
325 bc7cb1a1 2003-11-23 devnull l = *lp++;
326 bc7cb1a1 2003-11-23 devnull lineout(&tb, l);
327 bc7cb1a1 2003-11-23 devnull free(l->key);
328 bc7cb1a1 2003-11-23 devnull free(l);
330 bc7cb1a1 2003-11-23 devnull args.nline = 0;
331 bc7cb1a1 2003-11-23 devnull Bterm(&tb);
332 bc7cb1a1 2003-11-23 devnull close(f);
336 bc7cb1a1 2003-11-23 devnull done(char *xs)
340 bc7cb1a1 2003-11-23 devnull for(i=0; i<args.ntemp; i++)
341 bc7cb1a1 2003-11-23 devnull remove(tempfile(i));
342 bc7cb1a1 2003-11-23 devnull exits(xs);
346 bc7cb1a1 2003-11-23 devnull nomem(void)
348 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: out of memory\n");
349 bc7cb1a1 2003-11-23 devnull done("mem");
353 bc7cb1a1 2003-11-23 devnull tempfile(int n)
355 bc7cb1a1 2003-11-23 devnull static char file[100];
356 bc7cb1a1 2003-11-23 devnull static uint pid;
357 bc7cb1a1 2003-11-23 devnull char *dir;
359 c8b6342d 2005-01-13 devnull dir = "/var/tmp";
360 bc7cb1a1 2003-11-23 devnull if(args.tname)
361 bc7cb1a1 2003-11-23 devnull dir = args.tname;
362 bc7cb1a1 2003-11-23 devnull if(strlen(dir) >= nelem(file)-20) {
363 bc7cb1a1 2003-11-23 devnull fprint(2, "temp file directory name is too long: %s\n", dir);
364 bc7cb1a1 2003-11-23 devnull done("tdir");
367 bc7cb1a1 2003-11-23 devnull if(pid == 0) {
368 bc7cb1a1 2003-11-23 devnull pid = getpid();
369 bc7cb1a1 2003-11-23 devnull if(pid == 0) {
370 bc7cb1a1 2003-11-23 devnull pid = time(0);
371 bc7cb1a1 2003-11-23 devnull if(pid == 0)
372 bc7cb1a1 2003-11-23 devnull pid = 1;
376 bc7cb1a1 2003-11-23 devnull sprint(file, "%s/sort.%.4d.%.4d", dir, pid%10000, n);
377 bc7cb1a1 2003-11-23 devnull return file;
381 bc7cb1a1 2003-11-23 devnull mergeout(Biobuf *b)
383 bc7cb1a1 2003-11-23 devnull int n, i, f;
384 bc7cb1a1 2003-11-23 devnull char *tf;
385 bc7cb1a1 2003-11-23 devnull Biobuf tb;
387 bc7cb1a1 2003-11-23 devnull for(i=0; i<args.ntemp; i+=n) {
388 bc7cb1a1 2003-11-23 devnull n = args.ntemp - i;
389 bc7cb1a1 2003-11-23 devnull if(n > Nmerge) {
390 bc7cb1a1 2003-11-23 devnull tf = tempfile(args.ntemp);
391 bc7cb1a1 2003-11-23 devnull args.ntemp++;
392 bc7cb1a1 2003-11-23 devnull f = create(tf, OWRITE, 0666);
393 bc7cb1a1 2003-11-23 devnull if(f < 0) {
394 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: create %s: %r\n", tf);
395 bc7cb1a1 2003-11-23 devnull done("create");
397 bc7cb1a1 2003-11-23 devnull Binit(&tb, f, OWRITE);
399 bc7cb1a1 2003-11-23 devnull n = Nmerge;
400 bc7cb1a1 2003-11-23 devnull mergefiles(i, n, &tb);
402 bc7cb1a1 2003-11-23 devnull Bterm(&tb);
403 bc7cb1a1 2003-11-23 devnull close(f);
405 bc7cb1a1 2003-11-23 devnull mergefiles(i, n, b);
410 bc7cb1a1 2003-11-23 devnull mergefiles(int t, int n, Biobuf *b)
412 bc7cb1a1 2003-11-23 devnull Merge *m, *mp, **mmp;
413 bc7cb1a1 2003-11-23 devnull Key *ok;
414 bc7cb1a1 2003-11-23 devnull Line *l;
415 bc7cb1a1 2003-11-23 devnull char *tf;
416 bc7cb1a1 2003-11-23 devnull int i, f, nn;
418 bc7cb1a1 2003-11-23 devnull mmp = malloc(n*sizeof(*mmp));
419 bc7cb1a1 2003-11-23 devnull mp = malloc(n*sizeof(*mp));
420 bc7cb1a1 2003-11-23 devnull if(mmp == 0 || mp == 0)
421 bc7cb1a1 2003-11-23 devnull nomem();
425 bc7cb1a1 2003-11-23 devnull for(i=0; i<n; i++,m++) {
426 bc7cb1a1 2003-11-23 devnull tf = tempfile(t+i);
427 bc7cb1a1 2003-11-23 devnull f = open(tf, OREAD);
428 bc7cb1a1 2003-11-23 devnull if(f < 0) {
429 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: reopen %s: %r\n", tf);
430 bc7cb1a1 2003-11-23 devnull done("open");
432 bc7cb1a1 2003-11-23 devnull m->fd = f;
433 bc7cb1a1 2003-11-23 devnull Binit(&m->b, f, OREAD);
434 bc7cb1a1 2003-11-23 devnull mmp[nn] = m;
436 bc7cb1a1 2003-11-23 devnull l = newline(&m->b);
437 bc7cb1a1 2003-11-23 devnull if(l == 0)
438 bc7cb1a1 2003-11-23 devnull continue;
440 bc7cb1a1 2003-11-23 devnull m->line = l;
441 bc7cb1a1 2003-11-23 devnull m->key = l->key;
445 bc7cb1a1 2003-11-23 devnull for(;;) {
446 bc7cb1a1 2003-11-23 devnull sort4(mmp, nn);
447 bc7cb1a1 2003-11-23 devnull m = *mmp;
448 bc7cb1a1 2003-11-23 devnull if(nn == 0)
450 bc7cb1a1 2003-11-23 devnull for(;;) {
451 bc7cb1a1 2003-11-23 devnull l = m->line;
452 bc7cb1a1 2003-11-23 devnull if(args.uflag && ok && kcmp(ok, l->key) == 0) {
453 bc7cb1a1 2003-11-23 devnull free(l->key);
454 bc7cb1a1 2003-11-23 devnull free(l);
455 bc7cb1a1 2003-11-23 devnull } else {
456 bc7cb1a1 2003-11-23 devnull lineout(b, l);
458 bc7cb1a1 2003-11-23 devnull free(ok);
459 bc7cb1a1 2003-11-23 devnull ok = l->key;
460 bc7cb1a1 2003-11-23 devnull free(l);
463 bc7cb1a1 2003-11-23 devnull l = newline(&m->b);
464 bc7cb1a1 2003-11-23 devnull if(l == 0) {
466 bc7cb1a1 2003-11-23 devnull mmp[0] = mmp[nn];
469 bc7cb1a1 2003-11-23 devnull m->line = l;
470 bc7cb1a1 2003-11-23 devnull m->key = l->key;
471 bc7cb1a1 2003-11-23 devnull if(nn > 1 && kcmp(mmp[0]->key, mmp[1]->key) > 0)
476 bc7cb1a1 2003-11-23 devnull free(ok);
479 bc7cb1a1 2003-11-23 devnull for(i=0; i<n; i++,m++) {
480 bc7cb1a1 2003-11-23 devnull Bterm(&m->b);
481 bc7cb1a1 2003-11-23 devnull close(m->fd);
484 bc7cb1a1 2003-11-23 devnull free(mp);
485 bc7cb1a1 2003-11-23 devnull free(mmp);
489 bc7cb1a1 2003-11-23 devnull kcmp(Key *ka, Key *kb)
491 bc7cb1a1 2003-11-23 devnull int n, m;
494 bc7cb1a1 2003-11-23 devnull * set n to length of smaller key
496 bc7cb1a1 2003-11-23 devnull n = ka->klen;
497 bc7cb1a1 2003-11-23 devnull m = kb->klen;
498 bc7cb1a1 2003-11-23 devnull if(n > m)
500 bc7cb1a1 2003-11-23 devnull return memcmp(ka->key, kb->key, n);
504 bc7cb1a1 2003-11-23 devnull printout(Biobuf *b)
507 bc7cb1a1 2003-11-23 devnull Line **lp, *l;
508 bc7cb1a1 2003-11-23 devnull Key *ok;
510 bc7cb1a1 2003-11-23 devnull sort4(args.linep, args.nline);
511 bc7cb1a1 2003-11-23 devnull lp = args.linep;
513 bc7cb1a1 2003-11-23 devnull for(n=args.nline; n>0; n--) {
514 bc7cb1a1 2003-11-23 devnull l = *lp++;
515 bc7cb1a1 2003-11-23 devnull if(args.uflag && ok && kcmp(ok, l->key) == 0)
516 bc7cb1a1 2003-11-23 devnull continue;
517 bc7cb1a1 2003-11-23 devnull lineout(b, l);
518 bc7cb1a1 2003-11-23 devnull ok = l->key;
523 bc7cb1a1 2003-11-23 devnull setfield(int n, int c)
525 bc7cb1a1 2003-11-23 devnull Field *f;
527 bc7cb1a1 2003-11-23 devnull f = &args.field[n];
528 bc7cb1a1 2003-11-23 devnull switch(c) {
529 bc7cb1a1 2003-11-23 devnull default:
530 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: unknown option: field.%C\n", c);
531 bc7cb1a1 2003-11-23 devnull done("option");
532 bc7cb1a1 2003-11-23 devnull case 'b': /* skip blanks */
533 bc7cb1a1 2003-11-23 devnull f->flags |= Bflag;
535 bc7cb1a1 2003-11-23 devnull case 'd': /* directory order */
536 bc7cb1a1 2003-11-23 devnull f->flags |= Dflag;
538 bc7cb1a1 2003-11-23 devnull case 'f': /* fold case */
539 bc7cb1a1 2003-11-23 devnull f->flags |= Fflag;
541 bc7cb1a1 2003-11-23 devnull case 'g': /* floating point -n case */
542 bc7cb1a1 2003-11-23 devnull f->flags |= Gflag;
544 bc7cb1a1 2003-11-23 devnull case 'i': /* ignore non-ascii */
545 bc7cb1a1 2003-11-23 devnull f->flags |= Iflag;
547 bc7cb1a1 2003-11-23 devnull case 'M': /* month */
548 bc7cb1a1 2003-11-23 devnull f->flags |= Mflag;
550 bc7cb1a1 2003-11-23 devnull case 'n': /* numbers */
551 bc7cb1a1 2003-11-23 devnull f->flags |= Nflag;
553 bc7cb1a1 2003-11-23 devnull case 'r': /* reverse */
554 bc7cb1a1 2003-11-23 devnull f->flags |= Rflag;
556 bc7cb1a1 2003-11-23 devnull case 'w': /* ignore white */
557 bc7cb1a1 2003-11-23 devnull f->flags |= Wflag;
563 bc7cb1a1 2003-11-23 devnull dofield(char *s, int *n1, int *n2, int off1, int off2)
565 bc7cb1a1 2003-11-23 devnull int c, n;
567 bc7cb1a1 2003-11-23 devnull c = *s++;
568 bc7cb1a1 2003-11-23 devnull if(c >= '0' && c <= '9') {
570 bc7cb1a1 2003-11-23 devnull while(c >= '0' && c <= '9') {
571 bc7cb1a1 2003-11-23 devnull n = n*10 + (c-'0');
572 bc7cb1a1 2003-11-23 devnull c = *s++;
574 bc7cb1a1 2003-11-23 devnull n -= off1; /* posix committee: rot in hell */
575 bc7cb1a1 2003-11-23 devnull if(n < 0) {
576 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: field offset must be positive\n");
577 bc7cb1a1 2003-11-23 devnull done("option");
579 bc7cb1a1 2003-11-23 devnull *n1 = n;
581 bc7cb1a1 2003-11-23 devnull if(c == '.') {
582 bc7cb1a1 2003-11-23 devnull c = *s++;
583 bc7cb1a1 2003-11-23 devnull if(c >= '0' && c <= '9') {
585 bc7cb1a1 2003-11-23 devnull while(c >= '0' && c <= '9') {
586 bc7cb1a1 2003-11-23 devnull n = n*10 + (c-'0');
587 bc7cb1a1 2003-11-23 devnull c = *s++;
589 bc7cb1a1 2003-11-23 devnull n -= off2;
590 bc7cb1a1 2003-11-23 devnull if(n < 0) {
591 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: character offset must be positive\n");
592 bc7cb1a1 2003-11-23 devnull done("option");
594 bc7cb1a1 2003-11-23 devnull *n2 = n;
597 bc7cb1a1 2003-11-23 devnull while(c != 0) {
598 bc7cb1a1 2003-11-23 devnull setfield(args.nfield, c);
599 bc7cb1a1 2003-11-23 devnull c = *s++;
604 bc7cb1a1 2003-11-23 devnull printargs(void)
606 bc7cb1a1 2003-11-23 devnull int i, n;
607 bc7cb1a1 2003-11-23 devnull Field *f;
608 bc7cb1a1 2003-11-23 devnull char *prefix;
610 bc7cb1a1 2003-11-23 devnull fprint(2, "sort");
611 bc7cb1a1 2003-11-23 devnull for(i=0; i<=args.nfield; i++) {
612 bc7cb1a1 2003-11-23 devnull f = &args.field[i];
613 bc7cb1a1 2003-11-23 devnull prefix = " -";
615 bc7cb1a1 2003-11-23 devnull n = f->beg1;
616 bc7cb1a1 2003-11-23 devnull if(n >= 0)
617 bc7cb1a1 2003-11-23 devnull fprint(2, " +%d", n);
619 bc7cb1a1 2003-11-23 devnull fprint(2, " +*");
620 bc7cb1a1 2003-11-23 devnull n = f->beg2;
621 bc7cb1a1 2003-11-23 devnull if(n >= 0)
622 bc7cb1a1 2003-11-23 devnull fprint(2, ".%d", n);
624 bc7cb1a1 2003-11-23 devnull fprint(2, ".*");
626 bc7cb1a1 2003-11-23 devnull if(f->flags & B1flag)
627 bc7cb1a1 2003-11-23 devnull fprint(2, "b");
629 bc7cb1a1 2003-11-23 devnull n = f->end1;
630 bc7cb1a1 2003-11-23 devnull if(n >= 0)
631 bc7cb1a1 2003-11-23 devnull fprint(2, " -%d", n);
633 bc7cb1a1 2003-11-23 devnull fprint(2, " -*");
634 bc7cb1a1 2003-11-23 devnull n = f->end2;
635 bc7cb1a1 2003-11-23 devnull if(n >= 0)
636 bc7cb1a1 2003-11-23 devnull fprint(2, ".%d", n);
638 bc7cb1a1 2003-11-23 devnull fprint(2, ".*");
639 bc7cb1a1 2003-11-23 devnull prefix = "";
641 bc7cb1a1 2003-11-23 devnull if(f->flags & Bflag)
642 bc7cb1a1 2003-11-23 devnull fprint(2, "%sb", prefix);
643 bc7cb1a1 2003-11-23 devnull if(f->flags & Dflag)
644 bc7cb1a1 2003-11-23 devnull fprint(2, "%sd", prefix);
645 bc7cb1a1 2003-11-23 devnull if(f->flags & Fflag)
646 bc7cb1a1 2003-11-23 devnull fprint(2, "%sf", prefix);
647 bc7cb1a1 2003-11-23 devnull if(f->flags & Gflag)
648 bc7cb1a1 2003-11-23 devnull fprint(2, "%sg", prefix);
649 bc7cb1a1 2003-11-23 devnull if(f->flags & Iflag)
650 bc7cb1a1 2003-11-23 devnull fprint(2, "%si", prefix);
651 bc7cb1a1 2003-11-23 devnull if(f->flags & Mflag)
652 bc7cb1a1 2003-11-23 devnull fprint(2, "%sM", prefix);
653 bc7cb1a1 2003-11-23 devnull if(f->flags & Nflag)
654 bc7cb1a1 2003-11-23 devnull fprint(2, "%sn", prefix);
655 bc7cb1a1 2003-11-23 devnull if(f->flags & Rflag)
656 bc7cb1a1 2003-11-23 devnull fprint(2, "%sr", prefix);
657 bc7cb1a1 2003-11-23 devnull if(f->flags & Wflag)
658 bc7cb1a1 2003-11-23 devnull fprint(2, "%sw", prefix);
660 bc7cb1a1 2003-11-23 devnull if(args.cflag)
661 bc7cb1a1 2003-11-23 devnull fprint(2, " -c");
662 bc7cb1a1 2003-11-23 devnull if(args.uflag)
663 bc7cb1a1 2003-11-23 devnull fprint(2, " -u");
664 bc7cb1a1 2003-11-23 devnull if(args.ofile)
665 bc7cb1a1 2003-11-23 devnull fprint(2, " -o %s", args.ofile);
666 bc7cb1a1 2003-11-23 devnull if(args.mline != Nline)
667 bc7cb1a1 2003-11-23 devnull fprint(2, " -l %ld", args.mline);
668 bc7cb1a1 2003-11-23 devnull fprint(2, "\n");
672 bc7cb1a1 2003-11-23 devnull newfield(void)
675 bc7cb1a1 2003-11-23 devnull Field *f;
677 bc7cb1a1 2003-11-23 devnull n = args.nfield + 1;
678 bc7cb1a1 2003-11-23 devnull if(n >= Nfield) {
679 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: too many fields specified\n");
680 bc7cb1a1 2003-11-23 devnull done("option");
682 bc7cb1a1 2003-11-23 devnull args.nfield = n;
683 bc7cb1a1 2003-11-23 devnull f = &args.field[n];
684 bc7cb1a1 2003-11-23 devnull f->beg1 = -1;
685 bc7cb1a1 2003-11-23 devnull f->beg2 = -1;
686 bc7cb1a1 2003-11-23 devnull f->end1 = -1;
687 bc7cb1a1 2003-11-23 devnull f->end2 = -1;
691 bc7cb1a1 2003-11-23 devnull doargs(int argc, char *argv[])
693 bc7cb1a1 2003-11-23 devnull int i, c, hadplus;
694 bc7cb1a1 2003-11-23 devnull char *s, *p, *q;
695 bc7cb1a1 2003-11-23 devnull Field *f;
697 bc7cb1a1 2003-11-23 devnull hadplus = 0;
698 bc7cb1a1 2003-11-23 devnull args.mline = Nline;
699 bc7cb1a1 2003-11-23 devnull for(i=1; i<argc; i++) {
700 bc7cb1a1 2003-11-23 devnull s = argv[i];
701 bc7cb1a1 2003-11-23 devnull c = *s++;
702 bc7cb1a1 2003-11-23 devnull if(c == '-') {
704 bc7cb1a1 2003-11-23 devnull if(c == 0) /* forced end of arg marker */
706 bc7cb1a1 2003-11-23 devnull argv[i] = 0; /* clobber args processed */
707 bc7cb1a1 2003-11-23 devnull if(c == '.' || (c >= '0' && c <= '9')) {
708 bc7cb1a1 2003-11-23 devnull if(!hadplus)
709 bc7cb1a1 2003-11-23 devnull newfield();
710 bc7cb1a1 2003-11-23 devnull f = &args.field[args.nfield];
711 bc7cb1a1 2003-11-23 devnull dofield(s, &f->end1, &f->end2, 0, 0);
712 bc7cb1a1 2003-11-23 devnull hadplus = 0;
713 bc7cb1a1 2003-11-23 devnull continue;
716 bc7cb1a1 2003-11-23 devnull while(c = *s++)
717 bc7cb1a1 2003-11-23 devnull switch(c) {
718 bc7cb1a1 2003-11-23 devnull case '-': /* end of options */
719 bc7cb1a1 2003-11-23 devnull i = argc;
720 bc7cb1a1 2003-11-23 devnull continue;
721 bc7cb1a1 2003-11-23 devnull case 'T': /* temp directory */
722 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
724 bc7cb1a1 2003-11-23 devnull if(i < argc) {
725 bc7cb1a1 2003-11-23 devnull args.tname = argv[i];
726 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
729 bc7cb1a1 2003-11-23 devnull args.tname = s;
730 bc7cb1a1 2003-11-23 devnull s = strchr(s, 0);
732 bc7cb1a1 2003-11-23 devnull case 'o': /* output file */
733 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
735 bc7cb1a1 2003-11-23 devnull if(i < argc) {
736 bc7cb1a1 2003-11-23 devnull args.ofile = argv[i];
737 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
740 bc7cb1a1 2003-11-23 devnull args.ofile = s;
741 bc7cb1a1 2003-11-23 devnull s = strchr(s, 0);
743 bc7cb1a1 2003-11-23 devnull case 'k': /* posix key (what were they thinking?) */
745 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
747 bc7cb1a1 2003-11-23 devnull if(i < argc) {
748 bc7cb1a1 2003-11-23 devnull p = argv[i];
749 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
753 bc7cb1a1 2003-11-23 devnull s = strchr(s, 0);
754 bc7cb1a1 2003-11-23 devnull if(p == 0)
757 bc7cb1a1 2003-11-23 devnull newfield();
758 bc7cb1a1 2003-11-23 devnull q = strchr(p, ',');
760 bc7cb1a1 2003-11-23 devnull *q++ = 0;
761 bc7cb1a1 2003-11-23 devnull f = &args.field[args.nfield];
762 bc7cb1a1 2003-11-23 devnull dofield(p, &f->beg1, &f->beg2, 1, 1);
763 bc7cb1a1 2003-11-23 devnull if(f->flags & Bflag) {
764 bc7cb1a1 2003-11-23 devnull f->flags |= B1flag;
765 bc7cb1a1 2003-11-23 devnull f->flags &= ~Bflag;
768 bc7cb1a1 2003-11-23 devnull dofield(q, &f->end1, &f->end2, 1, 0);
769 bc7cb1a1 2003-11-23 devnull if(f->end2 <= 0)
770 bc7cb1a1 2003-11-23 devnull f->end1++;
772 bc7cb1a1 2003-11-23 devnull hadplus = 0;
774 bc7cb1a1 2003-11-23 devnull case 't': /* tab character */
775 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
777 bc7cb1a1 2003-11-23 devnull if(i < argc) {
778 bc7cb1a1 2003-11-23 devnull chartorune(&args.tabchar, argv[i]);
779 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
782 bc7cb1a1 2003-11-23 devnull s += chartorune(&args.tabchar, s);
783 bc7cb1a1 2003-11-23 devnull if(args.tabchar == '\n') {
784 bc7cb1a1 2003-11-23 devnull fprint(2, "aw come on, rob\n");
785 bc7cb1a1 2003-11-23 devnull done("rob");
788 bc7cb1a1 2003-11-23 devnull case 'c': /* check order */
789 bc7cb1a1 2003-11-23 devnull args.cflag = 1;
791 bc7cb1a1 2003-11-23 devnull case 'u': /* unique */
792 bc7cb1a1 2003-11-23 devnull args.uflag = 1;
794 bc7cb1a1 2003-11-23 devnull case 'v': /* debugging noise */
795 bc7cb1a1 2003-11-23 devnull args.vflag = 1;
797 bc7cb1a1 2003-11-23 devnull case 'l':
798 bc7cb1a1 2003-11-23 devnull if(*s == 0) {
800 bc7cb1a1 2003-11-23 devnull if(i < argc) {
801 bc7cb1a1 2003-11-23 devnull args.mline = atol(argv[i]);
802 bc7cb1a1 2003-11-23 devnull argv[i] = 0;
805 bc7cb1a1 2003-11-23 devnull args.mline = atol(s);
806 bc7cb1a1 2003-11-23 devnull s = strchr(s, 0);
809 bc7cb1a1 2003-11-23 devnull case 'M': /* month */
810 bc7cb1a1 2003-11-23 devnull case 'b': /* skip blanks */
811 bc7cb1a1 2003-11-23 devnull case 'd': /* directory order */
812 bc7cb1a1 2003-11-23 devnull case 'f': /* fold case */
813 bc7cb1a1 2003-11-23 devnull case 'g': /* floating numbers */
814 bc7cb1a1 2003-11-23 devnull case 'i': /* ignore non-ascii */
815 bc7cb1a1 2003-11-23 devnull case 'n': /* numbers */
816 bc7cb1a1 2003-11-23 devnull case 'r': /* reverse */
817 bc7cb1a1 2003-11-23 devnull case 'w': /* ignore white */
818 bc7cb1a1 2003-11-23 devnull if(args.nfield > 0)
819 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: global field set after -k\n");
820 bc7cb1a1 2003-11-23 devnull setfield(0, c);
822 bc7cb1a1 2003-11-23 devnull case 'm':
823 bc7cb1a1 2003-11-23 devnull /* option m silently ignored but required by posix */
825 bc7cb1a1 2003-11-23 devnull default:
826 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: unknown option: -%C\n", c);
827 bc7cb1a1 2003-11-23 devnull done("option");
829 bc7cb1a1 2003-11-23 devnull continue;
831 bc7cb1a1 2003-11-23 devnull if(c == '+') {
832 bc7cb1a1 2003-11-23 devnull argv[i] = 0; /* clobber args processed */
834 bc7cb1a1 2003-11-23 devnull if(c == '.' || (c >= '0' && c <= '9')) {
835 bc7cb1a1 2003-11-23 devnull newfield();
836 bc7cb1a1 2003-11-23 devnull f = &args.field[args.nfield];
837 bc7cb1a1 2003-11-23 devnull dofield(s, &f->beg1, &f->beg2, 0, 0);
838 bc7cb1a1 2003-11-23 devnull if(f->flags & Bflag) {
839 bc7cb1a1 2003-11-23 devnull f->flags |= B1flag;
840 bc7cb1a1 2003-11-23 devnull f->flags &= ~Bflag;
842 bc7cb1a1 2003-11-23 devnull hadplus = 1;
843 bc7cb1a1 2003-11-23 devnull continue;
845 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: unknown option: +%C\n", c);
846 bc7cb1a1 2003-11-23 devnull done("option");
848 bc7cb1a1 2003-11-23 devnull args.nfile++;
851 bc7cb1a1 2003-11-23 devnull for(i=0; i<=args.nfield; i++) {
852 bc7cb1a1 2003-11-23 devnull f = &args.field[i];
855 bc7cb1a1 2003-11-23 devnull * global options apply to fields that
856 bc7cb1a1 2003-11-23 devnull * specify no options
858 bc7cb1a1 2003-11-23 devnull if(f->flags == 0) {
859 bc7cb1a1 2003-11-23 devnull f->flags = args.field[0].flags;
860 bc7cb1a1 2003-11-23 devnull if(args.field[0].flags & Bflag)
861 bc7cb1a1 2003-11-23 devnull f->flags |= B1flag;
866 bc7cb1a1 2003-11-23 devnull * build buildkey specification
868 bc7cb1a1 2003-11-23 devnull switch(f->flags & ~(Bflag|B1flag)) {
869 bc7cb1a1 2003-11-23 devnull default:
870 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: illegal combination of flags: %lx\n", f->flags);
871 bc7cb1a1 2003-11-23 devnull done("option");
873 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_;
875 bc7cb1a1 2003-11-23 devnull case Rflag:
876 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_r;
878 bc7cb1a1 2003-11-23 devnull case Gflag:
879 bc7cb1a1 2003-11-23 devnull case Nflag:
880 bc7cb1a1 2003-11-23 devnull case Gflag|Nflag:
881 bc7cb1a1 2003-11-23 devnull case Gflag|Rflag:
882 bc7cb1a1 2003-11-23 devnull case Nflag|Rflag:
883 bc7cb1a1 2003-11-23 devnull case Gflag|Nflag|Rflag:
884 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_gn;
886 bc7cb1a1 2003-11-23 devnull case Mflag:
887 bc7cb1a1 2003-11-23 devnull case Mflag|Rflag:
888 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_m;
889 bc7cb1a1 2003-11-23 devnull makemapm(f);
891 bc7cb1a1 2003-11-23 devnull case Dflag:
892 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag:
893 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Iflag:
894 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Iflag|Rflag:
895 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Iflag|Rflag|Wflag:
896 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Iflag|Wflag:
897 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Rflag:
898 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Rflag|Wflag:
899 bc7cb1a1 2003-11-23 devnull case Dflag|Fflag|Wflag:
900 bc7cb1a1 2003-11-23 devnull case Dflag|Iflag:
901 bc7cb1a1 2003-11-23 devnull case Dflag|Iflag|Rflag:
902 bc7cb1a1 2003-11-23 devnull case Dflag|Iflag|Rflag|Wflag:
903 bc7cb1a1 2003-11-23 devnull case Dflag|Iflag|Wflag:
904 bc7cb1a1 2003-11-23 devnull case Dflag|Rflag:
905 bc7cb1a1 2003-11-23 devnull case Dflag|Rflag|Wflag:
906 bc7cb1a1 2003-11-23 devnull case Dflag|Wflag:
907 bc7cb1a1 2003-11-23 devnull case Fflag:
908 bc7cb1a1 2003-11-23 devnull case Fflag|Iflag:
909 bc7cb1a1 2003-11-23 devnull case Fflag|Iflag|Rflag:
910 bc7cb1a1 2003-11-23 devnull case Fflag|Iflag|Rflag|Wflag:
911 bc7cb1a1 2003-11-23 devnull case Fflag|Iflag|Wflag:
912 bc7cb1a1 2003-11-23 devnull case Fflag|Rflag:
913 bc7cb1a1 2003-11-23 devnull case Fflag|Rflag|Wflag:
914 bc7cb1a1 2003-11-23 devnull case Fflag|Wflag:
915 bc7cb1a1 2003-11-23 devnull case Iflag:
916 bc7cb1a1 2003-11-23 devnull case Iflag|Rflag:
917 bc7cb1a1 2003-11-23 devnull case Iflag|Rflag|Wflag:
918 bc7cb1a1 2003-11-23 devnull case Iflag|Wflag:
919 bc7cb1a1 2003-11-23 devnull case Wflag:
920 bc7cb1a1 2003-11-23 devnull f->dokey = dokey_dfi;
921 bc7cb1a1 2003-11-23 devnull makemapd(f);
927 bc7cb1a1 2003-11-23 devnull * random spot checks
929 bc7cb1a1 2003-11-23 devnull if(args.nfile > 1 && args.cflag) {
930 bc7cb1a1 2003-11-23 devnull fprint(2, "sort: -c can have at most one input file\n");
931 bc7cb1a1 2003-11-23 devnull done("option");
937 bc7cb1a1 2003-11-23 devnull skip(uchar *l, int n1, int n2, int bflag, int endfield)
939 bc7cb1a1 2003-11-23 devnull int i, c, tc;
942 bc7cb1a1 2003-11-23 devnull if(endfield && n1 < 0)
943 bc7cb1a1 2003-11-23 devnull return 0;
945 bc7cb1a1 2003-11-23 devnull c = *l++;
946 bc7cb1a1 2003-11-23 devnull tc = args.tabchar;
947 bc7cb1a1 2003-11-23 devnull if(tc) {
948 bc7cb1a1 2003-11-23 devnull if(tc < Runeself) {
949 bc7cb1a1 2003-11-23 devnull for(i=n1; i>0; i--) {
950 bc7cb1a1 2003-11-23 devnull while(c != tc) {
951 bc7cb1a1 2003-11-23 devnull if(c == '\n')
952 bc7cb1a1 2003-11-23 devnull return 0;
953 bc7cb1a1 2003-11-23 devnull c = *l++;
955 bc7cb1a1 2003-11-23 devnull if(!(endfield && i == 1))
956 bc7cb1a1 2003-11-23 devnull c = *l++;
958 bc7cb1a1 2003-11-23 devnull } else {
960 bc7cb1a1 2003-11-23 devnull l += chartorune(&r, (char*)l);
961 bc7cb1a1 2003-11-23 devnull for(i=n1; i>0; i--) {
962 bc7cb1a1 2003-11-23 devnull while(r != tc) {
963 bc7cb1a1 2003-11-23 devnull if(r == '\n')
964 bc7cb1a1 2003-11-23 devnull return 0;
965 bc7cb1a1 2003-11-23 devnull l += chartorune(&r, (char*)l);
967 bc7cb1a1 2003-11-23 devnull if(!(endfield && i == 1))
968 bc7cb1a1 2003-11-23 devnull l += chartorune(&r, (char*)l);
972 bc7cb1a1 2003-11-23 devnull } else {
973 bc7cb1a1 2003-11-23 devnull for(i=n1; i>0; i--) {
974 bc7cb1a1 2003-11-23 devnull while(c == ' ' || c == '\t')
975 bc7cb1a1 2003-11-23 devnull c = *l++;
976 bc7cb1a1 2003-11-23 devnull while(c != ' ' && c != '\t') {
977 bc7cb1a1 2003-11-23 devnull if(c == '\n')
978 bc7cb1a1 2003-11-23 devnull return 0;
979 bc7cb1a1 2003-11-23 devnull c = *l++;
984 bc7cb1a1 2003-11-23 devnull if(bflag)
985 bc7cb1a1 2003-11-23 devnull while(c == ' ' || c == '\t')
986 bc7cb1a1 2003-11-23 devnull c = *l++;
989 bc7cb1a1 2003-11-23 devnull for(i=n2; i>0; i--) {
991 bc7cb1a1 2003-11-23 devnull if(c < Runeself) {
992 bc7cb1a1 2003-11-23 devnull if(c == '\n')
993 bc7cb1a1 2003-11-23 devnull return 0;
995 bc7cb1a1 2003-11-23 devnull continue;
997 bc7cb1a1 2003-11-23 devnull l += chartorune(&r, (char*)l);
999 bc7cb1a1 2003-11-23 devnull return l;
1003 bc7cb1a1 2003-11-23 devnull dokey_gn(Key *k, uchar *lp, uchar *lpe, Field *f)
1005 bc7cb1a1 2003-11-23 devnull uchar *kp;
1006 bc7cb1a1 2003-11-23 devnull int c, cl, dp;
1007 bc7cb1a1 2003-11-23 devnull int state, nzero, exp, expsign, rflag;
1009 bc7cb1a1 2003-11-23 devnull cl = k->klen + 3;
1010 bc7cb1a1 2003-11-23 devnull kp = k->key + cl; /* skip place for sign, exponent[2] */
1012 bc7cb1a1 2003-11-23 devnull nzero = 0; /* number of trailing zeros */
1013 bc7cb1a1 2003-11-23 devnull exp = 0; /* value of the exponent */
1014 bc7cb1a1 2003-11-23 devnull expsign = 0; /* sign of the exponent */
1015 bc7cb1a1 2003-11-23 devnull dp = 0x4040; /* location of decimal point */
1016 bc7cb1a1 2003-11-23 devnull rflag = f->flags&Rflag; /* xor of rflag and - sign */
1017 bc7cb1a1 2003-11-23 devnull state = NSstart;
1019 bc7cb1a1 2003-11-23 devnull for(;; lp++) {
1020 bc7cb1a1 2003-11-23 devnull if(lp >= lpe)
1022 bc7cb1a1 2003-11-23 devnull c = *lp;
1024 bc7cb1a1 2003-11-23 devnull if(c == ' ' || c == '\t') {
1025 bc7cb1a1 2003-11-23 devnull switch(state) {
1026 bc7cb1a1 2003-11-23 devnull case NSstart:
1027 bc7cb1a1 2003-11-23 devnull case NSsign:
1028 bc7cb1a1 2003-11-23 devnull continue;
1032 bc7cb1a1 2003-11-23 devnull if(c == '+' || c == '-') {
1033 bc7cb1a1 2003-11-23 devnull switch(state) {
1034 bc7cb1a1 2003-11-23 devnull case NSstart:
1035 bc7cb1a1 2003-11-23 devnull state = NSsign;
1036 bc7cb1a1 2003-11-23 devnull if(c == '-')
1037 bc7cb1a1 2003-11-23 devnull rflag = !rflag;
1038 bc7cb1a1 2003-11-23 devnull continue;
1039 bc7cb1a1 2003-11-23 devnull case NSexp:
1040 bc7cb1a1 2003-11-23 devnull state = NSexpsign;
1041 bc7cb1a1 2003-11-23 devnull if(c == '-')
1042 bc7cb1a1 2003-11-23 devnull expsign = 1;
1043 bc7cb1a1 2003-11-23 devnull continue;
1047 bc7cb1a1 2003-11-23 devnull if(c == '0') {
1048 bc7cb1a1 2003-11-23 devnull switch(state) {
1049 bc7cb1a1 2003-11-23 devnull case NSdigit:
1050 bc7cb1a1 2003-11-23 devnull if(rflag)
1051 bc7cb1a1 2003-11-23 devnull c = ~c;
1052 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1054 bc7cb1a1 2003-11-23 devnull nzero++;
1056 bc7cb1a1 2003-11-23 devnull state = NSdigit;
1057 bc7cb1a1 2003-11-23 devnull continue;
1058 bc7cb1a1 2003-11-23 devnull case NSfract:
1059 bc7cb1a1 2003-11-23 devnull if(rflag)
1060 bc7cb1a1 2003-11-23 devnull c = ~c;
1061 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1063 bc7cb1a1 2003-11-23 devnull nzero++;
1064 bc7cb1a1 2003-11-23 devnull state = NSfract;
1065 bc7cb1a1 2003-11-23 devnull continue;
1066 bc7cb1a1 2003-11-23 devnull case NSstart:
1067 bc7cb1a1 2003-11-23 devnull case NSsign:
1068 bc7cb1a1 2003-11-23 devnull case NSzero:
1069 bc7cb1a1 2003-11-23 devnull state = NSzero;
1070 bc7cb1a1 2003-11-23 devnull continue;
1071 bc7cb1a1 2003-11-23 devnull case NSzerofract:
1072 bc7cb1a1 2003-11-23 devnull case NSpoint:
1074 bc7cb1a1 2003-11-23 devnull state = NSzerofract;
1075 bc7cb1a1 2003-11-23 devnull continue;
1076 bc7cb1a1 2003-11-23 devnull case NSexpsign:
1077 bc7cb1a1 2003-11-23 devnull case NSexp:
1078 bc7cb1a1 2003-11-23 devnull case NSexpdigit:
1079 bc7cb1a1 2003-11-23 devnull exp = exp*10 + (c - '0');
1080 bc7cb1a1 2003-11-23 devnull state = NSexpdigit;
1081 bc7cb1a1 2003-11-23 devnull continue;
1085 bc7cb1a1 2003-11-23 devnull if(c >= '1' && c <= '9') {
1086 bc7cb1a1 2003-11-23 devnull switch(state) {
1087 bc7cb1a1 2003-11-23 devnull case NSzero:
1088 bc7cb1a1 2003-11-23 devnull case NSstart:
1089 bc7cb1a1 2003-11-23 devnull case NSsign:
1090 bc7cb1a1 2003-11-23 devnull case NSdigit:
1091 bc7cb1a1 2003-11-23 devnull if(rflag)
1092 bc7cb1a1 2003-11-23 devnull c = ~c;
1093 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1095 bc7cb1a1 2003-11-23 devnull nzero = 0;
1097 bc7cb1a1 2003-11-23 devnull state = NSdigit;
1098 bc7cb1a1 2003-11-23 devnull continue;
1099 bc7cb1a1 2003-11-23 devnull case NSzerofract:
1100 bc7cb1a1 2003-11-23 devnull case NSpoint:
1101 bc7cb1a1 2003-11-23 devnull case NSfract:
1102 bc7cb1a1 2003-11-23 devnull if(rflag)
1103 bc7cb1a1 2003-11-23 devnull c = ~c;
1104 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1106 bc7cb1a1 2003-11-23 devnull nzero = 0;
1107 bc7cb1a1 2003-11-23 devnull state = NSfract;
1108 bc7cb1a1 2003-11-23 devnull continue;
1109 bc7cb1a1 2003-11-23 devnull case NSexpsign:
1110 bc7cb1a1 2003-11-23 devnull case NSexp:
1111 bc7cb1a1 2003-11-23 devnull case NSexpdigit:
1112 bc7cb1a1 2003-11-23 devnull exp = exp*10 + (c - '0');
1113 bc7cb1a1 2003-11-23 devnull state = NSexpdigit;
1114 bc7cb1a1 2003-11-23 devnull continue;
1118 bc7cb1a1 2003-11-23 devnull if(c == '.') {
1119 bc7cb1a1 2003-11-23 devnull switch(state) {
1120 bc7cb1a1 2003-11-23 devnull case NSstart:
1121 bc7cb1a1 2003-11-23 devnull case NSsign:
1122 bc7cb1a1 2003-11-23 devnull state = NSpoint;
1123 bc7cb1a1 2003-11-23 devnull continue;
1124 bc7cb1a1 2003-11-23 devnull case NSzero:
1125 bc7cb1a1 2003-11-23 devnull state = NSzerofract;
1126 bc7cb1a1 2003-11-23 devnull continue;
1127 bc7cb1a1 2003-11-23 devnull case NSdigit:
1128 bc7cb1a1 2003-11-23 devnull state = NSfract;
1129 bc7cb1a1 2003-11-23 devnull continue;
1133 bc7cb1a1 2003-11-23 devnull if((f->flags & Gflag) && (c == 'e' || c == 'E')) {
1134 bc7cb1a1 2003-11-23 devnull switch(state) {
1135 bc7cb1a1 2003-11-23 devnull case NSdigit:
1136 bc7cb1a1 2003-11-23 devnull case NSfract:
1137 bc7cb1a1 2003-11-23 devnull state = NSexp;
1138 bc7cb1a1 2003-11-23 devnull continue;
1145 bc7cb1a1 2003-11-23 devnull switch(state) {
1147 bc7cb1a1 2003-11-23 devnull * result is zero
1149 bc7cb1a1 2003-11-23 devnull case NSstart:
1150 bc7cb1a1 2003-11-23 devnull case NSsign:
1151 bc7cb1a1 2003-11-23 devnull case NSzero:
1152 bc7cb1a1 2003-11-23 devnull case NSzerofract:
1153 bc7cb1a1 2003-11-23 devnull case NSpoint:
1154 bc7cb1a1 2003-11-23 devnull kp = k->key + k->klen;
1155 bc7cb1a1 2003-11-23 devnull k->klen += 2;
1156 bc7cb1a1 2003-11-23 devnull kp[0] = 0x20; /* between + and - */
1157 bc7cb1a1 2003-11-23 devnull kp[1] = 0;
1158 bc7cb1a1 2003-11-23 devnull return;
1160 bc7cb1a1 2003-11-23 devnull * result has exponent
1162 bc7cb1a1 2003-11-23 devnull case NSexpsign:
1163 bc7cb1a1 2003-11-23 devnull case NSexp:
1164 bc7cb1a1 2003-11-23 devnull case NSexpdigit:
1165 bc7cb1a1 2003-11-23 devnull if(expsign)
1166 bc7cb1a1 2003-11-23 devnull exp = -exp;
1167 bc7cb1a1 2003-11-23 devnull dp += exp;
1170 bc7cb1a1 2003-11-23 devnull * result is fixed point number
1172 bc7cb1a1 2003-11-23 devnull case NSdigit:
1173 bc7cb1a1 2003-11-23 devnull case NSfract:
1174 bc7cb1a1 2003-11-23 devnull kp -= nzero;
1175 bc7cb1a1 2003-11-23 devnull cl -= nzero;
1180 bc7cb1a1 2003-11-23 devnull * end of number
1183 bc7cb1a1 2003-11-23 devnull if(rflag)
1184 bc7cb1a1 2003-11-23 devnull c = ~c;
1185 bc7cb1a1 2003-11-23 devnull *kp = c;
1188 bc7cb1a1 2003-11-23 devnull * sign and exponent
1190 bc7cb1a1 2003-11-23 devnull c = 0x30;
1191 bc7cb1a1 2003-11-23 devnull if(rflag) {
1192 bc7cb1a1 2003-11-23 devnull c = 0x10;
1193 bc7cb1a1 2003-11-23 devnull dp = ~dp;
1195 bc7cb1a1 2003-11-23 devnull kp = k->key + k->klen;
1196 bc7cb1a1 2003-11-23 devnull kp[0] = c;
1197 bc7cb1a1 2003-11-23 devnull kp[1] = (dp >> 8);
1198 bc7cb1a1 2003-11-23 devnull kp[2] = dp;
1199 bc7cb1a1 2003-11-23 devnull k->klen = cl+1;
1203 bc7cb1a1 2003-11-23 devnull dokey_m(Key *k, uchar *lp, uchar *lpe, Field *f)
1205 bc7cb1a1 2003-11-23 devnull uchar *kp;
1206 bc7cb1a1 2003-11-23 devnull Rune r, place[3];
1207 bc7cb1a1 2003-11-23 devnull int c, cl, pc;
1208 bc7cb1a1 2003-11-23 devnull int rflag;
1210 bc7cb1a1 2003-11-23 devnull rflag = f->flags&Rflag;
1211 bc7cb1a1 2003-11-23 devnull pc = 0;
1213 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1214 bc7cb1a1 2003-11-23 devnull kp = k->key + cl;
1216 bc7cb1a1 2003-11-23 devnull for(;;) {
1218 bc7cb1a1 2003-11-23 devnull * get the character
1220 bc7cb1a1 2003-11-23 devnull if(lp >= lpe)
1222 bc7cb1a1 2003-11-23 devnull c = *lp;
1223 bc7cb1a1 2003-11-23 devnull if(c >= Runeself) {
1224 bc7cb1a1 2003-11-23 devnull lp += chartorune(&r, (char*)lp);
1229 bc7cb1a1 2003-11-23 devnull if(c < nelem(f->mapto)) {
1230 bc7cb1a1 2003-11-23 devnull c = f->mapto[c];
1231 bc7cb1a1 2003-11-23 devnull if(c == 0)
1232 bc7cb1a1 2003-11-23 devnull continue;
1234 bc7cb1a1 2003-11-23 devnull place[pc++] = c;
1235 bc7cb1a1 2003-11-23 devnull if(pc < 3)
1236 bc7cb1a1 2003-11-23 devnull continue;
1237 bc7cb1a1 2003-11-23 devnull for(c=11; c>=0; c--)
1238 bc7cb1a1 2003-11-23 devnull if(memcmp(month[c], place, sizeof(place)) == 0)
1240 bc7cb1a1 2003-11-23 devnull c += 10;
1241 bc7cb1a1 2003-11-23 devnull if(rflag)
1242 bc7cb1a1 2003-11-23 devnull c = ~c;
1243 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1249 bc7cb1a1 2003-11-23 devnull if(rflag)
1250 bc7cb1a1 2003-11-23 devnull c = ~c;
1251 bc7cb1a1 2003-11-23 devnull *kp = c;
1252 bc7cb1a1 2003-11-23 devnull k->klen = cl+1;
1256 bc7cb1a1 2003-11-23 devnull dokey_dfi(Key *k, uchar *lp, uchar *lpe, Field *f)
1258 bc7cb1a1 2003-11-23 devnull uchar *kp;
1259 bc7cb1a1 2003-11-23 devnull Rune r;
1260 bc7cb1a1 2003-11-23 devnull int c, cl, n, rflag;
1262 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1263 bc7cb1a1 2003-11-23 devnull kp = k->key + cl;
1264 bc7cb1a1 2003-11-23 devnull rflag = f->flags & Rflag;
1266 bc7cb1a1 2003-11-23 devnull for(;;) {
1268 bc7cb1a1 2003-11-23 devnull * get the character
1270 bc7cb1a1 2003-11-23 devnull if(lp >= lpe)
1272 bc7cb1a1 2003-11-23 devnull c = *lp;
1273 bc7cb1a1 2003-11-23 devnull if(c >= Runeself) {
1274 bc7cb1a1 2003-11-23 devnull lp += chartorune(&r, (char*)lp);
1280 bc7cb1a1 2003-11-23 devnull * do the various mappings.
1281 bc7cb1a1 2003-11-23 devnull * the common case is handled
1282 bc7cb1a1 2003-11-23 devnull * completely by the table.
1284 bc7cb1a1 2003-11-23 devnull if(c != 0 && c < Runeself) {
1285 bc7cb1a1 2003-11-23 devnull c = f->mapto[c];
1286 bc7cb1a1 2003-11-23 devnull if(c) {
1287 bc7cb1a1 2003-11-23 devnull *kp++ = c;
1290 bc7cb1a1 2003-11-23 devnull continue;
1294 bc7cb1a1 2003-11-23 devnull * for characters out of range,
1295 bc7cb1a1 2003-11-23 devnull * the table does not do Rflag.
1296 bc7cb1a1 2003-11-23 devnull * ignore is based on mapto[255]
1298 bc7cb1a1 2003-11-23 devnull if(c != 0 && c < nelem(f->mapto)) {
1299 bc7cb1a1 2003-11-23 devnull c = f->mapto[c];
1300 bc7cb1a1 2003-11-23 devnull if(c == 0)
1301 bc7cb1a1 2003-11-23 devnull continue;
1303 bc7cb1a1 2003-11-23 devnull if(f->mapto[nelem(f->mapto)-1] == 0)
1304 bc7cb1a1 2003-11-23 devnull continue;
1307 bc7cb1a1 2003-11-23 devnull * put it in the key
1310 bc7cb1a1 2003-11-23 devnull n = runetochar((char*)kp, &r);
1311 bc7cb1a1 2003-11-23 devnull kp += n;
1312 bc7cb1a1 2003-11-23 devnull cl += n;
1313 bc7cb1a1 2003-11-23 devnull if(rflag)
1314 bc7cb1a1 2003-11-23 devnull while(n > 0) {
1315 bc7cb1a1 2003-11-23 devnull kp[-n] = ~kp[-n];
1321 bc7cb1a1 2003-11-23 devnull * end of key
1323 bc7cb1a1 2003-11-23 devnull k->klen = cl+1;
1324 bc7cb1a1 2003-11-23 devnull if(rflag) {
1325 bc7cb1a1 2003-11-23 devnull *kp = ~0;
1326 bc7cb1a1 2003-11-23 devnull return;
1328 bc7cb1a1 2003-11-23 devnull *kp = 0;
1332 bc7cb1a1 2003-11-23 devnull dokey_r(Key *k, uchar *lp, uchar *lpe, Field *f)
1334 bc7cb1a1 2003-11-23 devnull int cl, n;
1335 bc7cb1a1 2003-11-23 devnull uchar *kp;
1337 bc7cb1a1 2003-11-23 devnull USED(f);
1338 bc7cb1a1 2003-11-23 devnull n = lpe - lp;
1339 bc7cb1a1 2003-11-23 devnull if(n < 0)
1341 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1342 bc7cb1a1 2003-11-23 devnull kp = k->key + cl;
1343 bc7cb1a1 2003-11-23 devnull k->klen = cl+n+1;
1345 bc7cb1a1 2003-11-23 devnull lpe -= 3;
1346 bc7cb1a1 2003-11-23 devnull while(lp < lpe) {
1347 bc7cb1a1 2003-11-23 devnull kp[0] = ~lp[0];
1348 bc7cb1a1 2003-11-23 devnull kp[1] = ~lp[1];
1349 bc7cb1a1 2003-11-23 devnull kp[2] = ~lp[2];
1350 bc7cb1a1 2003-11-23 devnull kp[3] = ~lp[3];
1351 bc7cb1a1 2003-11-23 devnull kp += 4;
1352 bc7cb1a1 2003-11-23 devnull lp += 4;
1355 bc7cb1a1 2003-11-23 devnull lpe += 3;
1356 bc7cb1a1 2003-11-23 devnull while(lp < lpe)
1357 bc7cb1a1 2003-11-23 devnull *kp++ = ~*lp++;
1358 bc7cb1a1 2003-11-23 devnull *kp = ~0;
1362 bc7cb1a1 2003-11-23 devnull dokey_(Key *k, uchar *lp, uchar *lpe, Field *f)
1364 bc7cb1a1 2003-11-23 devnull int n, cl;
1365 bc7cb1a1 2003-11-23 devnull uchar *kp;
1367 bc7cb1a1 2003-11-23 devnull USED(f);
1368 bc7cb1a1 2003-11-23 devnull n = lpe - lp;
1369 bc7cb1a1 2003-11-23 devnull if(n < 0)
1371 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1372 bc7cb1a1 2003-11-23 devnull kp = k->key + cl;
1373 bc7cb1a1 2003-11-23 devnull k->klen = cl+n+1;
1374 bc7cb1a1 2003-11-23 devnull memmove(kp, lp, n);
1375 bc7cb1a1 2003-11-23 devnull kp[n] = 0;
1379 bc7cb1a1 2003-11-23 devnull buildkey(Line *l)
1381 bc7cb1a1 2003-11-23 devnull Key *k;
1382 bc7cb1a1 2003-11-23 devnull uchar *lp, *lpe;
1383 bc7cb1a1 2003-11-23 devnull int ll, kl, cl, i, n;
1384 bc7cb1a1 2003-11-23 devnull Field *f;
1386 bc7cb1a1 2003-11-23 devnull ll = l->llen - 1;
1387 bc7cb1a1 2003-11-23 devnull kl = 0; /* allocated length */
1388 bc7cb1a1 2003-11-23 devnull cl = 0; /* current length */
1391 bc7cb1a1 2003-11-23 devnull for(i=1; i<=args.nfield; i++) {
1392 bc7cb1a1 2003-11-23 devnull f = &args.field[i];
1393 bc7cb1a1 2003-11-23 devnull lp = skip(l->line, f->beg1, f->beg2, f->flags&B1flag, 0);
1394 bc7cb1a1 2003-11-23 devnull if(lp == 0)
1395 bc7cb1a1 2003-11-23 devnull lp = l->line + ll;
1396 bc7cb1a1 2003-11-23 devnull lpe = skip(l->line, f->end1, f->end2, f->flags&Bflag, 1);
1397 bc7cb1a1 2003-11-23 devnull if(lpe == 0)
1398 bc7cb1a1 2003-11-23 devnull lpe = l->line + ll;
1399 bc7cb1a1 2003-11-23 devnull n = (lpe - lp) + 1;
1400 bc7cb1a1 2003-11-23 devnull if(n <= 0)
1402 bc7cb1a1 2003-11-23 devnull if(cl+(n+4) > kl) {
1403 bc7cb1a1 2003-11-23 devnull kl = cl+(n+4);
1404 bc7cb1a1 2003-11-23 devnull k = realloc(k, sizeof(Key) +
1405 bc7cb1a1 2003-11-23 devnull (kl-1)*sizeof(k->key[0]));
1406 bc7cb1a1 2003-11-23 devnull if(k == 0)
1407 bc7cb1a1 2003-11-23 devnull nomem();
1409 bc7cb1a1 2003-11-23 devnull k->klen = cl;
1410 bc7cb1a1 2003-11-23 devnull (*f->dokey)(k, lp, lpe, f);
1411 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1415 bc7cb1a1 2003-11-23 devnull * global comparisons
1417 bc7cb1a1 2003-11-23 devnull if(!(args.uflag && cl > 0)) {
1418 bc7cb1a1 2003-11-23 devnull f = &args.field[0];
1419 bc7cb1a1 2003-11-23 devnull if(cl+(ll+4) > kl) {
1420 bc7cb1a1 2003-11-23 devnull kl = cl+(ll+4);
1421 bc7cb1a1 2003-11-23 devnull k = realloc(k, sizeof(Key) +
1422 bc7cb1a1 2003-11-23 devnull (kl-1)*sizeof(k->key[0]));
1423 bc7cb1a1 2003-11-23 devnull if(k == 0)
1424 bc7cb1a1 2003-11-23 devnull nomem();
1426 bc7cb1a1 2003-11-23 devnull k->klen = cl;
1427 bc7cb1a1 2003-11-23 devnull (*f->dokey)(k, l->line, l->line+ll, f);
1428 bc7cb1a1 2003-11-23 devnull cl = k->klen;
1431 bc7cb1a1 2003-11-23 devnull l->key = k;
1432 bc7cb1a1 2003-11-23 devnull k->klen = cl;
1434 bc7cb1a1 2003-11-23 devnull if(args.vflag) {
1435 bc7cb1a1 2003-11-23 devnull write(2, l->line, l->llen);
1436 bc7cb1a1 2003-11-23 devnull for(i=0; i<k->klen; i++) {
1437 bc7cb1a1 2003-11-23 devnull fprint(2, " %.2x", k->key[i]);
1438 bc7cb1a1 2003-11-23 devnull if(k->key[i] == 0x00 || k->key[i] == 0xff)
1439 bc7cb1a1 2003-11-23 devnull fprint(2, "\n");
1445 bc7cb1a1 2003-11-23 devnull makemapm(Field *f)
1447 bc7cb1a1 2003-11-23 devnull int i, c;
1449 bc7cb1a1 2003-11-23 devnull for(i=0; i<nelem(f->mapto); i++) {
1451 bc7cb1a1 2003-11-23 devnull if(i == ' ' || i == '\t')
1453 bc7cb1a1 2003-11-23 devnull if(i >= 'a' && i <= 'z')
1454 bc7cb1a1 2003-11-23 devnull c = i + ('A' - 'a');
1455 bc7cb1a1 2003-11-23 devnull if(i >= 'A' && i <= 'Z')
1457 bc7cb1a1 2003-11-23 devnull f->mapto[i] = c;
1458 bc7cb1a1 2003-11-23 devnull if(args.vflag) {
1459 bc7cb1a1 2003-11-23 devnull if((i & 15) == 0)
1460 bc7cb1a1 2003-11-23 devnull fprint(2, " ");
1461 bc7cb1a1 2003-11-23 devnull fprint(2, " %.2x", c);
1462 bc7cb1a1 2003-11-23 devnull if((i & 15) == 15)
1463 bc7cb1a1 2003-11-23 devnull fprint(2, "\n");
1469 bc7cb1a1 2003-11-23 devnull makemapd(Field *f)
1471 bc7cb1a1 2003-11-23 devnull int i, j, c;
1473 bc7cb1a1 2003-11-23 devnull for(i=0; i<nelem(f->mapto); i++) {
1475 bc7cb1a1 2003-11-23 devnull if(f->flags & Iflag)
1476 bc7cb1a1 2003-11-23 devnull if(c < 040 || c > 0176)
1477 bc7cb1a1 2003-11-23 devnull c = -1;
1478 bc7cb1a1 2003-11-23 devnull if((f->flags & Wflag) && c >= 0)
1479 bc7cb1a1 2003-11-23 devnull if(c == ' ' || c == '\t')
1480 bc7cb1a1 2003-11-23 devnull c = -1;
1481 bc7cb1a1 2003-11-23 devnull if((f->flags & Dflag) && c >= 0)
1482 bc7cb1a1 2003-11-23 devnull if(!(c == ' ' || c == '\t' ||
1483 bc7cb1a1 2003-11-23 devnull (c >= 'a' && c <= 'z') ||
1484 bc7cb1a1 2003-11-23 devnull (c >= 'A' && c <= 'Z') ||
1485 bc7cb1a1 2003-11-23 devnull (c >= '0' && c <= '9'))) {
1486 bc7cb1a1 2003-11-23 devnull for(j=0; latinmap[j]; j+=3)
1487 bc7cb1a1 2003-11-23 devnull if(c == latinmap[j+0] ||
1488 bc7cb1a1 2003-11-23 devnull c == latinmap[j+1])
1490 bc7cb1a1 2003-11-23 devnull if(latinmap[j] == 0)
1491 bc7cb1a1 2003-11-23 devnull c = -1;
1493 bc7cb1a1 2003-11-23 devnull if((f->flags & Fflag) && c >= 0) {
1494 bc7cb1a1 2003-11-23 devnull if(c >= 'a' && c <= 'z')
1495 bc7cb1a1 2003-11-23 devnull c += 'A' - 'a';
1496 bc7cb1a1 2003-11-23 devnull for(j=0; latinmap[j]; j+=3)
1497 bc7cb1a1 2003-11-23 devnull if(c == latinmap[j+0] ||
1498 bc7cb1a1 2003-11-23 devnull c == latinmap[j+1]) {
1499 bc7cb1a1 2003-11-23 devnull c = latinmap[j+2];
1503 bc7cb1a1 2003-11-23 devnull if((f->flags & Rflag) && c >= 0 && i > 0 && i < Runeself)
1504 bc7cb1a1 2003-11-23 devnull c = ~c & 0xff;
1505 bc7cb1a1 2003-11-23 devnull if(c < 0)
1507 bc7cb1a1 2003-11-23 devnull f->mapto[i] = c;
1508 bc7cb1a1 2003-11-23 devnull if(args.vflag) {
1509 bc7cb1a1 2003-11-23 devnull if((i & 15) == 0)
1510 bc7cb1a1 2003-11-23 devnull fprint(2, " ");
1511 bc7cb1a1 2003-11-23 devnull fprint(2, " %.2x", c);
1512 bc7cb1a1 2003-11-23 devnull if((i & 15) == 15)
1513 bc7cb1a1 2003-11-23 devnull fprint(2, "\n");
1518 bc7cb1a1 2003-11-23 devnull int latinmap[] =
1520 bc7cb1a1 2003-11-23 devnull /* lcase ucase fold */
1521 bc7cb1a1 2003-11-23 devnull 0xe0, 0xc0, 0x41, /* L'à', L'À', L'A', */
1522 bc7cb1a1 2003-11-23 devnull 0xe1, 0xc1, 0x41, /* L'á', L'Á', L'A', */
1523 bc7cb1a1 2003-11-23 devnull 0xe2, 0xc2, 0x41, /* L'â', L'Â', L'A', */
1524 bc7cb1a1 2003-11-23 devnull 0xe4, 0xc4, 0x41, /* L'ä', L'Ä', L'A', */
1525 bc7cb1a1 2003-11-23 devnull 0xe3, 0xc3, 0x41, /* L'ã', L'Ã', L'A', */
1526 bc7cb1a1 2003-11-23 devnull 0xe5, 0xc5, 0x41, /* L'å', L'Å', L'A', */
1527 bc7cb1a1 2003-11-23 devnull 0xe8, 0xc8, 0x45, /* L'è', L'È', L'E', */
1528 bc7cb1a1 2003-11-23 devnull 0xe9, 0xc9, 0x45, /* L'é', L'É', L'E', */
1529 bc7cb1a1 2003-11-23 devnull 0xea, 0xca, 0x45, /* L'ê', L'Ê', L'E', */
1530 bc7cb1a1 2003-11-23 devnull 0xeb, 0xcb, 0x45, /* L'ë', L'Ë', L'E', */
1531 bc7cb1a1 2003-11-23 devnull 0xec, 0xcc, 0x49, /* L'ì', L'Ì', L'I', */
1532 bc7cb1a1 2003-11-23 devnull 0xed, 0xcd, 0x49, /* L'í', L'Í', L'I', */
1533 bc7cb1a1 2003-11-23 devnull 0xee, 0xce, 0x49, /* L'î', L'Î', L'I', */
1534 bc7cb1a1 2003-11-23 devnull 0xef, 0xcf, 0x49, /* L'ï', L'Ï', L'I', */
1535 bc7cb1a1 2003-11-23 devnull 0xf2, 0xd2, 0x4f, /* L'ò', L'Ò', L'O', */
1536 bc7cb1a1 2003-11-23 devnull 0xf3, 0xd3, 0x4f, /* L'ó', L'Ó', L'O', */
1537 bc7cb1a1 2003-11-23 devnull 0xf4, 0xd4, 0x4f, /* L'ô', L'Ô', L'O', */
1538 bc7cb1a1 2003-11-23 devnull 0xf6, 0xd6, 0x4f, /* L'ö', L'Ö', L'O', */
1539 bc7cb1a1 2003-11-23 devnull 0xf5, 0xd5, 0x4f, /* L'õ', L'Õ', L'O', */
1540 bc7cb1a1 2003-11-23 devnull 0xf8, 0xd8, 0x4f, /* L'ø', L'Ø', L'O', */
1541 bc7cb1a1 2003-11-23 devnull 0xf9, 0xd9, 0x55, /* L'ù', L'Ù', L'U', */
1542 bc7cb1a1 2003-11-23 devnull 0xfa, 0xda, 0x55, /* L'ú', L'Ú', L'U', */
1543 bc7cb1a1 2003-11-23 devnull 0xfb, 0xdb, 0x55, /* L'û', L'Û', L'U', */
1544 bc7cb1a1 2003-11-23 devnull 0xfc, 0xdc, 0x55, /* L'ü', L'Ü', L'U', */
1545 bc7cb1a1 2003-11-23 devnull 0xe6, 0xc6, 0x41, /* L'æ', L'Æ', L'A', */
1546 bc7cb1a1 2003-11-23 devnull 0xf0, 0xd0, 0x44, /* L'ð', L'Ð', L'D', */
1547 bc7cb1a1 2003-11-23 devnull 0xf1, 0xd1, 0x4e, /* L'ñ', L'Ñ', L'N', */
1548 bc7cb1a1 2003-11-23 devnull 0xfd, 0xdd, 0x59, /* L'ý', L'Ý', L'Y', */
1549 bc7cb1a1 2003-11-23 devnull 0xe7, 0xc7, 0x43, /* L'ç', L'Ç', L'C', */
1553 bc7cb1a1 2003-11-23 devnull Rune LJAN[] = { 'J', 'A', 'N', 0 };
1554 bc7cb1a1 2003-11-23 devnull Rune LFEB[] = { 'F', 'E', 'B', 0 };
1555 bc7cb1a1 2003-11-23 devnull Rune LMAR[] = { 'M', 'A', 'R', 0 };
1556 bc7cb1a1 2003-11-23 devnull Rune LAPR[] = { 'A', 'P', 'R', 0 };
1557 bc7cb1a1 2003-11-23 devnull Rune LMAY[] = { 'M', 'A', 'Y', 0 };
1558 bc7cb1a1 2003-11-23 devnull Rune LJUN[] = { 'J', 'U', 'N', 0 };
1559 bc7cb1a1 2003-11-23 devnull Rune LJUL[] = { 'J', 'U', 'L', 0 };
1560 bc7cb1a1 2003-11-23 devnull Rune LAUG[] = { 'A', 'U', 'G', 0 };
1561 bc7cb1a1 2003-11-23 devnull Rune LSEP[] = { 'S', 'E', 'P', 0 };
1562 bc7cb1a1 2003-11-23 devnull Rune LOCT[] = { 'O', 'C', 'T', 0 };
1563 bc7cb1a1 2003-11-23 devnull Rune LNOV[] = { 'N', 'O', 'V', 0 };
1564 bc7cb1a1 2003-11-23 devnull Rune LDEC[] = { 'D', 'E', 'C', 0 };
1566 bc7cb1a1 2003-11-23 devnull Rune* month[12] =
1582 bc7cb1a1 2003-11-23 devnull /************** radix sort ***********/
1586 cbeb0b26 2006-04-01 devnull Threshold = 14
1589 bc7cb1a1 2003-11-23 devnull void rsort4(Key***, ulong, int);
1590 bc7cb1a1 2003-11-23 devnull void bsort4(Key***, ulong, int);
1593 bc7cb1a1 2003-11-23 devnull sort4(void *a, ulong n)
1595 bc7cb1a1 2003-11-23 devnull if(n > Threshold)
1596 bc7cb1a1 2003-11-23 devnull rsort4((Key***)a, n, 0);
1598 bc7cb1a1 2003-11-23 devnull bsort4((Key***)a, n, 0);
1602 bc7cb1a1 2003-11-23 devnull rsort4(Key ***a, ulong n, int b)
1604 bc7cb1a1 2003-11-23 devnull Key ***ea, ***t, ***u, **t1, **u1, *k;
1605 bc7cb1a1 2003-11-23 devnull Key ***part[257];
1606 bc7cb1a1 2003-11-23 devnull static long count[257];
1607 bc7cb1a1 2003-11-23 devnull long clist[257+257], *cp, *cp1;
1608 bc7cb1a1 2003-11-23 devnull int c, lowc, higc;
1611 bc7cb1a1 2003-11-23 devnull * pass 1 over all keys,
1612 bc7cb1a1 2003-11-23 devnull * count the number of each key[b].
1613 bc7cb1a1 2003-11-23 devnull * find low count and high count.
1615 bc7cb1a1 2003-11-23 devnull lowc = 256;
1616 bc7cb1a1 2003-11-23 devnull higc = 0;
1617 bc7cb1a1 2003-11-23 devnull ea = a+n;
1618 bc7cb1a1 2003-11-23 devnull for(t=a; t<ea; t++) {
1619 bc7cb1a1 2003-11-23 devnull k = **t;
1620 bc7cb1a1 2003-11-23 devnull n = k->klen;
1621 bc7cb1a1 2003-11-23 devnull if(b >= n) {
1622 bc7cb1a1 2003-11-23 devnull count[256]++;
1623 bc7cb1a1 2003-11-23 devnull continue;
1625 bc7cb1a1 2003-11-23 devnull c = k->key[b];
1626 bc7cb1a1 2003-11-23 devnull n = count[c]++;
1627 bc7cb1a1 2003-11-23 devnull if(n == 0) {
1628 bc7cb1a1 2003-11-23 devnull if(c < lowc)
1629 bc7cb1a1 2003-11-23 devnull lowc = c;
1630 bc7cb1a1 2003-11-23 devnull if(c > higc)
1631 bc7cb1a1 2003-11-23 devnull higc = c;
1636 bc7cb1a1 2003-11-23 devnull * pass 2 over all counts,
1637 bc7cb1a1 2003-11-23 devnull * put partition pointers in part[c].
1638 bc7cb1a1 2003-11-23 devnull * save compacted indexes and counts
1639 bc7cb1a1 2003-11-23 devnull * in clist[].
1642 bc7cb1a1 2003-11-23 devnull n = count[256];
1643 bc7cb1a1 2003-11-23 devnull clist[0] = n;
1644 bc7cb1a1 2003-11-23 devnull part[256] = t;
1645 bc7cb1a1 2003-11-23 devnull t += n;
1647 bc7cb1a1 2003-11-23 devnull cp1 = clist+1;
1648 bc7cb1a1 2003-11-23 devnull cp = count+lowc;
1649 bc7cb1a1 2003-11-23 devnull for(c=lowc; c<=higc; c++,cp++) {
1650 bc7cb1a1 2003-11-23 devnull n = *cp;
1651 bc7cb1a1 2003-11-23 devnull if(n) {
1652 bc7cb1a1 2003-11-23 devnull cp1[0] = n;
1653 bc7cb1a1 2003-11-23 devnull cp1[1] = c;
1654 bc7cb1a1 2003-11-23 devnull cp1 += 2;
1655 bc7cb1a1 2003-11-23 devnull part[c] = t;
1656 bc7cb1a1 2003-11-23 devnull t += n;
1659 bc7cb1a1 2003-11-23 devnull *cp1 = 0;
1662 bc7cb1a1 2003-11-23 devnull * pass 3 over all counts.
1663 bc7cb1a1 2003-11-23 devnull * chase lowest pointer in each partition
1664 bc7cb1a1 2003-11-23 devnull * around a permutation until it comes
1665 bc7cb1a1 2003-11-23 devnull * back and is stored where it started.
1666 bc7cb1a1 2003-11-23 devnull * static array, count[], should be
1667 bc7cb1a1 2003-11-23 devnull * reduced to zero entries except maybe
1668 bc7cb1a1 2003-11-23 devnull * count[256].
1670 bc7cb1a1 2003-11-23 devnull for(cp1=clist+1; cp1[0]; cp1+=2) {
1671 bc7cb1a1 2003-11-23 devnull c = cp1[1];
1672 bc7cb1a1 2003-11-23 devnull cp = count+c;
1673 bc7cb1a1 2003-11-23 devnull while(*cp) {
1674 bc7cb1a1 2003-11-23 devnull t1 = *part[c];
1675 bc7cb1a1 2003-11-23 devnull for(;;) {
1676 bc7cb1a1 2003-11-23 devnull k = *t1;
1677 bc7cb1a1 2003-11-23 devnull n = 256;
1678 bc7cb1a1 2003-11-23 devnull if(b < k->klen)
1679 bc7cb1a1 2003-11-23 devnull n = k->key[b];
1680 bc7cb1a1 2003-11-23 devnull u = part[n]++;
1681 bc7cb1a1 2003-11-23 devnull count[n]--;
1682 bc7cb1a1 2003-11-23 devnull u1 = *u;
1683 bc7cb1a1 2003-11-23 devnull *u = t1;
1684 bc7cb1a1 2003-11-23 devnull if(n == c)
1686 bc7cb1a1 2003-11-23 devnull t1 = u1;
1692 bc7cb1a1 2003-11-23 devnull * pass 4 over all partitions.
1693 bc7cb1a1 2003-11-23 devnull * call recursively.
1696 bc7cb1a1 2003-11-23 devnull t = a + clist[0];
1697 bc7cb1a1 2003-11-23 devnull count[256] = 0;
1698 bc7cb1a1 2003-11-23 devnull for(cp1=clist+1; n=cp1[0]; cp1+=2) {
1699 bc7cb1a1 2003-11-23 devnull if(n > Threshold)
1700 bc7cb1a1 2003-11-23 devnull rsort4(t, n, b);
1702 bc7cb1a1 2003-11-23 devnull if(n > 1)
1703 bc7cb1a1 2003-11-23 devnull bsort4(t, n, b);
1704 bc7cb1a1 2003-11-23 devnull t += n;
1709 bc7cb1a1 2003-11-23 devnull * bubble sort to pick up
1710 bc7cb1a1 2003-11-23 devnull * the pieces.
1713 bc7cb1a1 2003-11-23 devnull bsort4(Key ***a, ulong n, int b)
1715 bc7cb1a1 2003-11-23 devnull Key ***i, ***j, ***k, ***l, **t;
1716 bc7cb1a1 2003-11-23 devnull Key *ka, *kb;
1717 bc7cb1a1 2003-11-23 devnull int n1, n2;
1719 bc7cb1a1 2003-11-23 devnull l = a+n;
1725 bc7cb1a1 2003-11-23 devnull if(j >= l)
1726 bc7cb1a1 2003-11-23 devnull return;
1728 bc7cb1a1 2003-11-23 devnull ka = **i;
1729 bc7cb1a1 2003-11-23 devnull kb = **j;
1730 bc7cb1a1 2003-11-23 devnull n1 = ka->klen - b;
1731 bc7cb1a1 2003-11-23 devnull n2 = kb->klen - b;
1732 bc7cb1a1 2003-11-23 devnull if(n1 > n2)
1733 bc7cb1a1 2003-11-23 devnull n1 = n2;
1734 bc7cb1a1 2003-11-23 devnull if(n1 <= 0)
1735 bc7cb1a1 2003-11-23 devnull goto loop;
1736 bc7cb1a1 2003-11-23 devnull n2 = ka->key[b] - kb->key[b];
1737 bc7cb1a1 2003-11-23 devnull if(n2 == 0)
1738 bc7cb1a1 2003-11-23 devnull n2 = memcmp(ka->key+b, kb->key+b, n1);
1739 bc7cb1a1 2003-11-23 devnull if(n2 <= 0)
1740 bc7cb1a1 2003-11-23 devnull goto loop;
1742 bc7cb1a1 2003-11-23 devnull for(;;) {
1743 bc7cb1a1 2003-11-23 devnull k = i+1;
1745 bc7cb1a1 2003-11-23 devnull t = *k;
1746 bc7cb1a1 2003-11-23 devnull *k = *i;
1747 bc7cb1a1 2003-11-23 devnull *i = t;
1749 bc7cb1a1 2003-11-23 devnull if(i <= a)
1750 bc7cb1a1 2003-11-23 devnull goto loop;
1753 bc7cb1a1 2003-11-23 devnull ka = **i;
1754 bc7cb1a1 2003-11-23 devnull kb = *t;
1755 bc7cb1a1 2003-11-23 devnull n1 = ka->klen - b;
1756 bc7cb1a1 2003-11-23 devnull n2 = kb->klen - b;
1757 bc7cb1a1 2003-11-23 devnull if(n1 > n2)
1758 bc7cb1a1 2003-11-23 devnull n1 = n2;
1759 bc7cb1a1 2003-11-23 devnull if(n1 <= 0)
1760 bc7cb1a1 2003-11-23 devnull goto loop;
1761 bc7cb1a1 2003-11-23 devnull n2 = ka->key[b] - kb->key[b];
1762 bc7cb1a1 2003-11-23 devnull if(n2 == 0)
1763 bc7cb1a1 2003-11-23 devnull n2 = memcmp(ka->key+b, kb->key+b, n1);
1764 bc7cb1a1 2003-11-23 devnull if(n2 <= 0)
1765 bc7cb1a1 2003-11-23 devnull goto loop;