xref: /src/usr.bin/sort/msort.c

/*	$NetBSD: msort.c,v 1.26 2009/09/10 22:02:40 dsl Exp $	*/

/*-
 * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Ben Harris and Jaromir Dolecek.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

/*-
 * Copyright (c) 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Peter McIlroy.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include "sort.h"
#include "fsort.h"

#ifndef lint
__RCSID("$NetBSD: msort.c,v 1.26 2009/09/10 22:02:40 dsl Exp $");
__SCCSID("@(#)msort.c	8.1 (Berkeley) 6/6/93");
#endif /* not lint */

#include <stdlib.h>
#include <string.h>
#include <unistd.h>

/* Subroutines using comparisons: merge sort and check order */
#define DELETE (1)

typedef struct mfile {
	u_char *end;
	int flno;
	RECHEADER rec[1];
} MFILE;

static int cmp(RECHEADER *, RECHEADER *);
static int insert(struct mfile **, struct mfile **, int, int);
static void merge(int, int, get_func_t, FILE *, put_func_t, struct field *);

void
fmerge(int binno, struct filelist *filelist, int nfiles,
    get_func_t get, FILE *outfp, put_func_t fput, struct field *ftbl)
{
	FILE *tout;
	int i, j, last;
	put_func_t put;

	while (nfiles) {
		put = putrec;
		for (j = 0; j < nfiles; j += MERGE_FNUM) {
			if (nfiles <= MERGE_FNUM) {
				tout = outfp;
				put = fput;
			}
			else
				tout = ftmp();
			last = min(MERGE_FNUM, nfiles - j);
			if (binno < 0) {
				for (i = 0; i < last; i++)
					if (!(fstack[i+MAXFCT-1-MERGE_FNUM].fp =
					    fopen(filelist->names[j+i], "r")))
						err(2, "%s",
							filelist->names[j+i]);
				merge(MAXFCT-1-MERGE_FNUM, last, get, tout, put, ftbl);
			} else {
				for (i = 0; i< last; i++)
					rewind(fstack[i+j].fp);
				merge(j, last, get, tout, put, ftbl);
			}
			if (nfiles > MERGE_FNUM)
				fstack[j/MERGE_FNUM].fp = tout;
		}
		nfiles = (nfiles + (MERGE_FNUM - 1)) / MERGE_FNUM;
		if (nfiles == 1)
			nfiles = 0;
		if (binno < 0) {
			binno = 0;
			get = geteasy;
		}
	}
}

static void
merge(int infl0, int nfiles, get_func_t get, FILE *outfp, put_func_t put,
    struct field *ftbl)
{
	int c, i, j, nf = nfiles;
	struct mfile *flistb[MERGE_FNUM], **flist = flistb, *cfile;
	size_t availsz;
	static void *bufs[MERGE_FNUM + 1];
	static size_t bufs_sz[MERGE_FNUM + 1];

	/*
	 * We need nfiles + 1 buffers.
	 */
	for (i = 0; i < nfiles + 1; i++) {
		if (bufs[i])
			continue;

		bufs[i] = malloc(DEFLLEN);
		if (!bufs[i])
			err(2, "merge: malloc");
		memset(bufs[i], 0, DEFLLEN);
		bufs_sz[i] = DEFLLEN;
	}

	/* Read one record from each file (read again if a duplicate) */
	for (i = j = 0; i < nfiles; i++, j++) {
		cfile = (struct mfile *) bufs[j];
		cfile->flno = infl0 + j;
		cfile->end = (u_char *) bufs[j] + bufs_sz[j];
		for (c = 1; c == 1;) {
			c = get(cfile->flno, 0, NULL, nfiles, cfile->rec,
			    cfile->end, ftbl);
			if (c == EOF) {
				--i;
				--nfiles;
				break;
			}

			if (c == BUFFEND) {
				bufs_sz[j] *= 2;
				cfile = realloc(bufs[j], bufs_sz[j]);
				if (!cfile)
					err(2, "merge: realloc");

				bufs[j] = (void *) cfile;
				cfile->end = (u_char *)cfile + bufs_sz[j];

				c = 1;
				continue;
			}

			if (i)
				c = insert(flist, &cfile, i, !DELETE);
			else
				flist[0] = cfile;
		}
	}

	/*
	 * We now loop reading a new record from the file with the
	 * 'sorted first' existing record.
	 * As each record is added, the 'first' record is written to the
	 * output file - maintaining one record from each file in the sorted
	 * list.
	 */
	cfile = (struct mfile *) bufs[nf];
	cfile->end = (u_char *) cfile + bufs_sz[nf];
	cfile->flno = flist[0]->flno;
	for (;;) {
		c = get(cfile->flno, 0, NULL, nfiles, cfile->rec,
		    cfile->end, ftbl);
		if (c == EOF) {
			/* Write out last record from now-empty input */
			put(flist[0]->rec, outfp);
			if (--nfiles == 0)
				break;
			/* Replace from file with now-first sorted record. */
			/* (Moving base 'flist' saves copying everything!) */
			flist++;
			cfile->flno = flist[0]->flno;
			continue;
		}
		if (c == BUFFEND) {
			/* Buffer not large enough - double in size */
			char *oldbuf = (char *) cfile;
			availsz = (char *) cfile->end - oldbuf;
			availsz *= 2;
			cfile = realloc(oldbuf, availsz);
			if (!cfile)
				err(2, "merge: realloc");
			cfile->end = (u_char *)cfile + availsz;

			/* Update pointers we'll use for next merge */
			for (i = 0; i < nf + 1; i++) {
				if (bufs[i] == oldbuf) {
					bufs[i] = (char *)cfile;
					bufs_sz[i] = availsz;
					break;
				}
			}
			/* Read again from same file into same buffer */
			continue;
		}

		/* Add into sort, removing the original first entry */
		c = insert(flist, &cfile, nfiles, DELETE);

		/*
		 * 'cfile' is now the buffer from the old record from the
		 * file we just read, but with the file number of the
		 * current 'first record.
		 * (Unless we are rejecting a duplicate, when c == 1 and
		 * it is unchanged!)
		 */
		if (c == 0)
			put(cfile->rec, outfp);
	}
}

/*
 * if delete: inserts *rec in flist, deletes flist[0], and leaves it in *rec;
 * otherwise just inserts *rec in flist.
 */
static int
insert(struct mfile **flist, struct mfile **rec, int ttop, int delete)
{
	struct mfile *tmprec = *rec;
	int mid, top = ttop, bot = 0, cmpv = 1;

	for (mid = top / 2; bot + 1 != top; mid = (bot + top) / 2) {
		cmpv = cmp(tmprec->rec, flist[mid]->rec);
		if (cmpv == 0 ) {
			if (UNIQUE)
				/* Duplicate key, read another record */
				return 1;
			/*
			 * Apply sort by fileno, to give priority to earlier
			 * specified files, hence providing a stable sort.
			 * We could truncate the sort is the fileno are
			 * adjacent - but that is all too hard!
			 * The fileno cannot be equal, since we only have one
			 * record from each file (+ flist[0] which never
			 * comes here).
			 */
			cmpv = tmprec->flno - flist[mid]->flno;
			if (REVERSE)
				cmpv = -cmpv;
		}
		if (cmpv < 0)
			top = mid;
		else
			bot = mid;
	}

	/* At this point we haven't yet compared against flist[0] */

	if (delete) {
		/* flist[0] came from the same file, it cannot be earlier. */
		if (UNIQUE && bot == 0 && cmp(tmprec->rec, flist[0]->rec) == 0)
			/* Duplicate record (key) in original file */
			return 1;
		tmprec = flist[0];
		if (bot)
			memmove(flist, flist + 1, bot * sizeof(MFILE **));
		flist[bot] = *rec;
		tmprec->flno = flist[0]->flno;
		*rec = tmprec;
		return 0;
	}

	/* Inserting original set of records */

	if (bot == 0 && cmpv != 0) {
		/* Doesn't match flist[1], must compare with flist[0] */
		cmpv = cmp(tmprec->rec, flist[0]->rec);
		if (cmpv == 0 && UNIQUE)
			return 1;
		/* Add matching keys in file order (ie new is later) */
		if (cmpv < 0)
			bot = -1;
	}
	bot++;
	memmove(flist + bot + 1, flist + bot, (ttop - bot) * sizeof(MFILE **));
	flist[bot] = *rec;
	return 0;
}

/*
 * check order on one file
 */
void
order(struct filelist *filelist, get_func_t get, struct field *ftbl)
{
	RECHEADER *crec, *prec, *trec;
	u_char *crec_end, *prec_end, *trec_end;
	int c;

	crec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
	crec_end = crec->data + DEFLLEN;
	prec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
	prec_end = prec->data + DEFLLEN;

	/* XXX this does exit(0) for overlong lines */
	if (get(-1, 0, filelist, 1, prec, prec_end, ftbl) != 0)
		exit(0);
	while (get(-1, 0, filelist, 1, crec, crec_end, ftbl) == 0) {
		if (0 < (c = cmp(prec, crec))) {
			crec->data[crec->length-1] = 0;
			errx(1, "found disorder: %s", crec->data+crec->offset);
		}
		if (UNIQUE && !c) {
			crec->data[crec->length-1] = 0;
			errx(1, "found non-uniqueness: %s",
			    crec->data+crec->offset);
		}
		/*
		 * Swap pointers so that this record is on place pointed
		 * to by prec and new record is read to place pointed to by
		 * crec.
		 */
		trec = prec;
		prec = crec;
		crec = trec;
		trec_end = prec_end;
		prec_end = crec_end;
		crec_end = trec_end;
	}
	exit(0);
}

static int
cmp(RECHEADER *rec1, RECHEADER *rec2)
{
	int len;
	int r;

	/* key is weights */
	len = min(rec1->keylen, rec2->keylen);
	r = memcmp(rec1->data, rec2->data, len);
	if (r == 0)
		r = rec1->keylen - rec2->keylen;
	if (REVERSE)
		r = -r;
	return r;
}