fsort.c revision 1.33
1 /* $NetBSD: fsort.c,v 1.33 2009/08/15 09:48:46 dsl Exp $ */ 2 3 /*- 4 * Copyright (c) 2000-2003 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Ben Harris and Jaromir Dolecek. 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 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /*- 33 * Copyright (c) 1993 34 * The Regents of the University of California. All rights reserved. 35 * 36 * This code is derived from software contributed to Berkeley by 37 * Peter McIlroy. 38 * 39 * Redistribution and use in source and binary forms, with or without 40 * modification, are permitted provided that the following conditions 41 * are met: 42 * 1. Redistributions of source code must retain the above copyright 43 * notice, this list of conditions and the following disclaimer. 44 * 2. Redistributions in binary form must reproduce the above copyright 45 * notice, this list of conditions and the following disclaimer in the 46 * documentation and/or other materials provided with the distribution. 47 * 3. Neither the name of the University nor the names of its contributors 48 * may be used to endorse or promote products derived from this software 49 * without specific prior written permission. 50 * 51 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 52 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 53 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 54 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 55 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 56 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 57 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 59 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 60 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 61 * SUCH DAMAGE. 62 */ 63 64 /* 65 * Read in the next bin. If it fits in one segment sort it; 66 * otherwise refine it by segment deeper by one character, 67 * and try again on smaller bins. Sort the final bin at this level 68 * of recursion to keep the head of fstack at 0. 69 * After PANIC passes, abort to merge sort. 70 */ 71 #include "sort.h" 72 #include "fsort.h" 73 74 #ifndef lint 75 __RCSID("$NetBSD: fsort.c,v 1.33 2009/08/15 09:48:46 dsl Exp $"); 76 __SCCSID("@(#)fsort.c 8.1 (Berkeley) 6/6/93"); 77 #endif /* not lint */ 78 79 #include <stdlib.h> 80 #include <string.h> 81 82 static const u_char **keylist = 0; 83 u_char *buffer = 0, *linebuf = 0; 84 size_t bufsize = DEFBUFSIZE; 85 size_t linebuf_size; 86 #define FSORTMAX 4 87 int PANIC = FSORTMAX; 88 89 struct tempfile fstack[MAXFCT]; 90 #define MSTART (MAXFCT - MERGE_FNUM) 91 #define CHECKFSTACK(n) \ 92 if (n >= MAXFCT) \ 93 errx(2, "fstack: too many temporary files; use -H or sort in pieces") 94 95 #define SALIGN(n) ((n+sizeof(length_t)-1) & ~(sizeof(length_t)-1)) 96 97 void 98 fsort(int binno, int depth, int top, struct filelist *filelist, int nfiles, 99 FILE *outfp, struct field *ftbl) 100 { 101 const u_char **keypos; 102 u_char *bufend; 103 u_char *weights; 104 int ntfiles, mfct = 0, total, i, maxb, lastb, panic = 0; 105 int c, nelem, base; 106 long sizes [NBINS + 1]; 107 get_func_t get; 108 struct recheader *crec; 109 struct field tfield[2]; 110 FILE *prevfp, *tailfp[FSORTMAX + 1]; 111 u_char *nbuffer; 112 113 memset(tailfp, 0, sizeof(tailfp)); 114 prevfp = outfp; 115 memset(tfield, 0, sizeof(tfield)); 116 if (ftbl[0].flags & R) 117 tfield[0].weights = Rascii; 118 else 119 tfield[0].weights = ascii; 120 tfield[0].icol.num = 1; 121 weights = ftbl[0].weights; 122 if (!buffer) { 123 buffer = malloc(bufsize); 124 keylist = malloc(MAXNUM * sizeof(u_char *)); 125 memset(keylist, 0, MAXNUM * sizeof(u_char *)); 126 if (!SINGL_FLD) { 127 linebuf_size = DEFLLEN; 128 if ((linebuf = malloc(linebuf_size)) == NULL) 129 errx(2, "cannot allocate memory"); 130 } 131 } 132 bufend = buffer + bufsize; 133 if (binno >= 0) { 134 base = top + nfiles; 135 get = getnext; 136 } else { 137 base = 0; 138 if (SINGL_FLD) 139 get = makeline; 140 else 141 get = makekey; 142 } 143 for (;;) { 144 memset(sizes, 0, sizeof(sizes)); 145 c = nelem = ntfiles = 0; /* XXXGCC -Wuninitialized m68k */ 146 if (binno == weights[REC_D] && 147 !(SINGL_FLD && ftbl[0].flags & F)) { /* pop */ 148 rd_append(weights[REC_D], top, 149 nfiles, prevfp, buffer, bufend); 150 break; 151 } else if (binno == weights[REC_D]) { 152 depth = 0; /* start over on flat weights */ 153 ftbl = tfield; 154 weights = ftbl[0].weights; 155 } 156 keypos = keylist; /* XXXGCC -Wuninitialized m68k */ 157 crec = (RECHEADER *) buffer; /* XXXGCC -Wuninitialized m68k */ 158 while (c != EOF) { 159 keypos = keylist; 160 nelem = 0; 161 crec = (RECHEADER *) buffer; 162 163 do_read: 164 while ((c = get(binno, top, filelist, nfiles, crec, 165 bufend, ftbl)) == 0) { 166 *keypos++ = crec->data + depth; 167 if (++nelem == MAXNUM) { 168 c = BUFFEND; 169 break; 170 } 171 crec =(RECHEADER *)((char *) crec + 172 SALIGN(crec->length) + sizeof(TRECHEADER)); 173 } 174 175 if (c == BUFFEND && nelem < MAXNUM 176 && bufsize < MAXBUFSIZE) { 177 const u_char **keyp; 178 u_char *oldb = buffer; 179 180 /* buffer was too small for data, allocate 181 * bigger buffer */ 182 nbuffer = realloc(buffer, bufsize * 2); 183 if (!nbuffer) { 184 err(2, "failed to realloc buffer to %lu bytes", 185 (unsigned long) bufsize * 2); 186 } 187 buffer = nbuffer; 188 bufsize *= 2; 189 bufend = buffer + bufsize; 190 191 /* patch up keylist[] */ 192 for (keyp = &keypos[-1]; keyp >= keylist; keyp--) 193 *keyp = buffer + (*keyp - oldb); 194 195 crec = (RECHEADER *) (buffer + ((u_char *)crec - oldb)); 196 goto do_read; 197 } 198 199 if (c != BUFFEND && !ntfiles && !mfct) { 200 /* do not push */ 201 continue; 202 } 203 204 /* push */ 205 if (panic >= PANIC) { 206 fstack[MSTART + mfct].fp = ftmp(); 207 if ((stable_sort) 208 ? sradixsort(keylist, nelem, 209 weights, REC_D) 210 : radixsort(keylist, nelem, 211 weights, REC_D) ) 212 err(2, NULL); 213 append(keylist, nelem, depth, 214 fstack[MSTART + mfct].fp, putrec, 215 ftbl); 216 mfct++; 217 /* reduce number of open files */ 218 if (mfct == MERGE_FNUM ||(c == EOF && ntfiles)) { 219 /* 220 * Only copy extra incomplete crec 221 * data if there are any. 222 */ 223 int nodata = (bufend >= (u_char *)crec 224 && bufend <= crec->data); 225 size_t sz=0; 226 u_char *tmpbuf=NULL; 227 228 if (!nodata) { 229 sz = bufend - crec->data; 230 tmpbuf = malloc(sz); 231 memmove(tmpbuf, crec->data, sz); 232 } 233 234 CHECKFSTACK(base + ntfiles); 235 fstack[base + ntfiles].fp = ftmp(); 236 fmerge(0, MSTART, filelist, 237 mfct, geteasy, 238 fstack[base + ntfiles].fp, 239 putrec, ftbl); 240 ntfiles++; 241 mfct = 0; 242 243 if (!nodata) { 244 memmove(crec->data, tmpbuf, sz); 245 free(tmpbuf); 246 } 247 } 248 } else { 249 CHECKFSTACK(base + ntfiles); 250 fstack[base + ntfiles].fp = ftmp(); 251 onepass(keylist, depth, nelem, sizes, 252 weights, fstack[base + ntfiles].fp); 253 ntfiles++; 254 } 255 } 256 if (!ntfiles && !mfct) { /* everything in memory--pop */ 257 if (nelem > 1 258 && ((stable_sort) 259 ? sradixsort(keylist, nelem, weights, REC_D) 260 : radixsort(keylist, nelem, weights, REC_D) )) 261 err(2, NULL); 262 if (nelem > 0) 263 append(keylist, nelem, depth, outfp, putline, ftbl); 264 break; /* pop */ 265 } 266 if (panic >= PANIC) { 267 if (!ntfiles) 268 fmerge(0, MSTART, filelist, mfct, geteasy, 269 outfp, putline, ftbl); 270 else 271 fmerge(0, base, filelist, ntfiles, geteasy, 272 outfp, putline, ftbl); 273 break; 274 275 } 276 total = maxb = lastb = 0; /* find if one bin dominates */ 277 for (i = 0; i < NBINS; i++) 278 if (sizes[i]) { 279 if (sizes[i] > sizes[maxb]) 280 maxb = i; 281 lastb = i; 282 total += sizes[i]; 283 } 284 if (sizes[maxb] < max((total / 2) , BUFSIZE)) 285 maxb = lastb; /* otherwise pop after last bin */ 286 fstack[base].lastb = lastb; 287 fstack[base].maxb = maxb; 288 289 /* start refining next level. */ 290 getnext(-1, base, NULL, ntfiles, crec, bufend, 0); /* rewind */ 291 for (i = 0; i < maxb; i++) { 292 if (!sizes[i]) /* bin empty; step ahead file offset */ 293 getnext(i, base, NULL,ntfiles, crec, bufend, 0); 294 else 295 fsort(i, depth + 1, base, filelist, ntfiles, 296 outfp, ftbl); 297 } 298 299 get = getnext; 300 301 if (lastb != maxb) { 302 if (prevfp != outfp) 303 tailfp[panic] = prevfp; 304 prevfp = ftmp(); 305 for (i = maxb + 1; i <= lastb; i++) 306 if (!sizes[i]) 307 getnext(i, base, NULL, ntfiles, crec, 308 bufend,0); 309 else 310 fsort(i, depth + 1, base, filelist, 311 ntfiles, prevfp, ftbl); 312 } 313 314 /* sort biggest (or last) bin at this level */ 315 depth++; 316 panic++; 317 binno = maxb; 318 top = base; 319 nfiles = ntfiles; /* so overwrite them */ 320 } 321 if (prevfp != outfp) { 322 concat(outfp, prevfp); 323 fclose(prevfp); 324 } 325 for (i = panic; i >= 0; --i) 326 if (tailfp[i]) { 327 concat(outfp, tailfp[i]); 328 fclose(tailfp[i]); 329 } 330 331 /* If on top level, free our structures */ 332 if (depth == 0) { 333 free(keylist), keylist = NULL; 334 free(buffer), buffer = NULL; 335 } 336 } 337 338 /* 339 * This is one pass of radix exchange, dumping the bins to disk. 340 */ 341 #define swap(a, b, t) t = a, a = b, b = t 342 void 343 onepass(const u_char **a, int depth, long n, long sizes[], u_char *tr, FILE *fp) 344 { 345 size_t tsizes[NBINS + 1]; 346 const u_char **bin[257], ***bp, ***bpmax, **top[256], ***tp; 347 static int histo[256]; 348 int *hp; 349 int c; 350 const u_char **an, *t, **aj; 351 const u_char **ak, *r; 352 353 memset(tsizes, 0, sizeof(tsizes)); 354 depth += sizeof(TRECHEADER); 355 an = &a[n]; 356 for (ak = a; ak < an; ak++) { 357 histo[c = tr[**ak]]++; 358 tsizes[c] += ((const RECHEADER *) (*ak -= depth))->length; 359 } 360 361 bin[0] = a; 362 bpmax = bin + 256; 363 tp = top, hp = histo; 364 for (bp = bin; bp < bpmax; bp++) { 365 *tp++ = *(bp + 1) = *bp + (c = *hp); 366 *hp++ = 0; 367 if (c <= 1) 368 continue; 369 } 370 for (aj = a; aj < an; *aj = r, aj = bin[c + 1]) 371 for (r = *aj; aj < (ak = --top[c = tr[r[depth]]]) ;) 372 swap(*ak, r, t); 373 374 for (ak = a, c = 0; c < 256; c++) { 375 an = bin[c + 1]; 376 n = an - ak; 377 tsizes[c] += n * sizeof(TRECHEADER); 378 /* tell getnext how many elements in this bin, this segment. */ 379 EWRITE(&tsizes[c], sizeof(size_t), 1, fp); 380 sizes[c] += tsizes[c]; 381 for (; ak < an; ++ak) 382 putrec((const RECHEADER *) *ak, fp); 383 } 384 } 385
Indexes created Tue Sep 30 07:10:03 GMT 2025