ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/meta/sort.c
Revision: 1.2
Committed: Sun Jun 8 12:03:10 2003 UTC (21 years, 6 months ago) by schorsch
Content type: text/plain
Branch: MAIN
Changes since 1.1: +49 -46 lines
Log Message:
Reduced compile warnings/errors on Windows.

File Contents

# User Rev Content
1 greg 1.1 #ifndef lint
2 schorsch 1.2 static const char RCSid[] = "$Id: sort.c,v 1.1 2003/02/22 02:07:26 greg Exp $";
3 greg 1.1 #endif
4     /*
5     * Sorting routines for meta-files
6     */
7    
8 schorsch 1.2 #include "paths.h"
9     #include "meta.h"
10    
11 greg 1.1
12     #define PBSIZE 1000 /* max size of sort block */
13     /* maxalloc must be >= this */
14    
15     #define NFILES 4 /* number of sort files */
16    
17    
18 schorsch 1.2 static void treemerge(int height, int nt, int nf, PLIST *pl,
19     int (*pcmp)(), FILE *ofp);
20     static void sendsort( PLIST *pl, int (*pcmp)());
21     static void order(PRIMITIVE *pa[], int n, PLIST *pl);
22     static char * tfname( int lvl, int num);
23 greg 1.1
24     /*
25     * This sort routine does a combination quicksort and
26     * n-ary mergesort
27     */
28    
29    
30 schorsch 1.2 void
31     sort( /* sort primitives according to pcmp */
32     FILE *infp,
33     int (*pcmp)() /* compares pointers to pointers to primitives! */
34     )
35 greg 1.1 {
36     PRIMITIVE *prims[PBSIZE]; /* pointers to primitives */
37     PLIST primlist; /* our primitives list */
38     int nprims;
39     short done;
40    
41     do {
42    
43     for (nprims = 0; nprims < PBSIZE; nprims++) { /* read to global */
44    
45     if ((prims[nprims] = palloc()) == NULL)
46     error(SYSTEM, "memory exhausted in sort");
47    
48     readp(prims[nprims], infp);
49    
50     if (isglob(prims[nprims]->com))
51     break;
52     }
53    
54     qsort(prims, nprims, sizeof(*prims), pcmp); /* sort pointer array */
55    
56     if (nprims < PBSIZE) /* tack on global if one */
57     nprims++;
58    
59     order(prims, nprims, &primlist); /* make array into list */
60    
61     sendsort(&primlist, pcmp); /* send to merge sorter */
62    
63     done = primlist.pbot->com == PEOF;
64    
65     plfree(&primlist); /* free up array */
66    
67     } while (!done);
68    
69     }
70    
71    
72    
73    
74    
75     /*
76     * The following routine merges up to NFILES sorted primitive files
77     * with 0 or 1 primitive lists. Each set of primitives can end with
78     * 0 or 1 global commands.
79     */
80    
81 schorsch 1.2 void
82     mergesort( /* merge sorted files with list */
83 greg 1.1
84 schorsch 1.2 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 greg 1.1 {
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 schorsch 1.2 static void
147     treemerge( /* merge into one file */
148 greg 1.1
149 schorsch 1.2 int height, int nt, int nf,
150     PLIST *pl,
151     int (*pcmp)(),
152     FILE *ofp
153     )
154 greg 1.1 {
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 schorsch 1.2 static void
195     sendsort( /* send a sorted list */
196 greg 1.1
197 schorsch 1.2 PLIST *pl,
198     int (*pcmp)()
199     )
200 greg 1.1 {
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 schorsch 1.2 static void
251     order( /* order the first n array primitives into list */
252 greg 1.1
253 schorsch 1.2 PRIMITIVE *pa[],
254     int n,
255     PLIST *pl
256     )
257 greg 1.1 {
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 schorsch 1.2 tfname( /* create temporary file name */
274 greg 1.1
275 schorsch 1.2 int lvl, int num
276     )
277 greg 1.1 {
278 schorsch 1.2 static char pathbuf[PATH_MAX];
279 greg 1.1 static char fnbuf[32];
280    
281 schorsch 1.2 /*sprintf(fnbuf, "%sS%d%c%d", TDIR, getpid(), lvl+'A', num);*/
282     sprintf(fnbuf, "%c%d_XXXXXX", lvl+'A', num);
283     temp_filename(pathbuf, sizeof(pathbuf), fnbuf);
284 greg 1.1
285 schorsch 1.2 /*return(fnbuf);*/
286     return pathbuf;
287 greg 1.1 }