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 htable = (struct hashtable *)Vnet_Malloc(sizeof(struct hashtable));
201 if (htable == NULL) {
205 htable->table = (struct hash_entry **)Vnet_Malloc(sizeof(struct hash_entry*) * size);
207 if (htable->table == NULL) {
212 memset(htable->table, 0, size * sizeof(struct hash_entry *));
214 htable->table_length = size;
215 htable->prime_index = prime_index;
216 htable->entry_count = 0;
217 htable->hash_fn = hash_fn;
218 htable->eq_fn = eq_fn;
219 htable->load_limit = load_factors[prime_index];
226 static int hashtable_expand(struct hashtable * htable) {
227 /* Double the size of the table to accomodate more entries */
228 struct hash_entry ** new_table;
229 struct hash_entry * tmp_entry;
230 struct hash_entry ** entry_ptr;
235 /* Check we're not hitting max capacity */
236 if (htable->prime_index == (prime_table_length - 1)) {
240 new_size = primes[++(htable->prime_index)];
242 new_table = (struct hash_entry **)Vnet_Malloc(sizeof(struct hash_entry*) * new_size);
244 if (new_table != NULL) {
245 memset(new_table, 0, new_size * sizeof(struct hash_entry *));
246 /* This algorithm is not 'stable'. ie. it reverses the list
247 * when it transfers entries between the tables */
249 for (i = 0; i < htable->table_length; i++) {
251 while ((tmp_entry = htable->table[i]) != NULL) {
252 htable->table[i] = tmp_entry->next;
254 index = indexFor(new_size, tmp_entry->hash);
256 tmp_entry->next = new_table[index];
258 new_table[index] = tmp_entry;
262 Vnet_Free(htable->table);
264 htable->table = new_table;
266 /* Plan B: realloc instead */
268 //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
269 new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
270 new_size * sizeof(struct hash_entry *));
272 if (new_table == NULL) {
273 (htable->prime_index)--;
277 htable->table = new_table;
279 memset(new_table[htable->table_length], 0, new_size - htable->table_length);
281 for (i = 0; i < htable->table_length; i++) {
283 for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
285 tmp_entry = *entry_ptr) {
287 index = indexFor(new_size, tmp_entry->hash);
290 entry_ptr = &(tmp_entry->next);
292 *entry_ptr = tmp_entry->next;
293 tmp_entry->next = new_table[index];
294 new_table[index] = tmp_entry;
300 htable->table_length = new_size;
302 htable->load_limit = load_factors[htable->prime_index];
307 uint_t vnet_htable_count(struct hashtable * htable) {
308 return htable->entry_count;
311 int vnet_htable_insert(struct hashtable * htable, addr_t key, addr_t value) {
312 /* This method allows duplicate keys - but they shouldn't be used */
314 struct hash_entry * new_entry;
316 if (++(htable->entry_count) > htable->load_limit) {
317 /* Ignore the return value. If expand fails, we should
318 * still try cramming just this value into the existing table
319 * -- we may not have memory for a larger table, but one more
320 * element may be ok. Next time we insert, we'll try expanding again.*/
321 hashtable_expand(htable);
325 new_entry = (struct hash_entry *)Vnet_Malloc(sizeof(struct hash_entry));
327 if (new_entry == NULL) {
328 (htable->entry_count)--;
332 new_entry->hash = do_hash(htable, key);
334 index = indexFor(htable->table_length, new_entry->hash);
336 new_entry->key = key;
337 new_entry->value = value;
339 new_entry->next = htable->table[index];
341 htable->table[index] = new_entry;
347 /* returns value associated with key */
348 addr_t vnet_htable_search(struct hashtable * htable, addr_t key) {
349 struct hash_entry * cursor;
353 hash_value = do_hash(htable, key);
355 index = indexFor(htable->table_length, hash_value);
357 cursor = htable->table[index];
359 while (cursor != NULL) {
360 /* Check hash value to short circuit heavier comparison */
361 if ((hash_value == cursor->hash) &&
362 (htable->eq_fn(key, cursor->key))) {
363 return cursor->value;
366 cursor = cursor->next;
372 /* returns value associated with key */
373 addr_t vnet_htable_remove(struct hashtable * htable, addr_t key, int free_key) {
374 /* TODO: consider compacting the table when the load factor drops enough,
375 * or provide a 'compact' method. */
377 struct hash_entry * cursor;
378 struct hash_entry ** entry_ptr;
383 hash_value = do_hash(htable, key);
385 index = indexFor(htable->table_length, hash_value);
387 entry_ptr = &(htable->table[index]);
390 while (cursor != NULL) {
391 /* Check hash value to short circuit heavier comparison */
392 if ((hash_value == cursor->hash) &&
393 (htable->eq_fn(key, cursor->key))) {
395 *entry_ptr = cursor->next;
396 htable->entry_count--;
397 value = cursor->value;
400 freekey((void *)(cursor->key));
407 entry_ptr = &(cursor->next);
408 cursor = cursor->next;
414 void vnet_free_htable(struct hashtable * htable, int free_values, int free_keys) {
416 struct hash_entry * cursor;;
417 struct hash_entry **table = htable->table;
420 for (i = 0; i < htable->table_length; i++) {
423 while (cursor != NULL) {
424 struct hash_entry * tmp;
427 cursor = cursor->next;
430 freekey((void *)(tmp->key));
432 Vnet_Free((void *)(tmp->value));
437 for (i = 0; i < htable->table_length; i++) {
440 while (cursor != NULL) {
441 struct hash_entry * tmp;
444 cursor = cursor->next;
447 freekey((void *)(tmp->key));
454 Vnet_Free(htable->table);
460 * Copyright (c) 2002, Christopher Clark
461 * All rights reserved.
463 * Redistribution and use in source and binary forms, with or without
464 * modification, are permitted provided that the following conditions
467 * * Redistributions of source code must retain the above copyright
468 * notice, this list of conditions and the following disclaimer.
470 * * Redistributions in binary form must reproduce the above copyright
471 * notice, this list of conditions and the following disclaimer in the
472 * documentation and/or other materials provided with the distribution.
474 * * Neither the name of the original author; nor the names of any contributors
475 * may be used to endorse or promote products derived from this software
476 * without specific prior written permission.
479 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
480 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
481 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
482 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
483 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
484 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
485 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
486 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
487 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
488 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
489 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.