summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--hash.c34
1 files changed, 30 insertions, 4 deletions
diff --git a/hash.c b/hash.c
index 6e27233..51eb627 100644
--- a/hash.c
+++ b/hash.c
@@ -21,6 +21,7 @@ static struct hash_table_entry *lookup_hash_entry(unsigned int hash,
{
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;
@@ -28,6 +29,7 @@ static struct hash_table_entry *lookup_hash_entry(unsigned int hash,
if (nr >= size)
nr = 0;
}
+
return array + nr;
}
@@ -44,12 +46,16 @@ 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;
}
@@ -65,13 +71,17 @@ static void *remove_hash_entry(unsigned int hash, void *ptr, void *ptr_next,
struct hash_table *table)
{
struct hash_table_entry *entry = lookup_hash_entry(hash, table);
+
if (!entry->ptr)
return NULL;
+
else if (entry->ptr == ptr) {
entry->ptr = ptr_next;
entry->hash = hash;
+
if (!ptr_next)
table->nr--;
+
return NULL;
} else
return entry->ptr;
@@ -82,25 +92,30 @@ 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 = xzmalloc(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);
}
- if (old_array)
- xfree(old_array);
+
+ 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;
}
@@ -109,14 +124,17 @@ void *remove_hash(unsigned int hash, void *ptr, void *ptr_next,
{
if (!table->array)
return NULL;
+
return remove_hash_entry(hash, ptr, ptr_next, table);
}
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);
}
@@ -126,16 +144,20 @@ int for_each_hash(const struct hash_table *table, int (*fn)(void *))
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);
if (val < 0)
return val;
+
sum += val;
}
}
+
return sum;
}
@@ -146,23 +168,27 @@ int for_each_hash_int(const struct hash_table *table, int (*fn)(void *, int),
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, arg);
if (val < 0)
return val;
+
sum += val;
}
}
+
return sum;
}
void free_hash(struct hash_table *table)
{
- if (table->array)
- xfree(table->array);
+ free(table->array);
+
table->array = NULL;
table->size = 0;
table->nr = 0;