Annotation of src/usr.bin/sort/append.c, Revision 1.4
1.4 ! mickey 1: /* $OpenBSD: append.c,v 1.3 1997/06/30 05:36:15 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[] = "@(#)append.c 8.1 (Berkeley) 6/6/93";
42: #else
1.4 ! mickey 43: static char rcsid[] = "$OpenBSD: append.c,v 1.3 1997/06/30 05:36:15 millert Exp $";
1.1 millert 44: #endif
45: #endif /* not lint */
46:
47: #include "sort.h"
48:
49: #include <stdlib.h>
50: #include <string.h>
51:
52: #define OUTPUT { \
53: if ((n = cpos - ppos) > 1) { \
54: for (; ppos < cpos; ++ppos) \
55: *ppos -= odepth; \
56: ppos -= n; \
57: radixsort((const u_char **)ppos, n, wts1, REC_D); \
58: for (; ppos < cpos; ppos++) { \
59: prec = (RECHEADER *) (*ppos - sizeof(TRECHEADER));\
60: put(prec, fp); \
61: } \
1.2 millert 62: } else \
63: put(prec, fp); \
1.1 millert 64: }
65:
66: /*
67: * copy sorted lines to output; check for uniqueness
68: */
69: void
70: append(keylist, nelem, depth, fp, put, ftbl)
71: u_char **keylist;
72: int nelem;
73: register int depth;
74: FILE *fp;
75: void (*put)(RECHEADER *, FILE *);
76: struct field *ftbl;
77: {
78: register u_char *wts, *wts1;
79: register n, odepth;
80: register u_char **cpos, **ppos, **lastkey;
81: register u_char *cend, *pend, *start;
1.3 millert 82: register RECHEADER *crec, *prec;
1.1 millert 83:
84: if (*keylist == '\0' && UNIQUE)
85: return;
86: wts1 = wts = ftbl[0].weights;
87: if ((!UNIQUE) && SINGL_FLD) {
88: if (ftbl[0].flags & F && ftbl[0].flags & R)
89: wts1 = Rascii;
90: else if (ftbl[0].flags & F)
91: wts1 = ascii;
92: odepth = depth;
93: }
94: lastkey = keylist + nelem;
95: depth += sizeof(TRECHEADER);
96: if (SINGL_FLD && (UNIQUE || wts1 != wts)) {
97: ppos = keylist;
98: prec = (RECHEADER *) (*ppos - depth);
99: if (UNIQUE)
100: put(prec, fp);
101: for (cpos = keylist+1; cpos < lastkey; cpos++) {
102: crec = (RECHEADER *) (*cpos - depth);
103: if (crec->length == prec->length) {
104: pend = (u_char *) &prec->offset + prec->length;
105: cend = (u_char *) &crec->offset + crec->length;
106: for (start = *cpos; cend >= start; cend--) {
107: if (wts[*cend] != wts[*pend])
108: break;
109: pend--;
110: }
111: if (pend + 1 != *ppos) {
1.2 millert 112: if (!UNIQUE)
113: OUTPUT
114: else
1.1 millert 115: put(crec, fp);
116: ppos = cpos;
117: prec = crec;
118: }
119: } else {
1.2 millert 120: if (!UNIQUE)
121: OUTPUT
122: else
1.1 millert 123: put(crec, fp);
124: ppos = cpos;
125: prec = crec;
126: }
127: }
1.2 millert 128: if (!UNIQUE)
1.4 ! mickey 129: OUTPUT
1.1 millert 130: } else if (UNIQUE) {
131: ppos = keylist;
132: prec = (RECHEADER *) (*ppos - depth);
133: put(prec, fp);
134: for (cpos = keylist+1; cpos < lastkey; cpos++) {
135: crec = (RECHEADER *) (*cpos - depth);
136: if (crec->offset == prec->offset) {
137: pend = (u_char *) &prec->offset + prec->offset;
138: cend = (u_char *) &crec->offset + crec->offset;
139: for (start = *cpos; cend >= start; cend--) {
140: if (wts[*cend] != wts[*pend])
141: break;
142: pend--;
143: }
144: if (pend + 1 != *ppos) {
145: ppos = cpos;
146: prec = crec;
147: put(prec, fp);
148: }
149: } else {
150: ppos = cpos;
151: prec = crec;
152: put(prec, fp);
153: }
154: }
155: } else for (cpos = keylist; cpos < lastkey; cpos++) {
156: crec = (RECHEADER *) (*cpos - depth);
157: put(crec, fp);
158: }
159: }
160:
161: /*
162: * output the already sorted eol bin.
163: */
164: void
165: rd_append(binno, infl0, nfiles, outfp, buffer, bufend)
166: u_char *buffer, *bufend;
167: int binno, nfiles;
168: union f_handle infl0;
169: FILE *outfp;
170: {
1.3 millert 171: RECHEADER *rec;
1.2 millert 172:
1.1 millert 173: rec = (RECHEADER *) buffer;
174: if (!getnext(binno, infl0, nfiles, (RECHEADER *) buffer, bufend, 0)) {
175: putline(rec, outfp);
176: while (getnext(binno, infl0, nfiles, (RECHEADER *) buffer,
177: bufend, 0) == 0) {
178: if (!UNIQUE)
179: putline(rec, outfp);
180: }
181: }
182: }
183:
184: /*
185: * append plain text--used after sorting the biggest bin.
186: */
187: void
188: concat(a, b)
189: FILE *a, *b;
190: {
191: int nread;
192: char buffer[4096];
193:
194: rewind(b);
195: while ((nread = fread(buffer, 1, 4096, b)) > 0)
196: EWRITE(buffer, 1, nread, a);
197: }