1/*
2 * $Id: linkhash.h,v 1.6 2006/01/30 23:07:57 mclark Exp $
3 *
4 * Copyright (c) 2004, 2005 Metaparadigm Pte. Ltd.
5 * Michael Clark <michael@metaparadigm.com>
6 * Copyright (c) 2009 Hewlett-Packard Development Company, L.P.
7 *
8 * This library is free software; you can redistribute it and/or modify
9 * it under the terms of the MIT license. See COPYING for details.
10 *
11 */
12
13#ifndef _linkhash_h_
14#define _linkhash_h_
15
16#include "json_object.h"
17
18#ifdef __cplusplus
19extern "C" {
20#endif
21
22/**
23 * golden prime used in hash functions
24 */
25#define LH_PRIME 0x9e370001UL
26
27/**
28 * The fraction of filled hash buckets until an insert will cause the table
29 * to be resized.
30 * This can range from just above 0 up to 1.0.
31 */
32#define LH_LOAD_FACTOR 0.66
33
34/**
35 * sentinel pointer value for empty slots
36 */
37#define LH_EMPTY (void*)-1
38
39/**
40 * sentinel pointer value for freed slots
41 */
42#define LH_FREED (void*)-2
43
44struct lh_entry;
45
46/**
47 * callback function prototypes
48 */
49typedef void (lh_entry_free_fn) (struct lh_entry *e);
50/**
51 * callback function prototypes
52 */
53typedef unsigned long (lh_hash_fn) (const void *k);
54/**
55 * callback function prototypes
56 */
57typedef int (lh_equal_fn) (const void *k1, const void *k2);
58
59/**
60 * An entry in the hash table
61 */
62struct lh_entry {
63	/**
64	 * The key.
65	 */
66	void *k;
67	/**
68	 * The value.
69	 */
70	const void *v;
71	/**
72	 * The next entry
73	 */
74	struct lh_entry *next;
75	/**
76	 * The previous entry.
77	 */
78	struct lh_entry *prev;
79};
80
81
82/**
83 * The hash table structure.
84 */
85struct lh_table {
86	/**
87	 * Size of our hash.
88	 */
89	int size;
90	/**
91	 * Numbers of entries.
92	 */
93	int count;
94
95	/**
96	 * Number of collisions.
97	 */
98	int collisions;
99
100	/**
101	 * Number of resizes.
102	 */
103	int resizes;
104
105	/**
106	 * Number of lookups.
107	 */
108	int lookups;
109
110	/**
111	 * Number of inserts.
112	 */
113	int inserts;
114
115	/**
116	 * Number of deletes.
117	 */
118	int deletes;
119
120	/**
121	 * Name of the hash table.
122	 */
123	const char *name;
124
125	/**
126	 * The first entry.
127	 */
128	struct lh_entry *head;
129
130	/**
131	 * The last entry.
132	 */
133	struct lh_entry *tail;
134
135	struct lh_entry *table;
136
137	/**
138	 * A pointer onto the function responsible for freeing an entry.
139	 */
140	lh_entry_free_fn *free_fn;
141	lh_hash_fn *hash_fn;
142	lh_equal_fn *equal_fn;
143};
144
145
146/**
147 * Pre-defined hash and equality functions
148 */
149extern unsigned long lh_ptr_hash(const void *k);
150extern int lh_ptr_equal(const void *k1, const void *k2);
151
152extern unsigned long lh_char_hash(const void *k);
153extern int lh_char_equal(const void *k1, const void *k2);
154
155
156/**
157 * Convenience list iterator.
158 */
159#define lh_foreach(table, entry) \
160for(entry = table->head; entry; entry = entry->next)
161
162/**
163 * lh_foreach_safe allows calling of deletion routine while iterating.
164 */
165#define lh_foreach_safe(table, entry, tmp) \
166for(entry = table->head; entry && ((tmp = entry->next) || 1); entry = tmp)
167
168
169
170/**
171 * Create a new linkhash table.
172 * @param size initial table size. The table is automatically resized
173 * although this incurs a performance penalty.
174 * @param name the table name.
175 * @param free_fn callback function used to free memory for entries
176 * when lh_table_free or lh_table_delete is called.
177 * If NULL is provided, then memory for keys and values
178 * must be freed by the caller.
179 * @param hash_fn  function used to hash keys. 2 standard ones are defined:
180 * lh_ptr_hash and lh_char_hash for hashing pointer values
181 * and C strings respectively.
182 * @param equal_fn comparison function to compare keys. 2 standard ones defined:
183 * lh_ptr_hash and lh_char_hash for comparing pointer values
184 * and C strings respectively.
185 * @return a pointer onto the linkhash table.
186 */
187extern struct lh_table* lh_table_new(int size, const char *name,
188				     lh_entry_free_fn *free_fn,
189				     lh_hash_fn *hash_fn,
190				     lh_equal_fn *equal_fn);
191
192/**
193 * Convenience function to create a new linkhash
194 * table with char keys.
195 * @param size initial table size.
196 * @param name table name.
197 * @param free_fn callback function used to free memory for entries.
198 * @return a pointer onto the linkhash table.
199 */
200extern struct lh_table* lh_kchar_table_new(int size, const char *name,
201					   lh_entry_free_fn *free_fn);
202
203
204/**
205 * Convenience function to create a new linkhash
206 * table with ptr keys.
207 * @param size initial table size.
208 * @param name table name.
209 * @param free_fn callback function used to free memory for entries.
210 * @return a pointer onto the linkhash table.
211 */
212extern struct lh_table* lh_kptr_table_new(int size, const char *name,
213					  lh_entry_free_fn *free_fn);
214
215
216/**
217 * Free a linkhash table.
218 * If a callback free function is provided then it is called for all
219 * entries in the table.
220 * @param t table to free.
221 */
222extern void lh_table_free(struct lh_table *t);
223
224
225/**
226 * Insert a record into the table.
227 * @param t the table to insert into.
228 * @param k a pointer to the key to insert.
229 * @param v a pointer to the value to insert.
230 */
231extern int lh_table_insert(struct lh_table *t, void *k, const void *v);
232
233
234/**
235 * Lookup a record into the table.
236 * @param t the table to lookup
237 * @param k a pointer to the key to lookup
238 * @return a pointer to the record structure of the value or NULL if it does not exist.
239 */
240extern struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k);
241
242/**
243 * Lookup a record into the table
244 * @param t the table to lookup
245 * @param k a pointer to the key to lookup
246 * @return a pointer to the found value or NULL if it does not exist.
247 * @deprecated Use lh_table_lookup_ex instead.
248 */
249THIS_FUNCTION_IS_DEPRECATED(extern const void* lh_table_lookup(struct lh_table *t, const void *k));
250
251/**
252 * Lookup a record in the table
253 * @param t the table to lookup
254 * @param k a pointer to the key to lookup
255 * @param v a pointer to a where to store the found value (set to NULL if it doesn't exist).
256 * @return whether or not the key was found
257 */
258extern json_bool lh_table_lookup_ex(struct lh_table *t, const void *k, void **v);
259
260/**
261 * Delete a record from the table.
262 * If a callback free function is provided then it is called for the
263 * for the item being deleted.
264 * @param t the table to delete from.
265 * @param e a pointer to the entry to delete.
266 * @return 0 if the item was deleted.
267 * @return -1 if it was not found.
268 */
269extern int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e);
270
271
272/**
273 * Delete a record from the table.
274 * If a callback free function is provided then it is called for the
275 * for the item being deleted.
276 * @param t the table to delete from.
277 * @param k a pointer to the key to delete.
278 * @return 0 if the item was deleted.
279 * @return -1 if it was not found.
280 */
281extern int lh_table_delete(struct lh_table *t, const void *k);
282
283extern int lh_table_length(struct lh_table *t);
284
285void lh_abort(const char *msg, ...);
286void lh_table_resize(struct lh_table *t, int new_size);
287
288#ifdef __cplusplus
289}
290#endif
291
292#endif
293