diff options
| -rw-r--r-- | src/libmdsserver/hash-table.c | 61 | ||||
| -rw-r--r-- | src/libmdsserver/hash-table.h | 40 |
2 files changed, 52 insertions, 49 deletions
diff --git a/src/libmdsserver/hash-table.c b/src/libmdsserver/hash-table.c index ba3f846..ef3ae1f 100644 --- a/src/libmdsserver/hash-table.c +++ b/src/libmdsserver/hash-table.c @@ -37,9 +37,9 @@ * @param key The key to hash * @return The hash of the key */ -static inline long __attribute__((const)) hash(const hash_table_t* this, const void* key) +static inline size_t __attribute__((const)) hash(const hash_table_t* restrict this, size_t key) { - return this->hasher ? this->hasher(key) : (long)key; + return this->hasher ? this->hasher(key) : key; } @@ -50,9 +50,9 @@ static inline long __attribute__((const)) hash(const hash_table_t* this, const v * @param key The key to hash * @return A non-negative value less the the table's capacity */ -static inline size_t __attribute__((pure)) truncate_hash(const hash_table_t* restrict this, long hash) +static inline size_t __attribute__((pure)) truncate_hash(const hash_table_t* restrict this, size_t hash) { - return ((size_t)hash) % this->capacity; + return hash % this->capacity; } @@ -130,15 +130,16 @@ int /**/__attribute__((const))/**/ hash_table_clone(const hash_table_t* restrict } + /** * Release all resources in a hash table, should * be done even if construction fails * - * @param this The hash table - * @param values Whether to free all stored values - * @param keys Whether to free all stored keys + * @param this The hash table + * @param keys_out Linked list to fill with all keys in the table, `NULL` if it should not be collected + * @param values_out Linked list to fill with all values in the table, `NULL` if it should not be collected */ -void hash_table_destroy(hash_table_t* restrict this, int values, int keys) +void hash_table_destroy(hash_table_t* restrict this, linked_list_t* keys_out, linked_list_t* values_out) { size_t i = this->capacity; hash_entry_t* bucket; @@ -151,10 +152,10 @@ void hash_table_destroy(hash_table_t* restrict this, int values, int keys) bucket = *(this->buckets + --i); while (bucket) { - if (values) - free(bucket->value); - if (keys) - free(bucket->key); + if (keys_out != NULL) + linked_list_insert_end(keys_out, bucket->key); /* TODO: error support */ + if (values_out != NULL) + linked_list_insert_end(values_out, bucket->value); /* TODO: error support */ bucket = (last = bucket)->next; free(last); } @@ -171,7 +172,7 @@ void hash_table_destroy(hash_table_t* restrict this, int values, int keys) * @param value The value * @return Whether the value is stored in the table */ -int hash_table_contains_value(const hash_table_t* restrict this, void* restrict value) +int hash_table_contains_value(const hash_table_t* restrict this, size_t value) { size_t i = this->capacity; hash_entry_t* bucket; @@ -200,9 +201,9 @@ int hash_table_contains_value(const hash_table_t* restrict this, void* restrict * @param key The key * @return Whether the key is used */ -int hash_table_contains_key(const hash_table_t* restrict this, void* restrict key) +int hash_table_contains_key(const hash_table_t* restrict this, size_t key) { - long key_hash = hash(this, key); + size_t key_hash = hash(this, key); size_t index = truncate_hash(this, key_hash); hash_entry_t* bucket = *(this->buckets + index); @@ -222,11 +223,11 @@ int hash_table_contains_key(const hash_table_t* restrict this, void* restrict ke * * @param this The hash table * @param key The key associated with the value - * @return The value associated with the key, `NULL` i the key was not used + * @return The value associated with the key, 0 if the key was not used */ -void* hash_table_get(const hash_table_t* restrict this, const void* restrict key) +size_t hash_table_get(const hash_table_t* restrict this, size_t key) { - long key_hash = hash(this, key); + size_t key_hash = hash(this, key); size_t index = truncate_hash(this, key_hash); hash_entry_t* bucket = *(this->buckets + index); @@ -237,7 +238,7 @@ void* hash_table_get(const hash_table_t* restrict this, const void* restrict key bucket = bucket->next; } - return NULL; + return 0; } @@ -247,14 +248,14 @@ void* hash_table_get(const hash_table_t* restrict this, const void* restrict key * @param this The hash table * @param key The key of the entry to add * @param value The value of the entry to add - * @return The previous value associated with the key, `NULL` i the key was not used + * @return The previous value associated with the key, 0 if the key was not used */ -void* hash_table_put(hash_table_t* restrict this, void* restrict key, void* restrict value) +size_t hash_table_put(hash_table_t* restrict this, size_t key, size_t value) { - long key_hash = hash(this, key); + size_t key_hash = hash(this, key); size_t index = truncate_hash(this, key_hash); hash_entry_t* bucket = *(this->buckets + index); - void* rc; + size_t rc; while (bucket) if (TEST_KEY(this, bucket, key, key_hash)) @@ -272,14 +273,14 @@ void* hash_table_put(hash_table_t* restrict this, void* restrict key, void* rest index = truncate_hash(this, key_hash); } - bucket = malloc(sizeof(hash_entry_t)); /* TODO */ + bucket = malloc(sizeof(hash_entry_t)); /* TODO: error support */ bucket->value = value; bucket->key = key; bucket->hash = key_hash; bucket->next = *(this->buckets + index); *(this->buckets + index) = bucket; - return NULL; + return 0; } @@ -288,15 +289,15 @@ void* hash_table_put(hash_table_t* restrict this, void* restrict key, void* rest * * @param this The hash table * @param key The key of the entry to remove - * @return The previous value associated with the key, `NULL` i the key was not used + * @return The previous value associated with the key, 0 if the key was not used */ -void* hash_table_remove(hash_table_t* restrict this, const void* restrict key) +size_t hash_table_remove(hash_table_t* restrict this, size_t key) { - long key_hash = hash(this, key); + size_t key_hash = hash(this, key); size_t index = truncate_hash(this, key_hash); hash_entry_t* bucket = *(this->buckets + index); hash_entry_t* last = NULL; - void* rc; + size_t rc; while (bucket) { @@ -315,7 +316,7 @@ void* hash_table_remove(hash_table_t* restrict this, const void* restrict key) bucket = bucket->next; } - return NULL; + return 0; } diff --git a/src/libmdsserver/hash-table.h b/src/libmdsserver/hash-table.h index 8839a0d..f54ea6f 100644 --- a/src/libmdsserver/hash-table.h +++ b/src/libmdsserver/hash-table.h @@ -19,6 +19,8 @@ #define MDS_LIBMDSSERVER_HASH_TABLE_H +#include "linked-list.h" + #include <stdlib.h> @@ -30,17 +32,17 @@ typedef struct hash_entry /** * A key */ - void* key; + size_t key; /** * The value associated with the key */ - void* value; + size_t value; /** * The truncated hash value of the key */ - long hash; + size_t hash; /** * The next entry in the bucket @@ -51,7 +53,7 @@ typedef struct hash_entry /** - * Value lookup table based on hash value, that do not support `NULL` keys nor `NULL` values + * Value lookup table based on hash value, that do not support `0` keys nor `0` values */ typedef struct hash_table { @@ -91,7 +93,7 @@ typedef struct hash_table * @param value_b The second value * @return Whether the values are equals */ - int (*value_comparator)(const void* value_a, const void* value_b); + int (*value_comparator)(size_t value_a, size_t value_b); /** * Check whether two keys are equal @@ -104,7 +106,7 @@ typedef struct hash_table * @param key_b The second key * @return Whether the keys are equals */ - int (*key_comparator)(const void* key_a, const void* key_b); + int (*key_comparator)(size_t key_a, size_t key_b); /** * Calculate the hash of a key @@ -116,7 +118,7 @@ typedef struct hash_table * @param key The key * @return The hash of the key */ - long (*hasher)(const void* key); + size_t (*hasher)(size_t key); } hash_table_t; @@ -164,11 +166,11 @@ int hash_table_clone(const hash_table_t* restrict this, hash_table_t* restrict o * Release all resources in a hash table, should * be done even if construction fails * - * @param this The hash table - * @param values Whether to free all stored values - * @param keys Whether to free all stored keys + * @param this The hash table + * @param keys_out Linked list to fill with all keys in the table, `NULL` if it should not be collected + * @param values_out Linked list to fill with all values in the table, `NULL` if it should not be collected */ -void hash_table_destroy(hash_table_t* restrict this, int values, int keys); +void hash_table_destroy(hash_table_t* restrict this, linked_list_t* keys_out, linked_list_t* values_out); /** * Check whether a value is stored in the table @@ -177,7 +179,7 @@ void hash_table_destroy(hash_table_t* restrict this, int values, int keys); * @param value The value * @return Whether the value is stored in the table */ -int hash_table_contains_value(const hash_table_t* restrict this, void* restrict value) __attribute__((pure)); +int hash_table_contains_value(const hash_table_t* restrict this, size_t value) __attribute__((pure)); /** * Check whether a key is used in the table @@ -186,16 +188,16 @@ int hash_table_contains_value(const hash_table_t* restrict this, void* restrict * @param key The key * @return Whether the key is used */ -int hash_table_contains_key(const hash_table_t* restrict this, void* restrict key) __attribute__((pure)); +int hash_table_contains_key(const hash_table_t* restrict this, size_t key) __attribute__((pure)); /** * Look up a value in the table * * @param this The hash table * @param key The key associated with the value - * @return The value associated with the key, `NULL` i the key was not used + * @return The value associated with the key, 0 if the key was not used */ -void* hash_table_get(const hash_table_t* restrict this, const void* restrict key); +size_t hash_table_get(const hash_table_t* restrict this, size_t key); /** * Add an entry to the table @@ -203,18 +205,18 @@ void* hash_table_get(const hash_table_t* restrict this, const void* restrict key * @param this The hash table * @param key The key of the entry to add * @param value The value of the entry to add - * @return The previous value associated with the key, `NULL` i the key was not used + * @return The previous value associated with the key, 0 if the key was not used */ -void* hash_table_put(hash_table_t* restrict this, void* restrict key, void* restrict value); +size_t hash_table_put(hash_table_t* restrict this, size_t key, size_t value); /** * Remove an entry in the table * * @param this The hash table * @param key The key of the entry to remove - * @return The previous value associated with the key, `NULL` i the key was not used + * @return The previous value associated with the key, 0 if the key was not used */ -void* hash_table_remove(hash_table_t* restrict this, const void* restrict key); +size_t hash_table_remove(hash_table_t* restrict this, size_t key); /** * Remove all entries in the table |