1 /* $NetBSD: msort.c,v 1.29 2009/11/06 18:34:22 joerg Exp $ */
4 * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Ben Harris and Jaromir Dolecek.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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.
34 * The Regents of the University of California. All rights reserved.
36 * This code is derived from software contributed to Berkeley by
39 * Redistribution and use in source and binary forms, with or without
40 * modification, are permitted provided that the following conditions
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.
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
67 __RCSID("$NetBSD: msort.c,v 1.29 2009/11/06 18:34:22 joerg Exp $");
73 /* Subroutines using comparisons: merge sort and check order */
76 typedef struct mfile {
83 static int cmp(RECHEADER *, RECHEADER *);
84 static int insert(struct mfile **, struct mfile *, int, int);
85 static void merge_sort_fstack(FILE *, put_func_t, struct field *);
88 * Number of files merge() can merge in one pass.
92 static struct mfile fstack[MERGE_FNUM];
93 static struct mfile fstack_1[MERGE_FNUM];
94 static struct mfile fstack_2[MERGE_FNUM];
95 static int fstack_count, fstack_1_count, fstack_2_count;
98 save_for_merge(FILE *fp, get_func_t get, struct field *ftbl)
100 FILE *mfp, *mfp1, *mfp2;
102 if (fstack_count == MERGE_FNUM) {
103 /* Must reduce the number of temporary files */
105 merge_sort_fstack(mfp, putrec, ftbl);
106 /* Save output in next layer */
107 if (fstack_1_count == MERGE_FNUM) {
109 memcpy(fstack, fstack_1, sizeof fstack);
110 merge_sort_fstack(mfp1, putrec, ftbl);
111 if (fstack_2_count == MERGE_FNUM) {
112 /* More than 4096 files! */
114 memcpy(fstack, fstack_2, sizeof fstack);
115 merge_sort_fstack(mfp2, putrec, ftbl);
116 fstack_2[0].fp = mfp2;
119 fstack_2[fstack_2_count].fp = mfp1;
120 fstack_2[fstack_2_count].get = geteasy;
124 fstack_1[fstack_1_count].fp = mfp;
125 fstack_1[fstack_1_count].get = geteasy;
130 fstack[fstack_count].fp = fp;
131 fstack[fstack_count++].get = get;
135 fmerge(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl)
137 get_func_t get = SINGL_FLD ? makeline : makekey;
141 for (i = 0; i < nfiles; i++) {
142 fp = fopen(filelist->names[i], "r");
144 err(2, "%s", filelist->names[i]);
145 save_for_merge(fp, get, ftbl);
148 merge_sort(outfp, putline, ftbl);
152 merge_sort(FILE *outfp, put_func_t put, struct field *ftbl)
154 int count = fstack_1_count + fstack_2_count;
159 /* All files in initial array */
160 merge_sort_fstack(outfp, put, ftbl);
164 count += fstack_count;
166 /* Too many files for one merge sort */
168 /* Sort latest 16 files */
172 while (fstack_count > 0)
173 fstack[--i] = fstack[--fstack_count];
174 while (i > 0 && fstack_1_count > 0)
175 fstack[--i] = fstack_1[--fstack_1_count];
177 fstack[--i] = fstack_2[--fstack_2_count];
178 if (count <= MERGE_FNUM) {
179 /* Got all the data */
180 fstack_count = count;
181 merge_sort_fstack(outfp, put, ftbl);
185 fstack_count = count > MERGE_FNUM ? MERGE_FNUM : count;
186 merge_sort_fstack(mfp, putrec, ftbl);
188 fstack[0].get = geteasy;
190 count -= MERGE_FNUM - 1;
195 merge_sort_fstack(FILE *outfp, put_func_t put, struct field *ftbl)
197 struct mfile *flistb[MERGE_FNUM], **flist = flistb, *cfile;
204 /* Read one record from each file (read again if a duplicate) */
205 for (nfiles = i = 0; i < fstack_count; i++) {
207 if (cfile->rec == NULL) {
208 cfile->rec = allocrec(NULL, DEFLLEN);
209 cfile->end = (u_char *)cfile->rec + DEFLLEN;
214 c = cfile->get(cfile->fp, cfile->rec, cfile->end, ftbl);
219 /* Double buffer size */
220 sz = (cfile->end - (u_char *)cfile->rec) * 2;
221 cfile->rec = allocrec(cfile->rec, sz);
222 cfile->end = (u_char *)cfile->rec + sz;
227 if (insert(flist, cfile, nfiles, !DELETE))
228 /* Duplicate removed */
241 * We now loop reading a new record from the file with the
242 * 'sorted first' existing record.
243 * As each record is added, the 'first' record is written to the
244 * output file - maintaining one record from each file in the sorted
247 new_rec = allocrec(NULL, DEFLLEN);
248 new_end = (u_char *)new_rec + DEFLLEN;
251 c = cfile->get(cfile->fp, new_rec, new_end, ftbl);
253 /* Write out last record from now-empty input */
254 put(cfile->rec, outfp);
257 /* Replace from file with now-first sorted record. */
258 /* (Moving base 'flist' saves copying everything!) */
263 /* Buffer not large enough - double in size */
264 sz = (new_end - (u_char *)new_rec) * 2;
265 new_rec = allocrec(new_rec, sz);
266 new_end = (u_char *)new_rec +sz;
270 /* Swap in new buffer, saving old */
272 cfile->rec = new_rec;
275 cfile->end = new_end;
278 /* Add into sort, removing the original first entry */
279 c = insert(flist, cfile, nfiles, DELETE);
280 if (c != 0 || (UNIQUE && cfile == flist[0]
281 && cmp(new_rec, cfile->rec) == 0)) {
282 /* Was an unwanted duplicate, restore buffer */
284 cfile->rec = new_rec;
287 cfile->end = new_end;
292 /* Write out 'old' record */
300 * if delete: inserts rec in flist, deletes flist[0];
301 * otherwise just inserts *rec in flist.
302 * Returns 1 if record is a duplicate to be ignored.
305 insert(struct mfile **flist, struct mfile *rec, int ttop, int delete)
307 int mid, top = ttop, bot = 0, cmpv = 1;
309 for (mid = top / 2; bot + 1 != top; mid = (bot + top) / 2) {
310 cmpv = cmp(rec->rec, flist[mid]->rec);
313 /* Duplicate key, read another record */
314 /* NB: This doesn't guarantee to keep any
315 * particular record. */
318 * Apply sort by input file order.
319 * We could truncate the sort is the fileno are
320 * adjacent - but that is all too hard!
321 * The fileno cannot be equal, since we only have one
322 * record from each file (+ flist[0] which never
325 cmpv = rec < flist[mid] ? -1 : 1;
335 /* At this point we haven't yet compared against flist[0] */
338 /* flist[0] is ourselves, only the caller knows the old data */
340 memmove(flist, flist + 1, bot * sizeof(MFILE *));
346 /* Inserting original set of records */
348 if (bot == 0 && cmpv != 0) {
349 /* Doesn't match flist[1], must compare with flist[0] */
350 cmpv = cmp(rec->rec, flist[0]->rec);
351 if (cmpv == 0 && UNIQUE)
353 /* Add matching keys in file order (ie new is later) */
358 memmove(flist + bot + 1, flist + bot, (ttop - bot) * sizeof(MFILE *));
364 * check order on one file
367 order(struct filelist *filelist, struct field *ftbl)
369 get_func_t get = SINGL_FLD ? makeline : makekey;
370 RECHEADER *crec, *prec, *trec;
371 u_char *crec_end, *prec_end, *trec_end;
375 fp = fopen(filelist->names[0], "r");
377 err(2, "%s", filelist->names[0]);
379 crec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
380 crec_end = crec->data + DEFLLEN;
381 prec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
382 prec_end = prec->data + DEFLLEN;
384 /* XXX this does exit(0) for overlong lines */
385 if (get(fp, prec, prec_end, ftbl) != 0)
387 while (get(fp, crec, crec_end, ftbl) == 0) {
388 if (0 < (c = cmp(prec, crec))) {
389 crec->data[crec->length-1] = 0;
390 errx(1, "found disorder: %s", crec->data+crec->offset);
393 crec->data[crec->length-1] = 0;
394 errx(1, "found non-uniqueness: %s",
395 crec->data+crec->offset);
398 * Swap pointers so that this record is on place pointed
399 * to by prec and new record is read to place pointed to by
413 cmp(RECHEADER *rec1, RECHEADER *rec2)
419 len = min(rec1->keylen, rec2->keylen);
420 r = memcmp(rec1->data, rec2->data, len);
422 r = rec1->keylen - rec2->keylen;