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