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
71 /* Subroutines using comparisons: merge sort and check order */
74 typedef struct mfile {
81 static int cmp(RECHEADER *, RECHEADER *);
82 static int insert(struct mfile **, struct mfile *, int, int);
83 static void merge_sort_fstack(FILE *, put_func_t, struct field *);
86 * Number of files merge() can merge in one pass.
90 static struct mfile fstack[MERGE_FNUM];
91 static struct mfile fstack_1[MERGE_FNUM];
92 static struct mfile fstack_2[MERGE_FNUM];
93 static int fstack_count, fstack_1_count, fstack_2_count;
96 save_for_merge(FILE *fp, get_func_t get, struct field *ftbl)
98 FILE *mfp, *mfp1, *mfp2;
100 if (fstack_count == MERGE_FNUM) {
101 /* Must reduce the number of temporary files */
103 merge_sort_fstack(mfp, putrec, ftbl);
104 /* Save output in next layer */
105 if (fstack_1_count == MERGE_FNUM) {
107 memcpy(fstack, fstack_1, sizeof fstack);
108 merge_sort_fstack(mfp1, putrec, ftbl);
109 if (fstack_2_count == MERGE_FNUM) {
110 /* More than 4096 files! */
112 memcpy(fstack, fstack_2, sizeof fstack);
113 merge_sort_fstack(mfp2, putrec, ftbl);
114 fstack_2[0].fp = mfp2;
117 fstack_2[fstack_2_count].fp = mfp1;
118 fstack_2[fstack_2_count].get = geteasy;
122 fstack_1[fstack_1_count].fp = mfp;
123 fstack_1[fstack_1_count].get = geteasy;
128 fstack[fstack_count].fp = fp;
129 fstack[fstack_count++].get = get;
133 fmerge(struct filelist *filelist, int nfiles, FILE *outfp, struct field *ftbl)
135 get_func_t get = SINGL_FLD ? makeline : makekey;
139 for (i = 0; i < nfiles; i++) {
140 fp = fopen(filelist->names[i], "r");
142 err(2, "%s", filelist->names[i]);
143 save_for_merge(fp, get, ftbl);
146 merge_sort(outfp, putline, ftbl);
150 merge_sort(FILE *outfp, put_func_t put, struct field *ftbl)
152 int count = fstack_1_count + fstack_2_count;
157 /* All files in initial array */
158 merge_sort_fstack(outfp, put, ftbl);
162 count += fstack_count;
164 /* Too many files for one merge sort */
166 /* Sort latest 16 files */
170 while (fstack_count > 0)
171 fstack[--i] = fstack[--fstack_count];
172 while (i > 0 && fstack_1_count > 0)
173 fstack[--i] = fstack_1[--fstack_1_count];
175 fstack[--i] = fstack_2[--fstack_2_count];
176 if (count <= MERGE_FNUM) {
177 /* Got all the data */
178 fstack_count = count;
179 merge_sort_fstack(outfp, put, ftbl);
183 fstack_count = count > MERGE_FNUM ? MERGE_FNUM : count;
184 merge_sort_fstack(mfp, putrec, ftbl);
186 fstack[0].get = geteasy;
188 count -= MERGE_FNUM - 1;
193 merge_sort_fstack(FILE *outfp, put_func_t put, struct field *ftbl)
195 struct mfile *flistb[MERGE_FNUM], **flist = flistb, *cfile;
202 /* Read one record from each file (read again if a duplicate) */
203 for (nfiles = i = 0; i < fstack_count; i++) {
205 if (cfile->rec == NULL) {
206 cfile->rec = allocrec(NULL, DEFLLEN);
207 cfile->end = (u_char *)cfile->rec + DEFLLEN;
212 c = cfile->get(cfile->fp, cfile->rec, cfile->end, ftbl);
217 /* Double buffer size */
218 sz = (cfile->end - (u_char *)cfile->rec) * 2;
219 cfile->rec = allocrec(cfile->rec, sz);
220 cfile->end = (u_char *)cfile->rec + sz;
225 if (insert(flist, cfile, nfiles, !DELETE))
226 /* Duplicate removed */
239 * We now loop reading a new record from the file with the
240 * 'sorted first' existing record.
241 * As each record is added, the 'first' record is written to the
242 * output file - maintaining one record from each file in the sorted
245 new_rec = allocrec(NULL, DEFLLEN);
246 new_end = (u_char *)new_rec + DEFLLEN;
249 c = cfile->get(cfile->fp, new_rec, new_end, ftbl);
251 /* Write out last record from now-empty input */
252 put(cfile->rec, outfp);
255 /* Replace from file with now-first sorted record. */
256 /* (Moving base 'flist' saves copying everything!) */
261 /* Buffer not large enough - double in size */
262 sz = (new_end - (u_char *)new_rec) * 2;
263 new_rec = allocrec(new_rec, sz);
264 new_end = (u_char *)new_rec +sz;
268 /* Swap in new buffer, saving old */
270 cfile->rec = new_rec;
273 cfile->end = new_end;
276 /* Add into sort, removing the original first entry */
277 c = insert(flist, cfile, nfiles, DELETE);
278 if (c != 0 || (UNIQUE && cfile == flist[0]
279 && cmp(new_rec, cfile->rec) == 0)) {
280 /* Was an unwanted duplicate, restore buffer */
282 cfile->rec = new_rec;
285 cfile->end = new_end;
290 /* Write out 'old' record */
298 * if delete: inserts rec in flist, deletes flist[0];
299 * otherwise just inserts *rec in flist.
300 * Returns 1 if record is a duplicate to be ignored.
303 insert(struct mfile **flist, struct mfile *rec, int ttop, int delete)
305 int mid, top = ttop, bot = 0, cmpv = 1;
307 for (mid = top / 2; bot + 1 != top; mid = (bot + top) / 2) {
308 cmpv = cmp(rec->rec, flist[mid]->rec);
311 /* Duplicate key, read another record */
312 /* NB: This doesn't guarantee to keep any
313 * particular record. */
316 * Apply sort by input file order.
317 * We could truncate the sort is the fileno are
318 * adjacent - but that is all too hard!
319 * The fileno cannot be equal, since we only have one
320 * record from each file (+ flist[0] which never
323 cmpv = rec < flist[mid] ? -1 : 1;
333 /* At this point we haven't yet compared against flist[0] */
336 /* flist[0] is ourselves, only the caller knows the old data */
338 memmove(flist, flist + 1, bot * sizeof(MFILE *));
344 /* Inserting original set of records */
346 if (bot == 0 && cmpv != 0) {
347 /* Doesn't match flist[1], must compare with flist[0] */
348 cmpv = cmp(rec->rec, flist[0]->rec);
349 if (cmpv == 0 && UNIQUE)
351 /* Add matching keys in file order (ie new is later) */
356 memmove(flist + bot + 1, flist + bot, (ttop - bot) * sizeof(MFILE *));
362 * check order on one file
365 order(struct filelist *filelist, struct field *ftbl)
367 get_func_t get = SINGL_FLD ? makeline : makekey;
368 RECHEADER *crec, *prec, *trec;
369 u_char *crec_end, *prec_end, *trec_end;
373 fp = fopen(filelist->names[0], "r");
375 err(2, "%s", filelist->names[0]);
377 crec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
378 crec_end = crec->data + DEFLLEN;
379 prec = malloc(offsetof(RECHEADER, data[DEFLLEN]));
380 prec_end = prec->data + DEFLLEN;
382 /* XXX this does exit(0) for overlong lines */
383 if (get(fp, prec, prec_end, ftbl) != 0)
385 while (get(fp, crec, crec_end, ftbl) == 0) {
386 if (0 < (c = cmp(prec, crec))) {
387 crec->data[crec->length-1] = 0;
388 errx(1, "found disorder: %s", crec->data+crec->offset);
391 crec->data[crec->length-1] = 0;
392 errx(1, "found non-uniqueness: %s",
393 crec->data+crec->offset);
396 * Swap pointers so that this record is on place pointed
397 * to by prec and new record is read to place pointed to by
411 cmp(RECHEADER *rec1, RECHEADER *rec2)
417 len = min(rec1->keylen, rec2->keylen);
418 r = memcmp(rec1->data, rec2->data, len);
420 r = rec1->keylen - rec2->keylen;