ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/meta/sort.c
Revision: 1.1
Committed: Sat Feb 22 02:07:26 2003 UTC (21 years, 9 months ago) by greg
Content type: text/plain
Branch: MAIN
CVS Tags: rad3R5
Log Message:
Changes and check-in for 3.5 release
Includes new source files and modifications not recorded for many years
See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id$";
3 #endif
4 /*
5 * Sorting routines for meta-files
6 */
7
8
9 #define PBSIZE 1000 /* max size of sort block */
10 /* maxalloc must be >= this */
11
12
13 #define NFILES 4 /* number of sort files */
14
15
16
17 #include "meta.h"
18
19
20
21
22
23
24
25 /*
26 * This sort routine does a combination quicksort and
27 * n-ary mergesort
28 */
29
30
31 sort(infp, pcmp) /* sort primitives according to pcmp */
32
33 FILE *infp;
34 int (*pcmp)(); /* compares pointers to pointers to primitives! */
35
36 {
37 PRIMITIVE *prims[PBSIZE]; /* pointers to primitives */
38 PLIST primlist; /* our primitives list */
39 int nprims;
40 short done;
41
42 do {
43
44 for (nprims = 0; nprims < PBSIZE; nprims++) { /* read to global */
45
46 if ((prims[nprims] = palloc()) == NULL)
47 error(SYSTEM, "memory exhausted in sort");
48
49 readp(prims[nprims], infp);
50
51 if (isglob(prims[nprims]->com))
52 break;
53 }
54
55 qsort(prims, nprims, sizeof(*prims), pcmp); /* sort pointer array */
56
57 if (nprims < PBSIZE) /* tack on global if one */
58 nprims++;
59
60 order(prims, nprims, &primlist); /* make array into list */
61
62 sendsort(&primlist, pcmp); /* send to merge sorter */
63
64 done = primlist.pbot->com == PEOF;
65
66 plfree(&primlist); /* free up array */
67
68 } while (!done);
69
70 }
71
72
73
74
75
76 /*
77 * The following routine merges up to NFILES sorted primitive files
78 * with 0 or 1 primitive lists. Each set of primitives can end with
79 * 0 or 1 global commands.
80 */
81
82 mergesort(fi, nf, pl, pcmp, ofp) /* merge sorted files with list */
83
84 FILE *fi[]; /* array of input files */
85 int nf; /* number of input files */
86 PLIST *pl; /* sorted list */
87 int (*pcmp)(); /* comparison function, takes primitive handles */
88 FILE *ofp; /* output file */
89
90 {
91 PRIMITIVE *plp; /* position in list */
92 PRIMITIVE *pp[NFILES]; /* input primitives */
93 int minf;
94 PRIMITIVE *minp;
95 register int i;
96
97 if (pl == NULL)
98 plp = NULL; /* initialize list */
99 else
100 plp = pl->ptop;
101
102 for (i = 0; i < nf; i++) { /* initialize input files */
103 if ((pp[i] = palloc()) == NULL)
104 error(SYSTEM, "memory exhausted in mergesort");
105 readp(pp[i], fi[i]);
106 }
107
108 for ( ; ; ) {
109
110 if (plp != NULL && isprim(plp->com))
111 minp = plp;
112 else
113 minp = NULL;
114
115 for (i = 0; i < nf; i++)
116 if (isprim(pp[i]->com) &&
117 (minp == NULL || (*pcmp)(&pp[i], &minp) < 0))
118 minp = pp[minf=i];
119
120 if (minp == NULL)
121 break;
122
123 writep(minp, ofp);
124
125 if (minp == plp)
126 plp = plp->pnext;
127 else {
128 fargs(pp[minf]);
129 readp(pp[minf], fi[minf]);
130 }
131 }
132
133 if (plp != NULL && plp->com != PEOF)
134 writep(plp, ofp);
135
136 for (i = 0; i < nf; i++) {
137 if (pp[i]->com != PEOF)
138 writep(pp[i], ofp);
139 pfree(pp[i]);
140 }
141
142 }
143
144
145
146 static
147 treemerge(height, nt, nf, pl, pcmp, ofp) /* merge into one file */
148
149 int height, nt, nf;
150 PLIST *pl;
151 int (*pcmp)();
152 FILE *ofp;
153
154 {
155 char *tfname();
156 FILE *fi[NFILES], *fp;
157 int i;
158
159 if (nf <= NFILES) {
160
161 for (i = 0; i < nf; i++)
162 fi[i] = efopen(tfname(height, i + nt*NFILES), "r");
163
164 if ((fp = ofp) == NULL)
165 fp = efopen(tfname(height + 1, nt), "w");
166
167 mergesort(fi, nf, pl, pcmp, fp);
168
169 for (i = 0; i < nf; i++) {
170 fclose(fi[i]);
171 unlink(tfname(height, i + nt*NFILES));
172 }
173 if (ofp == NULL) {
174 writeof(fp);
175 fclose(fp);
176 }
177
178 } else {
179
180 for (i = 0; i < (nf-1)/NFILES; i++)
181 treemerge(height, i, NFILES, NULL, pcmp, NULL);
182
183 treemerge(height, (nf-1)/NFILES, (nf-1)%NFILES + 1, pl, pcmp, NULL);
184
185 treemerge(height + 1, 0, (nf-1)/NFILES + 1, NULL, pcmp, ofp);
186
187 }
188
189 }
190
191
192
193
194 static
195 sendsort(pl, pcmp) /* send a sorted list */
196
197 PLIST *pl;
198 int (*pcmp)();
199
200 {
201 static int nf = 0,
202 intree = FALSE;
203 FILE *fp;
204
205 if (isglob(pl->pbot->com)) {
206
207 /* send sorted output to stdout */
208 if (intree && nf <= NFILES)
209
210 treemerge(0, 0, nf, pl, pcmp, stdout);
211
212 else if (nf%NFILES == 0)
213
214 if (intree) {
215 treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
216 treemerge(1, 0, nf/NFILES, NULL, pcmp, stdout);
217 } else
218 treemerge(1, 0, nf/NFILES, pl, pcmp, stdout);
219
220 else {
221
222 treemerge(0, nf/NFILES, nf%NFILES, pl, pcmp, NULL);
223 treemerge(1, 0, nf/NFILES + 1, NULL, pcmp, stdout);
224
225 }
226
227 nf = 0; /* all done */
228 intree = FALSE; /* reset for next time */
229
230 } else if (intree && nf%NFILES == 0) {
231
232 /* merge NFILES with list */
233 treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
234 intree = FALSE;
235
236 } else {
237
238 /* output straight to temp file */
239 treemerge(-1, nf++, 0, pl, pcmp, NULL);
240 intree = TRUE;
241
242 }
243
244
245
246 }
247
248
249
250
251 static
252 order(pa, n, pl) /* order the first n array primitives into list */
253
254 PRIMITIVE *pa[];
255 int n;
256 PLIST *pl;
257
258 {
259 register int i;
260
261 for (i = 1; i < n; i++)
262 pa[i-1]->pnext = pa[i];
263
264 pa[n-1]->pnext = NULL;
265 pl->ptop = pa[0];
266 pl->pbot = pa[n-1];
267
268 }
269
270
271
272
273 static char *
274 tfname(lvl, num) /* create temporary file name */
275
276 int lvl, num;
277
278 {
279 static char fnbuf[32];
280
281 sprintf(fnbuf, "%sS%d%c%d", TDIR, getpid(), lvl+'A', num);
282
283 return(fnbuf);
284 }