Fixed up a few small bugs in the syscall_server stuff
[akaros.git] / kern / include / hashtable.h
1 /* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
2
3 #ifndef __ROS_KERN_HASHTABLE_H__
4 #define __ROS_KERN_HASHTABLE_H__
5
6 #include <ros/common.h>
7
8 /*****************************************************************************/
9 typedef struct hash_entry
10 {
11     void *k, *v;
12     size_t h;
13     struct hash_entry *next;
14 } hash_entry_t;
15
16 typedef struct hashtable {
17     size_t tablelength;
18     hash_entry_t **table;
19     size_t entrycount;
20     size_t loadlimit;
21     size_t primeindex;
22     size_t (*hashfn) (void *k);
23     ssize_t (*eqfn) (void *k1, void *k2);
24 } hashtable_t;
25
26 size_t hash(struct hashtable *h, void *k);
27 static inline size_t indexFor(unsigned int tablelength, unsigned int hashvalue)
28 {
29         return (hashvalue % tablelength);
30 };
31 #define freekey(X) kfree(X)
32
33 /*****************************************************************************/
34
35 /* Example of use:
36  *
37  *      struct hashtable  *h;
38  *      struct some_key   *k;
39  *      struct some_value *v;
40  *
41  *      static size_t         hash_from_key_fn( void *k );
42  *      static ssize_t        keys_equal_fn ( void *key1, void *key2 );
43  *
44  *      h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
45  *      k = (struct some_key *)     kmalloc(sizeof(struct some_key));
46  *      v = (struct some_value *)   kmalloc(sizeof(struct some_value));
47  *
48  *      (initialise k and v to suitable values)
49  * 
50  *      if (! hashtable_insert(h,k,v) )
51  *      {     panic("Hashtable broken...\n");       }
52  *
53  *      if (NULL == (found = hashtable_search(h,k) ))
54  *      {    printk("not found!");                  }
55  *
56  *      if (NULL == (found = hashtable_remove(h,k) ))
57  *      {    printk("Not found\n");                 }
58  *
59  */
60
61 /* Macros may be used to define type-safe(r) hashtable access functions, with
62  * methods specialized to take known key and value types as parameters.
63  * 
64  * Example:
65  *
66  * Insert this at the start of your file:
67  *
68  * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
69  * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
70  * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
71  *
72  * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
73  * These operate just like hashtable_insert etc., with the same parameters,
74  * but their function signatures have 'struct some_key *' rather than
75  * 'void *', and hence can generate compile time errors if your program is
76  * supplying incorrect data as a key (and similarly for value).
77  *
78  * Note that the hash and key equality functions passed to create_hashtable
79  * still take 'void *' parameters instead of 'some key *'. This shouldn't be
80  * a difficult issue as they're only defined and passed once, and the other
81  * functions will ensure that only valid keys are supplied to them.
82  *
83  * The cost for this checking is increased code size and runtime overhead
84  * - if performance is important, it may be worth switching back to the
85  * unsafe methods once your program has been debugged with the safe methods.
86  * This just requires switching to some simple alternative defines - eg:
87  * #define insert_some hashtable_insert
88  *
89  */
90
91 /*****************************************************************************
92  * create_hashtable
93    
94  * @name                    create_hashtable
95  * @param   minsize         minimum initial size of hashtable
96  * @param   hashfunction    function for hashing keys
97  * @param   key_eq_fn       function for determining key equality
98  * @return                  newly created hashtable or NULL on failure
99  */
100
101 hashtable_t *
102 create_hashtable(size_t minsize,
103                  size_t (*hashfunction) (void*),
104                  ssize_t (*key_eq_fn) (void*,void*));
105
106 /*****************************************************************************
107  * hashtable_insert
108    
109  * @name        hashtable_insert
110  * @param   h   the hashtable to insert into
111  * @param   k   the key - hashtable claims ownership and will free on removal
112  * @param   v   the value - does not claim ownership
113  * @return      non-zero for successful insertion
114  *
115  * This function will cause the table to expand if the insertion would take
116  * the ratio of entries to table size over the maximum load factor.
117  *
118  * This function does not check for repeated insertions with a duplicate key.
119  * The value returned when using a duplicate key is undefined -- when
120  * the hashtable changes size, the order of retrieval of duplicate key
121  * entries is reversed.
122  * If in doubt, remove before insert.
123  */
124
125 ssize_t 
126 hashtable_insert(hashtable_t *h, void *k, void *v);
127
128 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
129 ssize_t fnname (hashtable_t *h, keytype *k, valuetype *v) \
130 { \
131     return hashtable_insert(h,k,v); \
132 }
133
134 /*****************************************************************************
135  * hashtable_search
136    
137  * @name        hashtable_search
138  * @param   h   the hashtable to search
139  * @param   k   the key to search for  - does not claim ownership
140  * @return      the value associated with the key, or NULL if none found
141  */
142
143 void *
144 hashtable_search(hashtable_t *h, void *k);
145
146 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
147 valuetype * fnname (hashtable_t *h, keytype *k) \
148 { \
149     return (valuetype *) (hashtable_search(h,k)); \
150 }
151
152 /*****************************************************************************
153  * hashtable_remove
154    
155  * @name        hashtable_remove
156  * @param   h   the hashtable to remove the item from
157  * @param   k   the key to search for  - does not claim ownership
158  * @return      the value associated with the key, or NULL if none found
159  */
160
161 void * /* returns value */
162 hashtable_remove(hashtable_t *h, void *k);
163
164 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
165 valuetype * fnname (hashtable_t *h, keytype *k) \
166 { \
167     return (valuetype *) (hashtable_remove(h,k)); \
168 }
169
170
171 /*****************************************************************************
172  * hashtable_count
173    
174  * @name        hashtable_count
175  * @param   h   the hashtable
176  * @return      the number of items stored in the hashtable
177  */
178 size_t
179 hashtable_count(hashtable_t *h);
180
181
182 /*****************************************************************************
183  * hashtable_destroy
184    
185  * @name        hashtable_destroy
186  * @param   h   the hashtable
187  * @param       free_values     whether to call 'free' on the remaining values
188  */
189
190 void
191 hashtable_destroy(hashtable_t *h, int free_values);
192
193 #endif /* __ROS_KERN_HASHTABLE_H__ */
194
195 /*
196  * Copyright (c) 2002, Christopher Clark
197  * All rights reserved.
198  * 
199  * Redistribution and use in source and binary forms, with or without
200  * modification, are permitted provided that the following conditions
201  * are met:
202  * 
203  * * Redistributions of source code must retain the above copyright
204  * notice, this list of conditions and the following disclaimer.
205  * 
206  * * Redistributions in binary form must reproduce the above copyright
207  * notice, this list of conditions and the following disclaimer in the
208  * documentation and/or other materials provided with the distribution.
209  * 
210  * * Neither the name of the original author; nor the names of any contributors
211  * may be used to endorse or promote products derived from this software
212  * without specific prior written permission.
213  * 
214  * 
215  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
216  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
217  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
218  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
219  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
220  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
221  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
222  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
223  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
224  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
225  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
226 */