ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_usets.c
Revision: 3.4
Committed: Fri Jun 20 00:25:49 2003 UTC (20 years, 9 months ago) by greg
Content type: text/plain
Branch: MAIN
Changes since 3.3: +3 -3 lines
Log Message:
Changed instances of "int4" to "int32" and "int2" to "int16"

File Contents

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