diff options
Diffstat (limited to 'usr.bin/sort/fsort.c')
| -rw-r--r-- | usr.bin/sort/fsort.c | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/usr.bin/sort/fsort.c b/usr.bin/sort/fsort.c new file mode 100644 index 0000000..c229ae2 --- /dev/null +++ b/usr.bin/sort/fsort.c @@ -0,0 +1,202 @@ +/* $NetBSD: fsort.c,v 1.47 2010/02/05 21:58:41 enami 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. + */ + +/* + * Read in a block of records (until 'enough'). + * sort, write to temp file. + * Merge sort temp files into output file + * Small files miss out the temp file stage. + * Large files might get multiple merges. + */ +#include "sort.h" +#include "fsort.h" + +__RCSID("$NetBSD: fsort.c,v 1.47 2010/02/05 21:58:41 enami Exp $"); + +#include <stdlib.h> +#include <string.h> + +#define SALIGN(n) ((n+sizeof(length_t)-1) & ~(sizeof(length_t)-1)) + +void +fsort(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl) +{ + RECHEADER **keylist; + RECHEADER **keypos, **keyp; + RECHEADER *buffer; + size_t bufsize = DEFBUFSIZE; + u_char *bufend; + int mfct = 0; + int c, nelem; + get_func_t get; + RECHEADER *crec; + RECHEADER *nbuffer; + FILE *fp, *tmp_fp; + int file_no; + int max_recs = DEBUG('m') ? 16 : MAXNUM; + + buffer = allocrec(NULL, bufsize); + bufend = (u_char *)buffer + bufsize; + /* Allocate double length keymap for radix_sort */ + keylist = malloc(2 * max_recs * sizeof(*keylist)); + if (buffer == NULL || keylist == NULL) + err(2, "failed to malloc initial buffer or keylist"); + + if (SINGL_FLD) + /* Key and data are one! */ + get = makeline; + else + /* Key (merged key fields) added before data */ + get = makekey; + + file_no = 0; + fp = fopen(filelist->names[0], "r"); + if (fp == NULL) + err(2, "%s", filelist->names[0]); + + /* Loop through reads of chunk of input files that get sorted + * and then merged together. */ + for (;;) { + keypos = keylist; + nelem = 0; + crec = buffer; + makeline_copydown(crec); + + /* Loop reading records */ + for (;;) { + c = get(fp, crec, bufend, ftbl); + /* 'c' is 0, EOF or BUFFEND */ + if (c == 0) { + /* Save start of key in input buffer */ + *keypos++ = crec; + if (++nelem == max_recs) { + c = BUFFEND; + break; + } + crec = (RECHEADER *)(crec->data + SALIGN(crec->length)); + continue; + } + if (c == EOF) { + /* try next file */ + if (++file_no >= nfiles) + /* no more files */ + break; + fp = fopen(filelist->names[file_no], "r"); + if (fp == NULL) + err(2, "%s", filelist->names[file_no]); + continue; + } + if (nelem >= max_recs + || (bufsize >= MAXBUFSIZE && nelem > 8)) + /* Need to sort and save this lot of data */ + break; + + /* c == BUFFEND, and we can process more data */ + /* Allocate a larger buffer for this lot of data */ + bufsize *= 2; + nbuffer = allocrec(buffer, bufsize); + if (!nbuffer) { + err(2, "failed to realloc buffer to %zu bytes", + bufsize); + } + + /* patch up keylist[] */ + for (keyp = &keypos[-1]; keyp >= keylist; keyp--) + *keyp = nbuffer + (*keyp - buffer); + + crec = nbuffer + (crec - buffer); + buffer = nbuffer; + bufend = (u_char *)buffer + bufsize; + } + + /* Sort this set of records */ + radix_sort(keylist, keylist + max_recs, nelem); + + if (c == EOF && mfct == 0) { + /* all the data is (sorted) in the buffer */ + append(keylist, nelem, outfp, + DEBUG('k') ? putkeydump : putline); + break; + } + + /* Save current data to a temporary file for a later merge */ + if (nelem != 0) { + tmp_fp = ftmp(); + append(keylist, nelem, tmp_fp, putrec); + save_for_merge(tmp_fp, geteasy, ftbl); + } + mfct = 1; + + if (c == EOF) { + /* merge to output file */ + merge_sort(outfp, + DEBUG('k') ? putkeydump : putline, ftbl); + break; + } + } + + free(keylist); + keylist = NULL; + free(buffer); + buffer = NULL; +} |