src/common/modobject.c

#ifndef lint
static const char RCSid[] = "$Id: modobject.c,v 2.25 2025/06/21 17:42:17 greg Exp $";
#endif
/*
 *  Routines for tracking object modifiers
 *
 *  External symbols declared in object.h
 */

#include "copyright.h"

#include  "standard.h"
#include  "object.h"
#include  "otypes.h"


static struct ohtab {
        int     hsiz;                   /* current table size */
        OBJECT  *htab;                  /* table, if allocated */
}  modtab = {100, NULL}, objtab = {1000, NULL}; /* modifiers and objects */

static int  otndx(char *, struct ohtab *);


OBJECT
objndx(                         /* get object number from pointer */
        OBJREC  *op
)
{
#ifndef ONCACHESIZ
#define ONCACHESIZ      907     /* keep a cache of previous searches */
#endif
        static OBJECT   oncache[ONCACHESIZ];
        const int       ent = (size_t)op % ONCACHESIZ;  /* hash on pointer */
        int             i, lastblock;

#if OVOID != 0                  /* clear cache on first call */
        for (i = ONCACHESIZ*(!oncache[0] & !oncache[1]); i--; )
                oncache[i] = OVOID;
#endif
                                /* is this pointer in cache? */
        if ((oncache[ent] != OVOID) & (oncache[ent] < nobjects) &&
                                objptr(oncache[ent]) == op)
                return(oncache[ent]);           /* matches previous search */
                                /* else search for our block from first */
        lastblock = (nobjects-1)>>OBJBLKSHFT;
        for (i = 0; i <= lastblock; i++)
                if ((objblock[i] <= op) & (op < objblock[i]+OBJBLKSIZ)) {
                                /* found it -- cache corresponding index */
                        oncache[ent] = ((OBJECT)i << OBJBLKSHFT) +
                                                (op - objblock[i]);
                        return(oncache[ent]);
                }
        return(OVOID);          /* not allocated -- may still be valid */
}


OBJECT
lastmod(                        /* find modifier definition before obj */
        OBJECT  obj,
        char  *mname
)
{
        OBJREC  *op;
        OBJECT  i;

        i = modifier(mname);            /* try hash table first */
        if ((obj == OVOID) | (i < obj))
                return(i);
        for (i = obj; i-- > 0; ) {      /* need to search */
                op = objptr(i);
                if ((ismodifier(op->otype) != 0) & (op->oname[0] == mname[0])
                                && !strcmp(op->oname, mname))
                        return(i);
        }
        return(OVOID);
}


OBJECT
modifier(                       /* get a modifier number from its name */
        char  *mname
)
{
        int  ndx;

        ndx = otndx(mname, &modtab);
        return(modtab.htab[ndx]);
}


#ifdef  GETOBJ
OBJECT
object(                         /* get an object number from its name */
        char  *oname
)
{
        int  ndx;

        ndx = otndx(oname, &objtab);
        return(objtab.htab[ndx]);
}
#endif


int
eqreal(                         /* are two real values close enough to equal? */
        double  d1,
        double  d2
)
{
        if (d2 != 0.0)
                d1 = d1/d2 - 1.0;
        return((-FTINY <= d1) & (d1 <= FTINY));
}


int
eqobjects(                      /* check if two objects are equal */
        OBJECT  obj1,
        OBJECT  obj2
)
{
        OBJREC  *op1, *op2;
        int     i, n;

        while (obj1 != obj2) {
                if (obj1 == OVOID)
                        return(0);
                if (obj2 == OVOID)
                        return(0);
                op1 = objptr(obj1);
                op2 = objptr(obj2);
                if (op1->otype != op2->otype)
                        return(0);
                if (op1->oargs.nsargs != op2->oargs.nsargs)
                        return(0);
                if (op1->oargs.nfargs != op2->oargs.nfargs)
                        return(0);
#ifdef IARGS
                if (op1->oargs.niargs != op2->oargs.niargs)
                        return(0);
                for (i = op1->oargs.niargs; i-- > 0; )
                        if (op1->oargs.iarg[i] != op2->oargs.iarg[i])
                                return(0);
#endif
                for (i = op1->oargs.nfargs; i-- > 0; )
                        if (!eqreal(op1->oargs.farg[i], op2->oargs.farg[i]))
                                return(0);
                n = 0;
                switch (op1->otype) {   /* special cases (KEEP CONSISTENT!) */
                case MOD_ALIAS:
                case MAT_ILLUM:
                case MAT_MIRROR:
                        n = (op1->oargs.nsargs > 0);
                        break;
                case MIX_FUNC:
                case MIX_DATA:
                case MIX_TEXT:
                case MIX_PICT:
                        n = 2*(op1->oargs.nsargs >= 2);
                        break;
                case MAT_CLIP:
                        n = op1->oargs.nsargs;
                        break;
                }
                                        /* check other string arguments */
                for (i = op1->oargs.nsargs; i-- > n; )
                        if (strcmp(op1->oargs.sarg[i], op2->oargs.sarg[i]))
                                return(0);
                while (n-- > 0)         /* check modifier references */
                        if (!eqobjects( lastmod(obj1, op1->oargs.sarg[n]),
                                        lastmod(obj2, op2->oargs.sarg[n]) ))
                                return(0);
                obj1 = op1->omod;
                obj2 = op2->omod;
        }
        return(1);
}


void
insertobject(                   /* insert new object into our list */
        OBJECT  obj
)
{
        int  i;

        if (ismodifier(objptr(obj)->otype)) {
                i = otndx(objptr(obj)->oname, &modtab);
                if (eqobjects(obj, modtab.htab[i]))
                        return; /* don't index if same as earlier def. */
                modtab.htab[i] = obj;
        }
#ifdef  GETOBJ
        else {
                i = otndx(objptr(obj)->oname, &objtab);
                objtab.htab[i] = obj;
        }
#endif
        for (i = 0; addobjnotify[i] != NULL; i++)
                (*addobjnotify[i])(obj);
}


void
truncobjndx(void)               /* remove bogus table entries past end */
{
        int     ndx;

        if (nobjects <= 0) {
                if (modtab.htab != NULL) {
                        free(modtab.htab);
                        modtab.htab = NULL;
                        modtab.hsiz = 100;
                }
                if (objtab.htab != NULL) {
                        free(objtab.htab);
                        objtab.htab = NULL;
                        objtab.hsiz = 100;
                }
                return;
        }
        for (ndx = modtab.hsiz*(modtab.htab != NULL); ndx--; )
                if (modtab.htab[ndx] >= nobjects)
                        modtab.htab[ndx] = OVOID;

        for (ndx = objtab.hsiz*(objtab.htab != NULL); ndx--; )
                if (objtab.htab[ndx] >= nobjects)
                        objtab.htab[ndx] = OVOID;
}


static int
nexthsiz(                       /* return next hash table size */
        int  oldsiz
)
{
        static int  hsiztab[] = {
                251, 509, 1021, 2039, 4093, 8191, 16381,
                32749, 65521, 131071, 262139, 0
        };
        int  *hsp;

        for (hsp = hsiztab; *hsp; hsp++)
                if (*hsp > oldsiz)
                        return(*hsp);
        return(oldsiz*2 + 1);           /* not always prime */
}


static int
otndx(                          /* get object table index for name */
        char  *name,
        struct ohtab  *tab
)
{
        char    *onm;
        OBJECT  *oldhtab;
        int  hval, i;
        int  ndx;

        if (tab->htab == NULL) {                /* new table */
                tab->hsiz = nexthsiz(tab->hsiz);
                tab->htab = (OBJECT *)malloc(tab->hsiz*sizeof(OBJECT));
                if (tab->htab == NULL)
                        error(SYSTEM, "out of memory in otndx");
                ndx = tab->hsiz;
                while (ndx--)                   /* empty it */
                        tab->htab[ndx] = OVOID;
        }
                                        /* look up object */
        hval = shash(name);
tryagain:
        for (i = 0; i < tab->hsiz; i++) {
                ndx = (hval + (unsigned long)i*i) % tab->hsiz;
                if (tab->htab[ndx] == OVOID)
                        return(ndx);
                onm = objptr(tab->htab[ndx])->oname;
                if (onm != NULL && !strcmp(onm, name))
                        return(ndx);
        }
                                        /* table is full, reallocate */
        oldhtab = tab->htab;
        ndx = tab->hsiz;
        tab->htab = NULL;
        while (ndx--)
                if (oldhtab[ndx] != OVOID) {
                        onm = objptr(oldhtab[ndx])->oname;
                        if (onm == NULL)
                                continue;
                        i = otndx(onm, tab);
                        tab->htab[i] = oldhtab[ndx];
                }
        free(oldhtab);
        goto tryagain;                  /* should happen only once! */
}
Revision:	2.26
Committed:	Sun Jun 22 17:21:37 2025 UTC (12 days, 20 hours ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 2.25:	+11 -8 lines
Log Message:	perf: Minor code tweaks to speed initial search, check case OVOID==0
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.26	static const char RCSid[] = "$Id: modobject.c,v 2.25 2025/06/21 17:42:17 greg Exp $";
3	greg	1.1	#endif
4			/*
5			* Routines for tracking object modifiers
6	greg	2.7	*
7			* External symbols declared in object.h
8			*/
9
10	greg	2.8	#include "copyright.h"
11	greg	1.1
12			#include "standard.h"
13			#include "object.h"
14	greg	1.2	#include "otypes.h"
15
16	greg	1.1
17			static struct ohtab {
18	greg	2.22	int hsiz; /* current table size */
19			OBJECT htab; / table, if allocated */
20	greg	1.1	} modtab = {100, NULL}, objtab = {1000, NULL}; /* modifiers and objects */
21
22	schorsch	2.10	static int otndx(char , struct ohtab );
23	greg	1.3
24	greg	1.1
25	greg	2.9	OBJECT
26	greg	2.13	objndx( /* get object number from pointer */
27			OBJREC *op
28			)
29	greg	1.1	{
30	greg	2.25	#ifndef ONCACHESIZ
31			#define ONCACHESIZ 907 /* keep a cache of previous searches */
32			#endif
33			static OBJECT oncache[ONCACHESIZ];
34	greg	2.26	const int ent = (size_t)op % ONCACHESIZ; /* hash on pointer */
35			int i, lastblock;
36
37			#if OVOID != 0 /* clear cache on first call */
38	greg	2.25	for (i = ONCACHESIZ*(!oncache[0] & !oncache[1]); i--; )
39			oncache[i] = OVOID;
40	greg	2.26	#endif
41	greg	2.25	/* is this pointer in cache? */
42			if ((oncache[ent] != OVOID) & (oncache[ent] < nobjects) &&
43			objptr(oncache[ent]) == op)
44			return(oncache[ent]); /* matches previous search */
45	greg	2.26	/* else search for our block from first */
46			lastblock = (nobjects-1)>>OBJBLKSHFT;
47			for (i = 0; i <= lastblock; i++)
48	greg	2.25	if ((objblock[i] <= op) & (op < objblock[i]+OBJBLKSIZ)) {
49	greg	2.26	/* found it -- cache corresponding index */
50	greg	2.25	oncache[ent] = ((OBJECT)i << OBJBLKSHFT) +
51			(op - objblock[i]);
52			return(oncache[ent]);
53			}
54	greg	2.26	return(OVOID); /* not allocated -- may still be valid */
55	greg	1.1	}
56
57
58	greg	2.9	OBJECT
59	greg	2.13	lastmod( /* find modifier definition before obj */
60			OBJECT obj,
61			char *mname
62			)
63	greg	2.3	{
64	greg	2.13	OBJREC *op;
65	greg	2.22	OBJECT i;
66	greg	2.3
67	greg	2.4	i = modifier(mname); /* try hash table first */
68	greg	2.12	if ((obj == OVOID) \| (i < obj))
69	greg	2.4	return(i);
70			for (i = obj; i-- > 0; ) { /* need to search */
71	greg	2.3	op = objptr(i);
72	greg	2.22	if ((ismodifier(op->otype) != 0) & (op->oname[0] == mname[0])
73			&& !strcmp(op->oname, mname))
74	greg	2.3	return(i);
75			}
76			return(OVOID);
77			}
78
79
80	greg	2.9	OBJECT
81	greg	2.13	modifier( /* get a modifier number from its name */
82			char *mname
83			)
84	greg	1.1	{
85	greg	2.13	int ndx;
86	greg	1.1
87			ndx = otndx(mname, &modtab);
88			return(modtab.htab[ndx]);
89			}
90
91
92	greg	2.3	#ifdef GETOBJ
93	greg	2.9	OBJECT
94	greg	2.13	object( /* get an object number from its name */
95			char *oname
96			)
97	greg	2.3	{
98	greg	2.13	int ndx;
99	greg	2.3
100			ndx = otndx(oname, &objtab);
101			return(objtab.htab[ndx]);
102			}
103			#endif
104
105
106	greg	2.15	int
107	greg	2.14	eqreal( /* are two real values close enough to equal? */
108			double d1,
109			double d2
110			)
111			{
112			if (d2 != 0.0)
113			d1 = d1/d2 - 1.0;
114			return((-FTINY <= d1) & (d1 <= FTINY));
115			}
116
117
118			int
119			eqobjects( /* check if two objects are equal */
120			OBJECT obj1,
121			OBJECT obj2
122			)
123			{
124			OBJREC op1, op2;
125	greg	2.17	int i, n;
126	greg	2.14
127	greg	2.15	while (obj1 != obj2) {
128			if (obj1 == OVOID)
129			return(0);
130			if (obj2 == OVOID)
131			return(0);
132			op1 = objptr(obj1);
133			op2 = objptr(obj2);
134			if (op1->otype != op2->otype)
135			return(0);
136			if (op1->oargs.nsargs != op2->oargs.nsargs)
137			return(0);
138			if (op1->oargs.nfargs != op2->oargs.nfargs)
139			return(0);
140	greg	2.14	#ifdef IARGS
141	greg	2.15	if (op1->oargs.niargs != op2->oargs.niargs)
142	greg	2.14	return(0);
143	greg	2.15	for (i = op1->oargs.niargs; i-- > 0; )
144			if (op1->oargs.iarg[i] != op2->oargs.iarg[i])
145			return(0);
146	greg	2.14	#endif
147	greg	2.15	for (i = op1->oargs.nfargs; i-- > 0; )
148			if (!eqreal(op1->oargs.farg[i], op2->oargs.farg[i]))
149			return(0);
150	greg	2.17	n = 0;
151	greg	2.16	switch (op1->otype) { /* special cases (KEEP CONSISTENT!) */
152			case MOD_ALIAS:
153			case MAT_ILLUM:
154			case MAT_MIRROR:
155	greg	2.17	n = (op1->oargs.nsargs > 0);
156	greg	2.16	break;
157			case MIX_FUNC:
158			case MIX_DATA:
159			case MIX_TEXT:
160			case MIX_PICT:
161	greg	2.17	n = 2*(op1->oargs.nsargs >= 2);
162	greg	2.16	break;
163			case MAT_CLIP:
164	greg	2.17	n = op1->oargs.nsargs;
165	greg	2.16	break;
166			}
167	greg	2.17	/* check other string arguments */
168			for (i = op1->oargs.nsargs; i-- > n; )
169			if (strcmp(op1->oargs.sarg[i], op2->oargs.sarg[i]))
170			return(0);
171			while (n-- > 0) /* check modifier references */
172			if (!eqobjects( lastmod(obj1, op1->oargs.sarg[n]),
173			lastmod(obj2, op2->oargs.sarg[n]) ))
174	greg	2.16	return(0);
175	greg	2.15	obj1 = op1->omod;
176			obj2 = op2->omod;
177			}
178	greg	2.14	return(1);
179			}
180
181
182	greg	2.7	void
183	greg	2.13	insertobject( /* insert new object into our list */
184			OBJECT obj
185			)
186	greg	1.1	{
187	greg	2.13	int i;
188	greg	1.1
189			if (ismodifier(objptr(obj)->otype)) {
190			i = otndx(objptr(obj)->oname, &modtab);
191	greg	2.14	if (eqobjects(obj, modtab.htab[i]))
192	greg	2.16	return; /* don't index if same as earlier def. */
193	greg	1.1	modtab.htab[i] = obj;
194			}
195	greg	2.3	#ifdef GETOBJ
196			else {
197			i = otndx(objptr(obj)->oname, &objtab);
198			objtab.htab[i] = obj;
199			}
200			#endif
201	greg	1.1	for (i = 0; addobjnotify[i] != NULL; i++)
202			(*addobjnotify[i])(obj);
203			}
204
205
206	greg	2.7	void
207	greg	2.18	truncobjndx(void) /* remove bogus table entries past end */
208	greg	2.7	{
209	greg	2.18	int ndx;
210
211			if (nobjects <= 0) {
212			if (modtab.htab != NULL) {
213	greg	2.22	free(modtab.htab);
214	greg	2.18	modtab.htab = NULL;
215			modtab.hsiz = 100;
216			}
217			if (objtab.htab != NULL) {
218	greg	2.22	free(objtab.htab);
219	greg	2.18	objtab.htab = NULL;
220			objtab.hsiz = 100;
221			}
222			return;
223	greg	2.7	}
224	greg	2.18	for (ndx = modtab.hsiz*(modtab.htab != NULL); ndx--; )
225			if (modtab.htab[ndx] >= nobjects)
226			modtab.htab[ndx] = OVOID;
227
228			for (ndx = objtab.hsiz*(objtab.htab != NULL); ndx--; )
229			if (objtab.htab[ndx] >= nobjects)
230			objtab.htab[ndx] = OVOID;
231	greg	2.7	}
232
233
234	greg	1.1	static int
235	greg	2.13	nexthsiz( /* return next hash table size */
236			int oldsiz
237			)
238	greg	1.1	{
239			static int hsiztab[] = {
240	greg	2.19	251, 509, 1021, 2039, 4093, 8191, 16381,
241			32749, 65521, 131071, 262139, 0
242	greg	1.1	};
243	greg	2.13	int *hsp;
244	greg	1.1
245			for (hsp = hsiztab; *hsp; hsp++)
246			if (*hsp > oldsiz)
247			return(*hsp);
248			return(oldsiz2 + 1); / not always prime */
249			}
250
251
252			static int
253	greg	2.13	otndx( /* get object table index for name */
254			char *name,
255			struct ohtab *tab
256			)
257	greg	1.1	{
258	greg	2.19	char *onm;
259	greg	1.1	OBJECT *oldhtab;
260			int hval, i;
261	greg	2.13	int ndx;
262	greg	1.1
263			if (tab->htab == NULL) { /* new table */
264			tab->hsiz = nexthsiz(tab->hsiz);
265			tab->htab = (OBJECT )malloc(tab->hsizsizeof(OBJECT));
266			if (tab->htab == NULL)
267			error(SYSTEM, "out of memory in otndx");
268			ndx = tab->hsiz;
269			while (ndx--) /* empty it */
270			tab->htab[ndx] = OVOID;
271			}
272			/* look up object */
273			hval = shash(name);
274			tryagain:
275			for (i = 0; i < tab->hsiz; i++) {
276	greg	2.11	ndx = (hval + (unsigned long)i*i) % tab->hsiz;
277	greg	2.19	if (tab->htab[ndx] == OVOID)
278			return(ndx);
279			onm = objptr(tab->htab[ndx])->oname;
280			if (onm != NULL && !strcmp(onm, name))
281	greg	1.1	return(ndx);
282			}
283			/* table is full, reallocate */
284			oldhtab = tab->htab;
285			ndx = tab->hsiz;
286			tab->htab = NULL;
287			while (ndx--)
288			if (oldhtab[ndx] != OVOID) {
289	greg	2.19	onm = objptr(oldhtab[ndx])->oname;
290			if (onm == NULL)
291			continue;
292			i = otndx(onm, tab);
293	greg	1.1	tab->htab[i] = oldhtab[ndx];
294			}
295	greg	2.22	free(oldhtab);
296	greg	1.1	goto tryagain; /* should happen only once! */
297			}