msort.c revision 1.13
1 /* $NetBSD: msort.c,v 1.13 2003/08/07 11:15:54 agc 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. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 #include "sort.h" 36 #include "fsort.h" 37 38 #ifndef lint 39 __RCSID("$NetBSD: msort.c,v 1.13 2003/08/07 11:15:54 agc Exp $"); 40 __SCCSID("@(#)msort.c 8.1 (Berkeley) 6/6/93"); 41 #endif /* not lint */ 42 43 #include <stdlib.h> 44 #include <string.h> 45 #include <unistd.h> 46 47 /* Subroutines using comparisons: merge sort and check order */ 48 #define DELETE (1) 49 50 typedef struct mfile { 51 u_char *end; 52 short flno; 53 struct recheader rec[1]; 54 } MFILE; 55 56 static u_char *wts, *wts1 = NULL; 57 58 static int cmp __P((RECHEADER *, RECHEADER *)); 59 static int insert __P((struct mfile **, struct mfile **, int, int)); 60 static void merge(int, int, get_func_t, FILE *, put_func_t, struct field *); 61 62 void 63 fmerge(binno, top, filelist, nfiles, get, outfp, fput, ftbl) 64 int binno, top; 65 struct filelist *filelist; 66 int nfiles; 67 get_func_t get; 68 FILE *outfp; 69 put_func_t fput; 70 struct field *ftbl; 71 { 72 FILE *tout; 73 int i, j, last; 74 put_func_t put; 75 struct tempfile *l_fstack; 76 77 wts = ftbl->weights; 78 if (!UNIQUE && SINGL_FLD && ftbl->flags & F) 79 wts1 = (ftbl->flags & R) ? Rascii : ascii; 80 81 if (!buffer) { 82 buffer = malloc(bufsize); 83 if (!buffer) 84 err(2, "fmerge(): malloc"); 85 86 if (!linebuf && !SINGL_FLD) { 87 linebuf_size = DEFLLEN; 88 linebuf = malloc(linebuf_size); 89 } 90 } 91 92 if (binno >= 0) 93 l_fstack = fstack + top; 94 else 95 l_fstack = fstack; 96 97 while (nfiles) { 98 put = putrec; 99 for (j = 0; j < nfiles; j += MERGE_FNUM) { 100 if (nfiles <= MERGE_FNUM) { 101 tout = outfp; 102 put = fput; 103 } 104 else 105 tout = ftmp(); 106 last = min(MERGE_FNUM, nfiles - j); 107 if (binno < 0) { 108 for (i = 0; i < last; i++) 109 if (!(l_fstack[i+MAXFCT-1-MERGE_FNUM].fp = 110 fopen(filelist->names[j+i], "r"))) 111 err(2, "%s", 112 filelist->names[j+i]); 113 merge(MAXFCT-1-MERGE_FNUM, last, get, tout, put, ftbl); 114 } else { 115 for (i = 0; i< last; i++) 116 rewind(l_fstack[i+j].fp); 117 merge(top+j, last, get, tout, put, ftbl); 118 } 119 if (nfiles > MERGE_FNUM) 120 l_fstack[j/MERGE_FNUM].fp = tout; 121 } 122 nfiles = (nfiles + (MERGE_FNUM - 1)) / MERGE_FNUM; 123 if (nfiles == 1) 124 nfiles = 0; 125 if (binno < 0) { 126 binno = 0; 127 get = geteasy; 128 top = 0; 129 } 130 } 131 } 132 133 static void 134 merge(infl0, nfiles, get, outfp, put, ftbl) 135 int infl0, nfiles; 136 get_func_t get; 137 put_func_t put; 138 FILE *outfp; 139 struct field *ftbl; 140 { 141 int c, i, j, nf = nfiles; 142 struct mfile *flistb[MERGE_FNUM], **flist = flistb, *cfile; 143 size_t availsz = bufsize; 144 static void *bufs[MERGE_FNUM+1]; 145 static size_t bufs_sz[MERGE_FNUM+1]; 146 147 /* 148 * We need nfiles + 1 buffers. One is 'buffer', the 149 * rest needs to be allocated. 150 */ 151 bufs[0] = buffer; 152 bufs_sz[0] = bufsize; 153 for(i=1; i < nfiles+1; i++) { 154 if (bufs[i]) 155 continue; 156 157 bufs[i] = malloc(DEFLLEN); 158 if (!bufs[i]) 159 err(2, "merge: malloc"); 160 bufs_sz[i] = DEFLLEN; 161 } 162 163 for (i = j = 0; i < nfiles; i++, j++) { 164 cfile = (struct mfile *) bufs[j]; 165 cfile->flno = infl0 + j; 166 cfile->end = (u_char *) bufs[j] + bufs_sz[j]; 167 for (c = 1; c == 1;) { 168 if (EOF == (c = get(cfile->flno, 0, NULL, nfiles, 169 cfile->rec, cfile->end, ftbl))) { 170 --i; 171 --nfiles; 172 break; 173 } 174 175 if (c == BUFFEND) { 176 cfile = realloc(bufs[j], bufs_sz[j] *= 2); 177 if (!cfile) 178 err(2, "merge: realloc"); 179 180 bufs[j] = (void *) cfile; 181 cfile->end = (u_char *)cfile + bufs_sz[j]; 182 183 c = 1; 184 continue; 185 } 186 187 if (i) 188 c = insert(flist, &cfile, i, !DELETE); 189 else 190 flist[0] = cfile; 191 } 192 } 193 194 cfile = (struct mfile *) bufs[nf]; 195 cfile->flno = flist[0]->flno; 196 cfile->end = (u_char *) cfile + bufs_sz[nf]; 197 while (nfiles) { 198 for (c = 1; c == 1;) { 199 if (EOF == (c = get(cfile->flno, 0, NULL, nfiles, 200 cfile->rec, cfile->end, ftbl))) { 201 put(flist[0]->rec, outfp); 202 if (--nfiles > 0) { 203 flist++; 204 cfile->flno = flist[0]->flno; 205 } 206 break; 207 } 208 if (c == BUFFEND) { 209 char *oldbuf = (char *) cfile; 210 availsz = (char *) cfile->end - oldbuf; 211 availsz *= 2; 212 cfile = realloc(oldbuf, availsz); 213 if (!cfile) 214 err(2, "merge: realloc"); 215 216 for(i=0; i < nf+1; i++) { 217 if (bufs[i] == oldbuf) { 218 bufs[i] = (char *)cfile; 219 bufs_sz[i] = availsz; 220 break; 221 } 222 } 223 224 cfile->end = (u_char *)cfile + availsz; 225 c = 1; 226 continue; 227 } 228 229 if (!(c = insert(flist, &cfile, nfiles, DELETE))) 230 put(cfile->rec, outfp); 231 } 232 } 233 234 if (bufs_sz[0] > bufsize) { 235 buffer = bufs[0]; 236 bufsize = bufs_sz[0]; 237 } 238 } 239 240 /* 241 * if delete: inserts *rec in flist, deletes flist[0], and leaves it in *rec; 242 * otherwise just inserts *rec in flist. 243 */ 244 static int 245 insert(flist, rec, ttop, delete) 246 struct mfile **flist, **rec; 247 int delete, ttop; /* delete = 0 or 1 */ 248 { 249 struct mfile *tmprec = *rec; 250 int mid, top = ttop, bot = 0, cmpv = 1; 251 252 for (mid = top/2; bot +1 != top; mid = (bot+top)/2) { 253 cmpv = cmp(tmprec->rec, flist[mid]->rec); 254 if (cmpv < 0) 255 top = mid; 256 else if (cmpv > 0) 257 bot = mid; 258 else { 259 if (UNIQUE) 260 break; 261 262 if (stable_sort) { 263 /* 264 * Apply sort by fileno, to give priority 265 * to earlier specified files, hence providing 266 * more stable sort. 267 * If fileno is same, the new record should 268 * be put _after_ the previous entry. 269 */ 270 cmpv = tmprec->flno - flist[mid]->flno; 271 if (cmpv >= 0) 272 bot = mid; 273 else /* cmpv == 0 */ 274 bot = mid - 1; 275 } else { 276 /* non-stable sort */ 277 bot = mid - 1; 278 } 279 280 break; 281 } 282 } 283 284 if (delete) { 285 if (UNIQUE) { 286 if (!bot && cmpv) 287 cmpv = cmp(tmprec->rec, flist[0]->rec); 288 if (!cmpv) 289 return (1); 290 } 291 tmprec = flist[0]; 292 if (bot) 293 memmove(flist, flist+1, bot * sizeof(MFILE **)); 294 flist[bot] = *rec; 295 *rec = tmprec; 296 (*rec)->flno = flist[0]->flno; 297 return (0); 298 } else { 299 if (!bot && !(UNIQUE && !cmpv)) { 300 cmpv = cmp(tmprec->rec, flist[0]->rec); 301 if (cmpv < 0) 302 bot = -1; 303 } 304 if (UNIQUE && !cmpv) 305 return (1); 306 bot++; 307 memmove(flist + bot+1, flist + bot, 308 (ttop - bot) * sizeof(MFILE **)); 309 flist[bot] = *rec; 310 return (0); 311 } 312 } 313 314 /* 315 * check order on one file 316 */ 317 void 318 order(filelist, get, ftbl) 319 struct filelist *filelist; 320 get_func_t get; 321 struct field *ftbl; 322 { 323 u_char *crec_end, *prec_end, *trec_end; 324 int c; 325 RECHEADER *crec, *prec, *trec; 326 327 if (!SINGL_FLD) 328 linebuf = malloc(DEFLLEN); 329 buffer = malloc(2 * (DEFLLEN + sizeof(TRECHEADER))); 330 crec = (RECHEADER *) buffer; 331 crec_end = buffer + DEFLLEN + sizeof(TRECHEADER); 332 prec = (RECHEADER *) (buffer + DEFLLEN + sizeof(TRECHEADER)); 333 prec_end = buffer + 2*(DEFLLEN + sizeof(TRECHEADER)); 334 wts = ftbl->weights; 335 if (SINGL_FLD && (ftbl->flags & F)) 336 wts1 = (ftbl->flags & R) ? Rascii : ascii; 337 else 338 wts1 = NULL; 339 if (0 == get(-1, 0, filelist, 1, prec, prec_end, ftbl)) 340 while (0 == get(-1, 0, filelist, 1, crec, crec_end, ftbl)) { 341 if (0 < (c = cmp(prec, crec))) { 342 crec->data[crec->length-1] = 0; 343 errx(1, "found disorder: %s", crec->data+crec->offset); 344 } 345 if (UNIQUE && !c) { 346 crec->data[crec->length-1] = 0; 347 errx(1, "found non-uniqueness: %s", 348 crec->data+crec->offset); 349 } 350 /* 351 * Swap pointers so that this record is on place pointed 352 * to by prec and new record is read to place pointed to by 353 * crec. 354 */ 355 trec = prec; 356 prec = crec; 357 crec = trec; 358 trec_end = prec_end; 359 prec_end = crec_end; 360 crec_end = trec_end; 361 } 362 exit(0); 363 } 364 365 static int 366 cmp(rec1, rec2) 367 RECHEADER *rec1, *rec2; 368 { 369 int r; 370 u_char *pos1, *pos2, *end; 371 u_char *cwts; 372 for (cwts = wts; cwts; cwts = (cwts == wts1 ? NULL : wts1)) { 373 pos1 = rec1->data; 374 pos2 = rec2->data; 375 if (!SINGL_FLD && (UNIQUE || stable_sort)) 376 end = pos1 + min(rec1->offset, rec2->offset); 377 else 378 end = pos1 + min(rec1->length, rec2->length); 379 380 for (; pos1 < end; ) { 381 if ((r = cwts[*pos1++] - cwts[*pos2++])) 382 return (r); 383 } 384 } 385 return (0); 386 } 387
Indexes created Fri Oct 31 11:10:07 GMT 2025