diff options
-rw-r--r-- | hash.c | 34 |
1 files changed, 30 insertions, 4 deletions
@@ -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; |