X-Git-Url: http://v3vee.org/palacios/gitweb/gitweb.cgi?a=blobdiff_plain;f=palacios%2Fsrc%2Fpalacios%2Fvmm_hashtable.c;h=612ae784780d078360f4d64864c9b5a5539e2dae;hb=e5d7715c14a23e72d742d402d4e4cdf97ffab697;hp=3b742f15f3349676dfe67882aec4f0cc5fd35c71;hpb=af355c370ac80f8e19d6375cb3070213c29a92eb;p=palacios.git diff --git a/palacios/src/palacios/vmm_hashtable.c b/palacios/src/palacios/vmm_hashtable.c index 3b742f1..612ae78 100644 --- a/palacios/src/palacios/vmm_hashtable.c +++ b/palacios/src/palacios/vmm_hashtable.c @@ -1,6 +1,40 @@ -/* Copyright (C) 2004 Christopher Clark */ +/* + Copyright (c) 2002, 2004, Christopher Clark + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of the original author; nor the names of any contributors + may be used to endorse or promote products derived from this software + without specific prior written permission. + + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + /* Modifications made by Jack Lange */ + + #include #include #include @@ -10,8 +44,8 @@ struct hash_entry { - void * key; - void * value; + addr_t key; + addr_t value; uint_t hash; struct hash_entry * next; }; @@ -22,8 +56,8 @@ struct hashtable { uint_t entry_count; uint_t load_limit; uint_t prime_index; - uint_t (*hash_fn) (void * key); - int (*eq_fn) (void * key1, void * key2); + uint_t (*hash_fn) (addr_t key); + int (*eq_fn) (addr_t key1, addr_t key2); }; @@ -32,7 +66,7 @@ struct hashtable { -uint_t do_hash(struct hashtable * htable, void * key) { +uint_t do_hash(struct hashtable * htable, addr_t key) { /* Aim to protect against poor hash functions by adding logic here * - logic taken from java 1.4 hashtable source */ uint_t i = htable->hash_fn(key); @@ -91,7 +125,7 @@ ulong_t hash_long(ulong_t val, uint_t bits) { ulong_t hash_buffer(uchar_t * msg, uint_t length) { ulong_t hash = 0; ulong_t temp = 0; - int i; + uint_t i; for (i = 0; i < length; i++) { hash = (hash << 4) + *(msg + i) + i; @@ -159,8 +193,8 @@ const float max_load_factor = 0.65; /*****************************************************************************/ struct hashtable * create_hashtable(uint_t min_size, - uint_t (*hash_fn) (void *), - int (*eq_fn) (void *, void *)) { + uint_t (*hash_fn) (addr_t), + int (*eq_fn) (addr_t, addr_t)) { struct hashtable * htable; uint_t prime_index; uint_t size = primes[0]; @@ -199,7 +233,7 @@ struct hashtable * create_hashtable(uint_t min_size, htable->entry_count = 0; htable->hash_fn = hash_fn; htable->eq_fn = eq_fn; - htable->load_limit = (uint_t) ceil((double)(size * max_load_factor)); + htable->load_limit = (uint_t) v3_ceil((double)(size * max_load_factor)); return htable; } @@ -283,7 +317,7 @@ static int hashtable_expand(struct hashtable * htable) { htable->table_length = new_size; - htable->load_limit = (uint_t) ceil(new_size * max_load_factor); + htable->load_limit = (uint_t) v3_ceil(new_size * max_load_factor); return -1; } @@ -294,7 +328,7 @@ uint_t hashtable_count(struct hashtable * htable) { } /*****************************************************************************/ -int hashtable_insert(struct hashtable * htable, void * key, void * value) { +int hashtable_insert(struct hashtable * htable, addr_t key, addr_t value) { /* This method allows duplicate keys - but they shouldn't be used */ uint_t index; struct hash_entry * new_entry; @@ -331,7 +365,7 @@ int hashtable_insert(struct hashtable * htable, void * key, void * value) { -int hashtable_change(struct hashtable * htable, void * key, void * value) { +int hashtable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) { struct hash_entry * tmp_entry; uint_t hash_value; uint_t index; @@ -345,10 +379,13 @@ int hashtable_change(struct hashtable * htable, void * key, void * value) { while (tmp_entry != NULL) { /* Check hash value to short circuit heavier comparison */ if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) { - V3_Free(tmp_entry->value); - tmp_entry->value = value; - return -1; + if (free_value) { + V3_Free((void *)(tmp_entry->value)); + } + + tmp_entry->value = value; + return -1; } tmp_entry = tmp_entry->next; } @@ -360,7 +397,7 @@ int hashtable_change(struct hashtable * htable, void * key, void * value) { /*****************************************************************************/ /* returns value associated with key */ -void * hashtable_search(struct hashtable * htable, void * key) { +addr_t hashtable_search(struct hashtable * htable, addr_t key) { struct hash_entry * cursor; uint_t hash_value; uint_t index; @@ -381,18 +418,18 @@ void * hashtable_search(struct hashtable * htable, void * key) { cursor = cursor->next; } - return NULL; + return (addr_t)NULL; } /*****************************************************************************/ /* returns value associated with key */ -void * hashtable_remove(struct hashtable * htable, void * key) { +addr_t hashtable_remove(struct hashtable * htable, addr_t key, int free_key) { /* TODO: consider compacting the table when the load factor drops enough, * or provide a 'compact' method. */ struct hash_entry * cursor; struct hash_entry ** entry_ptr; - void * value; + addr_t value; uint_t hash_value; uint_t index; @@ -412,7 +449,9 @@ void * hashtable_remove(struct hashtable * htable, void * key) { htable->entry_count--; value = cursor->value; - freekey(cursor->key); + if (free_key) { + freekey((void *)(cursor->key)); + } V3_Free(cursor); return value; @@ -421,12 +460,12 @@ void * hashtable_remove(struct hashtable * htable, void * key) { entry_ptr = &(cursor->next); cursor = cursor->next; } - return NULL; + return (addr_t)NULL; } /*****************************************************************************/ /* destroy */ -void hashtable_destroy(struct hashtable * htable, int free_values) { +void hashtable_destroy(struct hashtable * htable, int free_values, int free_keys) { uint_t i; struct hash_entry * cursor;; struct hash_entry **table = htable->table; @@ -441,8 +480,10 @@ void hashtable_destroy(struct hashtable * htable, int free_values) { tmp = cursor; cursor = cursor->next; - freekey(tmp->key); - V3_Free(tmp->value); + if (free_keys) { + freekey((void *)(tmp->key)); + } + V3_Free((void *)(tmp->value)); V3_Free(tmp); } } @@ -455,8 +496,10 @@ void hashtable_destroy(struct hashtable * htable, int free_values) { tmp = cursor; cursor = cursor->next; - - freekey(tmp->key); + + if (free_keys) { + freekey((void *)(tmp->key)); + } V3_Free(tmp); } } @@ -505,11 +548,11 @@ struct hashtable_iter * create_hashtable_iterator(struct hashtable * htable) { } -void * hashtable_get_iter_key(struct hashtable_iter * iter) { +addr_t hashtable_get_iter_key(struct hashtable_iter * iter) { return iter->entry->key; } -void * hashtable_get_iter_value(struct hashtable_iter * iter) { +addr_t hashtable_get_iter_value(struct hashtable_iter * iter) { return iter->entry->value; } @@ -566,7 +609,7 @@ int hashtable_iterator_advance(struct hashtable_iter * iter) { * If you want the value, read it before you remove: * beware memory leaks if you don't. * Returns zero if end of iteration. */ -int hashtable_iterator_remove(struct hashtable_iter * iter) { +int hashtable_iterator_remove(struct hashtable_iter * iter, int free_key) { struct hash_entry * remember_entry; struct hash_entry * remember_parent; int ret; @@ -584,8 +627,10 @@ int hashtable_iterator_remove(struct hashtable_iter * iter) { /* itr->e is now outside the hashtable */ remember_entry = iter->entry; iter->htable->entry_count--; - freekey(remember_entry->key); - + if (free_key) { + freekey((void *)(remember_entry->key)); + } + /* Advance the iterator, correcting the parent */ remember_parent = iter->parent; ret = hashtable_iterator_advance(iter); @@ -601,7 +646,7 @@ int hashtable_iterator_remove(struct hashtable_iter * iter) { /* returns zero if not found */ int hashtable_iterator_search(struct hashtable_iter * iter, - struct hashtable * htable, void * key) { + struct hashtable * htable, addr_t key) { struct hash_entry * entry; struct hash_entry * parent; uint_t hash_value;