ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/common/objset.c
(Generate patch)

Comparing ray/src/common/objset.c (file contents):
Revision 2.2 by greg, Thu Mar 12 11:41:18 1992 UTC vs.
Revision 2.18 by greg, Sat Mar 18 15:21:17 2023 UTC

# Line 1 | Line 1
1 – /* Copyright (c) 1986 Regents of the University of California */
2 –
1   #ifndef lint
2 < static char SCCSid[] = "$SunId$ LBL";
2 > static const char       RCSid[] = "$Id$";
3   #endif
6 –
4   /*
5   *  objset.c - routines for maintaining object sets.
6   *
7 < *      7/28/85
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  
19 – #include  "otypes.h"
20 –
18   #ifndef  OSTSIZ
19 < #ifdef  BIGMEM
20 < #define  OSTSIZ         56437           /* object table size (a prime!) */
19 > #ifdef  SMLMEM
20 > #define  OSTSIZ         32749           /* object table size (a prime!) */
21   #else
22 < #define  OSTSIZ         12329           /* object table size (a prime!) */
22 > #define  OSTSIZ         1002583         /* object table size (a prime!) */
23   #endif
24   #endif
25  
26 + #undef xtra_long
27 + #ifdef _WIN64
28 + typedef unsigned long long int  xtra_long;
29 + #else
30 + typedef unsigned long int       xtra_long;
31 + #endif
32 +
33   static OBJECT  *ostable[OSTSIZ];        /* the object set table */
34  
35  
36 < insertelem(os, obj)             /* insert obj into os, no questions */
37 < register OBJECT  *os;
38 < OBJECT  obj;
36 > void
37 > insertelem(                     /* insert obj into os, no questions */
38 >        OBJECT  *os,
39 >        OBJECT  obj
40 > )
41   {
42 <        register int  i;
42 >        int  i;
43          
44          for (i = os[0]++; i > 0; i--)
45                  if (os[i] > obj)
# Line 44 | Line 50 | OBJECT  obj;
50   }
51  
52  
53 < deletelem(os, obj)              /* delete obj from os, no questions */
54 < register OBJECT  *os;
55 < OBJECT  obj;
53 > void
54 > deletelem(                      /* delete obj from os, no questions */
55 >        OBJECT  *os,
56 >        OBJECT  obj
57 > )
58   {
59 <        register int  i;
59 >        int  i;
60  
61          i = (*os)--;
62          os++;
# Line 63 | Line 71 | OBJECT  obj;
71   }
72  
73  
74 < inset(os, obj)                  /* determine if object is in set */
75 < register OBJECT  *os;
76 < OBJECT  obj;
74 > int
75 > inset(                          /* determine if object is in set */
76 >        OBJECT  *os,
77 >        OBJECT  obj
78 > )
79   {
80          int  upper, lower;
81 <        register int  cm, i;
81 >        int  cm, i;
82  
83 +        if ((i = os[0]) <= 12) {        /* linear search algorithm */
84 +                cm = obj;
85 +                while (i-- > 0)
86 +                        if (*++os == cm)
87 +                                return(1);
88 +                return(0);
89 +        }
90          lower = 1;
91 <        upper = cm = os[0] + 1;
92 <
91 >        upper = cm = i + 1;
92 >                                        /* binary search algorithm */
93          while ((i = (lower + upper) >> 1) != cm) {
94                  cm = obj - os[i];
95                  if (cm > 0)
# Line 87 | Line 104 | OBJECT  obj;
104   }
105  
106  
107 < setequal(os1, os2)              /* determine if two sets are equal */
108 < register OBJECT  *os1, *os2;
107 > int
108 > setequal(                       /* determine if two sets are equal */
109 >        OBJECT  *os1,
110 >        OBJECT  *os2
111 > )
112   {
113 <        register int  i;
113 >        int  i;
114  
115          for (i = *os1; i-- >= 0; )
116                  if (*os1++ != *os2++)
# Line 99 | Line 119 | register OBJECT  *os1, *os2;
119   }
120  
121  
122 < setcopy(os1, os2)               /* copy object set os2 into os1 */
123 < register OBJECT  *os1, *os2;
122 > void
123 > setcopy(                        /* copy object set os2 into os1 */
124 >        OBJECT  *os1,
125 >        OBJECT  *os2
126 > )
127   {
128 <        register int  i;
128 >        int  i;
129  
130          for (i = *os2; i-- >= 0; )
131                  *os1++ = *os2++;
132   }
133  
134  
135 + OBJECT *
136 + setsave(                        /* allocate space and save set */
137 +        OBJECT  *os
138 + )
139 + {
140 +        OBJECT  *osnew;
141 +        OBJECT  *oset;
142 +        int  i;
143 +
144 +        if ((osnew = oset = (OBJECT *)malloc((*os+1)*sizeof(OBJECT))) == NULL)
145 +                error(SYSTEM, "out of memory in setsave\n");
146 +        for (i = *os; i-- >= 0; )       /* inline setcopy */
147 +                *oset++ = *os++;
148 +        return(osnew);
149 + }
150 +
151 +
152 + void
153 + setunion(                       /* osr = os1 Union os2 */
154 +        OBJECT  *osr,
155 +        OBJECT  *os1,
156 +        OBJECT  *os2
157 + )
158 + {
159 +        int     i1, i2;
160 +
161 +        osr[0] = 0;
162 +        for (i1 = i2 = 1; i1 <= os1[0] || i2 <= os2[0]; ) {
163 +                while (i1 <= os1[0] && (i2 > os2[0] || os1[i1] <= os2[i2])) {
164 +                        osr[++osr[0]] = os1[i1];
165 +                        if (i2 <= os2[0] && os2[i2] == os1[i1])
166 +                                i2++;
167 +                        i1++;
168 +                }
169 +                while (i2 <= os2[0] && (i1 > os1[0] || os2[i2] < os1[i1]))
170 +                        osr[++osr[0]] = os2[i2++];
171 +        }
172 + }
173 +
174 +
175 + void
176 + setintersect(                   /* osr = os1 Intersect os2 */
177 +        OBJECT  *osr,
178 +        OBJECT  *os1,
179 +        OBJECT  *os2
180 + )
181 + {
182 +        int     i1, i2;
183 +
184 +        osr[0] = 0;
185 +        if (os1[0] <= 0)
186 +                return;
187 +        for (i1 = i2 = 1; i2 <= os2[0]; ) {
188 +                while (os1[i1] < os2[i2])
189 +                        if (++i1 > os1[0])
190 +                                return;
191 +                while (os2[i2] < os1[i1])
192 +                        if (++i2 > os2[0])
193 +                                return;
194 +                if (os1[i1] == os2[i2])
195 +                        osr[++osr[0]] = os2[i2++];
196 +        }
197 + }
198 +
199 +
200   OCTREE
201 < fullnode(oset)                  /* return octree for object set */
202 < OBJECT  *oset;
201 > fullnode(                       /* return octree for object set */
202 >        OBJECT  *oset
203 > )
204   {
205 <        int  osentry, ntries;
206 <        long  hval;
205 >        unsigned int  ntries;
206 >        xtra_long  hval;
207          OCTREE  ot;
208 <        register int  i;
209 <        register OBJECT  *os;
208 >        int  osentry, i;
209 >        OBJECT  *os;
210                                          /* hash on set */
211          hval = 0;
212          os = oset;
# Line 126 | Line 215 | OBJECT  *oset;
215                  hval += *os++;
216          ntries = 0;
217   tryagain:
218 <        osentry = (hval + (long)ntries*ntries) % OSTSIZ;
218 >        osentry = (hval + (xtra_long)ntries*ntries) % OSTSIZ;
219          os = ostable[osentry];
220          if (os == NULL) {
221                  os = ostable[osentry] = (OBJECT *)malloc(
# Line 142 | Line 231 | tryagain:
231                  ot = oseti(i*OSTSIZ + osentry);
232                  if (*os > 0)                    /* found it */
233                          return(ot);
234 <                if (!isfull(ot))                /* entry overflow */
234 >                if (!isfull(ot)) {              /* entry overflow */
235                          if (++ntries < OSTSIZ)
236                                  goto tryagain;
237                          else
238                                  error(INTERNAL, "hash table overflow in fullnode");
239 +                }
240                                                  /* remember position */
241                  i = os - ostable[osentry];
242                  os = ostable[osentry] = (OBJECT *)realloc(
243 <                                (char *)ostable[osentry],
243 >                                (void *)ostable[osentry],
244                                  (unsigned)(i+oset[0]+2)*sizeof(OBJECT));
245                  if (os == NULL)
246                          goto memerr;
# Line 162 | Line 252 | tryagain:
252          return(ot);
253   memerr:
254          error(SYSTEM, "out of memory in fullnode");
255 +        return 0; /* pro forma return */
256   }
257  
258  
259 < objset(oset, ot)                /* get object set for full node */
260 < register OBJECT  *oset;
261 < OCTREE  ot;
259 > void
260 > objset(                 /* get object set for full node */
261 >        OBJECT  *oset,
262 >        OCTREE  ot
263 > )
264   {
265 <        register OBJECT  *os;
266 <        register int  i;
265 >        OBJECT  *os;
266 >        int  i;
267  
268          if (!isfull(ot))
269                  goto noderr;
270 <        i = oseti(ot);
271 <        if ((os = ostable[i%OSTSIZ]) == NULL)
270 >        ot = oseti(ot);
271 >        if ((os = ostable[ot%OSTSIZ]) == NULL)
272                  goto noderr;
273 <        for (i /= OSTSIZ; i--; os += *os + 1)
273 >        for (i = ot/OSTSIZ; i--; os += *os + 1)
274                  if (*os <= 0)
275                          goto noderr;
276          for (i = *os; i-- >= 0; )               /* copy set here */
# Line 188 | Line 281 | noderr:
281   }
282  
283  
284 < nonsurfinset(orig, nobjs)               /* check sets for non-surfaces */
285 < int  orig, nobjs;
284 > void
285 > donesets(void)                  /* free ALL SETS in our table */
286   {
287          int  n;
195 –        register OBJECT  *os;
196 –        register OBJECT  i, s;
288  
289 <        for (n = 0; n < OSTSIZ; n++) {
290 <                if ((os = ostable[n]) == NULL)
291 <                        continue;
292 <                while ((i = *os++) > 0)
293 <                        while (i--) {
203 <                                s = *os;
204 <                                if (s >= orig && s < orig+nobjs &&
205 <                                                ismodifier(objptr(s)->otype))
206 <                                        return(1);
207 <                                os++;
208 <                        }
209 <        }
210 <        return(0);
289 >        for (n = 0; n < OSTSIZ; n++)
290 >                if (ostable[n] != NULL) {
291 >                        free((void *)ostable[n]);
292 >                        ostable[n] = NULL;
293 >                }
294   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines