From fee76fa26ae69aa28935efd51a912a44d539523b Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Tue, 22 Apr 2014 09:05:13 +0200 Subject: first draft of hash table implementation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/libmdsserver/hash-table.c | 392 ++++++++++++++++++++++++++++++++++++++++++ src/libmdsserver/hash-table.h | 254 +++++++++++++++++++++++++++ 2 files changed, 646 insertions(+) create mode 100644 src/libmdsserver/hash-table.c create mode 100644 src/libmdsserver/hash-table.h (limited to 'src') diff --git a/src/libmdsserver/hash-table.c b/src/libmdsserver/hash-table.c new file mode 100644 index 0000000..ba3f846 --- /dev/null +++ b/src/libmdsserver/hash-table.c @@ -0,0 +1,392 @@ +/** + * mds — A micro-display server + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ +#include "hash-table.h" + + +/** + * Test if a key matches the key in a bucket + * + * @param T The instance of the hash table + * @param B The bucket + * @param K The key + * @param H The hash of the key + */ +#define TEST_KEY(T, B, K, H) \ + ((B->key == K) || (T->key_comparator && (B->hash == H) && T->key_comparator(B->key, K))) + + +/** + * Calculate the hash of a key + * + * @param this The hash table + * @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) +{ + return this->hasher ? this->hasher(key) : (long)key; +} + + +/** + * Truncates the hash of a key to constrain it to the buckets + * + * @param this The hash table + * @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) +{ + return ((size_t)hash) % this->capacity; +} + + +/** + * Grow the table + * + * @param this The hash table + */ +static void rehash(hash_table_t* restrict this) +{ + hash_entry_t** old_buckets = this->buckets; + size_t old_capacity = this->capacity; + size_t i = old_capacity, index; + hash_entry_t* bucket; + hash_entry_t* destination; + hash_entry_t* next; + + this->capacity = old_capacity * 2 + 1; + this->threshold = (size_t)((float)(this->capacity) * this->load_factor); + this->buckets = calloc(this->capacity, sizeof(hash_entry_t*)); + + while (i) + { + bucket = *(this->buckets + --i); + while (bucket) + { + index = truncate_hash(this, bucket->hash); + if ((destination = *(this->buckets + index))) + { + next = destination->next; + while (next) + { + destination = next; + next = destination->next; + } + destination->next = bucket; + } + else + *(this->buckets + index) = bucket; + + next = bucket->next; + bucket->next = NULL; + bucket = next; + } + } + + free(old_buckets); +} + + +/** + * Create a hash table + * + * @param this Memory slot in which to store the new hash table + * @param initial_capacity The initial capacity of the table + * @param load_factor The load factor of the table, i.e. when to grow the table + * @return Non-zero on error, `errno` will have been set accordingly + */ +int /**/__attribute__((const))/**/ hash_table_create_fine_tuned(hash_table_t* restrict this, size_t initial_capacity, float load_factor) +{ + (void) this; (void) initial_capacity; (void) load_factor; return 0; /* TODO */ +} + + +/** + * Clone a hash table + * + * @param this The hash table to clone + * @param out Memory slot in which to store the new hash table + * @return Non-zero on error, `errno` will have been set accordingly + */ +int /**/__attribute__((const))/**/ hash_table_clone(const hash_table_t* restrict this, hash_table_t* restrict out) +{ + (void) this; (void) out; return 0; /* TODO */ +} + + +/** + * 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 + */ +void hash_table_destroy(hash_table_t* restrict this, int values, int keys) +{ + size_t i = this->capacity; + hash_entry_t* bucket; + hash_entry_t* last; + + if (this->buckets != NULL) + { + while (i) + { + bucket = *(this->buckets + --i); + while (bucket) + { + if (values) + free(bucket->value); + if (keys) + free(bucket->key); + bucket = (last = bucket)->next; + free(last); + } + } + free(this->buckets); + } +} + + +/** + * Check whether a value is stored in the table + * + * @param this The hash table + * @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) +{ + size_t i = this->capacity; + hash_entry_t* bucket; + + while (i) + { + bucket = *(this->buckets + --i); + while (bucket) + { + if (bucket->value == value) + return 1; + if (this->value_comparator && this->value_comparator(bucket->value, value)) + return 1; + bucket = bucket->next; + } + } + + return 0; +} + + +/** + * Check whether a key is used in the table + * + * @param this The hash table + * @param key The key + * @return Whether the key is used + */ +int hash_table_contains_key(const hash_table_t* restrict this, void* restrict key) +{ + long key_hash = hash(this, key); + size_t index = truncate_hash(this, key_hash); + hash_entry_t* bucket = *(this->buckets + index); + + while (bucket) + { + if (TEST_KEY(this, bucket, key, key_hash)) + return 1; + bucket = bucket->next; + } + + return 0; +} + + +/** + * 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 + */ +void* hash_table_get(const hash_table_t* restrict this, const void* restrict key) +{ + long key_hash = hash(this, key); + size_t index = truncate_hash(this, key_hash); + hash_entry_t* bucket = *(this->buckets + index); + + while (bucket) + { + if (TEST_KEY(this, bucket, key, key_hash)) + return bucket->value; + bucket = bucket->next; + } + + return NULL; +} + + +/** + * Add an entry to the table + * + * @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 + */ +void* hash_table_put(hash_table_t* restrict this, void* restrict key, void* restrict value) +{ + long key_hash = hash(this, key); + size_t index = truncate_hash(this, key_hash); + hash_entry_t* bucket = *(this->buckets + index); + void* rc; + + while (bucket) + if (TEST_KEY(this, bucket, key, key_hash)) + { + rc = bucket->value; + bucket->value = value; + return rc; + } + else + bucket = bucket->next; + + if (++(this->size) > this->threshold) + { + rehash(this); + index = truncate_hash(this, key_hash); + } + + bucket = malloc(sizeof(hash_entry_t)); /* TODO */ + bucket->value = value; + bucket->key = key; + bucket->hash = key_hash; + bucket->next = *(this->buckets + index); + *(this->buckets + index) = bucket; + + return NULL; +} + + +/** + * 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 + */ +void* hash_table_remove(hash_table_t* restrict this, const void* restrict key) +{ + long 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; + + while (bucket) + { + if (TEST_KEY(this, bucket, key, key_hash)) + { + if (last == NULL) + *(this->buckets + index) = bucket->next; + else + last->next = bucket->next; + this->size--; + rc = bucket->value; + free(bucket); + return rc; + } + last = bucket; + bucket = bucket->next; + } + + return NULL; +} + + +/** + * Remove all entries in the table + * + * @param this The hash table + */ +void hash_table_clear(hash_table_t* restrict this) +{ + hash_entry_t** buf; + hash_entry_t* bucket; + size_t i, ptr; + + if (this->size) + { + buf = alloca((this->size + 1) * sizeof(hash_entry_t*)); + i = this->capacity; + while (i) + { + bucket = *(this->buckets + --i); + ptr = 0; + *(buf + ptr++) = bucket; + while (bucket) + { + bucket = bucket->next; + *(buf + ptr++) = bucket; + } + while (ptr) + free(*(buf + --ptr)); + *(this->buckets + i) = NULL; + } + this->size = 0; + } +} + + +/** + * Calculate the buffer size need to marshal a hash table + * + * @param this The hash table + * @return The number of bytes to allocate to the output buffer + */ +size_t /**/__attribute__((const))/**/ hash_table_marshal_size(const hash_table_t* restrict this) +{ + (void) this; return 0; /* TODO */ +} + + +/** + * Marshals a hash table + * + * @param this The hash table + * @param data Output buffer for the marshalled data + */ +void /**/__attribute__((const))/**/ hash_table_marshal(const hash_table_t* restrict this, char* restrict data) +{ + (void) this; (void) data; /* TODO */ +} + + +/** + * Unmarshals a hash table + * + * @param this Memory slot in which to store the new hash table + * @param data In buffer with the marshalled data + * @return Non-zero one error, errno will be set accordingly. + * Destroy the list on error. + */ +int /**/__attribute__((const))/**/ hash_table_unmarshal(hash_table_t* restrict this, char* restrict data) +{ + (void) this; (void) data; return 0; /* TODO */ +} + diff --git a/src/libmdsserver/hash-table.h b/src/libmdsserver/hash-table.h new file mode 100644 index 0000000..8839a0d --- /dev/null +++ b/src/libmdsserver/hash-table.h @@ -0,0 +1,254 @@ +/** + * mds — A micro-display server + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ +#ifndef MDS_LIBMDSSERVER_HASH_TABLE_H +#define MDS_LIBMDSSERVER_HASH_TABLE_H + + +#include + + +/** + * Hash table entry + */ +typedef struct hash_entry +{ + /** + * A key + */ + void* key; + + /** + * The value associated with the key + */ + void* value; + + /** + * The truncated hash value of the key + */ + long hash; + + /** + * The next entry in the bucket + */ + struct hash_entry* next; + +} hash_entry_t; + + +/** + * Value lookup table based on hash value, that do not support `NULL` keys nor `NULL` values + */ +typedef struct hash_table +{ + /** + * The table's capacity, i.e. the number of buckets + */ + size_t capacity; + + /** + * Entry buckets + */ + hash_entry_t** buckets; + + /** + * When, in the ratio of entries comparied to the capacity, to grow the table + */ + float load_factor; + + /** + * When, in the number of entries, to grow the table + */ + size_t threshold; + + /** + * The number of entries stored in the table + */ + size_t size; + + /** + * Check whether two values are equal + * + * If this function pointer is `NULL`, the identity is used + * + * Be aware, this variable cannot be marshalled + * + * @param value_a The first value + * @param value_b The second value + * @return Whether the values are equals + */ + int (*value_comparator)(const void* value_a, const void* value_b); + + /** + * Check whether two keys are equal + * + * If this function pointer is `NULL`, the identity is used + * + * Be aware, this variable cannot be marshalled + * + * @param key_a The first key + * @param key_b The second key + * @return Whether the keys are equals + */ + int (*key_comparator)(const void* key_a, const void* key_b); + + /** + * Calculate the hash of a key + * + * If this function pointer is `NULL`, the identity hash is used + * + * Be aware, this variable cannot be marshalled + * + * @param key The key + * @return The hash of the key + */ + long (*hasher)(const void* key); + +} hash_table_t; + + + +/** + * Create a hash table + * + * @param this Memory slot in which to store the new hash table + * @param initial_capacity The initial capacity of the table + * @param load_factor The load factor of the table, i.e. when to grow the table + * @return Non-zero on error, `errno` will have been set accordingly + */ +int hash_table_create_fine_tuned(hash_table_t* restrict this, size_t initial_capacity, float load_factor); + +/** + * Create a hash table + * + * @param this:hash_table_t* Memory slot in which to store the new hash table + * @param initial_capacity:size_t The initial capacity of the table + * @return :int Non-zero on error, `errno` will have been set accordingly + */ +#define hash_table_create_tuned(this, initial_capacity) \ + hash_table_create_fine_tuned(this, initial_capacity, 0.75) + +/** + * Create a hash table + * + * @param this:hash_table_t* Memory slot in which to store the new hash table + * @return :int Non-zero on error, `errno` will have been set accordingly + */ +#define hash_table_create(this) \ + hash_table_create_tuned(this, 16) + +/** + * Clone a hash table + * + * @param this The hash table to clone + * @param out Memory slot in which to store the new hash table + * @return Non-zero on error, `errno` will have been set accordingly + */ +int hash_table_clone(const hash_table_t* restrict this, hash_table_t* restrict out); + +/** + * 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 + */ +void hash_table_destroy(hash_table_t* restrict this, int values, int keys); + +/** + * Check whether a value is stored in the table + * + * @param this The hash table + * @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)); + +/** + * Check whether a key is used in the table + * + * @param this The hash table + * @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)); + +/** + * 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 + */ +void* hash_table_get(const hash_table_t* restrict this, const void* restrict key); + +/** + * Add an entry to the table + * + * @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 + */ +void* hash_table_put(hash_table_t* restrict this, void* restrict key, void* restrict 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 + */ +void* hash_table_remove(hash_table_t* restrict this, const void* restrict key); + +/** + * Remove all entries in the table + * + * @param this The hash table + */ +void hash_table_clear(hash_table_t* restrict this); + +/** + * Calculate the buffer size need to marshal a hash table + * + * @param this The hash table + * @return The number of bytes to allocate to the output buffer + */ +size_t hash_table_marshal_size(const hash_table_t* restrict this) __attribute__((pure)); + +/** + * Marshals a hash table + * + * @param this The hash table + * @param data Output buffer for the marshalled data + */ +void hash_table_marshal(const hash_table_t* restrict this, char* restrict data); + +/** + * Unmarshals a hash table + * + * @param this Memory slot in which to store the new hash table + * @param data In buffer with the marshalled data + * @return Non-zero one error, errno will be set accordingly. + * Destroy the list on error. + */ +int hash_table_unmarshal(hash_table_t* restrict this, char* restrict data); + + +#endif + -- cgit v1.2.3-70-g09d2