• source navigation  • diff markup  • identifier search  • freetext search  • 

Sources/json-c/linkhash.h

  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 #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 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 

This page was automatically generated by LXR 0.3.1.  •  OpenWrt