4 * Copyright Metaparadigm Pte. Ltd. 2004.
5 * Michael Clark <michael@metaparadigm.com>
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public (LGPL)
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details: http://www.gnu.org/
23 * golden prime used in hash functions
25 #define LH_PRIME 0x9e370001UL
28 * sentinel pointer value for empty slots
30 #define LH_EMPTY (void*)-1
33 * sentinel pointer value for freed slots
35 #define LH_FREED (void*)-2
42 * callback function prototypes
44 typedef void (lh_entry_free_fn) (struct lh_entry *e);
46 * callback function prototypes
48 typedef unsigned long (lh_hash_fn) (void *k);
50 * callback function prototypes
52 typedef int (lh_equal_fn) (void *k1, void *k2);
55 * An entry in the hash table
69 struct lh_entry *next;
73 struct lh_entry *prev;
78 * The hash table structure.
91 * Number of collisions.
116 * Name of the hash table.
123 struct lh_entry *head;
128 struct lh_entry *tail;
130 struct lh_entry *table;
133 * A pointer onto the function responsible for freeing an entry.
135 lh_entry_free_fn *free_fn;
137 lh_equal_fn *equal_fn;
142 * Pre-defined hash and equality functions
144 extern unsigned long lh_ptr_hash(void *k);
145 extern int lh_ptr_equal(void *k1, void *k2);
147 extern unsigned long lh_char_hash(void *k);
148 extern int lh_char_equal(void *k1, void *k2);
152 * Convenience list iterator.
154 #define lh_foreach(table, entry) \
155 for(entry = table->head; entry; entry = entry->next)
158 * lh_foreach_safe allows calling of deletion routine while iterating.
160 #define lh_foreach_safe(table, entry, tmp) \
161 for(entry = table->head; entry && ((tmp = entry->next) || 1); entry = tmp)
166 * Create a new linkhash table.
167 * @param size initial table size. The table is automatically resized
168 * although this incurs a performance penalty.
169 * @param name the table name.
170 * @param free_fn callback function used to free memory for entries
171 * when lh_table_free or lh_table_delete is called.
172 * If NULL is provided, then memory for keys and values
173 * must be freed by the caller.
174 * @param hash_fn function used to hash keys. 2 standard ones are defined:
175 * lh_ptr_hash and lh_char_hash for hashing pointer values
176 * and C strings respectively.
177 * @param equal_fn comparison function to compare keys. 2 standard ones defined:
178 * lh_ptr_hash and lh_char_hash for comparing pointer values
179 * and C strings respectively.
180 * @return a pointer onto the linkhash table.
182 extern struct lh_table* lh_table_new(int size, char *name,
183 lh_entry_free_fn *free_fn,
185 lh_equal_fn *equal_fn);
188 * Convenience function to create a new linkhash
189 * table with char keys.
190 * @param size initial table size.
191 * @param name table name.
192 * @param free_fn callback function used to free memory for entries.
193 * @return a pointer onto the linkhash table.
195 extern struct lh_table* lh_kchar_table_new(int size, char *name,
196 lh_entry_free_fn *free_fn);
200 * Convenience function to create a new linkhash
201 * table with ptr keys.
202 * @param size initial table size.
203 * @param name table name.
204 * @param free_fn callback function used to free memory for entries.
205 * @return a pointer onto the linkhash table.
207 extern struct lh_table* lh_kptr_table_new(int size, char *name,
208 lh_entry_free_fn *free_fn);
212 * Free a linkhash table.
213 * If a callback free function is provided then it is called for all
214 * entries in the table.
215 * @param t table to free.
217 extern void lh_table_free(struct lh_table *t);
221 * Insert a record into the table.
222 * @param t the table to insert into.
223 * @param k a pointer to the key to insert.
224 * @param v a pointer to the value to insert.
226 extern int lh_table_insert(struct lh_table *t, void *k, void *v);
230 * Lookup a record into the table.
231 * @param t the table to lookup
232 * @param k a pointer to the key to lookup
233 * @return a pointer to the record structure of the value or NULL if it does not exist.
235 extern struct lh_entry* lh_table_lookup_entry(struct lh_table *t, void *k);
238 * Lookup a record into the table
239 * @param t the table to lookup
240 * @param k a pointer to the key to lookup
241 * @return a pointer to the found value or NULL if it does not exist.
243 extern void* lh_table_lookup(struct lh_table *t, void *k);
247 * Delete a record from the table.
248 * If a callback free function is provided then it is called for the
249 * for the item being deleted.
250 * @param t the table to delete from.
251 * @param e a pointer to the entry to delete.
252 * @return 0 if the item was deleted.
253 * @return -1 if it was not found.
255 extern int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e);
259 * Delete a record from the table.
260 * If a callback free function is provided then it is called for the
261 * for the item being deleted.
262 * @param t the table to delete from.
263 * @param k a pointer to the key to delete.
264 * @return 0 if the item was deleted.
265 * @return -1 if it was not found.
267 extern int lh_table_delete(struct lh_table *t, void *k);