fsort.c revision 1.39
1 /* $NetBSD: fsort.c,v 1.39 2009/08/22 10:53:28 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.39 2009/08/22 10:53:28 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 static const u_char **keylist = 0; 83 u_char *buffer = 0; 84 size_t bufsize = DEFBUFSIZE; 85 86 struct tempfile fstack[MAXFCT]; 87 88 #define SALIGN(n) ((n+sizeof(length_t)-1) & ~(sizeof(length_t)-1)) 89 90 void 91 fsort(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl) 92 { 93 const u_char **keypos, **keyp; 94 u_char *bufend; 95 int mfct = 0; 96 int c, nelem; 97 get_func_t get; 98 struct recheader *crec; 99 u_char *nbuffer; 100 FILE *fp; 101 102 if (!buffer) { 103 buffer = malloc(bufsize); 104 keylist = malloc(MAXNUM * sizeof(u_char *)); 105 memset(keylist, 0, MAXNUM * sizeof(u_char *)); 106 } 107 bufend = buffer + bufsize; 108 109 if (SINGL_FLD) 110 /* Key and data are one! */ 111 get = makeline; 112 else 113 /* Key (merged key fields) added before data */ 114 get = makekey; 115 116 /* Loop through reads of chunk of input files that get sorted 117 * and then merged together. */ 118 for (;;) { 119 keypos = keylist; 120 nelem = 0; 121 crec = (RECHEADER *) buffer; 122 123 /* Loop reading records */ 124 for (;;) { 125 c = get(-1, 0, filelist, nfiles, crec, bufend, ftbl); 126 /* 'c' is 0, EOF or BUFFEND */ 127 if (c == 0) { 128 /* Save start of key in input buffer */ 129 *keypos++ = crec->data; 130 if (++nelem == MAXNUM) { 131 c = BUFFEND; 132 break; 133 } 134 crec = (RECHEADER *)((char *) crec + 135 SALIGN(crec->length) + REC_DATA_OFFSET); 136 continue; 137 } 138 if (c == EOF) 139 break; 140 if (nelem >= MAXNUM || bufsize >= MAXBUFSIZE) 141 /* Need to sort and save this lot of data */ 142 break; 143 144 /* c == BUFFEND, and we can process more data */ 145 /* Allocate a larger buffer for this lot of data */ 146 bufsize *= 2; 147 nbuffer = realloc(buffer, bufsize); 148 if (!nbuffer) { 149 err(2, "failed to realloc buffer to %zu bytes", 150 bufsize); 151 } 152 153 /* patch up keylist[] */ 154 for (keyp = &keypos[-1]; keyp >= keylist; keyp--) 155 *keyp = nbuffer + (*keyp - buffer); 156 157 crec = (RECHEADER *) (nbuffer + ((u_char *)crec - buffer)); 158 buffer = nbuffer; 159 bufend = buffer + bufsize; 160 } 161 162 /* Sort this set of records */ 163 if (SINGL_FLD) { 164 if (radix_sort(keylist, nelem, ftbl[0].weights, REC_D)) 165 err(2, "single field radix_sort"); 166 } else { 167 if (radix_sort(keylist, nelem, unweighted, 0)) 168 err(2, "unweighted radix_sort"); 169 } 170 171 if (c == EOF && mfct == 0) { 172 /* all the data is (sorted) in the buffer */ 173 append(keylist, nelem, outfp, 174 DEBUG('k') ? putkeydump : putline, ftbl->weights); 175 break; 176 } 177 178 /* Save current data to a temporary file for a later merge */ 179 fp = ftmp(); 180 fstack[mfct].fp = fp; 181 append(keylist, nelem, fp, putrec, NULL); 182 mfct++; 183 184 if (c == EOF) { 185 /* merge to output file */ 186 fmerge(0, filelist, mfct, geteasy, outfp, 187 DEBUG('k') ? putkeydump : putline, ftbl); 188 break; 189 } 190 191 if (mfct == MERGE_FNUM) { 192 /* Merge the files we have */ 193 fp = ftmp(); 194 fmerge(0, filelist, mfct, geteasy, fp, putrec, ftbl); 195 mfct = 1; 196 fstack[0].fp = fp; 197 } 198 } 199 200 free(keylist); 201 keylist = NULL; 202 free(buffer); 203 buffer = NULL; 204 } 205
Indexes created Tue Sep 30 11:09:46 GMT 2025