fsort.c revision 1.41
1 /* $NetBSD: fsort.c,v 1.41 2009/09/10 22:02:40 dsl Exp $ */ 2 3 /*- 4 * Copyright (c) 2000-2003 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Ben Harris and Jaromir Dolecek. 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 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /*- 33 * Copyright (c) 1993 34 * The Regents of the University of California. All rights reserved. 35 * 36 * This code is derived from software contributed to Berkeley by 37 * Peter McIlroy. 38 * 39 * Redistribution and use in source and binary forms, with or without 40 * modification, are permitted provided that the following conditions 41 * are met: 42 * 1. Redistributions of source code must retain the above copyright 43 * notice, this list of conditions and the following disclaimer. 44 * 2. Redistributions in binary form must reproduce the above copyright 45 * notice, this list of conditions and the following disclaimer in the 46 * documentation and/or other materials provided with the distribution. 47 * 3. Neither the name of the University nor the names of its contributors 48 * may be used to endorse or promote products derived from this software 49 * without specific prior written permission. 50 * 51 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 52 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 53 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 54 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 55 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 56 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 57 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 59 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 60 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 61 * SUCH DAMAGE. 62 */ 63 64 /* 65 * Read in a block of records (until 'enough'). 66 * sort, write to temp file. 67 * Merge sort temp files into output file 68 * Small files miss out the temp file stage. 69 * Large files might get multiple merges. 70 */ 71 #include "sort.h" 72 #include "fsort.h" 73 74 #ifndef lint 75 __RCSID("$NetBSD: fsort.c,v 1.41 2009/09/10 22:02:40 dsl Exp $"); 76 __SCCSID("@(#)fsort.c 8.1 (Berkeley) 6/6/93"); 77 #endif /* not lint */ 78 79 #include <stdlib.h> 80 #include <string.h> 81 82 struct tempfile fstack[MAXFCT]; 83 84 #define SALIGN(n) ((n+sizeof(length_t)-1) & ~(sizeof(length_t)-1)) 85 86 void 87 fsort(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl) 88 { 89 RECHEADER **keylist; 90 RECHEADER **keypos, **keyp; 91 RECHEADER *buffer; 92 size_t bufsize = DEFBUFSIZE; 93 u_char *bufend; 94 int mfct = 0; 95 int c, nelem; 96 get_func_t get; 97 RECHEADER *crec; 98 RECHEADER *nbuffer; 99 FILE *fp; 100 101 buffer = malloc(bufsize); 102 bufend = (u_char *)buffer + bufsize; 103 /* Allocate double length keymap for radix_sort */ 104 keylist = malloc(2 * MAXNUM * sizeof(*keylist)); 105 if (buffer == NULL || keylist == NULL) 106 err(2, "failed to malloc initial buffer or keylist"); 107 108 if (SINGL_FLD) 109 /* Key and data are one! */ 110 get = makeline; 111 else 112 /* Key (merged key fields) added before data */ 113 get = makekey; 114 115 /* Loop through reads of chunk of input files that get sorted 116 * and then merged together. */ 117 for (;;) { 118 keypos = keylist; 119 nelem = 0; 120 crec = buffer; 121 122 /* Loop reading records */ 123 for (;;) { 124 c = get(-1, 0, filelist, nfiles, crec, bufend, ftbl); 125 /* 'c' is 0, EOF or BUFFEND */ 126 if (c == 0) { 127 /* Save start of key in input buffer */ 128 *keypos++ = crec; 129 if (++nelem == MAXNUM) { 130 c = BUFFEND; 131 break; 132 } 133 crec = (RECHEADER *)(crec->data + SALIGN(crec->length)); 134 continue; 135 } 136 if (c == EOF) 137 break; 138 if (nelem >= MAXNUM || bufsize >= MAXBUFSIZE) 139 /* Need to sort and save this lot of data */ 140 break; 141 142 /* c == BUFFEND, and we can process more data */ 143 /* Allocate a larger buffer for this lot of data */ 144 bufsize *= 2; 145 nbuffer = realloc(buffer, bufsize); 146 if (!nbuffer) { 147 err(2, "failed to realloc buffer to %zu bytes", 148 bufsize); 149 } 150 151 /* patch up keylist[] */ 152 for (keyp = &keypos[-1]; keyp >= keylist; keyp--) 153 *keyp = nbuffer + (*keyp - buffer); 154 155 crec = nbuffer + (crec - buffer); 156 buffer = nbuffer; 157 bufend = (u_char *)buffer + bufsize; 158 } 159 160 /* Sort this set of records */ 161 radix_sort(keylist, keylist + MAXNUM, nelem); 162 163 if (c == EOF && mfct == 0) { 164 /* all the data is (sorted) in the buffer */ 165 append(keylist, nelem, outfp, 166 DEBUG('k') ? putkeydump : putline); 167 break; 168 } 169 170 /* Save current data to a temporary file for a later merge */ 171 fp = ftmp(); 172 fstack[mfct].fp = fp; 173 append(keylist, nelem, fp, putrec); 174 mfct++; 175 176 if (c == EOF) { 177 /* merge to output file */ 178 fmerge(0, filelist, mfct, geteasy, outfp, 179 DEBUG('k') ? putkeydump : putline, ftbl); 180 break; 181 } 182 183 if (mfct == MERGE_FNUM) { 184 /* Merge the files we have */ 185 fp = ftmp(); 186 fmerge(0, filelist, mfct, geteasy, fp, putrec, ftbl); 187 mfct = 1; 188 fstack[0].fp = fp; 189 } 190 } 191 192 free(keylist); 193 keylist = NULL; 194 free(buffer); 195 buffer = NULL; 196 } 197
Indexes created Fri Sep 26 08:10:20 GMT 2025