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"

#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;
                                        /* 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);
}


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


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


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


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


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


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


donesets()                      /* free ALL SETS in our table */
{
        register int  n;

        for (n = 0; n < OSTSIZ; n++) 
                if (ostable[n] != NULL) {
                        free((char *)ostable[n]);
                        ostable[n] = NULL;
                }
}
Revision:	2.4
Committed:	Fri Mar 7 15:45:28 1997 UTC (27 years, 1 month ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.3:	+78 -13 lines
Log Message:	added new set routines
#	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.4	#ifndef OSTSIZ
20	greg	1.8	#ifdef BIGMEM
21			#define OSTSIZ 56437 /* object table size (a prime!) */
22			#else
23	greg	1.4	#define OSTSIZ 12329 /* object table size (a prime!) */
24	greg	1.8	#endif
25	greg	1.4	#endif
26	greg	1.1
27			static OBJECT ostable[OSTSIZ]; / the object set table */
28
29
30			insertelem(os, obj) /* insert obj into os, no questions */
31			register OBJECT *os;
32			OBJECT obj;
33			{
34			register int i;
35
36			for (i = os[0]++; i > 0; i--)
37			if (os[i] > obj)
38			os[i+1] = os[i];
39			else
40			break;
41			os[i+1] = obj;
42			}
43
44
45			deletelem(os, obj) /* delete obj from os, no questions */
46			register OBJECT *os;
47			OBJECT obj;
48			{
49			register int i;
50
51	greg	1.6	i = (*os)--;
52			os++;
53			while (i > 0 && *os < obj) {
54			i--;
55			os++;
56			}
57	greg	1.1	while (--i > 0) {
58			os[0] = os[1];
59			os++;
60			}
61			}
62
63
64			inset(os, obj) /* determine if object is in set */
65			register OBJECT *os;
66			OBJECT obj;
67			{
68			int upper, lower;
69			register int cm, i;
70
71			lower = 1;
72			upper = cm = os[0] + 1;
73	greg	2.4	/* binary search algorithm */
74	greg	1.1	while ((i = (lower + upper) >> 1) != cm) {
75			cm = obj - os[i];
76			if (cm > 0)
77			lower = i;
78			else if (cm < 0)
79			upper = i;
80			else
81			return(1);
82			cm = i;
83			}
84			return(0);
85			}
86
87
88			setequal(os1, os2) /* determine if two sets are equal */
89			register OBJECT os1, os2;
90			{
91			register int i;
92
93			for (i = *os1; i-- >= 0; )
94			if (os1++ != os2++)
95			return(0);
96			return(1);
97			}
98
99
100			setcopy(os1, os2) /* copy object set os2 into os1 */
101			register OBJECT os1, os2;
102			{
103			register int i;
104
105			for (i = *os2; i-- >= 0; )
106			os1++ = os2++;
107			}
108
109
110	greg	2.4	OBJECT *
111			setsave(os) /* allocate space and save set */
112			register OBJECT *os;
113			{
114			OBJECT *osnew;
115			register OBJECT *oset;
116			register int i;
117
118			if ((osnew = oset = (OBJECT )malloc((os+1)*sizeof(OBJECT))) == NULL)
119			error(SYSTEM, "out of memory in setsave\n");
120			for (i = os; i-- >= 0; ) / inline setcopy */
121			oset++ = os++;
122			return(osnew);
123			}
124
125
126			setunion(osr, os1, os2) /* osr = os1 Union os2 */
127			register OBJECT osr, os1, *os2;
128			{
129			register int i1, i2;
130
131			osr[0] = 0;
132			for (i1 = i2 = 1; i1 <= os1[0] \|\| i2 <= os2[0]; ) {
133			while (i1 <= os1[0] && (i2 > os2[0] \|\| os1[i1] <= os2[i2])) {
134			osr[++osr[0]] = os1[i1];
135			if (i2 <= os2[0] && os2[i2] == os1[i1])
136			i2++;
137			i1++;
138			}
139			while (i2 <= os2[0] && (i1 > os1[0] \|\| os2[i2] < os1[i1]))
140			osr[++osr[0]] = os2[i2++];
141			}
142			}
143
144
145			setintersect(osr, os1, os2) /* osr = os1 Intersect os2 */
146			register OBJECT osr, os1, *os2;
147			{
148			register int i1, i2;
149
150			osr[0] = 0;
151			if (os1[0] <= 0)
152			return;
153			for (i1 = i2 = 1; i2 <= os2[0]; ) {
154			while (os1[i1] < os2[i2])
155			if (++i1 > os1[0])
156			return;
157			while (os2[i2] < os1[i1])
158			if (++i2 > os2[0])
159			return;
160			if (os1[i1] == os2[i2])
161			osr[++osr[0]] = os2[i2++];
162			}
163			}
164
165
166	greg	1.1	OCTREE
167			fullnode(oset) /* return octree for object set */
168			OBJECT *oset;
169			{
170			int osentry, ntries;
171			long hval;
172			OCTREE ot;
173			register int i;
174			register OBJECT *os;
175			/* hash on set */
176			hval = 0;
177			os = oset;
178			i = *os++;
179			while (i-- > 0)
180			hval += *os++;
181			ntries = 0;
182			tryagain:
183			osentry = (hval + (long)ntries*ntries) % OSTSIZ;
184			os = ostable[osentry];
185			if (os == NULL) {
186			os = ostable[osentry] = (OBJECT *)malloc(
187			(unsigned)(oset[0]+2)*sizeof(OBJECT));
188			if (os == NULL)
189			goto memerr;
190			ot = oseti(osentry);
191			} else {
192			/* look for set */
193			for (i = 0; os > 0; i++, os += os + 1)
194			if (setequal(os, oset))
195			break;
196			ot = oseti(i*OSTSIZ + osentry);
197			if (os > 0) / found it */
198			return(ot);
199			if (!isfull(ot)) /* entry overflow */
200			if (++ntries < OSTSIZ)
201			goto tryagain;
202			else
203			error(INTERNAL, "hash table overflow in fullnode");
204			/* remember position */
205			i = os - ostable[osentry];
206			os = ostable[osentry] = (OBJECT *)realloc(
207			(char *)ostable[osentry],
208			(unsigned)(i+oset[0]+2)*sizeof(OBJECT));
209			if (os == NULL)
210			goto memerr;
211			os += i; /* last entry */
212			}
213			setcopy(os, oset); /* add new set */
214			os += *os + 1;
215			os = 0; / terminator */
216			return(ot);
217			memerr:
218			error(SYSTEM, "out of memory in fullnode");
219			}
220
221
222			objset(oset, ot) /* get object set for full node */
223			register OBJECT *oset;
224			OCTREE ot;
225			{
226			register OBJECT *os;
227			register int i;
228
229			if (!isfull(ot))
230			goto noderr;
231			i = oseti(ot);
232			if ((os = ostable[i%OSTSIZ]) == NULL)
233			goto noderr;
234			for (i /= OSTSIZ; i--; os += *os + 1)
235			if (*os <= 0)
236			goto noderr;
237			for (i = os; i-- >= 0; ) / copy set here */
238			oset++ = os++;
239			return;
240			noderr:
241			error(CONSISTENCY, "bad node in objset");
242	greg	1.2	}
243
244
245	greg	2.4	int
246			dosets(f) /* loop through all sets */
247			int (*f)();
248	greg	1.2	{
249	greg	2.4	int res = 0;
250	greg	1.2	int n;
251			register OBJECT *os;
252	greg	1.3
253	greg	1.2	for (n = 0; n < OSTSIZ; n++) {
254			if ((os = ostable[n]) == NULL)
255			continue;
256	greg	2.4	while (*os > 0) {
257			res += (*f)(os);
258			os += *os + 1;
259			}
260	greg	1.2	}
261	greg	2.4	return(res);
262			}
263
264
265			donesets() /* free ALL SETS in our table */
266			{
267			register int n;
268
269			for (n = 0; n < OSTSIZ; n++)
270			if (ostable[n] != NULL) {
271			free((char *)ostable[n]);
272			ostable[n] = NULL;
273			}
274	greg	1.1	}