Annotation of src/usr.bin/sort/fsort.c, Revision 1.6
1.6 ! mickey 1: /* $OpenBSD: fsort.c,v 1.5 1997/06/30 05:36:16 millert Exp $ */
1.1 millert 2:
3: /*-
4: * Copyright (c) 1993
5: * The Regents of the University of California. All rights reserved.
6: *
7: * This code is derived from software contributed to Berkeley by
8: * Peter McIlroy.
9: *
10: * Redistribution and use in source and binary forms, with or without
11: * modification, are permitted provided that the following conditions
12: * are met:
13: * 1. Redistributions of source code must retain the above copyright
14: * notice, this list of conditions and the following disclaimer.
15: * 2. Redistributions in binary form must reproduce the above copyright
16: * notice, this list of conditions and the following disclaimer in the
17: * documentation and/or other materials provided with the distribution.
18: * 3. All advertising materials mentioning features or use of this software
19: * must display the following acknowledgement:
20: * This product includes software developed by the University of
21: * California, Berkeley and its contributors.
22: * 4. Neither the name of the University nor the names of its contributors
23: * may be used to endorse or promote products derived from this software
24: * without specific prior written permission.
25: *
26: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36: * SUCH DAMAGE.
37: */
38:
39: #ifndef lint
40: #if 0
41: static char sccsid[] = "@(#)fsort.c 8.1 (Berkeley) 6/6/93";
42: #else
1.6 ! mickey 43: static char rcsid[] = "$OpenBSD: fsort.c,v 1.5 1997/06/30 05:36:16 millert Exp $";
1.1 millert 44: #endif
45: #endif /* not lint */
46:
47: /*
48: * Read in the next bin. If it fits in one segment sort it;
49: * otherwise refine it by segment deeper by one character,
50: * and try again on smaller bins. Sort the final bin at this level
51: * of recursion to keep the head of fstack at 0.
52: * After PANIC passes, abort to merge sort.
1.4 millert 53: */
1.1 millert 54: #include "sort.h"
55: #include "fsort.h"
56:
57: #include <stdlib.h>
58: #include <string.h>
59:
60: u_char **keylist = 0, *buffer = 0, *linebuf = 0;
61: struct tempfile fstack[MAXFCT];
62: extern char *toutpath;
63: #define FSORTMAX 4
64: int PANIC = FSORTMAX;
65:
66: void
67: fsort(binno, depth, infiles, nfiles, outfp, ftbl)
1.5 millert 68: register int binno, depth;
1.1 millert 69: register union f_handle infiles;
1.5 millert 70: register int nfiles;
1.1 millert 71: FILE *outfp;
72: register struct field *ftbl;
73: {
74: register u_char *bufend, **keypos, *tmpbuf;
75: u_char *weights;
76: int ntfiles, mfct = 0, total, i, maxb, lastb, panic = 0;
1.5 millert 77: int c, nelem;
78: int sizes [NBINS+1];
1.1 millert 79: union f_handle tfiles, mstart = {MAXFCT-16};
80: register int (*get)(int, union f_handle, int, RECHEADER *,
81: u_char *, struct field *);
1.5 millert 82: register RECHEADER *crec;
1.1 millert 83: struct field tfield[2];
84: FILE *prevfp, *tailfp[FSORTMAX+1];
85:
86: memset(tailfp, 0, sizeof(tailfp));
87: prevfp = outfp;
88: memset(tfield, 0, sizeof(tfield));
89: if (ftbl[0].flags & R)
90: tfield[0].weights = Rascii;
91: else
92: tfield[0].weights = ascii;
93: tfield[0].icol.num = 1;
94: weights = ftbl[0].weights;
95: if (!buffer) {
1.3 millert 96: buffer = malloc(BUFSIZE + 1);
1.1 millert 97: keylist = malloc(MAXNUM * sizeof(u_char *));
1.6 ! mickey 98: memset(keylist, 0, MAXNUM * sizeof(u_char *));
1.1 millert 99: if (!SINGL_FLD)
100: linebuf = malloc(MAXLLEN);
101: }
1.3 millert 102: bufend = buffer + BUFSIZE;
1.1 millert 103: if (binno >= 0) {
104: tfiles.top = infiles.top + nfiles;
105: get = getnext;
106: } else {
107: tfiles.top = 0;
108: if (SINGL_FLD)
109: get = makeline;
110: else
111: get = makekey;
112: }
113: for (;;) {
114: memset(sizes, 0, sizeof(sizes));
115: c = ntfiles = 0;
116: if (binno == weights[REC_D] &&
117: !(SINGL_FLD && ftbl[0].flags & F)) { /* pop */
118: rd_append(weights[REC_D],
119: infiles, nfiles, prevfp, buffer, bufend);
120: break;
121: } else if (binno == weights[REC_D]) {
122: depth = 0; /* start over on flat weights */
123: ftbl = tfield;
124: weights = ftbl[0].weights;
125: }
126: while (c != EOF) {
127: keypos = keylist;
128: nelem = 0;
129: crec = (RECHEADER *) buffer;
130: while((c = get(binno, infiles, nfiles, crec, bufend,
131: ftbl)) == 0) {
132: *keypos++ = crec->data + depth;
133: if (++nelem == MAXNUM) {
134: c = BUFFEND;
135: break;
136: }
137: crec =(RECHEADER *) ((char *) crec +
138: SALIGN(crec->length) + sizeof(TRECHEADER));
139: }
140: if (c == BUFFEND || ntfiles || mfct) { /* push */
141: if (panic >= PANIC) {
142: fstack[MAXFCT-16+mfct].fp = ftmp();
143: if (radixsort((const u_char **)keylist,
144: nelem, weights, REC_D))
145: err(2, NULL);
146: append(keylist, nelem, depth, fstack[
147: MAXFCT-16+mfct].fp, putrec, ftbl);
148: mfct++;
149: /* reduce number of open files */
150: if (mfct == 16 ||(c == EOF && ntfiles)) {
151: tmpbuf = malloc(bufend -
152: crec->data);
153: memmove(tmpbuf, crec->data,
154: bufend - crec->data);
155: fstack[tfiles.top + ntfiles].fp
156: = ftmp();
157: fmerge(0, mstart, mfct, geteasy,
158: fstack[tfiles.top+ntfiles].fp,
159: putrec, ftbl);
1.4 millert 160: ntfiles++;
1.1 millert 161: mfct = 0;
162: memmove(crec->data, tmpbuf,
163: bufend - crec->data);
164: free(tmpbuf);
165: }
166: } else {
167: fstack[tfiles.top + ntfiles].fp= ftmp();
168: onepass(keylist, depth, nelem, sizes,
169: weights, fstack[tfiles.top+ntfiles].fp);
1.4 millert 170: ntfiles++;
1.1 millert 171: }
172: }
173: }
174: get = getnext;
175: if (!ntfiles && !mfct) { /* everything in memory--pop */
176: if (nelem > 1 && radixsort((const u_char **)keylist,
177: nelem, weights, REC_D))
178: err(2, NULL);
179: append(keylist, nelem, depth, outfp, putline, ftbl);
180: break; /* pop */
181: }
182: if (panic >= PANIC) {
183: if (!ntfiles)
184: fmerge(0, mstart, mfct, geteasy,
185: outfp, putline, ftbl);
186: else
187: fmerge(0, tfiles, ntfiles, geteasy,
188: outfp, putline, ftbl);
189: break;
190:
191: }
192: total = maxb = lastb = 0; /* find if one bin dominates */
193: for (i = 0; i < NBINS; i++)
194: if (sizes[i]) {
195: if (sizes[i] > sizes[maxb])
196: maxb = i;
197: lastb = i;
198: total += sizes[i];
199: }
200: if (sizes[maxb] < max((total / 2) , BUFSIZE))
201: maxb = lastb; /* otherwise pop after last bin */
202: fstack[tfiles.top].lastb = lastb;
203: fstack[tfiles.top].maxb = maxb;
204:
205: /* start refining next level. */
206: get(-1, tfiles, ntfiles, crec, bufend, 0); /* rewind */
207: for (i = 0; i < maxb; i++) {
208: if (!sizes[i]) /* bin empty; step ahead file offset */
209: get(i, tfiles, ntfiles, crec, bufend, 0);
210: else
211: fsort(i, depth+1, tfiles, ntfiles, outfp, ftbl);
212: }
213: if (lastb != maxb) {
214: if (prevfp != outfp)
215: tailfp[panic] = prevfp;
216: prevfp = ftmp();
217: for (i = maxb+1; i <= lastb; i++)
218: if (!sizes[i])
219: get(i, tfiles, ntfiles, crec, bufend,0);
220: else
221: fsort(i, depth+1, tfiles, ntfiles,
222: prevfp, ftbl);
223: }
224:
225: /* sort biggest (or last) bin at this level */
226: depth++;
227: panic++;
228: binno = maxb;
229: infiles.top = tfiles.top; /* getnext will free tfiles, */
230: nfiles = ntfiles; /* so overwrite them */
231: }
232: if (prevfp != outfp) {
233: concat(outfp, prevfp);
234: fclose(prevfp);
235: }
236: for (i = panic; i >= 0; --i)
237: if (tailfp[i]) {
238: concat(outfp, tailfp[i]);
239: fclose(tailfp[i]);
240: }
241: }
242:
243: /*
1.4 millert 244: * This is one pass of radix exchange, dumping the bins to disk.
1.1 millert 245: */
246: #define swap(a, b, t) t = a, a = b, b = t
247: void
248: onepass(a, depth, n, sizes, tr, fp)
249: u_char **a;
250: int depth;
1.5 millert 251: int n;
252: int sizes[];
1.1 millert 253: u_char *tr;
254: FILE *fp;
255: {
1.5 millert 256: int tsizes[NBINS+1];
1.1 millert 257: u_char **bin[257], **top[256], ***bp, ***bpmax, ***tp;
258: static histo[256];
259: int *hp;
260: register int c;
261: u_char **an, *t, **aj;
262: register u_char **ak, *r;
263:
264: memset(tsizes, 0, sizeof(tsizes));
265: depth += sizeof(TRECHEADER);
266: an = a + n;
267: for (ak = a; ak < an; ak++) {
268: histo[c = tr[**ak]]++;
269: tsizes[c] += ((RECHEADER *) (*ak -= depth))->length;
270: }
271:
272: bin[0] = a;
273: bpmax = bin + 256;
274: tp = top, hp = histo;
275: for (bp = bin; bp < bpmax; bp++) {
276: *tp++ = *(bp+1) = *bp + (c = *hp);
277: *hp++ = 0;
278: if (c <= 1)
279: continue;
280: }
1.4 millert 281: for (aj = a; aj < an; *aj = r, aj = bin[c+1])
1.1 millert 282: for(r = *aj; aj < (ak = --top[c = tr[r[depth]]]) ;)
283: swap(*ak, r, t);
284:
285: for (ak = a, c = 0; c < 256; c++) {
286: an = bin[c+1];
287: n = an - ak;
288: tsizes[c] += n * sizeof(TRECHEADER);
289: /* tell getnext how many elements in this bin, this segment. */
1.5 millert 290: EWRITE(tsizes+c, sizeof(int), 1, fp);
1.1 millert 291: sizes[c] += tsizes[c];
292: for (; ak < an; ++ak)
293: putrec((RECHEADER *) *ak, fp);
294: }
295: }