ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/meta/sort.c
Revision: 1.7
Committed: Tue Oct 21 19:19:28 2003 UTC (21 years, 1 month ago) by schorsch
Content type: text/plain
Branch: MAIN
Changes since 1.6: +2 -1 lines
Log Message:
Various platform compatibility fixes.

File Contents

# User Rev Content
1 greg 1.1 #ifndef lint
2 schorsch 1.7 static const char RCSid[] = "$Id: sort.c,v 1.6 2003/07/14 20:02:29 schorsch Exp $";
3 greg 1.1 #endif
4     /*
5     * Sorting routines for meta-files
6     */
7    
8 schorsch 1.7 #include "platform.h" /* [_]snprintf() */
9 schorsch 1.6 #include "rtprocess.h" /* getpid() */
10     #include "rterror.h"
11 schorsch 1.2 #include "meta.h"
12 schorsch 1.3
13 greg 1.1
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 schorsch 1.2 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 greg 1.1
26     /*
27     * This sort routine does a combination quicksort and
28     * n-ary mergesort
29     */
30    
31    
32 schorsch 1.2 void
33     sort( /* sort primitives according to pcmp */
34     FILE *infp,
35     int (*pcmp)() /* compares pointers to pointers to primitives! */
36     )
37 greg 1.1 {
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 schorsch 1.2 void
84 greg 1.5 pmergesort( /* merge sorted files with list */
85 greg 1.1
86 schorsch 1.2 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 greg 1.1 {
93     PRIMITIVE *plp; /* position in list */
94     PRIMITIVE *pp[NFILES]; /* input primitives */
95     int minf;
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 greg 1.5 error(SYSTEM, "memory exhausted in pmergesort");
107 greg 1.1 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 schorsch 1.2 static void
149     treemerge( /* merge into one file */
150 greg 1.1
151 schorsch 1.2 int height, int nt, int nf,
152     PLIST *pl,
153     int (*pcmp)(),
154     FILE *ofp
155     )
156 greg 1.1 {
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 greg 1.5 pmergesort(fi, nf, pl, pcmp, fp);
169 greg 1.1
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 schorsch 1.2 static void
196     sendsort( /* send a sorted list */
197 greg 1.1
198 schorsch 1.2 PLIST *pl,
199     int (*pcmp)()
200     )
201 greg 1.1 {
202     static int nf = 0,
203     intree = FALSE;
204     FILE *fp;
205    
206     if (isglob(pl->pbot->com)) {
207    
208     /* send sorted output to stdout */
209     if (intree && nf <= NFILES)
210    
211     treemerge(0, 0, nf, pl, pcmp, stdout);
212    
213     else if (nf%NFILES == 0)
214    
215     if (intree) {
216     treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
217     treemerge(1, 0, nf/NFILES, NULL, pcmp, stdout);
218     } else
219     treemerge(1, 0, nf/NFILES, pl, pcmp, stdout);
220    
221     else {
222    
223     treemerge(0, nf/NFILES, nf%NFILES, pl, pcmp, NULL);
224     treemerge(1, 0, nf/NFILES + 1, NULL, pcmp, stdout);
225    
226     }
227    
228     nf = 0; /* all done */
229     intree = FALSE; /* reset for next time */
230    
231     } else if (intree && nf%NFILES == 0) {
232    
233     /* merge NFILES with list */
234     treemerge(0, nf/NFILES - 1, NFILES, pl, pcmp, NULL);
235     intree = FALSE;
236    
237     } else {
238    
239     /* output straight to temp file */
240     treemerge(-1, nf++, 0, pl, pcmp, NULL);
241     intree = TRUE;
242    
243     }
244    
245    
246    
247     }
248    
249    
250    
251 schorsch 1.2 static void
252     order( /* order the first n array primitives into list */
253 greg 1.1
254 schorsch 1.2 PRIMITIVE *pa[],
255     int n,
256     PLIST *pl
257     )
258 greg 1.1 {
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 schorsch 1.2 tfname( /* create temporary file name */
275 greg 1.1
276 schorsch 1.2 int lvl, int num
277     )
278 greg 1.1 {
279 schorsch 1.2 static char pathbuf[PATH_MAX];
280 schorsch 1.3 static char fnbuf[PATH_MAX];
281     static size_t psiz;
282 greg 1.1
283 schorsch 1.3 if (pathbuf[0] == '\0') { /* first time */
284     temp_directory(pathbuf, sizeof(pathbuf));
285     psiz = strlen(pathbuf);
286     }
287 schorsch 1.4 snprintf(fnbuf, sizeof(pathbuf)-psiz,
288 schorsch 1.3 "%s/S%d%c%d", pathbuf, getpid(), lvl+'A', num);
289 schorsch 1.2 /*sprintf(fnbuf, "%sS%d%c%d", TDIR, getpid(), lvl+'A', num);*/
290 greg 1.1
291 schorsch 1.3 return(fnbuf);
292 greg 1.1 }