ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/Development/ray/src/common/objset.c

Comparing ray/src/common/objset.c (file contents):
Revision 2.4 by greg, Fri Mar 7 15:45:28 1997 UTC vs.
Revision 2.17 by greg, Tue Apr 28 16:56:10 2015 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"
#	Line 17 | Line 16 | static char SCCSid[] = "$SunId$ LBL";
16		#include  "object.h"
17
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         262139          /* 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 42 | 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 61 | 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;
91	>	upper = cm = i + 1;
92		/* binary search algorithm */
93		while ((i = (lower + upper) >> 1) != cm) {
94		cm = obj - os[i];
#	Line 85 | 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 97 | 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++;
#	Line 108 | Line 133 | register OBJECT  *os1, *os2;
133
134
135		OBJECT *
136	<	setsave(os)                     /* allocate space and save set */
137	<	register OBJECT  *os;
136	>	setsave(                        /* allocate space and save set */
137	>	OBJECT  *os
138	>	)
139		{
140		OBJECT  *osnew;
141	<	register OBJECT  *oset;
142	<	register int  i;
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");
#	Line 123 | Line 149 | register OBJECT  *os;
149		}
150
151
152	<	setunion(osr, os1, os2)         /* osr = os1 Union os2 */
153	<	register OBJECT  *osr, *os1, *os2;
152	>	void
153	>	setunion(                       /* osr = os1 Union os2 */
154	>	OBJECT  *osr,
155	>	OBJECT  *os1,
156	>	OBJECT  *os2
157	>	)
158		{
159	<	register int    i1, i2;
159	>	int     i1, i2;
160
161		osr[0] = 0;
162		for (i1 = i2 = 1; i1 <= os1[0] || i2 <= os2[0]; ) {
#	Line 142 | Line 172 | register OBJECT  *osr, *os1, *os2;
172		}
173
174
175	<	setintersect(osr, os1, os2)     /* osr = os1 Intersect os2 */
176	<	register OBJECT  *osr, *os1, *os2;
175	>	void
176	>	setintersect(                   /* osr = os1 Intersect os2 */
177	>	OBJECT  *osr,
178	>	OBJECT  *os1,
179	>	OBJECT  *os2
180	>	)
181		{
182	<	register int    i1, i2;
182	>	int     i1, i2;
183
184		osr[0] = 0;
185		if (os1[0] <= 0)
#	Line 164 | Line 198 | register OBJECT  *osr, *os1, *os2;
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 180 | 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 196 | 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 216 | 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 242 | Line 281 | noderr:
281		}
282
283
284	<	int
285	<	dosets(f)                               /* loop through all sets */
247	<	int     (*f)();
284	>	void
285	>	donesets(void)                  /* free ALL SETS in our table */
286		{
249	–	int  res = 0;
287		int  n;
251	–	register OBJECT  *os;
288
253	–	for (n = 0; n < OSTSIZ; n++) {
254	–	if ((os = ostable[n]) == NULL)
255	–	continue;
256	–	while (*os > 0) {
257	–	res += (*f)(os);
258	–	os += *os + 1;
259	–	}
260	–	}
261	–	return(res);
262	–	}
263	–
264	–
265	–	donesets()                      /* free ALL SETS in our table */
266	–	{
267	–	register int  n;
268	–
289		for (n = 0; n < OSTSIZ; n++)
290		if (ostable[n] != NULL) {
291	<	free((char *)ostable[n]);
291	>	free((void *)ostable[n]);
292		ostable[n] = NULL;
293		}
294		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines (old)
>	Changed lines (new)