| 1 |
greg |
2.13 |
/* RCSid $Id: lookup.h,v 2.12 2004/03/28 20:33:12 schorsch Exp $ */
|
| 2 |
greg |
2.1 |
/*
|
| 3 |
|
|
* Header file for general associative table lookup routines
|
| 4 |
|
|
*/
|
| 5 |
schorsch |
2.8 |
#ifndef _RAD_LOOKUP_H_
|
| 6 |
|
|
#define _RAD_LOOKUP_H_
|
| 7 |
schorsch |
2.10 |
|
| 8 |
|
|
#include <string.h> /* strcmp() */
|
| 9 |
|
|
|
| 10 |
schorsch |
2.8 |
#ifdef __cplusplus
|
| 11 |
|
|
extern "C" {
|
| 12 |
|
|
#endif
|
| 13 |
greg |
2.6 |
|
| 14 |
schorsch |
2.12 |
typedef void lut_free_t(void *p);
|
| 15 |
|
|
typedef unsigned long lut_hashf_t(void*);
|
| 16 |
|
|
typedef int lut_keycmpf_t(const void*, const void*);
|
| 17 |
schorsch |
2.11 |
|
| 18 |
greg |
2.1 |
typedef struct {
|
| 19 |
gwlarson |
2.5 |
char *key; /* key name */
|
| 20 |
|
|
unsigned long hval; /* key hash value (for efficiency) */
|
| 21 |
|
|
char *data; /* pointer to client data */
|
| 22 |
greg |
2.1 |
} LUENT;
|
| 23 |
|
|
|
| 24 |
|
|
typedef struct {
|
| 25 |
schorsch |
2.12 |
lut_hashf_t *hashf; /* key hash function */
|
| 26 |
|
|
lut_keycmpf_t *keycmp; /* key comparison function */
|
| 27 |
schorsch |
2.11 |
lut_free_t *freek; /* free a key */
|
| 28 |
|
|
lut_free_t *freed; /* free the data */
|
| 29 |
gwlarson |
2.5 |
int tsiz; /* current table size */
|
| 30 |
|
|
LUENT *tabl; /* table, if allocated */
|
| 31 |
|
|
int ndel; /* number of deleted entries */
|
| 32 |
greg |
2.1 |
} LUTAB;
|
| 33 |
|
|
|
| 34 |
|
|
|
| 35 |
|
|
/*
|
| 36 |
|
|
* The lu_init routine is called to initialize a table. The number of
|
| 37 |
|
|
* elements passed is not a limiting factor, as a table can grow to
|
| 38 |
|
|
* any size permitted by memory. However, access will be more efficient
|
| 39 |
|
|
* if this number strikes a reasonable balance between default memory use
|
| 40 |
|
|
* and the expected (minimum) table size. The value returned is the
|
| 41 |
|
|
* actual allocated table size (or zero if there was insufficient memory).
|
| 42 |
|
|
*
|
| 43 |
|
|
* The hashf, keycmp, freek and freed member functions must be assigned
|
| 44 |
|
|
* separately. If the hash value is sufficient to guarantee equality
|
| 45 |
|
|
* between keys, then the keycmp pointer may be NULL. Otherwise, it
|
| 46 |
|
|
* should return 0 if the two passed keys match. If it is not necessary
|
| 47 |
|
|
* (or possible) to free the key and/or data values, then the freek and/or
|
| 48 |
|
|
* freed member functions may be NULL.
|
| 49 |
|
|
*
|
| 50 |
|
|
* It isn't fully necessary to call lu_init to initialize the LUTAB structure.
|
| 51 |
|
|
* If tsiz is 0, then the first call to lu_find will allocate a minimal table.
|
| 52 |
|
|
* The LU_SINIT macro provides a convenient static declaration for character
|
| 53 |
|
|
* string keys.
|
| 54 |
|
|
*
|
| 55 |
|
|
* The lu_find routine returns the entry corresponding to the given
|
| 56 |
|
|
* key. If the entry does not exist, the corresponding key field will
|
| 57 |
|
|
* be NULL. If the entry has been previously deleted but not yet freed,
|
| 58 |
|
|
* then only the data field will be NULL. It is the caller's
|
| 59 |
|
|
* responsibility to (allocate and) assign the key and data fields when
|
| 60 |
|
|
* creating a new entry. The only case where lu_find returns NULL is when
|
| 61 |
|
|
* the system has run out of memory.
|
| 62 |
|
|
*
|
| 63 |
|
|
* The lu_delete routine frees an entry's data (if any) by calling
|
| 64 |
|
|
* the freed member function, but does not free the key field. This
|
| 65 |
|
|
* will be freed later during (or instead of) table reallocation.
|
| 66 |
greg |
2.2 |
* It is therefore an error to reuse or do anything with the key
|
| 67 |
|
|
* field after calling lu_delete.
|
| 68 |
greg |
2.1 |
*
|
| 69 |
gwlarson |
2.4 |
* The lu_doall routine loops through every filled table entry, calling
|
| 70 |
|
|
* the given function once on each entry. If a NULL pointer is passed
|
| 71 |
|
|
* for this function, then lu_doall simply returns the total number of
|
| 72 |
|
|
* active entries. Otherwise, it returns the sum of all the function
|
| 73 |
|
|
* evaluations.
|
| 74 |
|
|
*
|
| 75 |
greg |
2.1 |
* The lu_done routine calls the given free function once for each
|
| 76 |
|
|
* assigned table entry (i.e. each entry with an assigned key value).
|
| 77 |
|
|
* The user must define these routines to free the key and the data
|
| 78 |
|
|
* in the LU_TAB structure. The final action of lu_done is to free the
|
| 79 |
|
|
* allocated table itself.
|
| 80 |
|
|
*/
|
| 81 |
greg |
2.6 |
|
| 82 |
greg |
2.13 |
typedef int lut_doallf_t(LUENT *e, void *p);
|
| 83 |
schorsch |
2.12 |
|
| 84 |
|
|
extern lut_keycmpf_t lu_strcmp;
|
| 85 |
greg |
2.6 |
extern int lu_init(LUTAB *tbl, int nel);
|
| 86 |
schorsch |
2.12 |
extern unsigned long lu_shash(void *s);
|
| 87 |
greg |
2.6 |
extern LUENT *lu_find(LUTAB *tbl, char *key);
|
| 88 |
|
|
extern void lu_delete(LUTAB *tbl, char *key);
|
| 89 |
greg |
2.13 |
extern int lu_doall(LUTAB *tbl, lut_doallf_t *f, void *p);
|
| 90 |
greg |
2.6 |
extern void lu_done(LUTAB *tbl);
|
| 91 |
|
|
|
| 92 |
schorsch |
2.12 |
#define LU_SINIT(fk,fd) {lu_shash,lu_strcmp,fk,fd,0,NULL,0}
|
| 93 |
schorsch |
2.8 |
|
| 94 |
|
|
#ifdef __cplusplus
|
| 95 |
|
|
}
|
| 96 |
greg |
2.6 |
#endif
|
| 97 |
schorsch |
2.8 |
#endif /* _RAD_LOOKUP_H_ */
|
| 98 |
|
|
|
