shithub: hmap

ref: d789157f513b2c3f324e00401f7e72e6010b6211
dir: /hash.c/

#include <u.h>
#include <libc.h>
#include "hash.h"

Hmap*
allochmap(uvlong (*hash)(void*), int (*cmp)(void*,void*), int nbuckets, usize size)
{
	void *store;
	Hmap *h;

	store = mallocz(sizeof(*h) + (nbuckets * size), 1);
	if(store == nil)
		return nil;

	h = store;
	h->size = nbuckets;
	h->nsize = size;
	h->hash = hash;
	h->cmp = cmp;
	h->len = h->cap = nbuckets;

	h->nodes = store;
	h->nodes += sizeof(*h);
	return store;
}

void
hmapset(Hmap **store, Hnode *new)
{
	Hnode *n;
	Hmap *h;
	int tmp;

	tmp = 0;
	h = *store;
	n = (Hnode*)(h->nodes + (h->hash(new)%h->size)*h->nsize);

	for(;;){
		if(n->filled == 0)
			goto replace;
		if(h->cmp(n, new) == 0){
			tmp = n->next;
			goto replace;
		}
		if(n->next == 0)
			break;
		n = (Hnode*)(h->nodes + n->next*h->nsize);
	}

	if(h->cap == h->len){
		h->cap *= 2;
		*store = realloc(*store, sizeof(*h) + h->cap*h->nsize);
		h = *store;
		h->nodes = (uchar*)*store + sizeof(*h);
		memset(h->nodes + h->len*h->nsize, 0, h->nsize);
	}
	n->next = h->len;
	h->len++;
	assert(h->len <= h->cap);
	n = (Hnode*)(h->nodes + n->next*h->nsize);

replace:
	memmove(n, new, h->nsize);
	n->filled++;
	n->next = tmp;
}

void*
hmapget(Hmap *h, Hnode *q)
{
	Hnode *n;

	n = (Hnode*)(h->nodes + (h->hash(q)%h->size)*h->nsize);
	for(;;){
		if(n->filled != 0 && h->cmp(n, q) == 0)
			return n;
		if(n->next == 0)
			break;
		n = (Hnode*)(h->nodes + n->next*h->nsize);
	}
	return nil;
}

void
hmapmark(Hmap *h, Hnode *n)
{
	n->filled = 0;
}

void*
hmapdel(Hmap *h, Hnode *q)
{
	Hnode *n;

	n = hmapget(h, q);
	if(n == nil)
		return nil;

	n->filled = 0;
	return n;
}

Hmap*
hmaprehash(Hmap *old, int buckets)
{
	int i;
	Hnode *n;
	Hmap *new;

	if(buckets == 0)
		buckets = old->len;

	new = allochmap(old->hash, old->cmp, buckets, old->nsize);
	for(i=0 ; i < old->len; i++){
		n = (Hnode*)(old->nodes + i*old->nsize);
		hmapset(&new, n);
	}
	free(old);
	return new;
}

int
hmapfmt(Fmt *f)
{
	Hmap *h;
	Hnode *n, *o;
	char fmt[16];
	int i, len;

	h = va_arg(f->args, Hmap*);
	fmt[0] = '%';
	memset(fmt+1, 0, UTFmax+1);
	runetochar(fmt+1, &h->nodeverb);
	for(i=len=0; i < h->size; i++){
		n = (Hnode*)(h->nodes + i*h->nsize);
		for(o=n;;){
			if(o->filled != 0)
				len += fmtprint(f, (char*)fmt, o);
			if(o->next == 0)
				break;
			o = (Hnode*)(h->nodes + o->next*h->nsize);
		}		
	}
	return len;
}