Line data Source code
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 : /**
14 : * @file
15 : * @brief Internal methods for working with json_type_object objects. Although
16 : * this is exposed by the json_object_get_object() function and within the
17 : * json_object_iter type, it is not recommended for direct use.
18 : */
19 : #ifndef _linkhash_h_
20 : #define _linkhash_h_
21 :
22 : #include "json_object.h"
23 :
24 : #ifdef __cplusplus
25 : extern "C" {
26 : #endif
27 :
28 : /**
29 : * golden prime used in hash functions
30 : */
31 : #define LH_PRIME 0x9e370001UL
32 :
33 : /**
34 : * The fraction of filled hash buckets until an insert will cause the table
35 : * to be resized.
36 : * This can range from just above 0 up to 1.0.
37 : */
38 : #define LH_LOAD_FACTOR 0.66
39 :
40 : /**
41 : * sentinel pointer value for empty slots
42 : */
43 : #define LH_EMPTY (void *)-1
44 :
45 : /**
46 : * sentinel pointer value for freed slots
47 : */
48 : #define LH_FREED (void *)-2
49 :
50 : /**
51 : * default string hash function
52 : */
53 : #define JSON_C_STR_HASH_DFLT 0
54 :
55 : /**
56 : * perl-like string hash function
57 : */
58 : #define JSON_C_STR_HASH_PERLLIKE 1
59 :
60 : /**
61 : * This function sets the hash function to be used for strings.
62 : * Must be one of the JSON_C_STR_HASH_* values.
63 : * @returns 0 - ok, -1 if parameter was invalid
64 : */
65 : int json_global_set_string_hash(const int h);
66 :
67 : struct lh_entry;
68 :
69 : /**
70 : * callback function prototypes
71 : */
72 : typedef void(lh_entry_free_fn)(struct lh_entry *e);
73 : /**
74 : * callback function prototypes
75 : */
76 : typedef unsigned long(lh_hash_fn)(const void *k);
77 : /**
78 : * callback function prototypes
79 : */
80 : typedef int(lh_equal_fn)(const void *k1, const void *k2);
81 :
82 : /**
83 : * An entry in the hash table
84 : */
85 : struct lh_entry
86 : {
87 : /**
88 : * The key. Use lh_entry_k() instead of accessing this directly.
89 : */
90 : const void *k;
91 : /**
92 : * A flag for users of linkhash to know whether or not they
93 : * need to free k.
94 : */
95 : int k_is_constant;
96 : /**
97 : * The value. Use lh_entry_v() instead of accessing this directly.
98 : */
99 : const void *v;
100 : /**
101 : * The next entry
102 : */
103 : struct lh_entry *next;
104 : /**
105 : * The previous entry.
106 : */
107 : struct lh_entry *prev;
108 : };
109 :
110 : /**
111 : * The hash table structure.
112 : */
113 : struct lh_table
114 : {
115 : /**
116 : * Size of our hash.
117 : */
118 : int size;
119 : /**
120 : * Numbers of entries.
121 : */
122 : int count;
123 :
124 : /**
125 : * The first entry.
126 : */
127 : struct lh_entry *head;
128 :
129 : /**
130 : * The last entry.
131 : */
132 : struct lh_entry *tail;
133 :
134 : struct lh_entry *table;
135 :
136 : /**
137 : * A pointer onto the function responsible for freeing an entry.
138 : */
139 : lh_entry_free_fn *free_fn;
140 : lh_hash_fn *hash_fn;
141 : lh_equal_fn *equal_fn;
142 : };
143 : typedef struct lh_table lh_table;
144 :
145 : /**
146 : * Convenience list iterator.
147 : */
148 : #define lh_foreach(table, entry) for (entry = table->head; entry; entry = entry->next)
149 :
150 : /**
151 : * lh_foreach_safe allows calling of deletion routine while iterating.
152 : *
153 : * @param table a struct lh_table * to iterate over
154 : * @param entry a struct lh_entry * variable to hold each element
155 : * @param tmp a struct lh_entry * variable to hold a temporary pointer to the next element
156 : */
157 : #define lh_foreach_safe(table, entry, tmp) \
158 : for (entry = table->head; entry && ((tmp = entry->next) || 1); entry = tmp)
159 :
160 : /**
161 : * Create a new linkhash table.
162 : *
163 : * @param size initial table size. The table is automatically resized
164 : * although this incurs a performance penalty.
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 On success, a pointer to the new linkhash table is returned.
176 : * On error, a null pointer is returned.
177 : */
178 : extern struct lh_table *lh_table_new(int size, lh_entry_free_fn *free_fn, lh_hash_fn *hash_fn,
179 : lh_equal_fn *equal_fn);
180 :
181 : /**
182 : * Convenience function to create a new linkhash table with char keys.
183 : *
184 : * @param size initial table size.
185 : * @param free_fn callback function used to free memory for entries.
186 : * @return On success, a pointer to the new linkhash table is returned.
187 : * On error, a null pointer is returned.
188 : */
189 : extern struct lh_table *lh_kchar_table_new(int size, lh_entry_free_fn *free_fn);
190 :
191 : /**
192 : * Convenience function to create a new linkhash table with ptr keys.
193 : *
194 : * @param size initial table size.
195 : * @param free_fn callback function used to free memory for entries.
196 : * @return On success, a pointer to the new linkhash table is returned.
197 : * On error, a null pointer is returned.
198 : */
199 : extern struct lh_table *lh_kptr_table_new(int size, lh_entry_free_fn *free_fn);
200 :
201 : /**
202 : * Free a linkhash table.
203 : *
204 : * If a lh_entry_free_fn callback free function was provided then it is
205 : * called for all entries in the table.
206 : *
207 : * @param t table to free.
208 : */
209 : extern void lh_table_free(struct lh_table *t);
210 :
211 : /**
212 : * Insert a record into the table.
213 : *
214 : * @param t the table to insert into.
215 : * @param k a pointer to the key to insert.
216 : * @param v a pointer to the value to insert.
217 : *
218 : * @return On success, <code>0</code> is returned.
219 : * On error, a negative value is returned.
220 : */
221 : extern int lh_table_insert(struct lh_table *t, const void *k, const void *v);
222 :
223 : /**
224 : * Insert a record into the table using a precalculated key hash.
225 : *
226 : * The hash h, which should be calculated with lh_get_hash() on k, is provided by
227 : * the caller, to allow for optimization when multiple operations with the same
228 : * key are known to be needed.
229 : *
230 : * @param t the table to insert into.
231 : * @param k a pointer to the key to insert.
232 : * @param v a pointer to the value to insert.
233 : * @param h hash value of the key to insert
234 : * @param opts if set to JSON_C_OBJECT_KEY_IS_CONSTANT, sets lh_entry.k_is_constant
235 : * so t's free function knows to avoid freeing the key.
236 : */
237 : extern int lh_table_insert_w_hash(struct lh_table *t, const void *k, const void *v,
238 : const unsigned long h, const unsigned opts);
239 :
240 : /**
241 : * Lookup a record in the table.
242 : *
243 : * @param t the table to lookup
244 : * @param k a pointer to the key to lookup
245 : * @return a pointer to the record structure of the value or NULL if it does not exist.
246 : */
247 : extern struct lh_entry *lh_table_lookup_entry(struct lh_table *t, const void *k);
248 :
249 : /**
250 : * Lookup a record in the table using a precalculated key hash.
251 : *
252 : * The hash h, which should be calculated with lh_get_hash() on k, is provided by
253 : * the caller, to allow for optimization when multiple operations with the same
254 : * key are known to be needed.
255 : *
256 : * @param t the table to lookup
257 : * @param k a pointer to the key to lookup
258 : * @param h hash value of the key to lookup
259 : * @return a pointer to the record structure of the value or NULL if it does not exist.
260 : */
261 : extern struct lh_entry *lh_table_lookup_entry_w_hash(struct lh_table *t, const void *k,
262 : const unsigned long h);
263 :
264 : /**
265 : * Lookup a record in the table.
266 : *
267 : * @param t the table to lookup
268 : * @param k a pointer to the key to lookup
269 : * @param v a pointer to a where to store the found value (set to NULL if it doesn't exist).
270 : * @return whether or not the key was found
271 : */
272 : extern json_bool lh_table_lookup_ex(struct lh_table *t, const void *k, void **v);
273 :
274 : /**
275 : * Delete a record from the table.
276 : *
277 : * If a callback free function is provided then it is called for the
278 : * for the item being deleted.
279 : * @param t the table to delete from.
280 : * @param e a pointer to the entry to delete.
281 : * @return 0 if the item was deleted.
282 : * @return -1 if it was not found.
283 : */
284 : extern int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e);
285 :
286 : /**
287 : * Delete a record from the table.
288 : *
289 : * If a callback free function is provided then it is called for the
290 : * for the item being deleted.
291 : * @param t the table to delete from.
292 : * @param k a pointer to the key to delete.
293 : * @return 0 if the item was deleted.
294 : * @return -1 if it was not found.
295 : */
296 : extern int lh_table_delete(struct lh_table *t, const void *k);
297 :
298 : extern int lh_table_length(struct lh_table *t);
299 :
300 : /**
301 : * Resizes the specified table.
302 : *
303 : * @param t Pointer to table to resize.
304 : * @param new_size New table size. Must be positive.
305 : *
306 : * @return On success, <code>0</code> is returned.
307 : * On error, a negative value is returned.
308 : */
309 : int lh_table_resize(struct lh_table *t, int new_size);
310 :
311 : /**
312 : * @deprecated Don't use this outside of linkhash.h:
313 : */
314 : #if (defined(AIX_CC) || (defined(_MSC_VER) && (_MSC_VER <= 1800)) )
315 : /* VS2010 can't handle inline funcs, so skip it there */
316 : #define _LH_INLINE
317 : #else
318 : #define _LH_INLINE inline
319 : #endif
320 :
321 : /**
322 : * Calculate the hash of a key for a given table.
323 : *
324 : * This is an extension to support functions that need to calculate
325 : * the hash several times and allows them to do it just once and then pass
326 : * in the hash to all utility functions. Depending on use case, this can be a
327 : * considerable performance improvement.
328 : * @param t the table (used to obtain hash function)
329 : * @param k a pointer to the key to lookup
330 : * @return the key's hash
331 : */
332 2530610 : static _LH_INLINE unsigned long lh_get_hash(const struct lh_table *t, const void *k)
333 : {
334 2530610 : return t->hash_fn(k);
335 : }
336 :
337 : #undef _LH_INLINE
338 :
339 : /**
340 : * @deprecated Don't use this outside of linkhash.h:
341 : */
342 : #ifdef __UNCONST
343 : #define _LH_UNCONST(a) __UNCONST(a)
344 : #else
345 : #define _LH_UNCONST(a) ((void *)(uintptr_t)(const void *)(a))
346 : #endif
347 :
348 : /**
349 : * Return a non-const version of lh_entry.k.
350 : *
351 : * lh_entry.k is const to indicate and help ensure that linkhash itself doesn't modify
352 : * it, but callers are allowed to do what they want with it.
353 : * See also lh_entry.k_is_constant
354 : */
355 : #define lh_entry_k(entry) _LH_UNCONST((entry)->k)
356 :
357 : /**
358 : * Return a non-const version of lh_entry.v.
359 : *
360 : * v is const to indicate and help ensure that linkhash itself doesn't modify
361 : * it, but callers are allowed to do what they want with it.
362 : */
363 : #define lh_entry_v(entry) _LH_UNCONST((entry)->v)
364 :
365 : #ifdef __cplusplus
366 : }
367 : #endif
368 :
369 : #endif
|
