fsort.c revision 1.17
1 /* $NetBSD: fsort.c,v 1.17 2001/02/20 18:33:09 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.17 2001/02/20 18:33:09 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 = DEFLLEN; 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 < min(9, MAXNUM)) { 149 const u_char **keyp; 150 u_char *oldb = buffer; 151 152 /* buffer was too small for data, allocate 153 * bigger buffer */ 154 bufsize *= 2; 155 buffer = realloc(buffer, bufsize); 156 if (!buffer) { 157 err(2, "failed to realloc buffer to %ld bytes", 158 (unsigned long) bufsize); 159 } 160 bufend = buffer + bufsize; 161 162 /* patch up keylist[] */ 163 for(keyp = &keypos[-1]; keyp >= keylist; keyp--) 164 *keyp = buffer + (*keyp - oldb); 165 166 crec = (RECHEADER *) (buffer + ((u_char *)crec - oldb)); 167 goto do_read; 168 } 169 if (c == BUFFEND || ntfiles || mfct) { /* push */ 170 if (panic >= PANIC) { 171 fstack[MSTART + mfct].fp = ftmp(); 172 if ((stable_sort) 173 ? sradixsort(keylist, nelem, 174 weights, REC_D) 175 : radixsort(keylist, nelem, 176 weights, REC_D) ) 177 err(2, NULL); 178 append(keylist, nelem, depth, 179 fstack[MSTART + mfct].fp, putrec, 180 ftbl); 181 mfct++; 182 /* reduce number of open files */ 183 if (mfct == MERGE_FNUM ||(c == EOF && ntfiles)) { 184 tmpbuf = malloc(bufend - 185 crec->data); 186 memmove(tmpbuf, crec->data, 187 bufend - crec->data); 188 fstack[base + ntfiles].fp 189 = ftmp(); 190 fmerge(0, MSTART, filelist, 191 mfct, geteasy, 192 fstack[base].fp, 193 putrec, ftbl); 194 ntfiles++; 195 mfct = 0; 196 memmove(crec->data, tmpbuf, 197 bufend - crec->data); 198 free(tmpbuf); 199 } 200 } else { 201 fstack[base + ntfiles].fp= ftmp(); 202 onepass(keylist, depth, nelem, sizes, 203 weights, fstack[base + ntfiles].fp); 204 ntfiles++; 205 } 206 } 207 } 208 if (!ntfiles && !mfct) { /* everything in memory--pop */ 209 if (nelem > 1 210 && ((stable_sort) 211 ? sradixsort(keylist, nelem, weights, REC_D) 212 : radixsort(keylist, nelem, weights, REC_D) )) 213 err(2, NULL); 214 if (nelem > 0) 215 append(keylist, nelem, depth, outfp, putline, ftbl); 216 break; /* pop */ 217 } 218 if (panic >= PANIC) { 219 if (!ntfiles) 220 fmerge(0, MSTART, filelist, mfct, geteasy, 221 outfp, putline, ftbl); 222 else 223 fmerge(0, base, filelist, ntfiles, geteasy, 224 outfp, putline, ftbl); 225 break; 226 227 } 228 total = maxb = lastb = 0; /* find if one bin dominates */ 229 for (i = 0; i < NBINS; i++) 230 if (sizes[i]) { 231 if (sizes[i] > sizes[maxb]) 232 maxb = i; 233 lastb = i; 234 total += sizes[i]; 235 } 236 if (sizes[maxb] < max((total / 2) , BUFSIZE)) 237 maxb = lastb; /* otherwise pop after last bin */ 238 fstack[base].lastb = lastb; 239 fstack[base].maxb = maxb; 240 241 /* start refining next level. */ 242 getnext(-1, base, NULL, ntfiles, crec, bufend, 0); /* rewind */ 243 for (i = 0; i < maxb; i++) { 244 if (!sizes[i]) /* bin empty; step ahead file offset */ 245 getnext(i, base, NULL,ntfiles, crec, bufend, 0); 246 else 247 fsort(i, depth+1, base, filelist, ntfiles, 248 outfp, ftbl); 249 } 250 251 get = getnext; 252 253 if (lastb != maxb) { 254 if (prevfp != outfp) 255 tailfp[panic] = prevfp; 256 prevfp = ftmp(); 257 for (i = maxb+1; i <= lastb; i++) 258 if (!sizes[i]) 259 getnext(i, base, NULL, ntfiles, crec, 260 bufend,0); 261 else 262 fsort(i, depth+1, base, filelist, 263 ntfiles, prevfp, ftbl); 264 } 265 266 /* sort biggest (or last) bin at this level */ 267 depth++; 268 panic++; 269 binno = maxb; 270 top = base; 271 nfiles = ntfiles; /* so overwrite them */ 272 } 273 if (prevfp != outfp) { 274 concat(outfp, prevfp); 275 fclose(prevfp); 276 } 277 for (i = panic; i >= 0; --i) 278 if (tailfp[i]) { 279 concat(outfp, tailfp[i]); 280 fclose(tailfp[i]); 281 } 282 } 283 284 /* 285 * This is one pass of radix exchange, dumping the bins to disk. 286 */ 287 #define swap(a, b, t) t = a, a = b, b = t 288 void 289 onepass(a, depth, n, sizes, tr, fp) 290 const u_char **a; 291 int depth; 292 long n, sizes[]; 293 u_char *tr; 294 FILE *fp; 295 { 296 size_t tsizes[NBINS+1]; 297 const u_char **bin[257], ***bp, ***bpmax, **top[256], ***tp; 298 static int histo[256]; 299 int *hp; 300 int c; 301 const u_char **an, *t, **aj; 302 const u_char **ak, *r; 303 304 memset(tsizes, 0, sizeof(tsizes)); 305 depth += sizeof(TRECHEADER); 306 an = &a[n]; 307 for (ak = a; ak < an; ak++) { 308 histo[c = tr[**ak]]++; 309 tsizes[c] += ((const RECHEADER *) (*ak -= depth))->length; 310 } 311 312 bin[0] = a; 313 bpmax = bin + 256; 314 tp = top, hp = histo; 315 for (bp = bin; bp < bpmax; bp++) { 316 *tp++ = *(bp+1) = *bp + (c = *hp); 317 *hp++ = 0; 318 if (c <= 1) 319 continue; 320 } 321 for (aj = a; aj < an; *aj = r, aj = bin[c+1]) 322 for (r = *aj; aj < (ak = --top[c = tr[r[depth]]]) ;) 323 swap(*ak, r, t); 324 325 for (ak = a, c = 0; c < 256; c++) { 326 an = bin[c+1]; 327 n = an - ak; 328 tsizes[c] += n * sizeof(TRECHEADER); 329 /* tell getnext how many elements in this bin, this segment. */ 330 EWRITE(&tsizes[c], sizeof(size_t), 1, fp); 331 sizes[c] += tsizes[c]; 332 for (; ak < an; ++ak) 333 putrec((const RECHEADER *) *ak, fp); 334 } 335 } 336
Indexes created Sun Sep 28 16:09:52 GMT 2025