ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/meta/sort.c
Revision: 1.5
Committed: Mon Jun 16 14:54:54 2003 UTC (21 years, 6 months ago) by greg
Content type: text/plain
Branch: MAIN
Changes since 1.4: +4 -4 lines
Log Message:
Removed malloc.h includes and renamed mergesort() to pmergesort()

File Contents

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