src/common/objset.c

/* Copyright (c) 1986 Regents of the University of California */

#ifndef lint
static char SCCSid[] = "$SunId$ LBL";
#endif

/*
 *  objset.c - routines for maintaining object sets.
 *
 *      7/28/85
 */

#include  "standard.h"

#include  "octree.h"

#include  "object.h"

#include  "otypes.h"

#define  OSTSIZ         3037            /* object table size (a prime!) */

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


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;
}


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

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


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

        lower = 1;
        upper = cm = os[0] + 1;

        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);
}


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);
}


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

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


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");
}


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;
        i = oseti(ot);
        if ((os = ostable[i%OSTSIZ]) == NULL)
                goto noderr;
        for (i /= 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");
}


nonsurfinset(orig, nobjs)               /* check sets for non-surfaces */
int  orig, nobjs;
{
        int  n;
        OBJECT  *nonset;
        register OBJECT  *os;
        register OBJECT  i;
                                                /* count non-surfaces */
        n = 0;
        for (i = orig; i < orig+nobjs; i++)
                if (!issurface(objptr(i)->otype))
                        n++;
        if (n <= 0)
                return(0);
                                                /* allocate set */
        if ((nonset = (OBJECT *)malloc((n+1)*sizeof(OBJECT))) == NULL)
                return(0);              /* give up if we haven't enough mem */
                                                /* fill set */
        os = nonset;
        *os = n;
        for (i = orig; i < orig+nobjs; i++)
                if (!issurface(objptr(i)->otype))
                        *++os = i;
                                                /* now check all sets */
        for (n = 0; n < OSTSIZ; n++) {
                if ((os = ostable[n]) == NULL)
                        continue;
                while ((i = *os++) > 0)
                        while (i--) {
                                if (*os >= nonset[1]
                                                && *os <= nonset[nonset[0]]
                                                && inset(nonset, *os))
                                        goto done;
                                os++;
                        }
        }
done:
        free((char *)nonset);
        return(n < OSTSIZ);
}
Revision:	1.2
Committed:	Thu Sep 6 23:32:41 1990 UTC (33 years, 7 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.1:	+44 -0 lines
Log Message:	added consistency checks to detect stale octrees
#	User	Rev	Content
1	greg	1.1	/* Copyright (c) 1986 Regents of the University of California */
2
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ LBL";
5			#endif
6
7			/*
8			* objset.c - routines for maintaining object sets.
9			*
10			* 7/28/85
11			*/
12
13			#include "standard.h"
14
15			#include "octree.h"
16
17			#include "object.h"
18
19	greg	1.2	#include "otypes.h"
20
21	greg	1.1	#define OSTSIZ 3037 /* object table size (a prime!) */
22
23			static OBJECT ostable[OSTSIZ]; / the object set table */
24
25
26			insertelem(os, obj) /* insert obj into os, no questions */
27			register OBJECT *os;
28			OBJECT obj;
29			{
30			register int i;
31
32			for (i = os[0]++; i > 0; i--)
33			if (os[i] > obj)
34			os[i+1] = os[i];
35			else
36			break;
37			os[i+1] = obj;
38			}
39
40
41			deletelem(os, obj) /* delete obj from os, no questions */
42			register OBJECT *os;
43			OBJECT obj;
44			{
45			register int i;
46
47			for (i = (os++)--; i > 0 && os < obj; i--, os++)
48			;
49			while (--i > 0) {
50			os[0] = os[1];
51			os++;
52			}
53			}
54
55
56			inset(os, obj) /* determine if object is in set */
57			register OBJECT *os;
58			OBJECT obj;
59			{
60			int upper, lower;
61			register int cm, i;
62
63			lower = 1;
64			upper = cm = os[0] + 1;
65
66			while ((i = (lower + upper) >> 1) != cm) {
67			cm = obj - os[i];
68			if (cm > 0)
69			lower = i;
70			else if (cm < 0)
71			upper = i;
72			else
73			return(1);
74			cm = i;
75			}
76			return(0);
77			}
78
79
80			setequal(os1, os2) /* determine if two sets are equal */
81			register OBJECT os1, os2;
82			{
83			register int i;
84
85			for (i = *os1; i-- >= 0; )
86			if (os1++ != os2++)
87			return(0);
88			return(1);
89			}
90
91
92			setcopy(os1, os2) /* copy object set os2 into os1 */
93			register OBJECT os1, os2;
94			{
95			register int i;
96
97			for (i = *os2; i-- >= 0; )
98			os1++ = os2++;
99			}
100
101
102			OCTREE
103			fullnode(oset) /* return octree for object set */
104			OBJECT *oset;
105			{
106			int osentry, ntries;
107			long hval;
108			OCTREE ot;
109			register int i;
110			register OBJECT *os;
111			/* hash on set */
112			hval = 0;
113			os = oset;
114			i = *os++;
115			while (i-- > 0)
116			hval += *os++;
117			ntries = 0;
118			tryagain:
119			osentry = (hval + (long)ntries*ntries) % OSTSIZ;
120			os = ostable[osentry];
121			if (os == NULL) {
122			os = ostable[osentry] = (OBJECT *)malloc(
123			(unsigned)(oset[0]+2)*sizeof(OBJECT));
124			if (os == NULL)
125			goto memerr;
126			ot = oseti(osentry);
127			} else {
128			/* look for set */
129			for (i = 0; os > 0; i++, os += os + 1)
130			if (setequal(os, oset))
131			break;
132			ot = oseti(i*OSTSIZ + osentry);
133			if (os > 0) / found it */
134			return(ot);
135			if (!isfull(ot)) /* entry overflow */
136			if (++ntries < OSTSIZ)
137			goto tryagain;
138			else
139			error(INTERNAL, "hash table overflow in fullnode");
140			/* remember position */
141			i = os - ostable[osentry];
142			os = ostable[osentry] = (OBJECT *)realloc(
143			(char *)ostable[osentry],
144			(unsigned)(i+oset[0]+2)*sizeof(OBJECT));
145			if (os == NULL)
146			goto memerr;
147			os += i; /* last entry */
148			}
149			setcopy(os, oset); /* add new set */
150			os += *os + 1;
151			os = 0; / terminator */
152			return(ot);
153			memerr:
154			error(SYSTEM, "out of memory in fullnode");
155			}
156
157
158			objset(oset, ot) /* get object set for full node */
159			register OBJECT *oset;
160			OCTREE ot;
161			{
162			register OBJECT *os;
163			register int i;
164
165			if (!isfull(ot))
166			goto noderr;
167			i = oseti(ot);
168			if ((os = ostable[i%OSTSIZ]) == NULL)
169			goto noderr;
170			for (i /= OSTSIZ; i--; os += *os + 1)
171			if (*os <= 0)
172			goto noderr;
173			for (i = os; i-- >= 0; ) / copy set here */
174			oset++ = os++;
175			return;
176			noderr:
177			error(CONSISTENCY, "bad node in objset");
178	greg	1.2	}
179
180
181			nonsurfinset(orig, nobjs) /* check sets for non-surfaces */
182			int orig, nobjs;
183			{
184			int n;
185			OBJECT *nonset;
186			register OBJECT *os;
187			register OBJECT i;
188			/* count non-surfaces */
189			n = 0;
190			for (i = orig; i < orig+nobjs; i++)
191			if (!issurface(objptr(i)->otype))
192			n++;
193			if (n <= 0)
194			return(0);
195			/* allocate set */
196			if ((nonset = (OBJECT )malloc((n+1)sizeof(OBJECT))) == NULL)
197			return(0); /* give up if we haven't enough mem */
198			/* fill set */
199			os = nonset;
200			*os = n;
201			for (i = orig; i < orig+nobjs; i++)
202			if (!issurface(objptr(i)->otype))
203			*++os = i;
204			/* now check all sets */
205			for (n = 0; n < OSTSIZ; n++) {
206			if ((os = ostable[n]) == NULL)
207			continue;
208			while ((i = *os++) > 0)
209			while (i--) {
210			if (*os >= nonset[1]
211			&& *os <= nonset[nonset[0]]
212			&& inset(nonset, *os))
213			goto done;
214			os++;
215			}
216			}
217			done:
218			free((char *)nonset);
219			return(n < OSTSIZ);
220	greg	1.1	}