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.
33 /* Modifications made by Lei Xia <lxia@northwestern.edu> */
35 #include <vnet/vnet_host.h>
36 #include <vnet/vnet_vmm.h>
37 #include <vnet/vnet_hashtable.h>
43 struct hash_entry * next;
48 struct hash_entry ** table;
52 uint_t (*hash_fn) (addr_t key);
53 int (*eq_fn) (addr_t key1, addr_t key2);
59 static inline uint_t do_hash(struct hashtable * htable, addr_t key) {
60 /* Aim to protect against poor hash functions by adding logic here
61 * - logic taken from java 1.4 hashtable source */
62 uint_t i = htable->hash_fn(key);
64 i ^= ((i >> 14) | (i << 18)); /* >>> */
66 i ^= ((i >> 10) | (i << 22)); /* >>> */
72 /* HASH AN UNSIGNED LONG */
73 /* LINUX UNSIGHED LONG HASH FUNCTION */
75 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
76 #define GOLDEN_RATIO_PRIME 0x9e370001UL
77 #define BITS_PER_LONG 32
78 #elif defined(__V3_64BIT__)
79 /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
80 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
81 #define BITS_PER_LONG 64
83 #error Define GOLDEN_RATIO_PRIME for your wordsize.
86 ulong_t vnet_hash_long(ulong_t val, uint_t bits) {
90 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */
105 /* On some cpus multiply is faster, on others gcc will do shifts */
106 hash *= GOLDEN_RATIO_PRIME;
109 /* High bits are more random, so use them. */
110 return hash >> (BITS_PER_LONG - bits);
113 /* HASH GENERIC MEMORY BUFFER */
114 /* ELF HEADER HASH FUNCTION */
115 ulong_t vnet_hash_buffer(uchar_t * msg, uint_t length) {
120 for (i = 0; i < length; i++) {
121 hash = (hash << 4) + *(msg + i) + i;
122 if ((temp = (hash & 0xF0000000))) {
123 hash ^= (temp >> 24);
131 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
132 return (hash_value % table_length);
135 #define freekey(X) Vnet_Free(X)
138 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
139 void * new_buf = Vnet_Malloc(new_size);
141 if (new_buf == NULL) {
145 memcpy(new_buf, old_ptr, old_size);
153 Credit for primes table: Aaron Krowne
154 http://br.endernet.org/~akrowne/
155 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
157 static const uint_t primes[] = {
159 769, 1543, 3079, 6151,
160 12289, 24593, 49157, 98317,
161 196613, 393241, 786433, 1572869,
162 3145739, 6291469, 12582917, 25165843,
163 50331653, 100663319, 201326611, 402653189,
164 805306457, 1610612741 };
167 // this assumes that the max load factor is .65
168 static const uint_t load_factors[] = {
170 500, 1003, 2002, 3999,
171 7988, 15986, 31953, 63907,
172 127799, 255607, 511182, 1022365,
173 2044731, 4089455, 8178897, 16357798,
174 32715575, 65431158, 130862298, 261724573,
175 523449198, 1046898282 };
177 static const uint_t prime_table_length = sizeof(primes) / sizeof(primes[0]);
179 struct hashtable * vnet_create_htable(uint_t min_size,
180 uint_t (*hash_fn) (addr_t),
181 int (*eq_fn) (addr_t, addr_t)) {
182 struct hashtable * htable;
184 uint_t size = primes[0];
186 /* Check requested hashtable isn't too large */
187 if (min_size > (1u << 30)) {
191 /* Enforce size as prime */
192 for (prime_index = 0; prime_index < prime_table_length; prime_index++) {
193 if (primes[prime_index] > min_size) {
194 size = primes[prime_index];
199 if (prime_index==prime_table_length) {
203 htable = (struct hashtable *)Vnet_Malloc(sizeof(struct hashtable));
205 if (htable == NULL) {
209 htable->table = (struct hash_entry **)Vnet_Malloc(sizeof(struct hash_entry*) * size);
211 if (htable->table == NULL) {
216 memset(htable->table, 0, size * sizeof(struct hash_entry *));
218 htable->table_length = size;
219 htable->prime_index = prime_index;
220 htable->entry_count = 0;
221 htable->hash_fn = hash_fn;
222 htable->eq_fn = eq_fn;
223 htable->load_limit = load_factors[prime_index];
230 static int hashtable_expand(struct hashtable * htable) {
231 /* Double the size of the table to accomodate more entries */
232 struct hash_entry ** new_table;
233 struct hash_entry * tmp_entry;
234 struct hash_entry ** entry_ptr;
239 /* Check we're not hitting max capacity */
240 if (htable->prime_index == (prime_table_length - 1)) {
244 new_size = primes[++(htable->prime_index)];
246 new_table = (struct hash_entry **)Vnet_Malloc(sizeof(struct hash_entry*) * new_size);
248 if (new_table != NULL) {
249 memset(new_table, 0, new_size * sizeof(struct hash_entry *));
250 /* This algorithm is not 'stable'. ie. it reverses the list
251 * when it transfers entries between the tables */
253 for (i = 0; i < htable->table_length; i++) {
255 while ((tmp_entry = htable->table[i]) != NULL) {
256 htable->table[i] = tmp_entry->next;
258 index = indexFor(new_size, tmp_entry->hash);
260 tmp_entry->next = new_table[index];
262 new_table[index] = tmp_entry;
266 Vnet_Free(htable->table);
268 htable->table = new_table;
270 /* Plan B: realloc instead */
272 //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
273 new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
274 new_size * sizeof(struct hash_entry *));
276 if (new_table == NULL) {
277 (htable->prime_index)--;
281 htable->table = new_table;
283 memset(new_table[htable->table_length], 0, new_size - htable->table_length);
285 for (i = 0; i < htable->table_length; i++) {
287 for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
289 tmp_entry = *entry_ptr) {
291 index = indexFor(new_size, tmp_entry->hash);
294 entry_ptr = &(tmp_entry->next);
296 *entry_ptr = tmp_entry->next;
297 tmp_entry->next = new_table[index];
298 new_table[index] = tmp_entry;
304 htable->table_length = new_size;
306 htable->load_limit = load_factors[htable->prime_index];
311 uint_t vnet_htable_count(struct hashtable * htable) {
312 return htable->entry_count;
315 int vnet_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
316 /* This method allows duplicate keys - but they shouldn't be used */
318 struct hash_entry * new_entry;
320 if (++(htable->entry_count) > htable->load_limit) {
321 /* Ignore the return value. If expand fails, we should
322 * still try cramming just this value into the existing table
323 * -- we may not have memory for a larger table, but one more
324 * element may be ok. Next time we insert, we'll try expanding again.*/
325 hashtable_expand(htable);
329 new_entry = (struct hash_entry *)Vnet_Malloc(sizeof(struct hash_entry));
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 /* returns value associated with key */
352 addr_t vnet_htable_search(struct hashtable * htable, addr_t key) {
353 struct hash_entry * cursor;
357 hash_value = do_hash(htable, key);
359 index = indexFor(htable->table_length, hash_value);
361 cursor = htable->table[index];
363 while (cursor != NULL) {
364 /* Check hash value to short circuit heavier comparison */
365 if ((hash_value == cursor->hash) &&
366 (htable->eq_fn(key, cursor->key))) {
367 return cursor->value;
370 cursor = cursor->next;
376 /* returns value associated with key */
377 addr_t vnet_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
378 /* TODO: consider compacting the table when the load factor drops enough,
379 * or provide a 'compact' method. */
381 struct hash_entry * cursor;
382 struct hash_entry ** entry_ptr;
387 hash_value = do_hash(htable, key);
389 index = indexFor(htable->table_length, hash_value);
391 entry_ptr = &(htable->table[index]);
394 while (cursor != NULL) {
395 /* Check hash value to short circuit heavier comparison */
396 if ((hash_value == cursor->hash) &&
397 (htable->eq_fn(key, cursor->key))) {
399 *entry_ptr = cursor->next;
400 htable->entry_count--;
401 value = cursor->value;
404 freekey((void *)(cursor->key));
411 entry_ptr = &(cursor->next);
412 cursor = cursor->next;
418 void vnet_free_htable(struct hashtable * htable, int free_values, int free_keys) {
420 struct hash_entry * cursor;;
421 struct hash_entry **table = htable->table;
424 for (i = 0; i < htable->table_length; i++) {
427 while (cursor != NULL) {
428 struct hash_entry * tmp;
431 cursor = cursor->next;
434 freekey((void *)(tmp->key));
436 Vnet_Free((void *)(tmp->value));
441 for (i = 0; i < htable->table_length; i++) {
444 while (cursor != NULL) {
445 struct hash_entry * tmp;
448 cursor = cursor->next;
451 freekey((void *)(tmp->key));
458 Vnet_Free(htable->table);
464 * Copyright (c) 2002, Christopher Clark
465 * All rights reserved.
467 * Redistribution and use in source and binary forms, with or without
468 * modification, are permitted provided that the following conditions
471 * * Redistributions of source code must retain the above copyright
472 * notice, this list of conditions and the following disclaimer.
474 * * Redistributions in binary form must reproduce the above copyright
475 * notice, this list of conditions and the following disclaimer in the
476 * documentation and/or other materials provided with the distribution.
478 * * Neither the name of the original author; nor the names of any contributors
479 * may be used to endorse or promote products derived from this software
480 * without specific prior written permission.
483 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
484 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
485 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
486 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
487 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
488 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
489 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
490 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
491 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
492 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
493 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.