//-*- 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_nonnullstatic 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);	}} voidHTNAME(_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;} 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->live--;		*bp = HT_NOTFOUND;		return true;	}	return false;} #undef hash_size#undef max_probe#undef noempty