1 /* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
3 * Modified 2009 by Barret Rhoden <brho@cs.berkeley.edu>
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. */
10 #include <ros/common.h>
11 #include <hashtable.h>
18 #include <arch/types.h>
21 Credit for primes table: Aaron Krowne
22 http://br.endernet.org/~akrowne/
23 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
25 static const unsigned int primes[] = {
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,
34 const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
35 #define APPLY_MAX_LOAD_FACTOR(size) \
37 //const float max_load_factor = 0.65;
39 struct kmem_cache *hentry_cache;
41 /* Call this once on bootup, after initializing the slab allocator. */
42 void hashtable_init(void)
44 hentry_cache = kmem_cache_create("hash_entry",
45 sizeof(struct hash_entry),
46 __alignof__(struct hash_entry), 0,
50 /* Common hash/equals functions. Don't call these directly. */
51 size_t __generic_hash(void *k)
53 return hash_long((unsigned long)k, BITS_PER_LONG);
56 ssize_t __generic_eq(void *k1, void *k2)
61 /*****************************************************************************/
63 create_hashtable(size_t minsize,
64 size_t (*hashf) (void*),
65 ssize_t (*eqf) (void*,void*))
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; }
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;
85 h->loadlimit = APPLY_MAX_LOAD_FACTOR(size);
89 /*****************************************************************************/
91 hash(hashtable_t *h, void *k)
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);
97 i ^= ((i >> 14) | (i << 18)); /* >>> */
99 i ^= ((i >> 10) | (i << 22)); /* >>> */
103 /*****************************************************************************/
105 hashtable_expand(hashtable_t *h)
107 /* Double the size of the table to accomodate more entries */
108 hash_entry_t **newtable;
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)];
116 newtable = (hash_entry_t **)kmalloc(sizeof(hash_entry_t*) * newsize, 0);
117 if (NULL != newtable)
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];
133 /* Plan B: realloc instead */
136 newtable = (hash_entry_t**)
137 krealloc(h->table, newsize*sizeof(hash_entry_t*), 0);
138 if (NULL == newtable) { (h->primeindex)--; return 0; }
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);
151 e->next = newtable[index];
157 h->tablelength = newsize;
158 h->loadlimit = APPLY_MAX_LOAD_FACTOR(newsize);
162 /*****************************************************************************/
164 hashtable_count(hashtable_t *h)
166 return h->entrycount;
169 /*****************************************************************************/
171 hashtable_insert(hashtable_t *h, void *k, void *v)
173 /* This method allows duplicate keys - but they shouldn't be used */
176 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 again.*/
184 e = (hash_entry_t *)kmem_cache_alloc(hentry_cache, 0);
185 if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
187 index = indexFor(h->tablelength,e->h);
190 e->next = h->table[index];
195 /*****************************************************************************/
196 void * /* returns value associated with key */
197 hashtable_search(hashtable_t *h, void *k)
200 size_t hashvalue, index;
201 hashvalue = hash(h,k);
202 index = indexFor(h->tablelength,hashvalue);
206 /* Check hash value to short circuit heavier comparison */
207 if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
213 /*****************************************************************************/
214 void * /* returns value associated with key */
215 hashtable_remove(hashtable_t *h, void *k)
217 /* TODO: consider compacting the table when the load factor drops enough,
218 * or provide a 'compact' method. */
223 size_t hashvalue, index;
225 hashvalue = hash(h,k);
226 index = indexFor(h->tablelength,hash(h,k));
227 pE = &(h->table[index]);
231 /* Check hash value to short circuit heavier comparison */
232 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
237 kmem_cache_free(hentry_cache, e);
246 /*****************************************************************************/
249 hashtable_destroy(hashtable_t *h)
251 if (hashtable_count(h))
252 warn("Destroying a non-empty hashtable, clean up after yourself!\n");
256 hash_entry_t **table = h->table;
257 for (i = 0; i < h->tablelength; i++) {
262 kmem_cache_free(hentry_cache, f);
269 /*****************************************************************************/
270 /* hashtable_iterator - iterator constructor, be sure to kfree this when
273 * If the htable isn't empty, e and index will refer to the first entry. */
276 hashtable_iterator(hashtable_t *h)
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;
285 tablelength = h->tablelength;
286 itr->index = tablelength;
287 if (0 == h->entrycount) return itr;
289 for (i = 0; i < tablelength; i++)
291 if (NULL != h->table[i])
293 itr->e = h->table[i];
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 */
306 hashtable_iterator_key(hashtable_itr_t *i)
310 hashtable_iterator_value(hashtable_itr_t *i)
313 /*****************************************************************************/
314 /* advance - advance the iterator to the next element
315 * returns zero if advanced to end of table */
318 hashtable_iterator_advance(hashtable_itr_t *itr)
320 size_t j,tablelength;
321 hash_entry_t **table;
323 if (NULL == itr->e) return 0; /* stupidity check */
328 itr->parent = itr->e;
332 tablelength = itr->h->tablelength;
334 if (tablelength <= (j = ++(itr->index)))
339 table = itr->h->table;
340 while (NULL == (next = table[j]))
342 if (++j >= tablelength)
344 itr->index = tablelength;
354 /*****************************************************************************/
355 /* remove - remove the entry at the current iterator position
356 * and advance the iterator, if there is a successive
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. */
363 hashtable_iterator_remove(hashtable_itr_t *itr)
365 hash_entry_t *remember_e, *remember_parent;
369 if (NULL == (itr->parent))
371 /* element is head of a chain */
372 itr->h->table[itr->index] = itr->e->next;
374 /* element is mid-chain */
375 itr->parent->next = itr->e->next;
377 /* itr->e is now outside the hashtable */
379 itr->h->entrycount--;
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);
389 /*****************************************************************************/
390 ssize_t /* returns zero if not found */
391 hashtable_iterator_search(hashtable_itr_t *itr,
392 hashtable_t *h, void *k)
394 hash_entry_t *e, *parent;
395 size_t hashvalue, index;
397 hashvalue = hash(h,k);
398 index = indexFor(h->tablelength,hashvalue);
404 /* Check hash value to short circuit heavier comparison */
405 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
409 itr->parent = parent;
419 /* Runs func on each member of the hash table */
420 void hash_for_each(struct hashtable *hash, void func(void *, void *),
423 if (hashtable_count(hash)) {
424 struct hashtable_itr *iter = hashtable_iterator(hash);
426 void *item = hashtable_iterator_value(iter);
428 } while (hashtable_iterator_advance(iter));
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 *),
438 if (hashtable_count(hash)) {
439 struct hashtable_itr *iter = hashtable_iterator(hash);
441 void *item = hashtable_iterator_value(iter);
443 } while (hashtable_iterator_remove(iter));
449 * Copyright (c) 2002, 2004, Christopher Clark
450 * All rights reserved.
452 * Redistribution and use in source and binary forms, with or without
453 * modification, are permitted provided that the following conditions
456 * * Redistributions of source code must retain the above copyright
457 * notice, this list of conditions and the following disclaimer.
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.
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.
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.