diff options
Diffstat (limited to 'src/hashtable.h')
-rw-r--r-- | src/hashtable.h | 139 |
1 files changed, 139 insertions, 0 deletions
diff --git a/src/hashtable.h b/src/hashtable.h new file mode 100644 index 0000000..9dfae70 --- /dev/null +++ b/src/hashtable.h @@ -0,0 +1,139 @@ +#ifndef HASHTABLE_H +#define HASHTABLE_H + +typedef unsigned long (*table_hash_func)(void *key); +typedef int (*table_compare_func)(void *key_a, void *key_b); + +struct bucket +{ + void *key; + void *value; + struct bucket *next; +}; +struct table +{ + int count; + int capacity; + int key_capacity; + table_hash_func hash; + table_compare_func compare; + void **keys; + struct bucket **buckets; +}; + +void table_init(struct table *table, int capacity, table_hash_func hash, table_compare_func compare); +void table_free(struct table *table); + +void *table_find(struct table *table, void *key); +void table_add(struct table *table, void *key, void *value); +void *table_remove(struct table *table, void *key); +void *table_reset(struct table *table, int *count); + +#endif + +#ifdef HASHTABLE_IMPLEMENTATION +#include <stdlib.h> +#include <string.h> + +static struct bucket * +table_new_bucket(void *key, void *value) +{ + struct bucket *bucket = malloc(sizeof(struct bucket)); + bucket->key = key; + bucket->value = value; + bucket->next = NULL; + return bucket; +} + +static struct bucket ** +table_get_bucket(struct table *table, void *key) +{ + struct bucket **bucket = table->buckets + (table->hash(key) % table->capacity); + while(*bucket) { + if(table->compare((*bucket)->key, key)) { + break; + } + bucket = &(*bucket)->next; + } + return bucket; +} + +void table_init(struct table *table, int capacity, table_hash_func hash, table_compare_func compare) +{ + table->count = 0; + table->capacity = capacity; + table->hash = hash; + table->compare = compare; + table->key_capacity = capacity * 2; + table->keys = malloc(sizeof(void *) * table->key_capacity); + table->buckets = malloc(sizeof(struct bucket *) * capacity); + memset(table->buckets, 0, sizeof(struct bucket *) * capacity); +} + +void table_free(struct table *table) +{ + for(int i = 0; i < table->capacity; ++i) { + struct bucket *next, *bucket = table->buckets[i]; + while(bucket) { + next = bucket->next; + free(bucket); + bucket = next; + } + } + free(table->buckets); +} + +void *table_find(struct table *table, void *key) +{ + struct bucket *bucket = *table_get_bucket(table, key); + return bucket ? bucket->value : NULL; +} + +void table_add(struct table *table, void *key, void *value) +{ + struct bucket **bucket = table_get_bucket(table, key); + if(*bucket) { + (*bucket)->value = value; + } else { + *bucket = table_new_bucket(key, value); + if(table->count == table->key_capacity) { + table->key_capacity *= 2; + table->keys = realloc(table->keys, sizeof(void *) * table->key_capacity); + } + table->keys[table->count++] = key; + } +} + +void *table_remove(struct table *table, void *key) +{ + void *result = NULL; + struct bucket *next, **bucket = table_get_bucket(table, key); + if(*bucket) { + result = (*bucket)->value; + next = (*bucket)->next; + free(*bucket); + *bucket = next; + --table->count; + } + return result; +} + +void *table_reset(struct table *table, int *count) +{ + void **values; + int index; + int item; + + *count = table->count; + values = malloc(sizeof(void *) * table->count); + item = 0; + + for(index = 0; index < *count; ++index) { + values[item++] = table_remove(table, table->keys[index]); + } + + return values; +} + +#undef HASHTABLE_IMPLEMENTATION +#endif |