src/common/lookup.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 * Table lookup routines
 */

/* ====================================================================
 * The Radiance Software License, Version 1.0
 *
 * Copyright (c) 1990 - 2002 The Regents of the University of California,
 * through Lawrence Berkeley National Laboratory.   All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *         notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *           if any, must include the following acknowledgment:
 *             "This product includes Radiance software
 *                 (http://radsite.lbl.gov/)
 *                 developed by the Lawrence Berkeley National Laboratory
 *               (http://www.lbl.gov/)."
 *       Alternately, this acknowledgment may appear in the software itself,
 *       if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
 *       and "The Regents of the University of California" must
 *       not be used to endorse or promote products derived from this
 *       software without prior written permission. For written
 *       permission, please contact [email protected].
 *
 * 5. Products derived from this software may not be called "Radiance",
 *       nor may "Radiance" appear in their name, without prior written
 *       permission of Lawrence Berkeley National Laboratory.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.   IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of Lawrence Berkeley National Laboratory.   For more
 * information on Lawrence Berkeley National Laboratory, please see
 * <http://www.lbl.gov/>.
 */

#include <stdio.h>
#include <stdlib.h>
#include "lookup.h"

#ifdef  NOSTRUCTASS
#define  copystruct(d,s)        bcopy((char *)(s),(char *)(d),sizeof(*(d)))
#else
#define  copystruct(d,s)        (*(d) = *(s))
#endif


int
lu_init(tbl, nel)               /* initialize tbl for at least nel elements */
register LUTAB  *tbl;
int     nel;
{
        static int  hsiztab[] = {
                31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 
                32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 
                4194301, 8388593, 0
        };
        register int  *hsp;

        nel += nel>>1;                  /* 66% occupancy */
        for (hsp = hsiztab; *hsp; hsp++)
                if (*hsp > nel)
                        break;
        if (!(tbl->tsiz = *hsp))
                tbl->tsiz = nel*2 + 1;          /* not always prime */
        tbl->tabl = (LUENT *)calloc(tbl->tsiz, sizeof(LUENT));
        if (tbl->tabl == NULL)
                tbl->tsiz = 0;
        tbl->ndel = 0;
        return(tbl->tsiz);
}


unsigned long
lu_shash(s)                     /* hash a nul-terminated string */
char    *s;
{
        static unsigned char shuffle[256] = {
                0, 157, 58, 215, 116, 17, 174, 75, 232, 133, 34,
                191, 92, 249, 150, 51, 208, 109, 10, 167, 68, 225,
                126, 27, 184, 85, 242, 143, 44, 201, 102, 3, 160,
                61, 218, 119, 20, 177, 78, 235, 136, 37, 194, 95,
                252, 153, 54, 211, 112, 13, 170, 71, 228, 129, 30,
                187, 88, 245, 146, 47, 204, 105, 6, 163, 64, 221,
                122, 23, 180, 81, 238, 139, 40, 197, 98, 255, 156,
                57, 214, 115, 16, 173, 74, 231, 132, 33, 190, 91,
                248, 149, 50, 207, 108, 9, 166, 67, 224, 125, 26,
                183, 84, 241, 142, 43, 200, 101, 2, 159, 60, 217,
                118, 19, 176, 77, 234, 135, 36, 193, 94, 251, 152,
                53, 210, 111, 12, 169, 70, 227, 128, 29, 186, 87,
                244, 145, 46, 203, 104, 5, 162, 63, 220, 121, 22,
                179, 80, 237, 138, 39, 196, 97, 254, 155, 56, 213,
                114, 15, 172, 73, 230, 131, 32, 189, 90, 247, 148,
                49, 206, 107, 8, 165, 66, 223, 124, 25, 182, 83,
                240, 141, 42, 199, 100, 1, 158, 59, 216, 117, 18,
                175, 76, 233, 134, 35, 192, 93, 250, 151, 52, 209,
                110, 11, 168, 69, 226, 127, 28, 185, 86, 243, 144,
                45, 202, 103, 4, 161, 62, 219, 120, 21, 178, 79,
                236, 137, 38, 195, 96, 253, 154, 55, 212, 113, 14,
                171, 72, 229, 130, 31, 188, 89, 246, 147, 48, 205,
                106, 7, 164, 65, 222, 123, 24, 181, 82, 239, 140,
                41, 198, 99
        };
        register int    i = 0;
        register unsigned long  h = 0;
        register unsigned char *t = (unsigned char *)s;

        while (*t)
                h ^= (unsigned long)shuffle[*t++] << ((i+=11) & 0xf);

        return(h);
}


LUENT *
lu_find(tbl, key)               /* find a table entry */
register LUTAB  *tbl;
char    *key;
{
        unsigned long   hval;
        int     i, n;
        register int    ndx;
        register LUENT  *le;
                                        /* look up object */
        if (tbl->tsiz == 0 && !lu_init(tbl, 1))
                return(NULL);
        hval = (*tbl->hashf)(key);
tryagain:
        ndx = hval % tbl->tsiz;
        for (i = 0, n = 1; i < tbl->tsiz; i++, n += 2) {
                le = &tbl->tabl[ndx];
                if (le->key == NULL) {
                        le->hval = hval;
                        return(le);
                }
                if (le->hval == hval && 
                      (tbl->keycmp == NULL || !(*tbl->keycmp)(le->key, key))) {
                        return(le);
                }
                if ((ndx += n) >= tbl->tsiz)    /* this happens rarely */
                        ndx = ndx % tbl->tsiz;
        }
                                        /* table is full, reallocate */
        le = tbl->tabl;
        ndx = tbl->tsiz;
        i = tbl->ndel;
        if (!lu_init(tbl, ndx-i+1)) {   /* no more memory! */
                tbl->tabl = le;
                tbl->tsiz = ndx;
                tbl->ndel = i;
                return(NULL);
        }
        /*
         * The following code may fail if the user has reclaimed many
         * deleted entries and the system runs out of memory in a
         * recursive call to lu_find().
         */
        while (ndx--)
                if (le[ndx].key != NULL)
                        if (le[ndx].data != NULL)
                                copystruct(lu_find(tbl,le[ndx].key), &le[ndx]);
                        else if (tbl->freek != NULL)
                                (*tbl->freek)(le[ndx].key);
        free((void *)le);
        goto tryagain;                  /* should happen only once! */
}


void
lu_delete(tbl, key)             /* delete a table entry */
register LUTAB  *tbl;
char    *key;
{
        register LUENT  *le;

        if ((le = lu_find(tbl, key)) == NULL)
                return;
        if (le->key == NULL || le->data == NULL)
                return;
        if (tbl->freed != NULL)
                (*tbl->freed)(le->data);
        le->data = NULL;
        tbl->ndel++;
}


int
lu_doall(tbl, f)                /* loop through all valid table entries */
register LUTAB  *tbl;
int     (*f)();
{
        int     rval = 0;
        register LUENT  *tp;

        for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
                if (tp->data != NULL)
                        if (f != NULL)
                                rval += (*f)(tp);
                        else
                                rval++;
        return(rval);
}


void
lu_done(tbl)                    /* free table and contents */
register LUTAB  *tbl;
{
        register LUENT  *tp;

        if (!tbl->tsiz)
                return;
        for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
                if (tp->key != NULL) {
                        if (tbl->freek != NULL)
                                (*tbl->freek)(tp->key);
                        if (tp->data != NULL && tbl->freed != NULL)
                                (*tbl->freed)(tp->data);
                }
        free((void *)tbl->tabl);
        tbl->tabl = NULL;
        tbl->tsiz = 0;
        tbl->ndel = 0;
}
Revision:	2.6
Committed:	Sat Feb 22 02:07:22 2003 UTC (21 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.5:	+61 -10 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	Content
1	#ifndef lint
2	static const char RCSid[] = "$Id$";
3	#endif
4	/*
5	* Table lookup routines
6	*/
7
8	/* ====================================================================
9	* The Radiance Software License, Version 1.0
10	*
11	* Copyright (c) 1990 - 2002 The Regents of the University of California,
12	* through Lawrence Berkeley National Laboratory. All rights reserved.
13	*
14	* Redistribution and use in source and binary forms, with or without
15	* modification, are permitted provided that the following conditions
16	* are met:
17	*
18	* 1. Redistributions of source code must retain the above copyright
19	* notice, this list of conditions and the following disclaimer.
20	*
21	* 2. Redistributions in binary form must reproduce the above copyright
22	* notice, this list of conditions and the following disclaimer in
23	* the documentation and/or other materials provided with the
24	* distribution.
25	*
26	* 3. The end-user documentation included with the redistribution,
27	* if any, must include the following acknowledgment:
28	* "This product includes Radiance software
29	* (http://radsite.lbl.gov/)
30	* developed by the Lawrence Berkeley National Laboratory
31	* (http://www.lbl.gov/)."
32	* Alternately, this acknowledgment may appear in the software itself,
33	* if and wherever such third-party acknowledgments normally appear.
34	*
35	* 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
36	* and "The Regents of the University of California" must
37	* not be used to endorse or promote products derived from this
38	* software without prior written permission. For written
39	* permission, please contact [email protected].
40	*
41	* 5. Products derived from this software may not be called "Radiance",
42	* nor may "Radiance" appear in their name, without prior written
43	* permission of Lawrence Berkeley National Laboratory.
44	*
45	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
46	* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
47	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
48	* DISCLAIMED. IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
49	* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
50	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
51	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
52	* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
53	* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
54	* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
55	* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
56	* SUCH DAMAGE.
57	* ====================================================================
58	*
59	* This software consists of voluntary contributions made by many
60	* individuals on behalf of Lawrence Berkeley National Laboratory. For more
61	* information on Lawrence Berkeley National Laboratory, please see
62	* <http://www.lbl.gov/>.
63	*/
64
65	#include <stdio.h>
66	#include <stdlib.h>
67	#include "lookup.h"
68
69	#ifdef NOSTRUCTASS
70	#define copystruct(d,s) bcopy((char )(s),(char )(d),sizeof(*(d)))
71	#else
72	#define copystruct(d,s) ((d) = (s))
73	#endif
74
75
76	int
77	lu_init(tbl, nel) /* initialize tbl for at least nel elements */
78	register LUTAB *tbl;
79	int nel;
80	{
81	static int hsiztab[] = {
82	31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381,
83	32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
84	4194301, 8388593, 0
85	};
86	register int *hsp;
87
88	nel += nel>>1; /* 66% occupancy */
89	for (hsp = hsiztab; *hsp; hsp++)
90	if (*hsp > nel)
91	break;
92	if (!(tbl->tsiz = *hsp))
93	tbl->tsiz = nel2 + 1; / not always prime */
94	tbl->tabl = (LUENT *)calloc(tbl->tsiz, sizeof(LUENT));
95	if (tbl->tabl == NULL)
96	tbl->tsiz = 0;
97	tbl->ndel = 0;
98	return(tbl->tsiz);
99	}
100
101
102	unsigned long
103	lu_shash(s) /* hash a nul-terminated string */
104	char *s;
105	{
106	static unsigned char shuffle[256] = {
107	0, 157, 58, 215, 116, 17, 174, 75, 232, 133, 34,
108	191, 92, 249, 150, 51, 208, 109, 10, 167, 68, 225,
109	126, 27, 184, 85, 242, 143, 44, 201, 102, 3, 160,
110	61, 218, 119, 20, 177, 78, 235, 136, 37, 194, 95,
111	252, 153, 54, 211, 112, 13, 170, 71, 228, 129, 30,
112	187, 88, 245, 146, 47, 204, 105, 6, 163, 64, 221,
113	122, 23, 180, 81, 238, 139, 40, 197, 98, 255, 156,
114	57, 214, 115, 16, 173, 74, 231, 132, 33, 190, 91,
115	248, 149, 50, 207, 108, 9, 166, 67, 224, 125, 26,
116	183, 84, 241, 142, 43, 200, 101, 2, 159, 60, 217,
117	118, 19, 176, 77, 234, 135, 36, 193, 94, 251, 152,
118	53, 210, 111, 12, 169, 70, 227, 128, 29, 186, 87,
119	244, 145, 46, 203, 104, 5, 162, 63, 220, 121, 22,
120	179, 80, 237, 138, 39, 196, 97, 254, 155, 56, 213,
121	114, 15, 172, 73, 230, 131, 32, 189, 90, 247, 148,
122	49, 206, 107, 8, 165, 66, 223, 124, 25, 182, 83,
123	240, 141, 42, 199, 100, 1, 158, 59, 216, 117, 18,
124	175, 76, 233, 134, 35, 192, 93, 250, 151, 52, 209,
125	110, 11, 168, 69, 226, 127, 28, 185, 86, 243, 144,
126	45, 202, 103, 4, 161, 62, 219, 120, 21, 178, 79,
127	236, 137, 38, 195, 96, 253, 154, 55, 212, 113, 14,
128	171, 72, 229, 130, 31, 188, 89, 246, 147, 48, 205,
129	106, 7, 164, 65, 222, 123, 24, 181, 82, 239, 140,
130	41, 198, 99
131	};
132	register int i = 0;
133	register unsigned long h = 0;
134	register unsigned char t = (unsigned char )s;
135
136	while (*t)
137	h ^= (unsigned long)shuffle[*t++] << ((i+=11) & 0xf);
138
139	return(h);
140	}
141
142
143	LUENT *
144	lu_find(tbl, key) /* find a table entry */
145	register LUTAB *tbl;
146	char *key;
147	{
148	unsigned long hval;
149	int i, n;
150	register int ndx;
151	register LUENT *le;
152	/* look up object */
153	if (tbl->tsiz == 0 && !lu_init(tbl, 1))
154	return(NULL);
155	hval = (*tbl->hashf)(key);
156	tryagain:
157	ndx = hval % tbl->tsiz;
158	for (i = 0, n = 1; i < tbl->tsiz; i++, n += 2) {
159	le = &tbl->tabl[ndx];
160	if (le->key == NULL) {
161	le->hval = hval;
162	return(le);
163	}
164	if (le->hval == hval &&
165	(tbl->keycmp == NULL \|\| !(*tbl->keycmp)(le->key, key))) {
166	return(le);
167	}
168	if ((ndx += n) >= tbl->tsiz) /* this happens rarely */
169	ndx = ndx % tbl->tsiz;
170	}
171	/* table is full, reallocate */
172	le = tbl->tabl;
173	ndx = tbl->tsiz;
174	i = tbl->ndel;
175	if (!lu_init(tbl, ndx-i+1)) { /* no more memory! */
176	tbl->tabl = le;
177	tbl->tsiz = ndx;
178	tbl->ndel = i;
179	return(NULL);
180	}
181	/*
182	* The following code may fail if the user has reclaimed many
183	* deleted entries and the system runs out of memory in a
184	* recursive call to lu_find().
185	*/
186	while (ndx--)
187	if (le[ndx].key != NULL)
188	if (le[ndx].data != NULL)
189	copystruct(lu_find(tbl,le[ndx].key), &le[ndx]);
190	else if (tbl->freek != NULL)
191	(*tbl->freek)(le[ndx].key);
192	free((void *)le);
193	goto tryagain; /* should happen only once! */
194	}
195
196
197	void
198	lu_delete(tbl, key) /* delete a table entry */
199	register LUTAB *tbl;
200	char *key;
201	{
202	register LUENT *le;
203
204	if ((le = lu_find(tbl, key)) == NULL)
205	return;
206	if (le->key == NULL \|\| le->data == NULL)
207	return;
208	if (tbl->freed != NULL)
209	(*tbl->freed)(le->data);
210	le->data = NULL;
211	tbl->ndel++;
212	}
213
214
215	int
216	lu_doall(tbl, f) /* loop through all valid table entries */
217	register LUTAB *tbl;
218	int (*f)();
219	{
220	int rval = 0;
221	register LUENT *tp;
222
223	for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
224	if (tp->data != NULL)
225	if (f != NULL)
226	rval += (*f)(tp);
227	else
228	rval++;
229	return(rval);
230	}
231
232
233	void
234	lu_done(tbl) /* free table and contents */
235	register LUTAB *tbl;
236	{
237	register LUENT *tp;
238
239	if (!tbl->tsiz)
240	return;
241	for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
242	if (tp->key != NULL) {
243	if (tbl->freek != NULL)
244	(*tbl->freek)(tp->key);
245	if (tp->data != NULL && tbl->freed != NULL)
246	(*tbl->freed)(tp->data);
247	}
248	free((void *)tbl->tabl);
249	tbl->tabl = NULL;
250	tbl->tsiz = 0;
251	tbl->ndel = 0;
252	}