printk: check for user pointers in format string parameters
[akaros.git] / kern / src / hashtable.c
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  *   - Uses the slab allocator for hash entry allocation.
7  *   - Merges the iterator code with the main hash table code, mostly to avoid
8  *   externing the hentry cache. */
9
10 #include <arch/types.h>
11 #include <assert.h>
12 #include <hash.h>
13 #include <hashtable.h>
14 #include <kmalloc.h>
15 #include <ros/common.h>
16 #include <slab.h>
17 #include <stdio.h>
18 #include <string.h>
19
20 /*
21 Credit for primes table: Aaron Krowne
22  http://br.endernet.org/~akrowne/
23  http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
24 */
25 static const unsigned int primes[] = {
26     53,        97,        193,       389,       769,       1543,     3079,
27     6151,      12289,     24593,     49157,     98317,     196613,   393241,
28     786433,    1572869,   3145739,   6291469,   12582917,  25165843, 50331653,
29     100663319, 201326611, 402653189, 805306457, 1610612741};
30 const unsigned int prime_table_length = sizeof(primes) / sizeof(primes[0]);
31 #define APPLY_MAX_LOAD_FACTOR(size) ((size * 13) / 20)
32 // const float max_load_factor = 0.65;
33
34 struct kmem_cache *hentry_cache;
35
36 /* Call this once on bootup, after initializing the slab allocator.  */
37 void hashtable_init(void)
38 {
39         hentry_cache = kmem_cache_create("hash_entry",
40                                          sizeof(struct hash_entry),
41                                          __alignof__(struct hash_entry), 0,
42                                          NULL, 0, 0, NULL);
43 }
44
45 /* Common hash/equals functions.  Don't call these directly. */
46 size_t __generic_hash(void *k)
47 {
48         return hash_long((unsigned long)k, BITS_PER_LONG);
49 }
50
51 ssize_t __generic_eq(void *k1, void *k2)
52 {
53         return k1 == k2;
54 }
55
56 /*****************************************************************************/
57 hashtable_t *create_hashtable(size_t minsize, size_t (*hashf)(void *),
58                               ssize_t (*eqf)(void *, void *))
59 {
60         hashtable_t *h;
61         size_t pindex, size = primes[0];
62
63         /* Check requested hashtable isn't too large */
64         if (minsize > (1u << 30))
65                 return NULL;
66         /* Enforce size as prime */
67         for (pindex = 0; pindex < prime_table_length; pindex++) {
68                 if (primes[pindex] > minsize) {
69                         size = primes[pindex];
70                         break;
71                 }
72         }
73         h = (hashtable_t *)kmalloc(sizeof(hashtable_t), 0);
74         if (NULL == h)
75                 return NULL; /*oom*/
76         h->table = (hash_entry_t **)kmalloc(sizeof(hash_entry_t *) * size, 0);
77         if (NULL == h->table) {
78                 kfree(h);
79                 return NULL;
80         } /*oom*/
81         memset(h->table, 0, size * sizeof(hash_entry_t *));
82         h->tablelength = size;
83         h->primeindex = pindex;
84         h->entrycount = 0;
85         h->hashfn = hashf;
86         h->eqfn = eqf;
87         h->loadlimit = APPLY_MAX_LOAD_FACTOR(size);
88         return h;
89 }
90
91 /*****************************************************************************/
92 static size_t hash(hashtable_t *h, void *k)
93 {
94         /* Aim to protect against poor hash functions by adding logic here
95          * - logic taken from java 1.4 hashtable source */
96         size_t i = h->hashfn(k);
97
98         i += ~(i << 9);
99         i ^= ((i >> 14) | (i << 18)); /* >>> */
100         i += (i << 4);
101         i ^= ((i >> 10) | (i << 22)); /* >>> */
102         return i;
103 }
104
105 /*****************************************************************************/
106 static ssize_t hashtable_expand(hashtable_t *h)
107 {
108         /* Double the size of the table to accomodate more entries */
109         hash_entry_t **newtable;
110         hash_entry_t *e;
111         hash_entry_t **pE;
112         size_t newsize, i, index;
113
114         /* Check we're not hitting max capacity */
115         if (h->primeindex == (prime_table_length - 1))
116                 return 0;
117         newsize = primes[++(h->primeindex)];
118
119         newtable =
120             (hash_entry_t **)kmalloc(sizeof(hash_entry_t *) * newsize, 0);
121         if (NULL != newtable) {
122                 memset(newtable, 0, newsize * sizeof(hash_entry_t *));
123                 /* This algorithm is not 'stable'. ie. it reverses the list
124                  * when it transfers entries between the tables */
125                 for (i = 0; i < h->tablelength; i++) {
126                         while (NULL != (e = h->table[i])) {
127                                 h->table[i] = e->next;
128                                 index = indexFor(newsize, e->h);
129                                 e->next = newtable[index];
130                                 newtable[index] = e;
131                         }
132                 }
133                 kfree(h->table);
134                 h->table = newtable;
135         }
136         /* Plan B: realloc instead */
137         else {
138                 newtable = (hash_entry_t **)krealloc(
139                     h->table, newsize * sizeof(hash_entry_t *), 0);
140                 if (NULL == newtable) {
141                         (h->primeindex)--;
142                         return 0;
143                 }
144                 h->table = newtable;
145                 memset(newtable[h->tablelength], 0, newsize - h->tablelength);
146                 for (i = 0; i < h->tablelength; i++) {
147                         for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
148                                 index = indexFor(newsize, e->h);
149                                 if (index == i) {
150                                         pE = &(e->next);
151                                 } else {
152                                         *pE = e->next;
153                                         e->next = newtable[index];
154                                         newtable[index] = e;
155                                 }
156                         }
157                 }
158         }
159         h->tablelength = newsize;
160         h->loadlimit = APPLY_MAX_LOAD_FACTOR(newsize);
161         return -1;
162 }
163
164 /*****************************************************************************/
165 size_t hashtable_count(hashtable_t *h)
166 {
167         return h->entrycount;
168 }
169
170 /*****************************************************************************/
171 ssize_t hashtable_insert(hashtable_t *h, void *k, void *v)
172 {
173         /* This method allows duplicate keys - but they shouldn't be used */
174         size_t index;
175         hash_entry_t *e;
176
177         if (++(h->entrycount) > h->loadlimit) {
178                 /* Ignore the return value. If expand fails, we should
179                  * still try cramming just this value into the existing table
180                  * -- we may not have memory for a larger table, but one more
181                  * element may be ok. Next time we insert, we'll try expanding
182                  * again.*/
183                 hashtable_expand(h);
184         }
185         e = (hash_entry_t *)kmem_cache_alloc(hentry_cache, 0);
186         if (NULL == e) {
187                 --(h->entrycount);
188                 return 0;
189         } /*oom*/
190         e->h = hash(h, k);
191         index = indexFor(h->tablelength, e->h);
192         e->k = k;
193         e->v = v;
194         e->next = h->table[index];
195         h->table[index] = e;
196         return -1;
197 }
198
199 /*****************************************************************************/
200 /* returns value associated with key */
201 void *hashtable_search(hashtable_t *h, void *k)
202 {
203         hash_entry_t *e;
204         size_t hashvalue, index;
205
206         hashvalue = hash(h, k);
207         index = indexFor(h->tablelength, hashvalue);
208         e = h->table[index];
209         while (NULL != e) {
210                 /* Check hash value to short circuit heavier comparison */
211                 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
212                         return e->v;
213                 e = e->next;
214         }
215         return NULL;
216 }
217
218 /*****************************************************************************/
219 /* returns value associated with key */
220 void *hashtable_remove(hashtable_t *h, void *k)
221 {
222         /* TODO: consider compacting the table when the load factor drops
223          * enough, or provide a 'compact' method. */
224
225         hash_entry_t *e;
226         hash_entry_t **pE;
227         void *v;
228         size_t hashvalue, index;
229
230         hashvalue = hash(h, k);
231         index = indexFor(h->tablelength, hash(h, k));
232         pE = &(h->table[index]);
233         e = *pE;
234         while (NULL != e) {
235                 /* Check hash value to short circuit heavier comparison */
236                 if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
237                         *pE = e->next;
238                         h->entrycount--;
239                         v = e->v;
240                         kmem_cache_free(hentry_cache, e);
241                         return v;
242                 }
243                 pE = &(e->next);
244                 e = e->next;
245         }
246         return NULL;
247 }
248
249 /*****************************************************************************/
250 /* destroy */
251 void hashtable_destroy(hashtable_t *h)
252 {
253         if (hashtable_count(h))
254                 warn("Destroying a non-empty hashtable, clean up after "
255                      "yourself!\n");
256
257         size_t i;
258         hash_entry_t *e, *f;
259         hash_entry_t **table = h->table;
260
261         for (i = 0; i < h->tablelength; i++) {
262                 e = table[i];
263                 while (NULL != e) {
264                         f = e;
265                         e = e->next;
266                         kmem_cache_free(hentry_cache, f);
267                 }
268         }
269         kfree(h->table);
270         kfree(h);
271 }
272
273 /*****************************************************************************/
274 /* hashtable_iterator    - iterator constructor, be sure to kfree this when
275  * you're done.
276  *
277  * If the htable isn't empty, e and index will refer to the first entry. */
278
279 hashtable_itr_t *hashtable_iterator(hashtable_t *h)
280 {
281         size_t i, tablelength;
282         hashtable_itr_t *itr =
283             (hashtable_itr_t *)kmalloc(sizeof(hashtable_itr_t), 0);
284
285         if (NULL == itr)
286                 return NULL;
287         itr->h = h;
288         itr->e = NULL;
289         itr->parent = NULL;
290         tablelength = h->tablelength;
291         itr->index = tablelength;
292         if (0 == h->entrycount)
293                 return itr;
294
295         for (i = 0; i < tablelength; i++) {
296                 if (NULL != h->table[i]) {
297                         itr->e = h->table[i];
298                         itr->index = i;
299                         break;
300                 }
301         }
302         return itr;
303 }
304
305 /*****************************************************************************/
306 /* key      - return the key of the (key,value) pair at the current position */
307 /* value    - return the value of the (key,value) pair at the current position
308  */
309
310 void *hashtable_iterator_key(hashtable_itr_t *i)
311 {
312         return i->e->k;
313 }
314
315 void *hashtable_iterator_value(hashtable_itr_t *i)
316 {
317         return i->e->v;
318 }
319
320 /*****************************************************************************/
321 /* advance - advance the iterator to the next element
322  *           returns zero if advanced to end of table */
323
324 ssize_t hashtable_iterator_advance(hashtable_itr_t *itr)
325 {
326         size_t j, tablelength;
327         hash_entry_t **table;
328         hash_entry_t *next;
329
330         if (NULL == itr->e)
331                 return 0; /* stupidity check */
332
333         next = itr->e->next;
334         if (NULL != next) {
335                 itr->parent = itr->e;
336                 itr->e = next;
337                 return -1;
338         }
339         tablelength = itr->h->tablelength;
340         itr->parent = NULL;
341         if (tablelength <= (j = ++(itr->index))) {
342                 itr->e = NULL;
343                 return 0;
344         }
345         table = itr->h->table;
346         while (NULL == (next = table[j])) {
347                 if (++j >= tablelength) {
348                         itr->index = tablelength;
349                         itr->e = NULL;
350                         return 0;
351                 }
352         }
353         itr->index = j;
354         itr->e = next;
355         return -1;
356 }
357
358 /*****************************************************************************/
359 /* remove - remove the entry at the current iterator position
360  *          and advance the iterator, if there is a successive
361  *          element.
362  *          If you want the value, read it before you remove:
363  *          beware memory leaks if you don't.
364  *          Returns zero if end of iteration. */
365
366 ssize_t hashtable_iterator_remove(hashtable_itr_t *itr)
367 {
368         hash_entry_t *remember_e, *remember_parent;
369         ssize_t ret;
370
371         /* Do the removal */
372         if (NULL == (itr->parent)) {
373                 /* element is head of a chain */
374                 itr->h->table[itr->index] = itr->e->next;
375         } else {
376                 /* element is mid-chain */
377                 itr->parent->next = itr->e->next;
378         }
379         /* itr->e is now outside the hashtable */
380         remember_e = itr->e;
381         itr->h->entrycount--;
382
383         /* Advance the iterator, correcting the parent */
384         remember_parent = itr->parent;
385         ret = hashtable_iterator_advance(itr);
386         if (itr->parent == remember_e) {
387                 itr->parent = remember_parent;
388         }
389         kmem_cache_free(hentry_cache, remember_e);
390         return ret;
391 }
392
393 /*****************************************************************************/
394 /* returns zero if not found */
395 ssize_t hashtable_iterator_search(hashtable_itr_t *itr, hashtable_t *h, void *k)
396 {
397         hash_entry_t *e, *parent;
398         size_t hashvalue, index;
399
400         hashvalue = hash(h, k);
401         index = indexFor(h->tablelength, hashvalue);
402
403         e = h->table[index];
404         parent = NULL;
405         while (NULL != e) {
406                 /* Check hash value to short circuit heavier comparison */
407                 if ((hashvalue == e->h) && (h->eqfn(k, e->k))) {
408                         itr->index = index;
409                         itr->e = e;
410                         itr->parent = parent;
411                         itr->h = h;
412                         return -1;
413                 }
414                 parent = e;
415                 e = e->next;
416         }
417         return 0;
418 }
419
420 /* Runs func on each member of the hash table */
421 void hash_for_each(struct hashtable *hash, void func(void *, void *),
422                    void *opaque)
423 {
424         if (hashtable_count(hash)) {
425                 struct hashtable_itr *iter = hashtable_iterator(hash);
426                 do {
427                         void *item = hashtable_iterator_value(iter);
428                         func(item, opaque);
429                 } while (hashtable_iterator_advance(iter));
430                 kfree(iter);
431         }
432 }
433
434 /* Runs func on each member of the hash table, removing the item after
435  * processing it.  Make sure func frees the item, o/w you'll leak. */
436 void hash_for_each_remove(struct hashtable *hash, void func(void *, void *),
437                           void *opaque)
438 {
439         if (hashtable_count(hash)) {
440                 struct hashtable_itr *iter = hashtable_iterator(hash);
441                 do {
442                         void *item = hashtable_iterator_value(iter);
443                         func(item, opaque);
444                 } while (hashtable_iterator_remove(iter));
445                 kfree(iter);
446         }
447 }
448
449 /*
450  * Copyright (c) 2002, 2004, Christopher Clark
451  * All rights reserved.
452  *
453  * Redistribution and use in source and binary forms, with or without
454  * modification, are permitted provided that the following conditions
455  * are met:
456  *
457  * * Redistributions of source code must retain the above copyright
458  * notice, this list of conditions and the following disclaimer.
459  *
460  * * Redistributions in binary form must reproduce the above copyright
461  * notice, this list of conditions and the following disclaimer in the
462  * documentation and/or other materials provided with the distribution.
463  *
464  * * Neither the name of the original author; nor the names of any contributors
465  * may be used to endorse or promote products derived from this software
466  * without specific prior written permission.
467  *
468  *
469  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
470  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
471  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
472  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
473  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
474  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
475  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
476  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
477  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
478  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
479  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
480  */