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