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"

#ifndef  OSTSIZ
#define  OSTSIZ         12329           /* object table size (a prime!) */
#endif

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;

        i = (*os)--;
        os++;
        while (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;
        register OBJECT  *os;
        register OBJECT  i, s;

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