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