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>
42 #include "util-hashtable.h"
49 struct hash_entry * next;
54 struct hash_entry ** table;
58 uint_t (*hash_fn) (addr_t key);
59 int (*eq_fn) (addr_t key1, addr_t key2);
65 static inline uint_t do_hash(struct hashtable * htable, addr_t key) {
66 /* Aim to protect against poor hash functions by adding logic here
67 * - logic taken from java 1.4 hashtable source */
68 uint_t i = htable->hash_fn(key);
70 i ^= ((i >> 14) | (i << 18)); /* >>> */
72 i ^= ((i >> 10) | (i << 22)); /* >>> */
78 /* HASH AN UNSIGNED LONG */
79 /* LINUX UNSIGHED LONG HASH FUNCTION */
81 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
82 #define GOLDEN_RATIO_PRIME 0x9e370001UL
83 //#define BITS_PER_LONG 32
84 #elif defined(__64BIT__)
85 /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
86 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
87 //#define BITS_PER_LONG 64
89 #error Define GOLDEN_RATIO_PRIME for your wordsize.
92 ulong_t palacios_hash_long(ulong_t val, uint_t bits) {
95 #ifdef __PALACIOS_64BIT__
96 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */
111 /* On some cpus multiply is faster, on others gcc will do shifts */
112 hash *= GOLDEN_RATIO_PRIME;
115 /* High bits are more random, so use them. */
116 return hash >> (BITS_PER_LONG - bits);
119 /* HASH GENERIC MEMORY BUFFER */
120 /* ELF HEADER HASH FUNCTION */
121 ulong_t palacios_hash_buffer(uchar_t * msg, uint_t length) {
126 for (i = 0; i < length; i++) {
127 hash = (hash << 4) + *(msg + i) + i;
128 if ((temp = (hash & 0xF0000000))) {
129 hash ^= (temp >> 24);
137 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
138 return (hash_value % table_length);
141 #define freekey(X) kfree(X)
144 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
145 void * new_buf = kmalloc(new_size, GFP_KERNEL);
147 if (new_buf == NULL) {
151 memcpy(new_buf, old_ptr, old_size);
159 Credit for primes table: Aaron Krowne
160 http://br.endernet.org/~akrowne/
161 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
163 static const uint_t primes[] = {
165 769, 1543, 3079, 6151,
166 12289, 24593, 49157, 98317,
167 196613, 393241, 786433, 1572869,
168 3145739, 6291469, 12582917, 25165843,
169 50331653, 100663319, 201326611, 402653189,
170 805306457, 1610612741 };
173 // this assumes that the max load factor is .65
174 static const uint_t load_factors[] = {
176 500, 1003, 2002, 3999,
177 7988, 15986, 31953, 63907,
178 127799, 255607, 511182, 1022365,
179 2044731, 4089455, 8178897, 16357798,
180 32715575, 65431158, 130862298, 261724573,
181 523449198, 1046898282 };
183 const uint_t prime_table_len = sizeof(primes) / sizeof(primes[0]);
185 struct hashtable * palacios_create_htable(uint_t min_size,
186 uint_t (*hash_fn) (addr_t),
187 int (*eq_fn) (addr_t, addr_t)) {
188 struct hashtable * htable;
190 uint_t size = primes[0];
192 /* Check requested hashtable isn't too large */
193 if (min_size > (1u << 30)) {
197 /* Enforce size as prime */
198 for (prime_index = 0; prime_index < prime_table_len; prime_index++) {
199 if (primes[prime_index] > min_size) {
200 size = primes[prime_index];
205 htable = (struct hashtable *)kmalloc(sizeof(struct hashtable), GFP_KERNEL);
207 if (htable == NULL) {
211 htable->table = (struct hash_entry **)kmalloc(sizeof(struct hash_entry*) * size, GFP_KERNEL);
213 if (htable->table == NULL) {
218 memset(htable->table, 0, size * sizeof(struct hash_entry *));
220 htable->table_length = size;
221 htable->prime_index = prime_index;
222 htable->entry_count = 0;
223 htable->hash_fn = hash_fn;
224 htable->eq_fn = eq_fn;
225 htable->load_limit = load_factors[prime_index];
231 static int hashtable_expand(struct hashtable * htable) {
232 /* Double the size of the table to accomodate more entries */
233 struct hash_entry ** new_table;
234 struct hash_entry * tmp_entry;
235 struct hash_entry ** entry_ptr;
240 /* Check we're not hitting max capacity */
241 if (htable->prime_index == (prime_table_len - 1)) {
245 new_size = primes[++(htable->prime_index)];
247 new_table = (struct hash_entry **)kmalloc(sizeof(struct hash_entry*) * new_size, GFP_KERNEL);
249 if (new_table != NULL) {
250 memset(new_table, 0, new_size * sizeof(struct hash_entry *));
251 /* This algorithm is not 'stable'. ie. it reverses the list
252 * when it transfers entries between the tables */
254 for (i = 0; i < htable->table_length; i++) {
256 while ((tmp_entry = htable->table[i]) != NULL) {
257 htable->table[i] = tmp_entry->next;
259 index = indexFor(new_size, tmp_entry->hash);
261 tmp_entry->next = new_table[index];
263 new_table[index] = tmp_entry;
267 kfree(htable->table);
269 htable->table = new_table;
271 /* Plan B: realloc instead */
273 //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
274 new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
275 new_size * sizeof(struct hash_entry *));
277 if (new_table == NULL) {
278 (htable->prime_index)--;
282 htable->table = new_table;
284 memset(new_table[htable->table_length], 0, new_size - htable->table_length);
286 for (i = 0; i < htable->table_length; i++) {
288 for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
290 tmp_entry = *entry_ptr) {
292 index = indexFor(new_size, tmp_entry->hash);
295 entry_ptr = &(tmp_entry->next);
297 *entry_ptr = tmp_entry->next;
298 tmp_entry->next = new_table[index];
299 new_table[index] = tmp_entry;
305 htable->table_length = new_size;
307 htable->load_limit = load_factors[htable->prime_index];
312 uint_t palacios_htable_count(struct hashtable * htable) {
313 return htable->entry_count;
316 int palacios_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
317 /* This method allows duplicate keys - but they shouldn't be used */
319 struct hash_entry * new_entry;
321 if (++(htable->entry_count) > htable->load_limit) {
322 /* Ignore the return value. If expand fails, we should
323 * still try cramming just this value into the existing table
324 * -- we may not have memory for a larger table, but one more
325 * element may be ok. Next time we insert, we'll try expanding again.*/
326 hashtable_expand(htable);
329 new_entry = (struct hash_entry *)kmalloc(sizeof(struct hash_entry), GFP_KERNEL);
331 if (new_entry == NULL) {
332 (htable->entry_count)--;
336 new_entry->hash = do_hash(htable, key);
338 index = indexFor(htable->table_length, new_entry->hash);
340 new_entry->key = key;
341 new_entry->value = value;
343 new_entry->next = htable->table[index];
345 htable->table[index] = new_entry;
351 int palacios_htable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) {
352 struct hash_entry * tmp_entry;
356 hash_value = do_hash(htable, key);
358 index = indexFor(htable->table_length, hash_value);
360 tmp_entry = htable->table[index];
362 while (tmp_entry != NULL) {
363 /* Check hash value to short circuit heavier comparison */
364 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
367 kfree((void *)(tmp_entry->value));
370 tmp_entry->value = value;
373 tmp_entry = tmp_entry->next;
380 int palacios_htable_inc(struct hashtable * htable, addr_t key, addr_t value) {
381 struct hash_entry * tmp_entry;
385 hash_value = do_hash(htable, key);
387 index = indexFor(htable->table_length, hash_value);
389 tmp_entry = htable->table[index];
391 while (tmp_entry != NULL) {
392 /* Check hash value to short circuit heavier comparison */
393 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
395 tmp_entry->value += value;
398 tmp_entry = tmp_entry->next;
404 int palacios_htable_dec(struct hashtable * htable, addr_t key, addr_t value) {
405 struct hash_entry * tmp_entry;
409 hash_value = do_hash(htable, key);
411 index = indexFor(htable->table_length, hash_value);
413 tmp_entry = htable->table[index];
415 while (tmp_entry != NULL) {
416 /* Check hash value to short circuit heavier comparison */
417 if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
419 tmp_entry->value -= value;
422 tmp_entry = tmp_entry->next;
428 /* returns value associated with key */
429 addr_t palacios_htable_search(struct hashtable * htable, addr_t key) {
430 struct hash_entry * cursor;
434 hash_value = do_hash(htable, key);
436 index = indexFor(htable->table_length, hash_value);
438 cursor = htable->table[index];
440 while (cursor != NULL) {
441 /* Check hash value to short circuit heavier comparison */
442 if ((hash_value == cursor->hash) &&
443 (htable->eq_fn(key, cursor->key))) {
444 return cursor->value;
447 cursor = cursor->next;
454 /* returns value associated with key */
455 addr_t palacios_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
456 /* TODO: consider compacting the table when the load factor drops enough,
457 * or provide a 'compact' method. */
459 struct hash_entry * cursor;
460 struct hash_entry ** entry_ptr;
465 hash_value = do_hash(htable, key);
467 index = indexFor(htable->table_length, hash_value);
469 entry_ptr = &(htable->table[index]);
472 while (cursor != NULL) {
473 /* Check hash value to short circuit heavier comparison */
474 if ((hash_value == cursor->hash) &&
475 (htable->eq_fn(key, cursor->key))) {
477 *entry_ptr = cursor->next;
478 htable->entry_count--;
479 value = cursor->value;
482 freekey((void *)(cursor->key));
489 entry_ptr = &(cursor->next);
490 cursor = cursor->next;
497 void palacios_free_htable(struct hashtable * htable, int free_values, int free_keys) {
499 struct hash_entry * cursor;
500 struct hash_entry * tmp;
501 struct hash_entry **table = htable->table;
504 for (i = 0; i < htable->table_length; i++) {
507 while (cursor != NULL) {
509 cursor = cursor->next;
512 freekey((void *)(tmp->key));
514 kfree((void *)(tmp->value));
519 for (i = 0; i < htable->table_length; i++) {
522 while (cursor != NULL) {
523 struct hash_entry * tmp;
526 cursor = cursor->next;
529 freekey((void *)(tmp->key));
536 kfree(htable->table);