C hashmap

hashmap.c

#include "hashmap.h"

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

static uint32_t strhash(const char *str)
{
	// I'm sitting at an airplane as I'm writing this,
	// I don't have access to resources on what reasonable hash algorithms,
	// I need something and this is something
	uint32_t num = 0;
	for (unsigned char ch; (ch = *str); ++str) {
		num <<= 5;
		num ^= (num >> 16);
		num ^= ch;
	}

	return num;
}

static void insert(struct hashmap *hm, struct hashmap_entry *entry)
{
	uint32_t idx = strhash(entry->payload) & (hm->capacity - 1);
	entry->next = hm->buckets[idx];
	hm->buckets[idx] = entry;
	hm->size += 1;
}

static void rehash(struct hashmap *hm, size_t capacity)
{
	struct hashmap old;
	memcpy(&old, hm, sizeof(*hm));

	// (hm->capacity - 1) is a valid bit mask iff capacity is a power of 2
	hm->buckets = calloc(capacity, sizeof(*hm->buckets));
	if (!hm->buckets) {
		abort();
	}

	hm->capacity = capacity;
	hm->size = 0;

	for (size_t i = 0; i < old.capacity; ++i) {
		struct hashmap_entry *entry = old.buckets[i];
		while (entry) {
			// insert modifies entry->next,
			// so we need to remember the old next
			struct hashmap_entry *next = entry->next;
			insert(hm, entry);
			entry = next;
		}
	}
}

void hashmap_init(struct hashmap *hm)
{
	hm->buckets = NULL;
	hm->capacity = 0;
	hm->size = 0;
}

struct hashmap_entry *hashmap_lookup(struct hashmap *hm, const char *key)
{
	if (hm->capacity == 0) {
		return NULL;
	}

	// (hm->capacity - 1) is a valid bit mask iff capacity is a power of 2
	uint32_t idx = strhash(key) & (hm->capacity - 1);

	struct hashmap_entry *entry = hm->buckets[idx];
	while (entry && strcmp(entry->payload, key) != 0) {
		entry = entry->next;
	}

	return entry;
}

void hashmap_insert(struct hashmap *hm, const char *key, const void *val, size_t size)
{
	if (hm->size >= hm->capacity / 2) {
		rehash(hm, hm->capacity ? hm->capacity * 2 : 4);
	}

	size_t keylen = strlen(key) + 1;
	struct hashmap_entry *entry = malloc(sizeof(*entry) + keylen + size);
	if (!entry) {
		abort();
	}

	entry->value_offset = keylen;
	memcpy(entry->payload, key, keylen);
	memcpy(&entry->payload[keylen], val, size);
	// Ignore entry->next, since 'insert' sets that
	insert(hm, entry);
}

void hashmap_iterate(struct hashmap *hm, struct hashmap_iter *iter)
{
	iter->hm = hm;
	for (iter->idx = 0; iter->idx < hm->capacity; ++iter->idx) {
		if (hm->buckets[iter->idx]) {
			iter->next = hm->buckets[iter->idx];
			return;
		}
	}

	iter->next = NULL;
}

struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter)
{
	if (!iter->next) {
		return NULL;
	}

	struct hashmap_entry *entry = iter->next;

	iter->next = iter->next->next;
	while (iter->next == NULL && iter->idx < iter->hm->capacity) {
		iter->idx += 1;
		iter->next = iter->hm->buckets[iter->idx];
	}

	return entry;
}

hashmap.h

#ifndef CHASHMAP_H
#define CHASHMAP_H

#include <stddef.h>
#include <string.h>

struct hashmap_entry {
	struct hashmap_entry *next;
	size_t value_offset;
	char payload[]; // First the key, then a 0 byte, then a value
};

inline void hashmap_entry_get(struct hashmap_entry *entry, void *val, size_t size)
{
	memcpy(val, &entry->payload[entry->value_offset], size);
}

struct hashmap_iter {
	struct hashmap *hm;
	struct hashmap_entry *next;
	size_t idx;
};

struct hashmap {
	struct hashmap_entry **buckets;
	size_t capacity;
	size_t size;
};

void hashmap_init(struct hashmap *hm);
struct hashmap_entry *hashmap_lookup(struct hashmap *hm, const char *key);
void hashmap_insert(struct hashmap *hm, const char *key, const void *val, size_t size);
void hashmap_iterate(struct hashmap *hm, struct hashmap_iter *iter);

struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter);

#endif