//-*- 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;} voidHTNAME(_put)(sl_htable *h, void *key, void *val){	void **bp = HTNAME(_lookup_bp)(h, key);	if(*bp == HT_NOTFOUND && val != HT_NOTFOUND)		h->num++;	*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;} boolHTNAME(_has)(sl_htable *h, void *key){	return HTNAME(_get)(h, key) != HT_NOTFOUND;} boolHTNAME(_remove)(sl_htable *h, void *key){	void **bp = HTNAME(_peek_bp)(h, key);	if(bp != nil && *bp != HT_NOTFOUND){		h->num--;		*bp = HT_NOTFOUND;		return true;	}	return false;}