Back to index

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