2 Copyright (c) 2002, 2004, Christopher Clark
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
9 * Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in the
14 documentation and/or other materials provided with the distribution.
16 * Neither the name of the original author; nor the names of any contributors
17 may be used to endorse or promote products derived from this software
18 without specific prior written permission.
21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
25 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 /* Modifications made by Lei Xia */
36 #include <linux/string.h>
37 #include <linux/errno.h>
38 #include <linux/preempt.h>
39 #include <linux/sched.h>
40 #include <linux/slab.h>
43 #include "util-hashtable.h"
50 struct hash_entry * next;
55 struct hash_entry ** table;
59 uint_t (*hash_fn) (addr_t key);
60 int (*eq_fn) (addr_t key1, addr_t key2);
66 static inline uint_t do_hash(struct hashtable * htable, addr_t key) {
67 /* Aim to protect against poor hash functions by adding logic here
68 * - logic taken from java 1.4 hashtable source */
69 uint_t i = htable->hash_fn(key);
71 i ^= ((i >> 14) | (i << 18)); /* >>> */
73 i ^= ((i >> 10) | (i << 22)); /* >>> */
79 /* HASH AN UNSIGNED LONG */
80 /* LINUX UNSIGHED LONG HASH FUNCTION */
82 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
83 #define GOLDEN_RATIO_PRIME 0x9e370001UL
84 //#define BITS_PER_LONG 32
85 #elif defined(__64BIT__)
86 /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
87 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
88 //#define BITS_PER_LONG 64
90 #error Define GOLDEN_RATIO_PRIME for your wordsize.
93 ulong_t palacios_hash_long(ulong_t val, uint_t bits) {
96 #ifdef __PALACIOS_64BIT__
97 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */
112 /* On some cpus multiply is faster, on others gcc will do shifts */
113 hash *= GOLDEN_RATIO_PRIME;
116 /* High bits are more random, so use them. */
117 return hash >> (BITS_PER_LONG - bits);
120 /* HASH GENERIC MEMORY BUFFER */
121 /* ELF HEADER HASH FUNCTION */
122 ulong_t palacios_hash_buffer(uchar_t * msg, uint_t length) {
127 for (i = 0; i < length; i++) {
128 hash = (hash << 4) + *(msg + i) + i;
129 if ((temp = (hash & 0xF0000000))) {
130 hash ^= (temp >> 24);
138 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
139 return (hash_value % table_length);
142 #define freekey(X) palacios_free(X)
145 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
146 void * new_buf = palacios_alloc(new_size);
148 if (new_buf == NULL) {
152 memcpy(new_buf, old_ptr, old_size);
153 palacios_free(old_ptr);
160 Credit for primes table: Aaron Krowne
161 http://br.endernet.org/~akrowne/
162 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
164 static const uint_t primes[] = {
166 769, 1543, 3079, 6151,
167 12289, 24593, 49157, 98317,
168 196613, 393241, 786433, 1572869,
169 3145739, 6291469, 12582917, 25165843,
170 50331653, 100663319, 201326611, 402653189,
171 805306457, 1610612741 };
174 // this assumes that the max load factor is .65
175 static const uint_t load_factors[] = {
177 500, 1003, 2002, 3999,
178 7988, 15986, 31953, 63907,
179 127799, 255607, 511182, 1022365,
180 2044731, 4089455, 8178897, 16357798,
181 32715575, 65431158, 130862298, 261724573,
182 523449198, 1046898282 };
184 const uint_t prime_table_len = sizeof(primes) / sizeof(primes[0]);
186 struct hashtable * palacios_create_htable(uint_t min_size,
187 uint_t (*hash_fn) (addr_t),
188 int (*eq_fn) (addr_t, addr_t)) {
189 struct hashtable * htable;
191 uint_t size = primes[0];
193 /* Check requested hashtable isn't too large */
194 if (min_size > (1u << 30)) {
198 /* Enforce size as prime */
199 for (prime_index = 0; prime_index < prime_table_len; prime_index++) {
200 if (primes[prime_index] > min_size) {
201 size = primes[prime_index];
206 if (prime_index==prime_table_len) {
207 // cannot build large enough hash table
211 htable = (struct hashtable *)palacios_alloc(sizeof(struct hashtable));
213 if (htable == NULL) {
217 htable->table = (struct hash_entry **)palacios_alloc(sizeof(struct hash_entry*) * size);
219 if (htable->table == NULL) {
220 palacios_free(htable);
224 memset(htable->table, 0, size * sizeof(struct hash_entry *));
226 htable->table_length = size;
227 htable->prime_index = prime_index;
228 htable->entry_count = 0;
229 htable->hash_fn = hash_fn;
230 htable->eq_fn = eq_fn;
231 htable->load_limit = load_factors[prime_index];
237 static int hashtable_expand(struct hashtable * htable) {
238 /* Double the size of the table to accomodate more entries */
239 struct hash_entry ** new_table;
240 struct hash_entry * tmp_entry;
241 struct hash_entry ** entry_ptr;
246 /* Check we're not hitting max capacity */
247 if (htable->prime_index == (prime_table_len - 1)) {
251 new_size = primes[++(htable->prime_index)];
253 new_table = (struct hash_entry **)palacios_alloc(sizeof(struct hash_entry*) * new_size);
255 if (new_table != NULL) {
256 memset(new_table, 0, new_size * sizeof(struct hash_entry *));
257 /* This algorithm is not 'stable'. ie. it reverses the list
258 * when it transfers entries between the tables */
260 for (i = 0; i < htable->table_length; i++) {
262 while ((tmp_entry = htable->table[i]) != NULL) {
263 htable->table[i] = tmp_entry->next;
265 index = indexFor(new_size, tmp_entry->hash);
267 tmp_entry->next = new_table[index];
269 new_table[index] = tmp_entry;
273 palacios_free(htable->table);
275 htable->table = new_table;
277 /* Plan B: realloc instead */
279 //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
280 new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
281 new_size * sizeof(struct hash_entry *));
283 if (new_table == NULL) {
284 (htable->prime_index)--;
288 htable->table = new_table;
290 memset(new_table[htable->table_length], 0, new_size - htable->table_length);
292 for (i = 0; i < htable->table_length; i++) {
294 for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
296 tmp_entry = *entry_ptr) {
298 index = indexFor(new_size, tmp_entry->hash);
301 entry_ptr = &(tmp_entry->next);
303 *entry_ptr = tmp_entry->next;
304 tmp_entry->next = new_table[index];
305 new_table[index] = tmp_entry;
311 htable->table_length = new_size;
313 htable->load_limit = load_factors[htable->prime_index];
318 uint_t palacios_htable_count(struct hashtable * htable) {
319 return htable->entry_count;
322 int palacios_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
323 /* This method allows duplicate keys - but they shouldn't be used */
325 struct hash_entry * new_entry;
327 if (++(htable->entry_count) > htable->load_limit) {
328 /* Ignore the return value. If expand fails, we should
329 * still try cramming just this value into the existing table
330 * -- we may not have memory for a larger table, but one more
331 * element may be ok. Next time we insert, we'll try expanding again.*/
332 hashtable_expand(htable);
335 new_entry = (struct hash_entry *)palacios_alloc(sizeof(struct hash_entry));
337 if (new_entry == NULL) {
338 (htable->entry_count)--;
342 new_entry->hash = do_hash(htable, key);
344 index = indexFor(htable->table_length, new_entry->hash);
346 new_entry->key = key;
347 new_entry->value = value;
349 new_entry->next = htable->table[index];
351 htable->table[index] = new_entry;
357 int palacios_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) {
358 struct hash_entry * tmp_entry;
362 hash_value = do_hash(htable, key);
364 index = indexFor(htable->table_length, hash_value);
366 tmp_entry = htable->table[index];
368 while (tmp_entry != NULL) {
369 /* Check hash value to short circuit heavier comparison */
370 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
373 palacios_free((void *)(tmp_entry->value));
376 tmp_entry->value = value;
379 tmp_entry = tmp_entry->next;
386 int palacios_htable_inc(struct hashtable * htable, addr_t key, addr_t value) {
387 struct hash_entry * tmp_entry;
391 hash_value = do_hash(htable, key);
393 index = indexFor(htable->table_length, hash_value);
395 tmp_entry = htable->table[index];
397 while (tmp_entry != NULL) {
398 /* Check hash value to short circuit heavier comparison */
399 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
401 tmp_entry->value += value;
404 tmp_entry = tmp_entry->next;
410 int palacios_htable_dec(struct hashtable * htable, addr_t key, addr_t value) {
411 struct hash_entry * tmp_entry;
415 hash_value = do_hash(htable, key);
417 index = indexFor(htable->table_length, hash_value);
419 tmp_entry = htable->table[index];
421 while (tmp_entry != NULL) {
422 /* Check hash value to short circuit heavier comparison */
423 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
425 tmp_entry->value -= value;
428 tmp_entry = tmp_entry->next;
434 /* returns value associated with key */
435 addr_t palacios_htable_search(struct hashtable * htable, addr_t key) {
436 struct hash_entry * cursor;
440 hash_value = do_hash(htable, key);
442 index = indexFor(htable->table_length, hash_value);
444 cursor = htable->table[index];
446 while (cursor != NULL) {
447 /* Check hash value to short circuit heavier comparison */
448 if ((hash_value == cursor->hash) &&
449 (htable->eq_fn(key, cursor->key))) {
450 return cursor->value;
453 cursor = cursor->next;
460 /* returns value associated with key */
461 addr_t palacios_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
462 /* TODO: consider compacting the table when the load factor drops enough,
463 * or provide a 'compact' method. */
465 struct hash_entry * cursor;
466 struct hash_entry ** entry_ptr;
471 hash_value = do_hash(htable, key);
473 index = indexFor(htable->table_length, hash_value);
475 entry_ptr = &(htable->table[index]);
478 while (cursor != NULL) {
479 /* Check hash value to short circuit heavier comparison */
480 if ((hash_value == cursor->hash) &&
481 (htable->eq_fn(key, cursor->key))) {
483 *entry_ptr = cursor->next;
484 htable->entry_count--;
485 value = cursor->value;
488 freekey((void *)(cursor->key));
490 palacios_free(cursor);
495 entry_ptr = &(cursor->next);
496 cursor = cursor->next;
503 void palacios_free_htable(struct hashtable * htable, int free_values, int free_keys) {
505 struct hash_entry * cursor;
506 struct hash_entry * tmp;
507 struct hash_entry **table = htable->table;
510 for (i = 0; i < htable->table_length; i++) {
513 while (cursor != NULL) {
515 cursor = cursor->next;
518 freekey((void *)(tmp->key));
520 palacios_free((void *)(tmp->value));
525 for (i = 0; i < htable->table_length; i++) {
528 while (cursor != NULL) {
529 struct hash_entry * tmp;
532 cursor = cursor->next;
535 freekey((void *)(tmp->key));
542 palacios_free(htable->table);
543 palacios_free(htable);