//-*- mode:c -*-

// define HTNAME, HFUNC and EQFUNC, then include this header

#define hash_size(h) ((h)->size/2)

// compute empirical max-probe for a given size
#define max_probe(size) ((size) <= (HT_N_INLINE*2) ? (HT_N_INLINE/2) : (size)>>3)

#define noempty ((usize)-1)

sl_nonnull(1)
sl_returns_nonnull
static void **
HTNAME(_lookup_bp)(sl_htable *h, void *key)
{
	usize sz = hash_size(h), maxprobe = max_probe(sz);
	usize newsz, i, orig, index, iter, empty;
	void **tab = h->table, **ol;
	sl_v hv = HFUNC(key);

	while(1){
		iter = 0;
		index = (hv & (sz-1)) * 2;
		sz *= 2;
		orig = index;
		empty = noempty;

		do{
			if(tab[index] == HT_NOTFOUND){
				if(empty == noempty)
					empty = index;
				break;
			}
			if(tab[index+1] == HT_NOTFOUND && empty == noempty)
				empty = index;
			if(EQFUNC(key, tab[index])){
				if(tab[index+1] == HT_NOTFOUND)
					h->live++; /* reviving a tombstone */
				return &tab[index+1];
			}
			iter++;
			index = (index + iter*2) & (sz-1);
			if(sl_unlikely(iter > maxprobe))
				break; /* grow if probe took too long */
		}while(index != orig);

		/* grow if live entries >= 75% of slots */
		if(empty != noempty && h->live*4 >= sz*3)
			empty = noempty;
		/* rehash if too many tombstones (>= 87.5% slots occupied) */
		bool grow = empty == noempty;
		if(!grow && 8*(sz - h->num) <= sz)
			empty = noempty;
		if(empty != noempty){
			if(tab[empty] == HT_NOTFOUND)
				h->num++;
			h->live++;
			tab[empty] = key;
			return &tab[empty+1];
		}

		/* quadruple size, rehash, retry the insert */
		/* it's important to grow the table really fast; otherwise we waste */
		/* lots of time rehashing all the keys over and over. */
		sz = h->size;
		ol = h->table;
		if(!grow)
			newsz = sz;
		else if(sz < HT_N_INLINE)
			newsz = HT_N_INLINE;
		else if(sz >= (1<<19) || (sz <= (1<<8)))
			newsz = sz<<1;
		else
			newsz = sz<<2;
		if((tab = (void**)MEM_ALLOC(newsz*sizeof(void*))) == nil)
			cthrow(error(sl_errmem, "could not allocate new hash table"), h);
		for(i = 0; i < newsz; i++)
			tab[i] = HT_NOTFOUND;
		h->table = tab;
		h->size = newsz;
		h->num = 0;
		h->live = 0;
		for(i = 0; i < sz; i += 2) {
			if(sl_likely(ol[i+1] != HT_NOTFOUND))
				(*HTNAME(_lookup_bp)(h, ol[i])) = ol[i+1];
		}
		if(ol != &h->local[0])
			MEM_FREE(ol);
		sz = hash_size(h);
	}
}

void
HTNAME(_put)(sl_htable *h, void *key, void *val)
{
	void **bp = HTNAME(_lookup_bp)(h, key);
	*bp = val;
}

void **
HTNAME(_bp)(sl_htable *h, void *key)
{
	return HTNAME(_lookup_bp)(h, key);
}

/* returns bp if key is in hash, otherwise nil */
/* if return is non-nil and *bp == HT_NOTFOUND then key was deleted */
sl_nonnull(1)
static void **
HTNAME(_peek_bp)(sl_htable *h, void *key)
{
	usize sz = hash_size(h);
	usize maxprobe = max_probe(sz);
	void **tab = h->table;
	usize index = (HFUNC(key) & (sz-1)) * 2;
	sz *= 2;
	usize orig = index;
	usize iter = 0;

	do {
		if(tab[index] == HT_NOTFOUND)
			return nil;
		if(EQFUNC(key, tab[index]))
			return &tab[index+1];

		iter++;
		index = (index + iter*2) & (sz-1);
		if(sl_unlikely(iter > maxprobe))
			break;
	}while(index != orig);

	return nil;
}

void *
HTNAME(_get)(sl_htable *h, void *key)
{
	void **bp = HTNAME(_peek_bp)(h, key);
	if(bp == nil)
		return HT_NOTFOUND;
	return *bp;
}

bool
HTNAME(_has)(sl_htable *h, void *key)
{
	return HTNAME(_get)(h, key) != HT_NOTFOUND;
}

bool
HTNAME(_remove)(sl_htable *h, void *key)
{
	void **bp = HTNAME(_peek_bp)(h, key);
	if(bp != nil && *bp != HT_NOTFOUND){
		h->live--;
		*bp = HT_NOTFOUND;
		return true;
	}
	return false;
}

#undef hash_size
#undef max_probe
#undef noempty