ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_usets.c
Revision: 3.5
Committed: Mon Jun 30 14:59:12 2003 UTC (20 years, 9 months ago) by schorsch
Content type: text/plain
Branch: MAIN
CVS Tags: rad3R6P1, rad3R6
Changes since 3.4: +6 -4 lines
Log Message:
Replaced most outdated BSD function calls with their posix equivalents, and cleaned up a few other platform dependencies.

File Contents

# User Rev Content
1 gwlarson 3.1 #ifndef lint
2 schorsch 3.5 static const char RCSid[] = "$Id: sm_usets.c,v 3.4 2003/06/20 00:25:49 greg Exp $";
3 gwlarson 3.1 #endif
4     /*
5     * Quadtree-specific set operations with unsorted sets.
6     */
7    
8 schorsch 3.5 #include <string.h>
9    
10 gwlarson 3.1 #include "standard.h"
11     #include "sm_flag.h"
12 greg 3.2 #include "object.h"
13 gwlarson 3.1 #include "sm_qtree.h"
14    
15    
16     #define QTSETIBLK 2048 /* set index allocation block size */
17     #define QTELEMBLK 8 /* set element allocation block */
18     #define QTELEMMOD(ne) ((ne)&7) /* (ne) % QTELEMBLK */
19    
20     #define QTONTHRESH(ne) (!QTELEMMOD((ne)+1))
21     #define QTNODESIZ(ne) ((ne) + QTELEMBLK - QTELEMMOD(ne))
22    
23     OBJECT **qtsettab= NULL; /* quadtree leaf node table */
24     QUADTREE qtnumsets=0; /* number of used set indices */
25     static int qtfreesets = EMPTY; /* free set index list */
26 greg 3.4 int32 *qtsetflag = NULL;
27 gwlarson 3.1 static int qtallocsets =0;
28    
29     qtclearsetflags()
30     {
31    
32     if(!qtsetflag)
33     return;
34    
35 schorsch 3.5 memset((char *)qtsetflag, '\0', FLAG_BYTES(qtallocsets));
36 gwlarson 3.1 }
37    
38    
39     QUADTREE
40     qtnewleaf(oset) /* return new leaf node for object set */
41     OBJECT *oset;
42     {
43     register QUADTREE osi;
44    
45     if (*oset <= 0)
46     return(EMPTY); /* should be error? */
47     if (qtfreesets != EMPTY) {
48     osi = qtfreesets;
49     qtfreesets = (int)qtsettab[osi];
50     } else if ((osi = qtnumsets++) % QTSETIBLK == 0) {
51 greg 3.3 qtsettab = (OBJECT **)realloc((void *)qtsettab,
52 gwlarson 3.1 (unsigned)(osi+QTSETIBLK)*sizeof(OBJECT *));
53     if (qtsettab == NULL)
54     goto memerr;
55 greg 3.4 qtsetflag = (int32 *)realloc((void *)qtsetflag,
56 gwlarson 3.1 FLAG_BYTES(osi+ QTSETIBLK));
57     if (qtsetflag == NULL)
58     goto memerr;
59     if(qtallocsets)
60 schorsch 3.5 memset((char *)((char *)(qtsetflag)+FLAG_BYTES(qtallocsets)), '\0',
61 gwlarson 3.1 FLAG_BYTES(osi+QTSETIBLK)-FLAG_BYTES(qtallocsets));
62     else
63 schorsch 3.5 memset((char *)(qtsetflag), '\0', FLAG_BYTES(osi +QTSETIBLK));
64 gwlarson 3.1
65     qtallocsets = osi + QTSETIBLK;
66     }
67     qtsettab[osi] = (OBJECT *)malloc(QTNODESIZ(*oset)*sizeof(OBJECT));
68     if (qtsettab[osi] == NULL)
69     goto memerr;
70     setcopy(qtsettab[osi], oset);
71     return(QT_INDEX(osi));
72     memerr:
73     error(SYSTEM, "out of memory in qtnewleaf\n");
74     }
75    
76    
77 greg 3.2 deletuelem(os, obj) /* delete obj from unsorted os, no questions */
78     register OBJECT *os;
79     OBJECT obj;
80     {
81     register int i,j;
82     OBJECT *optr;
83     /* Take 2nd to last and put in position of obj: move last down:
84     want to preserve last added
85     */
86     i = (*os)--;
87     #ifdef DEBUG
88     if( i <= 0)
89     error(CONSISTENCY,"deleteuelem():empty set\n");
90     #endif
91     if(i < 3)
92     {
93     if((i == 2) && (*(++os) == obj))
94     *os = *(os+1);
95     return;
96     }
97     optr = os + i;
98     os++;
99     while (i-- > 1 && *os != obj)
100     os++;
101     #ifdef DEBUG
102     if( *os != obj)
103     error(CONSISTENCY,"deleteuelem():id not found\n");
104     #endif
105     *os = *(optr-1);
106     *(optr-1) = *optr;
107     }
108    
109     QUADTREE
110     qtdeletuelem(qt, id) /* delete element from unsorted leaf node */
111     QUADTREE qt;
112     OBJECT id;
113     {
114     register QUADTREE lf;
115     #ifdef DEBUG
116     if(id < 0)
117     eputs("qtdeletuelem():Invalid triangle id\n");
118     if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
119     error(CONSISTENCY, "empty/bad node in qtdelelem");
120     #else
121     lf = QT_SET_INDEX(qt);
122     #endif
123     if (qtsettab[lf][0] <= 1) { /* blow leaf away */
124     free((void *)qtsettab[lf]);
125     qtsettab[lf] = (OBJECT *)qtfreesets;
126     qtfreesets = lf;
127     return(EMPTY);
128     }
129     deletuelem(qtsettab[lf], id);
130     if (QTONTHRESH(qtsettab[lf][0]))
131 greg 3.3 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
132 greg 3.2 QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
133     return(qt);
134     }
135 gwlarson 3.1
136     QUADTREE
137     qtdelelem(qt, id) /* delete element from leaf node */
138     QUADTREE qt;
139     OBJECT id;
140     {
141     register QUADTREE lf;
142     #ifdef DEBUG
143     if(id < 0)
144     eputs("qtdelelem():Invalid triangle id\n");
145     if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
146     error(CONSISTENCY, "empty/bad node in qtdelelem");
147     #else
148     lf = QT_SET_INDEX(qt);
149     #endif
150    
151     if (!inset(qtsettab[lf], id))
152     {
153     #ifdef DEBUG
154     eputs("id not in leaf in qtdelelem\n");
155     #endif
156     return(qt);
157     }
158     if (qtsettab[lf][0] <= 1) { /* blow leaf away */
159 greg 3.2 free((void *)qtsettab[lf]);
160 gwlarson 3.1 qtsettab[lf] = (OBJECT *)qtfreesets;
161     qtfreesets = lf;
162     return(EMPTY);
163     }
164     deletelem(qtsettab[lf], id);
165     if (QTONTHRESH(qtsettab[lf][0]))
166 greg 3.3 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
167 gwlarson 3.1 QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
168     return(qt);
169     }
170    
171    
172     QUADTREE
173     qtaddelem(qt, id) /* add element to leaf node */
174     QUADTREE qt;
175     OBJECT id;
176     {
177     OBJECT newset[2];
178     register QUADTREE lf;
179    
180     #ifdef DEBUG
181     if(id < 0)
182     eputs("qtaddelem():Invalid triangle id\n");
183     #endif
184     if (QT_IS_EMPTY(qt)) { /* create new leaf */
185     newset[0] = 1; newset[1] = id;
186     return(qtnewleaf(newset));
187     } /* else add element */
188     #ifdef DEBUG
189     if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
190     error(CONSISTENCY, "bad node in qtaddelem");
191     #else
192     lf = QT_SET_INDEX(qt);
193     #endif
194    
195     if (inset(qtsettab[lf], id))
196     {
197     #ifdef DEBUG
198     eputs("id already in leaf in qtaddelem\n");
199     #endif
200     return(qt);
201     }
202     if (QTONTHRESH(qtsettab[lf][0])) {
203 greg 3.3 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
204 gwlarson 3.1 QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
205     if (qtsettab[lf] == NULL)
206     error(SYSTEM, "out of memory in qtaddelem");
207     }
208     insertelem(qtsettab[lf], id);
209     return(qt);
210     }
211    
212     #define insertuelem(os,id) ((os)[++((os)[0])] = (id))
213    
214     int
215     qtcompressuelem(qt,compress_set)
216     QUADTREE qt;
217     int (*compress_set)();
218     {
219     register QUADTREE lf;
220     int i,j,osize;
221     OBJECT *os;
222    
223     if(QT_IS_EMPTY(qt))
224     return(qt);
225     #ifdef DEBUG
226     if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
227     error(CONSISTENCY, "bad node in qtaddelem");
228     #else
229     lf = QT_SET_INDEX(qt);
230     #endif
231     os = qtsettab[lf];
232     osize = os[0];
233     if((i=compress_set(os)) < osize)
234     {
235 greg 3.3 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
236 gwlarson 3.1 QTNODESIZ(i+1)*sizeof(OBJECT));
237     if (qtsettab[lf] == NULL)
238     error(SYSTEM, "out of memory in qtaddelem");
239     }
240     return(qt);
241     }
242    
243    
244     QUADTREE
245     qtadduelem(qt, id) /* add element to unsorted leaf node */
246     QUADTREE qt;
247     OBJECT id;
248     {
249     OBJECT newset[2];
250     register QUADTREE lf;
251    
252     #ifdef DEBUG
253     if(id < 0)
254 greg 3.2 eputs("qtadduelem():Invalid sample id\n");
255 gwlarson 3.1 #endif
256     if (QT_IS_EMPTY(qt)) { /* create new leaf */
257     newset[0] = 1; newset[1] = id;
258     return(qtnewleaf(newset));
259     } /* else add element */
260     #ifdef DEBUG
261     if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
262     error(CONSISTENCY, "bad node in qtaddelem");
263     #else
264     lf = QT_SET_INDEX(qt);
265     #endif
266     if (QTONTHRESH(qtsettab[lf][0])) {
267 greg 3.3 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
268 gwlarson 3.1 QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
269     if (qtsettab[lf] == NULL)
270     error(SYSTEM, "out of memory in qtaddelem");
271     }
272     insertuelem(qtsettab[lf], id);
273     return(qt);
274     }
275    
276    
277     #ifdef DEBUG
278     OBJECT *
279     qtqueryset(qt) /* return object set for leaf node */
280     QUADTREE qt;
281     {
282     register QUADTREE lf;
283    
284     if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
285     error(CONSISTENCY, "bad node in qtqueryset");
286     return(qtsettab[lf]);
287     }
288     #endif
289    
290     int
291     qtinuset(qt,id)
292     QUADTREE qt;
293     OBJECT id;
294     {
295     OBJECT *os;
296     int i;
297    
298     os = qtqueryset(qt);
299     for(i=os[0],os++; i > 0; i--,os++)
300     if(*os==id)
301     return(1);
302    
303     return(0);
304     }
305    
306    
307     qtfreeleaf(qt) /* free set and leaf node */
308     QUADTREE qt;
309     {
310     register QUADTREE osi;
311    
312     if (!QT_IS_LEAF(qt))
313     return;
314     osi = QT_SET_INDEX(qt);
315     if (osi >= qtnumsets)
316     return;
317 greg 3.2 free((void *)qtsettab[osi]);
318 gwlarson 3.1 qtsettab[osi] = (OBJECT *)qtfreesets;
319     qtfreesets = osi;
320     }
321    
322    
323    
324     qtfreeleaves() /* free ALL sets and leaf nodes */
325     {
326     register int i;
327    
328     while ((i = qtfreesets) != EMPTY) {
329     qtfreesets = (int)qtsettab[i];
330     qtsettab[i] = NULL;
331     }
332     for (i = qtnumsets; i--; )
333     if (qtsettab[i] != NULL)
334 greg 3.2 free((void *)qtsettab[i]);
335     free((void *)qtsettab);
336 gwlarson 3.1 qtsettab = NULL;
337     if(qtsetflag)
338     {
339 greg 3.2 free((void *)qtsetflag);
340 gwlarson 3.1 qtsetflag=0;
341     }
342     qtnumsets = 0;
343     }
344    
345    
346     /* no bounds on os csptr. This routine is conservative: the result returned
347     in os is the set intersection, and therefore is bounded by the size of os.
348     cs is bound to be <= QT_MAXCSET
349     */
350     check_set_large(os, cs) /* modify checked set and set to check */
351     register OBJECT *os; /* os' = os - cs */
352     register OBJECT *cs; /* cs' = cs + os */
353     {
354     OBJECT cset[QT_MAXCSET+1];
355     register int i, j;
356     int k;
357     /* copy os in place, cset <- cs */
358    
359     cset[0] = 0;
360     k = 0;
361     for (i = j = 1; i <= os[0]; i++) {
362     while (j <= cs[0] && cs[j] < os[i])
363     if(cset[0] < QT_MAXCSET)
364     cset[++cset[0]] = cs[j++];
365     else
366     j++;
367     if (j > cs[0] || os[i] != cs[j]) { /* object to check */
368     os[++k] = os[i];
369     if(cset[0] < QT_MAXCSET)
370     cset[++cset[0]] = os[i];
371     }
372     }
373     if (!(os[0] = k)) /* new "to check" set size */
374     return; /* special case */
375    
376     while (j <= cs[0]) /* get the rest of cs */
377     if(cset[0] == QT_MAXCSET)
378     break;
379     else
380     cset[++cset[0]] = cs[j++];
381    
382     os = cset; /* copy cset back to cs */
383     for (i = os[0]; i-- >= 0; )
384     *cs++ = *os++;
385    
386     }
387    
388    
389    
390