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