Back to index

radiance  4R0+20100331
lookup.h
Go to the documentation of this file.
00001 /* RCSid $Id: lookup.h,v 2.14 2004/05/25 22:04:13 greg Exp $ */
00002 /*
00003  * Header file for general associative table lookup routines
00004  */
00005 #ifndef _RAD_LOOKUP_H_
00006 #define _RAD_LOOKUP_H_
00007 
00008 #ifdef __cplusplus
00009 extern "C" {
00010 #endif
00011 
00012 typedef void lut_free_t(void *p);
00013 typedef unsigned long lut_hashf_t(const void *);
00014 typedef int lut_keycmpf_t(const void *, const void *);
00015 
00016 typedef struct {
00017        char   *key;                /* key name */
00018        unsigned long hval;         /* key hash value (for efficiency) */
00019        char   *data;               /* pointer to client data */
00020 } LUENT;
00021 
00022 typedef struct {
00023        lut_hashf_t *hashf;  /* key hash function */
00024        lut_keycmpf_t *keycmp;      /* key comparison function */
00025        lut_free_t *freek;          /* free a key */
00026        lut_free_t *freed;          /* free the data */
00027        int    tsiz;                /* current table size */
00028        LUENT  *tabl;               /* table, if allocated */
00029        int    ndel;                /* number of deleted entries */
00030 } LUTAB;
00031 
00032 
00033 /*
00034  * The lu_init routine is called to initialize a table.  The number of
00035  * elements passed is not a limiting factor, as a table can grow to
00036  * any size permitted by memory.  However, access will be more efficient
00037  * if this number strikes a reasonable balance between default memory use
00038  * and the expected (minimum) table size.  The value returned is the
00039  * actual allocated table size (or zero if there was insufficient memory).
00040  *
00041  * The hashf, keycmp, freek and freed member functions must be assigned
00042  * separately.  If the hash value is sufficient to guarantee equality
00043  * between keys, then the keycmp pointer may be NULL.  Otherwise, it
00044  * should return 0 if the two passed keys match.  If it is not necessary
00045  * (or possible) to free the key and/or data values, then the freek and/or
00046  * freed member functions may be NULL.
00047  *
00048  * It isn't fully necessary to call lu_init to initialize the LUTAB structure.
00049  * If tsiz is 0, then the first call to lu_find will allocate a minimal table.
00050  * The LU_SINIT macro provides a convenient static declaration for character
00051  * string keys.
00052  *
00053  * The lu_find routine returns the entry corresponding to the given
00054  * key.  If the entry does not exist, the corresponding key field will
00055  * be NULL.  If the entry has been previously deleted but not yet freed,
00056  * then only the data field will be NULL.  It is the caller's
00057  * responsibility to (allocate and) assign the key and data fields when
00058  * creating a new entry.  The only case where lu_find returns NULL is when
00059  * the system has run out of memory.
00060  *
00061  * The lu_delete routine frees an entry's data (if any) by calling
00062  * the freed member function, but does not free the key field.  This
00063  * will be freed later during (or instead of) table reallocation.
00064  * It is therefore an error to reuse or do anything with the key
00065  * field after calling lu_delete.
00066  *
00067  * The lu_doall routine loops through every filled table entry, calling
00068  * the given function once on each entry.  If a NULL pointer is passed
00069  * for this function, then lu_doall simply returns the total number of
00070  * active entries.  Otherwise, it returns the sum of all the function
00071  * evaluations.
00072  *
00073  * The lu_done routine calls the given free function once for each
00074  * assigned table entry (i.e. each entry with an assigned key value).
00075  * The user must define these routines to free the key and the data
00076  * in the LU_TAB structure.  The final action of lu_done is to free the
00077  * allocated table itself.
00078  */
00079 
00080 typedef int lut_doallf_t(const LUENT *e, void *p);
00081 
00082 extern lut_keycmpf_t lu_strcmp;
00083 extern int    lu_init(LUTAB *tbl, int nel);
00084 extern unsigned long lu_shash(const void *s);
00085 extern LUENT  *lu_find(LUTAB *tbl, const char *key);
00086 extern void   lu_delete(LUTAB *tbl, const char *key);
00087 extern int    lu_doall(const LUTAB *tbl, lut_doallf_t *f, void *p);
00088 extern void   lu_done(LUTAB *tbl);
00089 
00090 #define LU_SINIT(fk,fd) {lu_shash,lu_strcmp,fk,fd,0,NULL,0}
00091 
00092 #ifdef __cplusplus
00093 }
00094 #endif
00095 #endif /* _RAD_LOOKUP_H_ */
00096