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