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 exension 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 { 334 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 370
This page was automatically generated by LXR 0.3.1. • OpenWrt