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