src/common/objset.c

#ifndef lint
static const char       RCSid[] = "$Id: objset.c,v 2.17 2015/04/28 16:56:10 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         1002583         /* object table size (a prime!) */
#endif
#endif

#undef xtra_long
#ifdef _WIN64
typedef unsigned long long int  xtra_long;
#else
typedef unsigned long int       xtra_long;
#endif

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


void
insertelem(                     /* insert obj into os, no questions */
        OBJECT  *os,
        OBJECT  obj
)
{
        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(                      /* delete obj from os, no questions */
        OBJECT  *os,
        OBJECT  obj
)
{
        int  i;

        i = (*os)--;
        os++;
        while (i > 0 && *os < obj) {
                i--;
                os++;
        }
        while (--i > 0) {
                os[0] = os[1];
                os++;
        }
}


int
inset(                          /* determine if object is in set */
        OBJECT  *os,
        OBJECT  obj
)
{
        int  upper, lower;
        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(                       /* determine if two sets are equal */
        OBJECT  *os1,
        OBJECT  *os2
)
{
        int  i;

        for (i = *os1; i-- >= 0; )
                if (*os1++ != *os2++)
                        return(0);
        return(1);
}


void
setcopy(                        /* copy object set os2 into os1 */
        OBJECT  *os1,
        OBJECT  *os2
)
{
        int  i;

        for (i = *os2; i-- >= 0; )
                *os1++ = *os2++;
}


OBJECT *
setsave(                        /* allocate space and save set */
        OBJECT  *os
)
{
        OBJECT  *osnew;
        OBJECT  *oset;
        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 Union os2 */
        OBJECT  *osr,
        OBJECT  *os1,
        OBJECT  *os2
)
{
        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 Intersect os2 */
        OBJECT  *osr,
        OBJECT  *os1,
        OBJECT  *os2
)
{
        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(                       /* return octree for object set */
        OBJECT  *oset
)
{
        unsigned int  ntries;
        xtra_long  hval;
        OCTREE  ot;
        int  osentry, i;
        OBJECT  *os;
                                        /* hash on set */
        hval = 0;
        os = oset;
        i = *os++;
        while (i-- > 0)
                hval += *os++;
        ntries = 0;
tryagain:
        osentry = (hval + (xtra_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(                 /* get object set for full node */
        OBJECT  *oset,
        OCTREE  ot
)
{
        OBJECT  *os;
        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(void)                  /* free ALL SETS in our table */
{
        int  n;

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