Home | History | Annotate | Line # | Download | only in sort
msort.c revision 1.12 
      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