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 (21 years, 1 month 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

# User Rev Content
1 greg 1.1 #ifndef lint
2 schorsch 1.8 static const char RCSid[] = "$Id: sort.c,v 1.7 2003/10/21 19:19:28 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 schorsch 1.8 int minf = 0;
96 greg 1.1 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    
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 schorsch 1.3 static char fnbuf[PATH_MAX];
280     static size_t psiz;
281 greg 1.1
282 schorsch 1.3 if (pathbuf[0] == '\0') { /* first time */
283     temp_directory(pathbuf, sizeof(pathbuf));
284     psiz = strlen(pathbuf);
285     }
286 schorsch 1.4 snprintf(fnbuf, sizeof(pathbuf)-psiz,
287 schorsch 1.3 "%s/S%d%c%d", pathbuf, getpid(), lvl+'A', num);
288 schorsch 1.2 /*sprintf(fnbuf, "%sS%d%c%d", TDIR, getpid(), lvl+'A', num);*/
289 greg 1.1
290 schorsch 1.3 return(fnbuf);
291 greg 1.1 }