diff options
Diffstat (limited to '')
| -rw-r--r-- | src/libmdsserver/hash-table.h | 254 |
1 files changed, 254 insertions, 0 deletions
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 <http://www.gnu.org/licenses/>. + */ +#ifndef MDS_LIBMDSSERVER_HASH_TABLE_H +#define MDS_LIBMDSSERVER_HASH_TABLE_H + + +#include <stdlib.h> + + +/** + * 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 + |