Skip to content
This repository
tag: v1.7.10.2
Fetching contributors…

Cannot retrieve contributors at this time

file 110 lines (98 sloc) 2.6 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
/*
* Some generic hashing helpers.
*/
#include "cache.h"
#include "hash.h"

/*
* Look up a hash entry in the hash table. Return the pointer to
* the existing entry, or the empty slot if none existed. The caller
* can then look at the (*ptr) to see whether it existed or not.
*/
static struct hash_table_entry *lookup_hash_entry(unsigned int hash, const struct hash_table *table)
{
unsigned int size = table->size, nr = hash % size;
struct hash_table_entry *array = table->array;

while (array[nr].ptr) {
if (array[nr].hash == hash)
break;
nr++;
if (nr >= size)
nr = 0;
}
return array + nr;
}


/*
* Insert a new hash entry pointer into the table.
*
* If that hash entry already existed, return the pointer to
* the existing entry (and the caller can create a list of the
* pointers or do anything else). If it didn't exist, return
* NULL (and the caller knows the pointer has been inserted).
*/
static void **insert_hash_entry(unsigned int hash, void *ptr, struct hash_table *table)
{
struct hash_table_entry *entry = lookup_hash_entry(hash, table);

if (!entry->ptr) {
entry->ptr = ptr;
entry->hash = hash;
table->nr++;
return NULL;
}
return &entry->ptr;
}

static void grow_hash_table(struct hash_table *table)
{
unsigned int i;
unsigned int old_size = table->size, new_size;
struct hash_table_entry *old_array = table->array, *new_array;

new_size = alloc_nr(old_size);
new_array = xcalloc(sizeof(struct hash_table_entry), new_size);
table->size = new_size;
table->array = new_array;
table->nr = 0;
for (i = 0; i < old_size; i++) {
unsigned int hash = old_array[i].hash;
void *ptr = old_array[i].ptr;
if (ptr)
insert_hash_entry(hash, ptr, table);
}
free(old_array);
}

void *lookup_hash(unsigned int hash, const struct hash_table *table)
{
if (!table->array)
return NULL;
return lookup_hash_entry(hash, table)->ptr;
}

void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)
{
unsigned int nr = table->nr;
if (nr >= table->size/2)
grow_hash_table(table);
return insert_hash_entry(hash, ptr, table);
}

int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data)
{
int sum = 0;
unsigned int i;
unsigned int size = table->size;
struct hash_table_entry *array = table->array;

for (i = 0; i < size; i++) {
void *ptr = array->ptr;
array++;
if (ptr) {
int val = fn(ptr, data);
if (val < 0)
return val;
sum += val;
}
}
return sum;
}

void free_hash(struct hash_table *table)
{
free(table->array);
table->array = NULL;
table->size = 0;
table->nr = 0;
}
Something went wrong with that request. Please try again.