Home | History | Annotate | Line # | Download | only in sort
fsort.c revision 1.9 
      1 /*	$NetBSD: fsort.c,v 1.9 2001/01/13 17:27:21 itojun 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 /*
     40  * Read in the next bin.  If it fits in one segment sort it;
     41  * otherwise refine it by segment deeper by one character,
     42  * and try again on smaller bins.  Sort the final bin at this level
     43  * of recursion to keep the head of fstack at 0.
     44  * After PANIC passes, abort to merge sort.
     45 */
     46 #include "sort.h"
     47 #include "fsort.h"
     48 
     49 #ifndef lint
     50 __RCSID("$NetBSD: fsort.c,v 1.9 2001/01/13 17:27:21 itojun Exp $");
     51 __SCCSID("@(#)fsort.c	8.1 (Berkeley) 6/6/93");
     52 #endif /* not lint */
     53 
     54 #include <stdlib.h>
     55 #include <string.h>
     56 
     57 const u_char **keylist = 0;
     58 u_char *buffer = 0, *linebuf = 0;
     59 size_t bufsize, linebuf_size;
     60 struct tempfile fstack[MAXFCT];
     61 extern char *toutpath;
     62 #define FSORTMAX 4
     63 int PANIC = FSORTMAX;
     64 
     65 #define MSTART		(MAXFCT - 16)
     66 
     67 void
     68 fsort(binno, depth, top, filelist, nfiles, outfp, ftbl)
     69 	int binno, depth, top;
     70 	struct filelist *filelist;
     71 	int nfiles;
     72 	FILE *outfp;
     73 	struct field *ftbl;
     74 {
     75 	const u_char **keypos;
     76 	u_char *bufend, *tmpbuf;
     77 	u_char *weights;
     78 	int ntfiles, mfct = 0, total, i, maxb, lastb, panic = 0;
     79 	int c, nelem, base;
     80 	long sizes [NBINS+1];
     81 	get_func_t get;
     82 	struct recheader *crec;
     83 	struct field tfield[2];
     84 	FILE *prevfp, *tailfp[FSORTMAX+1];
     85 
     86 	memset(tailfp, 0, sizeof(tailfp));
     87 	prevfp = outfp;
     88 	memset(tfield, 0, sizeof(tfield));
     89 	if (ftbl[0].flags & R)
     90 		tfield[0].weights = Rascii;
     91 	else
     92 		tfield[0].weights = ascii;
     93 	tfield[0].icol.num = 1;
     94 	weights = ftbl[0].weights;
     95 	if (!buffer) {
     96 		bufsize = BUFSIZE;
     97 		buffer = malloc(bufsize);
     98 		keylist = malloc(MAXNUM * sizeof(u_char *));
     99 		if (!SINGL_FLD) {
    100 			linebuf_size = DEFLLEN;
    101 			linebuf = malloc(linebuf_size);
    102 		}
    103 	}
    104 	bufend = buffer + bufsize;
    105 	if (binno >= 0) {
    106 		base = top + nfiles;
    107 		get = getnext;
    108 	} else {
    109 		base = 0;
    110 		if (SINGL_FLD)
    111 			get = makeline;
    112 		else
    113 			get = makekey;
    114 	}
    115 	for (;;) {
    116 		memset(sizes, 0, sizeof(sizes));
    117 		c = ntfiles = 0;
    118 		if (binno == weights[REC_D] &&
    119 		    !(SINGL_FLD && ftbl[0].flags & F)) {	/* pop */
    120 			rd_append(weights[REC_D], top,
    121 			    nfiles, prevfp, buffer, bufend);
    122 			break;
    123 		} else if (binno == weights[REC_D]) {
    124 			depth = 0;		/* start over on flat weights */
    125 			ftbl = tfield;
    126 			weights = ftbl[0].weights;
    127 		}
    128 		while (c != EOF) {
    129 			keypos = keylist;
    130 			nelem = 0;
    131 			crec = (RECHEADER *) buffer;
    132 			while((c = get(binno, top, filelist, nfiles, crec,
    133 			    bufend, ftbl)) == 0) {
    134 				*keypos++ = crec->data + depth;
    135 				if (++nelem == MAXNUM) {
    136 					c = BUFFEND;
    137 					break;
    138 				}
    139 				crec =(RECHEADER *)	((char *) crec +
    140 				SALIGN(crec->length) + sizeof(TRECHEADER));
    141 			}
    142 			if (c == BUFFEND && nelem == 0) {
    143 				/* buffer was too small for data, allocate
    144 				 * bigger buffer */
    145 				bufsize *= 2;
    146 				buffer = realloc(buffer, bufsize);
    147 				if (!buffer) {
    148 					err(2, "failed to realloc buffer to %ld bytes",
    149 						(unsigned long) bufsize);
    150 				}
    151 				bufend = buffer + bufsize;
    152 				continue;
    153 			}
    154 			if (c == BUFFEND || ntfiles || mfct) {	/* push */
    155 				if (panic >= PANIC) {
    156 					fstack[MAXFCT-16+mfct].fp = ftmp();
    157 					if ((stable_sort)
    158 						? sradixsort(keylist, nelem,
    159 							weights, REC_D)
    160 						: radixsort(keylist, nelem,
    161 							weights, REC_D) )
    162 						err(2, NULL);
    163 					append(keylist, nelem, depth,
    164 					    fstack[MAXFCT-16+mfct].fp, putrec,
    165 					    ftbl);
    166 					mfct++;
    167 					/* reduce number of open files */
    168 					if (mfct == 16 ||(c == EOF && ntfiles)) {
    169 						tmpbuf = malloc(bufend -
    170 						    crec->data);
    171 						memmove(tmpbuf, crec->data,
    172 						    bufend - crec->data);
    173 						fstack[base + ntfiles].fp
    174 						    = ftmp();
    175 						fmerge(0, MSTART, filelist,
    176 						    mfct, geteasy,
    177 						    fstack[base].fp,
    178 						    putrec, ftbl);
    179 						++ntfiles;
    180 						mfct = 0;
    181 						memmove(crec->data, tmpbuf,
    182 						    bufend - crec->data);
    183 						free(tmpbuf);
    184 					}
    185 				} else {
    186 					fstack[base + ntfiles].fp= ftmp();
    187 					onepass(keylist, depth, nelem, sizes,
    188 					    weights, fstack[base + ntfiles].fp);
    189 					++ntfiles;
    190 				}
    191 			}
    192 		}
    193 		if (!ntfiles && !mfct) {	/* everything in memory--pop */
    194 			if (nelem > 1) {
    195 			   if ((stable_sort)
    196 				? sradixsort(keylist, nelem, weights, REC_D)
    197 				: radixsort(keylist, nelem, weights, REC_D) )
    198 				err(2, NULL);
    199 			}
    200 			append(keylist, nelem, depth, outfp, putline, ftbl);
    201 			break;					/* pop */
    202 		}
    203 		if (panic >= PANIC) {
    204 			if (!ntfiles)
    205 				fmerge(0, MSTART, filelist, mfct, geteasy,
    206 				    outfp, putline, ftbl);
    207 			else
    208 				fmerge(0, base, filelist, ntfiles, geteasy,
    209 				    outfp, putline, ftbl);
    210 			break;
    211 
    212 		}
    213 		total = maxb = lastb = 0;	/* find if one bin dominates */
    214 		for (i = 0; i < NBINS; i++)
    215 			if (sizes[i]) {
    216 				if (sizes[i] > sizes[maxb])
    217 					maxb = i;
    218 				lastb = i;
    219 				total += sizes[i];
    220 			}
    221 		if (sizes[maxb] < max((total / 2) , BUFSIZE))
    222 			maxb = lastb;	/* otherwise pop after last bin */
    223 		fstack[base].lastb = lastb;
    224 		fstack[base].maxb = maxb;
    225 
    226 		/* start refining next level. */
    227 		getnext(-1, base, NULL, ntfiles, crec, bufend, 0); /* rewind */
    228 		for (i = 0; i < maxb; i++) {
    229 			if (!sizes[i])	/* bin empty; step ahead file offset */
    230 				getnext(i, base, NULL,ntfiles, crec, bufend, 0);
    231 			else {
    232 				fsort(i, depth+1, base, filelist, ntfiles,
    233 					outfp, ftbl);
    234 			}
    235 		}
    236 
    237 		get = getnext;
    238 
    239 		if (lastb != maxb) {
    240 			if (prevfp != outfp)
    241 				tailfp[panic] = prevfp;
    242 			prevfp = ftmp();
    243 			for (i = maxb+1; i <= lastb; i++)
    244 				if (!sizes[i]) {
    245 					getnext(i, base, NULL, ntfiles, crec,
    246 					    bufend,0);
    247 				} else {
    248 					fsort(i, depth+1, base, filelist,
    249 					    ntfiles, prevfp, ftbl);
    250 				}
    251 		}
    252 
    253 		/* sort biggest (or last) bin at this level */
    254 		depth++;
    255 		panic++;
    256 		binno = maxb;
    257 		top = base;
    258 		nfiles = ntfiles;		/* so overwrite them */
    259 	}
    260 	if (prevfp != outfp) {
    261 		concat(outfp, prevfp);
    262 		fclose(prevfp);
    263 	}
    264 	for (i = panic; i >= 0; --i)
    265 		if (tailfp[i]) {
    266 			concat(outfp, tailfp[i]);
    267 			fclose(tailfp[i]);
    268 		}
    269 }
    270 
    271 /*
    272  This is one pass of radix exchange, dumping the bins to disk.
    273  */
    274 #define swap(a, b, t) t = a, a = b, b = t
    275 void
    276 onepass(a, depth, n, sizes, tr, fp)
    277 	const u_char **a;
    278 	int depth;
    279 	long n, sizes[];
    280 	u_char *tr;
    281 	FILE *fp;
    282 {
    283 	size_t tsizes[NBINS+1];
    284 	const u_char **bin[257], ***bp, ***bpmax, **top[256], ***tp;
    285 	static int histo[256];
    286 	int *hp;
    287 	int c;
    288 	const u_char **an, *t, **aj;
    289 	const u_char **ak, *r;
    290 
    291 	memset(tsizes, 0, sizeof(tsizes));
    292 	depth += sizeof(TRECHEADER);
    293 	an = &a[n];
    294 	for (ak = a; ak < an; ak++) {
    295 		histo[c = tr[**ak]]++;
    296 		tsizes[c] += ((const RECHEADER *) (*ak -= depth))->length;
    297 	}
    298 
    299 	bin[0] = a;
    300 	bpmax = bin + 256;
    301 	tp = top, hp = histo;
    302 	for (bp = bin; bp < bpmax; bp++) {
    303 		*tp++ = *(bp+1) = *bp + (c = *hp);
    304 		*hp++ = 0;
    305 		if (c <= 1)
    306 			continue;
    307 	}
    308 	for (aj = a; aj < an; *aj = r, aj = bin[c+1])
    309 		for (r = *aj; aj < (ak = --top[c = tr[r[depth]]]) ;)
    310 			swap(*ak, r, t);
    311 
    312 	for (ak = a, c = 0; c < 256; c++) {
    313 		an = bin[c+1];
    314 		n = an - ak;
    315 		tsizes[c] += n * sizeof(TRECHEADER);
    316 		/* tell getnext how many elements in this bin, this segment. */
    317 		EWRITE(&tsizes[c], sizeof(size_t), 1, fp);
    318 		sizes[c] += tsizes[c];
    319 		for (; ak < an; ++ak)
    320 			putrec((const RECHEADER *) *ak, fp);
    321 	}
    322 }
    323