Annotation of src/usr.bin/sort/append.c, Revision 1.8
1.8 ! millert 1: /* $OpenBSD: append.c,v 1.7 2001/03/20 19:36:27 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.
1.8 ! millert 18: * 3. Neither the name of the University nor the names of its contributors
1.1 millert 19: * may be used to endorse or promote products derived from this software
20: * without specific prior written permission.
21: *
22: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32: * SUCH DAMAGE.
33: */
34:
35: #ifndef lint
36: #if 0
37: static char sccsid[] = "@(#)append.c 8.1 (Berkeley) 6/6/93";
38: #else
1.8 ! millert 39: static char rcsid[] = "$OpenBSD: append.c,v 1.7 2001/03/20 19:36:27 millert Exp $";
1.1 millert 40: #endif
41: #endif /* not lint */
42:
43: #include "sort.h"
44:
45: #include <stdlib.h>
46: #include <string.h>
47:
48: #define OUTPUT { \
49: if ((n = cpos - ppos) > 1) { \
50: for (; ppos < cpos; ++ppos) \
51: *ppos -= odepth; \
52: ppos -= n; \
53: radixsort((const u_char **)ppos, n, wts1, REC_D); \
54: for (; ppos < cpos; ppos++) { \
55: prec = (RECHEADER *) (*ppos - sizeof(TRECHEADER));\
56: put(prec, fp); \
57: } \
1.2 millert 58: } else \
59: put(prec, fp); \
1.1 millert 60: }
61:
62: /*
63: * copy sorted lines to output; check for uniqueness
64: */
65: void
66: append(keylist, nelem, depth, fp, put, ftbl)
67: u_char **keylist;
68: int nelem;
1.6 ericj 69: int depth;
1.1 millert 70: FILE *fp;
71: void (*put)(RECHEADER *, FILE *);
72: struct field *ftbl;
73: {
1.6 ericj 74: u_char *wts, *wts1;
75: int n, odepth;
76: u_char **cpos, **ppos, **lastkey;
77: u_char *cend, *pend, *start;
78: RECHEADER *crec, *prec;
1.1 millert 79:
1.7 millert 80: if (*keylist == NULL)
1.1 millert 81: return;
82: wts1 = wts = ftbl[0].weights;
83: if ((!UNIQUE) && SINGL_FLD) {
84: if (ftbl[0].flags & F && ftbl[0].flags & R)
85: wts1 = Rascii;
86: else if (ftbl[0].flags & F)
87: wts1 = ascii;
88: odepth = depth;
89: }
90: lastkey = keylist + nelem;
91: depth += sizeof(TRECHEADER);
92: if (SINGL_FLD && (UNIQUE || wts1 != wts)) {
93: ppos = keylist;
94: prec = (RECHEADER *) (*ppos - depth);
95: if (UNIQUE)
96: put(prec, fp);
1.6 ericj 97: for (cpos = &keylist[1]; cpos < lastkey; cpos++) {
1.1 millert 98: crec = (RECHEADER *) (*cpos - depth);
99: if (crec->length == prec->length) {
1.6 ericj 100: /*
101: * Set pend and cend so that trailing NUL and
102: * record separator is ignored.
103: */
104: pend = (u_char *)&prec->data + prec->length - 2;
105: cend = (u_char *)&crec->data + crec->length - 2;
1.1 millert 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);
1.6 ericj 134: for (cpos = &keylist[1]; cpos < lastkey; cpos++) {
1.1 millert 135: crec = (RECHEADER *) (*cpos - depth);
136: if (crec->offset == prec->offset) {
1.6 ericj 137: /*
138: * Set pend and cend so that trailing NUL and
139: * record separator is ignored.
140: */
141: pend = (u_char *)&prec->data + prec->offset - 2;
142: cend = (u_char *)&crec->data + crec->offset - 2;
1.1 millert 143: for (start = *cpos; cend >= start; cend--) {
144: if (wts[*cend] != wts[*pend])
145: break;
146: pend--;
147: }
148: if (pend + 1 != *ppos) {
149: ppos = cpos;
150: prec = crec;
151: put(prec, fp);
152: }
153: } else {
154: ppos = cpos;
155: prec = crec;
156: put(prec, fp);
157: }
158: }
159: } else for (cpos = keylist; cpos < lastkey; cpos++) {
160: crec = (RECHEADER *) (*cpos - depth);
161: put(crec, fp);
162: }
163: }
164:
165: /*
166: * output the already sorted eol bin.
167: */
168: void
169: rd_append(binno, infl0, nfiles, outfp, buffer, bufend)
170: u_char *buffer, *bufend;
171: int binno, nfiles;
172: union f_handle infl0;
173: FILE *outfp;
174: {
1.3 millert 175: RECHEADER *rec;
1.2 millert 176:
1.1 millert 177: rec = (RECHEADER *) buffer;
178: if (!getnext(binno, infl0, nfiles, (RECHEADER *) buffer, bufend, 0)) {
179: putline(rec, outfp);
180: while (getnext(binno, infl0, nfiles, (RECHEADER *) buffer,
181: bufend, 0) == 0) {
182: if (!UNIQUE)
183: putline(rec, outfp);
184: }
185: }
186: }
187:
188: /*
189: * append plain text--used after sorting the biggest bin.
190: */
191: void
192: concat(a, b)
193: FILE *a, *b;
194: {
195: int nread;
196: char buffer[4096];
197:
198: rewind(b);
199: while ((nread = fread(buffer, 1, 4096, b)) > 0)
200: EWRITE(buffer, 1, nread, a);
201: }