1 /* Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
2 /* Modifications made by Jack Lange <jarusl@cs.northwestern.edu> */
4 #include <palacios/vmm.h>
5 #include <palacios/vmm_hashtable.h>
6 #include <palacios/vmm_string.h>
16 struct hash_entry * next;
21 struct hash_entry ** table;
25 uint_t (*hash_fn) (void * key);
26 int (*eq_fn) (void * key1, void * key2);
35 uint_t do_hash(struct hashtable * htable, void * key) {
36 /* Aim to protect against poor hash functions by adding logic here
37 * - logic taken from java 1.4 hashtable source */
38 uint_t i = htable->hash_fn(key);
40 i ^= ((i >> 14) | (i << 18)); /* >>> */
42 i ^= ((i >> 10) | (i << 22)); /* >>> */
48 /* HASH AN UNSIGNED LONG */
49 /* LINUX UNSIGHED LONG HASH FUNCTION */
51 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
52 #define GOLDEN_RATIO_PRIME 0x9e370001UL
53 #define BITS_PER_LONG 32
54 #elif defined(__V3_64BIT__)
55 /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
56 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
57 #define BITS_PER_LONG 64
59 #error Define GOLDEN_RATIO_PRIME for your wordsize.
62 ulong_t hash_long(ulong_t val, uint_t bits) {
66 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */
81 /* On some cpus multiply is faster, on others gcc will do shifts */
82 hash *= GOLDEN_RATIO_PRIME;
85 /* High bits are more random, so use them. */
86 return hash >> (BITS_PER_LONG - bits);
89 /* HASH GENERIC MEMORY BUFFER */
90 /* ELF HEADER HASH FUNCTION */
91 ulong_t hash_buffer(uchar_t * msg, uint_t length) {
96 for (i = 0; i < length; i++) {
97 hash = (hash << 4) + *(msg + i) + i;
98 if ((temp = (hash & 0xF0000000))) {
108 /*****************************************************************************/
110 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
111 return (hash_value % table_length);
114 /* Only works if table_length == 2^N */
116 static inline uint_t indexFor(uint_t table_length, uint_t hashvalue)
118 return (hashvalue & (table_length - 1u));
122 /*****************************************************************************/
123 #define freekey(X) V3_Free(X)
124 /*define freekey(X) ; */
127 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
128 void * new_buf = V3_Malloc(new_size);
130 if (new_buf == NULL) {
134 memcpy(new_buf, old_ptr, old_size);
142 Credit for primes table: Aaron Krowne
143 http://br.endernet.org/~akrowne/
144 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
146 static const uint_t primes[] = {
148 769, 1543, 3079, 6151,
149 12289, 24593, 49157, 98317,
150 196613, 393241, 786433, 1572869,
151 3145739, 6291469, 12582917, 25165843,
152 50331653, 100663319, 201326611, 402653189,
153 805306457, 1610612741 };
156 const uint_t prime_table_length = sizeof(primes) / sizeof(primes[0]);
158 const float max_load_factor = 0.65;
160 /*****************************************************************************/
161 struct hashtable * create_hashtable(uint_t min_size,
162 uint_t (*hash_fn) (void *),
163 int (*eq_fn) (void *, void *)) {
164 struct hashtable * htable;
166 uint_t size = primes[0];
168 /* Check requested hashtable isn't too large */
169 if (min_size > (1u << 30)) {
173 /* Enforce size as prime */
174 for (prime_index = 0; prime_index < prime_table_length; prime_index++) {
175 if (primes[prime_index] > min_size) {
176 size = primes[prime_index];
181 htable = (struct hashtable *)V3_Malloc(sizeof(struct hashtable));
183 if (htable == NULL) {
187 htable->table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * size);
189 if (htable->table == NULL) {
195 memset(htable->table, 0, size * sizeof(struct hash_entry *));
197 htable->table_length = size;
198 htable->prime_index = prime_index;
199 htable->entry_count = 0;
200 htable->hash_fn = hash_fn;
201 htable->eq_fn = eq_fn;
202 htable->load_limit = (uint_t) ceil((double)(size * max_load_factor));
209 /*****************************************************************************/
210 static int hashtable_expand(struct hashtable * htable) {
211 /* Double the size of the table to accomodate more entries */
212 struct hash_entry ** new_table;
213 struct hash_entry * tmp_entry;
214 struct hash_entry ** entry_ptr;
219 /* Check we're not hitting max capacity */
220 if (htable->prime_index == (prime_table_length - 1)) {
224 new_size = primes[++(htable->prime_index)];
226 new_table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * new_size);
228 if (new_table != NULL) {
229 memset(new_table, 0, new_size * sizeof(struct hash_entry *));
230 /* This algorithm is not 'stable'. ie. it reverses the list
231 * when it transfers entries between the tables */
233 for (i = 0; i < htable->table_length; i++) {
235 while ((tmp_entry = htable->table[i]) != NULL) {
236 htable->table[i] = tmp_entry->next;
238 index = indexFor(new_size, tmp_entry->hash);
240 tmp_entry->next = new_table[index];
242 new_table[index] = tmp_entry;
246 V3_Free(htable->table);
248 htable->table = new_table;
250 /* Plan B: realloc instead */
252 //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
253 new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
254 new_size * sizeof(struct hash_entry *));
256 if (new_table == NULL) {
257 (htable->prime_index)--;
261 htable->table = new_table;
263 memset(new_table[htable->table_length], 0, new_size - htable->table_length);
265 for (i = 0; i < htable->table_length; i++) {
267 for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
269 tmp_entry = *entry_ptr) {
271 index = indexFor(new_size, tmp_entry->hash);
274 entry_ptr = &(tmp_entry->next);
276 *entry_ptr = tmp_entry->next;
277 tmp_entry->next = new_table[index];
278 new_table[index] = tmp_entry;
284 htable->table_length = new_size;
286 htable->load_limit = (uint_t) ceil(new_size * max_load_factor);
291 /*****************************************************************************/
292 uint_t hashtable_count(struct hashtable * htable) {
293 return htable->entry_count;
296 /*****************************************************************************/
297 int hashtable_insert(struct hashtable * htable, void * key, void * value) {
298 /* This method allows duplicate keys - but they shouldn't be used */
300 struct hash_entry * new_entry;
302 if (++(htable->entry_count) > htable->load_limit) {
303 /* Ignore the return value. If expand fails, we should
304 * still try cramming just this value into the existing table
305 * -- we may not have memory for a larger table, but one more
306 * element may be ok. Next time we insert, we'll try expanding again.*/
307 hashtable_expand(htable);
311 new_entry = (struct hash_entry *)V3_Malloc(sizeof(struct hash_entry));
313 if (new_entry == NULL) {
314 (htable->entry_count)--;
318 new_entry->hash = do_hash(htable, key);
320 index = indexFor(htable->table_length, new_entry->hash);
322 new_entry->key = key;
323 new_entry->value = value;
325 new_entry->next = htable->table[index];
327 htable->table[index] = new_entry;
334 int hashtable_change(struct hashtable * htable, void * key, void * value) {
335 struct hash_entry * tmp_entry;
339 hash_value = do_hash(htable, key);
341 index = indexFor(htable->table_length, hash_value);
343 tmp_entry = htable->table[index];
345 while (tmp_entry != NULL) {
346 /* Check hash value to short circuit heavier comparison */
347 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
348 V3_Free(tmp_entry->value);
349 tmp_entry->value = value;
353 tmp_entry = tmp_entry->next;
361 /*****************************************************************************/
362 /* returns value associated with key */
363 void * hashtable_search(struct hashtable * htable, void * key) {
364 struct hash_entry * cursor;
368 hash_value = do_hash(htable, key);
370 index = indexFor(htable->table_length, hash_value);
372 cursor = htable->table[index];
374 while (cursor != NULL) {
375 /* Check hash value to short circuit heavier comparison */
376 if ((hash_value == cursor->hash) &&
377 (htable->eq_fn(key, cursor->key))) {
378 return cursor->value;
381 cursor = cursor->next;
387 /*****************************************************************************/
388 /* returns value associated with key */
389 void * hashtable_remove(struct hashtable * htable, void * key) {
390 /* TODO: consider compacting the table when the load factor drops enough,
391 * or provide a 'compact' method. */
393 struct hash_entry * cursor;
394 struct hash_entry ** entry_ptr;
399 hash_value = do_hash(htable, key);
401 index = indexFor(htable->table_length, hash_value);
403 entry_ptr = &(htable->table[index]);
406 while (cursor != NULL) {
407 /* Check hash value to short circuit heavier comparison */
408 if ((hash_value == cursor->hash) &&
409 (htable->eq_fn(key, cursor->key))) {
411 *entry_ptr = cursor->next;
412 htable->entry_count--;
413 value = cursor->value;
415 freekey(cursor->key);
421 entry_ptr = &(cursor->next);
422 cursor = cursor->next;
427 /*****************************************************************************/
429 void hashtable_destroy(struct hashtable * htable, int free_values) {
431 struct hash_entry * cursor;;
432 struct hash_entry **table = htable->table;
435 for (i = 0; i < htable->table_length; i++) {
438 while (cursor != NULL) {
439 struct hash_entry * tmp;
442 cursor = cursor->next;
450 for (i = 0; i < htable->table_length; i++) {
453 while (cursor != NULL) {
454 struct hash_entry * tmp;
457 cursor = cursor->next;
465 V3_Free(htable->table);
472 /* HASH TABLE ITERATORS */
476 struct hashtable_iter * create_hashtable_iterator(struct hashtable * htable) {
480 struct hashtable_iter * iter = (struct hashtable_iter *)V3_Malloc(sizeof(struct hashtable_iter));
486 iter->htable = htable;
489 table_length = htable->table_length;
490 iter->index = table_length;
492 if (htable->entry_count == 0) {
496 for (i = 0; i < table_length; i++) {
497 if (htable->table[i] != NULL) {
498 iter->entry = htable->table[i];
508 void * hashtable_get_iter_key(struct hashtable_iter * iter) {
509 return iter->entry->key;
512 void * hashtable_get_iter_value(struct hashtable_iter * iter) {
513 return iter->entry->value;
517 /* advance - advance the iterator to the next element
518 * returns zero if advanced to end of table */
519 int hashtable_iterator_advance(struct hashtable_iter * iter) {
522 struct hash_entry ** table;
523 struct hash_entry * next;
525 if (iter->entry == NULL) {
526 return 0; /* stupidity check */
530 next = iter->entry->next;
533 iter->parent = iter->entry;
538 table_length = iter->htable->table_length;
541 if (table_length <= (j = ++(iter->index))) {
546 table = iter->htable->table;
548 while ((next = table[j]) == NULL) {
549 if (++j >= table_length) {
550 iter->index = table_length;
563 /* remove - remove the entry at the current iterator position
564 * and advance the iterator, if there is a successive
566 * If you want the value, read it before you remove:
567 * beware memory leaks if you don't.
568 * Returns zero if end of iteration. */
569 int hashtable_iterator_remove(struct hashtable_iter * iter) {
570 struct hash_entry * remember_entry;
571 struct hash_entry * remember_parent;
575 if ((iter->parent) == NULL) {
576 /* element is head of a chain */
577 iter->htable->table[iter->index] = iter->entry->next;
579 /* element is mid-chain */
580 iter->parent->next = iter->entry->next;
584 /* itr->e is now outside the hashtable */
585 remember_entry = iter->entry;
586 iter->htable->entry_count--;
587 freekey(remember_entry->key);
589 /* Advance the iterator, correcting the parent */
590 remember_parent = iter->parent;
591 ret = hashtable_iterator_advance(iter);
593 if (iter->parent == remember_entry) {
594 iter->parent = remember_parent;
597 V3_Free(remember_entry);
602 /* returns zero if not found */
603 int hashtable_iterator_search(struct hashtable_iter * iter,
604 struct hashtable * htable, void * key) {
605 struct hash_entry * entry;
606 struct hash_entry * parent;
610 hash_value = do_hash(htable, key);
611 index = indexFor(htable->table_length, hash_value);
613 entry = htable->table[index];
616 while (entry != NULL) {
617 /* Check hash value to short circuit heavier comparison */
618 if ((hash_value == entry->hash) &&
619 (htable->eq_fn(key, entry->key))) {
622 iter->parent = parent;
623 iter->htable = htable;
647 * Copyright (c) 2002, Christopher Clark
648 * All rights reserved.
650 * Redistribution and use in source and binary forms, with or without
651 * modification, are permitted provided that the following conditions
654 * * Redistributions of source code must retain the above copyright
655 * notice, this list of conditions and the following disclaimer.
657 * * Redistributions in binary form must reproduce the above copyright
658 * notice, this list of conditions and the following disclaimer in the
659 * documentation and/or other materials provided with the distribution.
661 * * Neither the name of the original author; nor the names of any contributors
662 * may be used to endorse or promote products derived from this software
663 * without specific prior written permission.
666 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
667 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
668 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
669 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
670 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
671 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
672 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
673 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
674 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
675 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
676 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.