/** * mds — A micro-display server * Copyright © 2014, 2015, 2016 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 "table-common.h" #define HASH_TABLE_T_VERSION 0 /** * Hash table entry */ typedef struct hash_entry { /** * A key */ size_t key; /** * The value associated with the key */ size_t value; /** * The truncated hash value of the key */ size_t 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 */ 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 */ compare_func* value_comparator; /** * Check whether two keys are equal * * If this function pointer is `NULL`, the identity is used * * Be aware, this variable cannot be marshalled */ compare_func* key_comparator; /** * 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 */ hash_func* hasher; } 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 */ __attribute__((nonnull)) 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.75f) /** * 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) /** * Release all resources in a hash table, should * be done even if construction fails * * @param this The hash table * @param keys_freer Function that frees a key, `NULL` if keys should not be freed * @param values_freer Function that frees a value, `NULL` if value should not be freed */ __attribute__((nonnull(1))) void hash_table_destroy(hash_table_t* restrict this, free_func* key_freer, free_func* value_freer); /** * 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 */ __attribute__((pure, nonnull)) int hash_table_contains_value(const hash_table_t* restrict this, size_t value); /** * Check whether a key is used in the table * * @param this The hash table * @param key The key * @return Whether the key is used */ __attribute__((pure, nonnull)) int hash_table_contains_key(const hash_table_t* restrict this, size_t key); /** * 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, 0 if the key was not used */ __attribute__((pure, nonnull)) size_t hash_table_get(const hash_table_t* restrict this, size_t key); /** * Look up an entry in the table * * @param this The hash table * @param key The key associated with the value * @return The entry associated with the key, `NULL` if the key was not used */ __attribute__((pure, nonnull)) hash_entry_t* hash_table_get_entry(const hash_table_t* restrict this, size_t 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, 0 if the key was not used. * 0 will also be returned on error, check the `errno` variable. */ __attribute__((nonnull)) 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, 0 if the key was not used */ __attribute__((nonnull)) size_t hash_table_remove(hash_table_t* restrict this, size_t key); /** * Remove all entries in the table * * @param this The hash table */ __attribute__((nonnull)) void hash_table_clear(hash_table_t* restrict this); /** * Wrapper for `for` keyword that iterates over entry element in a hash table * * @param this:hash_table_t The hash table * @param i:size_t The variable to store the buckey index in at each iteration * @param entry:hash_entry_t* The variable to store the entry in at each iteration */ #define foreach_hash_table_entry(this, i, entry) \ for (i = 0; i < (this).capacity; i++) \ for (entry = (this).buckets[i]; entry != NULL; entry = entry->next) /** * 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 */ __attribute__((pure, nonnull)) size_t hash_table_marshal_size(const hash_table_t* restrict this); /** * Marshals a hash table * * @param this The hash table * @param data Output buffer for the marshalled data */ __attribute__((nonnull)) 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 * @param remapper Function that translates values, `NULL` if not translation takes place * @return Non-zero on error, `errno` will be set accordingly. * Destroy the table on error. */ __attribute__((nonnull(1, 2))) int hash_table_unmarshal(hash_table_t* restrict this, char* restrict data, remap_func* remapper); #endif