src/common/objset.c

#ifndef lint
static const char       RCSid[] = "$Id: objset.c,v 2.15 2004/12/15 22:02:04 greg Exp $";
#endif
/*
 *  objset.c - routines for maintaining object sets.
 *
 *  External symbols declared in object.h
 */

#include "copyright.h"

#include  "standard.h"

#include  "octree.h"

#include  "object.h"

#ifndef  OSTSIZ
#ifdef  SMLMEM
#define  OSTSIZ         32749           /* object table size (a prime!) */
#else
#define  OSTSIZ         262139          /* object table size (a prime!) */
#endif
#endif

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


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


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


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

        if ((i = os[0]) <= 12) {        /* linear search algorithm */
                cm = obj;
                while (i-- > 0)
                        if (*++os == cm)
                                return(1);
                return(0);
        }
        lower = 1;
        upper = cm = i + 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);
}


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


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


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


void
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(
                                (void *)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");
        return 0; /* pro forma return */
}


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


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

        for (n = 0; n < OSTSIZ; n++) 
                if (ostable[n] != NULL) {
                        free((void *)ostable[n]);
                        ostable[n] = NULL;
                }
}
Revision:	2.16
Committed:	Wed Feb 22 17:05:36 2006 UTC (19 years, 8 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad4R2, rad4R1, rad4R0, rad3R8, rad3R9, rad4R2P1, rad4R2P2
Changes since 2.15:	+2 -2 lines
Log Message:	Increased trace modifier limit to 8192 in rtrace
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.16	static const char RCSid[] = "$Id: objset.c,v 2.15 2004/12/15 22:02:04 greg Exp $";
3	greg	1.1	#endif
4			/*
5			* objset.c - routines for maintaining object sets.
6			*
7	greg	2.8	* External symbols declared in object.h
8			*/
9
10	greg	2.9	#include "copyright.h"
11	greg	1.1
12			#include "standard.h"
13
14			#include "octree.h"
15
16			#include "object.h"
17
18	greg	1.4	#ifndef OSTSIZ
19	greg	2.11	#ifdef SMLMEM
20			#define OSTSIZ 32749 /* object table size (a prime!) */
21			#else
22	gregl	2.5	#define OSTSIZ 262139 /* object table size (a prime!) */
23	greg	1.8	#endif
24	greg	1.4	#endif
25	greg	1.1
26			static OBJECT ostable[OSTSIZ]; / the object set table */
27
28
29	greg	2.8	void
30	greg	1.1	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	greg	2.8	void
46	greg	1.1	deletelem(os, obj) /* delete obj from os, no questions */
47			register OBJECT *os;
48			OBJECT obj;
49			{
50			register int i;
51
52	greg	1.6	i = (*os)--;
53			os++;
54			while (i > 0 && *os < obj) {
55			i--;
56			os++;
57			}
58	greg	1.1	while (--i > 0) {
59			os[0] = os[1];
60			os++;
61			}
62			}
63
64
65	greg	2.8	int
66	greg	1.1	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	greg	2.16	if ((i = os[0]) <= 12) { /* linear search algorithm */
74	gwlarson	2.7	cm = obj;
75			while (i-- > 0)
76			if (*++os == cm)
77			return(1);
78			return(0);
79			}
80	greg	1.1	lower = 1;
81	gwlarson	2.7	upper = cm = i + 1;
82	greg	2.4	/* binary search algorithm */
83	greg	1.1	while ((i = (lower + upper) >> 1) != cm) {
84			cm = obj - os[i];
85			if (cm > 0)
86			lower = i;
87			else if (cm < 0)
88			upper = i;
89			else
90			return(1);
91			cm = i;
92			}
93			return(0);
94			}
95
96
97	greg	2.8	int
98	greg	1.1	setequal(os1, os2) /* determine if two sets are equal */
99			register OBJECT os1, os2;
100			{
101			register int i;
102
103			for (i = *os1; i-- >= 0; )
104			if (os1++ != os2++)
105			return(0);
106			return(1);
107			}
108
109
110	greg	2.8	void
111	greg	1.1	setcopy(os1, os2) /* copy object set os2 into os1 */
112			register OBJECT os1, os2;
113			{
114			register int i;
115
116			for (i = *os2; i-- >= 0; )
117			os1++ = os2++;
118			}
119
120
121	greg	2.4	OBJECT *
122			setsave(os) /* allocate space and save set */
123			register OBJECT *os;
124			{
125			OBJECT *osnew;
126			register OBJECT *oset;
127			register int i;
128
129			if ((osnew = oset = (OBJECT )malloc((os+1)*sizeof(OBJECT))) == NULL)
130			error(SYSTEM, "out of memory in setsave\n");
131			for (i = os; i-- >= 0; ) / inline setcopy */
132			oset++ = os++;
133			return(osnew);
134			}
135
136
137	greg	2.8	void
138	greg	2.4	setunion(osr, os1, os2) /* osr = os1 Union os2 */
139			register OBJECT osr, os1, *os2;
140			{
141			register int i1, i2;
142
143			osr[0] = 0;
144			for (i1 = i2 = 1; i1 <= os1[0] \|\| i2 <= os2[0]; ) {
145			while (i1 <= os1[0] && (i2 > os2[0] \|\| os1[i1] <= os2[i2])) {
146			osr[++osr[0]] = os1[i1];
147			if (i2 <= os2[0] && os2[i2] == os1[i1])
148			i2++;
149			i1++;
150			}
151			while (i2 <= os2[0] && (i1 > os1[0] \|\| os2[i2] < os1[i1]))
152			osr[++osr[0]] = os2[i2++];
153			}
154			}
155
156
157	greg	2.8	void
158	greg	2.4	setintersect(osr, os1, os2) /* osr = os1 Intersect os2 */
159			register OBJECT osr, os1, *os2;
160			{
161			register int i1, i2;
162
163			osr[0] = 0;
164			if (os1[0] <= 0)
165			return;
166			for (i1 = i2 = 1; i2 <= os2[0]; ) {
167			while (os1[i1] < os2[i2])
168			if (++i1 > os1[0])
169			return;
170			while (os2[i2] < os1[i1])
171			if (++i2 > os2[0])
172			return;
173			if (os1[i1] == os2[i2])
174			osr[++osr[0]] = os2[i2++];
175			}
176			}
177
178
179	greg	1.1	OCTREE
180			fullnode(oset) /* return octree for object set */
181			OBJECT *oset;
182			{
183			int osentry, ntries;
184			long hval;
185			OCTREE ot;
186			register int i;
187			register OBJECT *os;
188			/* hash on set */
189			hval = 0;
190			os = oset;
191			i = *os++;
192			while (i-- > 0)
193			hval += *os++;
194			ntries = 0;
195			tryagain:
196			osentry = (hval + (long)ntries*ntries) % OSTSIZ;
197			os = ostable[osentry];
198			if (os == NULL) {
199			os = ostable[osentry] = (OBJECT *)malloc(
200			(unsigned)(oset[0]+2)*sizeof(OBJECT));
201			if (os == NULL)
202			goto memerr;
203			ot = oseti(osentry);
204			} else {
205			/* look for set */
206			for (i = 0; os > 0; i++, os += os + 1)
207			if (setequal(os, oset))
208			break;
209			ot = oseti(i*OSTSIZ + osentry);
210			if (os > 0) / found it */
211			return(ot);
212	schorsch	2.13	if (!isfull(ot)) { /* entry overflow */
213	greg	1.1	if (++ntries < OSTSIZ)
214			goto tryagain;
215			else
216			error(INTERNAL, "hash table overflow in fullnode");
217	schorsch	2.13	}
218	greg	1.1	/* remember position */
219			i = os - ostable[osentry];
220			os = ostable[osentry] = (OBJECT *)realloc(
221	greg	2.10	(void *)ostable[osentry],
222	greg	1.1	(unsigned)(i+oset[0]+2)*sizeof(OBJECT));
223			if (os == NULL)
224			goto memerr;
225			os += i; /* last entry */
226			}
227			setcopy(os, oset); /* add new set */
228			os += *os + 1;
229			os = 0; / terminator */
230			return(ot);
231			memerr:
232			error(SYSTEM, "out of memory in fullnode");
233	greg	2.14	return 0; /* pro forma return */
234	greg	1.1	}
235
236
237	greg	2.8	void
238	greg	1.1	objset(oset, ot) /* get object set for full node */
239			register OBJECT *oset;
240			OCTREE ot;
241			{
242			register OBJECT *os;
243			register int i;
244
245			if (!isfull(ot))
246			goto noderr;
247	gwlarson	2.6	ot = oseti(ot);
248			if ((os = ostable[ot%OSTSIZ]) == NULL)
249	greg	1.1	goto noderr;
250	gwlarson	2.6	for (i = ot/OSTSIZ; i--; os += *os + 1)
251	greg	1.1	if (*os <= 0)
252			goto noderr;
253			for (i = os; i-- >= 0; ) / copy set here */
254			oset++ = os++;
255			return;
256			noderr:
257			error(CONSISTENCY, "bad node in objset");
258	greg	1.2	}
259
260
261	greg	2.8	void
262	greg	2.4	donesets() /* free ALL SETS in our table */
263			{
264			register int n;
265
266			for (n = 0; n < OSTSIZ; n++)
267			if (ostable[n] != NULL) {
268	greg	2.8	free((void *)ostable[n]);
269	greg	2.4	ostable[n] = NULL;
270			}
271	greg	1.1	}