![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to bprint.out CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / sort|
Return to bprint.out CVS log | Up to [Research Unix] / researchv10no / cmd / sort |
1.1 root 1: number.c:
2:
3: /* Copyright 1990, AT&T Bell Labs */
4:
5: /* Canonicalize the number string pointed to by dp, of length
6: len. Put the result in kp.
7:
8: A field of length zero, or all blank, is regarded as 0.
9: Over/underflow is rendered as huge or zero and properly signed.
10: It happens 1e+-1022.
11:
12: Canonicalized strings may be compared as strings of unsigned
13: chars. For good measure, a canonical string has no zero bytes.
14:
15: Syntax: optionally signed floating point, with optional
16: leading spaces. A syntax deviation ends the number.
17:
18: Form of output: packed in 4-bit nibbles. First
19: 3 nibbles count the number N of significant digits
20: before the decimal point. The quantity actually stored
21: is 2048+sign(x)*(N+1024). Further nibbles contain
22: 1 decimal digit d each, stored as d+2 if x is positive
23: and as 10-d if x is negative. Leading and trailing
24: zeros are stripped, and a trailing "digit" d = -1
25: is appended. (The trailing digit handled like all others,
26: so encodes as 1 or 0xb according to the sign of x.)
27: An odd number of nibbles is padded with zero.
28:
29: Buglet: overflow is reported if output is exactly filled.
30:
31: */
32: #include "fsort.h"
33:
34: #define encode(x) (neg? 10-(x): (x)+2)
35: #define putdig(x) (nib? (*dig=encode(x)<<4, nib=0): \
36: (*dig++|=encode(x), nib=1))
37:
38: static int gflag;
39:
40: int
41: gcode(uchar *dp, uchar*kp, int len, struct field *f)
42: <60>{
43: int ret;
44: <60>gflag++;
45: <60>ret = ncode(dp, kp, len, f);
46: <60>gflag--;
47: return <60>ret;
48: }
49:
50: int
51: ncode(uchar *dp, uchar*kp, int len, struct field *f)
52: <374264>{
53: uchar *dig = <374264>kp + 1; /* byte for next digit */
54: int nib = <374264>0; /* high nibble 1, low nibble 0 */
55: uchar *cp = <374264>dp;
56: uchar *ep = <374264>cp + len; /* end pointer */
57: int zeros = <374264>0; /* count zeros seen but not installed */
58: int sigdig = <374264>1024;
59: int neg = <374264>f->rflag; /* 0 for +, 1 for - */
60: int decimal = <374264>0;
61: int n, inv;
62:
63: <374264>kp[1] = 0;
64: for( <374264>; <418322>cp<ep ; <44058>cp++) /* eat blanks */
65: if(<418322>*cp!=' ' && <374272>*cp!='\t')
66: <374264>break;
67: if(<374264>cp < ep) /* eat sign */
68: switch(<374264>*cp) {
69: case '-':
70: <218>neg ^= 1;
71: case '+':
72: <225>cp++;
73: }
74: for( <374264>; <707527>cp<ep; <333263>cp++) /* eat leading zeros */
75: if(<707511>*cp != '0')
76: <374248>break;
77: if(<374264>*cp=='.' && <331112>cp<ep) { /* decimal point among lead zeros */
78: <331112>decimal++;
79: for(<331112>cp++; <367735>cp<ep; <36623>cp++) {
80: if(<367735>*cp != '0')
81: <331112>break;
82: <36623>sigdig--;
83: }
84: }
85: if(<374264>*cp>'9' || <374255>*cp<'0' || <373799>cp>=ep) { /* no sig digit*/
86: <465>sigdig = 0;
87: <465>neg = 0;
88: <465>goto retzero;
89: }
90: for( <373799>; <2405784>cp<ep; <2031985>cp++) {
91: switch(<2071744>*cp) {
92: default:
93: <39726>goto out;
94: case '.':
95: if(<16>decimal)
96: <2>goto out;
97: <14>decimal++;
98: <14>continue;
99: case '0':
100: <132382>zeros++;
101: if(<132382>!decimal)
102: <3976>sigdig++;
103: <132382>continue;
104: case '1': case '2': case '3': case '4': case '5':
105: case '6': case '7': case '8': case '9':
106: for( <1899589>; <2027985>zeros>0; <128396>zeros--)
107: <128396>putdig<65793>(0);
108: <1899589>n = *cp - '0';
109: <1899589>putdig<929380>(n);
110: if(<1899589>!decimal)
111: <77803>sigdig++;
112: <1899589>continue;
113: case 'e':
114: case 'E':
115: if(<31>!gflag)
116: <6>goto out;
117: <25>inv = 1;
118: if(<25>cp < ep) switch(<25>*++cp) {
119: case '-':
120: <13>inv = -1;
121: case '+':
122: <15>cp++;
123: }
124: if(<25>*cp>'9' || <25>*cp<'0' || <21>cp>=ep)
125: <4>goto out;
126: for(<21>n=0; <62>cp<ep; <41>cp++) {
127: int c = <44>*cp;
128: if(<44>c<'0' || <44>c>'9')
129: <3>break;
130: if(<41>(n = 10*n+c-'0') >= 0)
131: <41>continue;
132: <0>sigdig = 2047*inv;
133: <0>goto out;
134: }
135: <21>sigdig += n*inv;
136: <21>goto out;
137: }
138: }
139: out:
140: if(<373799>sigdig<0 || <373799>sigdig>=2047) {
141: <0>sigdig = sigdig<0? <0>0: <0>2047;
142: <0>warn("numeric field overflow", (char*)dp, len);
143: <0>dig = kp + 1;
144: <0>*dig = 0;
145: <0>nib = 0;
146: }
147: retzero:
148: if(<374264>neg)
149: <219>sigdig = 2048 - sigdig;
150: else
151: <374045>sigdig = 2048 + sigdig;
152: <374264>kp[0] = sigdig >> 4;
153: <374264>kp[1] |= sigdig << 4;
154: <374264>putdig<37639>(-1);
155: return <374264>dig - kp + 1 - nib;
156: }
157: rsort.c:
158:
159: /* Copyright 1990, AT&T Bell Labs */
160: #include "fsort.h"
161:
162: /* Radix sort by bytes. Records are chained in a list.
163: There are up to 257 bins at each recursion level.
164: The "null bin" is for short strings that have run out;
165: the rest are for byte values 0-255 */
166:
167: int aflag = 0;
168: int uflag = 0;
169: int rflag = 0;
170: int sflag = 0;
171:
172: /* Sort the list s by distributing according to
173: digit d into an array of bins, sorting the bins
174: recursively, and re-collecting them back into the list.
175: If uflag is nonzero return only 1 representative of
176: each equivalence class. The squeeze step noted
177: below determines what bins are in use, and squeezes
178: those into a stack frame, which is contiguous to s.
179: The null bin is handled separately to cut the span
180: of the squeeze loop.
181: Precondition: length(s) > 1 */
182:
183: #define tiebreak(t) \
184: if(uflag) { \
185: t->tail = !aflag? t->head: \
186: listaccum(t->head, t->tail); \
187: t->tail->next = 0; \
188: } else if(keyed && !sflag && t->head->next) { \
189: rflag = fields[0].rflag; \
190: keyed = 0; \
191: sort(t, 0); \
192: keyed = 1; \
193: rflag = 0; \
194: } else
195:
196: void
197: sort(struct list *s, int d)
198: <126745>{
199: extern int uflag;
200: struct list *t;
201: struct rec *r, *q;
202: struct list *frame = <126745>s + 1; /* stack frame */
203: static struct list bins[257];
204: # define nullbin (bins+256)
205: int nbin; /* number of filled bins */
206: struct list *low; /* lowest unsorted nonnull bin */
207: loop:
208: <447576>r = s->head;
209: <447576>low = bins + 256;
210: <447576>nbin = 0;
211: while(<3688466>r) {
212: if(<3240890>keyed)
213: if(<1334292>r->klen > (len_t)d)
214: <1116270>t = bins + key(r)[d];
215: else
216: <218022>t = nullbin;
217: else
218: if(<1906598>r->dlen > (len_t)d)
219: <1714238>t = bins + data(r)[d];
220: else
221: <192360>t = nullbin;
222: if(<3240890>t->head == 0) {
223: if(<555902>low > t)
224: <363502>low = t;
225: <555902>t->head = r;
226: <555902>nbin++;
227: } else
228: <2684988>t->tail->next = r; /* stable sort */
229: <3240890>t->tail = r;
230: <3240890>r = r->next;
231: }
232: <447576>t = frame; /* t is stack top */
233: if(<447576>t+nbin > stackmax)
234: <0>fatal("stack overflow", "", 0);
235: # define push(b) /* onto stack */ \
236: *t = *b, \
237: t->tail->next = 0, \
238: t++, \
239: b->head = 0, \
240: nbin--
241: if(<447576>nullbin->head)
242: <106517>push(nullbin);
243: for( <447576>; <1381435>nbin>0; <933859>low++)
244: if(<933859>low->head)
245: <449385>push(low);
246: if(<447576>t == frame+1) { /* tail recursion */
247: /* debug(frame, t, d);*/
248: <427056>r = frame->head;
249: if(<427056>r->len[keyed] <= d) {
250: <106225>tiebreak(<26635>frame);
251: <106225>*s = *frame;
252: return<106225>; /* string ran out */
253: }
254: <320831>d++;
255: <320831>goto loop;
256: }
257: /* debug(frame, t, d);*/
258: <20520>t--;
259: if(<20520>t->head->next) /* skip 1-item list */
260: <13713>sort(t, d+1);
261: if(<20520>!rflag) { /* forward order */
262: <15796>r = t->tail;
263: while(<112441>t > frame) {
264: <96645>q = t->head;
265: if(<96645>(--t>frame || <15796>t->head->len[keyed]>d)
266: && <96353>t->head->next)
267: <82209>sort(t, d+1);
268: else if(<14436>t==frame)
269: <3163>tiebreak(t);<295>
270: <96645>t->tail->next = q; /* concatenate */
271: }
272: <15796>s->head = frame->head;
273: <15796>s->tail = r;
274: } else { /* reverse order */
275: <4724>r = t->head;
276: while(<16405>t > frame) {
277: <11681>q = t->tail;
278: if(<11681>(--t>frame || <4724>t->head->len[keyed]>d)
279: && <11681>t->head->next)
280: <4070>sort(t, d+1);
281: else if(<7611>t==frame)
282: <3881>tiebreak(t);<1360>
283: <11681>q->next = t->head; /* concatenate */
284: }
285: <4724>s->head = r;
286: <4724>s->tail = frame->tail;
287: }
288: /* printf("return\n"); debug(s,s+1,d);*/
289: <20520>}
290:
291: /*
292: debug(struct list *stack, struct list *top, int d)
293: {
294: printf("----------------------level %d\n", d);
295: while(stack<top) {
296: printout(stack->head, stdout, "stdout");
297: printf("----------------------\n");
298: stack++;
299: }
300: }
301: */
302: merge.c:
303:
304: /* Copyright 1990, AT&T Bell Labs */
305: #include <stdlib.h>
306: #include <string.h>
307: #include "fsort.h"
308:
309: char *disorder = "key out of order";
310: char *duplicate = "duplicate key";
311: char *space = "out of space for merging";
312:
313: enum { IEOF, IOK };
314: enum { IPRE = 01000, IFOL = 02000 }; /* see find() */
315: enum { NMERGE = 16 };
316:
317: int nmerge = NMERGE; /* max number of files to merge at once */
318: int nextfile;
319:
320: struct merge { /* current record in an open file */
321: char *name; /* name of file (for diagnostics) */
322: FILE *file;
323: struct rec *rec; /* pointer to the data (and key) */
324: short serial; /* file no., breaks ties for stable sort */
325: short del; /* delete at close */
326: };
327:
328: struct merge *mfile; /* one struct per open file */
329: struct merge **f; /* pointers to mfile, ordered by content */
330:
331: static void mergephase(int, char*);
332: static int find(int, int*);
333: static int fillrec(struct merge*);
334: static int compare(struct merge*, struct merge*);
335: static void syncerr(struct merge*, char*);
336: extern int link(char*, char*);
337: extern int unlink(char*);
338: static void recinit(int nf, int nm, int n);
339: static void mv(int, int);
340:
341: static void
342: recalloc(struct merge *m)
343: <1241>{
344: if(<1241>m->rec)
345: return<784>; /* hygiene; doesn't happen */
346: <457>m->rec = (struct rec*)malloc(MINREC);
347: if(<457>m->rec == 0)
348: <0>fatal(space, "", 0);
349: <457>m->rec->dlen = 0;
350: <457>m->rec->next = (struct rec*)((uchar*)m->rec + MINREC);
351: <457>}
352:
353: /* misfortune : all fields are parsed and converted
354: before comparison. Lazy parsing might be in order,
355: but it's too hard to contemplate */
356:
357: /* Merge strategy, to merge N inputs in groups of at most M.
358: Numbers, like (1), are keyed to comments in code.
359: If N <= M, merge everything. (4)
360: If N > M*(M-1)+1
361: greedily merge M at a time (1) to reduce to the next case.
362: Merge x bunches of M (3) and one bunch of y (2),
363: then merge the x+1 new files (4) with the remaining z files
364: in an exactly M-way merge. Calculate x,y,z thus:
365: Mx + y + z = N file count
366: x + 1 + z = M final merge
367: 2 <= y <= M
368: x >= 0
369: z >= 0
370: by algebra
371: (M-1)x + y = N-M+1
372: y == (N-M+1) mod (M-1), 2 <= y <= M
373: x == (n-M+1-y)/(M-1)
374: Total cost is Mx + y + N. (Strategy due to P. McIlroy.) */
375:
376: /* merge n files. the first unmerged temp file is nm (i.e.
377: nm is the number of already merged files). the first
378: unmerged input file is nf.
379: rename temp files to keep a dense set beginning at 0
380: (It seems silly to rename 100 files after merging
381: every 1; how much time does that actually cost?) */
382: void
383: merge1(int nf, int nm, int n)
384: <161>{
385: char *name;
386: int i, j;
387: int flag = <161>nf<nfiles;
388: <161>recinit(nf, nm, n);
389: <161>name = filename(nextfile++);
390: <161>mergephase(n, name);
391: <161>free(name);
392: if(<161>flag)
393: return<137>;
394: <24>mv(--nextfile, nm);
395: for(<24>i=nm+n, j=nm+1; <180>i<nextfile; <156>i++, j++)
396: <156>mv(i, j);
397: <24>nextfile -= n - 1;
398: <24>}
399:
400: /* if flag = 0 merge input files; else temps only.
401: this program is specialized to two levels of merge;
402: should fix that some day. */
403:
404: void
405: merge(int flag)
406: <68>{
407: char buf[BUFSIZ];
408: FILE *input, *output;
409: int n, y;
410: char *name;
411: int nf = <68>0; /* next input file to merge */
412: int nm = <68>0; /* total already merged once */
413: int nt = <68>nfiles; /* files as yet unmerged */
414: if(<68>flag) {
415: <21>nf = nfiles;
416: <21>nt = nextfile;
417: }
418: if(<68>mfile == 0)
419: <49>mfile = (struct merge*)calloc(nmerge+1,
420: sizeof(*mfile));
421: if(<68>f == 0)
422: <49>f = (struct merge**)calloc(nmerge+1,
423: sizeof(*f));
424: if(<68>mfile==0 || <68>f==0)
425: <0>fatal(space,"",0);
426:
427: if(<68>nt > nmerge*(nmerge-1)+1) { /* (1) */
428: for(<19>nm=0; <135>nt>0; <116>) {
429: <116>n = nt>nmerge? <97>nmerge: <19>nt;
430: <116>merge1(nf, nm, n);
431: if(<116>flag) <0>nf += n;
432: <116>nt -= n;
433: <116>nm++;
434: }
435: <19>merge(1);
436: return<19>;
437: }
438: if(<49>nt > nmerge) { /* (2) */
439: <30>y = (nt-nmerge+1)%(nmerge-1);
440: if(<30>y <= 1) <14>y += nmerge-1;
441: <30>merge1(nf, nm, y);
442: <30>nf = nf+y>=nfiles? <18>nfiles: <12>nf+y;
443: <30>nt -= y;
444: <30>nm++;
445: }
446: while(<64>nt+nm > nmerge) { /* (3) */
447: <15>merge1(nf, nm, nmerge);
448: <15>nf = nf+nmerge>=nfiles? <6>nfiles: <9>nf+nmerge;
449: <15>nt -= nmerge;
450: <15>nm++;
451: }
452:
453: <49>n = nm+nt; /* (4) */
454: <49>recinit(nf, 0, n);
455: if(<49>!overwrite(nf))
456: <46>name = oname;
457: else
458: <3>name = filename(nextfile++);
459: <49>mergephase(n, name);
460: if(<48>name == oname)
461: return<45>;
462: <3>input = fileopen(name, "r");
463: <3>output = fileopen(oname, "w");
464: while(<88>n = fread(buf, 1, sizeof(buf), input))
465: if(<85>fwrite(buf, 1, n, output) != n)
466: <0>fatal("error writing", oname, 0);
467: <3>fileclose(input, name);
468: <3>unlink(name);
469: <3>free(name);
470: <3>fileclose(output, oname);
471: <3>}
472:
473: /* Initialize merge records for n files, beginning with
474: input file number nf and temp file number nm.
475:
476: There are nfiles-nf input files; any files beyond that
477: number must be temporaries, which come from already
478: merged inputs. (The only time that both kinds of
479: files are present is the very last merge, when for
480: stability, the temps are regarded as earlier.) */
481:
482: static void
483: recinit(int nf, int nm, int n)
484: <210>{
485: int i;
486: struct merge *m;
487: int last = <210>nfiles-nf + nextfile-nm == n;
488: for(<210>i=0; <1277>i<=n; <1067>i++) /* one extra, for mergephase() */
489: <1067>recalloc(&mfile[i]);
490: for(<210>i=0; <1067>i<n; <857>i++) {
491: <857>m = &mfile[i];
492: <857>m->del = nf>=nfiles || <635>last && <126>i<nextfile;
493: <857>m->name = m->del? <243>filename(nm++): <614>files[nf++];
494: <857>m->file = fileopen(m->name, "r");
495: <857>m->serial = i;
496: <857>f[i] = m;
497: }
498: <210>f[n] = &mfile[n];
499: <210>}
500:
501: static void
502: mv(int i, int j)
503: <180>{
504: char *old, *new;
505: if(<180>i == j) return<0>; /* believed not to happen */
506: <180>old = filename(i);
507: <180>new = filename(j);
508: <180>unlink(new);
509: if(<180>link(old,new) == -1 || <180>unlink(old) == -1)
510: <0>fatal("cannot move", old, 0);
511: <180>free(old);
512: <180>free(new);
513: <180>}
514:
515: static void
516: emit(FILE *output)
517: <22296>{
518: struct merge *m = <22296>f[0];
519: int n = <22296>m->rec->dlen;
520: uchar *p = <22296>data(m->rec); /* hanky panky for speed */
521: uchar *e = <22296>p + n++; /* use fwrite instead of */
522: int c = <22296>*e; /* printf */
523: <22296>*e = '\n';
524: if(<22296>fwrite((char*)p, 1, n, output) != n)
525: <0>fatal("error writing", m->name, 0);
526: <22296>*e = c;
527: <22296>}
528:
529: /* Merge files in mfile[0]..mfile[n-1].
530: f[0]..f[l-1] points to files in increasing order
531: of their current records. All the current records
532: are strictly ordered, either by tie-breaking, or
533: by skipping records that compare equal under -u.
534: There are two phases: (a) initialization (reading
535: from a file when there is no record at hand) and
536: (b) continuation (reading the next record with the
537: intent of displacing the current record).
538: These conditions arise, at places numbered in comments
539: (1) the record compares equal to another, and would follow
540: that other if ties were broken
541: (2) the record compares equal to another, and would precede
542: that other if ties were broken
543: (3) the record falls between two others
544:
545: At all times the keys pointed to by f[0]..f[l]
546: are distinct (perhaps due to tie-breaking), as
547: are the files they come from. When a new key
548: is read, its proper home (in tie-broken order)
549: is between f[j-1] and f[j].
550: The picture below shows the hardest case (2b),
551: where key a from file F is about to be emitted.
552: All keys in the sequence axby are distinct, as
553: are the files they come from. A new key is read
554: from file F into the extra space pointed to by
555: f[i]. (Keeping one extra key allows disorder to
556: be detected almost for free.) The
557: new key is equal to key b pointed to by f[j]
558: and file F precedes file G in stability order.
559: Thus b(F) deserves to be kept and b(G) discarded.
560: 0 j l=n
561: --------------------------------------------
562: | a(F) | x | b(G) | y | b(F) |
563: --------------------------------------------
564:
565: We emit the record at 0, and displace the key
566: at j, from whose file there is now no record
567: present; l decreases by one.
568: 0 j l n
569: --------------------------------------------
570: | x | b(F) | y | ?(G) | |
571: --------------------------------------------
572:
573: This takes us back to initialization. From
574: this configuration it is possible to reach
575: case (2a), like (2b) except that the key at 0
576: is not to be emitted; (2a) cannot happen during
577: the original initialization.
578: */
579:
580: #define moveup(a,n) memmove(a+1, a, (n)*sizeof(*a))
581: #define movedown(a,n) memmove(a-1, a, (n)*sizeof(*a))
582:
583: static void
584: mergephase(int n, char *name)
585: <210>{
586: int j, flags;
587: struct merge *mp;
588: struct rec *r;
589: int l = <210>0;
590: int k = <210>-1; /* for spotting sync errors */
591: FILE *output = fileopen(<210>name, "w");
592: init: while(<19606>l < n) { /*(a)*/
593: <19124>mp = f[l];
594: if(<19124>fillrec(mp) == IEOF) {
595: <52>movedown(f+l+1, n-l);
596: <52>f[n--] = mp;
597: <52>continue;
598: }
599: <19072>j = find(l, &flags);
600: if(<19072>j <= k)
601: <0>syncerr(mp, disorder);
602: if(<19072>flags & IFOL) { /*(1a)*/
603: if(<17234>!aflag || <17169>doaccum(f[j-1]->rec, mp->rec))
604: <17234>continue;
605: } else if(<1838>flags & IPRE) /*(2a)*/
606: if(<761>!aflag || <758>doaccum(mp->rec, f[j]->rec)) {
607: <761>f[l] = f[j];
608: <761>f[j] = mp;
609: <761>k = j;
610: <761>continue;
611: }
612: <1077>moveup(f+j, l-j); /*(3a)*/
613: <1077>f[j] = mp;
614: <1077>l++;
615: }
616: while(<24714>n > 0) { /*(b)*/
617: <24505>mp = f[l];
618: <24505>r = mp->rec;
619: <24505>*mp = *f[0];
620: <24505>mp->rec = r;
621: if(<24505>fillrec(mp) == IEOF) {
622: <803>emit(output);
623: <803>mp = f[0];
624: <803>movedown(f+1, l);
625: <803>f[--n] = mp;
626: <803>l = n;
627: <803>continue;
628: }
629: <23702>j = find(l, &flags);
630: if(<23702>j == 0)
631: <1>syncerr(mp, disorder);
632: if(<23701>flags & IFOL) { /*(1b)*/
633: if(<2208>!aflag || <1906>doaccum(f[j-1]->rec, mp->rec))
634: <2208>continue;
635: } else if(<21493>flags & IPRE) /*(2b)*/
636: if(<272>!aflag || <107>doaccum(mp->rec, f[j]->rec)) {
637: <272>emit(output);
638: <272>f[l] = f[j];
639: <272>f[j] = mp;
640: <272>mp = f[0];
641: <272>movedown(f+1, l);
642: <272>f[l--] = mp;
643: <272>k = j - 1;
644: <272>goto init;
645: }
646: <21221>emit(output); /*(3b)*/
647: <21221>mp = f[0];
648: <21221>movedown(f+1, j-1);
649: <21221>f[j-1] = f[l];
650: <21221>f[l] = mp;
651: }
652:
653: <209>fileclose(output, name);
654: <209>}
655:
656: static int
657: fillrec(struct merge *mp)
658: <284696>{
659: struct rec *r = <284696>getline(mp->rec, mp->file);
660: if(<284696>r == 0)
661: return <283702>IOK;
662: if(<994>r == ENDFILE) {
663: <937>fileclose(mp->file, mp->name);
664: if(<937>mp->del)
665: <243>unlink(mp->name);
666: return <937>IEOF;
667: }
668: <57>mp->rec = r;
669: return <57>IOK;
670: }
671:
672: /*
673: Return the proper index for the extra record f[l]
674: to be inserted before (regardless of -u).
675: Under -u, if the extra record is a duplicate, return
676: the index flagged by IFOL or IPRE according as
677: the insertion position follows or precedes a
678: record of the same value.
679: */
680:
681: static int
682: find(int l, int *flags)
683: <42774>{
684: int i, t;
685: int bot = <42774>0;
686: int top = <42774>l;
687: while(<145791>bot < top) {
688: <123492>i = (bot+top)/2;
689: <123492>t = compare(f[l], f[i]);
690: if(<123492>t < 0)
691: <55383>top = i;
692: else if(<68109>t > 0)
693: <39369>bot = i + 1;
694: else if(<28740>uflag) {
695: if(<20475>f[l]->serial < f[i]->serial) {
696: <1033>*flags = IPRE;
697: return <1033>i;
698: } else {
699: <19442>*flags = IFOL;
700: return <19442>i + 1;
701: }
702: }
703: else if(<8265>f[l]->serial < f[i]->serial)
704: <2917>top = i;
705: else
706: <5348>bot = i + 1;
707: }
708: <22299>*flags = 0;
709: return <22299>top;
710: }
711:
712: static int
713: compare(struct merge *mi, struct merge *mj)
714: <364393>{
715: uchar *ip, *jp;
716: uchar *ei, *ej;
717: uchar *trans, *keep;
718: int li, lj, k;
719: if(<364393>simplekeyed) {
720: <19>trans = fields->trans;
721: <19>keep = fields->keep;
722: <19>ip = data(mi->rec);
723: <19>jp = data(mj->rec);
724: <19>ei = ip + mi->rec->dlen;
725: <19>ej = jp + mj->rec->dlen;
726: for( <19>; <13>; <13>ip++, jp++) {
727: while(<35>ip<ei && <29>!keep[*ip]) <3>ip++;
728: while(<35>jp<ej && <29>!keep[*jp]) <3>jp++;
729: if(<32>ip>=ei || <26>jp>=ej) <7>break;
730: <25>k = trans[*ip] - trans[*jp];
731: if(<25>k != 0) <12>break;
732: }
733: if(<19>ip<ei && <13>jp<ej)
734: return <12>k*signedrflag;
735: else if(<7>ip < ei)
736: return <1>signedrflag;
737: else if(<6>jp < ej)
738: return <1>-signedrflag;
739: else if(<5>sflag)
740: return <4>0;
741: } else if(<364374>keyed) {
742: <194802>ip = key(mi->rec);
743: <194802>jp = key(mj->rec);
744: <194802>li = mi->rec->klen;
745: <194802>lj = mj->rec->klen;
746: for(<194802>k=li<lj?<1091>li:<193711>lj; <901648>--k>=0; <706846>ip++, jp++)
747: if(<807963>*ip != *jp)
748: <101117>break;
749: if(<194802>k < 0) {
750: if(<93685>li != lj)
751: <0>fatal("theorem disproved","",0);
752: if(<93685>sflag)
753: return <24419>0;
754: } else
755: return <101117>*ip - *jp;
756:
757: }
758: <238839>li = mi->rec->dlen;
759: <238839>lj = mj->rec->dlen;
760: <238839>ip = data(mi->rec);
761: <238839>jp = data(mj->rec);
762: for(<238839>k=li<lj?<7726>li:<231113>lj; <1907768>--k>=0; <1668929>ip++, jp++)
763: if(<1764308>*ip != *jp)
764: <95379>break;
765: return <238839>(k<0? <143460>li-lj: <95379>*ip-*jp)*signedrflag;
766: }
767:
768: void
769: check(char *name)
770: <87>{
771: int i, t;
772:
773: <87>mfile = (struct merge*)calloc(2,sizeof(*mfile));
774: <87>recalloc(&mfile[0]);
775: <87>recalloc(&mfile[1]);
776: <87>mfile[0].name = mfile[1].name = name;
777: <87>mfile[0].file = mfile[1].file = fileopen(name, "r");
778: if(<87>mfile[0].file == 0)
779: <0>fatal("can't open ", name, 0);
780:
781: if(<87>fillrec(&mfile[0]) == IEOF)
782: return<3>;
783: for(<84>i=1; <240980>fillrec(&mfile[i])!=IEOF; <240896>i^=1) {
784: <240901>t = compare(&mfile[i^1], &mfile[i]);
785: if(<240901>t>0)
786: <4>syncerr(&mfile[i], disorder);
787: else if(<240897>t==0 && <138849>uflag)
788: <1>syncerr(&mfile[i], duplicate);
789: }
790: <79>}
791:
792: static void
793: syncerr(struct merge *m, char *message)
794: <6>{
795: int n = <6>m->rec->dlen;
796: <6>warn("trouble in file", m->name, 0);
797: <6>fatal(message, n?<6>(char*)data(m->rec):"", n);
798: <0>}
799: optiona.c:
800:
801: #include <float.h>
802: #include <math.h>
803: #include <ctype.h>
804: #include <string.h>
805: #include <stdlib.h>
806: #include "fsort.h"
807:
808: /* portability hack for old libc's */
809: #define realloc(p,q) (p?realloc(p,q):malloc(q))
810:
811: struct field accum[NF];
812: int naccum;
813:
814: typedef struct {
815: uchar *e; /* last+1st char */
816: signed char s; /* -1 for neg, 1 for pos */
817: char c; /* 1 if + sign, else 0 */
818: char z; /* 1 for leading 0, else 0 */
819: char p; /* nonzero if a decimal point */
820: int f; /* number of digits after dec. pt. */
821: } desc;
822:
823: #define max(a, b) ((a)>(b)?(a):(b))
824: #define mod10(a) (((a)+20)%10)
825: #define div10(a) (((a)+20)/10-2)
826:
827: /* find least significant digit and other facts about a number
828: in field beginning at a and ending just before e */
829:
830: desc
831: lsd(uchar *a, uchar *e)
832: <99690>{
833: desc d = <99690>{ 0, 1, 0, 0, 0, 0 };
834: while(<271072>a<e && <269069>(*a==' '||<97687>*a=='\t')) <171382>a++;
835: if(<99690>a >= e)
836: <2003>;
837: else if(<97687>*a == '-') {
838: <7505>d.s = -1;
839: <7505>a++;
840: } else if(<90182>*a == '+') {
841: <3>d.c = 1;
842: <3>a++;
843: }
844: if(<99690>a+1<e && <51891>*a=='0' && <13>isdigit(a[1])) d.z = 1;
845: while(<299631>a<e && <199978>isdigit(*a))
846: <199941>a++;
847: if(<99690>a<e && <37>*a=='.') {
848: <13>d.p = 1;
849: while(<38>++a<e && <25>isdigit(*a))
850: <25>d.f++;
851: }
852: <99690>d.e = a;
853: return <99690>d;
854: }
855:
856: /* add the fields at a and b as desc-ribed,
857: putting result, with decimal point omitted,
858: right justified before re.
859: calculates in 10's complement and recomplements
860: magnitude if negative.
861: set *sgn -1 for neg, 1 for signed +, 0 for unsigned. */
862:
863: uchar *
864: add(uchar *re, uchar *a, desc ad, uchar *b, desc bd, int *sgn)
865: <49845>{
866: int d = <49845>0;
867: uchar *t;
868: uchar *r = <49845>re;
869: while(<49848>ad.f > bd.f) {
870: <3>d += (*--ad.e - '0')*ad.s;
871: <3>*--re = mod10(d);
872: <3>d = div10(d);
873: <3>ad.f--;
874: }
875: while(<49861>bd.f > ad.f) {
876: <16>d += (*--bd.e - '0')*bd.s;
877: <16>*--re = mod10(d);
878: <16>d = div10(d);
879: <16>bd.f--;
880: }
881: while(<220476>ad.e>a || <50616>bd.e>b) {
882: if(<170631>ad.f-- == 0) {
883: if(<49843>ad.p)
884: <6>ad.e--;
885: if(<49843>bd.p)
886: <7>bd.e--;
887: }
888: if(<170631>ad.e > a)
889: if(<169860>isdigit(*--ad.e))
890: <139640>d += (*ad.e - '0')*ad.s;
891: else
892: <30220>ad.e = a;
893: if(<170631>bd.e > b)
894: if(<109780>isdigit(*--bd.e))
895: <60307>d += (*bd.e - '0')*bd.s;
896: else
897: <49473>bd.e = b;
898: <170631>*--re = mod10(d);
899: <170631>d = div10(d);
900: }
901: <49845>*sgn = ad.c | bd.c;
902: if(<49845>d > 0)
903: <1>*--re = 1; /* happens only on overflow */
904: else if(<49844>d < 0) {
905: int x = <4997>10;
906: <4997>*sgn = -1;
907: for(<4997>t = r; <33242>--t>=re; <28245>) {
908: <28245>*t = (x - *t)%10;
909: if(<28245>*t != 0)
910: <21111>x = 9;
911: }
912: if(<4997>d < -1)
913: <0>*--re = 1; /* hygiene, can't happen */
914: }
915: while(<81359>re<r && <79328>*re==0)
916: <31514>re++;
917: return <49845>re;
918: }
919:
920: int
921: fieldaccum(uchar *a, uchar *ae, uchar *b, uchar *be)
922: <49845>{
923: static uchar *r, *re; /* not pure ansi (re-r=nil-nil=?) */
924: desc da = <49845>lsd(a, ae);
925: desc db = <49845>lsd(b, be);
926: int sgn, Sgn, f;
927: uchar *v;
928: while(<51247>re-r < max(da.e-a+db.f, db.e-b+da.f) <26>+ 1) {
929: int l = <1402>re - r + 100;
930: <1402>r = (uchar*)<1387>realloc(r, l);
931: if(<1402>r == 0)
932: <0>fatal("out of space","",0);
933: <1402>re = r + l;
934: }
935: <49845>f = max(da.f, db.f);<3>
936: <49845>v = add(re, a, da, b, db, &sgn);
937: <49845>Sgn = sgn != 0;
938: if(<49845>Sgn+max(re-v,f+1)+<46132>(da.p|<3713>db.p) > ae-a)
939: return <1>0;
940: while(<49860>re>v && <47829>--f>=0)
941: <16>*--ae = *--re + '0';
942: while(<49850>--f >= 0)
943: <6>*--ae = '0';
944: if(<49844>da.p | db.p)
945: <10>*--ae = '.';
946: if(<49844>re <= v)
947: <2031>*--ae = '0';
948: while(<188963>re > v)
949: <139119>*--ae = *--re + '0';
950: if(<49844>da.z | db.z)
951: while(<16>ae > a+Sgn)
952: <9>*--ae = '0';
953: if(<49844>sgn > 0)
954: <3>*--ae = '+';
955: else if(<49841>sgn < 0)
956: <4997>*--ae = '-';
957: if(<49844>ae<a || <49844>v<r)
958: <0>fatal("bug in accumulation","",0);
959: while(<93111>ae > a)
960: <43267>*--ae = ' ';
961: return <49844>1;
962: }
963:
964: void
965: chkaccum(struct field *field)
966: <34>{
967: if(<34>field->coder == 0)
968: <34>field->coder = acode;
969: if(<34>field->coder != acode)
970: <0>goto bad;
971: if(<34>field->trans == 0)
972: <33>field->trans = ident;
973: if(<34>field->trans != ident)
974: <1>goto bad;
975: if(<33>field->keep == 0)
976: <31>field->keep = all;
977: if(<33>field->keep != all)
978: <2>goto bad;
979: if(<31>field->rflag)
980: <1>goto bad;
981: return<30>;
982: bad:
983: <4>fatal("improper modifier with -a","",0);
984: return<0>;
985: }
986:
987: /* acode is unlike other coding functions. instead of
988: making a key in the place pointed to by op,
989: it makes a list of field locations. it might
990: be more honest if op were declared void* */
991:
992: struct loc { uchar *from, *to; };
993:
994: int
995: acode(uchar *ip, uchar *op, int len, struct field *f)
996: <99690>{
997: struct loc *lp = <99690>(struct loc*)op;
998: <99690>lp->from = ip;
999: <99690>lp->to = ip + len;
1000: if(<99690>!tab && <99690>!f->bflag &&
1001: <99686>f->begin.fieldno>0 && <99560>f->begin.charno==0)
1002: <99556>lp->from++;
1003: return <99690>sizeof(*lp);
1004: }
1005:
1006: int
1007: doaccum(struct rec *arec, struct rec *brec)
1008: <44842>{
1009: int i;
1010: struct loc aloc[NF], bloc[NF];
1011: <44842>fieldcode(data(arec), (uchar*)aloc, arec->dlen,
1012: (uchar*)-1, accum, naccum);
1013: <44842>fieldcode(data(brec), (uchar*)bloc, brec->dlen,
1014: (uchar*)-1, accum, naccum);
1015: for(<44842>i=0; <94686>i<naccum; <49844>i++)
1016: if(<49845>!fieldaccum(aloc[i].from, aloc[i].to,
1017: bloc[i].from, bloc[i].to)) {
1018: if(<1>i==0)
1019: <1>warn("sum too long; record kept: ",
1020: (char*)data(brec), brec->dlen);
1021: else
1022: <0>fatal("sum too long on adding: ",
1023: (char*)data(brec), brec->dlen);
1024: return <1>0;
1025: }
1026: return <44841>1;
1027: }
1028:
1029: struct rec *
1030: listaccum(struct rec *head, struct rec *tail)
1031: <134>{
1032: struct rec *q = <134>head;
1033: struct rec *p = <134>head;
1034: for(<134>;<24902>;<24902>) {
1035: if(<25036>q == tail)
1036: <134>break;
1037: <24902>q = q->next;
1038: if(<24902>doaccum(p, q))
1039: <24901>p->next = q->next;
1040: else
1041: <1>p = q;
1042: }
1043: return <134>p;
1044: }
1045: fsort.c:
1046:
1047: /* Copyright 1990, AT&T Bell Labs */
1048: #include <stdlib.h>
1049: #include <string.h>
1050: #include <ctype.h>
1051: #include "fsort.h"
1052:
1053: int mflag = 0;
1054: int cflag = 0;
1055: int keyed = 0;
1056:
1057: extern void readin(void);
1058: extern void dumptotemp(void);
1059: extern void sealstack(struct rec *p);
1060: extern void filelist(int, char**);
1061: extern int getopt(int, char*const*, const char*);
1062: extern char *optarg;
1063: extern int optind;
1064:
1065: FILE *input;
1066: char *oname = "-";
1067: char *tname[] = { "/usr/tmp"/*substitutable*/, "/usr/tmp", "/tmp", 0 };
1068:
1069: char **files;
1070: int nfiles;
1071: char *nofiles[] = { "-", 0 };
1072:
1073: main(int argc, char **argv)
1074: <311>{
1075: int c, n;
1076: static char s[3] = { '-' };
1077: for(<311>;<590>;<590>) {
1078: if(<901>optind<argc && <873>argv[optind][0]=='+' &&
1079: <26>isdigit(argv[optind][1])) {
1080: <26>optind += fieldarg(argv[optind],
1081: argv[optind+1]);
1082: <26>continue;
1083: }
1084: <875>n = optind; /* for sake of case '?' */
1085: <875>c = getopt(argc,argv,"a:bcdfgik:mno:rst:uw:y:MT:");
1086: switch(<875>c) {
1087: case '?':
1088: <16>fatal("bad option", argv[n], 0);
1089: default:
1090: <0>fatal("implementation error 1","",0);
1091: case 'b':
1092: case 'd':
1093: case 'f':
1094: case 'g':
1095: case 'i':
1096: case 'n':
1097: case 'M':
1098: case 'r':
1099: <97>s[1] = c;
1100: <97>fieldarg(s, 0);
1101: <97>continue;
1102: case 'c':
1103: <88>cflag++;
1104: <88>continue;
1105: case 'm':
1106: <49>mflag++;
1107: <49>continue;
1108: case 's':
1109: <9>sflag++;
1110: <9>continue;
1111: case 'u':
1112: <17>uflag++;
1113: <17>sflag++;
1114: <17>continue;
1115: case 'a':
1116: <35>aflag++;
1117: <35>uflag++;
1118: <35>sflag++;
1119: <35>optionk(optarg, accum, &naccum);
1120: <35>continue;
1121: case 'k':
1122: <181>optionk(optarg, fields, &nfields);
1123: <175>continue;
1124: case 'o':
1125: <5>oname = optarg;
1126: <5>continue;
1127: case 'T':
1128: <1>tname[0] = optarg;
1129: <1>continue;
1130: case 'w':
1131: <33>nmerge = atoi(optarg);
1132: if(<33>nmerge < 2)
1133: <0>fatal("-w too small","",0);
1134: <33>continue;
1135: case 'y':
1136: <5>optiony(optarg);
1137: <5>continue;
1138: case 't':
1139: if(<51>strlen(optarg) != 1)
1140: <1>fatal("bad argument for -t", "", 0);
1141: <50>tab = optarg[0];
1142: <50>continue;
1143: case 'z':
1144: <0>warn("nonstandard option -z ignored","",0);
1145: case -1:
1146: <288>break;
1147: }
1148: <288>break;
1149: }
1150: <288>filelist(argc, argv);
1151: if(<288>cflag)
1152: <88>aflag = 0;
1153: <288>fieldwrapup();
1154: <282>tabinit();
1155: <282>setsigs(cleanup);
1156:
1157: if(<282>cflag) {
1158: if(<88>nfiles > 1)
1159: <1>fatal("-c takes just one file", "", 0);
1160: <87>check(files[0]);
1161: return <82>0;
1162: }
1163: if(<194>mflag) {
1164: <47>merge(0);
1165: return <46>0;
1166: }
1167: for(<147>n=0; <820>n<nfiles; <673>n++) {
1168: <676>input = fileopen(files[n], "r");
1169: <674>readin();
1170: <674>fileclose(input, files[n]);
1171: }
1172: if(<144>stack->head==0 && <12>nextfile==0) { /* empty input */
1173: if(<12>strcmp(oname,"-") != 0)
1174: <4>fileclose(fileopen(oname, "w"), oname);
1175: return <12>0;
1176: }
1177: if(<132>stack->head && <132>stack->head->next)
1178: <120>sort(stack, 0);
1179: if(<132>nextfile > 0) {
1180: if(<2>stack->head)
1181: <2>dumptotemp();
1182: <2>tabfree();
1183: <2>merge(1);
1184: } else {
1185: FILE *f;
1186: <130>f = fileopen(oname, "w");
1187: <129>printout(stack->head, f, oname);
1188: <129>fileclose(f, oname);
1189: }
1190: return <131>0;
1191: }
1192:
1193: void
1194: filelist(int argc, char **argv)
1195: <288>{
1196: int i, j;
1197: <288>files = nofiles;
1198: <288>nfiles = argc - optind;
1199: if(<288>nfiles != 0)
1200: <260>files = argv + optind;
1201: else
1202: <28>nfiles = 1;
1203: if(<288>strcmp(argv[optind-1], "--") == 0)
1204: return<2>;
1205: for(<286>i=j=0; <1673>i<nfiles; <1387>i++) {
1206: if(<1387>strncmp(files[i], "-o", 2) == 0) {
1207: if(<6>files[i][2] != 0)
1208: <1>oname = files[i] + 2;
1209: else if(<5>i < argc-1)
1210: <5>oname = files[++i];
1211: else
1212: <0>fatal("incomplete -o", "", 0);
1213: } else
1214: <1381>files[j++] = files[i];
1215: }
1216: <286>files[j] = 0;
1217: <286>nfiles = j;
1218: <286>}
1219:
1220: void
1221: readin(void)
1222: <674>{
1223: int n;
1224: struct rec *new;
1225: struct rec *p = <674>stack->tail;
1226: struct rec *r = <674>p? <529>succ(p): buffer;
1227:
1228: for(<674>;<342230>;<342230>) {
1229: if(<342904>bufmax-(uchar*)r < MINREC) {
1230: <78>sealstack(p);
1231: <78>dumptotemp();
1232: <78>p = 0;
1233: <78>r = buffer;
1234: }
1235: <342904>r->next = (struct rec*)bufmax;
1236: <342904>new = getline(r, input);
1237: recenter:
1238: if(<342906>new == 0) {
1239: <342230>r->next = 0;
1240: if(<342230>p)
1241: <342017>p->next = r;
1242: <342230>p = r;
1243: <342230>r = succ(r);
1244: } else if(<676>new == ENDFILE) {
1245: <674>sealstack(p);
1246: return<674>;
1247: } else {
1248: <2>sealstack(p);
1249: <2>dumptotemp();
1250: <2>p = 0;
1251: <2>r = buffer;
1252: <2>n = data(new)-(uchar*)new+new->dlen+new->klen;
1253: if(<2>(uchar*)r+n > bufmax)
1254: <0>fatal("monster record", "", 0);
1255: <2>memmove(r, new, n);
1256: <2>free(new);
1257: <2>new = 0;
1258: <2>goto recenter;
1259: }
1260: }
1261: }
1262:
1263: void
1264: sealstack(struct rec *p)
1265: <754>{
1266: if(<754>p == 0)
1267: return<12>;
1268: <742>p->next = 0;
1269: if(<742>stack->head == 0)
1270: <213>stack->head = buffer;
1271: <742>stack->tail = p;
1272: <742>}
1273:
1274: void
1275: printout(struct rec *r, FILE *f, char *name)
1276: <211>{
1277: int c, n;
1278: uchar *dp, *ep;
1279: for( <211>; <248661>r; <248450>r=r->next) {
1280: <248450>dp = data(r);
1281: <248450>n = r->dlen;
1282: <248450>ep = dp + n++;
1283: <248450>c = *ep;
1284: <248450>*ep = '\n';
1285: if(<248450>fwrite((char*)dp, 1, n, f) != n)
1286: <0>fatal("error writing", name, 0);
1287: <248450>*ep = c;
1288: }
1289: <211>}
1290:
1291: void
1292: dumptotemp()
1293: <82>{
1294: char *tempfile = <82>filename(nextfile++);
1295: FILE *temp = fileopen(<82>tempfile,"w");
1296:
1297: if(<82>stack->head == 0)
1298: <0>fatal("monster record", "", 0);
1299: <82>stack->tail->next = 0; /* for good measure */
1300: <82>sort(stack, 0);
1301: <82>printout(stack->head, temp, tempfile);
1302: <82>fileclose(temp, tempfile);
1303: <82>free(tempfile);
1304: <82>stack->head = stack->tail = 0;
1305: return<82>;
1306: }
1307: field.c:
1308:
1309: /* Copyright 1990, AT&T Bell Labs */
1310: #include <stdlib.h>
1311: #include <ctype.h>
1312: #include "fsort.h"
1313:
1314:
1315:
1316: static char *modifiers(struct field*, char*, int);
1317: static char *keyspec(struct pos*, char*);
1318: static void globalmods(struct field*);
1319: static void chkfieldno(struct field*);
1320:
1321: struct field fields[NF] = {
1322: { 0, 0, 0, 0, 0, 0, 0, { 0, 0 }, { NP, 0 } }
1323: };
1324: int nfields = 0;
1325:
1326: int tab;
1327: int signedrflag;
1328: int simplekeyed;
1329:
1330: #define blank(p) (*(p)==' ' || *(p)=='\t')
1331:
1332: enum { OLD, NEW };
1333:
1334: /* interpret 1 or 2 arguments and return how many */
1335: int
1336: fieldarg(char *argv1, char *argv2)
1337: <123>{
1338: char *av1 = <123>argv1;
1339: char *av2 = <123>argv2;
1340: struct field *field;
1341:
1342: if(<123>av1[0] == '+' && <26>isdigit(av1[1])) {
1343: if(<26>++nfields >= NF)
1344: <0>fatal("too many fields", argv1, 0);
1345: <26>field = &fields[nfields];
1346: <26>field->end.fieldno = NP+1;
1347: <26>field->style = OLD;
1348:
1349: <26>av1 = keyspec(&field->begin, av1+1);
1350: if(<26>*modifiers(field, av1, 0))
1351: <0>goto bad;
1352:
1353: if(<26>av2==0 || <25>av2[0]!='-' || <12>!isdigit(av2[1]))
1354: return <14>1;
1355: <12>av2 = keyspec(&field->end, av2+1);
1356: <12>argv1 = argv2; /* in case of diagnostic */
1357: if(<12>*modifiers(field, av2, 1))
1358: <0>goto bad;
1359: return <12>2;
1360: } else if(<97>*modifiers(fields, av1+1, -1))
1361: <0>goto bad; /* believed not to happen */
1362: return <97>1;
1363: bad:
1364: <0>fatal("bad field specification", argv1, 0);
1365: return <0>0; /* dummy */
1366: }
1367:
1368: void
1369: optionk(char *arg, struct field *fields, int *nfields)
1370: <216>{
1371: char *a = <216>arg;
1372: struct field *field;
1373: if(<216>++*nfields >= NF)
1374: <0>fatal("too many fields", arg, 0);
1375: <216>field = &fields[*nfields];
1376: <216>field->begin.charno = 1;
1377: <216>field->end.fieldno = NP+1;
1378: <216>field->style = NEW;
1379:
1380: <216>a = keyspec(&field->begin, a);
1381: <213>a = modifiers(field, a, 0);
1382: if(<213>*a == ',') {
1383: <116>a = keyspec(&field->end, a+1);
1384: <115>a = modifiers(field, a, 1);
1385: }
1386: if(<212>*a == 0)
1387: return<210>;
1388: bad:
1389: <2>fatal("bad -k specification", arg, 0);
1390: <0>}
1391:
1392: static char *
1393: keyspec(struct pos *p, char *arg)
1394: <370>{
1395: if(<370>!isdigit(*arg))
1396: <3>fatal("missing field number", "", 0);
1397: <367>p->fieldno = strtoul(arg, &arg, 10);
1398: if(<367>*arg == '.')
1399: if(<69>!isdigit(*++arg))
1400: <1>fatal("missing character number", "", 0);
1401: else
1402: <68>p->charno = strtoul(arg, &arg, 10);
1403: return <366>arg;
1404: }
1405:
1406: /* keyed = 1 if there are fields present (+ options) or if
1407: numeric (-ng), translation (-f) or deletion (-idb) options
1408: are present. In these cases, a separate key is constructed
1409: for rsort. The key, however is not carried on
1410: intermediate files. (It would be interesting to try.)
1411: It must be reconstructed for the merge phase, and that
1412: may be expensive, since relatively few comparisons
1413: happen in that phase. simplekeyed = 1 if there are options,
1414: so that pure ascii comparison won't work, but no fields, no
1415: months, no numerics. */
1416:
1417: void
1418: fieldwrapup(void)
1419: <288>{
1420: int i;
1421: if(<288>nfields==0 && <145>aflag)
1422: <1>fatal("-a without -k", "", 0);
1423: if(<287>fields->coder == 0) <262>fields->coder = tcode;
1424: if(<287>fields->trans == 0) <270>fields->trans = ident;
1425: if(<287>fields->keep == 0) <269>fields->keep = all;
1426: for(<287>i=1; <487>i<=nfields; <200>i++) {
1427: <201>globalmods(&fields[i]);
1428: <201>chkfieldno(&fields[i]);
1429: }
1430: for(<286>i=1; <316>i<=naccum; <30>i++) {
1431: <34>chkaccum(&accum[i]);
1432: <30>chkfieldno(&accum[i]);
1433: }
1434: <282>signedrflag = fields->rflag? <24>-1: <258>1; /* used only by merge.c*/
1435: <282>simplekeyed = nfields==0 && <144>fields->coder==tcode
1436: && <119>(fields->trans!=ident || <112>fields->keep!=all);
1437: if(<282>nfields==0 && <144>!keyed) /* used only by rsort.c */
1438: <109>rflag = fields->rflag;
1439: if(<282>nfields > 0)
1440: <138>keyed = 1;
1441: <282>}
1442:
1443: static void
1444: conflict(void)
1445: <4>{
1446: <4>warn("conflicting key types", "", 0);
1447: <4>}
1448:
1449: static void
1450: dupla(uchar **oldp, uchar *new)
1451: <48>{
1452: if(<48>*oldp != 0 && <1>*oldp != new)
1453: <1>conflict();
1454: <48>*oldp = new;
1455: <48>}
1456:
1457: static void
1458: duplb(int (**oldp)(uchar*,uchar*,int,struct field*), int (*new)(uchar*,uchar*,int,struct field*))
1459: <56>{
1460: if(<56>*oldp != 0 && <2>*oldp != new)
1461: <2>conflict();
1462: <56>*oldp = new;
1463: <56>}
1464:
1465: /* eflag=-1 global flags, =0 field start, =1 field end */
1466:
1467: static char *
1468: modifiers(struct field *field, char *argv1, int eflag)
1469: <463>{
1470: for( <463>; <629>*argv1; <166>argv1++) {
1471: switch(<284>*argv1) {
1472: case 'b': if(<22>eflag==1) <6>field->eflag = 1;
1473: else <16>field->bflag = 1; <22>goto ckglob;
1474: case 'r': <40>field->rflag = 1; <40>goto ckglob;
1475: case 'f': <23>dupla(&field->trans, fold); <23>break;
1476: case 'd': <20>dupla(&field->keep, dict); <20>break;
1477: case 'i': <5>dupla(&field->keep, ascii); <5>break;
1478: case 'g': <10>duplb(&field->coder, gcode); <10>break;
1479: case 'n': <38>duplb(&field->coder, ncode); <38>break;
1480: case 'M': <8>duplb(&field->coder, Mcode); <8>break;
1481: default:
1482: <118>goto done;
1483: }
1484: <104>keyed = 1;
1485: ckglob:
1486: if(<166>field==fields && <97>nfields>0)
1487: <2>warn("field spec precedes global option",argv1,1);
1488: }
1489: done:
1490: if(<463>field->coder==ncode && <40>field->keep)
1491: <1>conflict();
1492: return <463>argv1;
1493: }
1494:
1495: static void
1496: globalmods(struct field *field)
1497: <201>{
1498: int flagged = <201>field->bflag | field->eflag | field->rflag;
1499: if(<201>!field->coder) <172>field->coder = tcode;
1500: else <29>flagged++;
1501: if(<201>!field->trans) <196>field->trans = ident;
1502: else <5>flagged++;
1503: if(<201>!field->keep) <197>field->keep = all;
1504: else <4>flagged++;
1505: if(<201>!flagged) {
1506: <146>field->coder = fields->coder;
1507: <146>field->trans = fields->trans;
1508: <146>field->keep = fields->keep;
1509: <146>field->rflag = fields->rflag;
1510: <146>field->bflag = fields->bflag;
1511: if(<146>field->style == NEW)
1512: <126>field->eflag = fields->bflag;
1513: }
1514: <201>}
1515:
1516: /* convert field representation from numbers given in arguments
1517: to a 0-origin first,last+1 representation, with a negative
1518: quantity for a character offset to the end of this field */
1519:
1520: static void
1521: chkfieldno(struct field *field)
1522: <231>{
1523: if(<231>field->style == NEW) {
1524: if(<205>--field->begin.fieldno < 0 ||
1525: <204>--field->begin.charno < 0 ||
1526: <204>--field->end.fieldno < 0)
1527: <1>fatal("improper 0 in field specifier", "", 0);
1528: if(<204>field->end.charno == 0)
1529: <180>field->end.charno--;
1530: } else if(<26>field->end.charno==0 && <22>field->end.fieldno>0) {
1531: if(<22>tab && <8>field->eflag)
1532: <0>fatal("skipping blanks right after tab char"
1533: " is ill-defined", "", 0);
1534: <22>field->end.fieldno--;
1535: <22>field->end.charno--;
1536: }
1537: if(<230>field->begin.fieldno > NP)
1538: <0>field->begin.fieldno = NP;
1539: if(<230>field->end.fieldno > NP)
1540: <0>field->end.fieldno = NP;
1541: /* fprintf(stderr,"%d %d.%d,%d.%d\n",field-fields,field->begin.fieldno, field->begin.charno,field->end.fieldno, field->end.charno);*/
1542: <230>}
1543:
1544: int
1545: fieldcode(uchar *dp, uchar *kp, int len, uchar *b, struct field *fields, int nfields)
1546: <474734>{
1547: uchar *posns[NP+1]; /* field start positions */
1548: uchar *cp;
1549: struct field *field;
1550: uchar *op = <474734>kp;
1551: uchar *ep;
1552: uchar *bound = <474734>kp + MAXREC;
1553: int i;
1554: int np;
1555: if(<474734>bound > b)
1556: <155959>bound = b;
1557: <474734>posns[0] = dp;
1558: if(<474734>tab)
1559: for(<304>np=1, i=len, cp=dp; <6355>i>0 && <6051>np<NP; i-<6051>-) {
1560: if(<6051>*cp++ != tab)
1561: <4411>continue;
1562: <1640>posns[np++] = cp;
1563: }
1564: else
1565: for(<474430>np=1, i=len, cp=dp; <1110378>i>0 && <635948>np<NP; ) <635948>{
1566: while(<1228760>blank(cp) && i><636001>0)
1567: <592812>cp++, i--;
1568: while(<3943779>!blank(cp) && i><3782124>0)
1569: <3307831>cp++, i--;
1570: <635948>posns[np++] = cp;
1571: }
1572:
1573: if(<474734>nfields > 0)
1574: <143100>field = &fields[1];
1575: else
1576: <331634>field = &fields[0];
1577: <474734>i = nfields;
1578: do {
1579: int t = <486184>field->begin.fieldno;
1580: uchar *xp = <486184>dp + len;
1581: if(<486184>t < np) {
1582: <486176>cp = posns[t];
1583: if(<486176>field->bflag && <144>nfields)
1584: while(<454>cp<xp && <454>blank(cp))
1585: <316>cp++;
1586: <486176>cp += field->begin.charno;
1587: if(<486176>cp > xp)
1588: <12>cp = xp;
1589: } else
1590: <8>cp = xp;
1591: <486184>t = field->end.fieldno;
1592: if(<486184>t < np) {
1593: if(<112104>field->end.charno < 0) {
1594: if(<111816>t >= np-1)
1595: <25>ep = xp;
1596: else {
1597: <111791>ep = posns[t+1];
1598: if(<111791>tab) <22>ep--;
1599: }
1600: } else {
1601: <288>ep = posns[t];
1602: if(<288>field->eflag)
1603: while(<262>ep<xp && <262>blank(ep))
1604: <186>ep++;
1605: <288>ep += field->end.charno;
1606: }
1607: if(<112104>ep > xp)
1608: <28>ep = xp;
1609: else if(<112076>ep < cp)
1610: <10>ep = cp;
1611: } else
1612: <374080>ep = xp;
1613: <486184>t = ep - cp;
1614: if(<486184>field->coder != acode && <386494>op+room(t) > bound)
1615: return <17>-1;
1616: <486167>op += (*field->coder)(cp, op, ep-cp, field);
1617: <486167>field++;
1618: } while(<486167>--i > 0);
1619: return <474717>op - kp;
1620: }
1621:
1622: /* Encode text field subject to options -r -fdi -b.
1623: Fields are separated by 0 (or 255 if rflag is set)
1624: the anti-ambiguity stuff prevents such codes from
1625: happening otherwise by coding real zeros and ones
1626: as 0x0101 and 0x0102, and similarly for complements */
1627:
1628: int
1629: tcode(uchar *dp, uchar *kp, int len, struct field *f)
1630: <12156>{
1631: uchar *cp = <12156>kp;
1632: int c;
1633: uchar *keep = <12156>f->keep;
1634: uchar *trans = <12156>f->trans;
1635: int reverse = <12156>f->rflag? <106>~0: <12050>0;
1636: while(<211231>--len >= 0) {
1637: <199075>c = *dp++;
1638: if(<199075>keep[c]) {
1639: <198337>c = trans[c];
1640: if(<198337>c <= 1) { /* anti-ambiguity */
1641: <4>*cp++ = 1^reverse;
1642: <4>c++;
1643: } else if(<198333>c >= 254) {
1644: <4>*cp++ = 255^reverse;
1645: <4>c--;
1646: }
1647: <198337>*cp++ = c^reverse;
1648: }
1649: }
1650: <12156>*cp++ = reverse;
1651: return <12156>cp - kp;
1652: }
1653:
1654: static char *month[] = { "jan", "feb", "mar", "apr", "may",
1655: "jun", "jul", "aug", "sep", "oct", "nov", "dec" };
1656:
1657: int
1658: Mcode(uchar *dp, uchar *kp, int len, struct field *f)
1659: <57>{
1660: int j = <57>-1;
1661: int i;
1662: uchar *cp;
1663: for( <57>; <69>len>0; <12>dp++, len--) {
1664: if(<69>*dp!=' ' && <57>*dp!='\t')
1665: <57>break;
1666: }
1667: if(<57>len >= 3)
1668: while(<294>++j < 12) {
1669: <292>cp = (uchar*)month[j];
1670: for(<292>i=0; <166>i<3; <166>i++)
1671: if(<410>(dp[i]|('a'-'A')) != *cp++)
1672: <244>break;
1673: if(<292>i >= 3)
1674: <48>break;
1675: }
1676: <57>*kp = j>=12? <2>0: <55>j+1;
1677: if(<57>f->rflag)
1678: <8>*kp ^= ~0;
1679: return <57>1;
1680: }
1681: tables.c:
1682:
1683: /* Copyright 1990, AT&T Bell Labs */
1684: #include <stdlib.h>
1685: #include <string.h>
1686: #include <ctype.h>
1687: #include "fsort.h"
1688:
1689: /* STACK=1000 makes lots of room under normal conditions.
1690: But it can be broken. 40 cycles like this will do it:
1691: a,b,...z,za,zb,...zz,zza,zzb,...,zzz,zzza,...
1692: Minor changes to rsort() would allow the stack to be
1693: extended discontiguously. Pity we don't have alloca any more.
1694: */
1695:
1696: #define BUFFER 6000000
1697: #define MINBUF 10000 /* not worth trying */
1698: #define STACK 1000
1699:
1700: uchar *bufmax;
1701: struct rec *buffer;
1702: unsigned long bufsiz = BUFFER;
1703: struct rec endfile;
1704: struct list *stack;
1705: struct list *stackmax;
1706:
1707: uchar ident[256]; /* identity transform */
1708: uchar fold[256]; /* fold upper case to lower */
1709:
1710: uchar all[256]; /* all chars significant */
1711: uchar dict[256]; /* sig chars for dictionary order */
1712: uchar ascii[256]; /* ascii graphics significant */
1713:
1714: void
1715: tabinit(void)
1716: <282>{
1717: int i;
1718: <282>memset((char*)all,1,256);
1719:
1720: <282>memset((char*)(dict+'0'),1,10);
1721: <282>memset((char*)(dict+'A'),1,26);
1722: <282>memset((char*)(dict+'a'),1,26);
1723: <282>dict[' '] = dict['\t'] = 1;
1724:
1725: <282>memset((char*)(ascii+040),1,0137); /* 040-0176 */
1726:
1727: for(<282>i=0; <72192>i<256; <72192>i++)
1728: <72192>fold[i] = ident[i] = i;
1729: for(<282>i='a'; <7332>i<='z'; <7332>i++)
1730: <7332>fold[i] += 'A' - 'a';
1731:
1732: <282>stack = (struct list*)malloc(STACK*sizeof(*stack));
1733: do {
1734: if(<282>(buffer=(struct rec*)malloc(bufsiz)) != 0)
1735: <282>break;
1736: } while(<0>(bufsiz/=2) > MINBUF);
1737: if(<282>buffer==0 || <282>stack==0)
1738: <0>fatal("can't get working space", "", 0);
1739: <282>bufmax = (uchar*)buffer + bufsiz - 2*sizeof(*buffer);
1740: <282>stack->head = stack->tail = 0;
1741: <282>stackmax = stack + STACK;
1742: <282>}
1743:
1744: void
1745: tabfree(void)
1746: <2>{
1747: <2>free(stack);
1748: <2>free(buffer);
1749: <2>}
1750:
1751: void
1752: optiony(char *s)
1753: <5>{
1754: long size = <5>atol(s);
1755: if(<5>!isdigit(s[0]))
1756: <0>fatal("no size for -y","",0);
1757: if(<5>size >= MINBUF/10) /* tiny helps debugging */
1758: <5>bufsiz = size;
1759: else if(<0>size == 0)
1760: <0>bufsiz = 10L*BUFFER;
1761: else <0>fatal("-y too small", "", 0);
1762: <5>}
1763: cfiles.c:
1764:
1765: /* Copyright 1990, AT&T Bell Labs */
1766: #include "fsort.h"
1767: #include <stdlib.h>
1768: #include <string.h>
1769: #include <signal.h>
1770: #include <errno.h>
1771: #include <sys/types.h>
1772: #include <sys/stat.h>
1773:
1774: #define SIGHUP 1
1775: #define SIGINT 2
1776: #define SIGQUIT 3
1777: #define SIGPIPE 13
1778: #define SIGTERM 15
1779:
1780: extern int getpid(void);
1781: extern int access(char*, int);
1782: extern int unlink(char*);
1783: extern int stat(const char*, struct stat *);
1784: extern int cgets(char*, int, FILE*);
1785:
1786: FILE *
1787: fileopen(char *name, char *mode)
1788: <2052>{
1789: FILE *f;
1790: if(<2052>strcmp(name,"-") == 0)
1791: if(<199>strcmp(mode, "r") == 0)
1792: <27>f = stdin;
1793: else {
1794: <172>setbuf(stdout,malloc(BUFSIZ));
1795: <172>f = stdout;
1796: }
1797: else {
1798: if(<1853>strcmp(mode, "w") == 0 &&
1799: <257>strcmp(name, oname) == 0 &&
1800: <11>overwrite(0))
1801: <4>setsigs(SIG_IGN);
1802: <1853>f = fopen(name, mode);
1803: }
1804: if(<2052>f == 0)
1805: <3>fatal("can't open", name, 0);
1806: return <2049>f;
1807: }
1808:
1809: void
1810: fileclose(FILE *f, char *name)
1811: <2041>{
1812: if(<2041>fclose(f)==EOF && <1>name!=0)
1813: <1>fatal("error on", name, 0);
1814: <2040>}
1815:
1816: /* file name strings accumulate as garbage */
1817:
1818: char *
1819: filename(int number)
1820: <849>{
1821: char name[50];
1822: char *s;
1823: int i;
1824: for(<849>i=0; <849>(s=tname[i])!=0; <0>i++)
1825: if(<849>access(s, 03) != -1)
1826: <849>break;
1827: if(<849>s == 0)
1828: <0>fatal("no accessible temp directory", "", 0);
1829: <849>sprintf(name, "%s/stm%.5d.%.4d", s, getpid(), number);
1830: <849>s = malloc(strlen(name) + 1);
1831: if(<849>s == 0)
1832: <0>fatal("out of space", "", 0);
1833: <849>strcpy(s, name);
1834: return <849>s;
1835: }
1836:
1837: /* if there is enough room in record r, getline puts
1838: a line of data there and returns 0; otherwise it
1839: returns a pointer to a new record. The record
1840: may be grown in stages; intermediate stages can
1841: be discarded, but the original cannot. */
1842:
1843: static struct rec *
1844: newrec(struct rec *r, struct rec *retval)
1845: <83>{
1846: int n = <83>(uchar*)r->next - data(r);
1847: int len = <83>(uchar*)r->next - (uchar*)r;
1848: struct rec *new = <83>(struct rec*)malloc(len + n);
1849: if(<83>new == 0)
1850: <0>fatal("no space for record", "", 0);
1851: <83>memmove(new, r, len);
1852: <83>new->next = (struct rec*)((uchar*)new + len + n);
1853: if(<83>retval)
1854: <24>free(retval);
1855: return <83>new;
1856: }
1857:
1858: struct rec*
1859: getline(struct rec *r, FILE *f)
1860: <627600>{
1861: int n = <627600>0;
1862: int m;
1863: uchar *cp, *dp;
1864: struct rec *retval = <627600>0;
1865:
1866: if(<627600>feof(f)) /* in case newline was appended */
1867: return <1>ENDFILE;
1868: for(<627599>;<133>;<133>) { /* usually executed once */
1869: <627732>dp = data(r);
1870: <627732>cp = dp + n;
1871: <627732>m = (uchar*)r->next - cp;
1872: if(<627732>m <= 1)
1873: <66>retval = r = newrec(r, retval);
1874: else {
1875: <627666>m = cgets((char*)cp, m, f);
1876: if(<627666>m == 0) {
1877: if(<1611>n == 0)
1878: return <1610>ENDFILE;
1879: <1>warn("newline appended", "", 0);
1880: <1>break;
1881: }
1882: <626055>n += m;
1883: if(<626055>dp[n-1] == '\n') {
1884: <625988>n--;
1885: <625988>break;
1886: }
1887: }
1888: }
1889:
1890: <625989>r->dlen = n;
1891: if(<625989>n > MAXREC)
1892: <0>fatal("monster record", "", 0);
1893: if(<625989>!keyed) {
1894: <240956>r->klen = 0; /* hygiene */
1895: return <240956>retval;
1896: }
1897: while(<385050>(n = fieldcode(data(r),key(r), r->dlen,
1898: (uchar*)r->next, fields, nfields)) < 0)
1899: <17>retval = r = newrec(r, retval); /* rare event */
1900: if(<385033>n > MAXREC)
1901: <0>fatal("monster key", "", 0);
1902: <385033>r->klen = n;
1903: return <385033>retval;
1904: }
1905:
1906: static char *level = "warning";
1907:
1908: void
1909: warn(char *m, char *s, int l)
1910: <54>{
1911: <54>fprintf(stderr, "sort: %s: %s %.*s\n",
1912: level, m, l==0?<45>strlen(s):<9>l, s);
1913: <54>}
1914:
1915: void
1916: fatal(char *m, char *s, int l)
1917: <40>{
1918: <40>level = "error";
1919: <40>warn(m, s, l);
1920: if(<40>errno)
1921: <3>perror("");
1922: <40>cleanup(1);
1923: <0>}
1924:
1925: int
1926: overwrite(int j)
1927: <60>{
1928: struct stat sb1, sb2;
1929: if(<60>strcmp(oname, "-") == 0)
1930: return <46>0;
1931: if(<14>stat(oname, &sb1) == -1)
1932: return <4>0;
1933: for( <10>; <29>j<nfiles; <19>j++) {
1934: if(<26>strcmp(files[j], "-") == 0)
1935: <2>continue;
1936: if(<24>stat(files[j], &sb2) == -1)
1937: <0>fatal("cannot locate", files[j], 0);
1938: if(<24>sb1.st_dev==sb2.st_dev && <24>sb1.st_ino==sb2.st_ino)
1939: return <7>1;
1940: }
1941: return <3>0;
1942: }
1943:
1944: static int siglist[] = { SIGHUP, SIGINT, SIGQUIT, SIGPIPE, SIGTERM };
1945:
1946: void
1947: setsigs(void(*f)(int))
1948: <326>{
1949: int i;
1950: for(<326>i=0; <1956>i<sizeof(siglist)/sizeof(*siglist); <1630>i++)
1951: if(<1630>signal(siglist[i], f) == SIG_IGN)
1952: <0>signal(siglist[i], SIG_IGN);
1953: <326>}
1954:
1955: void
1956: cleanup(int i)
1957: <40>{
1958: char *name;
1959: <40>setsigs(SIG_IGN);
1960: while(<40>--nextfile >= 0) {
1961: <0>name = filename(nextfile);
1962: <0>unlink(name);
1963: <0>free(name);
1964: }
1965: <40>exit(i);
1966: <0>}
1967: cgets.c:
1968:
1969: /* Copyright AT&T Bell Laboratories, 1993 */
1970: #include <stdio.h>
1971:
1972: /* same as fgets, but returns a char count instead of first arg.
1973: * robust against null bytes in input */
1974:
1975: int
1976: cgets(char *ptr, int n, FILE *iop)
1977: <627666>{
1978: int l;
1979: char *s = <627666>ptr;
1980: unsigned char *t;
1981: while(<631159>--n > 0) {
1982: <631159>l = iop->_cnt;
1983: if(<631159>l > 0) {
1984: if(<627758>l > n) <277838>l = n;
1985: <627758>t = iop->_ptr;
1986: while(<8783600>--l >= 0 && <8781637>(*s++ = *t++) != '\n')
1987: <8155842>continue;
1988: <627758>l = t - iop->_ptr;
1989: <627758>iop->_ptr = t;
1990: <627758>iop->_cnt -= l;
1991: if(<627758>t[-1] == '\n' || <1963>(n -= l) <= 0)
1992: <625861>break;
1993: }
1994: <5298>l = getc(iop);
1995: if(<5298>l == EOF)
1996: <1612>break;
1997: <3686>*s++ = l;
1998: if(<3686>l == '\n')
1999: <193>break;
2000: }
2001: <627666>*s = 0;
2002: return <627666>s - ptr;
2003: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.