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;

        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;
        register OBJECT  *os;
        register OBJECT  i;

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