ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/common/objset.c
Revision: 2.14
Committed: Mon Oct 20 15:10:18 2003 UTC (20 years, 5 months ago) by greg
Content type: text/plain
Branch: MAIN
CVS Tags: rad3R6, rad3R6P1
Changes since 2.13: +2 -2 lines
Log Message:
Fixed inappropriate removal of auxiliary files during build

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id: objset.c,v 2.13 2003/07/21 22:30:17 schorsch Exp $";
3 #endif
4 /*
5 * objset.c - routines for maintaining object sets.
6 *
7 * External symbols declared in object.h
8 */
9
10 #include "copyright.h"
11
12 #include "standard.h"
13
14 #include "octree.h"
15
16 #include "object.h"
17
18 #ifndef OSTSIZ
19 #ifdef SMLMEM
20 #define OSTSIZ 32749 /* object table size (a prime!) */
21 #else
22 #define OSTSIZ 262139 /* object table size (a prime!) */
23 #endif
24 #endif
25
26 static OBJECT *ostable[OSTSIZ]; /* the object set table */
27
28
29 void
30 insertelem(os, obj) /* insert obj into os, no questions */
31 register OBJECT *os;
32 OBJECT obj;
33 {
34 register int i;
35
36 for (i = os[0]++; i > 0; i--)
37 if (os[i] > obj)
38 os[i+1] = os[i];
39 else
40 break;
41 os[i+1] = obj;
42 }
43
44
45 void
46 deletelem(os, obj) /* delete obj from os, no questions */
47 register OBJECT *os;
48 OBJECT obj;
49 {
50 register int i;
51
52 i = (*os)--;
53 os++;
54 while (i > 0 && *os < obj) {
55 i--;
56 os++;
57 }
58 while (--i > 0) {
59 os[0] = os[1];
60 os++;
61 }
62 }
63
64
65 int
66 inset(os, obj) /* determine if object is in set */
67 register OBJECT *os;
68 OBJECT obj;
69 {
70 int upper, lower;
71 register int cm, i;
72
73 if ((i = os[0]) <= 6) { /* linear search algorithm */
74 cm = obj;
75 while (i-- > 0)
76 if (*++os == cm)
77 return(1);
78 return(0);
79 }
80 lower = 1;
81 upper = cm = i + 1;
82 /* binary search algorithm */
83 while ((i = (lower + upper) >> 1) != cm) {
84 cm = obj - os[i];
85 if (cm > 0)
86 lower = i;
87 else if (cm < 0)
88 upper = i;
89 else
90 return(1);
91 cm = i;
92 }
93 return(0);
94 }
95
96
97 int
98 setequal(os1, os2) /* determine if two sets are equal */
99 register OBJECT *os1, *os2;
100 {
101 register int i;
102
103 for (i = *os1; i-- >= 0; )
104 if (*os1++ != *os2++)
105 return(0);
106 return(1);
107 }
108
109
110 void
111 setcopy(os1, os2) /* copy object set os2 into os1 */
112 register OBJECT *os1, *os2;
113 {
114 register int i;
115
116 for (i = *os2; i-- >= 0; )
117 *os1++ = *os2++;
118 }
119
120
121 OBJECT *
122 setsave(os) /* allocate space and save set */
123 register OBJECT *os;
124 {
125 OBJECT *osnew;
126 register OBJECT *oset;
127 register int i;
128
129 if ((osnew = oset = (OBJECT *)malloc((*os+1)*sizeof(OBJECT))) == NULL)
130 error(SYSTEM, "out of memory in setsave\n");
131 for (i = *os; i-- >= 0; ) /* inline setcopy */
132 *oset++ = *os++;
133 return(osnew);
134 }
135
136
137 void
138 setunion(osr, os1, os2) /* osr = os1 Union os2 */
139 register OBJECT *osr, *os1, *os2;
140 {
141 register int i1, i2;
142
143 osr[0] = 0;
144 for (i1 = i2 = 1; i1 <= os1[0] || i2 <= os2[0]; ) {
145 while (i1 <= os1[0] && (i2 > os2[0] || os1[i1] <= os2[i2])) {
146 osr[++osr[0]] = os1[i1];
147 if (i2 <= os2[0] && os2[i2] == os1[i1])
148 i2++;
149 i1++;
150 }
151 while (i2 <= os2[0] && (i1 > os1[0] || os2[i2] < os1[i1]))
152 osr[++osr[0]] = os2[i2++];
153 }
154 }
155
156
157 void
158 setintersect(osr, os1, os2) /* osr = os1 Intersect os2 */
159 register OBJECT *osr, *os1, *os2;
160 {
161 register int i1, i2;
162
163 osr[0] = 0;
164 if (os1[0] <= 0)
165 return;
166 for (i1 = i2 = 1; i2 <= os2[0]; ) {
167 while (os1[i1] < os2[i2])
168 if (++i1 > os1[0])
169 return;
170 while (os2[i2] < os1[i1])
171 if (++i2 > os2[0])
172 return;
173 if (os1[i1] == os2[i2])
174 osr[++osr[0]] = os2[i2++];
175 }
176 }
177
178
179 OCTREE
180 fullnode(oset) /* return octree for object set */
181 OBJECT *oset;
182 {
183 int osentry, ntries;
184 long hval;
185 OCTREE ot;
186 register int i;
187 register OBJECT *os;
188 /* hash on set */
189 hval = 0;
190 os = oset;
191 i = *os++;
192 while (i-- > 0)
193 hval += *os++;
194 ntries = 0;
195 tryagain:
196 osentry = (hval + (long)ntries*ntries) % OSTSIZ;
197 os = ostable[osentry];
198 if (os == NULL) {
199 os = ostable[osentry] = (OBJECT *)malloc(
200 (unsigned)(oset[0]+2)*sizeof(OBJECT));
201 if (os == NULL)
202 goto memerr;
203 ot = oseti(osentry);
204 } else {
205 /* look for set */
206 for (i = 0; *os > 0; i++, os += *os + 1)
207 if (setequal(os, oset))
208 break;
209 ot = oseti(i*OSTSIZ + osentry);
210 if (*os > 0) /* found it */
211 return(ot);
212 if (!isfull(ot)) { /* entry overflow */
213 if (++ntries < OSTSIZ)
214 goto tryagain;
215 else
216 error(INTERNAL, "hash table overflow in fullnode");
217 }
218 /* remember position */
219 i = os - ostable[osentry];
220 os = ostable[osentry] = (OBJECT *)realloc(
221 (void *)ostable[osentry],
222 (unsigned)(i+oset[0]+2)*sizeof(OBJECT));
223 if (os == NULL)
224 goto memerr;
225 os += i; /* last entry */
226 }
227 setcopy(os, oset); /* add new set */
228 os += *os + 1;
229 *os = 0; /* terminator */
230 return(ot);
231 memerr:
232 error(SYSTEM, "out of memory in fullnode");
233 return 0; /* pro forma return */
234 }
235
236
237 void
238 objset(oset, ot) /* get object set for full node */
239 register OBJECT *oset;
240 OCTREE ot;
241 {
242 register OBJECT *os;
243 register int i;
244
245 if (!isfull(ot))
246 goto noderr;
247 ot = oseti(ot);
248 if ((os = ostable[ot%OSTSIZ]) == NULL)
249 goto noderr;
250 for (i = ot/OSTSIZ; i--; os += *os + 1)
251 if (*os <= 0)
252 goto noderr;
253 for (i = *os; i-- >= 0; ) /* copy set here */
254 *oset++ = *os++;
255 return;
256 noderr:
257 error(CONSISTENCY, "bad node in objset");
258 }
259
260
261 int
262 dosets(f) /* loop through all sets */
263 int (*f)();
264 {
265 int res = 0;
266 int n;
267 register OBJECT *os;
268
269 for (n = 0; n < OSTSIZ; n++) {
270 if ((os = ostable[n]) == NULL)
271 continue;
272 while (*os > 0) {
273 res += (*f)(os);
274 os += *os + 1;
275 }
276 }
277 return(res);
278 }
279
280
281 void
282 donesets() /* free ALL SETS in our table */
283 {
284 register int n;
285
286 for (n = 0; n < OSTSIZ; n++)
287 if (ostable[n] != NULL) {
288 free((void *)ostable[n]);
289 ostable[n] = NULL;
290 }
291 }