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 htable = (struct hashtable *)palacios_alloc(sizeof(struct hashtable));
208 if (htable == NULL) {
212 htable->table = (struct hash_entry **)palacios_alloc(sizeof(struct hash_entry*) * size);
214 if (htable->table == NULL) {
215 palacios_free(htable);
219 memset(htable->table, 0, size * sizeof(struct hash_entry *));
221 htable->table_length = size;
222 htable->prime_index = prime_index;
223 htable->entry_count = 0;
224 htable->hash_fn = hash_fn;
225 htable->eq_fn = eq_fn;
226 htable->load_limit = load_factors[prime_index];
232 static int hashtable_expand(struct hashtable * htable) {
233 /* Double the size of the table to accomodate more entries */
234 struct hash_entry ** new_table;
235 struct hash_entry * tmp_entry;
236 struct hash_entry ** entry_ptr;
241 /* Check we're not hitting max capacity */
242 if (htable->prime_index == (prime_table_len - 1)) {
246 new_size = primes[++(htable->prime_index)];
248 new_table = (struct hash_entry **)palacios_alloc(sizeof(struct hash_entry*) * new_size);
250 if (new_table != NULL) {
251 memset(new_table, 0, new_size * sizeof(struct hash_entry *));
252 /* This algorithm is not 'stable'. ie. it reverses the list
253 * when it transfers entries between the tables */
255 for (i = 0; i < htable->table_length; i++) {
257 while ((tmp_entry = htable->table[i]) != NULL) {
258 htable->table[i] = tmp_entry->next;
260 index = indexFor(new_size, tmp_entry->hash);
262 tmp_entry->next = new_table[index];
264 new_table[index] = tmp_entry;
268 palacios_free(htable->table);
270 htable->table = new_table;
272 /* Plan B: realloc instead */
274 //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
275 new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
276 new_size * sizeof(struct hash_entry *));
278 if (new_table == NULL) {
279 (htable->prime_index)--;
283 htable->table = new_table;
285 memset(new_table[htable->table_length], 0, new_size - htable->table_length);
287 for (i = 0; i < htable->table_length; i++) {
289 for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
291 tmp_entry = *entry_ptr) {
293 index = indexFor(new_size, tmp_entry->hash);
296 entry_ptr = &(tmp_entry->next);
298 *entry_ptr = tmp_entry->next;
299 tmp_entry->next = new_table[index];
300 new_table[index] = tmp_entry;
306 htable->table_length = new_size;
308 htable->load_limit = load_factors[htable->prime_index];
313 uint_t palacios_htable_count(struct hashtable * htable) {
314 return htable->entry_count;
317 int palacios_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
318 /* This method allows duplicate keys - but they shouldn't be used */
320 struct hash_entry * new_entry;
322 if (++(htable->entry_count) > htable->load_limit) {
323 /* Ignore the return value. If expand fails, we should
324 * still try cramming just this value into the existing table
325 * -- we may not have memory for a larger table, but one more
326 * element may be ok. Next time we insert, we'll try expanding again.*/
327 hashtable_expand(htable);
330 new_entry = (struct hash_entry *)palacios_alloc(sizeof(struct hash_entry));
332 if (new_entry == NULL) {
333 (htable->entry_count)--;
337 new_entry->hash = do_hash(htable, key);
339 index = indexFor(htable->table_length, new_entry->hash);
341 new_entry->key = key;
342 new_entry->value = value;
344 new_entry->next = htable->table[index];
346 htable->table[index] = new_entry;
352 int palacios_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) {
353 struct hash_entry * tmp_entry;
357 hash_value = do_hash(htable, key);
359 index = indexFor(htable->table_length, hash_value);
361 tmp_entry = htable->table[index];
363 while (tmp_entry != NULL) {
364 /* Check hash value to short circuit heavier comparison */
365 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
368 palacios_free((void *)(tmp_entry->value));
371 tmp_entry->value = value;
374 tmp_entry = tmp_entry->next;
381 int palacios_htable_inc(struct hashtable * htable, addr_t key, addr_t value) {
382 struct hash_entry * tmp_entry;
386 hash_value = do_hash(htable, key);
388 index = indexFor(htable->table_length, hash_value);
390 tmp_entry = htable->table[index];
392 while (tmp_entry != NULL) {
393 /* Check hash value to short circuit heavier comparison */
394 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
396 tmp_entry->value += value;
399 tmp_entry = tmp_entry->next;
405 int palacios_htable_dec(struct hashtable * htable, addr_t key, addr_t value) {
406 struct hash_entry * tmp_entry;
410 hash_value = do_hash(htable, key);
412 index = indexFor(htable->table_length, hash_value);
414 tmp_entry = htable->table[index];
416 while (tmp_entry != NULL) {
417 /* Check hash value to short circuit heavier comparison */
418 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
420 tmp_entry->value -= value;
423 tmp_entry = tmp_entry->next;
429 /* returns value associated with key */
430 addr_t palacios_htable_search(struct hashtable * htable, addr_t key) {
431 struct hash_entry * cursor;
435 hash_value = do_hash(htable, key);
437 index = indexFor(htable->table_length, hash_value);
439 cursor = htable->table[index];
441 while (cursor != NULL) {
442 /* Check hash value to short circuit heavier comparison */
443 if ((hash_value == cursor->hash) &&
444 (htable->eq_fn(key, cursor->key))) {
445 return cursor->value;
448 cursor = cursor->next;
455 /* returns value associated with key */
456 addr_t palacios_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
457 /* TODO: consider compacting the table when the load factor drops enough,
458 * or provide a 'compact' method. */
460 struct hash_entry * cursor;
461 struct hash_entry ** entry_ptr;
466 hash_value = do_hash(htable, key);
468 index = indexFor(htable->table_length, hash_value);
470 entry_ptr = &(htable->table[index]);
473 while (cursor != NULL) {
474 /* Check hash value to short circuit heavier comparison */
475 if ((hash_value == cursor->hash) &&
476 (htable->eq_fn(key, cursor->key))) {
478 *entry_ptr = cursor->next;
479 htable->entry_count--;
480 value = cursor->value;
483 freekey((void *)(cursor->key));
485 palacios_free(cursor);
490 entry_ptr = &(cursor->next);
491 cursor = cursor->next;
498 void palacios_free_htable(struct hashtable * htable, int free_values, int free_keys) {
500 struct hash_entry * cursor;
501 struct hash_entry * tmp;
502 struct hash_entry **table = htable->table;
505 for (i = 0; i < htable->table_length; i++) {
508 while (cursor != NULL) {
510 cursor = cursor->next;
513 freekey((void *)(tmp->key));
515 palacios_free((void *)(tmp->value));
520 for (i = 0; i < htable->table_length; i++) {
523 while (cursor != NULL) {
524 struct hash_entry * tmp;
527 cursor = cursor->next;
530 freekey((void *)(tmp->key));
537 palacios_free(htable->table);
538 palacios_free(htable);