src/common/lookup.h

/* RCSid $Id$ */
/*
 * Header file for general associative table lookup routines
 */

#include "copyright.h"

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