net: tcp: Fix up the receive window
[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
18 /*
19 Credit for primes table: Aaron Krowne
20  http://br.endernet.org/~akrowne/
21  http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
22 */
23 static const unsigned int primes[] = {
24 53, 97, 193, 389,
25 769, 1543, 3079, 6151,
26 12289, 24593, 49157, 98317,
27 196613, 393241, 786433, 1572869,
28 3145739, 6291469, 12582917, 25165843,
29 50331653, 100663319, 201326611, 402653189,
30 805306457, 1610612741
31 };
32 const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
33 #define APPLY_MAX_LOAD_FACTOR(size) \
34     ((size * 13)/20)
35 //const float max_load_factor = 0.65;
36
37 struct kmem_cache *hentry_cache;
38
39 /* Call this once on bootup, after initializing the slab allocator.  */
40 void hashtable_init(void)
41 {
42         hentry_cache = kmem_cache_create("hash_entry",
43                                          sizeof(struct hash_entry),
44                                          __alignof__(struct hash_entry), 0,
45                                          NULL, 0, 0, NULL);
46 }
47
48 /* Common hash/equals functions.  Don't call these directly. */
49 size_t __generic_hash(void *k)
50 {
51         /* 0x9e370001UL used by Linux (32 bit)
52          * (prime approx to the golden ratio to the max integer, IAW Knuth)
53          */
54         return (size_t)k * 0x9e370001UL;
55 }
56
57 ssize_t __generic_eq(void *k1, void *k2)
58 {
59         return k1 == k2;
60 }
61
62 /*****************************************************************************/
63 hashtable_t *
64 create_hashtable(size_t minsize,
65                  size_t (*hashf) (void*),
66                  ssize_t (*eqf) (void*,void*))
67 {
68     hashtable_t *h;
69     size_t pindex, size = primes[0];
70     /* Check requested hashtable isn't too large */
71     if (minsize > (1u << 30)) return NULL;
72     /* Enforce size as prime */
73     for (pindex=0; pindex < prime_table_length; pindex++) {
74         if (primes[pindex] > minsize) { size = primes[pindex]; break; }
75     }
76     h = (hashtable_t *)kmalloc(sizeof(hashtable_t), 0);
77     if (NULL == h) return NULL; /*oom*/
78     h->table = (hash_entry_t **)kmalloc(sizeof(hash_entry_t*) * size, 0);
79     if (NULL == h->table) { kfree(h); return NULL; } /*oom*/
80     memset(h->table, 0, size * sizeof(hash_entry_t *));
81     h->tablelength  = size;
82     h->primeindex   = pindex;
83     h->entrycount   = 0;
84     h->hashfn       = hashf;
85     h->eqfn         = eqf;
86     h->loadlimit    = APPLY_MAX_LOAD_FACTOR(size);
87     return h;
88 }
89
90 /*****************************************************************************/
91 static size_t
92 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     i += ~(i << 9);
98     i ^=  ((i >> 14) | (i << 18)); /* >>> */
99     i +=  (i << 4);
100     i ^=  ((i >> 10) | (i << 22)); /* >>> */
101     return i;
102 }
103
104 /*****************************************************************************/
105 static ssize_t
106 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     /* Check we're not hitting max capacity */
114     if (h->primeindex == (prime_table_length - 1)) return 0;
115     newsize = primes[++(h->primeindex)];
116
117     newtable = (hash_entry_t **)kmalloc(sizeof(hash_entry_t*) * newsize, 0);
118     if (NULL != newtable)
119     {
120         memset(newtable, 0, newsize * sizeof(hash_entry_t*));
121         /* This algorithm is not 'stable'. ie. it reverses the list
122          * when it transfers entries between the tables */
123         for (i = 0; i < h->tablelength; i++) {
124             while (NULL != (e = h->table[i])) {
125                 h->table[i] = e->next;
126                 index = indexFor(newsize,e->h);
127                 e->next = newtable[index];
128                 newtable[index] = e;
129             }
130         }
131         kfree(h->table);
132         h->table = newtable;
133     }
134     /* Plan B: realloc instead */
135     else
136     {
137         newtable = (hash_entry_t**)
138                    krealloc(h->table, newsize*sizeof(hash_entry_t*), 0);
139         if (NULL == newtable) { (h->primeindex)--; return 0; }
140         h->table = newtable;
141         memset(newtable[h->tablelength], 0, newsize - h->tablelength);
142         for (i = 0; i < h->tablelength; i++) {
143             for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
144                 index = indexFor(newsize,e->h);
145                 if (index == i)
146                 {
147                     pE = &(e->next);
148                 }
149                 else
150                 {
151                     *pE = e->next;
152                     e->next = newtable[index];
153                     newtable[index] = e;
154                 }
155             }
156         }
157     }
158     h->tablelength = newsize;
159     h->loadlimit   = APPLY_MAX_LOAD_FACTOR(newsize);
160     return -1;
161 }
162
163 /*****************************************************************************/
164 size_t
165 hashtable_count(hashtable_t *h)
166 {
167     return h->entrycount;
168 }
169
170 /*****************************************************************************/
171 ssize_t
172 hashtable_insert(hashtable_t *h, void *k, void *v)
173 {
174     /* This method allows duplicate keys - but they shouldn't be used */
175     size_t index;
176     hash_entry_t *e;
177     if (++(h->entrycount) > h->loadlimit)
178     {
179         /* Ignore the return value. If expand fails, we should
180          * still try cramming just this value into the existing table
181          * -- we may not have memory for a larger table, but one more
182          * element may be ok. Next time we insert, we'll try expanding again.*/
183         hashtable_expand(h);
184     }
185     e = (hash_entry_t *)kmem_cache_alloc(hentry_cache, 0);
186     if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
187     e->h = hash(h,k);
188     index = indexFor(h->tablelength,e->h);
189     e->k = k;
190     e->v = v;
191     e->next = h->table[index];
192     h->table[index] = e;
193     return -1;
194 }
195
196 /*****************************************************************************/
197 void * /* returns value associated with key */
198 hashtable_search(hashtable_t *h, void *k)
199 {
200     hash_entry_t *e;
201     size_t hashvalue, index;
202     hashvalue = hash(h,k);
203     index = indexFor(h->tablelength,hashvalue);
204     e = h->table[index];
205     while (NULL != e)
206     {
207         /* Check hash value to short circuit heavier comparison */
208         if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
209         e = e->next;
210     }
211     return NULL;
212 }
213
214 /*****************************************************************************/
215 void * /* returns value associated with key */
216 hashtable_remove(hashtable_t *h, void *k)
217 {
218     /* TODO: consider compacting the table when the load factor drops enough,
219      *       or provide a 'compact' method. */
220
221     hash_entry_t *e;
222     hash_entry_t **pE;
223     void *v;
224     size_t hashvalue, index;
225
226     hashvalue = hash(h,k);
227     index = indexFor(h->tablelength,hash(h,k));
228     pE = &(h->table[index]);
229     e = *pE;
230     while (NULL != e)
231     {
232         /* Check hash value to short circuit heavier comparison */
233         if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
234         {
235             *pE = e->next;
236             h->entrycount--;
237             v = e->v;
238                         kmem_cache_free(hentry_cache, e);
239             return v;
240         }
241         pE = &(e->next);
242         e = e->next;
243     }
244     return NULL;
245 }
246
247 /*****************************************************************************/
248 /* destroy */
249 void
250 hashtable_destroy(hashtable_t *h)
251 {
252         if (hashtable_count(h))
253                 warn("Destroying a non-empty hashtable, clean up after yourself!\n");
254
255     size_t i;
256     hash_entry_t *e, *f;
257     hash_entry_t **table = h->table;
258         for (i = 0; i < h->tablelength; i++) {
259                 e = table[i];
260                 while (NULL != e) {
261                         f = e;
262                         e = e->next;
263                         kmem_cache_free(hentry_cache, f);
264                 }
265         }
266     kfree(h->table);
267     kfree(h);
268 }
269
270 /*****************************************************************************/
271 /* hashtable_iterator    - iterator constructor, be sure to kfree this when
272  * you're done.
273  *
274  * If the htable isn't empty, e and index will refer to the first entry. */
275
276 hashtable_itr_t *
277 hashtable_iterator(hashtable_t *h)
278 {
279     size_t i, tablelength;
280     hashtable_itr_t *itr = (hashtable_itr_t *)
281         kmalloc(sizeof(hashtable_itr_t), 0);
282     if (NULL == itr) return NULL;
283     itr->h = h;
284     itr->e = NULL;
285     itr->parent = NULL;
286     tablelength = h->tablelength;
287     itr->index = tablelength;
288     if (0 == h->entrycount) return itr;
289
290     for (i = 0; i < tablelength; i++)
291     {
292         if (NULL != h->table[i])
293         {
294             itr->e = h->table[i];
295             itr->index = i;
296             break;
297         }
298     }
299     return itr;
300 }
301
302 /*****************************************************************************/
303 /* key      - return the key of the (key,value) pair at the current position */
304 /* value    - return the value of the (key,value) pair at the current position */
305
306 void *
307 hashtable_iterator_key(hashtable_itr_t *i)
308 { return i->e->k; }
309
310 void *
311 hashtable_iterator_value(hashtable_itr_t *i)
312 { return i->e->v; }
313
314 /*****************************************************************************/
315 /* advance - advance the iterator to the next element
316  *           returns zero if advanced to end of table */
317
318 ssize_t
319 hashtable_iterator_advance(hashtable_itr_t *itr)
320 {
321     size_t j,tablelength;
322     hash_entry_t **table;
323     hash_entry_t *next;
324     if (NULL == itr->e) return 0; /* stupidity check */
325
326     next = itr->e->next;
327     if (NULL != next)
328     {
329         itr->parent = itr->e;
330         itr->e = next;
331         return -1;
332     }
333     tablelength = itr->h->tablelength;
334     itr->parent = NULL;
335     if (tablelength <= (j = ++(itr->index)))
336     {
337         itr->e = NULL;
338         return 0;
339     }
340     table = itr->h->table;
341     while (NULL == (next = table[j]))
342     {
343         if (++j >= tablelength)
344         {
345             itr->index = tablelength;
346             itr->e = NULL;
347             return 0;
348         }
349     }
350     itr->index = j;
351     itr->e = next;
352     return -1;
353 }
354
355 /*****************************************************************************/
356 /* remove - remove the entry at the current iterator position
357  *          and advance the iterator, if there is a successive
358  *          element.
359  *          If you want the value, read it before you remove:
360  *          beware memory leaks if you don't.
361  *          Returns zero if end of iteration. */
362
363 ssize_t
364 hashtable_iterator_remove(hashtable_itr_t *itr)
365 {
366     hash_entry_t *remember_e, *remember_parent;
367     ssize_t ret;
368
369     /* Do the removal */
370     if (NULL == (itr->parent))
371     {
372         /* element is head of a chain */
373         itr->h->table[itr->index] = itr->e->next;
374     } else {
375         /* element is mid-chain */
376         itr->parent->next = itr->e->next;
377     }
378     /* itr->e is now outside the hashtable */
379     remember_e = itr->e;
380     itr->h->entrycount--;
381
382     /* Advance the iterator, correcting the parent */
383     remember_parent = itr->parent;
384     ret = hashtable_iterator_advance(itr);
385     if (itr->parent == remember_e) { itr->parent = remember_parent; }
386         kmem_cache_free(hentry_cache, remember_e);
387     return ret;
388 }
389
390 /*****************************************************************************/
391 ssize_t /* returns zero if not found */
392 hashtable_iterator_search(hashtable_itr_t *itr,
393                           hashtable_t *h, void *k)
394 {
395     hash_entry_t *e, *parent;
396     size_t hashvalue, index;
397
398     hashvalue = hash(h,k);
399     index = indexFor(h->tablelength,hashvalue);
400
401     e = h->table[index];
402     parent = NULL;
403     while (NULL != e)
404     {
405         /* Check hash value to short circuit heavier comparison */
406         if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
407         {
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 */