ia64/xen-unstable

view tools/vnet/libxutil/hash_table.h @ 6766:219d96d545fc

merge?
author cl349@firebug.cl.cam.ac.uk
date Mon Sep 12 20:00:41 2005 +0000 (2005-09-12)
parents 9f22db685802
children 71b0f00f6344
line source
1 /*
2 * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
3 *
4 * This library is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation; either version 2.1 of the License, or
7 * (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this library; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
19 #ifndef _XUTIL_HASH_TABLE_H_
20 #define _XUTIL_HASH_TABLE_H_
22 #include "iostream.h"
24 typedef unsigned long Hashcode;
26 /** Type used to pass parameters to table functions. */
27 typedef union TableArg {
28 unsigned long ul;
29 void *ptr;
30 } TableArg;
32 /** An entry in a bucket list. */
33 typedef struct HTEntry {
34 /** Hashcode of the entry's key. */
35 Hashcode hashcode;
36 /** Identifier for this entry in the table. */
37 int index;
38 /** The key for this entry. */
39 void *key;
40 /** The value in this entry. */
41 void *value;
42 /** The next entry in the list. */
43 struct HTEntry *next;
44 } HTEntry;
46 /** A bucket in a rule table. */
47 typedef struct HTBucket {
48 /** Number of entries in the bucket. */
49 int count;
50 /** First entry in the bucket (may be null). */
51 HTEntry *head;
52 } HTBucket;
54 /** Default number of buckets in a hash table.
55 * You want enough buckets so the lists in the buckets will typically be short.
56 * It's a good idea if this is prime, since that will help to spread hashcodes
57 * around the table.
58 */
59 //#define HT_BUCKETS_N 1
60 //#define HT_BUCKETS_N 3
61 //#define HT_BUCKETS_N 7
62 //#define HT_BUCKETS_N 17
63 //#define HT_BUCKETS_N 97
64 //#define HT_BUCKETS_N 211
65 //#define HT_BUCKETS_N 401
66 #define HT_BUCKETS_N 1021
68 typedef struct HashTable HashTable;
70 /** Type for a function used to select table entries. */
71 typedef int TableTestFn(TableArg arg, HashTable *table, HTEntry *entry);
73 /** Type for a function to map over table entries. */
74 typedef int TableMapFn(TableArg arg, HashTable *table, HTEntry *entry);
76 /** Type for a function to free table entries. */
77 typedef void TableFreeFn(HashTable *table, HTEntry *entry);
79 /** Type for a function to hash table keys. */
80 typedef Hashcode TableHashFn(void *key);
82 /** Type for a function to test table keys for equality. */
83 typedef int TableEqualFn(void *key1, void *key2);
85 /** Type for a function to order table entries. */
86 typedef int TableOrderFn(HTEntry *e1, HTEntry *e2);
88 /** General hash table.
89 * A hash table with a list in each bucket.
90 * Functions can be supplied for freeing entries, hashing keys, and comparing keys.
91 * These all default to 0, when default behaviour treating keys as integers is used.
92 */
93 struct HashTable {
94 /** Flag indicating whether the table has been initialised. */
95 int init_done;
96 /** Next value for the id field in inserted rules. */
97 unsigned long next_id;
98 /** Number of buckets in the bucket array. */
99 int buckets_n;
100 /** Array of buckets, each with its own list. */
101 HTBucket *buckets;
102 /** Number of entries in the table. */
103 int entry_count;
104 /** Function to free keys and values in entries. */
105 TableFreeFn *entry_free_fn;
106 /** Function to hash keys. */
107 TableHashFn *key_hash_fn;
108 /** Function to compare keys for equality. */
109 TableEqualFn *key_equal_fn;
110 /** Place for the user of the table to hang extra data. */
111 void *user_data;
112 };
114 extern HashTable *HashTable_new(int bucket_n);
115 extern void HashTable_free(HashTable *table);
116 extern HTEntry * HTEntry_new(Hashcode hashcode, void *key, void *value);
117 extern void HTEntry_free(HTEntry *entry);
118 extern int HashTable_set_bucket_n(HashTable *table, int bucket_n);
119 extern void HashTable_clear(HashTable *table);
120 extern HTEntry * HashTable_add_entry(HashTable *table, Hashcode hashcode, void *key, void *value);
121 extern HTEntry * HashTable_get_entry(HashTable *table, void *key);
122 extern HTEntry * HashTable_add(HashTable *table, void *key, void *value);
123 extern void * HashTable_get(HashTable *table, void *key);
124 extern int HashTable_remove(HashTable *table, void *key);
125 extern HTEntry * HashTable_find_entry(HashTable *table, Hashcode hashcode,
126 TableTestFn *test_fn, TableArg arg);
127 extern int HashTable_remove_entry(HashTable *table, Hashcode hashcode,
128 TableTestFn *test_fn, TableArg arg);
129 //extern int HashTable_map(HashTable *table, TableMapFn *map_fn, TableArg arg);
130 extern void HashTable_print(HashTable *table, IOStream *out);
131 extern int HashTable_set_buckets_n(HashTable *table, int buckets_n);
132 extern int HashTable_adjust(HashTable *table, int buckets_min);
133 extern void pseudo_des(unsigned long *pleft, unsigned long *pright);
134 extern Hashcode hash_string(char *s);
136 extern int HashTable_order_bucket(HashTable *table, Hashcode hashcode, TableOrderFn *order);
138 /** Control whether to use hashing based on DES or simple
139 * hashing. DES hashing is `more random' but much more expensive.
140 */
141 #define HASH_PSEUDO_DES 0
143 /** Hash a long using a quick and dirty linear congruential random number generator.
144 * See `Numerical Recipes in C', Chapter 7, "An Even Quicker Generator".
145 *
146 * @param a value to hash
147 * @return hashed input
148 */
149 static inline unsigned long lcrng_hash(unsigned long a){
150 return (1664525L * a + 1013904223L);
151 }
153 /** Hash an unsigned long.
154 *
155 * @param a input to hash
156 * @return hashcode
157 */
158 static inline Hashcode hash_ul(unsigned long a){
159 #if HASH_PSEUDO_DES
160 unsigned long left = a;
161 unsigned long right = 0L;
162 pseudo_des(&left, &right);
163 return right;
164 #else
165 a = lcrng_hash(a);
166 a = lcrng_hash(a);
167 return a;
168 #endif
169 }
171 /** Hash two unsigned longs together.
172 *
173 * @param a input to hash
174 * @param b input to hash
175 * @return hashcode
176 */
177 static inline Hashcode hash_2ul(unsigned long a, unsigned long b){
178 #if HASH_PSEUDO_DES
179 unsigned long left = a;
180 unsigned long right = b;
181 pseudo_des(&left, &right);
182 return right;
183 #else
184 a = lcrng_hash(a);
185 a ^= b;
186 a = lcrng_hash(a);
187 return a;
188 #endif
189 }
191 /** Hash a hashcode and an unsigned long together.
192 *
193 * @param a input hashcode
194 * @param b input to hash
195 * @return hashcode
196 */
197 static inline Hashcode hash_hul(Hashcode a, unsigned long b){
198 #if HASH_PSEUDO_DES
199 unsigned long left = a;
200 unsigned long right = b;
201 pseudo_des(&left, &right);
202 return right;
203 #else
204 a ^= b;
205 a = lcrng_hash(a);
206 return a;
207 #endif
208 }
210 /** Macro to declare variables for HashTable_for_each() to use.
211 *
212 * @param entry variable that is set to entries in the table
213 */
214 #define HashTable_for_decl(entry) \
215 HashTable *_var_table; \
216 HTBucket *_var_bucket; \
217 HTBucket *_var_end; \
218 HTEntry *_var_next; \
219 HTEntry *entry
221 /** Macro to iterate over the entries in a hashtable.
222 * Must be in a scope where HashTable_for_decl() has been used to declare
223 * variables for it to use.
224 * The variable 'entry' is iterated over entries in the table.
225 * The code produced is syntactically a loop, so it must be followed by
226 * a loop body, typically some statements in braces:
227 * HashTable_for_each(entry, table){ ...loop body... }
228 *
229 * HashTable_for_each() and HashTable_for_decl() cannot be used for nested
230 * loops as variables will clash.
231 *
232 * @note The simplest way to code a direct loop over the entries in a hashtable
233 * is to use a loop over the buckets, with a nested loop over the entries
234 * in a bucket. Using this approach in a macro means the macro contains
235 * an opening brace, and calls to it must be followed by 2 braces!
236 * To avoid this the code has been restructured so that it is a for loop.
237 * So that statements could be used in the test expression of the for loop,
238 * we have used the gcc statement expression extension ({ ... }).
239 *
240 * @param entry variable to iterate over the entries
241 * @param table to iterate over (non-null)
242 */
243 #define HashTable_for_each(entry, table) \
244 _var_table = table; \
245 _var_bucket = _var_table->buckets; \
246 _var_end = _var_bucket + _var_table->buckets_n; \
247 for(entry=0, _var_next=0; \
248 ({ if(_var_next){ \
249 entry = _var_next; \
250 _var_next = entry->next; \
251 } else { \
252 while(_var_bucket < _var_end){ \
253 entry = _var_bucket->head; \
254 _var_bucket++; \
255 if(entry){ \
256 _var_next = entry->next; \
257 break; \
258 } \
259 } \
260 }; \
261 entry; }); \
262 entry = _var_next )
264 /** Map a function over the entries in a table.
265 * Mapping stops when the function returns a non-zero value.
266 * Uses the gcc statement expression extension ({ ... }).
267 *
268 * @param table to map over
269 * @param fn function to apply to entries
270 * @param arg first argument to call the function with
271 * @return 0 if fn always returned 0, first non-zero value otherwise
272 */
273 #define HashTable_map(table, fn, arg) \
274 ({ HashTable_for_decl(_var_entry); \
275 TableArg _var_arg = arg; \
276 int _var_value = 0; \
277 HashTable_for_each(_var_entry, table){ \
278 if((_var_value = fn(_var_arg, _var_table, _var_entry))) break; \
279 } \
280 _var_value; })
282 /** Cast x to the type for a key or value in a hash table.
283 * This avoids compiler warnings when using short integers
284 * as keys or values (especially on 64-bit platforms).
285 */
286 #define HKEY(x) ((void*)(unsigned long)(x))
288 /** Cast x from the type for a key or value in a hash table.
289 * to an unsigned long. This avoids compiler warnings when using
290 * short integers as keys or values (especially on 64-bit platforms).
291 */
292 #define HVAL(x) ((unsigned long)(x))
294 #endif /* !_XUTIL_HASH_TABLE_H_ */