fsort.c revision 1.7
1 /* $NetBSD: fsort.c,v 1.7 2001/01/08 18:00:31 jdolecek Exp $ */ 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 /* 40 * Read in the next bin. If it fits in one segment sort it; 41 * otherwise refine it by segment deeper by one character, 42 * and try again on smaller bins. Sort the final bin at this level 43 * of recursion to keep the head of fstack at 0. 44 * After PANIC passes, abort to merge sort. 45 */ 46 #include "sort.h" 47 #include "fsort.h" 48 49 #ifndef lint 50 __RCSID("$NetBSD: fsort.c,v 1.7 2001/01/08 18:00:31 jdolecek Exp $"); 51 __SCCSID("@(#)fsort.c 8.1 (Berkeley) 6/6/93"); 52 #endif /* not lint */ 53 54 #include <stdlib.h> 55 #include <string.h> 56 57 const u_char **keylist = 0; 58 u_char *buffer = 0, *linebuf = 0; 59 size_t bufsize, linebuf_size; 60 struct tempfile fstack[MAXFCT]; 61 extern char *toutpath; 62 #define FSORTMAX 4 63 int PANIC = FSORTMAX; 64 65 void 66 fsort(binno, depth, infiles, nfiles, outfp, ftbl) 67 int binno, depth, nfiles; 68 union f_handle infiles; 69 FILE *outfp; 70 struct field *ftbl; 71 { 72 const u_char **keypos; 73 u_char *bufend, *tmpbuf; 74 u_char *weights; 75 int ntfiles, mfct = 0, total, i, maxb, lastb, panic = 0; 76 int c, nelem; 77 long sizes [NBINS+1]; 78 union f_handle tfiles, mstart = {MAXFCT-16}; 79 int (*get)(int, union f_handle, int, RECHEADER *, 80 u_char *, struct field *); 81 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 bufsize = BUFSIZE; 96 buffer = malloc(bufsize); 97 keylist = malloc(MAXNUM * sizeof(u_char *)); 98 if (!SINGL_FLD) { 99 linebuf_size = DEFLLEN; 100 linebuf = malloc(linebuf_size); 101 } 102 } 103 bufend = buffer + bufsize; 104 if (binno >= 0) { 105 tfiles.top = infiles.top + nfiles; 106 get = getnext; 107 } else { 108 tfiles.top = 0; 109 if (SINGL_FLD) 110 get = makeline; 111 else 112 get = makekey; 113 } 114 for (;;) { 115 memset(sizes, 0, sizeof(sizes)); 116 c = ntfiles = 0; 117 if (binno == weights[REC_D] && 118 !(SINGL_FLD && ftbl[0].flags & F)) { /* pop */ 119 rd_append(weights[REC_D], 120 infiles, nfiles, prevfp, buffer, bufend); 121 break; 122 } else if (binno == weights[REC_D]) { 123 depth = 0; /* start over on flat weights */ 124 ftbl = tfield; 125 weights = ftbl[0].weights; 126 } 127 while (c != EOF) { 128 keypos = keylist; 129 nelem = 0; 130 crec = (RECHEADER *) buffer; 131 while((c = get(binno, infiles, nfiles, crec, bufend, 132 ftbl)) == 0) { 133 *keypos++ = crec->data + depth; 134 if (++nelem == MAXNUM) { 135 c = BUFFEND; 136 break; 137 } 138 crec =(RECHEADER *) ((char *) crec + 139 SALIGN(crec->length) + sizeof(TRECHEADER)); 140 } 141 if (c == BUFFEND && nelem == 0) { 142 /* buffer was too small for data, allocate 143 * bigger buffer */ 144 bufsize *= 2; 145 buffer = realloc(buffer, bufsize); 146 if (!buffer) { 147 err(2, "failed to realloc buffer to %ld bytes", 148 (unsigned long) bufsize); 149 } 150 bufend = buffer + bufsize; 151 continue; 152 } 153 if (c == BUFFEND || ntfiles || mfct) { /* push */ 154 if (panic >= PANIC) { 155 fstack[MAXFCT-16+mfct].fp = ftmp(); 156 if ((stable_sort) 157 ? sradixsort(keylist, nelem, 158 weights, REC_D) 159 : radixsort(keylist, nelem, 160 weights, REC_D) ) 161 err(2, NULL); 162 append(keylist, nelem, depth, fstack[ 163 MAXFCT-16+mfct].fp, putrec, ftbl); 164 mfct++; 165 /* reduce number of open files */ 166 if (mfct == 16 ||(c == EOF && ntfiles)) { 167 tmpbuf = malloc(bufend - 168 crec->data); 169 memmove(tmpbuf, crec->data, 170 bufend - crec->data); 171 fstack[tfiles.top + ntfiles].fp 172 = ftmp(); 173 fmerge(0, mstart, mfct, geteasy, 174 fstack[tfiles.top+ntfiles].fp, 175 putrec, ftbl); 176 ++ntfiles; 177 mfct = 0; 178 memmove(crec->data, tmpbuf, 179 bufend - crec->data); 180 free(tmpbuf); 181 } 182 } else { 183 fstack[tfiles.top + ntfiles].fp= ftmp(); 184 onepass(keylist, depth, nelem, sizes, 185 weights, fstack[tfiles.top+ntfiles].fp); 186 ++ntfiles; 187 } 188 } 189 } 190 get = getnext; 191 if (!ntfiles && !mfct) { /* everything in memory--pop */ 192 if (nelem > 1) { 193 if ((stable_sort) 194 ? sradixsort(keylist, nelem, weights, REC_D) 195 : radixsort(keylist, nelem, weights, REC_D) ) 196 err(2, NULL); 197 } 198 append(keylist, nelem, depth, outfp, putline, ftbl); 199 break; /* pop */ 200 } 201 if (panic >= PANIC) { 202 if (!ntfiles) 203 fmerge(0, mstart, mfct, geteasy, 204 outfp, putline, ftbl); 205 else 206 fmerge(0, tfiles, ntfiles, geteasy, 207 outfp, putline, ftbl); 208 break; 209 210 } 211 total = maxb = lastb = 0; /* find if one bin dominates */ 212 for (i = 0; i < NBINS; i++) 213 if (sizes[i]) { 214 if (sizes[i] > sizes[maxb]) 215 maxb = i; 216 lastb = i; 217 total += sizes[i]; 218 } 219 if (sizes[maxb] < max((total / 2) , BUFSIZE)) 220 maxb = lastb; /* otherwise pop after last bin */ 221 fstack[tfiles.top].lastb = lastb; 222 fstack[tfiles.top].maxb = maxb; 223 224 /* start refining next level. */ 225 get(-1, tfiles, ntfiles, crec, bufend, 0); /* rewind */ 226 for (i = 0; i < maxb; i++) { 227 if (!sizes[i]) /* bin empty; step ahead file offset */ 228 get(i, tfiles, ntfiles, crec, bufend, 0); 229 else 230 fsort(i, depth+1, tfiles, ntfiles, outfp, ftbl); 231 } 232 if (lastb != maxb) { 233 if (prevfp != outfp) 234 tailfp[panic] = prevfp; 235 prevfp = ftmp(); 236 for (i = maxb+1; i <= lastb; i++) 237 if (!sizes[i]) 238 get(i, tfiles, ntfiles, crec, bufend,0); 239 else 240 fsort(i, depth+1, tfiles, ntfiles, 241 prevfp, ftbl); 242 } 243 244 /* sort biggest (or last) bin at this level */ 245 depth++; 246 panic++; 247 binno = maxb; 248 infiles.top = tfiles.top; /* getnext will free tfiles, */ 249 nfiles = ntfiles; /* so overwrite them */ 250 } 251 if (prevfp != outfp) { 252 concat(outfp, prevfp); 253 fclose(prevfp); 254 } 255 for (i = panic; i >= 0; --i) 256 if (tailfp[i]) { 257 concat(outfp, tailfp[i]); 258 fclose(tailfp[i]); 259 } 260 } 261 262 /* 263 This is one pass of radix exchange, dumping the bins to disk. 264 */ 265 #define swap(a, b, t) t = a, a = b, b = t 266 void 267 onepass(a, depth, n, sizes, tr, fp) 268 const u_char **a; 269 int depth; 270 long n, sizes[]; 271 u_char *tr; 272 FILE *fp; 273 { 274 size_t tsizes[NBINS+1]; 275 const u_char **bin[257], ***bp, ***bpmax, **top[256], ***tp; 276 static int histo[256]; 277 int *hp; 278 int c; 279 const u_char **an, *t, **aj; 280 const u_char **ak, *r; 281 282 memset(tsizes, 0, sizeof(tsizes)); 283 depth += sizeof(TRECHEADER); 284 an = &a[n]; 285 for (ak = a; ak < an; ak++) { 286 histo[c = tr[**ak]]++; 287 tsizes[c] += ((const RECHEADER *) (*ak -= depth))->length; 288 } 289 290 bin[0] = a; 291 bpmax = bin + 256; 292 tp = top, hp = histo; 293 for (bp = bin; bp < bpmax; bp++) { 294 *tp++ = *(bp+1) = *bp + (c = *hp); 295 *hp++ = 0; 296 if (c <= 1) 297 continue; 298 } 299 for(aj = a; aj < an; *aj = r, aj = bin[c+1]) 300 for(r = *aj; aj < (ak = --top[c = tr[r[depth]]]) ;) 301 swap(*ak, r, t); 302 303 for (ak = a, c = 0; c < 256; c++) { 304 an = bin[c+1]; 305 n = an - ak; 306 tsizes[c] += n * sizeof(TRECHEADER); 307 /* tell getnext how many elements in this bin, this segment. */ 308 EWRITE(&tsizes[c], sizeof(size_t), 1, fp); 309 sizes[c] += tsizes[c]; 310 for (; ak < an; ++ak) 311 putrec((const RECHEADER *) *ak, fp); 312 } 313 } 314
Indexes created Fri Sep 26 08:10:20 GMT 2025