/* =============================================================================
* 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 .
* ===========================================================================*/
#include
#include
#include "hashtable.h"
size_t hashtable_hash(const void *key, size_t size)
{
#if UINTPTR_MAX == 0xFFFFFFFF
size_t hash = 0x811C9DC5;
for (size_t i = 0; i < size; ++i) {
hash ^= *((uint8_t*)key + i);
hash *= 0x01000193;
}
return hash;
#elif UINTPTR_MAX == 0xFFFFFFFFFFFFFFFF
size_t hash = 0xcbf29ce484222325;
for (size_t i = 0; i < size; ++i) {
hash ^= *((uint8_t*)key + i);
hash *= 0x100000001b3;
}
return hash;
#else
#error Hashtable only supports 32-bit and 64-bit builds.
#endif
}
int hashtable_copy_key(void *dst, const void *src, size_t size)
{
memcpy(dst, src, size);
return 0;
}
int hashtable_compare_keys(const void *a, const void *b, size_t size)
{return memcmp(a, b, size);}
void *_hashtable_init(size_t *num_buckets, size_t num, size_t bucket_size,
size_t *num_values, int *ret_err)
{
void *ret = calloc(num, bucket_size);
if (!ret && num) {
if (ret_err)
*ret_err = 1;
return ret;
}
*num_buckets = num;
*num_values = 0;
if (ret_err)
*ret_err = 0;
return ret;
}
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)
{
if (!free_key)
goto out;
for (size_t i = 0; i < num_buckets; ++i) {
uint8_t *bucket = buckets + i * bucket_size;
for (unsigned int j = 0; j < HASHTABLE_BUCKET_SIZE; ++j) {
uint8_t *item = bucket + items_off + j * item_size;
if (*(item + reserved_off))
free_key(item + key_off);
}
}
out:
free(buckets);
memset(table, 0, table_size);
}
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_func)(const void *a, const void *b, size_t size),
int (*copy_key)(void *dst, const void *src, size_t size))
{
if (!hash) {
if (ret_err)
*ret_err = 1;
return buckets;
}
/* Resize if num_values / num_buckets >= 75% */
size_t load = (size_t)100 * (*num_values) / (*num_buckets *
HASHTABLE_BUCKET_SIZE);
if (load >= 75)
goto alloc_more1;
top: {}
size_t bucket = (size_t)(hash % (size_t)(*num_buckets));
uint8_t *bucket_ptr = buckets + bucket * bucket_size;
/* Check if the item exists */
for (unsigned int i = 0; i < HASHTABLE_BUCKET_SIZE; ++i) {
uint8_t *item = bucket_ptr + items_offset + i * item_size;
if (!*(item + reserved_off1))
continue;
if (!compare_func(key, item + key_off1, key_size)) {
if (ret_err)
*ret_err = 2;
return buckets;
}
}
for (unsigned int i = 0; i < HASHTABLE_BUCKET_SIZE; ++i) {
uint8_t *item = bucket_ptr + items_offset + i * item_size;
if (*(item + reserved_off1))
continue;
if (copy_key(item + key_off1, key, key_size)) {
if (ret_err)
*ret_err = 3;
return buckets;
}
memcpy(item + value_off1, value, value_size);
memcpy(item + hash_off1, &hash, sizeof(size_t));
*((item) + reserved_off1) = 1;
if (ret_err)
*ret_err = 0;
(*num_values)++;
return buckets;
}
alloc_more1: {}
size_t num_new_buckets = (*num_buckets) * 150 / 100;
if (num_new_buckets < 0)
num_new_buckets = 8;
alloc_more2: {}
uint8_t *new_buckets = calloc(num_new_buckets, bucket_size);
if (!new_buckets) {
if (ret_err)
*ret_err = 4;
return buckets;
}
for (size_t i = 0; i < (*num_buckets); ++i) {
uint8_t *old_bucket = buckets + i * bucket_size;
for (size_t j = 0; j < HASHTABLE_BUCKET_SIZE; ++j) {
uint8_t *old_item = old_bucket + items_offset + j * item_size;
if (!*(old_item + reserved_off1))
continue;
uint8_t *old_key_ptr = old_item + key_off1;
uint8_t *old_value_ptr = old_item + value_off1;
uint8_t *old_hash_ptr = old_item + hash_off1;
size_t old_hash;
memcpy(&old_hash, old_hash_ptr, sizeof(hash));
uint8_t *new_bucket = new_buckets + (old_hash % num_new_buckets) *
bucket_size;
int found_slot = 0;
for (size_t k = 0; k < HASHTABLE_BUCKET_SIZE; ++k) {
uint8_t *new_item = new_bucket + items_offset + k * item_size;
if (*(new_item + reserved_off1))
continue;
memcpy(new_item + key_off1, old_key_ptr, key_size);
memcpy(new_item + value_off1, old_value_ptr, value_size);
memcpy(new_item + hash_off1, old_hash_ptr, sizeof(hash));
*(new_item + reserved_off1) = 1;
found_slot = 1;
break;
}
if (found_slot)
continue;
num_new_buckets = num_new_buckets * 150 / 100;
free(new_buckets);
goto alloc_more2;
}
}
free(buckets);
buckets = new_buckets;
*num_buckets = num_new_buckets;
goto top;
}
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_func)(const void *a, const void *b, size_t size))
{
if (!num_buckets || !hash)
return 0;
size_t bucket_index = hash % num_buckets;
uint8_t *bucket = buckets + bucket_index * bucket_size;
for (size_t i = 0; i < HASHTABLE_BUCKET_SIZE; ++i) {
uint8_t *item = bucket + items_offset + i * item_size;
if (!*(item + reserved_offset))
continue;
if (!compare_func(item + key_offset, key, key_size))
return item + value_offset;
}
return 0;
}
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))
{
if (!hash || !bucket_size)
return;
size_t bucket_index = hash % num_buckets;
uint8_t *bucket = buckets + bucket_index * bucket_size;
for (unsigned int i = 0; i < HASHTABLE_BUCKET_SIZE; ++i) {
uint8_t *item = bucket + items_off + i * item_size;
if (!*(item + reserved_off))
continue;
if (compare_keys(item + key_off, key, key_size))
continue;
*(item + reserved_off) = 0;
if (free_key)
free_key(item + key_off);
(*num_values)--;
return;
}
}