2 Copyright (c) 2002, 2004, Christopher Clark
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
9 * Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in the
14 documentation and/or other materials provided with the distribution.
16 * Neither the name of the original author; nor the names of any contributors
17 may be used to endorse or promote products derived from this software
18 without specific prior written permission.
21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
25 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 /* Modifications made by Jack Lange <jarusl@cs.northwestern.edu> */
37 #ifndef __VMM_HASHTABLE_H__
38 #define __VMM_HASHTABLE_H__
46 * struct hashtable *h;
48 * struct some_value *v;
50 * static uint_t hash_from_key_fn( void *k );
51 * static int keys_equal_fn ( void *key1, void *key2 );
53 * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
54 * k = (struct some_key *) malloc(sizeof(struct some_key));
55 * v = (struct some_value *) malloc(sizeof(struct some_value));
57 * (initialise k and v to suitable values)
59 * if (! hashtable_insert(h,k,v) )
62 * if (NULL == (found = hashtable_search(h,k) ))
63 * { printf("not found!"); }
65 * if (NULL == (found = hashtable_remove(h,k) ))
66 * { printf("Not found\n"); }
70 /* Macros may be used to define type-safe(r) hashtable access functions, with
71 * methods specialized to take known key and value types as parameters.
75 * Insert this at the start of your file:
77 * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
78 * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
79 * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
81 * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
82 * These operate just like hashtable_insert etc., with the same parameters,
83 * but their function signatures have 'struct some_key *' rather than
84 * 'void *', and hence can generate compile time errors if your program is
85 * supplying incorrect data as a key (and similarly for value).
87 * Note that the hash and key equality functions passed to create_hashtable
88 * still take 'void *' parameters instead of 'some key *'. This shouldn't be
89 * a difficult issue as they're only defined and passed once, and the other
90 * functions will ensure that only valid keys are supplied to them.
92 * The cost for this checking is increased code size and runtime overhead
93 * - if performance is important, it may be worth switching back to the
94 * unsafe methods once your program has been debugged with the safe methods.
95 * This just requires switching to some simple alternative defines - eg:
96 * #define insert_some hashtable_insert
100 ulong_t hash_long(ulong_t val, uint_t bits);
101 ulong_t hash_buffer(uchar_t * msg, uint_t length);
106 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
107 int fnname (struct hashtable * htable, keytype key, valuetype value) { \
108 return hashtable_insert(htable, (addr_t)key, (addr_t)value); \
111 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
112 valuetype * fnname (struct hashtable * htable, keytype key) { \
113 return (valuetype *) (hashtable_search(htable, (addr_t)key)); \
116 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype, free_key) \
117 valuetype * fnname (struct hashtable * htable, keytype key) { \
118 return (valuetype *) (hashtable_remove(htable, (addr_t)key, free_key)); \
126 struct hashtable * create_hashtable(uint_t min_size,
127 uint_t (*hashfunction) (addr_t key),
128 int (*key_eq_fn) (addr_t key1, addr_t key2));
130 void hashtable_destroy(struct hashtable * htable, int free_values, int free_keys);
133 * returns non-zero for successful insertion
135 * This function will cause the table to expand if the insertion would take
136 * the ratio of entries to table size over the maximum load factor.
138 * This function does not check for repeated insertions with a duplicate key.
139 * The value returned when using a duplicate key is undefined -- when
140 * the hashtable changes size, the order of retrieval of duplicate key
141 * entries is reversed.
142 * If in doubt, remove before insert.
144 int hashtable_insert(struct hashtable * htable, addr_t key, addr_t value);
146 int hashtable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value);
149 // returns the value associated with the key, or NULL if none found
150 addr_t hashtable_search(struct hashtable * htable, addr_t key);
152 // returns the value associated with the key, or NULL if none found
153 addr_t hashtable_remove(struct hashtable * htable, addr_t key, int free_key);
155 uint_t hashtable_count(struct hashtable * htable);
161 #define DEFINE_HASHTABLE_ITERATOR_SEARCH(fnname, keytype) \
162 int fnname (struct hashtable_itr * iter, struct hashtable * htable, keytype * key) { \
163 return (hashtable_iterator_search(iter, htable, key)); \
168 /*****************************************************************************/
169 /* This struct is only concrete here to allow the inlining of two of the
170 * accessor functions. */
171 struct hashtable_iter {
172 struct hashtable * htable;
173 struct hash_entry * entry;
174 struct hash_entry * parent;
179 struct hashtable_iter * create_hashtable_iterator(struct hashtable * htable);
181 /* - return the value of the (key,value) pair at the current position */
183 addr_t hashtable_get_iter_key(struct hashtable_iter * iter);
185 return iter->entry->key;
190 /* value - return the value of the (key,value) pair at the current position */
192 addr_t hashtable_get_iter_value(struct hashtable_iter * iter);
194 return iter->entry->value;
200 /* returns zero if advanced to end of table */
201 int hashtable_iterator_advance(struct hashtable_iter * iter);
203 /* remove current element and advance the iterator to the next element
204 * NB: if you need the value to free it, read it before
205 * removing. ie: beware memory leaks!
206 * returns zero if advanced to end of table
208 int hashtable_iterator_remove(struct hashtable_iter * iter, int free_key);
211 /* search - overwrite the supplied iterator, to point to the entry
212 * matching the supplied key.
213 * returns zero if not found. */
214 int hashtable_iterator_search(struct hashtable_iter * iter, struct hashtable * htable, addr_t key);
219 #endif // ! __V3VEE__
222 #endif /* __VMM_HASHTABLE_H__ */
262 * Copyright (c) 2002, Christopher Clark
263 * All rights reserved.
265 * Redistribution and use in source and binary forms, with or without
266 * modification, are permitted provided that the following conditions
269 * * Redistributions of source code must retain the above copyright
270 * notice, this list of conditions and the following disclaimer.
272 * * Redistributions in binary form must reproduce the above copyright
273 * notice, this list of conditions and the following disclaimer in the
274 * documentation and/or other materials provided with the distribution.
276 * * Neither the name of the original author; nor the names of any contributors
277 * may be used to endorse or promote products derived from this software
278 * without specific prior written permission.
281 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
282 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
283 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
284 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
285 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
286 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
287 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
288 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
289 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
290 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
291 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.