Annotation of src/usr.bin/sort/msort.c, Revision 1.9
1.9 ! ericj 1: /* $OpenBSD: msort.c,v 1.8 2000/06/30 16:00:23 millert Exp $ */
1.1 millert 2:
3: /*-
4: * Copyright (c) 1993
5: * The Regents of the University of California. All rights reserved.
6: *
7: * This code is derived from software contributed to Berkeley by
8: * Peter McIlroy.
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: * 3. All advertising materials mentioning features or use of this software
19: * must display the following acknowledgement:
20: * This product includes software developed by the University of
21: * California, Berkeley and its contributors.
22: * 4. Neither the name of the University nor the names of its contributors
23: * may be used to endorse or promote products derived from this software
24: * without specific prior written permission.
25: *
26: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36: * SUCH DAMAGE.
37: */
38:
39: #ifndef lint
40: #if 0
41: static char sccsid[] = "@(#)msort.c 8.1 (Berkeley) 6/6/93";
42: #else
1.9 ! ericj 43: static char rcsid[] = "$OpenBSD: msort.c,v 1.8 2000/06/30 16:00:23 millert Exp $";
1.1 millert 44: #endif
45: #endif /* not lint */
46:
47: #include "sort.h"
48: #include "fsort.h"
49:
50: #include <stdlib.h>
51: #include <string.h>
52: #include <unistd.h>
53:
54: /* Subroutines using comparisons: merge sort and check order */
55: #define DELETE (1)
1.5 millert 56: #define LALIGN(n) ((n+(sizeof(long)-1)) & ~(sizeof(long)-1))
1.1 millert 57:
58: typedef struct mfile {
59: u_char *end;
60: short flno;
1.6 millert 61: RECHEADER rec[1];
1.1 millert 62: } MFILE;
63: typedef struct tmfile {
64: u_char *end;
65: short flno;
1.6 millert 66: TRECHEADER rec[1];
1.1 millert 67: } TMFILE;
68: u_char *wts, *wts1 = 0;
69: struct mfile *cfilebuf;
70:
1.6 millert 71: static int cmp __P((RECHEADER *, RECHEADER *));
1.1 millert 72: static int insert __P((struct mfile **, struct mfile **, int, int));
73:
74: void
75: fmerge(binno, files, nfiles, get, outfp, fput, ftbl)
76: union f_handle files;
77: int binno, nfiles;
78: int (*get)();
79: FILE *outfp;
80: void (*fput)();
81: struct field *ftbl;
82: {
83: FILE *tout;
84: int i, j, last;
1.6 millert 85: void (*put)(RECHEADER *, FILE *);
1.1 millert 86: extern int geteasy();
87: struct tempfile *l_fstack;
88:
89: wts = ftbl->weights;
1.9 ! ericj 90: if (!UNIQUE && SINGL_FLD && (ftbl->flags & F))
1.1 millert 91: wts1 = (ftbl->flags & R) ? Rascii : ascii;
1.7 millert 92: if (!cfilebuf) {
1.1 millert 93: cfilebuf = malloc(MAXLLEN + sizeof(TMFILE));
1.7 millert 94: if (cfilebuf == NULL)
95: errx(2, "cannot allocate memory");
96: }
1.1 millert 97:
98: i = min(16, nfiles) * LALIGN(MAXLLEN+sizeof(TMFILE));
99: if (!buffer || i > BUFSIZE) {
100: buffer = buffer ? realloc(buffer, i) : malloc(i);
101: if (!buffer)
1.7 millert 102: errx(2, "cannot allocate memory");
103: if (!SINGL_FLD) {
104: if ((linebuf = malloc(MAXLLEN)) == NULL)
105: errx(2, "cannot allocate memory");
106: }
1.1 millert 107: }
108:
109: if (binno >= 0)
110: l_fstack = fstack + files.top;
111: else
112: l_fstack = fstack;
1.4 millert 113:
1.1 millert 114: while (nfiles) {
115: put = putrec;
116: for (j = 0; j < nfiles; j += 16) {
117: if (nfiles <= 16) {
118: tout = outfp;
119: put = fput;
120: }
121: else
122: tout = ftmp();
123: last = min(16, nfiles - j);
124: if (binno < 0) {
125: for (i = 0; i < last; i++)
126: if (!(l_fstack[i+MAXFCT-1-16].fp =
127: fopen(files.names[j + i], "r")))
1.8 millert 128: err(2, "%s", files.names[j+i]);
1.1 millert 129: merge(MAXFCT-1-16, last, get, tout, put, ftbl);
1.4 millert 130: } else {
1.1 millert 131: for (i = 0; i< last; i++)
132: rewind(l_fstack[i+j].fp);
133: merge(files.top+j, last, get, tout, put, ftbl);
134: }
1.4 millert 135: if (nfiles > 16)
136: l_fstack[j/16].fp = tout;
1.1 millert 137: }
138: nfiles = (nfiles + 15) / 16;
139: if (nfiles == 1)
140: nfiles = 0;
141: if (binno < 0) {
142: binno = 0;
143: get = geteasy;
144: files.top = 0;
145: }
146: }
147: }
148:
149: void
150: merge(infl0, nfiles, get, outfp, put, ftbl)
151: int infl0, nfiles;
152: int (*get)();
1.6 millert 153: void (*put)(RECHEADER *, FILE *);
1.1 millert 154: FILE *outfp;
155: struct field *ftbl;
156: {
157: int c, i, j;
158: union f_handle dummy = {0};
159: struct mfile *flist[16], *cfile;
1.2 millert 160:
1.1 millert 161: for (i = j = 0; i < nfiles; i++) {
162: cfile = (MFILE *) (buffer +
163: i * LALIGN(MAXLLEN + sizeof(TMFILE)));
164: cfile->flno = j + infl0;
165: cfile->end = cfile->rec->data + MAXLLEN;
166: for (c = 1; c == 1;) {
167: if (EOF == (c = get(j+infl0, dummy, nfiles,
168: cfile->rec, cfile->end, ftbl))) {
1.4 millert 169: i--;
170: nfiles--;
1.1 millert 171: break;
172: }
173: if (i)
174: c = insert(flist, &cfile, i, !DELETE);
175: else
176: flist[0] = cfile;
177: }
178: j++;
179: }
1.2 millert 180: if (nfiles > 0) {
181: cfile = cfilebuf;
182: cfile->flno = flist[0]->flno;
183: cfile->end = cfile->rec->data + MAXLLEN;
184: while (nfiles) {
185: for (c = 1; c == 1;) {
186: if (EOF == (c = get(cfile->flno, dummy, nfiles,
187: cfile->rec, cfile->end, ftbl))) {
188: put(flist[0]->rec, outfp);
189: memmove(flist, flist + 1,
190: sizeof(MFILE *) * (--nfiles));
191: cfile->flno = flist[0]->flno;
192: break;
193: }
194: if (!(c = insert(flist, &cfile, nfiles, DELETE)))
195: put(cfile->rec, outfp);
1.1 millert 196: }
1.2 millert 197: }
1.1 millert 198: }
199: }
200:
201: /*
202: * if delete: inserts *rec in flist, deletes flist[0], and leaves it in *rec;
203: * otherwise just inserts *rec in flist.
1.4 millert 204: */
1.1 millert 205: static int
206: insert(flist, rec, ttop, delete)
207: struct mfile **flist, **rec;
208: int delete, ttop; /* delete = 0 or 1 */
209: {
1.9 ! ericj 210: struct mfile *tmprec;
! 211: int top, mid, bot = 0, cmpv = 1;
1.1 millert 212: tmprec = *rec;
213: top = ttop;
214: for (mid = top/2; bot +1 != top; mid = (bot+top)/2) {
215: cmpv = cmp(tmprec->rec, flist[mid]->rec);
216: if (cmpv < 0)
217: top = mid;
218: else if (cmpv > 0)
219: bot = mid;
220: else {
221: if (!UNIQUE)
222: bot = mid - 1;
223: break;
224: }
225: }
226: if (delete) {
227: if (UNIQUE) {
228: if (!bot && cmpv)
229: cmpv = cmp(tmprec->rec, flist[0]->rec);
230: if (!cmpv)
1.4 millert 231: return (1);
1.1 millert 232: }
233: tmprec = flist[0];
234: if (bot)
235: memmove(flist, flist+1, bot * sizeof(MFILE **));
236: flist[bot] = *rec;
237: *rec = tmprec;
238: (*rec)->flno = (*flist)->flno;
239: return (0);
240: }
241: else {
242: if (!bot && !(UNIQUE && !cmpv)) {
243: cmpv = cmp(tmprec->rec, flist[0]->rec);
244: if (cmpv < 0)
245: bot = -1;
246: }
247: if (UNIQUE && !cmpv)
248: return (1);
249: bot++;
250: memmove(flist + bot+1, flist + bot,
251: (ttop - bot) * sizeof(MFILE **));
252: flist[bot] = *rec;
253: return (0);
254: }
255: }
256:
257: /*
258: * check order on one file
259: */
260: void
261: order(infile, get, ftbl)
262: union f_handle infile;
263: int (*get)();
264: struct field *ftbl;
265: {
1.9 ! ericj 266: u_char *crec_end, *prec_end, *trec_end;
1.1 millert 267: int c;
1.6 millert 268: RECHEADER *crec, *prec, *trec;
1.1 millert 269:
1.7 millert 270: if (!SINGL_FLD) {
271: if ((linebuf = malloc(MAXLLEN)) == NULL)
272: errx(2, "cannot allocate memory");
273: }
1.1 millert 274: buffer = malloc(2 * (MAXLLEN + sizeof(TRECHEADER)));
1.7 millert 275: if (buffer == NULL)
276: errx(2, "cannot allocate memory");
1.1 millert 277: crec = (RECHEADER *) buffer;
1.9 ! ericj 278: crec_end = buffer + MAXLLEN + sizeof(TRECHEADER);
1.1 millert 279: prec = (RECHEADER *) (buffer + MAXLLEN + sizeof(TRECHEADER));
1.9 ! ericj 280: prec_end = buffer + 2 * (MAXLLEN + sizeof(TRECHEADER));
1.1 millert 281: wts = ftbl->weights;
1.9 ! ericj 282: if (SINGL_FLD && (ftbl->flags & F))
1.1 millert 283: wts1 = ftbl->flags & R ? Rascii : ascii;
284: else
285: wts1 = 0;
1.9 ! ericj 286: if (get(-1, infile, 1, prec, prec_end, ftbl) == 0)
! 287: while (get(-1, infile, 1, crec, crec_end, ftbl) == 0) {
1.4 millert 288: if (0 < (c = cmp(prec, crec))) {
289: crec->data[crec->length-1] = 0;
290: errx(1, "found disorder: %s",
291: crec->data+crec->offset);
292: }
293: if (UNIQUE && !c) {
294: crec->data[crec->length-1] = 0;
295: errx(1, "found non-uniqueness: %s",
296: crec->data+crec->offset);
297: }
1.9 ! ericj 298: /* Swap pointers so that this record is on place
! 299: * pointed to by prec and new record is read to place
! 300: * pointed to by crec.
! 301: */
1.4 millert 302: trec = prec;
303: prec = crec;
304: crec = trec;
1.9 ! ericj 305: trec_end = prec_end;
! 306: prec_end = crec_end;
! 307: crec_end = trec_end;
1.1 millert 308: }
309: exit(0);
310: }
311:
312: static int
313: cmp(rec1, rec2)
1.6 millert 314: RECHEADER *rec1, *rec2;
1.1 millert 315: {
1.9 ! ericj 316: int r;
! 317: u_char *pos1, *pos2, *end;
! 318: u_char *cwts;
1.1 millert 319: for (cwts = wts; cwts; cwts = (cwts == wts1 ? 0 : wts1)) {
320: pos1 = rec1->data;
321: pos2 = rec2->data;
322: if (!SINGL_FLD && UNIQUE)
323: end = pos1 + min(rec1->offset, rec2->offset);
324: else
325: end = pos1 + min(rec1->length, rec2->length);
326: for (; pos1 < end; ) {
327: if ((r = cwts[*pos1++] - cwts[*pos2++]))
328: return (r);
329: }
330: }
331: return (0);
332: }
![[BACK]](/icons/back.gif){kind=icon}
Return to msort.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / sort