c string hash map

cstrmap.h

/*
 * fixed-size string hashmap (FNV-1)
 */
#ifndef __CSTRMAP_H__
#define __CSTRMAP_H__


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


/* thanks to: http://www.isthe.com/chongo/src/fnv/hash_64.c */
#define _FNV_64_OFFSET 14695981039346656037UL


typedef struct {
	const char *key;
	void       *val;
} CstrMapItem;

typedef struct {
	size_t       size;
	CstrMapItem *items;
} CstrMap;

int          cstrmap_init(CstrMap *c, size_t size);
void         cstrmap_deinit(CstrMap *c);
CstrMapItem *cstrmap_get(CstrMap *c, const char key[]);


/*
 * private
 */
static uint64_t _hash_key(const char key[]);


/*
 * IMPL
 */
static uint64_t
_hash_key(const char key[])
{
	uint64_t hval = _FNV_64_OFFSET;
	for (const char *p = key; *p != '\0'; p++) {
		hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) +
			(hval << 8) + (hval << 40);
		hval ^= (uint64_t)*p;
	}

	return hval;
}


int
cstrmap_init(CstrMap *c, size_t size)
{
	assert(size != 0);
	void *const items = calloc(size, sizeof(CstrMapItem));
	if (items == NULL)
		return -ENOMEM;

	c->size = size;
	c->items = items;
	return 0;
}


void
cstrmap_deinit(CstrMap *c)
{
	free(c->items);
}


CstrMapItem *
cstrmap_get(CstrMap *c, const char key[])
{
	const size_t size = c->size;
	size_t index = (size_t)(_hash_key(key) & (size - 1));
	CstrMapItem *item = &c->items[index];

	for (size_t i = 0; (i < size) && (item->key != NULL); i++) {
		if (strcmp(item->key, key) == 0)
			return item;

		index = (index + 1) % size;
		item = &c->items[index];
	}

	if (item->key != NULL)
		return NULL;

	item->key = key;
	return item;
}


#endif

test.c

#include <stdio.h>

#include "cstrmap.h"


static void
print_val(CstrMap *map, const char key[])
{
	CstrMapItem *const item = cstrmap_get(map, key);
	if (item == NULL)
		return;

	if (item->val == NULL)
		return;

	printf("%d\n", *(int *)item->val);
}


static void
set_val(CstrMap *map, const char key[], int *val)
{
	CstrMapItem *const item = cstrmap_get(map, key);
	if (item == NULL)
		return;

	item->val = val;
}


static void
del_item(CstrMap *map, const char key[])
{
	CstrMapItem *const item = cstrmap_get(map, key);
	if (item == NULL)
		return;

	item->key = NULL;
	item->val = NULL;
}


int
main(void)
{
	const char *keys[] = {
		"000000000",
		"111111111",
		"222222222",
		"333333333",
		"444444444",
		"555555555",
	};

	int items[100] = {
		1,2,3,4,5,6,
	};
	CstrMap map;


	if (cstrmap_init(&map, 8) < 0)
		return 1;

	set_val(&map, keys[0], &items[0]);
	set_val(&map, keys[1], &items[1]);
	set_val(&map, keys[2], &items[2]);

	// delete map
	del_item(&map, keys[0]);

	set_val(&map, keys[3], &items[3]);
	set_val(&map, keys[4], &items[4]);
	set_val(&map, keys[5], &items[5]);

	// delete map
	del_item(&map, keys[3]);

	print_val(&map, keys[0]);
	print_val(&map, keys[1]);
	print_val(&map, keys[2]);
	print_val(&map, keys[3]);
	print_val(&map, keys[4]);
	print_val(&map, keys[5]);

	cstrmap_deinit(&map);
	return 0;
}