ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/meta/sort.c
Revision: 1.8
Committed: Sat Nov 15 02:13:37 2003 UTC (20 years, 11 months ago) by schorsch
Content type: text/plain
Branch: MAIN
CVS Tags: rad5R4, rad5R2, rad4R2P2, rad5R0, rad5R1, rad3R7P2, rad3R7P1, rad4R2, rad4R1, rad4R0, rad3R6, rad3R6P1, rad3R8, rad3R9, rad4R2P1, rad5R3, HEAD
Changes since 1.7: +2 -3 lines
Log Message:
Continued ANSIfication, and reduced other compile warnings.

File Contents

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