# new flat hashtable code, called 'flat' to be different!

# key may not be zero, val may not be zero;
# TODO? change those sentinel values, or make a parameter?

# TODO check c >= n/2 or whatever, then double.
# Will infinite loop at the moment if it gets full :/

export util hash alloc

struct flat:
	size_t size
	size_t count
	key_value *table
	hash_fn *hash
	eq_fn *eq

def flat_default_size 101

# I assume size < 2^32
def flat_init(d)
	flat_init_prime(d, flat_default_size)
def flat_init(d, size)
	flat_init(d, cstr_hash, cstr_eq, size)
def flat_init(d, hash, eq)
	flat_init_prime(d, hash, eq, flat_default_size)
def flat_init(d, hash, eq, size)
	flat_init_prime(d, hash, eq, prime_2pow_32(size))

# note: flat_init_prime: size MUST be prime
def flat_init_prime(d, size)
	flat_init_prime(d, cstr_hash, cstr_eq, size)
flat_init_prime(flat *d, hash_fn *hash, eq_fn *eq, size_t size)
	d->size = size
	d->count = 0
	d->table = Valloc(key_value, size)
	d->hash = hash
	d->eq = eq

def flat_hash(hash, i, step, d, key):
	ulong hash = (*d->hash)(key)
	ulong i = hash % d->size
	ulong step = hash % (d->size-1) + 1

flat_add(flat *d, void *key, void *val):
	flat_hash(hash, i, step, d, key)
	flat_find_empty(d, i, step, key)
	flat_add_at(d, i, key, val)

def flat_add_at(d, i, key, val)
	d->table[i] = (key_value){key, val}
	++d->count

def flat_find_empty(d, i, step, key):
	while d->table[i].k:
		flat_step(d, i, step)

def flat_next_empty(last, d, i, step, key):
	do:
		flat_step(d, i, step)
	 while !d->table[i].k

def flat_step(d, i, step)
	i += step
	if i >= d->size:
		i -= d->size

void *flat_put(flat *d, void *key, void *val):
	void *old
	flat_hash(hash, i, step, d, key)
	flat_find_key(eq, d, i, step, key)
	if eq:
		old = d->table[i].v
		d->table[i].v = val
	 else:
		flat_add_at(d, i, key, val)
		old = NULL
	return old

def flat_find_key(eq, d, i, step, key):
	bit eq = 0
	while d->table[i].k:
		eq = (*d->eq)(key, d->table[i].k)
		if eq:
			break
		flat_step(d, i, step)

def flat_next_key(eq, d, i, step, key):
	bit eq = 0
	repeat:
		flat_step(d, i, step)
		if !d->table[i].k:
			break
		eq = (*d->eq)(key, d->table[i].k)
		if eq:
			break

void *flat_get(flat *d, void *key):
	flat_hash(hash, i, step, d, key)
	flat_find_key(eq, d, i, step, key)
	if eq:
		return d->table[i].v
	return NULL

struct flatp:
	ulong i
	ulong step

flatp flat_find(flat *d, void *key):
	flat_hash(hash, i, step, d, key)
	flat_find_key(eq, d, i, step, key)
	if eq:
		return (flatp){i, step}
	return (flatp){-1, 0}

def flatp(p) p->step

def flatp_val(d, p):
	d->table[p.i].v

flatp_next(flat *d, flatp *p, void *key):
	flat_next_key(eq, d, p->i, p->step, key)

#flatp_del(flat *d, flatp *p):
#	d->table[p.i] = {0, 0}

# XXX this is only for benchmark, not ok for multi-valued keys
bit flat_del1(flat *d, void *key):
	flat_hash(hash, i, step, d, key)
	flat_find_key(eq, d, i, step, key)
	if eq:
		d->table[i] = (key_value){0, 0}
	return eq