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