fsort.c revision 1.18
1 /* $NetBSD: fsort.c,v 1.18 2001/05/14 21:45:19 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.18 2001/05/14 21:45:19 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 static const u_char **keylist = 0; 58 u_char *buffer = 0, *linebuf = 0; 59 size_t bufsize = DEFBUFSIZE; 60 size_t linebuf_size; 61 struct tempfile fstack[MAXFCT]; 62 extern char *toutpath; 63 #define FSORTMAX 4 64 int PANIC = FSORTMAX; 65 66 #define MSTART (MAXFCT - MERGE_FNUM) 67 #define SALIGN(n) ((n+sizeof(length_t)-1) & ~(sizeof(length_t)-1)) 68 69 void 70 fsort(binno, depth, top, filelist, nfiles, outfp, ftbl) 71 int binno, depth, top; 72 struct filelist *filelist; 73 int nfiles; 74 FILE *outfp; 75 struct field *ftbl; 76 { 77 const u_char **keypos; 78 u_char *bufend, *tmpbuf; 79 u_char *weights; 80 int ntfiles, mfct = 0, total, i, maxb, lastb, panic = 0; 81 int c, nelem, base; 82 long sizes [NBINS+1]; 83 get_func_t get; 84 struct recheader *crec; 85 struct field tfield[2]; 86 FILE *prevfp, *tailfp[FSORTMAX+1]; 87 88 memset(tailfp, 0, sizeof(tailfp)); 89 prevfp = outfp; 90 memset(tfield, 0, sizeof(tfield)); 91 if (ftbl[0].flags & R) 92 tfield[0].weights = Rascii; 93 else 94 tfield[0].weights = ascii; 95 tfield[0].icol.num = 1; 96 weights = ftbl[0].weights; 97 if (!buffer) { 98 buffer = malloc(bufsize); 99 keylist = malloc(MAXNUM * sizeof(u_char *)); 100 memset(keylist, 0, MAXNUM * sizeof(u_char *)); 101 if (!SINGL_FLD) { 102 linebuf_size = DEFLLEN; 103 if ((linebuf = malloc(linebuf_size)) == NULL) 104 errx(2, "cannot allocate memory"); 105 } 106 } 107 bufend = buffer + bufsize; 108 if (binno >= 0) { 109 base = top + nfiles; 110 get = getnext; 111 } else { 112 base = 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], top, 124 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 136 do_read: 137 while((c = get(binno, top, filelist, nfiles, crec, 138 bufend, ftbl)) == 0) { 139 *keypos++ = crec->data + depth; 140 if (++nelem == MAXNUM) { 141 c = BUFFEND; 142 break; 143 } 144 crec =(RECHEADER *) ((char *) crec + 145 SALIGN(crec->length) + sizeof(TRECHEADER)); 146 } 147 148 if (c == BUFFEND && nelem < MAXNUM 149 && bufsize < MAXBUFSIZE) { 150 const u_char **keyp; 151 u_char *oldb = buffer; 152 153 /* buffer was too small for data, allocate 154 * bigger buffer */ 155 bufsize *= 2; 156 buffer = realloc(buffer, bufsize); 157 if (!buffer) { 158 err(2, "failed to realloc buffer to %ld bytes", 159 (unsigned long) bufsize); 160 } 161 bufend = buffer + bufsize; 162 163 /* patch up keylist[] */ 164 for(keyp = &keypos[-1]; keyp >= keylist; keyp--) 165 *keyp = buffer + (*keyp - oldb); 166 167 crec = (RECHEADER *) (buffer + ((u_char *)crec - oldb)); 168 goto do_read; 169 } 170 if (c == BUFFEND || ntfiles || mfct) { /* push */ 171 if (panic >= PANIC) { 172 fstack[MSTART + mfct].fp = ftmp(); 173 if ((stable_sort) 174 ? sradixsort(keylist, nelem, 175 weights, REC_D) 176 : radixsort(keylist, nelem, 177 weights, REC_D) ) 178 err(2, NULL); 179 append(keylist, nelem, depth, 180 fstack[MSTART + mfct].fp, putrec, 181 ftbl); 182 mfct++; 183 /* reduce number of open files */ 184 if (mfct == MERGE_FNUM ||(c == EOF && ntfiles)) { 185 tmpbuf = malloc(bufend - 186 crec->data); 187 memmove(tmpbuf, crec->data, 188 bufend - crec->data); 189 fstack[base + ntfiles].fp 190 = ftmp(); 191 fmerge(0, MSTART, filelist, 192 mfct, geteasy, 193 fstack[base].fp, 194 putrec, ftbl); 195 ntfiles++; 196 mfct = 0; 197 memmove(crec->data, tmpbuf, 198 bufend - crec->data); 199 free(tmpbuf); 200 } 201 } else { 202 fstack[base + ntfiles].fp= ftmp(); 203 onepass(keylist, depth, nelem, sizes, 204 weights, fstack[base + ntfiles].fp); 205 ntfiles++; 206 } 207 } 208 } 209 if (!ntfiles && !mfct) { /* everything in memory--pop */ 210 if (nelem > 1 211 && ((stable_sort) 212 ? sradixsort(keylist, nelem, weights, REC_D) 213 : radixsort(keylist, nelem, weights, REC_D) )) 214 err(2, NULL); 215 if (nelem > 0) 216 append(keylist, nelem, depth, outfp, putline, ftbl); 217 break; /* pop */ 218 } 219 if (panic >= PANIC) { 220 if (!ntfiles) 221 fmerge(0, MSTART, filelist, mfct, geteasy, 222 outfp, putline, ftbl); 223 else 224 fmerge(0, base, filelist, ntfiles, geteasy, 225 outfp, putline, ftbl); 226 break; 227 228 } 229 total = maxb = lastb = 0; /* find if one bin dominates */ 230 for (i = 0; i < NBINS; i++) 231 if (sizes[i]) { 232 if (sizes[i] > sizes[maxb]) 233 maxb = i; 234 lastb = i; 235 total += sizes[i]; 236 } 237 if (sizes[maxb] < max((total / 2) , BUFSIZE)) 238 maxb = lastb; /* otherwise pop after last bin */ 239 fstack[base].lastb = lastb; 240 fstack[base].maxb = maxb; 241 242 /* start refining next level. */ 243 getnext(-1, base, NULL, ntfiles, crec, bufend, 0); /* rewind */ 244 for (i = 0; i < maxb; i++) { 245 if (!sizes[i]) /* bin empty; step ahead file offset */ 246 getnext(i, base, NULL,ntfiles, crec, bufend, 0); 247 else 248 fsort(i, depth+1, base, filelist, ntfiles, 249 outfp, ftbl); 250 } 251 252 get = getnext; 253 254 if (lastb != maxb) { 255 if (prevfp != outfp) 256 tailfp[panic] = prevfp; 257 prevfp = ftmp(); 258 for (i = maxb+1; i <= lastb; i++) 259 if (!sizes[i]) 260 getnext(i, base, NULL, ntfiles, crec, 261 bufend,0); 262 else 263 fsort(i, depth+1, base, filelist, 264 ntfiles, prevfp, ftbl); 265 } 266 267 /* sort biggest (or last) bin at this level */ 268 depth++; 269 panic++; 270 binno = maxb; 271 top = base; 272 nfiles = ntfiles; /* so overwrite them */ 273 } 274 if (prevfp != outfp) { 275 concat(outfp, prevfp); 276 fclose(prevfp); 277 } 278 for (i = panic; i >= 0; --i) 279 if (tailfp[i]) { 280 concat(outfp, tailfp[i]); 281 fclose(tailfp[i]); 282 } 283 } 284 285 /* 286 * This is one pass of radix exchange, dumping the bins to disk. 287 */ 288 #define swap(a, b, t) t = a, a = b, b = t 289 void 290 onepass(a, depth, n, sizes, tr, fp) 291 const u_char **a; 292 int depth; 293 long n, sizes[]; 294 u_char *tr; 295 FILE *fp; 296 { 297 size_t tsizes[NBINS+1]; 298 const u_char **bin[257], ***bp, ***bpmax, **top[256], ***tp; 299 static int histo[256]; 300 int *hp; 301 int c; 302 const u_char **an, *t, **aj; 303 const u_char **ak, *r; 304 305 memset(tsizes, 0, sizeof(tsizes)); 306 depth += sizeof(TRECHEADER); 307 an = &a[n]; 308 for (ak = a; ak < an; ak++) { 309 histo[c = tr[**ak]]++; 310 tsizes[c] += ((const RECHEADER *) (*ak -= depth))->length; 311 } 312 313 bin[0] = a; 314 bpmax = bin + 256; 315 tp = top, hp = histo; 316 for (bp = bin; bp < bpmax; bp++) { 317 *tp++ = *(bp+1) = *bp + (c = *hp); 318 *hp++ = 0; 319 if (c <= 1) 320 continue; 321 } 322 for (aj = a; aj < an; *aj = r, aj = bin[c+1]) 323 for (r = *aj; aj < (ak = --top[c = tr[r[depth]]]) ;) 324 swap(*ak, r, t); 325 326 for (ak = a, c = 0; c < 256; c++) { 327 an = bin[c+1]; 328 n = an - ak; 329 tsizes[c] += n * sizeof(TRECHEADER); 330 /* tell getnext how many elements in this bin, this segment. */ 331 EWRITE(&tsizes[c], sizeof(size_t), 1, fp); 332 sizes[c] += tsizes[c]; 333 for (; ak < an; ++ak) 334 putrec((const RECHEADER *) *ak, fp); 335 } 336 } 337
Indexes created Sat Sep 27 14:09:57 GMT 2025