diff options
Diffstat (limited to 'contrib/sort/msort.c')
-rw-r--r-- | contrib/sort/msort.c | 390 |
1 files changed, 0 insertions, 390 deletions
diff --git a/contrib/sort/msort.c b/contrib/sort/msort.c deleted file mode 100644 index 8a2500c..0000000 --- a/contrib/sort/msort.c +++ /dev/null @@ -1,390 +0,0 @@ -/* $NetBSD: msort.c,v 1.10 2001/02/19 20:50:17 jdolecek Exp $ */ - -/*- - * 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. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. 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.10 2001/02/19 20:50:17 jdolecek 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; - short flno; - struct recheader rec[1]; -} MFILE; - -static u_char *wts, *wts1 = NULL; - -static int cmp __P((RECHEADER *, RECHEADER *)); -static int insert __P((struct mfile **, struct mfile **, int, int)); - -void -fmerge(binno, top, filelist, nfiles, get, outfp, fput, ftbl) - int binno, top; - 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; - struct tempfile *l_fstack; - - wts = ftbl->weights; - if (!UNIQUE && SINGL_FLD && ftbl->flags & F) - wts1 = (ftbl->flags & R) ? Rascii : ascii; - - if (!buffer) { - buffer = malloc(bufsize); - if (!buffer) - err(2, "fmerge(): realloc"); - - if (!linebuf && !SINGL_FLD) { - linebuf_size = DEFLLEN; - linebuf = malloc(linebuf_size); - } - } - - if (binno >= 0) - l_fstack = fstack + top; - else - l_fstack = fstack; - - 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 (!(l_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(l_fstack[i+j].fp); - merge(top+j, last, get, tout, put, ftbl); - } - if (nfiles > MERGE_FNUM) - l_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; - top = 0; - } - } -} - -void -merge(infl0, nfiles, get, outfp, put, ftbl) - int infl0, nfiles; - get_func_t get; - put_func_t put; - FILE *outfp; - struct field *ftbl; -{ - int c, i, j, nf = nfiles; - struct mfile *flist[MERGE_FNUM], *cfile; - size_t availsz = bufsize; - static void *bufs[MERGE_FNUM+1]; - static size_t bufs_sz[MERGE_FNUM+1]; - - /* - * We need nfiles + 1 buffers. One is 'buffer', the - * rest needs to be allocated. - */ - bufs[0] = buffer; - bufs_sz[0] = bufsize; - for(i=1; i < nfiles+1; i++) { - if (bufs[i]) - continue; - - bufs[i] = malloc(DEFLLEN); - if (!bufs[i]) - err(2, "merge(): realloc"); - bufs_sz[i] = DEFLLEN; - } - - for (i = j = 0; i < nfiles; i++) { - cfile = (struct mfile *) bufs[j]; - cfile->flno = infl0 + j; - cfile->end = (u_char *) bufs[j] + bufs_sz[j]; - for (c = 1; c == 1;) { - if (EOF == (c = get(cfile->flno, 0, NULL, nfiles, - cfile->rec, cfile->end, ftbl))) { - --i; - --nfiles; - break; - } - - if (c == BUFFEND) { - cfile = realloc(bufs[j], bufs_sz[j] *= 2); - bufs[j] = (void *) cfile; - - if (!cfile) - err(2, "merge(): realloc"); - - cfile->end = (u_char *)cfile + bufs_sz[j]; - - c = 1; - continue; - } - - if (i) - c = insert(flist, &cfile, i, !DELETE); - else - flist[0] = cfile; - } - j++; - } - - cfile = (struct mfile *) bufs[nf]; - cfile->flno = flist[0]->flno; - cfile->end = (u_char *) cfile + bufs_sz[nf]; - while (nfiles) { - for (c = 1; c == 1;) { - if (EOF == (c = get(cfile->flno, 0, NULL, nfiles, - cfile->rec, cfile->end, ftbl))) { - put(flist[0]->rec, outfp); - memmove(flist, flist + 1, - sizeof(MFILE *) * (--nfiles)); - cfile->flno = flist[0]->flno; - break; - } - if (c == BUFFEND) { - char *oldbuf = (char *) cfile; - availsz = (char *) cfile->end - oldbuf; - availsz *= 2; - cfile = realloc(oldbuf, availsz); - for(i=0; i < nf+1; i++) { - if (bufs[i] == oldbuf) { - bufs[i] = (char *)cfile; - bufs_sz[i] = availsz; - break; - } - } - - if (!cfile) - err(2, "merge: realloc"); - - cfile->end = (u_char *)cfile + availsz; - c = 1; - continue; - } - - if (!(c = insert(flist, &cfile, nfiles, DELETE))) - put(cfile->rec, outfp); - } - } - - if (bufs_sz[0] > bufsize) { - buffer = bufs[0]; - bufsize = bufs_sz[0]; - } -} - -/* - * if delete: inserts *rec in flist, deletes flist[0], and leaves it in *rec; - * otherwise just inserts *rec in flist. - */ -static int -insert(flist, rec, ttop, delete) - struct mfile **flist, **rec; - int delete, ttop; /* delete = 0 or 1 */ -{ - 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) - top = mid; - else if (cmpv > 0) - bot = mid; - else { - if (UNIQUE) - break; - - if (stable_sort) { - /* - * Apply sort by fileno, to give priority - * to earlier specified files, hence providing - * more stable sort. - * If fileno is same, the new record should - * be put _after_ the previous entry. - */ - cmpv = tmprec->flno - flist[mid]->flno; - if (cmpv >= 0) - bot = mid; - else /* cmpv == 0 */ - bot = mid - 1; - } else { - /* non-stable sort */ - bot = mid - 1; - } - - break; - } - } - - if (delete) { - if (UNIQUE) { - if (!bot && cmpv) - cmpv = cmp(tmprec->rec, flist[0]->rec); - if (!cmpv) - return (1); - } - tmprec = flist[0]; - if (bot) - memmove(flist, flist+1, bot * sizeof(MFILE **)); - flist[bot] = *rec; - *rec = tmprec; - (*rec)->flno = flist[0]->flno; - return (0); - } else { - if (!bot && !(UNIQUE && !cmpv)) { - cmpv = cmp(tmprec->rec, flist[0]->rec); - if (cmpv < 0) - bot = -1; - } - if (UNIQUE && !cmpv) - return (1); - bot++; - memmove(flist + bot+1, flist + bot, - (ttop - bot) * sizeof(MFILE **)); - flist[bot] = *rec; - return (0); - } -} - -/* - * check order on one file - */ -void -order(filelist, get, ftbl) - struct filelist *filelist; - get_func_t get; - struct field *ftbl; -{ - u_char *crec_end, *prec_end, *trec_end; - int c; - RECHEADER *crec, *prec, *trec; - - if (!SINGL_FLD) - linebuf = malloc(DEFLLEN); - buffer = malloc(2 * (DEFLLEN + sizeof(TRECHEADER))); - crec = (RECHEADER *) buffer; - crec_end = buffer + DEFLLEN + sizeof(TRECHEADER); - prec = (RECHEADER *) (buffer + DEFLLEN + sizeof(TRECHEADER)); - prec_end = buffer + 2*(DEFLLEN + sizeof(TRECHEADER)); - wts = ftbl->weights; - if (SINGL_FLD && (ftbl->flags & F)) - wts1 = (ftbl->flags & R) ? Rascii : ascii; - else - wts1 = NULL; - if (0 == get(-1, 0, filelist, 1, prec, prec_end, ftbl)) - while (0 == get(-1, 0, filelist, 1, crec, crec_end, ftbl)) { - 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(rec1, rec2) - RECHEADER *rec1, *rec2; -{ - int r; - u_char *pos1, *pos2, *end; - u_char *cwts; - for (cwts = wts; cwts; cwts = (cwts == wts1 ? NULL : wts1)) { - pos1 = rec1->data; - pos2 = rec2->data; - if (!SINGL_FLD && (UNIQUE || stable_sort)) - end = pos1 + min(rec1->offset, rec2->offset); - else - end = pos1 + min(rec1->length, rec2->length); - - for (; pos1 < end; ) { - if ((r = cwts[*pos1++] - cwts[*pos2++])) - return (r); - } - } - return (0); -} |