shithub: sl

ref: 12c9d2fc728b51aa1eb9a70d0d331eb9464912d9
dir: /src/htable_c.h/

//-*- 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)

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

	hv = HFUNC(key);
retry_bp:
	iter = 0;
	index = (hv & (sz-1)) * 2;
	sz *= 2;
	orig = index;

	do{
		if(tab[index+1] == HT_NOTFOUND){
			tab[index] = key;
			return &tab[index+1];
		}
		if(EQFUNC(key, tab[index]))
			return &tab[index+1];
		index = (index+2) & (sz-1);
		iter++;
		if(iter > maxprobe)
			break;
	}while(index != orig);

	/* table full */
	/* 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(sz >= (1<<19) || (sz <= (1<<8)))
		newsz = sz<<1;
	else if(sz <= HT_N_INLINE)
		newsz = HT_N_INLINE;
	else
		newsz = sz<<2;
	tab = (void**)MEM_ALLOC(newsz*sizeof(void*));
	if(tab == nil)
		return nil;
	for(i = 0; i < newsz; i++)
		tab[i] = HT_NOTFOUND;
	h->table = tab;
	h->size = newsz;
	for(i = 0; i < sz; i += 2) {
		if(ol[i+1] != HT_NOTFOUND)
			(*HTNAME(_lookup_bp)(h, ol[i])) = ol[i+1];
	}
	if(ol != &h->_space[0])
		MEM_FREE(ol);
	sz = hash_size(h);
	maxprobe = max_probe(sz);
	tab = h->table;
	goto retry_bp;
}

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 */
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];

		index = (index+2) & (sz-1);
		iter++;
		if(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){
		*bp = HT_NOTFOUND;
		return true;
	}
	return false;
}