2 * $Id: linkhash.h,v 1.6 2006/01/30 23:07:57 mclark Exp $
4 * Copyright (c) 2004, 2005 Metaparadigm Pte. Ltd.
5 * Michael Clark <michael@metaparadigm.com>
7 * This library is free software; you can redistribute it and/or modify
8 * it under the terms of the MIT license. See COPYING for details.
20 * golden prime used in hash functions
22 #define LH_PRIME 0x9e370001UL
25 * sentinel pointer value for empty slots
27 #define LH_EMPTY (void*)-1
30 * sentinel pointer value for freed slots
32 #define LH_FREED (void*)-2
37 * callback function prototypes
39 typedef void (lh_entry_free_fn) (struct lh_entry *e);
41 * callback function prototypes
43 typedef unsigned long (lh_hash_fn) (const void *k);
45 * callback function prototypes
47 typedef int (lh_equal_fn) (const void *k1, const void *k2);
50 * An entry in the hash table
64 struct lh_entry *next;
68 struct lh_entry *prev;
73 * The hash table structure.
86 * Number of collisions.
111 * Name of the hash table.
118 struct lh_entry *head;
123 struct lh_entry *tail;
125 struct lh_entry *table;
128 * A pointer onto the function responsible for freeing an entry.
130 lh_entry_free_fn *free_fn;
132 lh_equal_fn *equal_fn;
137 * Pre-defined hash and equality functions
139 extern unsigned long lh_ptr_hash(const void *k);
140 extern int lh_ptr_equal(const void *k1, const void *k2);
142 extern unsigned long lh_char_hash(const void *k);
143 extern int lh_char_equal(const void *k1, const void *k2);
147 * Convenience list iterator.
149 #define lh_foreach(table, entry) \
150 for(entry = table->head; entry; entry = entry->next)
153 * lh_foreach_safe allows calling of deletion routine while iterating.
155 #define lh_foreach_safe(table, entry, tmp) \
156 for(entry = table->head; entry && ((tmp = entry->next) || 1); entry = tmp)
161 * Create a new linkhash table.
162 * @param size initial table size. The table is automatically resized
163 * although this incurs a performance penalty.
164 * @param name the table name.
165 * @param free_fn callback function used to free memory for entries
166 * when lh_table_free or lh_table_delete is called.
167 * If NULL is provided, then memory for keys and values
168 * must be freed by the caller.
169 * @param hash_fn function used to hash keys. 2 standard ones are defined:
170 * lh_ptr_hash and lh_char_hash for hashing pointer values
171 * and C strings respectively.
172 * @param equal_fn comparison function to compare keys. 2 standard ones defined:
173 * lh_ptr_hash and lh_char_hash for comparing pointer values
174 * and C strings respectively.
175 * @return a pointer onto the linkhash table.
177 extern struct lh_table* lh_table_new(int size, const char *name,
178 lh_entry_free_fn *free_fn,
180 lh_equal_fn *equal_fn);
183 * Convenience function to create a new linkhash
184 * table with char keys.
185 * @param size initial table size.
186 * @param name table name.
187 * @param free_fn callback function used to free memory for entries.
188 * @return a pointer onto the linkhash table.
190 extern struct lh_table* lh_kchar_table_new(int size, const char *name,
191 lh_entry_free_fn *free_fn);
195 * Convenience function to create a new linkhash
196 * table with ptr keys.
197 * @param size initial table size.
198 * @param name table name.
199 * @param free_fn callback function used to free memory for entries.
200 * @return a pointer onto the linkhash table.
202 extern struct lh_table* lh_kptr_table_new(int size, const char *name,
203 lh_entry_free_fn *free_fn);
207 * Free a linkhash table.
208 * If a callback free function is provided then it is called for all
209 * entries in the table.
210 * @param t table to free.
212 extern void lh_table_free(struct lh_table *t);
216 * Insert a record into the table.
217 * @param t the table to insert into.
218 * @param k a pointer to the key to insert.
219 * @param v a pointer to the value to insert.
221 extern int lh_table_insert(struct lh_table *t, void *k, const void *v);
225 * Lookup a record into the table.
226 * @param t the table to lookup
227 * @param k a pointer to the key to lookup
228 * @return a pointer to the record structure of the value or NULL if it does not exist.
230 extern struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k);
233 * Lookup a record into the table
234 * @param t the table to lookup
235 * @param k a pointer to the key to lookup
236 * @return a pointer to the found value or NULL if it does not exist.
238 extern const void* lh_table_lookup(struct lh_table *t, const void *k);
242 * Delete a record from the table.
243 * If a callback free function is provided then it is called for the
244 * for the item being deleted.
245 * @param t the table to delete from.
246 * @param e a pointer to the entry to delete.
247 * @return 0 if the item was deleted.
248 * @return -1 if it was not found.
250 extern int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e);
254 * Delete a record from the table.
255 * If a callback free function is provided then it is called for the
256 * for the item being deleted.
257 * @param t the table to delete from.
258 * @param k a pointer to the key to delete.
259 * @return 0 if the item was deleted.
260 * @return -1 if it was not found.
262 extern int lh_table_delete(struct lh_table *t, const void *k);
265 void lh_abort(const char *msg, ...);
266 void lh_table_resize(struct lh_table *t, int new_size);