fsort.c revision 1.34
1 /* $NetBSD: fsort.c,v 1.34 2009/08/15 16:50:29 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.34 2009/08/15 16:50:29 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; 84 size_t bufsize = DEFBUFSIZE; 85 #define FSORTMAX 4 86 int PANIC = FSORTMAX; 87 88 struct tempfile fstack[MAXFCT]; 89 #define MSTART (MAXFCT - MERGE_FNUM) 90 #define CHECKFSTACK(n) \ 91 if (n >= MAXFCT) \ 92 errx(2, "fstack: too many temporary files; use -H or sort in pieces") 93 94 #define SALIGN(n) ((n+sizeof(length_t)-1) & ~(sizeof(length_t)-1)) 95 96 void 97 fsort(int binno, int depth, int top, struct filelist *filelist, int nfiles, 98 FILE *outfp, struct field *ftbl) 99 { 100 const u_char **keypos; 101 u_char *bufend; 102 u_char *weights; 103 int ntfiles, mfct = 0, total, i, maxb, lastb, panic = 0; 104 int c, nelem, base; 105 long sizes [NBINS + 1]; 106 get_func_t get; 107 struct recheader *crec; 108 struct field tfield[2]; 109 FILE *prevfp, *tailfp[FSORTMAX + 1]; 110 u_char *nbuffer; 111 112 memset(tailfp, 0, sizeof(tailfp)); 113 prevfp = outfp; 114 memset(tfield, 0, sizeof(tfield)); 115 if (ftbl[0].flags & R) 116 tfield[0].weights = Rascii; 117 else 118 tfield[0].weights = ascii; 119 tfield[0].icol.num = 1; 120 weights = ftbl[0].weights; 121 if (!buffer) { 122 buffer = malloc(bufsize); 123 keylist = malloc(MAXNUM * sizeof(u_char *)); 124 memset(keylist, 0, MAXNUM * sizeof(u_char *)); 125 } 126 bufend = buffer + bufsize; 127 if (binno >= 0) { 128 base = top + nfiles; 129 get = getnext; 130 } else { 131 base = 0; 132 if (SINGL_FLD) 133 get = makeline; 134 else 135 get = makekey; 136 } 137 for (;;) { 138 memset(sizes, 0, sizeof(sizes)); 139 c = nelem = ntfiles = 0; /* XXXGCC -Wuninitialized m68k */ 140 if (binno == weights[REC_D] && 141 !(SINGL_FLD && ftbl[0].flags & F)) { /* pop */ 142 rd_append(weights[REC_D], top, 143 nfiles, prevfp, buffer, bufend); 144 break; 145 } else if (binno == weights[REC_D]) { 146 depth = 0; /* start over on flat weights */ 147 ftbl = tfield; 148 weights = ftbl[0].weights; 149 } 150 keypos = keylist; /* XXXGCC -Wuninitialized m68k */ 151 crec = (RECHEADER *) buffer; /* XXXGCC -Wuninitialized m68k */ 152 while (c != EOF) { 153 keypos = keylist; 154 nelem = 0; 155 crec = (RECHEADER *) buffer; 156 157 do_read: 158 while ((c = get(binno, top, filelist, nfiles, crec, 159 bufend, ftbl)) == 0) { 160 *keypos++ = crec->data + depth; 161 if (++nelem == MAXNUM) { 162 c = BUFFEND; 163 break; 164 } 165 crec =(RECHEADER *)((char *) crec + 166 SALIGN(crec->length) + sizeof(TRECHEADER)); 167 } 168 169 if (c == BUFFEND && nelem < MAXNUM 170 && bufsize < MAXBUFSIZE) { 171 const u_char **keyp; 172 u_char *oldb = buffer; 173 174 /* buffer was too small for data, allocate 175 * bigger buffer */ 176 nbuffer = realloc(buffer, bufsize * 2); 177 if (!nbuffer) { 178 err(2, "failed to realloc buffer to %lu bytes", 179 (unsigned long) bufsize * 2); 180 } 181 buffer = nbuffer; 182 bufsize *= 2; 183 bufend = buffer + bufsize; 184 185 /* patch up keylist[] */ 186 for (keyp = &keypos[-1]; keyp >= keylist; keyp--) 187 *keyp = buffer + (*keyp - oldb); 188 189 crec = (RECHEADER *) (buffer + ((u_char *)crec - oldb)); 190 goto do_read; 191 } 192 193 if (c != BUFFEND && !ntfiles && !mfct) { 194 /* do not push */ 195 continue; 196 } 197 198 /* push */ 199 if (panic >= PANIC) { 200 fstack[MSTART + mfct].fp = ftmp(); 201 if ((stable_sort) 202 ? sradixsort(keylist, nelem, 203 weights, REC_D) 204 : radixsort(keylist, nelem, 205 weights, REC_D) ) 206 err(2, NULL); 207 append(keylist, nelem, depth, 208 fstack[MSTART + mfct].fp, putrec, 209 ftbl); 210 mfct++; 211 /* reduce number of open files */ 212 if (mfct == MERGE_FNUM ||(c == EOF && ntfiles)) { 213 /* 214 * Only copy extra incomplete crec 215 * data if there are any. 216 */ 217 int nodata = (bufend >= (u_char *)crec 218 && bufend <= crec->data); 219 size_t sz=0; 220 u_char *tmpbuf=NULL; 221 222 if (!nodata) { 223 sz = bufend - crec->data; 224 tmpbuf = malloc(sz); 225 memmove(tmpbuf, crec->data, sz); 226 } 227 228 CHECKFSTACK(base + ntfiles); 229 fstack[base + ntfiles].fp = ftmp(); 230 fmerge(0, MSTART, filelist, 231 mfct, geteasy, 232 fstack[base + ntfiles].fp, 233 putrec, ftbl); 234 ntfiles++; 235 mfct = 0; 236 237 if (!nodata) { 238 memmove(crec->data, tmpbuf, sz); 239 free(tmpbuf); 240 } 241 } 242 } else { 243 CHECKFSTACK(base + ntfiles); 244 fstack[base + ntfiles].fp = ftmp(); 245 onepass(keylist, depth, nelem, sizes, 246 weights, fstack[base + ntfiles].fp); 247 ntfiles++; 248 } 249 } 250 if (!ntfiles && !mfct) { /* everything in memory--pop */ 251 if (nelem > 1 252 && ((stable_sort) 253 ? sradixsort(keylist, nelem, weights, REC_D) 254 : radixsort(keylist, nelem, weights, REC_D) )) 255 err(2, NULL); 256 if (nelem > 0) 257 append(keylist, nelem, depth, outfp, putline, ftbl); 258 break; /* pop */ 259 } 260 if (panic >= PANIC) { 261 if (!ntfiles) 262 fmerge(0, MSTART, filelist, mfct, geteasy, 263 outfp, putline, ftbl); 264 else 265 fmerge(0, base, filelist, ntfiles, geteasy, 266 outfp, putline, ftbl); 267 break; 268 269 } 270 total = maxb = lastb = 0; /* find if one bin dominates */ 271 for (i = 0; i < NBINS; i++) 272 if (sizes[i]) { 273 if (sizes[i] > sizes[maxb]) 274 maxb = i; 275 lastb = i; 276 total += sizes[i]; 277 } 278 if (sizes[maxb] < max((total / 2) , BUFSIZE)) 279 maxb = lastb; /* otherwise pop after last bin */ 280 fstack[base].lastb = lastb; 281 fstack[base].maxb = maxb; 282 283 /* start refining next level. */ 284 getnext(-1, base, NULL, ntfiles, crec, bufend, 0); /* rewind */ 285 for (i = 0; i < maxb; i++) { 286 if (!sizes[i]) /* bin empty; step ahead file offset */ 287 getnext(i, base, NULL,ntfiles, crec, bufend, 0); 288 else 289 fsort(i, depth + 1, base, filelist, ntfiles, 290 outfp, ftbl); 291 } 292 293 get = getnext; 294 295 if (lastb != maxb) { 296 if (prevfp != outfp) 297 tailfp[panic] = prevfp; 298 prevfp = ftmp(); 299 for (i = maxb + 1; i <= lastb; i++) 300 if (!sizes[i]) 301 getnext(i, base, NULL, ntfiles, crec, 302 bufend,0); 303 else 304 fsort(i, depth + 1, base, filelist, 305 ntfiles, prevfp, ftbl); 306 } 307 308 /* sort biggest (or last) bin at this level */ 309 depth++; 310 panic++; 311 binno = maxb; 312 top = base; 313 nfiles = ntfiles; /* so overwrite them */ 314 } 315 if (prevfp != outfp) { 316 concat(outfp, prevfp); 317 fclose(prevfp); 318 } 319 for (i = panic; i >= 0; --i) 320 if (tailfp[i]) { 321 concat(outfp, tailfp[i]); 322 fclose(tailfp[i]); 323 } 324 325 /* If on top level, free our structures */ 326 if (depth == 0) { 327 free(keylist), keylist = NULL; 328 free(buffer), buffer = NULL; 329 } 330 } 331 332 /* 333 * This is one pass of radix exchange, dumping the bins to disk. 334 */ 335 #define swap(a, b, t) t = a, a = b, b = t 336 void 337 onepass(const u_char **a, int depth, long n, long sizes[], u_char *tr, FILE *fp) 338 { 339 size_t tsizes[NBINS + 1]; 340 const u_char **bin[257], ***bp, ***bpmax, **top[256], ***tp; 341 static int histo[256]; 342 int *hp; 343 int c; 344 const u_char **an, *t, **aj; 345 const u_char **ak, *r; 346 347 memset(tsizes, 0, sizeof(tsizes)); 348 depth += sizeof(TRECHEADER); 349 an = &a[n]; 350 for (ak = a; ak < an; ak++) { 351 histo[c = tr[**ak]]++; 352 tsizes[c] += ((const RECHEADER *) (*ak -= depth))->length; 353 } 354 355 bin[0] = a; 356 bpmax = bin + 256; 357 tp = top, hp = histo; 358 for (bp = bin; bp < bpmax; bp++) { 359 *tp++ = *(bp + 1) = *bp + (c = *hp); 360 *hp++ = 0; 361 if (c <= 1) 362 continue; 363 } 364 for (aj = a; aj < an; *aj = r, aj = bin[c + 1]) 365 for (r = *aj; aj < (ak = --top[c = tr[r[depth]]]) ;) 366 swap(*ak, r, t); 367 368 for (ak = a, c = 0; c < 256; c++) { 369 an = bin[c + 1]; 370 n = an - ak; 371 tsizes[c] += n * sizeof(TRECHEADER); 372 /* tell getnext how many elements in this bin, this segment. */ 373 EWRITE(&tsizes[c], sizeof(size_t), 1, fp); 374 sizes[c] += tsizes[c]; 375 for (; ak < an; ++ak) 376 putrec((const RECHEADER *) *ak, fp); 377 } 378 } 379
Indexes created Tue Sep 30 11:09:46 GMT 2025