GCC Code Coverage Report

Directory: ./
File: submodules/json-c/linkhash.h
Date: 2023-09-29 04:53:15
Exec Total Coverage
Lines: 0 7 0.0%
Branches: 0 8 0.0%
Line Branch Exec Source
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 _json_c_linkhash_h_
20 #define _json_c_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. Outside of linkhash.c, treat this as opaque.
84 */
85 struct lh_entry
86 {
87 /**
88 * The key.
89 * @deprecated Use lh_entry_k() instead of accessing this directly.
90 */
91 const void *k;
92 /**
93 * A flag for users of linkhash to know whether or not they
94 * need to free k.
95 * @deprecated use lh_entry_k_is_constant() instead.
96 */
97 int k_is_constant;
98 /**
99 * The value.
100 * @deprecated Use lh_entry_v() instead of accessing this directly.
101 */
102 const void *v;
103 /**
104 * The next entry.
105 * @deprecated Use lh_entry_next() instead of accessing this directly.
106 */
107 struct lh_entry *next;
108 /**
109 * The previous entry.
110 * @deprecated Use lh_entry_prev() instead of accessing this directly.
111 */
112 struct lh_entry *prev;
113 };
114
115 /**
116 * The hash table structure. Outside of linkhash.c, treat this as opaque.
117 */
118 struct lh_table
119 {
120 /**
121 * Size of our hash.
122 * @deprecated do not use outside of linkhash.c
123 */
124 int size;
125 /**
126 * Numbers of entries.
127 * @deprecated Use lh_table_length() instead.
128 */
129 int count;
130
131 /**
132 * The first entry.
133 * @deprecated Use lh_table_head() instead.
134 */
135 struct lh_entry *head;
136
137 /**
138 * The last entry.
139 * @deprecated Do not use, may be removed in a future release.
140 */
141 struct lh_entry *tail;
142
143 /**
144 * Internal storage of the actual table of entries.
145 * @deprecated do not use outside of linkhash.c
146 */
147 struct lh_entry *table;
148
149 /**
150 * A pointer to the function responsible for freeing an entry.
151 * @deprecated do not use outside of linkhash.c
152 */
153 lh_entry_free_fn *free_fn;
154 /**
155 * @deprecated do not use outside of linkhash.c
156 */
157 lh_hash_fn *hash_fn;
158 /**
159 * @deprecated do not use outside of linkhash.c
160 */
161 lh_equal_fn *equal_fn;
162 };
163 typedef struct lh_table lh_table;
164
165 /**
166 * Convenience list iterator.
167 */
168 #define lh_foreach(table, entry) for (entry = lh_table_head(table); entry; entry = lh_entry_next(entry))
169
170 /**
171 * lh_foreach_safe allows calling of deletion routine while iterating.
172 *
173 * @param table a struct lh_table * to iterate over
174 * @param entry a struct lh_entry * variable to hold each element
175 * @param tmp a struct lh_entry * variable to hold a temporary pointer to the next element
176 */
177 #define lh_foreach_safe(table, entry, tmp) \
178 for (entry = lh_table_head(table); entry && ((tmp = lh_entry_next(entry)) || 1); entry = tmp)
179
180 /**
181 * Create a new linkhash table.
182 *
183 * @param size initial table size. The table is automatically resized
184 * although this incurs a performance penalty.
185 * @param free_fn callback function used to free memory for entries
186 * when lh_table_free or lh_table_delete is called.
187 * If NULL is provided, then memory for keys and values
188 * must be freed by the caller.
189 * @param hash_fn function used to hash keys. 2 standard ones are defined:
190 * lh_ptr_hash and lh_char_hash for hashing pointer values
191 * and C strings respectively.
192 * @param equal_fn comparison function to compare keys. 2 standard ones defined:
193 * lh_ptr_hash and lh_char_hash for comparing pointer values
194 * and C strings respectively.
195 * @return On success, a pointer to the new linkhash table is returned.
196 * On error, a null pointer is returned.
197 */
198 extern struct lh_table *lh_table_new(int size, lh_entry_free_fn *free_fn, lh_hash_fn *hash_fn,
199 lh_equal_fn *equal_fn);
200
201 /**
202 * Convenience function to create a new linkhash table with char keys.
203 *
204 * @param size initial table size.
205 * @param free_fn callback function used to free memory for entries.
206 * @return On success, a pointer to the new linkhash table is returned.
207 * On error, a null pointer is returned.
208 */
209 extern struct lh_table *lh_kchar_table_new(int size, lh_entry_free_fn *free_fn);
210
211 /**
212 * Convenience function to create a new linkhash table with ptr keys.
213 *
214 * @param size initial table size.
215 * @param free_fn callback function used to free memory for entries.
216 * @return On success, a pointer to the new linkhash table is returned.
217 * On error, a null pointer is returned.
218 */
219 extern struct lh_table *lh_kptr_table_new(int size, lh_entry_free_fn *free_fn);
220
221 /**
222 * Free a linkhash table.
223 *
224 * If a lh_entry_free_fn callback free function was provided then it is
225 * called for all entries in the table.
226 *
227 * @param t table to free.
228 */
229 extern void lh_table_free(struct lh_table *t);
230
231 /**
232 * Insert a record into the table.
233 *
234 * @param t the table to insert into.
235 * @param k a pointer to the key to insert.
236 * @param v a pointer to the value to insert.
237 *
238 * @return On success, <code>0</code> is returned.
239 * On error, a negative value is returned.
240 */
241 extern int lh_table_insert(struct lh_table *t, const void *k, const void *v);
242
243 /**
244 * Insert a record into the table using a precalculated key hash.
245 *
246 * The hash h, which should be calculated with lh_get_hash() on k, is provided by
247 * the caller, to allow for optimization when multiple operations with the same
248 * key are known to be needed.
249 *
250 * @param t the table to insert into.
251 * @param k a pointer to the key to insert.
252 * @param v a pointer to the value to insert.
253 * @param h hash value of the key to insert
254 * @param opts if set to JSON_C_OBJECT_ADD_CONSTANT_KEY, sets lh_entry.k_is_constant
255 * so t's free function knows to avoid freeing the key.
256 */
257 extern int lh_table_insert_w_hash(struct lh_table *t, const void *k, const void *v,
258 const unsigned long h, const unsigned opts);
259
260 /**
261 * Lookup a record in the table.
262 *
263 * @param t the table to lookup
264 * @param k a pointer to the key to lookup
265 * @return a pointer to the record structure of the value or NULL if it does not exist.
266 */
267 extern struct lh_entry *lh_table_lookup_entry(struct lh_table *t, const void *k);
268
269 /**
270 * Lookup a record in the table using a precalculated key hash.
271 *
272 * The hash h, which should be calculated with lh_get_hash() on k, is provided by
273 * the caller, to allow for optimization when multiple operations with the same
274 * key are known to be needed.
275 *
276 * @param t the table to lookup
277 * @param k a pointer to the key to lookup
278 * @param h hash value of the key to lookup
279 * @return a pointer to the record structure of the value or NULL if it does not exist.
280 */
281 extern struct lh_entry *lh_table_lookup_entry_w_hash(struct lh_table *t, const void *k,
282 const unsigned long h);
283
284 /**
285 * Lookup a record in the table.
286 *
287 * @param t the table to lookup
288 * @param k a pointer to the key to lookup
289 * @param v a pointer to a where to store the found value (set to NULL if it doesn't exist).
290 * @return whether or not the key was found
291 */
292 extern json_bool lh_table_lookup_ex(struct lh_table *t, const void *k, void **v);
293
294 /**
295 * Delete a record from the table.
296 *
297 * If a callback free function is provided then it is called for the
298 * for the item being deleted.
299 * @param t the table to delete from.
300 * @param e a pointer to the entry to delete.
301 * @return 0 if the item was deleted.
302 * @return -1 if it was not found.
303 */
304 extern int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e);
305
306 /**
307 * Delete a record from the table.
308 *
309 * If a callback free function is provided then it is called for the
310 * for the item being deleted.
311 * @param t the table to delete from.
312 * @param k a pointer to the key to delete.
313 * @return 0 if the item was deleted.
314 * @return -1 if it was not found.
315 */
316 extern int lh_table_delete(struct lh_table *t, const void *k);
317
318 /**
319 * Return the number of entries in the table.
320 */
321 extern int lh_table_length(struct lh_table *t);
322
323 /**
324 * Resizes the specified table.
325 *
326 * @param t Pointer to table to resize.
327 * @param new_size New table size. Must be positive.
328 *
329 * @return On success, <code>0</code> is returned.
330 * On error, a negative value is returned.
331 */
332 int lh_table_resize(struct lh_table *t, int new_size);
333
334 /**
335 * @deprecated Don't use this outside of linkhash.h:
336 */
337 #if (defined(AIX_CC) || (defined(_MSC_VER) && (_MSC_VER <= 1800)) )
338 /* VS2010 can't handle inline funcs, so skip it there */
339 #define _LH_INLINE
340 #else
341 #define _LH_INLINE inline
342 #endif
343
344 /**
345 * Return the first entry in the lh_table.
346 * @see lh_entry_next()
347 */
348 static _LH_INLINE struct lh_entry *lh_table_head(const lh_table *t)
349 {
350 ✗ return t->head;
351 }
352
353 /**
354 * Calculate the hash of a key for a given table.
355 *
356 * This is an extension to support functions that need to calculate
357 * the hash several times and allows them to do it just once and then pass
358 * in the hash to all utility functions. Depending on use case, this can be a
359 * considerable performance improvement.
360 * @param t the table (used to obtain hash function)
361 * @param k a pointer to the key to lookup
362 * @return the key's hash
363 */
364 static _LH_INLINE unsigned long lh_get_hash(const struct lh_table *t, const void *k)
365 {
366 ✗ return t->hash_fn(k);
367 }
368
369
370 /**
371 * @deprecated Don't use this outside of linkhash.h:
372 */
373 #ifdef __UNCONST
374 #define _LH_UNCONST(a) __UNCONST(a)
375 #else
376 #define _LH_UNCONST(a) ((void *)(uintptr_t)(const void *)(a))
377 #endif
378
379 /**
380 * Return a non-const version of lh_entry.k.
381 *
382 * lh_entry.k is const to indicate and help ensure that linkhash itself doesn't modify
383 * it, but callers are allowed to do what they want with it.
384 * @see lh_entry_k_is_constant()
385 */
386 static _LH_INLINE void *lh_entry_k(const struct lh_entry *e)
387 {
388 ✗ return _LH_UNCONST(e->k);
389 }
390
391 /**
392 * Returns 1 if the key for the given entry is constant, and thus
393 * does not need to be freed when the lh_entry is freed.
394 * @see lh_table_insert_w_hash()
395 */
396 static _LH_INLINE int lh_entry_k_is_constant(const struct lh_entry *e)
397 {
398 ✗ return e->k_is_constant;
399 }
400
401 /**
402 * Return a non-const version of lh_entry.v.
403 *
404 * v is const to indicate and help ensure that linkhash itself doesn't modify
405 * it, but callers are allowed to do what they want with it.
406 */
407 static _LH_INLINE void *lh_entry_v(const struct lh_entry *e)
408 {
409 ✗ return _LH_UNCONST(e->v);
410 }
411
412 /**
413 * Change the value for an entry. The caller is responsible for freeing
414 * the previous value.
415 */
416 static _LH_INLINE void lh_entry_set_val(struct lh_entry *e, void *newval)
417 {
418 ✗ e->v = newval;
419 }
420
421 /**
422 * Return the next element, or NULL if there is no next element.
423 * @see lh_table_head()
424 * @see lh_entry_prev()
425 */
426 static _LH_INLINE struct lh_entry *lh_entry_next(const struct lh_entry *e)
427 {
428 ✗ return e->next;
429 }
430
431 /**
432 * Return the previous element, or NULL if there is no previous element.
433 * @see lh_table_head()
434 * @see lh_entry_next()
435 */
436 static _LH_INLINE struct lh_entry *lh_entry_prev(const struct lh_entry *e)
437 {
438 return e->prev;
439 }
440
441 #undef _LH_INLINE
442
443 #ifdef __cplusplus
444 }
445 #endif
446
447 #endif
448