1 /* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
2 /* Modifications made by Jack Lange <jarusl@cs.northwestern.edu> */
3 /* (c) 2008, Jack Lange <jarusl@cs.northwestern.edu> */
4 /* (c) 2008, The V3VEE Project <http://www.v3vee.org> */
7 #ifndef __VMM_HASHTABLE_H__
8 #define __VMM_HASHTABLE_H__
16 * struct hashtable *h;
18 * struct some_value *v;
20 * static uint_t hash_from_key_fn( void *k );
21 * static int keys_equal_fn ( void *key1, void *key2 );
23 * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
24 * k = (struct some_key *) malloc(sizeof(struct some_key));
25 * v = (struct some_value *) malloc(sizeof(struct some_value));
27 * (initialise k and v to suitable values)
29 * if (! hashtable_insert(h,k,v) )
32 * if (NULL == (found = hashtable_search(h,k) ))
33 * { printf("not found!"); }
35 * if (NULL == (found = hashtable_remove(h,k) ))
36 * { printf("Not found\n"); }
40 /* Macros may be used to define type-safe(r) hashtable access functions, with
41 * methods specialized to take known key and value types as parameters.
45 * Insert this at the start of your file:
47 * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
48 * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
49 * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
51 * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
52 * These operate just like hashtable_insert etc., with the same parameters,
53 * but their function signatures have 'struct some_key *' rather than
54 * 'void *', and hence can generate compile time errors if your program is
55 * supplying incorrect data as a key (and similarly for value).
57 * Note that the hash and key equality functions passed to create_hashtable
58 * still take 'void *' parameters instead of 'some key *'. This shouldn't be
59 * a difficult issue as they're only defined and passed once, and the other
60 * functions will ensure that only valid keys are supplied to them.
62 * The cost for this checking is increased code size and runtime overhead
63 * - if performance is important, it may be worth switching back to the
64 * unsafe methods once your program has been debugged with the safe methods.
65 * This just requires switching to some simple alternative defines - eg:
66 * #define insert_some hashtable_insert
70 ulong_t hash_long(ulong_t val, uint_t bits);
71 ulong_t hash_buffer(uchar_t * msg, uint_t length);
76 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
77 int fnname (struct hashtable * htable, keytype key, valuetype value) { \
78 return hashtable_insert(htable, (addr_t)key, (addr_t)value); \
81 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
82 valuetype * fnname (struct hashtable * htable, keytype key) { \
83 return (valuetype *) (hashtable_search(htable, (addr_t)key)); \
86 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype, free_key) \
87 valuetype * fnname (struct hashtable * htable, keytype key) { \
88 return (valuetype *) (hashtable_remove(htable, (addr_t)key, free_key)); \
96 struct hashtable * create_hashtable(uint_t min_size,
97 uint_t (*hashfunction) (addr_t key),
98 int (*key_eq_fn) (addr_t key1, addr_t key2));
100 void hashtable_destroy(struct hashtable * htable, int free_values, int free_keys);
103 * returns non-zero for successful insertion
105 * This function will cause the table to expand if the insertion would take
106 * the ratio of entries to table size over the maximum load factor.
108 * This function does not check for repeated insertions with a duplicate key.
109 * The value returned when using a duplicate key is undefined -- when
110 * the hashtable changes size, the order of retrieval of duplicate key
111 * entries is reversed.
112 * If in doubt, remove before insert.
114 int hashtable_insert(struct hashtable * htable, addr_t key, addr_t value);
116 int hashtable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value);
119 // returns the value associated with the key, or NULL if none found
120 addr_t hashtable_search(struct hashtable * htable, addr_t key);
122 // returns the value associated with the key, or NULL if none found
123 addr_t hashtable_remove(struct hashtable * htable, addr_t key, int free_key);
125 uint_t hashtable_count(struct hashtable * htable);
131 #define DEFINE_HASHTABLE_ITERATOR_SEARCH(fnname, keytype) \
132 int fnname (struct hashtable_itr * iter, struct hashtable * htable, keytype * key) { \
133 return (hashtable_iterator_search(iter, htable, key)); \
138 /*****************************************************************************/
139 /* This struct is only concrete here to allow the inlining of two of the
140 * accessor functions. */
141 struct hashtable_iter {
142 struct hashtable * htable;
143 struct hash_entry * entry;
144 struct hash_entry * parent;
149 struct hashtable_iter * create_hashtable_iterator(struct hashtable * htable);
151 /* - return the value of the (key,value) pair at the current position */
153 addr_t hashtable_get_iter_key(struct hashtable_iter * iter);
155 return iter->entry->key;
160 /* value - return the value of the (key,value) pair at the current position */
162 addr_t hashtable_get_iter_value(struct hashtable_iter * iter);
164 return iter->entry->value;
170 /* returns zero if advanced to end of table */
171 int hashtable_iterator_advance(struct hashtable_iter * iter);
173 /* remove current element and advance the iterator to the next element
174 * NB: if you need the value to free it, read it before
175 * removing. ie: beware memory leaks!
176 * returns zero if advanced to end of table
178 int hashtable_iterator_remove(struct hashtable_iter * iter, int free_key);
181 /* search - overwrite the supplied iterator, to point to the entry
182 * matching the supplied key.
183 * returns zero if not found. */
184 int hashtable_iterator_search(struct hashtable_iter * iter, struct hashtable * htable, addr_t key);
189 #endif // ! __V3VEE__
192 #endif /* __VMM_HASHTABLE_H__ */
232 * Copyright (c) 2002, Christopher Clark
233 * All rights reserved.
235 * Redistribution and use in source and binary forms, with or without
236 * modification, are permitted provided that the following conditions
239 * * Redistributions of source code must retain the above copyright
240 * notice, this list of conditions and the following disclaimer.
242 * * Redistributions in binary form must reproduce the above copyright
243 * notice, this list of conditions and the following disclaimer in the
244 * documentation and/or other materials provided with the distribution.
246 * * Neither the name of the original author; nor the names of any contributors
247 * may be used to endorse or promote products derived from this software
248 * without specific prior written permission.
251 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
252 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
253 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
254 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
255 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
256 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
257 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
258 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
259 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
260 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
261 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.