cv/mgflib/lookup.h

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

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

#ifdef NOPROTO
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;
#else
typedef struct {
        unsigned long   (*hashf)(char *);       /* key hash function */
        int     (*keycmp)(const char *, const char *);  /* key comparison function */
        void    (*freek)(char *);       /* free a key */
        void    (*freed)(char *);       /* free the data */
        int     tsiz;           /* current table size */
        LUENT   *tabl;          /* table, if allocated */
        int     ndel;           /* number of deleted entries */
} LUTAB;
#endif

#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_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.
 */

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