Generic C string->any hashmap

map.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "map.h"

/* Hash function */
static uint64_t fnv1a(const char * c)
{
    uint64_t h = 0xcbf29ce484222325; /* FNV offset basis */
    for (; *c != '\0'; ++c)
    {
        h ^= *c;
        h *= 0x100000001b3; /* FNV prime */
    }

    return h;
}

static char * _strdup(char * c)
{
    char * r;
    size_t n = strlen(c)+1;
    r = MAP_MALLOC(n);
    memcpy(r, c, n+1);
    return r;
}

void map_init(Map * m)
{
    m->k   = MAP_CALLOC(16, sizeof(char *));
    m->v   = MAP_MALLOC(16 * sizeof(void *));
    m->h   = MAP_MALLOC(16 * sizeof(uint64_t));
    m->c   = 16;
    m->n   = 0;
}

/* Resize map */
void grow(Map * m)
{
    char ** tmp_k;
    void ** tmp_v;
    uint64_t * tmp_h;
    size_t i;

    m->c *= 1.5;

    tmp_k = calloc(m->c, sizeof(char *));
    tmp_v = malloc(m->c * sizeof(void *));
    tmp_h = malloc(m->c * sizeof(uint64_t));
    for (i = 0; i < m->n; ++i)
    {
        size_t j;

        j = m->h[i] % m->c;
        while (tmp_k[j]) j = (j+1) % m->c;
        
        tmp_k[j] = m->k[i];
        tmp_v[j] = m->v[i];
        tmp_h[j] = m->h[i];
    }

    MAP_FREE(m->k);
    MAP_FREE(m->v);
    MAP_FREE(m->h);

    m->k = tmp_k;
    m->v = tmp_v;
    m->h = tmp_h;
}

void map_set(Map * m, char * k, void * v)
{
    size_t i;   /* Index into map */
    uint64_t h; /* Hash value */

    if (++m->n >= m->c) grow(m);

    h = fnv1a(k);
    i = h % m->c;

    /* Skip to next free space */
    while (m->k[i]) i = (i+1) % m->c;

    m->k[i]   = _strdup(k);
    m->v[i]   = v;
    m->h[i]   = h;
}

void * map_get(Map * m, char * k)
{
    size_t i;
    size_t i_start;
    uint64_t h;

    h = fnv1a(k);
    i = h % m->c;
    if (!m->k[i]) return NULL;

iter:
    /* Find item, or return NULL */
    i_start = i;
    while (m->h[i] != h)
    {
        i = (i+1) % m->c;
        if (i == i_start || !m->k[i]) return NULL;
    }

    /* Hash matches but the key doesn't */
    if (__builtin_expect(!!strcmp(m->k[i], k), 1))
    {
        ++i;
        goto iter;
    }

    return m->v[i];
}

void map_free(Map * m)
{
    MAP_FREE(m->k);
    MAP_FREE(m->v);
    MAP_FREE(m->h);
}

map.h

#ifndef MAP_H
#define MAP_H

#ifndef MAP_MALLOC
#define MAP_MALLOC malloc
#endif

#ifndef MAP_REALLOC
#define MAP_REALLOC realloc
#endif

#ifndef MAP_CALLOC
#define MAP_CALLOC calloc
#endif

#ifndef MAP_FREE
#define MAP_FREE free
#endif

#include <stdint.h>
#include <stddef.h>

typedef struct
{
    char    ** k; /* Keys - 0 if empty*/
    void    ** v; /* Values */
    uint64_t * h; /* Key hashes */

    size_t c; /* Capacity */
    size_t n; /* Current size */
} Map;

void map_init(Map *);
void map_set(Map *, char *, void *);
void * map_get(Map *, char *);
void map_free(Map * m);

#endif