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