summaryrefslogtreecommitdiffstats
path: root/comm/third_party/json-c/linkhash.h
blob: 5e5e240822a1f8312072452243a5926cadbd5c4d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
/*
 * $Id: linkhash.h,v 1.6 2006/01/30 23:07:57 mclark Exp $
 *
 * Copyright (c) 2004, 2005 Metaparadigm Pte. Ltd.
 * Michael Clark <michael@metaparadigm.com>
 * Copyright (c) 2009 Hewlett-Packard Development Company, L.P.
 *
 * This library is free software; you can redistribute it and/or modify
 * it under the terms of the MIT license. See COPYING for details.
 *
 */

/**
 * @file
 * @brief Internal methods for working with json_type_object objects.  Although
 *        this is exposed by the json_object_get_object() function and within the
 *        json_object_iter type, it is not recommended for direct use.
 */
#ifndef _json_c_linkhash_h_
#define _json_c_linkhash_h_

#include "json_object.h"

#ifdef __cplusplus
extern "C" {
#endif

/**
 * golden prime used in hash functions
 */
#define LH_PRIME 0x9e370001UL

/**
 * The fraction of filled hash buckets until an insert will cause the table
 * to be resized.
 * This can range from just above 0 up to 1.0.
 */
#define LH_LOAD_FACTOR 0.66

/**
 * sentinel pointer value for empty slots
 */
#define LH_EMPTY (void *)-1

/**
 * sentinel pointer value for freed slots
 */
#define LH_FREED (void *)-2

/**
 * default string hash function
 */
#define JSON_C_STR_HASH_DFLT 0

/**
 * perl-like string hash function
 */
#define JSON_C_STR_HASH_PERLLIKE 1

/**
 * This function sets the hash function to be used for strings.
 * Must be one of the JSON_C_STR_HASH_* values.
 * @returns 0 - ok, -1 if parameter was invalid
 */
int json_global_set_string_hash(const int h);

struct lh_entry;

/**
 * callback function prototypes
 */
typedef void(lh_entry_free_fn)(struct lh_entry *e);
/**
 * callback function prototypes
 */
typedef unsigned long(lh_hash_fn)(const void *k);
/**
 * callback function prototypes
 */
typedef int(lh_equal_fn)(const void *k1, const void *k2);

/**
 * An entry in the hash table.  Outside of linkhash.c, treat this as opaque.
 */
struct lh_entry
{
	/**
	 * The key.
	 * @deprecated Use lh_entry_k() instead of accessing this directly.
	 */
	const void *k;
	/**
	 * A flag for users of linkhash to know whether or not they
	 * need to free k.
	 * @deprecated use lh_entry_k_is_constant() instead.
	 */
	int k_is_constant;
	/**
	 * The value.
	 * @deprecated Use lh_entry_v() instead of accessing this directly.
	 */
	const void *v;
	/**
	 * The next entry.
	 * @deprecated Use lh_entry_next() instead of accessing this directly.
	 */
	struct lh_entry *next;
	/**
	 * The previous entry.
	 * @deprecated Use lh_entry_prev() instead of accessing this directly.
	 */
	struct lh_entry *prev;
};

/**
 * The hash table structure.  Outside of linkhash.c, treat this as opaque.
 */
struct lh_table
{
	/**
	 * Size of our hash.
	 * @deprecated do not use outside of linkhash.c
	 */
	int size;
	/**
	 * Numbers of entries.
	 * @deprecated Use lh_table_length() instead.
	 */
	int count;

	/**
	 * The first entry.
	 * @deprecated Use lh_table_head() instead.
	 */
	struct lh_entry *head;

	/**
	 * The last entry.
	 * @deprecated Do not use, may be removed in a future release.
	 */
	struct lh_entry *tail;

	/**
	 * Internal storage of the actual table of entries.
	 * @deprecated do not use outside of linkhash.c
	 */
	struct lh_entry *table;

	/**
	 * A pointer to the function responsible for freeing an entry.
	 * @deprecated do not use outside of linkhash.c
	 */
	lh_entry_free_fn *free_fn;
	/**
	 * @deprecated do not use outside of linkhash.c
	 */
	lh_hash_fn *hash_fn;
	/**
	 * @deprecated do not use outside of linkhash.c
	 */
	lh_equal_fn *equal_fn;
};
typedef struct lh_table lh_table;

/**
 * Convenience list iterator.
 */
#define lh_foreach(table, entry) for (entry = lh_table_head(table); entry; entry = lh_entry_next(entry))

/**
 * lh_foreach_safe allows calling of deletion routine while iterating.
 *
 * @param table a struct lh_table * to iterate over
 * @param entry a struct lh_entry * variable to hold each element
 * @param tmp a struct lh_entry * variable to hold a temporary pointer to the next element
 */
#define lh_foreach_safe(table, entry, tmp) \
	for (entry = lh_table_head(table); entry && ((tmp = lh_entry_next(entry)) || 1); entry = tmp)

/**
 * Create a new linkhash table.
 *
 * @param size initial table size. The table is automatically resized
 * although this incurs a performance penalty.
 * @param free_fn callback function used to free memory for entries
 * when lh_table_free or lh_table_delete is called.
 * If NULL is provided, then memory for keys and values
 * must be freed by the caller.
 * @param hash_fn  function used to hash keys. 2 standard ones are defined:
 * lh_ptr_hash and lh_char_hash for hashing pointer values
 * and C strings respectively.
 * @param equal_fn comparison function to compare keys. 2 standard ones defined:
 * lh_ptr_hash and lh_char_hash for comparing pointer values
 * and C strings respectively.
 * @return On success, a pointer to the new linkhash table is returned.
 * 	On error, a null pointer is returned.
 */
extern struct lh_table *lh_table_new(int size, lh_entry_free_fn *free_fn, lh_hash_fn *hash_fn,
                                     lh_equal_fn *equal_fn);

/**
 * Convenience function to create a new linkhash table with char keys.
 *
 * @param size initial table size.
 * @param free_fn callback function used to free memory for entries.
 * @return On success, a pointer to the new linkhash table is returned.
 * 	On error, a null pointer is returned.
 */
extern struct lh_table *lh_kchar_table_new(int size, lh_entry_free_fn *free_fn);

/**
 * Convenience function to create a new linkhash table with ptr keys.
 *
 * @param size initial table size.
 * @param free_fn callback function used to free memory for entries.
 * @return On success, a pointer to the new linkhash table is returned.
 * 	On error, a null pointer is returned.
 */
extern struct lh_table *lh_kptr_table_new(int size, lh_entry_free_fn *free_fn);

/**
 * Free a linkhash table.
 *
 * If a lh_entry_free_fn callback free function was provided then it is
 * called for all entries in the table.
 *
 * @param t table to free.
 */
extern void lh_table_free(struct lh_table *t);

/**
 * Insert a record into the table.
 *
 * @param t the table to insert into.
 * @param k a pointer to the key to insert.
 * @param v a pointer to the value to insert.
 *
 * @return On success, <code>0</code> is returned.
 * 	On error, a negative value is returned.
 */
extern int lh_table_insert(struct lh_table *t, const void *k, const void *v);

/**
 * Insert a record into the table using a precalculated key hash.
 *
 * The hash h, which should be calculated with lh_get_hash() on k, is provided by
 *  the caller, to allow for optimization when multiple operations with the same
 *  key are known to be needed.
 *
 * @param t the table to insert into.
 * @param k a pointer to the key to insert.
 * @param v a pointer to the value to insert.
 * @param h hash value of the key to insert
 * @param opts if set to JSON_C_OBJECT_ADD_CONSTANT_KEY, sets lh_entry.k_is_constant
 *             so t's free function knows to avoid freeing the key.
 */
extern int lh_table_insert_w_hash(struct lh_table *t, const void *k, const void *v,
                                  const unsigned long h, const unsigned opts);

/**
 * Lookup a record in the table.
 *
 * @param t the table to lookup
 * @param k a pointer to the key to lookup
 * @return a pointer to the record structure of the value or NULL if it does not exist.
 */
extern struct lh_entry *lh_table_lookup_entry(struct lh_table *t, const void *k);

/**
 * Lookup a record in the table using a precalculated key hash.
 *
 * The hash h, which should be calculated with lh_get_hash() on k, is provided by
 *  the caller, to allow for optimization when multiple operations with the same
 *  key are known to be needed.
 *
 * @param t the table to lookup
 * @param k a pointer to the key to lookup
 * @param h hash value of the key to lookup
 * @return a pointer to the record structure of the value or NULL if it does not exist.
 */
extern struct lh_entry *lh_table_lookup_entry_w_hash(struct lh_table *t, const void *k,
                                                     const unsigned long h);

/**
 * Lookup a record in the table.
 *
 * @param t the table to lookup
 * @param k a pointer to the key to lookup
 * @param v a pointer to a where to store the found value (set to NULL if it doesn't exist).
 * @return whether or not the key was found
 */
extern json_bool lh_table_lookup_ex(struct lh_table *t, const void *k, void **v);

/**
 * Delete a record from the table.
 *
 * If a callback free function is provided then it is called for the
 * for the item being deleted.
 * @param t the table to delete from.
 * @param e a pointer to the entry to delete.
 * @return 0 if the item was deleted.
 * @return -1 if it was not found.
 */
extern int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e);

/**
 * Delete a record from the table.
 *
 * If a callback free function is provided then it is called for the
 * for the item being deleted.
 * @param t the table to delete from.
 * @param k a pointer to the key to delete.
 * @return 0 if the item was deleted.
 * @return -1 if it was not found.
 */
extern int lh_table_delete(struct lh_table *t, const void *k);

/**
 * Return the number of entries in the table.
 */
extern int lh_table_length(struct lh_table *t);

/**
 * Resizes the specified table.
 *
 * @param t Pointer to table to resize.
 * @param new_size New table size. Must be positive.
 *
 * @return On success, <code>0</code> is returned.
 * 	On error, a negative value is returned.
 */
int lh_table_resize(struct lh_table *t, int new_size);

/**
 * @deprecated Don't use this outside of linkhash.h:
 */
#if (defined(AIX_CC) || (defined(_MSC_VER) && (_MSC_VER <= 1800)) )
/* VS2010 can't handle inline funcs, so skip it there */
#define _LH_INLINE
#else
#define _LH_INLINE inline
#endif

/**
 * Return the first entry in the lh_table.
 * @see lh_entry_next()
 */
static _LH_INLINE struct lh_entry *lh_table_head(const lh_table *t)
{
	return t->head;
}

/**
 * Calculate the hash of a key for a given table.
 *
 * This is an extension to support functions that need to calculate
 * the hash several times and allows them to do it just once and then pass
 * in the hash to all utility functions. Depending on use case, this can be a
 * considerable performance improvement.
 * @param t the table (used to obtain hash function)
 * @param k a pointer to the key to lookup
 * @return the key's hash
 */
static _LH_INLINE unsigned long lh_get_hash(const struct lh_table *t, const void *k)
{
	return t->hash_fn(k);
}


/**
 * @deprecated Don't use this outside of linkhash.h:
 */
#ifdef __UNCONST
#define _LH_UNCONST(a) __UNCONST(a)
#else
#define _LH_UNCONST(a) ((void *)(uintptr_t)(const void *)(a))
#endif

/**
 * Return a non-const version of lh_entry.k.
 *
 * lh_entry.k is const to indicate and help ensure that linkhash itself doesn't modify
 * it, but callers are allowed to do what they want with it.
 * @see lh_entry_k_is_constant()
 */
static _LH_INLINE void *lh_entry_k(const struct lh_entry *e)
{
	return _LH_UNCONST(e->k);
}

/**
 * Returns 1 if the key for the given entry is constant, and thus
 *  does not need to be freed when the lh_entry is freed.
 * @see lh_table_insert_w_hash()
 */
static _LH_INLINE int lh_entry_k_is_constant(const struct lh_entry *e)
{
	return e->k_is_constant;
}

/**
 * Return a non-const version of lh_entry.v.
 *
 * v is const to indicate and help ensure that linkhash itself doesn't modify
 * it, but callers are allowed to do what they want with it.
 */
static _LH_INLINE void *lh_entry_v(const struct lh_entry *e)
{
	return _LH_UNCONST(e->v);
}

/**
 * Change the value for an entry.  The caller is responsible for freeing
 *  the previous value.
 */
static _LH_INLINE void lh_entry_set_val(struct lh_entry *e, void *newval)
{
	e->v = newval;
}

/**
 * Return the next element, or NULL if there is no next element.
 * @see lh_table_head()
 * @see lh_entry_prev()
 */
static _LH_INLINE struct lh_entry *lh_entry_next(const struct lh_entry *e)
{
	return e->next;
}

/**
 * Return the previous element, or NULL if there is no previous element.
 * @see lh_table_head()
 * @see lh_entry_next()
 */
static _LH_INLINE struct lh_entry *lh_entry_prev(const struct lh_entry *e)
{
	return e->prev;
}

#undef _LH_INLINE

#ifdef __cplusplus
}
#endif

#endif