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
#	User	Rev	Content
1	greg	2.1	#ifndef lint
2	greg	2.6	static const char RCSid[] = "$Id$";
3	greg	2.1	#endif
4			/*
5			* Table lookup routines
6			*/
7
8	greg	2.6	/* ====================================================================
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	greg	2.1	#include <stdio.h>
66	greg	2.6	#include <stdlib.h>
67	greg	2.1	#include "lookup.h"
68
69	gwlarson	2.5	#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	greg	2.1
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	gregl	2.3	31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381,
83			32749, 65521, 131071, 262139, 524287, 1048573, 2097143,
84			4194301, 8388593, 0
85	greg	2.1	};
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	gwlarson	2.5	unsigned long
103	greg	2.1	lu_shash(s) /* hash a nul-terminated string */
104	gregl	2.3	char *s;
105	greg	2.1	{
106	gregl	2.3	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	greg	2.1	register int i = 0;
133	gwlarson	2.5	register unsigned long h = 0;
134	gregl	2.3	register unsigned char t = (unsigned char )s;
135	greg	2.1
136	gregl	2.3	while (*t)
137	gwlarson	2.5	h ^= (unsigned long)shuffle[*t++] << ((i+=11) & 0xf);
138	gregl	2.3
139	greg	2.1	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	gwlarson	2.5	unsigned long hval;
149	gregl	2.3	int i, n;
150	greg	2.1	register int ndx;
151	gregl	2.3	register LUENT *le;
152	greg	2.1	/* look up object */
153	gwlarson	2.5	if (tbl->tsiz == 0 && !lu_init(tbl, 1))
154			return(NULL);
155	greg	2.1	hval = (*tbl->hashf)(key);
156			tryagain:
157	gregl	2.3	ndx = hval % tbl->tsiz;
158			for (i = 0, n = 1; i < tbl->tsiz; i++, n += 2) {
159	gwlarson	2.5	le = &tbl->tabl[ndx];
160	gregl	2.3	if (le->key == NULL) {
161			le->hval = hval;
162			return(le);
163	greg	2.1	}
164	gregl	2.3	if (le->hval == hval &&
165			(tbl->keycmp == NULL \|\| !(*tbl->keycmp)(le->key, key))) {
166			return(le);
167			}
168	gwlarson	2.5	if ((ndx += n) >= tbl->tsiz) /* this happens rarely */
169	gregl	2.3	ndx = ndx % tbl->tsiz;
170	greg	2.1	}
171			/* table is full, reallocate */
172	gregl	2.3	le = tbl->tabl;
173	greg	2.1	ndx = tbl->tsiz;
174			i = tbl->ndel;
175	greg	2.2	if (!lu_init(tbl, ndx-i+1)) { /* no more memory! */
176	gregl	2.3	tbl->tabl = le;
177	greg	2.1	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	gregl	2.3	if (le[ndx].key != NULL)
188			if (le[ndx].data != NULL)
189	gwlarson	2.5	copystruct(lu_find(tbl,le[ndx].key), &le[ndx]);
190	greg	2.1	else if (tbl->freek != NULL)
191	gregl	2.3	(*tbl->freek)(le[ndx].key);
192	greg	2.6	free((void *)le);
193	greg	2.1	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	gwlarson	2.4	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	greg	2.1	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	greg	2.6	free((void *)tbl->tabl);
249	greg	2.1	tbl->tabl = NULL;
250			tbl->tsiz = 0;
251			tbl->ndel = 0;
252			}