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