#include "ht.h"

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

#include "mem.h"

#define FNV_BASIS 0x811c9dc5 
#define FNV_PRIME 0x01000193

// fnv-1a
uint32_t hash_string(char *s, size_t len) {
	uint32_t h = FNV_BASIS;
	for(int i = 0; i < len; i++) {
		h ^= s[i];
		h *= FNV_PRIME;
	}
	return h;
}

Ht ht_new() {
	return (Ht){ 0 };
}

static HtEntry *find(HtEntry *b, size_t cap, ObjString *k) {
	// cap is guaranteed to be power of 2
	size_t mask = cap - 1;
	size_t ix = k->hash & mask;
	if (cap == 0) return NULL;
	for (;;) {
		HtEntry *ent = &b[ix];
		// XXX tombstones
		if (ent->k == NULL || ent->k == k) {
			return ent;
		}
		ix = (ix+1) & mask;
	}
}

ObjString *ht_findstring(State *S, Ht *h, char *s, size_t len, uint32_t hash) {
	const size_t cap = h->cap;
	if (cap == 0) return NULL;
	size_t ix = hash % cap;

	for (;;) {
		HtEntry *ent = &h->d[ix];
		// XXX tombstones
		if (ent->k == NULL) 
			return NULL;
		else if (ent->k->hash == hash
		         && ent->k->len == len
		         && memcmp(ent->k->d, s, len) == 0)
			return ent->k;

		ix = (ix+1)%cap;
	}
}

static void grow(State *S, Ht *h) {
	HtEntry *old = h->d;
	size_t newsz = h->cap == 0 ? 8 : h->cap * 2;
	HtEntry *new = NEW_ARR(S, HtEntry, newsz);
	for (int i = 0; i<newsz; i++) {
		new[i].k = NULL;
		new[i].v = VAL_NIL;
	}

	if (old != NULL) {
		for (int i = 0; i < h->cap; i++) {
			HtEntry *oldent = &old[i];
			if (oldent->k == NULL) continue;

			HtEntry *newent = find(new, newsz, oldent->k);
			newent->k = oldent->k;
			newent->v = oldent->v;
		}
	}

	h->d = new;
	FREE_ARR(S, old, HtEntry, h->cap);
	h->cap = newsz;
}


void ht_put(State *S, Ht *h, ObjString *k, Val v) {
	if (h->cap == 0 || h->len >= (h->cap/2)) {
		grow(S, h);
	}
	HtEntry *ent = find(h->d, h->cap, k);
	if (ent->k == NULL) {
		ent->k = k;
		h->len++;
	}
	ent->v = v;
}

Val ht_get(State *S, Ht *h, ObjString *k) {
	HtEntry *ent = find(h->d, h->cap, k);
	if (ent == NULL) 
		return VAL_NIL;
	else if (ent->k == NULL)
		return VAL_NIL;
	else
		return ent->v;
}