root/src/json-lib/linkhash.h

Revision efa9375336eec306ede14a9a1032985a71482810, 5.9 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 4 years ago)

refs #294 resmon no support arbitrary json objects

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