src/common/lookup.h

/* RCSid: $Id$ */
/*
 * Header file for general associative 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/>.
 */

typedef struct {
        char    *key;                   /* key name */
        unsigned long   hval;           /* key hash value (for efficiency) */
        char    *data;                  /* pointer to client data */
} LUENT;

typedef struct {
        unsigned long   (*hashf)();     /* key hash function */
        int     (*keycmp)();            /* key comparison function */
        void    (*freek)();             /* free a key */
        void    (*freed)();             /* free the data */
        int     tsiz;                   /* current table size */
        LUENT   *tabl;                  /* table, if allocated */
        int     ndel;                   /* number of deleted entries */
} LUTAB;

#undef strcmp
#define LU_SINIT(fk,fd)         {lu_shash,strcmp,(void (*)())(fk),\
                                (void (*)())(fd),0,NULL,0}

/*
 * The lu_init routine is called to initialize a table.  The number of
 * elements passed is not a limiting factor, as a table can grow to
 * any size permitted by memory.  However, access will be more efficient
 * if this number strikes a reasonable balance between default memory use
 * and the expected (minimum) table size.  The value returned is the
 * actual allocated table size (or zero if there was insufficient memory).
 *
 * The hashf, keycmp, freek and freed member functions must be assigned
 * separately.  If the hash value is sufficient to guarantee equality
 * between keys, then the keycmp pointer may be NULL.  Otherwise, it
 * should return 0 if the two passed keys match.  If it is not necessary
 * (or possible) to free the key and/or data values, then the freek and/or
 * freed member functions may be NULL.
 *
 * It isn't fully necessary to call lu_init to initialize the LUTAB structure.
 * If tsiz is 0, then the first call to lu_find will allocate a minimal table.
 * The LU_SINIT macro provides a convenient static declaration for character
 * string keys.
 *
 * The lu_find routine returns the entry corresponding to the given
 * key.  If the entry does not exist, the corresponding key field will
 * be NULL.  If the entry has been previously deleted but not yet freed,
 * then only the data field will be NULL.  It is the caller's
 * responsibility to (allocate and) assign the key and data fields when
 * creating a new entry.  The only case where lu_find returns NULL is when
 * the system has run out of memory.
 *
 * The lu_delete routine frees an entry's data (if any) by calling
 * the freed member function, but does not free the key field.  This
 * will be freed later during (or instead of) table reallocation.
 * It is therefore an error to reuse or do anything with the key
 * field after calling lu_delete.
 *
 * The lu_doall routine loops through every filled table entry, calling
 * the given function once on each entry.  If a NULL pointer is passed
 * for this function, then lu_doall simply returns the total number of
 * active entries.  Otherwise, it returns the sum of all the function
 * evaluations.
 *
 * The lu_done routine calls the given free function once for each
 * assigned table entry (i.e. each entry with an assigned key value).
 * The user must define these routines to free the key and the data
 * in the LU_TAB structure.  The final action of lu_done is to free the
 * allocated table itself.
 */

extern int      strcmp();

#ifdef NOPROTO

extern int      lu_init();
extern LUENT    *lu_find();
extern void     lu_delete();
extern int      lu_doall();
extern void     lu_done();
extern unsigned long    lu_shash();

#else

extern int      lu_init(LUTAB *tbl, int nel);
extern unsigned long    lu_shash(char *s);
extern LUENT    *lu_find(LUTAB *tbl, char *key);
extern void     lu_delete(LUTAB *tbl, char *key);
extern int      lu_doall(LUTAB *tbl, int (*f)());
extern void     lu_done(LUTAB *tbl);

#endif
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:	+72 -5 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	/* RCSid: $Id$ */
2	/*
3	* Header file for general associative table lookup routines
4	*/
5
6	/* ====================================================================
7	* The Radiance Software License, Version 1.0
8	*
9	* Copyright (c) 1990 - 2002 The Regents of the University of California,
10	* through Lawrence Berkeley National Laboratory. All rights reserved.
11	*
12	* Redistribution and use in source and binary forms, with or without
13	* modification, are permitted provided that the following conditions
14	* are met:
15	*
16	* 1. Redistributions of source code must retain the above copyright
17	* notice, this list of conditions and the following disclaimer.
18	*
19	* 2. Redistributions in binary form must reproduce the above copyright
20	* notice, this list of conditions and the following disclaimer in
21	* the documentation and/or other materials provided with the
22	* distribution.
23	*
24	* 3. The end-user documentation included with the redistribution,
25	* if any, must include the following acknowledgment:
26	* "This product includes Radiance software
27	* (http://radsite.lbl.gov/)
28	* developed by the Lawrence Berkeley National Laboratory
29	* (http://www.lbl.gov/)."
30	* Alternately, this acknowledgment may appear in the software itself,
31	* if and wherever such third-party acknowledgments normally appear.
32	*
33	* 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
34	* and "The Regents of the University of California" must
35	* not be used to endorse or promote products derived from this
36	* software without prior written permission. For written
37	* permission, please contact [email protected].
38	*
39	* 5. Products derived from this software may not be called "Radiance",
40	* nor may "Radiance" appear in their name, without prior written
41	* permission of Lawrence Berkeley National Laboratory.
42	*
43	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
44	* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
45	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
46	* DISCLAIMED. IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
47	* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
48	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
49	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
50	* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
51	* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
52	* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
53	* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
54	* SUCH DAMAGE.
55	* ====================================================================
56	*
57	* This software consists of voluntary contributions made by many
58	* individuals on behalf of Lawrence Berkeley National Laboratory. For more
59	* information on Lawrence Berkeley National Laboratory, please see
60	* <http://www.lbl.gov/>.
61	*/
62
63	typedef struct {
64	char key; / key name */
65	unsigned long hval; /* key hash value (for efficiency) */
66	char data; / pointer to client data */
67	} LUENT;
68
69	typedef struct {
70	unsigned long (hashf)(); / key hash function */
71	int (keycmp)(); / key comparison function */
72	void (freek)(); / free a key */
73	void (freed)(); / free the data */
74	int tsiz; /* current table size */
75	LUENT tabl; / table, if allocated */
76	int ndel; /* number of deleted entries */
77	} LUTAB;
78
79	#undef strcmp
80	#define LU_SINIT(fk,fd) {lu_shash,strcmp,(void (*)())(fk),\
81	(void (*)())(fd),0,NULL,0}
82
83	/*
84	* The lu_init routine is called to initialize a table. The number of
85	* elements passed is not a limiting factor, as a table can grow to
86	* any size permitted by memory. However, access will be more efficient
87	* if this number strikes a reasonable balance between default memory use
88	* and the expected (minimum) table size. The value returned is the
89	* actual allocated table size (or zero if there was insufficient memory).
90	*
91	* The hashf, keycmp, freek and freed member functions must be assigned
92	* separately. If the hash value is sufficient to guarantee equality
93	* between keys, then the keycmp pointer may be NULL. Otherwise, it
94	* should return 0 if the two passed keys match. If it is not necessary
95	* (or possible) to free the key and/or data values, then the freek and/or
96	* freed member functions may be NULL.
97	*
98	* It isn't fully necessary to call lu_init to initialize the LUTAB structure.
99	* If tsiz is 0, then the first call to lu_find will allocate a minimal table.
100	* The LU_SINIT macro provides a convenient static declaration for character
101	* string keys.
102	*
103	* The lu_find routine returns the entry corresponding to the given
104	* key. If the entry does not exist, the corresponding key field will
105	* be NULL. If the entry has been previously deleted but not yet freed,
106	* then only the data field will be NULL. It is the caller's
107	* responsibility to (allocate and) assign the key and data fields when
108	* creating a new entry. The only case where lu_find returns NULL is when
109	* the system has run out of memory.
110	*
111	* The lu_delete routine frees an entry's data (if any) by calling
112	* the freed member function, but does not free the key field. This
113	* will be freed later during (or instead of) table reallocation.
114	* It is therefore an error to reuse or do anything with the key
115	* field after calling lu_delete.
116	*
117	* The lu_doall routine loops through every filled table entry, calling
118	* the given function once on each entry. If a NULL pointer is passed
119	* for this function, then lu_doall simply returns the total number of
120	* active entries. Otherwise, it returns the sum of all the function
121	* evaluations.
122	*
123	* The lu_done routine calls the given free function once for each
124	* assigned table entry (i.e. each entry with an assigned key value).
125	* The user must define these routines to free the key and the data
126	* in the LU_TAB structure. The final action of lu_done is to free the
127	* allocated table itself.
128	*/
129
130	extern int strcmp();
131
132	#ifdef NOPROTO
133
134	extern int lu_init();
135	extern LUENT *lu_find();
136	extern void lu_delete();
137	extern int lu_doall();
138	extern void lu_done();
139	extern unsigned long lu_shash();
140
141	#else
142
143	extern int lu_init(LUTAB *tbl, int nel);
144	extern unsigned long lu_shash(char *s);
145	extern LUENT lu_find(LUTAB tbl, char *key);
146	extern void lu_delete(LUTAB tbl, char key);
147	extern int lu_doall(LUTAB tbl, int (f)());
148	extern void lu_done(LUTAB *tbl);
149
150	#endif