shithub: femtolisp

ref: 62389c8990cafb8e99ae29b2bccbcd100ce4c7f0
dir: /htable.inc/

//-*- 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)(htable_t *h, void *key)
{
	value_t hv;
	size_t i, orig, index, iter;
	size_t newsz, sz = hash_size(h);
	size_t maxprobe = max_probe(sz);
	void **tab = h->table;
	void **ol;

	hv = HFUNC((uintptr_t)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)(htable_t *h, void *key, void *val)
{
    void **bp = HTNAME(_lookup_bp)(h, key);
    *bp = val;
}

void **
HTNAME(_bp)(htable_t *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)(htable_t *h, void *key)
{
    size_t sz = hash_size(h);
    size_t maxprobe = max_probe(sz);
    void **tab = h->table;
    size_t index = (HFUNC((uintptr_t)key) & (sz-1)) * 2;
    sz *= 2;
    size_t orig = index;
    size_t 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)(htable_t *h, void *key)
{
    void **bp = HTNAME(_peek_bp)(h, key);
    if(bp == nil)
        return HT_NOTFOUND;
    return *bp;
}

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

int
HTNAME(_remove)(htable_t *h, void *key)
{
    void **bp = HTNAME(_peek_bp)(h, key);
    if(bp != nil){
        *bp = HT_NOTFOUND;
        return 1;
    }
    return 0;
}

void
HTNAME(_adjoin)(htable_t *h, void *key, void *val)
{
    void **bp = HTNAME(_lookup_bp)(h, key);
    if(*bp == HT_NOTFOUND)
        *bp = val;
}