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
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.8	static const char RCSid[] = "$Id$";
3	greg	1.1	#endif
4			/*
5			* objset.c - routines for maintaining object sets.
6			*
7	greg	2.8	* 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	greg	1.1	*/
66
67			#include "standard.h"
68
69			#include "octree.h"
70
71			#include "object.h"
72
73	greg	1.4	#ifndef OSTSIZ
74	greg	1.8	#ifdef BIGMEM
75	gregl	2.5	#define OSTSIZ 262139 /* object table size (a prime!) */
76	greg	1.8	#else
77	gregl	2.5	#define OSTSIZ 32749 /* object table size (a prime!) */
78	greg	1.8	#endif
79	greg	1.4	#endif
80	greg	1.1
81			static OBJECT ostable[OSTSIZ]; / the object set table */
82
83
84	greg	2.8	void
85	greg	1.1	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	greg	2.8	void
101	greg	1.1	deletelem(os, obj) /* delete obj from os, no questions */
102			register OBJECT *os;
103			OBJECT obj;
104			{
105			register int i;
106
107	greg	1.6	i = (*os)--;
108			os++;
109			while (i > 0 && *os < obj) {
110			i--;
111			os++;
112			}
113	greg	1.1	while (--i > 0) {
114			os[0] = os[1];
115			os++;
116			}
117			}
118
119
120	greg	2.8	int
121	greg	1.1	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	gwlarson	2.7	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	greg	1.1	lower = 1;
136	gwlarson	2.7	upper = cm = i + 1;
137	greg	2.4	/* binary search algorithm */
138	greg	1.1	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	greg	2.8	int
153	greg	1.1	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	greg	2.8	void
166	greg	1.1	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	greg	2.4	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	greg	2.8	void
193	greg	2.4	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	greg	2.8	void
213	greg	2.4	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	greg	1.1	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	greg	2.8	void
291	greg	1.1	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	gwlarson	2.6	ot = oseti(ot);
301			if ((os = ostable[ot%OSTSIZ]) == NULL)
302	greg	1.1	goto noderr;
303	gwlarson	2.6	for (i = ot/OSTSIZ; i--; os += *os + 1)
304	greg	1.1	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	greg	1.2	}
312
313
314	greg	2.4	int
315			dosets(f) /* loop through all sets */
316			int (*f)();
317	greg	1.2	{
318	greg	2.4	int res = 0;
319	greg	1.2	int n;
320			register OBJECT *os;
321	greg	1.3
322	greg	1.2	for (n = 0; n < OSTSIZ; n++) {
323			if ((os = ostable[n]) == NULL)
324			continue;
325	greg	2.4	while (*os > 0) {
326			res += (*f)(os);
327			os += *os + 1;
328			}
329	greg	1.2	}
330	greg	2.4	return(res);
331			}
332
333
334	greg	2.8	void
335	greg	2.4	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	greg	2.8	free((void *)ostable[n]);
342	greg	2.4	ostable[n] = NULL;
343			}
344	greg	1.1	}