Fixed up a few small bugs in the syscall_server stuff
[akaros.git] / kern / src / hashtable.c
1 /* Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
2
3 #include <ros/common.h>
4 #include <hashtable.h>
5 #include <stdio.h>
6 #include <string.h>
7 #include <kmalloc.h>
8
9 /*
10 Credit for primes table: Aaron Krowne
11  http://br.endernet.org/~akrowne/
12  http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
13 */
14 static const unsigned int primes[] = {
15 53, 97, 193, 389,
16 769, 1543, 3079, 6151,
17 12289, 24593, 49157, 98317,
18 196613, 393241, 786433, 1572869,
19 3145739, 6291469, 12582917, 25165843,
20 50331653, 100663319, 201326611, 402653189,
21 805306457, 1610612741
22 };
23 const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
24 #define APPLY_MAX_LOAD_FACTOR(size) \
25     ((size * 13)/20)
26 //const float max_load_factor = 0.65;
27
28 /*****************************************************************************/
29 hashtable_t *
30 create_hashtable(size_t minsize,
31                  size_t (*hashf) (void*),
32                  ssize_t (*eqf) (void*,void*))
33 {
34     hashtable_t *h;
35     size_t pindex, size = primes[0];
36     /* Check requested hashtable isn't too large */
37     if (minsize > (1u << 30)) return NULL;
38     /* Enforce size as prime */
39     for (pindex=0; pindex < prime_table_length; pindex++) {
40         if (primes[pindex] > minsize) { size = primes[pindex]; break; }
41     }
42     h = (hashtable_t *)kmalloc(sizeof(hashtable_t), 0);
43     if (NULL == h) return NULL; /*oom*/
44     h->table = (hash_entry_t **)kmalloc(sizeof(hash_entry_t*) * size, 0);
45     if (NULL == h->table) { kfree(h); return NULL; } /*oom*/
46     memset(h->table, 0, size * sizeof(hash_entry_t *));
47     h->tablelength  = size;
48     h->primeindex   = pindex;
49     h->entrycount   = 0;
50     h->hashfn       = hashf;
51     h->eqfn         = eqf;
52     h->loadlimit    = APPLY_MAX_LOAD_FACTOR(size);
53     return h;
54 }
55
56 /*****************************************************************************/
57 size_t
58 hash(hashtable_t *h, void *k)
59 {
60     /* Aim to protect against poor hash functions by adding logic here
61      * - logic taken from java 1.4 hashtable source */
62     size_t i = h->hashfn(k);
63     i += ~(i << 9);
64     i ^=  ((i >> 14) | (i << 18)); /* >>> */
65     i +=  (i << 4);
66     i ^=  ((i >> 10) | (i << 22)); /* >>> */
67     return i;
68 }
69
70 /*****************************************************************************/
71 static ssize_t
72 hashtable_expand(hashtable_t *h)
73 {
74     /* Double the size of the table to accomodate more entries */
75     hash_entry_t **newtable;
76     hash_entry_t *e;
77     hash_entry_t **pE;
78     size_t newsize, i, index;
79     /* Check we're not hitting max capacity */
80     if (h->primeindex == (prime_table_length - 1)) return 0;
81     newsize = primes[++(h->primeindex)];
82
83     newtable = (hash_entry_t **)kmalloc(sizeof(hash_entry_t*) * newsize, 0);
84     if (NULL != newtable)
85     {
86         memset(newtable, 0, newsize * sizeof(hash_entry_t*));
87         /* This algorithm is not 'stable'. ie. it reverses the list
88          * when it transfers entries between the tables */
89         for (i = 0; i < h->tablelength; i++) {
90             while (NULL != (e = h->table[i])) {
91                 h->table[i] = e->next;
92                 index = indexFor(newsize,e->h);
93                 e->next = newtable[index];
94                 newtable[index] = e;
95             }
96         }
97         kfree(h->table);
98         h->table = newtable;
99     }
100     /* Plan B: realloc instead */
101     else 
102     {
103         newtable = (hash_entry_t**)
104                    krealloc(h->table, newsize*sizeof(hash_entry_t*), 0);
105         if (NULL == newtable) { (h->primeindex)--; return 0; }
106         h->table = newtable;
107         memset(newtable[h->tablelength], 0, newsize - h->tablelength);
108         for (i = 0; i < h->tablelength; i++) {
109             for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
110                 index = indexFor(newsize,e->h);
111                 if (index == i)
112                 {
113                     pE = &(e->next);
114                 }
115                 else
116                 {
117                     *pE = e->next;
118                     e->next = newtable[index];
119                     newtable[index] = e;
120                 }
121             }
122         }
123     }
124     h->tablelength = newsize;
125     h->loadlimit   = APPLY_MAX_LOAD_FACTOR(newsize);
126     return -1;
127 }
128
129 /*****************************************************************************/
130 size_t
131 hashtable_count(hashtable_t *h)
132 {
133     return h->entrycount;
134 }
135
136 /*****************************************************************************/
137 ssize_t
138 hashtable_insert(hashtable_t *h, void *k, void *v)
139 {
140     /* This method allows duplicate keys - but they shouldn't be used */
141     size_t index;
142     hash_entry_t *e;
143     if (++(h->entrycount) > h->loadlimit)
144     {
145         /* Ignore the return value. If expand fails, we should
146          * still try cramming just this value into the existing table
147          * -- we may not have memory for a larger table, but one more
148          * element may be ok. Next time we insert, we'll try expanding again.*/
149         hashtable_expand(h);
150     }
151     e = (hash_entry_t *)kmalloc(sizeof(hash_entry_t), 0);
152     if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
153     e->h = hash(h,k);
154     index = indexFor(h->tablelength,e->h);
155     e->k = k;
156     e->v = v;
157     e->next = h->table[index];
158     h->table[index] = e;
159     return -1;
160 }
161
162 /*****************************************************************************/
163 void * /* returns value associated with key */
164 hashtable_search(hashtable_t *h, void *k)
165 {
166     hash_entry_t *e;
167     size_t hashvalue, index;
168     hashvalue = hash(h,k);
169     index = indexFor(h->tablelength,hashvalue);
170     e = h->table[index];
171     while (NULL != e)
172     {
173         /* Check hash value to short circuit heavier comparison */
174         if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
175         e = e->next;
176     }
177     return NULL;
178 }
179
180 /*****************************************************************************/
181 void * /* returns value associated with key */
182 hashtable_remove(hashtable_t *h, void *k)
183 {
184     /* TODO: consider compacting the table when the load factor drops enough,
185      *       or provide a 'compact' method. */
186
187     hash_entry_t *e;
188     hash_entry_t **pE;
189     void *v;
190     size_t hashvalue, index;
191
192     hashvalue = hash(h,k);
193     index = indexFor(h->tablelength,hash(h,k));
194     pE = &(h->table[index]);
195     e = *pE;
196     while (NULL != e)
197     {
198         /* Check hash value to short circuit heavier comparison */
199         if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
200         {
201             *pE = e->next;
202             h->entrycount--;
203             v = e->v;
204             freekey(e->k);
205             kfree(e);
206             return v;
207         }
208         pE = &(e->next);
209         e = e->next;
210     }
211     return NULL;
212 }
213
214 /*****************************************************************************/
215 /* destroy */
216 void
217 hashtable_destroy(hashtable_t *h, int free_values)
218 {
219     size_t i;
220     hash_entry_t *e, *f;
221     hash_entry_t **table = h->table;
222     if (free_values)
223     {
224         for (i = 0; i < h->tablelength; i++)
225         {
226             e = table[i];
227             while (NULL != e)
228             { f = e; e = e->next; freekey(f->k); kfree(f->v); kfree(f); }
229         }
230     }
231     else
232     {
233         for (i = 0; i < h->tablelength; i++)
234         {
235             e = table[i];
236             while (NULL != e)
237             { f = e; e = e->next; freekey(f->k); kfree(f); }
238         }
239     }
240     kfree(h->table);
241     kfree(h);
242 }
243
244 /*
245  * Copyright (c) 2002, Christopher Clark
246  * All rights reserved.
247  * 
248  * Redistribution and use in source and binary forms, with or without
249  * modification, are permitted provided that the following conditions
250  * are met:
251  * 
252  * * Redistributions of source code must retain the above copyright
253  * notice, this list of conditions and the following disclaimer.
254  * 
255  * * Redistributions in binary form must reproduce the above copyright
256  * notice, this list of conditions and the following disclaimer in the
257  * documentation and/or other materials provided with the distribution.
258  * 
259  * * Neither the name of the original author; nor the names of any contributors
260  * may be used to endorse or promote products derived from this software
261  * without specific prior written permission.
262  * 
263  * 
264  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
265  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
266  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
267  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
268  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
269  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
270  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
271  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
272  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
273  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
274  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
275 */