Atomic PCI-space accesses
[akaros.git] / kern / include / hashtable.h
1 /* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
2  * 
3  * Modified 2009 by Barret Rhoden <brho@cs.berkeley.edu>
4  * Changes include:
5  *   - No longer frees keys or values.  It's up to the client to do that.
6  *   - Provides common hash and equality functions (meant for longs)
7  *   - Uses the slab allocator for hash entry allocation.
8  *   - Merges the iterator code with the main hash table code, mostly to avoid
9  *   externing the hentry cache.
10  *   - hash for each */
11
12 #ifndef __ROS_KERN_HASHTABLE_H__
13 #define __ROS_KERN_HASHTABLE_H__
14
15 #ifdef __DEPUTY__
16 #pragma nodeputy
17 #endif
18
19 #ifdef __SHARC__
20 #pragma nosharc
21 #endif
22
23 #include <ros/common.h>
24
25 /*****************************************************************************/
26 typedef struct hash_entry
27 {
28     void *k, *v;
29     size_t h;
30     struct hash_entry *next;
31 } hash_entry_t;
32
33 typedef struct hashtable {
34     size_t tablelength;
35     hash_entry_t **table;
36     size_t entrycount;
37     size_t loadlimit;
38     size_t primeindex;
39     size_t (*hashfn) (void *k);
40     ssize_t (*eqfn) (void *k1, void *k2);
41 } hashtable_t;
42
43 static inline size_t indexFor(unsigned int tablelength, unsigned int hashvalue)
44 {
45         return (hashvalue % tablelength);
46 };
47
48 /*****************************************************************************/
49
50 /* Example of use:
51  *              hashtable_init(); // Do this once during kernel initialization
52  *
53  *      struct hashtable  *h;
54  *      struct some_key   *k;
55  *      struct some_value *v;
56  *
57  *      static size_t         hash_from_key_fn( void *k );
58  *      static ssize_t        keys_equal_fn ( void *key1, void *key2 );
59  *
60  *      h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
61  *      k = (struct some_key *)     kmalloc(sizeof(struct some_key));
62  *      v = (struct some_value *)   kmalloc(sizeof(struct some_value));
63  *
64  *      (initialise k and v to suitable values)
65  * 
66  *      if (! hashtable_insert(h,k,v) )
67  *      {     panic("Hashtable broken...\n");       }
68  *
69  *      if (NULL == (found = hashtable_search(h,k) ))
70  *      {    printk("not found!");                  }
71  *
72  *      if (NULL == (found = hashtable_remove(h,k) ))
73  *      {    printk("Not found\n");                 }
74  *
75  */
76
77 /* Macros may be used to define type-safe(r) hashtable access functions, with
78  * methods specialized to take known key and value types as parameters.
79  * 
80  * Example:
81  *
82  * Insert this at the start of your file:
83  *
84  * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
85  * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
86  * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
87  *
88  * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
89  * These operate just like hashtable_insert etc., with the same parameters,
90  * but their function signatures have 'struct some_key *' rather than
91  * 'void *', and hence can generate compile time errors if your program is
92  * supplying incorrect data as a key (and similarly for value).
93  *
94  * Note that the hash and key equality functions passed to create_hashtable
95  * still take 'void *' parameters instead of 'some key *'. This shouldn't be
96  * a difficult issue as they're only defined and passed once, and the other
97  * functions will ensure that only valid keys are supplied to them.
98  *
99  * The cost for this checking is increased code size and runtime overhead
100  * - if performance is important, it may be worth switching back to the
101  * unsafe methods once your program has been debugged with the safe methods.
102  * This just requires switching to some simple alternative defines - eg:
103  * #define insert_some hashtable_insert
104  *
105  */
106
107 /* Call this once on bootup, after initializing the slab allocator.  */
108 void hashtable_init(void);
109
110 /* Common hash/equals functions.  Don't call these directly. */
111 size_t __generic_hash(void *k);
112 ssize_t __generic_eq(void *k1, void *k2);
113
114 /*****************************************************************************
115  * create_hashtable
116    
117  * @name                    create_hashtable
118  * @param   minsize         minimum initial size of hashtable
119  * @param   hashfunction    function for hashing keys
120  * @param   key_eq_fn       function for determining key equality
121  * @return                  newly created hashtable or NULL on failure
122  */
123
124 hashtable_t *
125 create_hashtable(size_t minsize,
126                  size_t (*hashfunction) (void*),
127                  ssize_t (*key_eq_fn) (void*,void*));
128
129 /*****************************************************************************
130  * hashtable_insert
131    
132  * @name        hashtable_insert
133  * @param   h   the hashtable to insert into
134  * @param   k   the key
135  * @param   v   the value
136  * @return      non-zero for successful insertion
137  *
138  * This function will cause the table to expand if the insertion would take
139  * the ratio of entries to table size over the maximum load factor.
140  *
141  * This function does not check for repeated insertions with a duplicate key.
142  * The value returned when using a duplicate key is undefined -- when
143  * the hashtable changes size, the order of retrieval of duplicate key
144  * entries is reversed.
145  * If in doubt, remove before insert.
146  */
147
148 ssize_t 
149 hashtable_insert(hashtable_t *h, void *k, void *v);
150
151 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
152 ssize_t fnname (hashtable_t *h, keytype *k, valuetype *v) \
153 { \
154     return hashtable_insert(h,k,v); \
155 }
156
157 /*****************************************************************************
158  * hashtable_search
159    
160  * @name        hashtable_search
161  * @param   h   the hashtable to search
162  * @param   k   the key to search for
163  * @return      the value associated with the key, or NULL if none found
164  */
165
166 void *
167 hashtable_search(hashtable_t *h, void *k);
168
169 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
170 valuetype * fnname (hashtable_t *h, keytype *k) \
171 { \
172     return (valuetype *) (hashtable_search(h,k)); \
173 }
174
175 /*****************************************************************************
176  * hashtable_remove
177    
178  * @name        hashtable_remove
179  * @param   h   the hashtable to remove the item from
180  * @param   k   the key to search for
181  * @return      the value associated with the key, or NULL if none found
182  *
183  * Caller ought to free the key, if appropriate.
184  */
185
186 void * /* returns value */
187 hashtable_remove(hashtable_t *h, void *k);
188
189 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
190 valuetype * fnname (hashtable_t *h, keytype *k) \
191 { \
192     return (valuetype *) (hashtable_remove(h,k)); \
193 }
194
195
196 /*****************************************************************************
197  * hashtable_count
198    
199  * @name        hashtable_count
200  * @param   h   the hashtable
201  * @return      the number of items stored in the hashtable
202  */
203
204 size_t
205 hashtable_count(hashtable_t *h);
206
207
208 /*****************************************************************************
209  * hashtable_destroy
210    
211  * @name        hashtable_destroy
212  * @param   h   the hashtable
213  *
214  * This will not free the values or the keys.  Each user of the hashtable may
215  * have a different way of freeing (such as the slab allocator, kfree, or
216  * nothing (key is just an integer)).
217  *
218  * If the htable isn't empty, you ought to iterate through and destroy manually.
219  * This will warn if you try to destroy an non-empty htable.
220  */
221
222 void
223 hashtable_destroy(hashtable_t *h);
224
225 /***************************** Hashtable Iterator ****************************/
226 /*****************************************************************************/
227 /* This struct is only concrete here to allow the inlining of two of the
228  * accessor functions. */
229 typedef struct hashtable_itr {
230     hashtable_t *h;
231     hash_entry_t *e;
232     hash_entry_t *parent;
233     size_t index;
234 } hashtable_itr_t;
235
236 /*****************************************************************************/
237 /* hashtable_iterator.  Be sure to kfree this when you are done.
238  */
239
240 hashtable_itr_t *
241 hashtable_iterator(hashtable_t *h);
242
243 /*****************************************************************************/
244 /* hashtable_iterator_key
245  * - return the key of the (key,value) pair at the current position
246  *
247  * Keep this in sync with the non-externed version in the .c */
248
249 extern inline void *
250 hashtable_iterator_key(hashtable_itr_t *i)
251 {
252     return i->e->k;
253 }
254
255 /*****************************************************************************/
256 /* value - return the value of the (key,value) pair at the current position
257  *
258  * Keep this in sync with the non-externed version in the .c */
259
260 extern inline void *
261 hashtable_iterator_value(hashtable_itr_t *i)
262 {
263     return i->e->v;
264 }
265
266 /*****************************************************************************/
267 /* advance - advance the iterator to the next element
268  *           returns zero if advanced to end of table */
269
270 ssize_t
271 hashtable_iterator_advance(hashtable_itr_t *itr);
272
273 /*****************************************************************************/
274 /* remove - remove current element and advance the iterator to the next element
275  *          NB: if you need the key or value to free it, read it before
276  *          removing. ie: beware memory leaks!  this will not remove the key.
277  *          returns zero if advanced to end of table */
278
279 ssize_t
280 hashtable_iterator_remove(hashtable_itr_t *itr);
281
282 /*****************************************************************************/
283 /* search - overwrite the supplied iterator, to point to the entry
284  *          matching the supplied key.
285  *          h points to the hashtable to be searched.
286  *          returns zero if not found. */
287 ssize_t
288 hashtable_iterator_search(hashtable_itr_t *itr,
289                           hashtable_t *h, void *k);
290
291 #define DEFINE_HASHTABLE_ITERATOR_SEARCH(fnname, keytype) \
292 ssize_t fnname (hashtable_itr_t *i, hashtable_t *h, keytype *k) \
293 { \
294     return (hashtable_iterator_search(i,h,k)); \
295 }
296
297 /* Runs func on each member of the hash table */
298 void hash_for_each(struct hashtable *hash, void func(void*));
299 /* Same, but removes the item too */
300 void hash_for_each_remove(struct hashtable *hash, void func(void*));
301
302 #endif /* __ROS_KERN_HASHTABLE_H__ */
303
304 /*
305  * Copyright (c) 2002, 2004, Christopher Clark
306  * All rights reserved.
307  * 
308  * Redistribution and use in source and binary forms, with or without
309  * modification, are permitted provided that the following conditions
310  * are met:
311  * 
312  * * Redistributions of source code must retain the above copyright
313  * notice, this list of conditions and the following disclaimer.
314  * 
315  * * Redistributions in binary form must reproduce the above copyright
316  * notice, this list of conditions and the following disclaimer in the
317  * documentation and/or other materials provided with the distribution.
318  * 
319  * * Neither the name of the original author; nor the names of any contributors
320  * may be used to endorse or promote products derived from this software
321  * without specific prior written permission.
322  * 
323  * 
324  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
325  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
326  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
327  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
328  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
329  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
330  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
331  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
332  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
333  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
334  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
335 */