msort.c revision 1.15
1 /* $NetBSD: msort.c,v 1.15 2003/10/16 07:01:51 itojun 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 #include "sort.h" 72 #include "fsort.h" 73 74 #ifndef lint 75 __RCSID("$NetBSD: msort.c,v 1.15 2003/10/16 07:01:51 itojun Exp $"); 76 __SCCSID("@(#)msort.c 8.1 (Berkeley) 6/6/93"); 77 #endif /* not lint */ 78 79 #include <stdlib.h> 80 #include <string.h> 81 #include <unistd.h> 82 83 /* Subroutines using comparisons: merge sort and check order */ 84 #define DELETE (1) 85 86 typedef struct mfile { 87 u_char *end; 88 short flno; 89 struct recheader rec[1]; 90 } MFILE; 91 92 static u_char *wts, *wts1 = NULL; 93 94 static int cmp __P((RECHEADER *, RECHEADER *)); 95 static int insert __P((struct mfile **, struct mfile **, int, int)); 96 static void merge(int, int, get_func_t, FILE *, put_func_t, struct field *); 97 98 void 99 fmerge(binno, top, filelist, nfiles, get, outfp, fput, ftbl) 100 int binno, top; 101 struct filelist *filelist; 102 int nfiles; 103 get_func_t get; 104 FILE *outfp; 105 put_func_t fput; 106 struct field *ftbl; 107 { 108 FILE *tout; 109 int i, j, last; 110 put_func_t put; 111 struct tempfile *l_fstack; 112 113 wts = ftbl->weights; 114 if (!UNIQUE && SINGL_FLD && ftbl->flags & F) 115 wts1 = (ftbl->flags & R) ? Rascii : ascii; 116 117 if (!buffer) { 118 buffer = malloc(bufsize); 119 if (!buffer) 120 err(2, "fmerge(): malloc"); 121 122 if (!linebuf && !SINGL_FLD) { 123 linebuf_size = DEFLLEN; 124 linebuf = malloc(linebuf_size); 125 } 126 } 127 128 if (binno >= 0) 129 l_fstack = fstack + top; 130 else 131 l_fstack = fstack; 132 133 while (nfiles) { 134 put = putrec; 135 for (j = 0; j < nfiles; j += MERGE_FNUM) { 136 if (nfiles <= MERGE_FNUM) { 137 tout = outfp; 138 put = fput; 139 } 140 else 141 tout = ftmp(); 142 last = min(MERGE_FNUM, nfiles - j); 143 if (binno < 0) { 144 for (i = 0; i < last; i++) 145 if (!(l_fstack[i+MAXFCT-1-MERGE_FNUM].fp = 146 fopen(filelist->names[j+i], "r"))) 147 err(2, "%s", 148 filelist->names[j+i]); 149 merge(MAXFCT-1-MERGE_FNUM, last, get, tout, put, ftbl); 150 } else { 151 for (i = 0; i< last; i++) 152 rewind(l_fstack[i+j].fp); 153 merge(top+j, last, get, tout, put, ftbl); 154 } 155 if (nfiles > MERGE_FNUM) 156 l_fstack[j/MERGE_FNUM].fp = tout; 157 } 158 nfiles = (nfiles + (MERGE_FNUM - 1)) / MERGE_FNUM; 159 if (nfiles == 1) 160 nfiles = 0; 161 if (binno < 0) { 162 binno = 0; 163 get = geteasy; 164 top = 0; 165 } 166 } 167 } 168 169 static void 170 merge(infl0, nfiles, get, outfp, put, ftbl) 171 int infl0, nfiles; 172 get_func_t get; 173 put_func_t put; 174 FILE *outfp; 175 struct field *ftbl; 176 { 177 int c, i, j, nf = nfiles; 178 struct mfile *flistb[MERGE_FNUM], **flist = flistb, *cfile; 179 size_t availsz = bufsize; 180 static void *bufs[MERGE_FNUM+1]; 181 static size_t bufs_sz[MERGE_FNUM+1]; 182 183 /* 184 * We need nfiles + 1 buffers. One is 'buffer', the 185 * rest needs to be allocated. 186 */ 187 bufs[0] = buffer; 188 bufs_sz[0] = bufsize; 189 for(i=1; i < nfiles+1; i++) { 190 if (bufs[i]) 191 continue; 192 193 bufs[i] = malloc(DEFLLEN); 194 if (!bufs[i]) 195 err(2, "merge: malloc"); 196 bufs_sz[i] = DEFLLEN; 197 } 198 199 for (i = j = 0; i < nfiles; i++, j++) { 200 cfile = (struct mfile *) bufs[j]; 201 cfile->flno = infl0 + j; 202 cfile->end = (u_char *) bufs[j] + bufs_sz[j]; 203 for (c = 1; c == 1;) { 204 if (EOF == (c = get(cfile->flno, 0, NULL, nfiles, 205 cfile->rec, cfile->end, ftbl))) { 206 --i; 207 --nfiles; 208 break; 209 } 210 211 if (c == BUFFEND) { 212 cfile = realloc(bufs[j], bufs_sz[j]); 213 if (!cfile) 214 err(2, "merge: realloc"); 215 216 bufs[j] = (void *) cfile; 217 bufs_sz[j] *= 2; 218 cfile->end = (u_char *)cfile + bufs_sz[j]; 219 220 c = 1; 221 continue; 222 } 223 224 if (i) 225 c = insert(flist, &cfile, i, !DELETE); 226 else 227 flist[0] = cfile; 228 } 229 } 230 231 cfile = (struct mfile *) bufs[nf]; 232 cfile->flno = flist[0]->flno; 233 cfile->end = (u_char *) cfile + bufs_sz[nf]; 234 while (nfiles) { 235 for (c = 1; c == 1;) { 236 if (EOF == (c = get(cfile->flno, 0, NULL, nfiles, 237 cfile->rec, cfile->end, ftbl))) { 238 put(flist[0]->rec, outfp); 239 if (--nfiles > 0) { 240 flist++; 241 cfile->flno = flist[0]->flno; 242 } 243 break; 244 } 245 if (c == BUFFEND) { 246 char *oldbuf = (char *) cfile; 247 availsz = (char *) cfile->end - oldbuf; 248 availsz *= 2; 249 cfile = realloc(oldbuf, availsz); 250 if (!cfile) 251 err(2, "merge: realloc"); 252 253 for(i=0; i < nf+1; i++) { 254 if (bufs[i] == oldbuf) { 255 bufs[i] = (char *)cfile; 256 bufs_sz[i] = availsz; 257 break; 258 } 259 } 260 261 cfile->end = (u_char *)cfile + availsz; 262 c = 1; 263 continue; 264 } 265 266 if (!(c = insert(flist, &cfile, nfiles, DELETE))) 267 put(cfile->rec, outfp); 268 } 269 } 270 271 if (bufs_sz[0] > bufsize) { 272 buffer = bufs[0]; 273 bufsize = bufs_sz[0]; 274 } 275 } 276 277 /* 278 * if delete: inserts *rec in flist, deletes flist[0], and leaves it in *rec; 279 * otherwise just inserts *rec in flist. 280 */ 281 static int 282 insert(flist, rec, ttop, delete) 283 struct mfile **flist, **rec; 284 int delete, ttop; /* delete = 0 or 1 */ 285 { 286 struct mfile *tmprec = *rec; 287 int mid, top = ttop, bot = 0, cmpv = 1; 288 289 for (mid = top/2; bot +1 != top; mid = (bot+top)/2) { 290 cmpv = cmp(tmprec->rec, flist[mid]->rec); 291 if (cmpv < 0) 292 top = mid; 293 else if (cmpv > 0) 294 bot = mid; 295 else { 296 if (UNIQUE) 297 break; 298 299 if (stable_sort) { 300 /* 301 * Apply sort by fileno, to give priority 302 * to earlier specified files, hence providing 303 * more stable sort. 304 * If fileno is same, the new record should 305 * be put _after_ the previous entry. 306 */ 307 cmpv = tmprec->flno - flist[mid]->flno; 308 if (cmpv >= 0) 309 bot = mid; 310 else /* cmpv == 0 */ 311 bot = mid - 1; 312 } else { 313 /* non-stable sort */ 314 bot = mid - 1; 315 } 316 317 break; 318 } 319 } 320 321 if (delete) { 322 if (UNIQUE) { 323 if (!bot && cmpv) 324 cmpv = cmp(tmprec->rec, flist[0]->rec); 325 if (!cmpv) 326 return (1); 327 } 328 tmprec = flist[0]; 329 if (bot) 330 memmove(flist, flist+1, bot * sizeof(MFILE **)); 331 flist[bot] = *rec; 332 *rec = tmprec; 333 (*rec)->flno = flist[0]->flno; 334 return (0); 335 } else { 336 if (!bot && !(UNIQUE && !cmpv)) { 337 cmpv = cmp(tmprec->rec, flist[0]->rec); 338 if (cmpv < 0) 339 bot = -1; 340 } 341 if (UNIQUE && !cmpv) 342 return (1); 343 bot++; 344 memmove(flist + bot+1, flist + bot, 345 (ttop - bot) * sizeof(MFILE **)); 346 flist[bot] = *rec; 347 return (0); 348 } 349 } 350 351 /* 352 * check order on one file 353 */ 354 void 355 order(filelist, get, ftbl) 356 struct filelist *filelist; 357 get_func_t get; 358 struct field *ftbl; 359 { 360 u_char *crec_end, *prec_end, *trec_end; 361 int c; 362 RECHEADER *crec, *prec, *trec; 363 364 if (!SINGL_FLD) 365 linebuf = malloc(DEFLLEN); 366 buffer = malloc(2 * (DEFLLEN + sizeof(TRECHEADER))); 367 crec = (RECHEADER *) buffer; 368 crec_end = buffer + DEFLLEN + sizeof(TRECHEADER); 369 prec = (RECHEADER *) (buffer + DEFLLEN + sizeof(TRECHEADER)); 370 prec_end = buffer + 2*(DEFLLEN + sizeof(TRECHEADER)); 371 wts = ftbl->weights; 372 if (SINGL_FLD && (ftbl->flags & F)) 373 wts1 = (ftbl->flags & R) ? Rascii : ascii; 374 else 375 wts1 = NULL; 376 if (0 == get(-1, 0, filelist, 1, prec, prec_end, ftbl)) 377 while (0 == get(-1, 0, filelist, 1, crec, crec_end, ftbl)) { 378 if (0 < (c = cmp(prec, crec))) { 379 crec->data[crec->length-1] = 0; 380 errx(1, "found disorder: %s", crec->data+crec->offset); 381 } 382 if (UNIQUE && !c) { 383 crec->data[crec->length-1] = 0; 384 errx(1, "found non-uniqueness: %s", 385 crec->data+crec->offset); 386 } 387 /* 388 * Swap pointers so that this record is on place pointed 389 * to by prec and new record is read to place pointed to by 390 * crec. 391 */ 392 trec = prec; 393 prec = crec; 394 crec = trec; 395 trec_end = prec_end; 396 prec_end = crec_end; 397 crec_end = trec_end; 398 } 399 exit(0); 400 } 401 402 static int 403 cmp(rec1, rec2) 404 RECHEADER *rec1, *rec2; 405 { 406 int r; 407 u_char *pos1, *pos2, *end; 408 u_char *cwts; 409 for (cwts = wts; cwts; cwts = (cwts == wts1 ? NULL : wts1)) { 410 pos1 = rec1->data; 411 pos2 = rec2->data; 412 if (!SINGL_FLD && (UNIQUE || stable_sort)) 413 end = pos1 + min(rec1->offset, rec2->offset); 414 else 415 end = pos1 + min(rec1->length, rec2->length); 416 417 for (; pos1 < end; ) { 418 if ((r = cwts[*pos1++] - cwts[*pos2++])) 419 return (r); 420 } 421 } 422 return (0); 423 } 424
Indexes created Mon Oct 27 04:09:48 GMT 2025