BACKGROUND READING:
http://www.geocities.com/logan.lee30..._analysis.html
http://www.geocities.com/logan.lee30..._analysis.html
Like this:
CODE:
#include "sort.h"
40
41
#ifndef lint
42
__RCSID("$NetBSD: append.c,v 1.10 2001/02/19 20:50:17 jdolecek Exp $");
43
__SCCSID("@(#)append.c 8.1 (Berkeley) 6/6/93");
44
#endif /* not lint */
45
46
#include <stdlib.h>
47
#include <string.h>
48
49
#define OUTPUT { \
50
if ((n = cpos - ppos) 1) { \
51
for (; ppos < cpos; ++ppos) \
52
*ppos -= odepth; \
53
ppos -= n; \
54
if (stable_sort) \
55
sradixsort(ppos, n, wts1, REC_D); \
56
else \
57
radixsort(ppos, n, wts1, REC_D); \
58
for (; ppos < cpos; ppos++) { \
59
prec = (const RECHEADER *) (*ppos - sizeof(TRECHEADER));\
60
put(prec, fp); \
61
} \
62
} else put(prec, fp); \
63
}
64
65
/*
66
* copy sorted lines to output; check for uniqueness
67
*/
68
void
69
append(keylist, nelem, depth, fp, put, ftbl)
70
const u_char **keylist;
71
int nelem;
72
int depth;
73
FILE *fp;
74
put_func_t put;
75
struct field *ftbl;
76
{
77
u_char *wts, *wts1;
78
int n, odepth=0;
79
const u_char **cpos, **ppos, **lastkey;
80
const u_char *cend, *pend, *start;
81
const struct recheader *crec, *prec;
82
83
if (*keylist == '\0' && UNIQUE)
84
return;
85
wts1 = wts = ftbl[0].weights;
86
if ((!UNIQUE) && SINGL_FLD) {
87
if ((ftbl[0].flags & F) && (ftbl[0].flags & R))
88
wts1 = Rascii;
89
else if (ftbl[0].flags & F)
90
wts1 = ascii;
91
odepth = depth;
92
}
93
lastkey = keylist + nelem;
94
depth += sizeof(TRECHEADER);
95
if (SINGL_FLD && (UNIQUE || wts1 != wts)) {
96
ppos = keylist;
97
prec = (const RECHEADER *) (*ppos - depth);
98
if (UNIQUE)
99
put(prec, fp);
100
for (cpos = &keylist[1]; cpos < lastkey; cpos++) {
101
crec = (const RECHEADER *) (*cpos - depth);
102
if (crec->length == prec->length) {
103
/*
104
* Set pend and cend so that trailing NUL and
105
* record separator is ignored.
106
*/
107
pend = (const u_char *) &prec->data + prec->length - 2;
108
cend = (const u_char *) &crec->data + crec->length - 2;
109
for (start = *cpos; cend >= start; cend--) {
110
if (wts[*cend] != wts[*pend])
111
break;
112
pend--;
113
}
114
if (pend + 1 != *ppos) {
115
if (!UNIQUE) {
116
OUTPUT;
117
} else
118
put(crec, fp);
119
ppos = cpos;
120
prec = crec;
121
}
122
} else {
123
if (!UNIQUE) {
124
OUTPUT;
125
} else
126
put(crec, fp);
127
ppos = cpos;
128
prec = crec;
129
}
130
}
131
if (!UNIQUE) { OUTPUT; }
132
} else if (UNIQUE) {
133
ppos = keylist;
134
prec = (const RECHEADER *) (*ppos - depth);
135
put(prec, fp);
136
for (cpos = &keylist[1]; cpos < lastkey; cpos++) {
137
crec = (const RECHEADER *) (*cpos - depth);
138
if (crec->offset == prec->offset) {
139
/*
140
* Set pend and cend so that trailing NUL and
141
* record separator is ignored.
142
*/
143
pend = (const u_char *) &prec->data + prec->offset - 2;
144
cend = (const u_char *) &crec->data + crec->offset - 2;
145
for (start = *cpos; cend >= start; cend--) {
146
if (wts[*cend] != wts[*pend])
147
break;
148
pend--;
149
}
150
if (pend + 1 != *ppos) {
151
ppos = cpos;
152
prec = crec;
153
put(prec, fp);
154
}
155
} else {
156
ppos = cpos;
157
prec = crec;
158
put(prec, fp);
159
}
160
}
161
} else for (cpos = keylist; cpos < lastkey; cpos++) {
162
crec = (const RECHEADER *) (*cpos - depth);
163
put(crec, fp);
164
}
165
}
166
167
/*
168
* output the already sorted eol bin.
169
*/
170
void
171
rd_append(binno, infl0, nfiles, outfp, buffer, bufend)
172
u_char *buffer;
173
int infl0;
174
int binno, nfiles;
175
FILE *outfp;
176
u_char *bufend;
177
{
178
RECHEADER *rec;
179
180
rec = (RECHEADER *) buffer;
181
if (!getnext(binno, infl0, NULL, nfiles,
182
(RECHEADER *) buffer, bufend, 0)) {
183
putline(rec, outfp);
184
while (getnext(binno, infl0, NULL, nfiles, (RECHEADER *) buffer,
185
bufend, 0) == 0) {
186
if (!UNIQUE)
187
putline(rec, outfp);
188
}
189
}
190
}
191
192
/*
193
* append plain text--used after sorting the biggest bin.
194
*/
195
void
196
concat(a, b)
197
FILE *a, *b;
198
{
199
int nread;
200
char buffer[4096];
201
202
rewind(b);
203
while ((nread = fread(buffer, 1, 4096, b)) 0)
204
EWRITE(buffer, 1, nread, a);
205
}
------------------------------------
SUMMARY:
sort
append.c
#include 3
#define OUTPUT
(I)[2]((I))_1[1,2,1]
append 6 200101
10211
I
I(I)[2]
(I)[3]((I))_2[1,1,1]
(I)[2]((I))_1[1,1]I
(I)[2]
(I)[2]
F(I)[2]((I))_1[1,1]I
F
rd_append 6 10011
1
IWI
concat 2 11
01
W
------------------------------------
You see it's much more simpler and aids human understanding of the code.
