shithub: hmap

ref: d3298a0f73f8d45249df6b45b167ae17bea22167
dir: /hash.c/

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

Hmap*
allochmap(uvlong (*hash)(Hnode*), int (*cmp)(Hnode*,Hnode*), int nbuckets, usize size)
{
	Hmap *h = mallocz(sizeof(Hmap), 1);
	if(h == nil)
		return nil;
	h->size = nbuckets;
	h->nsize = size;
	h->hash = hash;
	h->cmp = cmp;
	h->len = h->cap = nbuckets;
	h->nodes = mallocz(h->cap*h->nsize, 1);
	if(h->nodes == nil)
		return nil;
	return h;
}

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

	tmp = nil;
	wlock(h);
	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 == nil)
			break;
		n = n->next;
	}

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

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

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

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

	runlock(h);
	return nil;
}

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

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

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

void
hmapfree(Hmap *h)
{
	free(h->nodes);
	free(h);
}

int
hmapfmt(Fmt *f)
{
	Hmap *h;
	Hnode *n, *o;
	Rune r[3] = {0, 0, 0};
	char fmt[16];
	int i, len;

	h = va_arg(f->args, Hmap*);
	rlock(h);
	r[0] = '%';
	r[1] = h->nodeverb;
	snprint(fmt, sizeof fmt - 1, "%S", r);
	for(i=len=0; i < h->size; i++){
		n = (Hnode*)(h->nodes + i*h->nsize);
		for(o=n; o != nil; o = o->next)
			if(n->filled != 0)
				len += fmtprint(f, (char*)fmt, o);
	}
	runlock(h);
	return len;
}