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