![[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.8 ! ericj 1: /* $OpenBSD: fsort.c,v 1.7 1999/05/24 17:57:18 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.8 ! ericj 43: static char rcsid[] = "$OpenBSD: fsort.c,v 1.7 1999/05/24 17:57:18 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;
1.8 ! ericj 61: size_t bufsize, linebuf_size;
1.1 millert 62: struct tempfile fstack[MAXFCT];
63: extern char *toutpath;
64: #define FSORTMAX 4
65: int PANIC = FSORTMAX;
66:
67: void
68: fsort(binno, depth, infiles, nfiles, outfp, ftbl)
1.8 ! ericj 69: int binno, depth;
! 70: union f_handle infiles;
! 71: int nfiles;
1.1 millert 72: FILE *outfp;
1.8 ! ericj 73: struct field *ftbl;
1.1 millert 74: {
1.8 ! ericj 75: u_char *bufend, **keypos, *tmpbuf;
1.1 millert 76: u_char *weights;
77: int ntfiles, mfct = 0, total, i, maxb, lastb, panic = 0;
1.5 millert 78: int c, nelem;
1.8 ! ericj 79: long sizes[NBINS+1];
1.1 millert 80: union f_handle tfiles, mstart = {MAXFCT-16};
1.8 ! ericj 81: int (*get)(int, union f_handle, int, RECHEADER *,
1.1 millert 82: u_char *, struct field *);
1.8 ! ericj 83: RECHEADER *crec;
1.1 millert 84: struct field tfield[2];
85: FILE *prevfp, *tailfp[FSORTMAX+1];
86:
87: memset(tailfp, 0, sizeof(tailfp));
88: prevfp = outfp;
89: memset(tfield, 0, sizeof(tfield));
90: if (ftbl[0].flags & R)
91: tfield[0].weights = Rascii;
92: else
93: tfield[0].weights = ascii;
94: tfield[0].icol.num = 1;
95: weights = ftbl[0].weights;
96: if (!buffer) {
1.8 ! ericj 97: bufsize = BUFSIZE;
! 98: if ((buffer = malloc(bufsize + 1)) == NULL ||
1.7 millert 99: (keylist = calloc(MAXNUM, sizeof(u_char *))) == NULL)
100: errx(2, "cannot allocate memory");
101: if (!SINGL_FLD) {
1.8 ! ericj 102: linebuf_size = MAXLLEN;
! 103: if ((linebuf = malloc(linebuf_size)) == NULL)
1.7 millert 104: errx(2, "cannot allocate memory");
105: }
1.1 millert 106: }
1.8 ! ericj 107: bufend = buffer + bufsize;
1.1 millert 108: if (binno >= 0) {
109: tfiles.top = infiles.top + nfiles;
110: get = getnext;
111: } else {
112: tfiles.top = 0;
113: if (SINGL_FLD)
114: get = makeline;
115: else
116: get = makekey;
117: }
118: for (;;) {
119: memset(sizes, 0, sizeof(sizes));
120: c = ntfiles = 0;
121: if (binno == weights[REC_D] &&
122: !(SINGL_FLD && ftbl[0].flags & F)) { /* pop */
123: rd_append(weights[REC_D],
124: infiles, nfiles, prevfp, buffer, bufend);
125: break;
126: } else if (binno == weights[REC_D]) {
127: depth = 0; /* start over on flat weights */
128: ftbl = tfield;
129: weights = ftbl[0].weights;
130: }
131: while (c != EOF) {
132: keypos = keylist;
133: nelem = 0;
134: crec = (RECHEADER *) buffer;
135: while((c = get(binno, infiles, nfiles, crec, bufend,
136: ftbl)) == 0) {
137: *keypos++ = crec->data + depth;
138: if (++nelem == MAXNUM) {
139: c = BUFFEND;
140: break;
141: }
142: crec =(RECHEADER *) ((char *) crec +
143: SALIGN(crec->length) + sizeof(TRECHEADER));
144: }
1.8 ! ericj 145: /*
! 146: * buffer was too small for data, allocate
! 147: * a bigger buffer.
! 148: */
! 149: if (c == BUFFEND && nelem == 0) {
! 150: bufsize *= 2;
! 151: buffer = realloc(buffer, bufsize);
! 152: if (!buffer)
! 153: err(2, "failed to realloc buffer");
! 154: bufend = buffer + bufsize;
! 155: continue;
! 156: }
1.1 millert 157: if (c == BUFFEND || ntfiles || mfct) { /* push */
158: if (panic >= PANIC) {
159: fstack[MAXFCT-16+mfct].fp = ftmp();
160: if (radixsort((const u_char **)keylist,
161: nelem, weights, REC_D))
162: err(2, NULL);
163: append(keylist, nelem, depth, fstack[
164: MAXFCT-16+mfct].fp, putrec, ftbl);
165: mfct++;
166: /* reduce number of open files */
167: if (mfct == 16 ||(c == EOF && ntfiles)) {
168: tmpbuf = malloc(bufend -
169: crec->data);
1.7 millert 170: if (tmpbuf == NULL)
171: errx(2, "cannot "
172: "allocate memory");
1.1 millert 173: memmove(tmpbuf, crec->data,
174: bufend - crec->data);
175: fstack[tfiles.top + ntfiles].fp
176: = ftmp();
177: fmerge(0, mstart, mfct, geteasy,
178: fstack[tfiles.top+ntfiles].fp,
179: putrec, ftbl);
1.4 millert 180: ntfiles++;
1.1 millert 181: mfct = 0;
182: memmove(crec->data, tmpbuf,
183: bufend - crec->data);
184: free(tmpbuf);
185: }
186: } else {
187: fstack[tfiles.top + ntfiles].fp= ftmp();
188: onepass(keylist, depth, nelem, sizes,
189: weights, fstack[tfiles.top+ntfiles].fp);
1.4 millert 190: ntfiles++;
1.1 millert 191: }
192: }
193: }
194: get = getnext;
195: if (!ntfiles && !mfct) { /* everything in memory--pop */
196: if (nelem > 1 && radixsort((const u_char **)keylist,
197: nelem, weights, REC_D))
198: err(2, NULL);
199: append(keylist, nelem, depth, outfp, putline, ftbl);
200: break; /* pop */
201: }
202: if (panic >= PANIC) {
203: if (!ntfiles)
204: fmerge(0, mstart, mfct, geteasy,
205: outfp, putline, ftbl);
206: else
207: fmerge(0, tfiles, ntfiles, geteasy,
208: outfp, putline, ftbl);
209: break;
210:
211: }
212: total = maxb = lastb = 0; /* find if one bin dominates */
213: for (i = 0; i < NBINS; i++)
214: if (sizes[i]) {
215: if (sizes[i] > sizes[maxb])
216: maxb = i;
217: lastb = i;
218: total += sizes[i];
219: }
220: if (sizes[maxb] < max((total / 2) , BUFSIZE))
221: maxb = lastb; /* otherwise pop after last bin */
222: fstack[tfiles.top].lastb = lastb;
223: fstack[tfiles.top].maxb = maxb;
224:
225: /* start refining next level. */
226: get(-1, tfiles, ntfiles, crec, bufend, 0); /* rewind */
227: for (i = 0; i < maxb; i++) {
228: if (!sizes[i]) /* bin empty; step ahead file offset */
229: get(i, tfiles, ntfiles, crec, bufend, 0);
230: else
231: fsort(i, depth+1, tfiles, ntfiles, outfp, ftbl);
232: }
233: if (lastb != maxb) {
234: if (prevfp != outfp)
235: tailfp[panic] = prevfp;
236: prevfp = ftmp();
237: for (i = maxb+1; i <= lastb; i++)
238: if (!sizes[i])
239: get(i, tfiles, ntfiles, crec, bufend,0);
240: else
241: fsort(i, depth+1, tfiles, ntfiles,
242: prevfp, ftbl);
243: }
244:
245: /* sort biggest (or last) bin at this level */
246: depth++;
247: panic++;
248: binno = maxb;
249: infiles.top = tfiles.top; /* getnext will free tfiles, */
250: nfiles = ntfiles; /* so overwrite them */
251: }
252: if (prevfp != outfp) {
253: concat(outfp, prevfp);
254: fclose(prevfp);
255: }
256: for (i = panic; i >= 0; --i)
257: if (tailfp[i]) {
258: concat(outfp, tailfp[i]);
259: fclose(tailfp[i]);
260: }
261: }
262:
263: /*
1.4 millert 264: * This is one pass of radix exchange, dumping the bins to disk.
1.1 millert 265: */
266: #define swap(a, b, t) t = a, a = b, b = t
267: void
268: onepass(a, depth, n, sizes, tr, fp)
269: u_char **a;
270: int depth;
1.8 ! ericj 271: long n;
! 272: long sizes[];
1.1 millert 273: u_char *tr;
274: FILE *fp;
275: {
1.8 ! ericj 276: size_t tsizes[NBINS+1];
1.1 millert 277: u_char **bin[257], **top[256], ***bp, ***bpmax, ***tp;
1.7 millert 278: static int histo[256];
1.1 millert 279: int *hp;
1.8 ! ericj 280: int c;
1.1 millert 281: u_char **an, *t, **aj;
1.8 ! ericj 282: u_char **ak, *r;
1.1 millert 283:
284: memset(tsizes, 0, sizeof(tsizes));
285: depth += sizeof(TRECHEADER);
1.8 ! ericj 286: an = &a[n];
1.1 millert 287: for (ak = a; ak < an; ak++) {
288: histo[c = tr[**ak]]++;
289: tsizes[c] += ((RECHEADER *) (*ak -= depth))->length;
290: }
291:
292: bin[0] = a;
293: bpmax = bin + 256;
294: tp = top, hp = histo;
295: for (bp = bin; bp < bpmax; bp++) {
296: *tp++ = *(bp+1) = *bp + (c = *hp);
297: *hp++ = 0;
298: if (c <= 1)
299: continue;
300: }
1.4 millert 301: for (aj = a; aj < an; *aj = r, aj = bin[c+1])
1.1 millert 302: for(r = *aj; aj < (ak = --top[c = tr[r[depth]]]) ;)
303: swap(*ak, r, t);
304:
305: for (ak = a, c = 0; c < 256; c++) {
306: an = bin[c+1];
307: n = an - ak;
308: tsizes[c] += n * sizeof(TRECHEADER);
309: /* tell getnext how many elements in this bin, this segment. */
1.8 ! ericj 310: EWRITE(&tsizes[c], sizeof(size_t), 1, fp);
1.1 millert 311: sizes[c] += tsizes[c];
312: for (; ak < an; ++ak)
313: putrec((RECHEADER *) *ak, fp);
314: }
315: }