Hash table in C

dict.c

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

#include "set.h"
#include "dict.h"

int
dict_eq(const void *x, const void *y)
{
	const struct keyvalue *a = x, *b = y;
	return !strcmp(a->key, b->key);
}

uint32_t
dict_hash(const void *x)
{
	const struct keyvalue *a = x;
	const char *s = a->key;
	/* djb 2 */
	uint32_t hash = 5381;
	int c;
	while (c = *s++) {
		hash = ((hash << 5) + hash) + c;
	}
	return hash;
}

long long *
dict_lookup(const struct set *d, const char *key)
{
	struct keyvalue tmp = {key, 0};
	struct keyvalue *p = set_contains(d, &tmp);
	if (!p)
		return NULL;
	return &p->value;
}

int
main(void)
{
	size_t cap = 5;
	size_t sz = set_size(cap);
	struct keyvalue kv;

	if (!sz) {
		fprintf(stderr, "Bad capacity\n");
		return 1;
	}

	struct keyvalue *values = calloc(cap, sizeof(*values));
	struct set *s = malloc(sz);
	set_init(s, cap, sizeof(*values), values, dict_eq, dict_hash);

	kv.key = "hello";
	kv.value = 10;
	set_insert(s, &kv);

	printf("%lld\n", *dict_lookup(s, "hello"));
	return 0;
}

dict.h

struct keyvalue {
	const char *key;
	long long value;
};

int dict_eq(const void *x, const void *y);
uint32_t dict_hash(const void *x);
long long *dict_lookup(const struct set *d, const char *key);

Makefile

.PHONY: default
default: dict
	./dict

dict: dict.c set.o

test: test.c set.o

set.o: set.c set.h

.PHONY: clean
clean:
	rm -f test *.o

set.c

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

#include "set.h"

#define CELL_EMPTY 0xFFFFFFFF
#define CELL_FINAL 0x80000000
#define CELL_MAX   0x7FFFFFFF

size_t
set_size(size_t capacity)
{
	if ((SIZE_MAX - sizeof(struct set)) / sizeof(uint32_t) < capacity)
		return 0;
	return sizeof(struct set) + capacity * sizeof(uint32_t);
}

void
set_init(
	struct set *s,
	size_t capacity,
	size_t value_sz,
	void *value_buf,
	int (*eq)(const void *, const void *),
	uint32_t (*hash)(const void *)
) {
	s->len = 0;
	s->capacity = capacity;
	s->value_sz = value_sz;
	s->value_buf = value_buf;
	s->eq = eq;
	s->hash = hash;
	memset(s->cells, 0xFF, capacity * sizeof(uint32_t));
}

void
set_insert(struct set *s, const void *x)
{
	uint32_t h = s->hash(x) % s->capacity;
	if (s->cells[h] != CELL_EMPTY) {
		while (s->cells[h] != CELL_FINAL) {
			h = s->cells[h];
		}
		s->cells[h] = (h + 1) % s->capacity;
		while (s->cells[s->cells[h]] != CELL_EMPTY) {
			s->cells[h] = (s->cells[h] + 1) % s->capacity;
		}
		h = s->cells[h];
	}
	s->cells[h] = CELL_FINAL;
	memcpy(s->value_buf + s->value_sz * h, x, s->value_sz);
	s->len++;
}

void *
set_contains(const struct set *s, const void *x)
{
	uint32_t h = s->hash(x) % s->capacity;
	if (s->cells[h] == CELL_EMPTY)
		return NULL;
	do {
		void *p = s->value_buf + s->value_sz * h;
		if (s->eq(p, x))
			return p;
		h = s->cells[h];
	} while (h != CELL_FINAL);
	return NULL;
}

set.h

struct set {
	size_t len;
	size_t capacity;
	size_t value_sz;
	void *value_buf;
	int (*eq)(const void *, const void *);
	uint32_t (*hash)(const void *);
	uint32_t cells[];
};

size_t set_size(size_t capacity);

void set_init(
	struct set *s,
	size_t capacity,
	size_t value_sz,
	void *value_buf,
	int (*eq)(const void *, const void *),
	uint32_t (*hash)(const void *)
);

void set_insert(struct set *s, const void *x);

void *set_contains(const struct set *s, const void *x);

test.c

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

#include "set.h"

#define CELL_EMPTY 0xFFFFFFFF
#define CELL_FINAL 0x80000000
#define CELL_MAX   0x7FFFFFFF

#define log(...) fprintf(stderr, __VA_ARGS__)

int
int_eq(const void *x, const void *y)
{
	const int *a = x, *b = y;
	return *a == *b;
}

uint32_t
int_hash(const void *x)
{
	const int *a = x;
	return (uint32_t) *a;
}

void
debug(const struct set *s)
{
	for (size_t i = 0; i < s->capacity; ++i) {
		int *x = (int *)(s->value_buf + i * s->value_sz);
		printf("%d | ", *x);
	}
	printf("\n");
	for (size_t i = 0; i < s->capacity; ++i) {
		int a = s->cells[i] == CELL_FINAL ? -1 : (int)s->cells[i];
		printf("%d | ", a);
	}
	printf("\n\n");
}

int
main(void)
{
	size_t cap = 5;
	size_t sz = set_size(cap);

	if (!sz) {
		fprintf(stderr, "Bad capacity\n");
		return 1;
	}

	int *values = calloc(cap, sizeof(*values));
	struct set *s = malloc(sz);
	set_init(s, cap, sizeof(*values), values, int_eq, int_hash);

	int test_values[8] = {0};
	uint32_t test_cells[8];
	memset(test_cells, 0xFF, sizeof(test_cells));
	int n;

	assert(!memcmp(values, test_values, cap * sizeof(*values)));
	assert(!memcmp(s->cells, test_cells, cap * sizeof(*s->cells)));

	assert(!set_contains(s, &n));

	/* Test inserting 7 */
	n = 7;
	set_insert(s, &n);
	test_values[2] = 7; test_cells[2] = CELL_FINAL;
	assert(!memcmp(values, test_values, cap * sizeof(*values)));
	assert(!memcmp(s->cells, test_cells, cap * sizeof(*s->cells)));
	assert(set_contains(s, &n));

	/* Test inserting 2 */
	n = 2;
	set_insert(s, &n);
	test_values[2] = 7; test_cells[2] = 3;
	test_values[3] = 2;  test_cells[3] = CELL_FINAL;
	assert(!memcmp(values, test_values, cap * sizeof(*values)));
	assert(!memcmp(s->cells, test_cells, cap * sizeof(*s->cells)));
	assert(set_contains(s, &n));

	/* Test inserting 3 */
	n = 3;
	set_insert(s, &n);
	test_values[2] = 7; test_cells[2] = 3;
	test_values[3] = 2;  test_cells[3] = 4;
	test_values[4] = 3;  test_cells[4] = CELL_FINAL;
	assert(!memcmp(values, test_values, cap * sizeof(*values)));
	assert(!memcmp(s->cells, test_cells, cap * sizeof(*s->cells)));
	assert(set_contains(s, &n));

	/* Test inserting 4 and 11 */
	n = 4;
	set_insert(s, &n);
	n = 11;
	set_insert(s, &n);
	test_values[0] = 4; test_cells[0] = CELL_FINAL;
	test_values[1] = 11; test_cells[1] = CELL_FINAL;
	test_values[2] = 7; test_cells[2] = 3;
	test_values[3] = 2;  test_cells[3] = 4;
	test_values[4] = 3;  test_cells[4] = 0;
	assert(!memcmp(values, test_values, cap * sizeof(*values)));
	assert(!memcmp(s->cells, test_cells, cap * sizeof(*s->cells)));
	n = 7; assert(set_contains(s, &n));
	n = 2; assert(set_contains(s, &n));
	n = 3; assert(set_contains(s, &n));
	n = 4; assert(set_contains(s, &n));
	n = 11; assert(set_contains(s, &n));

	assert(s->len == 5);

	debug(s);

	return 0;
}