/* =============================================================================
* This file is part of Kuvis' Hashtable.
*
* Kuvis' Hashtable 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.
*
* Kuvis' Hashtable 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
* Kuvis' Hashtable. If not, see .
* ===========================================================================*/
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include
#include
#define HASHTABLE_BUCKET_SIZE 4
/* =============================================================================
* hashtable()
* Declare a new hashtable variable.
*
* PARAMETERS
* key_type: the type of the key used by this table.
* value_type: the type of the values contained by this table.
*
* EXAMPLE
* hashtable(uint32_t, void*) my_table;
* ===========================================================================*/
#define hashtable(key_type, value_type) \
struct { \
struct { \
struct { \
key_type _key; \
value_type _value; \
size_t _hash; \
uint8_t _reserved; \
} _items[HASHTABLE_BUCKET_SIZE]; \
} *_buckets; \
size_t _num_buckets; \
size_t _num_values; \
}
/* =============================================================================
* hashtable_init()
* Initialize a hashtable.
*
* PARAMETERS
* table: The hashtable to initialize.
* size: Number of initial buckets.
* ret_err: A pointer to an int two which a potential error code is written. Can
* be NULL. A value of 0 indicates success.
*
* RETURN VALUE
* void
* ===========================================================================*/
#define hashtable_init(table, size, ret_err) \
((void)(table._buckets = _hashtable_init(&table._num_buckets, (size), \
sizeof(table._buckets[0]), &table._num_values, (ret_err))))
#define hashtable_num_buckets(table) \
(table._num_buckets)
#define hashtable_num_values(table) \
(table._num_values)
/* =============================================================================
* hashtable_destroy()
* Free resources used by a hashtable.
*
* PARAMETERS
* table: The hashtable to destroy.
* free_key: A pointer to a function to free keys of entries in case the keys
* were dynamically allocated using a custom key copying function.
* Can be NULL. Must have the following signature:
* void free_key(void *key);
*
* RETURN VALUE
* void
* ===========================================================================*/
#define hashtable_destroy(table, free_key) \
_hashtable_destroy(&table, sizeof(table), (uint8_t*)table._buckets, \
free_key, table._num_buckets, sizeof(table._buckets[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0], \
&table._buckets[0]), sizeof(table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._reserved, \
&table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._key, \
&table._buckets[0]._items[0]))
/* =============================================================================
* hashtable_insert()
* Insert a key-hash-value combination into the table. Any hash function that
* returns a size_t may be used to generate the hash.
* This macro is for fixed-size key types - for variable length types such as
* strings, see hashtable_insert_ext().
*
* PARAMETERS
* table: The hashtable
* key: The key used to compute the hash. Must refer to an existing
* variable of the correct type.
* hash: The hash computed from the key. Must be of type size_t.
* value: The value to be inserted. Must refer to an existing variable of the
* correct type.
* ret_err: A pointer to an int to write a return code to. NULL if none. A value
* of 0 indicates success.
*
* RETURN VALUE
* void
*
* EXAMPLE
* size_t hash_u32(uint32_t key); // Custom hash function
* hashtable(uint32_t, void *) my_table; // The table to insert into
* ...
* uint32_t key = 324;
* size_t hash = hash_u32(key);
* void *value = NULL;
* hashtable_insert(my_table, key, hash, &value, NULL);
* ===========================================================================*/
#define hashtable_insert(table, key, hash, value, ret_err) \
hashtable_insert_ext(table, key, hash, value, \
hashtable_compare_keys, hashtable_copy_key, ret_err)
/* =============================================================================
* hashtable_insert_ext()
* Similar to hashtable_insert(), but uses custom key comparison and key
* duplication functions.
*
* PARAMETERS
* table: The hashtable
* key: The key used to compute the hash. Must refer to an existing
* variable of the correct type.
* hash: The hash computed from the key. Must be of type size_t.
* value: The value to be inserted. Must refer to an existing variable
* of the correct type.
* compare_keys: A pointer to a function that checks if keys are equal. A
* return value of 0 indicates the keys are equal. The function
* signature must be as follows:
* int compare_keys(const void *a, const void *b, size_t size);
* hashtable_insert() uses the function
* hashtable_compare_keys().
* copy_key: A pointer to a function that copies the key passed to the
* macro. The return value must be 0 on success. The signature
* must be as follows:
* int copy_key(void *dst, const void *src, size_t size);
* hashtable_insert() uses the function hashtable_copy_keys().
* ret_err: A pointer to an int to write a return code to. NULL if none.
* A value of 0 indicates success.
*
* RETURN VALUE
* void
* ===========================================================================*/
#define hashtable_insert_ext(table, key, hash, value, \
compare_keys, copy_key, ret_err_) \
((void)(table._buckets = _hashtable_insert((ret_err_), \
(uint8_t*)table._buckets, &table._num_buckets, &table._num_values, \
sizeof(*table._buckets), sizeof(table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0], \
&table._buckets[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._key, \
&table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._value, \
&table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._hash, \
&table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._reserved, \
&table._buckets[0]._items[0]), \
&key, sizeof(key), hash, &value, sizeof(value), compare_keys, \
copy_key)))
/* =============================================================================
* hashtable_find()
* Find a value by key in the given hashtable.
*
* PARAMETERS
* table: The hashtable to find from
* key: The key used to compute the hash. Must refer to an existing variable
* of the correct type.
* hash: The hash computed from the key. Must be of type size_t.
*
* RETURN VALUE
* A void * to the value, or NULL if value is not found.
*
* EXAMPLE
* size_t hash_u32(uint32_t key); // Custom hash function
* hashtable(uint32_t, void *) my_table; // The table to find values from
* ...
* uint32_t key = 324;
* void **value = hashtable_find(my_table, key, hash_u32(key));
* if (value) {
* ... Value found ...
* }
* ===========================================================================*/
#define hashtable_find(table, key, hash) \
hashtable_find_ext(table, key, hash, hashtable_compare_keys)
/* =============================================================================
* hashtable_find_ext()
* Like hashtable_find(), but uses a custom key comparison function.
*
* PARAMETERS
* table: The hashtable to find from
* key: The key used to compute the hash. Must refer to an existing
* variable of the correct type.
* hash: The hash computed from the key. Must be of type size_t.
* compare_keys: A pointer to a function to compare two keys with each other.
* Must return 0 if keys are equal. Signature must be as
* follows:
* int compare_keys(const void *a, const void *b, size_t size);
*
* RETURN VALUE
* A void * to the value, or NULL if value is not found.
* ===========================================================================*/
#define hashtable_find_ext(table, key, hash, compare_keys) \
_hashtable_find(&key, sizeof(key), \
hash, (uint8_t*)table._buckets, table._num_buckets, \
sizeof(table._buckets[0]), sizeof(table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0], \
&table._buckets[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._key, \
&table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._value, \
&table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._reserved, \
&table._buckets[0]._items[0]), compare_keys)
/* =============================================================================
* hashtable_erase()
* Erase a key-value pair from a hashtable.
*
* PARAMETERS
* table: The hashtable to erase from.
* key: The key used to compute the hash. Must refer to an existing variable
* of the correct type.
* hash: The hash computed from the key. Must be of type size_t.
*
* RETURN VALUE
* void
*
* EXAMPLE
* size_t hash_u32(uint32_t key); // Custom hash function
* hashtable(uint32_t, int) my_table; // The table to erase from
* ...
* uint32_t key = 324;
* hashtable_erase(my_table, key, hash_u32(key));
* ===========================================================================*/
#define hashtable_erase(table, key, hash) \
hashtable_erase_ext(table, key, hash, hashtable_compare_keys, 0)
/* =============================================================================
* hashtable_erase_ext()
* Like hashtable_erase(), but uses custom key comparison and key freeing
* functions.
*
* PARAMETERS
* table: The hashtable to erase from.
* key: The key used to compute the hash. Must refer to an existing
* variable of the correct type.
* hash: The hash computed from the key. Must be of type size_t.
* compare_keys: A pointer to a function to check if two keys are equal. Must
* return 0 if keys are equal. Must have the following
* signature:
* int compare_keys(const void *a, const void *b, size_t size);
* free_key: A pointer to a function to free a key when a key-value
* combination is erased. This can be used if a custom key was
* dynamically allocated using a custom copy_key function
* during insertion. If this parameter is NULL, no function is
* called to free the key. The function signature must be as
* follows:
* void free_key(void *key);
*
* RETURN VALUE
* void
* ===========================================================================*/
#define hashtable_erase_ext(table, key, hash, compare_keys, free_key) \
_hashtable_erase((uint8_t*)table._buckets, table._num_buckets, \
&table._num_values, &key, sizeof(key), \
hash, \
sizeof(table._buckets[0]), sizeof(table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0], &table._buckets[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._key, \
&table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._value, \
&table._buckets[0]._items[0]), \
_hashtable_ptr_offset(&table._buckets[0]._items[0]._reserved, \
&table._buckets[0]._items[0]), \
compare_keys, free_key)
/* =============================================================================
* hashtable_hash()
* A default hash function. Uses the 32 bit or 64 bit fnv-a1 algorithm depending
* on architecture.
* ===========================================================================*/
size_t hashtable_hash(const void *key, size_t size);
/* =============================================================================
* hashtable_compare_keys()
* The default key comparison function. Compares values like memcmp() does.
* ===========================================================================*/
int hashtable_compare_keys(const void *a, const void *b, size_t size);
/* =============================================================================
* hashtable_copy_key()
* The default key copying function. Works similarly to memcpy().
* ===========================================================================*/
int hashtable_copy_key(void *dst, const void *src, size_t size);
#define _hashtable_ptr_offset(ptr, base) \
((size_t)((uint8_t*)(ptr) - (uint8_t*)(base)))
void *_hashtable_init(size_t *num_buckets, size_t num,
size_t bucket_size, size_t *num_values, int *ret_err);
void _hashtable_destroy(void *table, size_t table_size, uint8_t *buckets,
void (*free_key)(void *), size_t num_buckets, size_t bucket_size,
size_t items_off, size_t item_size, size_t reserved_off, size_t key_off);
void *_hashtable_insert(int *ret_err, uint8_t *buckets, size_t *num_buckets,
size_t *num_values, size_t bucket_size, size_t item_size,
size_t items_offset, size_t key_off1, size_t value_off1, size_t hash_off1,
size_t reserved_off1, void *key, size_t key_size, size_t hash, void *value,
size_t value_size,
int (*compare_keys)(const void *a, const void *b, size_t size),
int (*copy_key)(void *dst, const void *src, size_t size));
void *_hashtable_find(void *key, size_t key_size, size_t hash,
uint8_t *buckets, size_t num_buckets, size_t bucket_size, size_t item_size,
size_t items_offset, size_t key_offset, size_t value_offset,
size_t reserved_offset,
int (*compare_keys)(const void *a, const void *b, size_t size));
void _hashtable_erase(uint8_t *buckets, size_t num_buckets, size_t *num_values,
void *key, size_t key_size, size_t hash, size_t bucket_size,
size_t item_size, size_t items_off, size_t key_off, size_t value_off,
size_t reserved_off,
int (*compare_keys)(const void *a, const void *b, size_t size),
void (*free_key)(void *key));
#endif