ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/Development/ray/src/common/lookup.c

Comparing ray/src/common/lookup.c (file contents):
Revision 2.3 by gregl, Wed Dec 3 10:59:30 1997 UTC vs.
Revision 2.19 by greg, Sun Feb 9 00:08:18 2014 UTC

#	Line 1 | Line 1
1	–	/* Copyright (c) 1997 Silicon Graphics, Inc. */
2	–
1		#ifndef lint
2	<	static char SCCSid[] = "$SunId$ SGI";
2	>	static const char       RCSid[] = "$Id$";
3		#endif
6	–
4		/*
5		* Table lookup routines
6		*/
7
8		#include <stdio.h>
9	+	#include <stdlib.h>
10	+	#include <string.h>
11	+
12		#include "lookup.h"
13
14	–	#define MEM_PTR         char *
14
16	–	extern MEM_PTR  calloc();
17	–
18	–
15		int
16	<	lu_init(tbl, nel)               /* initialize tbl for at least nel elements */
17	<	register LUTAB  *tbl;
18	<	int     nel;
16	>	lu_init(                /* initialize tbl for at least nel elements */
17	>	LUTAB   *tbl,
18	>	int     nel
19	>	)
20		{
21		static int  hsiztab[] = {
22		31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381,
23		32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
24		4194301, 8388593, 0
25		};
26	<	register int  *hsp;
26	>	int  *hsp;
27
28		nel += nel>>1;                  /* 66% occupancy */
29		for (hsp = hsiztab; *hsp; hsp++)
#	Line 42 | Line 39 | int    nel;
39		}
40
41
42	<	long
43	<	lu_shash(s)                     /* hash a nul-terminated string */
44	<	char    *s;
42	>	unsigned long
43	>	lu_shash(                       /* hash a nul-terminated string */
44	>	const char      *s
45	>	)
46		{
47		static unsigned char shuffle[256] = {
48		0, 157, 58, 215, 116, 17, 174, 75, 232, 133, 34,
#	Line 72 | Line 70 | char   *s;
70		106, 7, 164, 65, 222, 123, 24, 181, 82, 239, 140,
71		41, 198, 99
72		};
73	<	register int    i = 0;
74	<	register long   h = 0;
75	<	register unsigned char *t = (unsigned char *)s;
73	>	int                     i = 0;
74	>	unsigned long           h = 0;
75	>	unsigned const char     *t = (unsigned const char *)s;
76
77		while (*t)
78	<	h ^= (long)shuffle[*t++] << ((i+=11) & 0xf);
78	>	h ^= (unsigned long)shuffle[*t++] << ((i+=11) & 0xf);
79
80		return(h);
81		}
82
83
84		LUENT *
85	<	lu_find(tbl, key)               /* find a table entry */
86	<	register LUTAB  *tbl;
87	<	char    *key;
85	>	lu_find(                /* find a table entry */
86	>	LUTAB   *tbl,
87	>	const char      *key
88	>	)
89		{
90	<	long    hval;
90	>	unsigned long   hval;
91		int     i, n;
92	<	register int    ndx;
93	<	register LUENT  *le;
92	>	int     ndx;
93	>	LUENT   *le;
94		/* look up object */
95	<	if (tbl->tsiz == 0)
96	<	lu_init(tbl, 1);
95	>	if (tbl->tsiz == 0 && !lu_init(tbl, 1))
96	>	return(NULL);
97		hval = (*tbl->hashf)(key);
98		tryagain:
99		ndx = hval % tbl->tsiz;
101	–	le = &tbl->tabl[ndx];
100		for (i = 0, n = 1; i < tbl->tsiz; i++, n += 2) {
101	+	le = &tbl->tabl[ndx];
102		if (le->key == NULL) {
103		le->hval = hval;
104		return(le);
#	Line 108 | Line 107 | tryagain:
107		(tbl->keycmp == NULL || !(*tbl->keycmp)(le->key, key))) {
108		return(le);
109		}
110	<	le += n;
112	<	if ((ndx += n) >= tbl->tsiz) {  /* this happens rarely */
110	>	if ((ndx += n) >= tbl->tsiz)    /* this happens rarely */
111		ndx = ndx % tbl->tsiz;
114	–	le = &tbl->tabl[ndx];
115	–	}
112		}
113		/* table is full, reallocate */
114		le = tbl->tabl;
#	Line 124 | Line 120 | tryagain:
120		tbl->ndel = i;
121		return(NULL);
122		}
127	–	if (!ndx)
128	–	goto tryagain;
123		/*
124		* The following code may fail if the user has reclaimed many
125		* deleted entries and the system runs out of memory in a
126		* recursive call to lu_find().
127		*/
128		while (ndx--)
129	<	if (le[ndx].key != NULL)
129	>	if (le[ndx].key != NULL) {
130		if (le[ndx].data != NULL)
131	<	*lu_find(tbl, le[ndx].key) = le[ndx];
131	>	*lu_find(tbl,le[ndx].key) = le[ndx];
132		else if (tbl->freek != NULL)
133		(*tbl->freek)(le[ndx].key);
134	<	free((MEM_PTR)le);
134	>	}
135	>	free((void *)le);
136		goto tryagain;                  /* should happen only once! */
137		}
138
139
140		void
141	<	lu_delete(tbl, key)             /* delete a table entry */
142	<	register LUTAB  *tbl;
143	<	char    *key;
141	>	lu_delete(              /* delete a table entry */
142	>	LUTAB *tbl,
143	>	const char *key
144	>	)
145		{
146	<	register LUENT  *le;
146	>	LUENT   *le;
147
148		if ((le = lu_find(tbl, key)) == NULL)
149		return;
#	Line 160 | Line 156 | char   *key;
156		}
157
158
159	+	int
160	+	lu_doall(               /* loop through all valid table entries */
161	+	const LUTAB *tbl,
162	+	/* int  (*f)(const LUENT *, void *) */
163	+	lut_doallf_t *f,
164	+	void *p
165	+	)
166	+	{
167	+	int     rval = 0;
168	+	const LUENT     *tp;
169	+
170	+	for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
171	+	if (tp->data != NULL) {
172	+	if (f != NULL) {
173	+	int     r = (*f)(tp, p);
174	+	if (r < 0)
175	+	return(-1);
176	+	rval += r;
177	+	} else
178	+	rval++;
179	+	}
180	+	return(rval);
181	+	}
182	+
183	+
184		void
185	<	lu_done(tbl)                    /* free table and contents */
186	<	register LUTAB  *tbl;
185	>	lu_done(                        /* free table and contents */
186	>	LUTAB   *tbl
187	>	)
188		{
189	<	register LUENT  *tp;
189	>	LUENT   *tp;
190
191		if (!tbl->tsiz)
192		return;
#	Line 175 | Line 197 | register LUTAB *tbl;
197		if (tp->data != NULL && tbl->freed != NULL)
198		(*tbl->freed)(tp->data);
199		}
200	<	free((MEM_PTR)tbl->tabl);
200	>	free((void *)tbl->tabl);
201		tbl->tabl = NULL;
202		tbl->tsiz = 0;
203		tbl->ndel = 0;

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines (old)
>	Changed lines (new)