#ifndef SHASH_H
#define SHASH_H

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

#include "stdwrm.h"
#include "dynarr.h"
#include "str.h"

#ifndef SHASH_SLOTS
#define SHASH_SLOTS 8192
#endif

typedef uint64_t hash_t;

typedef struct {
	string key;
	void *value;
	hash_t hash;
} StrHashEntry;

typedef struct {
	DYNARR(StrHashEntry) entries;
} StrHashSlot;

typedef struct {
	StrHashSlot slots[SHASH_SLOTS];
} StrHashTable;

hash_t shash(strv_t s);
void shash_init(StrHashTable *h);
void shash_free(StrHashTable *h);
void *shash_get(StrHashTable *h, strv_t key);
void shash_put(StrHashTable *h, strv_t key, void *value);
StrHashEntry *shash_find(StrHashTable *h, strv_t key);

#ifdef STDWRM_IMPL_SHASH

/* hacky FNV-1a hash */

#define FNV_64_PRIME (hash_t)1099511628211LU
#define FNV_OFFSET_BASIS (hash_t)14695981039346656037LU
hash_t shash(strv_t s) {
	hash_t h = FNV_OFFSET_BASIS;
	for (size_t i = 0; i < s.n; i++) h = (h ^ s.s[i]) * FNV_64_PRIME;
	return h;
}

/* hash table */

void shash_init(StrHashTable *h) {
	*h = (StrHashTable) { 0 };
}

void shash_free(StrHashTable *h) {
	for (unsigned i = 0; i < SHASH_SLOTS; i++) {
		StrHashSlot *s = &h->slots[i];
		if (!s->entries) continue;
		DA_FOR(s->entries, e) sfree(e->key);
		DA_FREE(s->entries);
	}
}

static inline int shash_entry_match(StrHashEntry *h, strv_t s, hash_t shash) {
	return h->hash == shash && slen(h->key) == s.n && !strncmp(h->key, s.s, s.n);
}

static inline StrHashEntry *shash_find_hashed(StrHashTable *h, strv_t key, hash_t k) {
	size_t i = k & (SHASH_SLOTS - 1);
	if (h->slots[i].entries) {
		DA_FOR(h->slots[i].entries, e) {
			if (shash_entry_match(e, key, k)) {
				return e;
			}
		}
	}
	return NULL;
}

StrHashEntry *shash_find(StrHashTable *h, strv_t key) {
	return shash_find_hashed(h, key, shash(key));
}

void *shash_get(StrHashTable *h, strv_t key) {
	StrHashEntry *e = shash_find(h, key);
	return e ? e->value : NULL;
}

void shash_put(StrHashTable *h, strv_t key, void *value) {
	hash_t keyh = shash(key);
	StrHashEntry *e = shash_find_hashed(h, key, keyh);
	if (e) {
		e->value = value;
	} else {
		hash_t keyi = keyh & (SHASH_SLOTS - 1);
		if (!h->slots[keyi].entries) {
			DA_INIT(h->slots[keyi].entries);
		}
		string s = snew();
		scats(&s, key);
		DA_PUSH(h->slots[keyi].entries, (StrHashEntry) {
			.key = s,
			.value = value,
			.hash = keyh
		});
	}
}

#endif
#endif