Hash Table in C11

table.c

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "table.h"

#define NORMALIZE(HASH) (HASH % table->len) - 1

static uint64_t fnv1a(const char* data, size_t len);

struct table_t {
    struct item_t** list;
    size_t cap, len;
};

struct item_t {
    void* data;
    char* key;
};

static struct item_t* item_new(char* key, void* data) {
    struct item_t* item = malloc(sizeof(struct item_t));
    item->key = key;
    item->data = data;
    return item;
}

Table* table_new(size_t size) {
    size = ((size + 1) / 2) * 2;  // keep the size to be multiple of 2
    Table* table = calloc(size, sizeof(void*));
    table->cap = size;
    table->len = size;
    return table;
}

int table_put(Table* table, char* key, size_t len, void* value) {
    if (table->cap < 1) {
        return -1;  // table is full, no cap left
    }
    uint64_t hashed = NORMALIZE(fnv1a(key, len));
    if (table->list[hashed]) {  // existed or collision
        size_t last = table->len, i = hashed;
        while (1) {  // linear probing
            i++;
            if (i < last) {
                if (!table->list[i]) {
                    hashed = i;
                    break;
                }
                continue;
            }
            i = -1;  // wrap around
            last = hashed;
        }
    }
    table->list[hashed] = item_new(key, value);  // store the value
    table->cap--;                                // decrase the capacity
    return 0;
}

void* table_take(Table* table, char* key, size_t len) {
    if (table->cap == table->len) {
        return NULL;  // table empty
    }
    uint64_t hashed = NORMALIZE(fnv1a(key, len));
    if (strcmp(table->list[hashed]->key, key)) {
        size_t i = hashed, last = table->len;
        while (1) {  // linear search
            i++;
            if (i < last) {
                if (!strcmp(table->list[i]->key, key)) {
                    hashed = i;
                    break;
                }
                continue;
            }
            i = -1;  // wrap around
            last = hashed;
        }
    }
    return table->list[hashed]->data;
}

void* table_delete(Table* table, char* key, size_t len) {
    if (table->cap == table->len) {
        return NULL;  // table empty
    }
    uint64_t hashed = NORMALIZE(fnv1a(key, len));
    if (strcmp(table->list[hashed]->key, key)) {
        size_t i = hashed, last = table->len;
        while (1) {  // linear search
            i++;
            if (i < last) {
                if (!strcmp(table->list[i]->key, key)) {
                    hashed = i;
                    break;
                }
                continue;
            }
            i = -1;  // wrap around
            last = hashed;
        }
    }
    void* data = table->list[hashed]->data;
    table->cap++;  // increase if data is actually exists
    free(table->list[hashed]->key);
    free(table->list[hashed]);
    table->list[hashed] = NULL;  // remove item
    return data;
}

// reference https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
static uint64_t fnv1a(const char* data, size_t len) {
    const uint64_t FNV_prime = 0x00000100000001B3;
    const uint64_t FNV_offset_basis = 0xcbf29ce484222325;

    uint64_t hash = FNV_offset_basis;
    for (size_t i = 0; i < len; ++i) {
        hash ^= data[i];
        hash *= FNV_prime;
    }
    return hash;
}

table.h

#include <stdlib.h>

/*
 * use must allocated the key on their own.
 * the key must be valid string and allocated on the heap.
 * using constant string or local variable, undefined behavior.
 * user responsible to freed the data only.
 */

typedef struct table_t Table;

Table* table_new(size_t size);
int table_put(Table* table, char* key, size_t len, void* value);
void* table_take(Table* table, char* key, size_t len);
void* table_delete(Table* table, char* key, size_t len);