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 <[email protected]> 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 #ifndef _linkhash_h_ 14 #define _linkhash_h_ 15 16 #include "json_object.h" 17 18 #ifdef __cplusplus 19 extern "C" { 20 #endif 21 22 /** 23 * golden prime used in hash functions 24 */ 25 #define LH_PRIME 0x9e370001UL 26 27 /** 28 * The fraction of filled hash buckets until an insert will cause the table 29 * to be resized. 30 * This can range from just above 0 up to 1.0. 31 */ 32 #define LH_LOAD_FACTOR 0.66 33 34 /** 35 * sentinel pointer value for empty slots 36 */ 37 #define LH_EMPTY (void*)-1 38 39 /** 40 * sentinel pointer value for freed slots 41 */ 42 #define LH_FREED (void*)-2 43 44 struct lh_entry; 45 46 /** 47 * callback function prototypes 48 */ 49 typedef void (lh_entry_free_fn) (struct lh_entry *e); 50 /** 51 * callback function prototypes 52 */ 53 typedef unsigned long (lh_hash_fn) (const void *k); 54 /** 55 * callback function prototypes 56 */ 57 typedef int (lh_equal_fn) (const void *k1, const void *k2); 58 59 /** 60 * An entry in the hash table 61 */ 62 struct lh_entry { 63 /** 64 * The key. 65 */ 66 void *k; 67 /** 68 * The value. 69 */ 70 const void *v; 71 /** 72 * The next entry 73 */ 74 struct lh_entry *next; 75 /** 76 * The previous entry. 77 */ 78 struct lh_entry *prev; 79 }; 80 81 82 /** 83 * The hash table structure. 84 */ 85 struct lh_table { 86 /** 87 * Size of our hash. 88 */ 89 int size; 90 /** 91 * Numbers of entries. 92 */ 93 int count; 94 95 /** 96 * Number of collisions. 97 */ 98 int collisions; 99 100 /** 101 * Number of resizes. 102 */ 103 int resizes; 104 105 /** 106 * Number of lookups. 107 */ 108 int lookups; 109 110 /** 111 * Number of inserts. 112 */ 113 int inserts; 114 115 /** 116 * Number of deletes. 117 */ 118 int deletes; 119 120 /** 121 * Name of the hash table. 122 */ 123 const char *name; 124 125 /** 126 * The first entry. 127 */ 128 struct lh_entry *head; 129 130 /** 131 * The last entry. 132 */ 133 struct lh_entry *tail; 134 135 struct lh_entry *table; 136 137 /** 138 * A pointer onto the function responsible for freeing an entry. 139 */ 140 lh_entry_free_fn *free_fn; 141 lh_hash_fn *hash_fn; 142 lh_equal_fn *equal_fn; 143 }; 144 145 146 /** 147 * Pre-defined hash and equality functions 148 */ 149 extern unsigned long lh_ptr_hash(const void *k); 150 extern int lh_ptr_equal(const void *k1, const void *k2); 151 152 extern unsigned long lh_char_hash(const void *k); 153 extern int lh_char_equal(const void *k1, const void *k2); 154 155 156 /** 157 * Convenience list iterator. 158 */ 159 #define lh_foreach(table, entry) \ 160 for(entry = table->head; entry; entry = entry->next) 161 162 /** 163 * lh_foreach_safe allows calling of deletion routine while iterating. 164 */ 165 #define lh_foreach_safe(table, entry, tmp) \ 166 for(entry = table->head; entry && ((tmp = entry->next) || 1); entry = tmp) 167 168 169 170 /** 171 * Create a new linkhash table. 172 * @param size initial table size. The table is automatically resized 173 * although this incurs a performance penalty. 174 * @param name the table name. 175 * @param free_fn callback function used to free memory for entries 176 * when lh_table_free or lh_table_delete is called. 177 * If NULL is provided, then memory for keys and values 178 * must be freed by the caller. 179 * @param hash_fn function used to hash keys. 2 standard ones are defined: 180 * lh_ptr_hash and lh_char_hash for hashing pointer values 181 * and C strings respectively. 182 * @param equal_fn comparison function to compare keys. 2 standard ones defined: 183 * lh_ptr_hash and lh_char_hash for comparing pointer values 184 * and C strings respectively. 185 * @return a pointer onto the linkhash table. 186 */ 187 extern struct lh_table* lh_table_new(int size, const char *name, 188 lh_entry_free_fn *free_fn, 189 lh_hash_fn *hash_fn, 190 lh_equal_fn *equal_fn); 191 192 /** 193 * Convenience function to create a new linkhash 194 * table with char keys. 195 * @param size initial table size. 196 * @param name table name. 197 * @param free_fn callback function used to free memory for entries. 198 * @return a pointer onto the linkhash table. 199 */ 200 extern struct lh_table* lh_kchar_table_new(int size, const char *name, 201 lh_entry_free_fn *free_fn); 202 203 204 /** 205 * Convenience function to create a new linkhash 206 * table with ptr keys. 207 * @param size initial table size. 208 * @param name table name. 209 * @param free_fn callback function used to free memory for entries. 210 * @return a pointer onto the linkhash table. 211 */ 212 extern struct lh_table* lh_kptr_table_new(int size, const char *name, 213 lh_entry_free_fn *free_fn); 214 215 216 /** 217 * Free a linkhash table. 218 * If a callback free function is provided then it is called for all 219 * entries in the table. 220 * @param t table to free. 221 */ 222 extern void lh_table_free(struct lh_table *t); 223 224 225 /** 226 * Insert a record into the table. 227 * @param t the table to insert into. 228 * @param k a pointer to the key to insert. 229 * @param v a pointer to the value to insert. 230 */ 231 extern int lh_table_insert(struct lh_table *t, void *k, const void *v); 232 233 234 /** 235 * Lookup a record into the table. 236 * @param t the table to lookup 237 * @param k a pointer to the key to lookup 238 * @return a pointer to the record structure of the value or NULL if it does not exist. 239 */ 240 extern struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k); 241 242 /** 243 * Lookup a record into the table 244 * @param t the table to lookup 245 * @param k a pointer to the key to lookup 246 * @return a pointer to the found value or NULL if it does not exist. 247 * @deprecated Use lh_table_lookup_ex instead. 248 */ 249 THIS_FUNCTION_IS_DEPRECATED(extern const void* lh_table_lookup(struct lh_table *t, const void *k)); 250 251 /** 252 * Lookup a record in the table 253 * @param t the table to lookup 254 * @param k a pointer to the key to lookup 255 * @param v a pointer to a where to store the found value (set to NULL if it doesn't exist). 256 * @return whether or not the key was found 257 */ 258 extern json_bool lh_table_lookup_ex(struct lh_table *t, const void *k, void **v); 259 260 /** 261 * Delete a record from the table. 262 * If a callback free function is provided then it is called for the 263 * for the item being deleted. 264 * @param t the table to delete from. 265 * @param e a pointer to the entry to delete. 266 * @return 0 if the item was deleted. 267 * @return -1 if it was not found. 268 */ 269 extern int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e); 270 271 272 /** 273 * Delete a record from the table. 274 * If a callback free function is provided then it is called for the 275 * for the item being deleted. 276 * @param t the table to delete from. 277 * @param k a pointer to the key to delete. 278 * @return 0 if the item was deleted. 279 * @return -1 if it was not found. 280 */ 281 extern int lh_table_delete(struct lh_table *t, const void *k); 282 283 extern int lh_table_length(struct lh_table *t); 284 285 void lh_abort(const char *msg, ...); 286 void lh_table_resize(struct lh_table *t, int new_size); 287 288 #ifdef __cplusplus 289 } 290 #endif 291 292 #endif 293