src/common/objset.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 *  objset.c - routines for maintaining object sets.
 *
 *  External symbols declared in object.h
 */

/* ====================================================================
 * The Radiance Software License, Version 1.0
 *
 * Copyright (c) 1990 - 2002 The Regents of the University of California,
 * through Lawrence Berkeley National Laboratory.   All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *         notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *           if any, must include the following acknowledgment:
 *             "This product includes Radiance software
 *                 (http://radsite.lbl.gov/)
 *                 developed by the Lawrence Berkeley National Laboratory
 *               (http://www.lbl.gov/)."
 *       Alternately, this acknowledgment may appear in the software itself,
 *       if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
 *       and "The Regents of the University of California" must
 *       not be used to endorse or promote products derived from this
 *       software without prior written permission. For written
 *       permission, please contact [email protected].
 *
 * 5. Products derived from this software may not be called "Radiance",
 *       nor may "Radiance" appear in their name, without prior written
 *       permission of Lawrence Berkeley National Laboratory.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.   IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of Lawrence Berkeley National Laboratory.   For more
 * information on Lawrence Berkeley National Laboratory, please see
 * <http://www.lbl.gov/>.
 */

#include  "standard.h"

#include  "octree.h"

#include  "object.h"

#ifndef  OSTSIZ
#ifdef  BIGMEM
#define  OSTSIZ         262139          /* object table size (a prime!) */
#else
#define  OSTSIZ         32749           /* object table size (a prime!) */
#endif
#endif

static OBJECT  *ostable[OSTSIZ];        /* the object set table */


void
insertelem(os, obj)             /* insert obj into os, no questions */
register OBJECT  *os;
OBJECT  obj;
{
        register int  i;
        
        for (i = os[0]++; i > 0; i--)
                if (os[i] > obj)
                        os[i+1] = os[i];
                else
                        break;
        os[i+1] = obj;
}


void
deletelem(os, obj)              /* delete obj from os, no questions */
register OBJECT  *os;
OBJECT  obj;
{
        register int  i;

        i = (*os)--;
        os++;
        while (i > 0 && *os < obj) {
                i--;
                os++;
        }
        while (--i > 0) {
                os[0] = os[1];
                os++;
        }
}


int
inset(os, obj)                  /* determine if object is in set */
register OBJECT  *os;
OBJECT  obj;
{
        int  upper, lower;
        register int  cm, i;

        if ((i = os[0]) <= 6) {         /* linear search algorithm */
                cm = obj;
                while (i-- > 0)
                        if (*++os == cm)
                                return(1);
                return(0);
        }
        lower = 1;
        upper = cm = i + 1;
                                        /* binary search algorithm */
        while ((i = (lower + upper) >> 1) != cm) {
                cm = obj - os[i];
                if (cm > 0)
                        lower = i;
                else if (cm < 0)
                        upper = i;
                else
                        return(1);
                cm = i;
        }
        return(0);
}


int
setequal(os1, os2)              /* determine if two sets are equal */
register OBJECT  *os1, *os2;
{
        register int  i;

        for (i = *os1; i-- >= 0; )
                if (*os1++ != *os2++)
                        return(0);
        return(1);
}


void
setcopy(os1, os2)               /* copy object set os2 into os1 */
register OBJECT  *os1, *os2;
{
        register int  i;

        for (i = *os2; i-- >= 0; )
                *os1++ = *os2++;
}


OBJECT *
setsave(os)                     /* allocate space and save set */
register OBJECT  *os;
{
        OBJECT  *osnew;
        register OBJECT  *oset;
        register int  i;

        if ((osnew = oset = (OBJECT *)malloc((*os+1)*sizeof(OBJECT))) == NULL)
                error(SYSTEM, "out of memory in setsave\n");
        for (i = *os; i-- >= 0; )       /* inline setcopy */
                *oset++ = *os++;
        return(osnew);
}


void
setunion(osr, os1, os2)         /* osr = os1 Union os2 */
register OBJECT  *osr, *os1, *os2;
{
        register int    i1, i2;

        osr[0] = 0;
        for (i1 = i2 = 1; i1 <= os1[0] || i2 <= os2[0]; ) {
                while (i1 <= os1[0] && (i2 > os2[0] || os1[i1] <= os2[i2])) {
                        osr[++osr[0]] = os1[i1];
                        if (i2 <= os2[0] && os2[i2] == os1[i1])
                                i2++;
                        i1++;
                }
                while (i2 <= os2[0] && (i1 > os1[0] || os2[i2] < os1[i1]))
                        osr[++osr[0]] = os2[i2++];
        }
}


void
setintersect(osr, os1, os2)     /* osr = os1 Intersect os2 */
register OBJECT  *osr, *os1, *os2;
{
        register int    i1, i2;

        osr[0] = 0;
        if (os1[0] <= 0)
                return;
        for (i1 = i2 = 1; i2 <= os2[0]; ) {
                while (os1[i1] < os2[i2])
                        if (++i1 > os1[0])
                                return;
                while (os2[i2] < os1[i1])
                        if (++i2 > os2[0])
                                return;
                if (os1[i1] == os2[i2])
                        osr[++osr[0]] = os2[i2++];
        }
}


OCTREE
fullnode(oset)                  /* return octree for object set */
OBJECT  *oset;
{
        int  osentry, ntries;
        long  hval;
        OCTREE  ot;
        register int  i;
        register OBJECT  *os;
                                        /* hash on set */
        hval = 0;
        os = oset;
        i = *os++;
        while (i-- > 0)
                hval += *os++;
        ntries = 0;
tryagain:
        osentry = (hval + (long)ntries*ntries) % OSTSIZ;
        os = ostable[osentry];
        if (os == NULL) {
                os = ostable[osentry] = (OBJECT *)malloc(
                                (unsigned)(oset[0]+2)*sizeof(OBJECT));
                if (os == NULL)
                        goto memerr;
                ot = oseti(osentry);
        } else {
                                                /* look for set */
                for (i = 0; *os > 0; i++, os += *os + 1)
                        if (setequal(os, oset))
                                break;
                ot = oseti(i*OSTSIZ + osentry);
                if (*os > 0)                    /* found it */
                        return(ot);
                if (!isfull(ot))                /* entry overflow */
                        if (++ntries < OSTSIZ)
                                goto tryagain;
                        else
                                error(INTERNAL, "hash table overflow in fullnode");
                                                /* remember position */
                i = os - ostable[osentry];
                os = ostable[osentry] = (OBJECT *)realloc(
                                (char *)ostable[osentry],
                                (unsigned)(i+oset[0]+2)*sizeof(OBJECT));
                if (os == NULL)
                        goto memerr;
                os += i;                        /* last entry */
        }
        setcopy(os, oset);              /* add new set */
        os += *os + 1;
        *os = 0;                        /* terminator */
        return(ot);
memerr:
        error(SYSTEM, "out of memory in fullnode");
}


void
objset(oset, ot)                /* get object set for full node */
register OBJECT  *oset;
OCTREE  ot;
{
        register OBJECT  *os;
        register int  i;

        if (!isfull(ot))
                goto noderr;
        ot = oseti(ot);
        if ((os = ostable[ot%OSTSIZ]) == NULL)
                goto noderr;
        for (i = ot/OSTSIZ; i--; os += *os + 1)
                if (*os <= 0)
                        goto noderr;
        for (i = *os; i-- >= 0; )               /* copy set here */
                *oset++ = *os++;
        return;
noderr:
        error(CONSISTENCY, "bad node in objset");
}


int
dosets(f)                               /* loop through all sets */
int     (*f)();
{
        int  res = 0;
        int  n;
        register OBJECT  *os;

        for (n = 0; n < OSTSIZ; n++) {
                if ((os = ostable[n]) == NULL)
                        continue;
                while (*os > 0) {
                        res += (*f)(os);
                        os += *os + 1;
                }
        }
        return(res);
}


void
donesets()                      /* free ALL SETS in our table */
{
        register int  n;

        for (n = 0; n < OSTSIZ; n++) 
                if (ostable[n] != NULL) {
                        free((void *)ostable[n]);
                        ostable[n] = NULL;
                }
}
Revision:	2.8
Committed:	Sat Feb 22 02:07:22 2003 UTC (21 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.7:	+69 -6 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	Content
1	#ifndef lint
2	static const char RCSid[] = "$Id$";
3	#endif
4	/*
5	* objset.c - routines for maintaining object sets.
6	*
7	* External symbols declared in object.h
8	*/
9
10	/* ====================================================================
11	* The Radiance Software License, Version 1.0
12	*
13	* Copyright (c) 1990 - 2002 The Regents of the University of California,
14	* through Lawrence Berkeley National Laboratory. All rights reserved.
15	*
16	* Redistribution and use in source and binary forms, with or without
17	* modification, are permitted provided that the following conditions
18	* are met:
19	*
20	* 1. Redistributions of source code must retain the above copyright
21	* notice, this list of conditions and the following disclaimer.
22	*
23	* 2. Redistributions in binary form must reproduce the above copyright
24	* notice, this list of conditions and the following disclaimer in
25	* the documentation and/or other materials provided with the
26	* distribution.
27	*
28	* 3. The end-user documentation included with the redistribution,
29	* if any, must include the following acknowledgment:
30	* "This product includes Radiance software
31	* (http://radsite.lbl.gov/)
32	* developed by the Lawrence Berkeley National Laboratory
33	* (http://www.lbl.gov/)."
34	* Alternately, this acknowledgment may appear in the software itself,
35	* if and wherever such third-party acknowledgments normally appear.
36	*
37	* 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
38	* and "The Regents of the University of California" must
39	* not be used to endorse or promote products derived from this
40	* software without prior written permission. For written
41	* permission, please contact [email protected].
42	*
43	* 5. Products derived from this software may not be called "Radiance",
44	* nor may "Radiance" appear in their name, without prior written
45	* permission of Lawrence Berkeley National Laboratory.
46	*
47	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
48	* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
49	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
50	* DISCLAIMED. IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
51	* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
52	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
53	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
54	* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
55	* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
56	* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
57	* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
58	* SUCH DAMAGE.
59	* ====================================================================
60	*
61	* This software consists of voluntary contributions made by many
62	* individuals on behalf of Lawrence Berkeley National Laboratory. For more
63	* information on Lawrence Berkeley National Laboratory, please see
64	* <http://www.lbl.gov/>.
65	*/
66
67	#include "standard.h"
68
69	#include "octree.h"
70
71	#include "object.h"
72
73	#ifndef OSTSIZ
74	#ifdef BIGMEM
75	#define OSTSIZ 262139 /* object table size (a prime!) */
76	#else
77	#define OSTSIZ 32749 /* object table size (a prime!) */
78	#endif
79	#endif
80
81	static OBJECT ostable[OSTSIZ]; / the object set table */
82
83
84	void
85	insertelem(os, obj) /* insert obj into os, no questions */
86	register OBJECT *os;
87	OBJECT obj;
88	{
89	register int i;
90
91	for (i = os[0]++; i > 0; i--)
92	if (os[i] > obj)
93	os[i+1] = os[i];
94	else
95	break;
96	os[i+1] = obj;
97	}
98
99
100	void
101	deletelem(os, obj) /* delete obj from os, no questions */
102	register OBJECT *os;
103	OBJECT obj;
104	{
105	register int i;
106
107	i = (*os)--;
108	os++;
109	while (i > 0 && *os < obj) {
110	i--;
111	os++;
112	}
113	while (--i > 0) {
114	os[0] = os[1];
115	os++;
116	}
117	}
118
119
120	int
121	inset(os, obj) /* determine if object is in set */
122	register OBJECT *os;
123	OBJECT obj;
124	{
125	int upper, lower;
126	register int cm, i;
127
128	if ((i = os[0]) <= 6) { /* linear search algorithm */
129	cm = obj;
130	while (i-- > 0)
131	if (*++os == cm)
132	return(1);
133	return(0);
134	}
135	lower = 1;
136	upper = cm = i + 1;
137	/* binary search algorithm */
138	while ((i = (lower + upper) >> 1) != cm) {
139	cm = obj - os[i];
140	if (cm > 0)
141	lower = i;
142	else if (cm < 0)
143	upper = i;
144	else
145	return(1);
146	cm = i;
147	}
148	return(0);
149	}
150
151
152	int
153	setequal(os1, os2) /* determine if two sets are equal */
154	register OBJECT os1, os2;
155	{
156	register int i;
157
158	for (i = *os1; i-- >= 0; )
159	if (os1++ != os2++)
160	return(0);
161	return(1);
162	}
163
164
165	void
166	setcopy(os1, os2) /* copy object set os2 into os1 */
167	register OBJECT os1, os2;
168	{
169	register int i;
170
171	for (i = *os2; i-- >= 0; )
172	os1++ = os2++;
173	}
174
175
176	OBJECT *
177	setsave(os) /* allocate space and save set */
178	register OBJECT *os;
179	{
180	OBJECT *osnew;
181	register OBJECT *oset;
182	register int i;
183
184	if ((osnew = oset = (OBJECT )malloc((os+1)*sizeof(OBJECT))) == NULL)
185	error(SYSTEM, "out of memory in setsave\n");
186	for (i = os; i-- >= 0; ) / inline setcopy */
187	oset++ = os++;
188	return(osnew);
189	}
190
191
192	void
193	setunion(osr, os1, os2) /* osr = os1 Union os2 */
194	register OBJECT osr, os1, *os2;
195	{
196	register int i1, i2;
197
198	osr[0] = 0;
199	for (i1 = i2 = 1; i1 <= os1[0] \|\| i2 <= os2[0]; ) {
200	while (i1 <= os1[0] && (i2 > os2[0] \|\| os1[i1] <= os2[i2])) {
201	osr[++osr[0]] = os1[i1];
202	if (i2 <= os2[0] && os2[i2] == os1[i1])
203	i2++;
204	i1++;
205	}
206	while (i2 <= os2[0] && (i1 > os1[0] \|\| os2[i2] < os1[i1]))
207	osr[++osr[0]] = os2[i2++];
208	}
209	}
210
211
212	void
213	setintersect(osr, os1, os2) /* osr = os1 Intersect os2 */
214	register OBJECT osr, os1, *os2;
215	{
216	register int i1, i2;
217
218	osr[0] = 0;
219	if (os1[0] <= 0)
220	return;
221	for (i1 = i2 = 1; i2 <= os2[0]; ) {
222	while (os1[i1] < os2[i2])
223	if (++i1 > os1[0])
224	return;
225	while (os2[i2] < os1[i1])
226	if (++i2 > os2[0])
227	return;
228	if (os1[i1] == os2[i2])
229	osr[++osr[0]] = os2[i2++];
230	}
231	}
232
233
234	OCTREE
235	fullnode(oset) /* return octree for object set */
236	OBJECT *oset;
237	{
238	int osentry, ntries;
239	long hval;
240	OCTREE ot;
241	register int i;
242	register OBJECT *os;
243	/* hash on set */
244	hval = 0;
245	os = oset;
246	i = *os++;
247	while (i-- > 0)
248	hval += *os++;
249	ntries = 0;
250	tryagain:
251	osentry = (hval + (long)ntries*ntries) % OSTSIZ;
252	os = ostable[osentry];
253	if (os == NULL) {
254	os = ostable[osentry] = (OBJECT *)malloc(
255	(unsigned)(oset[0]+2)*sizeof(OBJECT));
256	if (os == NULL)
257	goto memerr;
258	ot = oseti(osentry);
259	} else {
260	/* look for set */
261	for (i = 0; os > 0; i++, os += os + 1)
262	if (setequal(os, oset))
263	break;
264	ot = oseti(i*OSTSIZ + osentry);
265	if (os > 0) / found it */
266	return(ot);
267	if (!isfull(ot)) /* entry overflow */
268	if (++ntries < OSTSIZ)
269	goto tryagain;
270	else
271	error(INTERNAL, "hash table overflow in fullnode");
272	/* remember position */
273	i = os - ostable[osentry];
274	os = ostable[osentry] = (OBJECT *)realloc(
275	(char *)ostable[osentry],
276	(unsigned)(i+oset[0]+2)*sizeof(OBJECT));
277	if (os == NULL)
278	goto memerr;
279	os += i; /* last entry */
280	}
281	setcopy(os, oset); /* add new set */
282	os += *os + 1;
283	os = 0; / terminator */
284	return(ot);
285	memerr:
286	error(SYSTEM, "out of memory in fullnode");
287	}
288
289
290	void
291	objset(oset, ot) /* get object set for full node */
292	register OBJECT *oset;
293	OCTREE ot;
294	{
295	register OBJECT *os;
296	register int i;
297
298	if (!isfull(ot))
299	goto noderr;
300	ot = oseti(ot);
301	if ((os = ostable[ot%OSTSIZ]) == NULL)
302	goto noderr;
303	for (i = ot/OSTSIZ; i--; os += *os + 1)
304	if (*os <= 0)
305	goto noderr;
306	for (i = os; i-- >= 0; ) / copy set here */
307	oset++ = os++;
308	return;
309	noderr:
310	error(CONSISTENCY, "bad node in objset");
311	}
312
313
314	int
315	dosets(f) /* loop through all sets */
316	int (*f)();
317	{
318	int res = 0;
319	int n;
320	register OBJECT *os;
321
322	for (n = 0; n < OSTSIZ; n++) {
323	if ((os = ostable[n]) == NULL)
324	continue;
325	while (*os > 0) {
326	res += (*f)(os);
327	os += *os + 1;
328	}
329	}
330	return(res);
331	}
332
333
334	void
335	donesets() /* free ALL SETS in our table */
336	{
337	register int n;
338
339	for (n = 0; n < OSTSIZ; n++)
340	if (ostable[n] != NULL) {
341	free((void *)ostable[n]);
342	ostable[n] = NULL;
343	}
344	}