struct hash_entry {
- addr_t key;
- addr_t value;
- uint_t hash;
- struct hash_entry * next;
+ addr_t key;
+ addr_t value;
+ uint_t hash;
+ struct hash_entry * next;
};
struct hashtable {
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);
- i += ~(i << 9);
- i ^= ((i >> 14) | (i << 18)); /* >>> */
- i += (i << 4);
- i ^= ((i >> 10) | (i << 22)); /* >>> */
-
- return i;
+ /* 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);
+ i += ~(i << 9);
+ i ^= ((i >> 14) | (i << 18)); /* >>> */
+ i += (i << 4);
+ i ^= ((i >> 10) | (i << 22)); /* >>> */
+
+ return i;
}
#endif
ulong_t hash_long(ulong_t val, uint_t bits) {
- ulong_t hash = val;
+ ulong_t hash = val;
#ifdef __V3_64BIT__
- /* Sigh, gcc can't optimise this alone like it does for 32 bits. */
- ulong_t n = hash;
- n <<= 18;
- hash -= n;
- n <<= 33;
- hash -= n;
- n <<= 3;
- hash += n;
- n <<= 3;
- hash -= n;
- n <<= 4;
- hash += n;
- n <<= 2;
- hash += n;
+ /* Sigh, gcc can't optimise this alone like it does for 32 bits. */
+ ulong_t n = hash;
+ n <<= 18;
+ hash -= n;
+ n <<= 33;
+ hash -= n;
+ n <<= 3;
+ hash += n;
+ n <<= 3;
+ hash -= n;
+ n <<= 4;
+ hash += n;
+ n <<= 2;
+ hash += n;
#else
- /* On some cpus multiply is faster, on others gcc will do shifts */
- hash *= GOLDEN_RATIO_PRIME;
+ /* On some cpus multiply is faster, on others gcc will do shifts */
+ hash *= GOLDEN_RATIO_PRIME;
#endif
- /* High bits are more random, so use them. */
- return hash >> (BITS_PER_LONG - bits);
+ /* High bits are more random, so use them. */
+ return hash >> (BITS_PER_LONG - bits);
}
/* HASH GENERIC MEMORY BUFFER */
/* ELF HEADER HASH FUNCTION */
ulong_t hash_buffer(uchar_t * msg, uint_t length) {
- ulong_t hash = 0;
- ulong_t temp = 0;
- uint_t i;
-
- for (i = 0; i < length; i++) {
- hash = (hash << 4) + *(msg + i) + i;
- if ((temp = (hash & 0xF0000000))) {
- hash ^= (temp >> 24);
+ ulong_t hash = 0;
+ ulong_t temp = 0;
+ uint_t i;
+
+ for (i = 0; i < length; i++) {
+ hash = (hash << 4) + *(msg + i) + i;
+ if ((temp = (hash & 0xF0000000))) {
+ hash ^= (temp >> 24);
+ }
+ hash &= ~temp;
}
- hash &= ~temp;
- }
- return hash;
+ return hash;
}
/*****************************************************************************/
/* indexFor */
static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
- return (hash_value % table_length);
+ return (hash_value % table_length);
};
/* Only works if table_length == 2^N */
static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
- void * new_buf = V3_Malloc(new_size);
+ void * new_buf = V3_Malloc(new_size);
- if (new_buf == NULL) {
- return NULL;
- }
+ if (new_buf == NULL) {
+ return NULL;
+ }
- memcpy(new_buf, old_ptr, old_size);
- V3_Free(old_ptr);
+ memcpy(new_buf, old_ptr, old_size);
+ V3_Free(old_ptr);
- return new_buf;
+ return new_buf;
}
/*
-Credit for primes table: Aaron Krowne
- http://br.endernet.org/~akrowne/
- http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
+ Credit for primes table: Aaron Krowne
+ http://br.endernet.org/~akrowne/
+ http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
*/
static const uint_t primes[] = {
- 53, 97, 193, 389,
- 769, 1543, 3079, 6151,
- 12289, 24593, 49157, 98317,
- 196613, 393241, 786433, 1572869,
- 3145739, 6291469, 12582917, 25165843,
- 50331653, 100663319, 201326611, 402653189,
- 805306457, 1610612741 };
+ 53, 97, 193, 389,
+ 769, 1543, 3079, 6151,
+ 12289, 24593, 49157, 98317,
+ 196613, 393241, 786433, 1572869,
+ 3145739, 6291469, 12582917, 25165843,
+ 50331653, 100663319, 201326611, 402653189,
+ 805306457, 1610612741 };
const uint_t prime_table_length = sizeof(primes) / sizeof(primes[0]);
/* Check requested hashtable isn't too large */
if (min_size > (1u << 30)) {
- return NULL;
+ return NULL;
}
/* Enforce size as prime */
for (prime_index = 0; prime_index < prime_table_length; prime_index++) {
if (primes[prime_index] > min_size) {
- size = primes[prime_index];
- break;
+ size = primes[prime_index];
+ break;
}
}
htable = (struct hashtable *)V3_Malloc(sizeof(struct hashtable));
if (htable == NULL) {
- return NULL; /*oom*/
+ return NULL; /*oom*/
}
htable->table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * size);
if (htable->table == NULL) {
- V3_Free(htable);
- return NULL; /*oom*/
+ V3_Free(htable);
+ return NULL; /*oom*/
}
/* Check we're not hitting max capacity */
if (htable->prime_index == (prime_table_length - 1)) {
- return 0;
+ return 0;
}
new_size = primes[++(htable->prime_index)];
for (i = 0; i < htable->table_length; i++) {
- while ((tmp_entry = htable->table[i]) != NULL) {
- htable->table[i] = tmp_entry->next;
+ while ((tmp_entry = htable->table[i]) != NULL) {
+ htable->table[i] = tmp_entry->next;
- index = indexFor(new_size, tmp_entry->hash);
+ index = indexFor(new_size, tmp_entry->hash);
- tmp_entry->next = new_table[index];
+ tmp_entry->next = new_table[index];
- new_table[index] = tmp_entry;
- }
+ new_table[index] = tmp_entry;
+ }
}
V3_Free(htable->table);
htable->table = new_table;
} else {
- /* Plan B: realloc instead */
+ /* Plan B: realloc instead */
- //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
- new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
- new_size * sizeof(struct hash_entry *));
+ //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
+ new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
+ new_size * sizeof(struct hash_entry *));
- if (new_table == NULL) {
- (htable->prime_index)--;
- return 0;
- }
+ if (new_table == NULL) {
+ (htable->prime_index)--;
+ return 0;
+ }
- htable->table = new_table;
+ htable->table = new_table;
- memset(new_table[htable->table_length], 0, new_size - htable->table_length);
+ memset(new_table[htable->table_length], 0, new_size - htable->table_length);
- for (i = 0; i < htable->table_length; i++) {
+ for (i = 0; i < htable->table_length; i++) {
- for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
- tmp_entry != NULL;
- tmp_entry = *entry_ptr) {
+ for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
+ tmp_entry != NULL;
+ tmp_entry = *entry_ptr) {
- index = indexFor(new_size, tmp_entry->hash);
+ index = indexFor(new_size, tmp_entry->hash);
- if (i == index) {
- entry_ptr = &(tmp_entry->next);
- } else {
- *entry_ptr = tmp_entry->next;
- tmp_entry->next = new_table[index];
- new_table[index] = tmp_entry;
- }
+ if (i == index) {
+ entry_ptr = &(tmp_entry->next);
+ } else {
+ *entry_ptr = tmp_entry->next;
+ tmp_entry->next = new_table[index];
+ new_table[index] = tmp_entry;
+ }
+ }
}
- }
}
htable->table_length = new_size;
struct hash_entry * new_entry;
if (++(htable->entry_count) > htable->load_limit) {
- /* Ignore the return value. If expand fails, we should
- * still try cramming just this value into the existing table
- * -- we may not have memory for a larger table, but one more
- * element may be ok. Next time we insert, we'll try expanding again.*/
- hashtable_expand(htable);
+ /* Ignore the return value. If expand fails, we should
+ * still try cramming just this value into the existing table
+ * -- we may not have memory for a larger table, but one more
+ * element may be ok. Next time we insert, we'll try expanding again.*/
+ hashtable_expand(htable);
}
new_entry = (struct hash_entry *)V3_Malloc(sizeof(struct hash_entry));
if (new_entry == NULL) {
- (htable->entry_count)--;
- return 0; /*oom*/
+ (htable->entry_count)--;
+ return 0; /*oom*/
}
new_entry->hash = do_hash(htable, key);
/* Check hash value to short circuit heavier comparison */
if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
- if (free_value) {
- V3_Free((void *)(tmp_entry->value));
- }
+ if (free_value) {
+ V3_Free((void *)(tmp_entry->value));
+ }
- tmp_entry->value = value;
- return -1;
+ tmp_entry->value = value;
+ return -1;
}
tmp_entry = tmp_entry->next;
}
/* Check hash value to short circuit heavier comparison */
if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
- tmp_entry->value += value;
- return -1;
+ tmp_entry->value += value;
+ return -1;
}
tmp_entry = tmp_entry->next;
}
/* Check hash value to short circuit heavier comparison */
if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
- tmp_entry->value -= value;
- return -1;
+ tmp_entry->value -= value;
+ return -1;
}
tmp_entry = tmp_entry->next;
}
/*****************************************************************************/
/* returns value associated with key */
addr_t hashtable_search(struct hashtable * htable, addr_t key) {
- struct hash_entry * cursor;
- uint_t hash_value;
- uint_t index;
+ struct hash_entry * cursor;
+ uint_t hash_value;
+ uint_t index;
- hash_value = do_hash(htable, key);
+ hash_value = do_hash(htable, key);
- index = indexFor(htable->table_length, hash_value);
+ index = indexFor(htable->table_length, hash_value);
- cursor = htable->table[index];
+ cursor = htable->table[index];
- while (cursor != NULL) {
- /* Check hash value to short circuit heavier comparison */
- if ((hash_value == cursor->hash) &&
- (htable->eq_fn(key, cursor->key))) {
- return cursor->value;
- }
+ while (cursor != NULL) {
+ /* Check hash value to short circuit heavier comparison */
+ if ((hash_value == cursor->hash) &&
+ (htable->eq_fn(key, cursor->key))) {
+ return cursor->value;
+ }
- cursor = cursor->next;
- }
+ cursor = cursor->next;
+ }
- return (addr_t)NULL;
+ return (addr_t)NULL;
}
/*****************************************************************************/
/* returns value associated with 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. */
+ /* 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;
- addr_t value;
- uint_t hash_value;
- uint_t index;
+ struct hash_entry * cursor;
+ struct hash_entry ** entry_ptr;
+ addr_t value;
+ uint_t hash_value;
+ uint_t index;
- hash_value = do_hash(htable, key);
+ hash_value = do_hash(htable, key);
- index = indexFor(htable->table_length, hash_value);
+ index = indexFor(htable->table_length, hash_value);
- entry_ptr = &(htable->table[index]);
- cursor = *entry_ptr;
+ entry_ptr = &(htable->table[index]);
+ cursor = *entry_ptr;
- while (cursor != NULL) {
- /* Check hash value to short circuit heavier comparison */
- if ((hash_value == cursor->hash) &&
- (htable->eq_fn(key, cursor->key))) {
+ while (cursor != NULL) {
+ /* Check hash value to short circuit heavier comparison */
+ if ((hash_value == cursor->hash) &&
+ (htable->eq_fn(key, cursor->key))) {
- *entry_ptr = cursor->next;
- htable->entry_count--;
- value = cursor->value;
+ *entry_ptr = cursor->next;
+ htable->entry_count--;
+ value = cursor->value;
- if (free_key) {
- freekey((void *)(cursor->key));
- }
- V3_Free(cursor);
+ if (free_key) {
+ freekey((void *)(cursor->key));
+ }
+ V3_Free(cursor);
- return value;
- }
+ return value;
+ }
- entry_ptr = &(cursor->next);
- cursor = cursor->next;
- }
- return (addr_t)NULL;
+ entry_ptr = &(cursor->next);
+ cursor = cursor->next;
+ }
+ return (addr_t)NULL;
}
/*****************************************************************************/
/* destroy */
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;
+ uint_t i;
+ struct hash_entry * cursor;;
+ struct hash_entry **table = htable->table;
- if (free_values) {
- for (i = 0; i < htable->table_length; i++) {
- cursor = table[i];
+ if (free_values) {
+ for (i = 0; i < htable->table_length; i++) {
+ cursor = table[i];
- while (cursor != NULL) {
- struct hash_entry * tmp;
-
- tmp = cursor;
- cursor = cursor->next;
-
- if (free_keys) {
- freekey((void *)(tmp->key));
+ while (cursor != NULL) {
+ struct hash_entry * tmp;
+
+ tmp = cursor;
+ cursor = cursor->next;
+
+ if (free_keys) {
+ freekey((void *)(tmp->key));
+ }
+ V3_Free((void *)(tmp->value));
+ V3_Free(tmp);
+ }
}
- V3_Free((void *)(tmp->value));
- V3_Free(tmp);
- }
- }
- } else {
- for (i = 0; i < htable->table_length; i++) {
- cursor = table[i];
+ } else {
+ for (i = 0; i < htable->table_length; i++) {
+ cursor = table[i];
- while (cursor != NULL) {
- struct hash_entry * tmp;
+ while (cursor != NULL) {
+ struct hash_entry * tmp;
- tmp = cursor;
- cursor = cursor->next;
+ tmp = cursor;
+ cursor = cursor->next;
- if (free_keys) {
- freekey((void *)(tmp->key));
+ if (free_keys) {
+ freekey((void *)(tmp->key));
+ }
+ V3_Free(tmp);
+ }
}
- V3_Free(tmp);
- }
}
- }
- V3_Free(htable->table);
- V3_Free(htable);
+ V3_Free(htable->table);
+ V3_Free(htable);
}
struct hashtable_iter * create_hashtable_iterator(struct hashtable * htable) {
- uint_t i;
- uint_t table_length;
+ uint_t i;
+ uint_t table_length;
- struct hashtable_iter * iter = (struct hashtable_iter *)V3_Malloc(sizeof(struct hashtable_iter));
+ struct hashtable_iter * iter = (struct hashtable_iter *)V3_Malloc(sizeof(struct hashtable_iter));
- if (iter == NULL) {
- return NULL;
- }
+ if (iter == NULL) {
+ return NULL;
+ }
- iter->htable = htable;
- iter->entry = NULL;
- iter->parent = NULL;
- table_length = htable->table_length;
- iter->index = table_length;
+ iter->htable = htable;
+ iter->entry = NULL;
+ iter->parent = NULL;
+ table_length = htable->table_length;
+ iter->index = table_length;
- if (htable->entry_count == 0) {
- return iter;
- }
+ if (htable->entry_count == 0) {
+ return iter;
+ }
- for (i = 0; i < table_length; i++) {
- if (htable->table[i] != NULL) {
- iter->entry = htable->table[i];
- iter->index = i;
- break;
+ for (i = 0; i < table_length; i++) {
+ if (htable->table[i] != NULL) {
+ iter->entry = htable->table[i];
+ iter->index = i;
+ break;
+ }
}
- }
- return iter;
+ return iter;
}
addr_t hashtable_get_iter_key(struct hashtable_iter * iter) {
- return iter->entry->key;
+ return iter->entry->key;
}
addr_t hashtable_get_iter_value(struct hashtable_iter * iter) {
- return iter->entry->value;
+ return iter->entry->value;
}
/* advance - advance the iterator to the next element
* returns zero if advanced to end of table */
int hashtable_iterator_advance(struct hashtable_iter * iter) {
- uint_t j;
- uint_t table_length;
- struct hash_entry ** table;
- struct hash_entry * next;
+ uint_t j;
+ uint_t table_length;
+ struct hash_entry ** table;
+ struct hash_entry * next;
- if (iter->entry == NULL) {
- return 0; /* stupidity check */
- }
+ if (iter->entry == NULL) {
+ return 0; /* stupidity check */
+ }
- next = iter->entry->next;
+ next = iter->entry->next;
- if (next != NULL) {
- iter->parent = iter->entry;
- iter->entry = next;
- return -1;
- }
+ if (next != NULL) {
+ iter->parent = iter->entry;
+ iter->entry = next;
+ return -1;
+ }
- table_length = iter->htable->table_length;
- iter->parent = NULL;
+ table_length = iter->htable->table_length;
+ iter->parent = NULL;
- if (table_length <= (j = ++(iter->index))) {
- iter->entry = NULL;
- return 0;
- }
+ if (table_length <= (j = ++(iter->index))) {
+ iter->entry = NULL;
+ return 0;
+ }
- table = iter->htable->table;
+ table = iter->htable->table;
- while ((next = table[j]) == NULL) {
- if (++j >= table_length) {
- iter->index = table_length;
- iter->entry = NULL;
- return 0;
+ while ((next = table[j]) == NULL) {
+ if (++j >= table_length) {
+ iter->index = table_length;
+ iter->entry = NULL;
+ return 0;
+ }
}
- }
- iter->index = j;
- iter->entry = next;
+ iter->index = j;
+ iter->entry = next;
- return -1;
+ return -1;
}
* beware memory leaks if you don't.
* Returns zero if end of iteration. */
int hashtable_iterator_remove(struct hashtable_iter * iter, int free_key) {
- struct hash_entry * remember_entry;
- struct hash_entry * remember_parent;
- int ret;
-
- /* Do the removal */
- if ((iter->parent) == NULL) {
- /* element is head of a chain */
- iter->htable->table[iter->index] = iter->entry->next;
- } else {
- /* element is mid-chain */
- iter->parent->next = iter->entry->next;
- }
+ struct hash_entry * remember_entry;
+ struct hash_entry * remember_parent;
+ int ret;
+
+ /* Do the removal */
+ if ((iter->parent) == NULL) {
+ /* element is head of a chain */
+ iter->htable->table[iter->index] = iter->entry->next;
+ } else {
+ /* element is mid-chain */
+ iter->parent->next = iter->entry->next;
+ }
- /* itr->e is now outside the hashtable */
- remember_entry = iter->entry;
- iter->htable->entry_count--;
- if (free_key) {
- freekey((void *)(remember_entry->key));
- }
+ /* itr->e is now outside the hashtable */
+ remember_entry = iter->entry;
+ iter->htable->entry_count--;
+ if (free_key) {
+ freekey((void *)(remember_entry->key));
+ }
- /* Advance the iterator, correcting the parent */
- remember_parent = iter->parent;
- ret = hashtable_iterator_advance(iter);
+ /* Advance the iterator, correcting the parent */
+ remember_parent = iter->parent;
+ ret = hashtable_iterator_advance(iter);
- if (iter->parent == remember_entry) {
- iter->parent = remember_parent;
- }
+ if (iter->parent == remember_entry) {
+ iter->parent = remember_parent;
+ }
- V3_Free(remember_entry);
- return ret;
+ V3_Free(remember_entry);
+ return ret;
}
/* returns zero if not found */
int hashtable_iterator_search(struct hashtable_iter * iter,
struct hashtable * htable, addr_t key) {
- struct hash_entry * entry;
- struct hash_entry * parent;
- uint_t hash_value;
- uint_t index;
+ struct hash_entry * entry;
+ struct hash_entry * parent;
+ uint_t hash_value;
+ uint_t index;
- hash_value = do_hash(htable, key);
- index = indexFor(htable->table_length, hash_value);
+ hash_value = do_hash(htable, key);
+ index = indexFor(htable->table_length, hash_value);
- entry = htable->table[index];
- parent = NULL;
+ entry = htable->table[index];
+ parent = NULL;
- while (entry != NULL) {
- /* Check hash value to short circuit heavier comparison */
- if ((hash_value == entry->hash) &&
- (htable->eq_fn(key, entry->key))) {
- iter->index = index;
- iter->entry = entry;
- iter->parent = parent;
- iter->htable = htable;
- return -1;
+ while (entry != NULL) {
+ /* Check hash value to short circuit heavier comparison */
+ if ((hash_value == entry->hash) &&
+ (htable->eq_fn(key, entry->key))) {
+ iter->index = index;
+ iter->entry = entry;
+ iter->parent = parent;
+ iter->htable = htable;
+ return -1;
+ }
+ parent = entry;
+ entry = entry->next;
}
- parent = entry;
- entry = entry->next;
- }
- return 0;
+ return 0;
}
* 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.
-*/
+ */
