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

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id: sm_usets.c,v 3.3 2003/04/23 00:52:34 greg Exp $";
3 #endif
4 /*
5 * Quadtree-specific set operations with unsorted sets.
6 */
7
8 #include "standard.h"
9 #include "sm_flag.h"
10 #include "object.h"
11 #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 int32 *qtsetflag = NULL;
25 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 qtsettab = (OBJECT **)realloc((void *)qtsettab,
50 (unsigned)(osi+QTSETIBLK)*sizeof(OBJECT *));
51 if (qtsettab == NULL)
52 goto memerr;
53 qtsetflag = (int32 *)realloc((void *)qtsetflag,
54 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 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 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
130 QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
131 return(qt);
132 }
133
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 free((void *)qtsettab[lf]);
158 qtsettab[lf] = (OBJECT *)qtfreesets;
159 qtfreesets = lf;
160 return(EMPTY);
161 }
162 deletelem(qtsettab[lf], id);
163 if (QTONTHRESH(qtsettab[lf][0]))
164 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
165 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 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
202 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 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
234 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 eputs("qtadduelem():Invalid sample id\n");
253 #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 qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
266 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 free((void *)qtsettab[osi]);
316 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 free((void *)qtsettab[i]);
333 free((void *)qtsettab);
334 qtsettab = NULL;
335 if(qtsetflag)
336 {
337 free((void *)qtsetflag);
338 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