hash_table.c

#include <kiba/containers/hash_table.h>
 
#include <kiba/core/hash.h>
#include <kiba/core/log.h>
#include <kiba/core/memory.h>
 
#include <string.h>  // TODO add memcmp to core lib
 
hash_table_entry *hash_table_find_entry(hash_table *table, const void *key, usize key_size);
 
b8 hash_table_create(hash_table *table, usize initial_capacity, f64 max_load, allocator *alloc) {
    KB_ASSERT(table != KB_NULL, "table to populate must be a valid pointer");
    KB_ASSERT(alloc != KB_NULL, "must be given valid allocator pointer");
    KB_ASSERT(initial_capacity != 0, "initial capacity must not be 0");
    KB_ASSERT(max_load <= 1.0 && max_load > 0.0, "max load must be in range (0, 1] but is {f64}", max_load);
    table->size     = 0;
    table->capacity = initial_capacity;
    table->max_load = max_load;
    table->alloc    = alloc;
    table->data     = allocator_allocate(alloc, initial_capacity * sizeof(hash_table_entry));
    return table->data != KB_NULL;
}
 
void hash_table_destroy(hash_table *table) {
    KB_ASSERT(table != KB_NULL && table->alloc != KB_NULL && table->data != KB_NULL,
              "table must have initialized state");
    allocator_free(table->alloc, table->data);
    memory_zero(table, sizeof(hash_table));
}
 
b8 hash_table_set(hash_table *table, const void *key, usize key_size, uptr value) {
    hash_table_entry *new_entry = hash_table_find_entry(table, key, key_size);
    if (new_entry->key_size == 0) {
        ++table->size;
        if ((f64) table->size / (f64) table->capacity >= table->max_load) {
            // reached max load -> migrate to larger hash table
            hash_table new_table;
            if (!hash_table_create(&new_table, table->capacity * 2, table->max_load, table->alloc)) {
                KB_ERROR("could not expand hash table");
                return false;
            }
            hash_table_for_each(*table) {
                KB_ASSERT(hash_table_set(&new_table, entry->key, entry->key_size, entry->value),
                          "migration of old values must work");
            }
            KB_ASSERT(table->size == new_table.size + 1, "size between tables must not change");
            allocator_free(table->alloc, table->data);
            table->capacity = new_table.capacity;
            table->data     = new_table.data;
        }
    }
    new_entry->key_size = key_size;
    new_entry->key      = (void *) key;
    new_entry->value    = value;
    return true;
}
 
b8 hash_table_get(hash_table *table, const void *key, usize key_size, void *value_ptr) {
    hash_table_entry *entry = hash_table_find_entry(table, key, key_size);
    if (entry->key_size != 0) {
        memory_copy(value_ptr, &entry->value, sizeof(uptr));
        return true;
    }
    return false;
}
 
hash_table_entry *hash_table_find_entry(hash_table *table, const void *key, usize key_size) {
    KB_ASSERT(table != KB_NULL && table->alloc != KB_NULL && table->data != KB_NULL,
              "table must have initialized state");
    KB_ASSERT(key != KB_NULL && key_size != 0, "a valid key must be provided");
    u64               hash  = hash_fnv_1a(key, key_size);
    usize             index = hash % table->capacity;
    hash_table_entry *entry = table->data + index;
    while (entry->key_size != 0
           && !(key_size == entry->key_size && hash == entry->hash && memcmp(key, entry->key, key_size) == 0)) {
        index = (index + 1) % table->capacity;
        entry = table->data + index;
    }
    entry->hash = hash;
    return entry;
}