/src/gdal/ogr/ogrsf_frmts/geojson/libjson/linkhash.h

Source (jump to first uncovered line)
/*
 * $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 _linkhash_h_
#define _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
 */
struct lh_entry
{
  /**
   * The key.  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.
   */
  int k_is_constant;
  /**
   * The value.  Use lh_entry_v() instead of accessing this directly.
   */
  const void *v;
  /**
   * The next entry
   */
  struct lh_entry *next;
  /**
   * The previous entry.
   */
  struct lh_entry *prev;
};

/**
 * The hash table structure.
 */
struct lh_table
{
  /**
   * Size of our hash.
   */
  int size;
  /**
   * Numbers of entries.
   */
  int count;

  /**
   * The first entry.
   */
  struct lh_entry *head;

  /**
   * The last entry.
   */
  struct lh_entry *tail;

  struct lh_entry *table;

  /**
   * A pointer onto the function responsible for freeing an entry.
   */
  lh_entry_free_fn *free_fn;
  lh_hash_fn *hash_fn;
  lh_equal_fn *equal_fn;
};
typedef struct lh_table lh_table;

/**
 * Convenience list iterator.
 */
#define lh_foreach(table, entry) for (entry = table->head; entry; entry = entry->next)

/**
 * 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 = table->head; entry && ((tmp = entry->next) || 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_KEY_IS_CONSTANT, 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);

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

/**
 * 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);
}

#undef _LH_INLINE

/**
 * @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 also lh_entry.k_is_constant
 */
#define lh_entry_k(entry) _LH_UNCONST((entry)->k)

/**
 * 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.
 */
#define lh_entry_v(entry) _LH_UNCONST((entry)->v)

#ifdef __cplusplus
}
#endif

#endif

Coverage Report

Created: 2025-06-22 06:59

Line	Count	Source (jump to first uncovered line)
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	0	#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	0	#define LH_LOAD_FACTOR 0.66
39
40		/**
41		* sentinel pointer value for empty slots
42		*/
43	0	#define LH_EMPTY (void *)-1
44
45		/**
46		* sentinel pointer value for freed slots
47		*/
48	0	#define LH_FREED (void *)-2
49
50		/**
51		* default string hash function
52		*/
53	0	#define JSON_C_STR_HASH_DFLT 0
54
55		/**
56		* perl-like string hash function
57		*/
58	0	#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		static _LH_INLINE unsigned long lh_get_hash(const struct lh_table t, const void k)
333	0	{
334	0	return t->hash_fn(k);
335	0	} Unexecuted instantiation: json_object.c:gdal_lh_get_hash Unexecuted instantiation: linkhash.c:gdal_lh_get_hash Unexecuted instantiation: ogrgeojsonlayer.cpp:lh_get_hash(lh_table const, void const) Unexecuted instantiation: ogrjsoncollectionstreamingparser.cpp:lh_get_hash(lh_table const, void const) Unexecuted instantiation: gdal_rat.cpp:lh_get_hash(lh_table const, void const)
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	0	#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	0	#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	0	#define lh_entry_v(entry) _LH_UNCONST((entry)->v)
364
365		#ifdef __cplusplus
366		}
367		#endif
368
369		#endif