shithub: hmap

ref: 8e631b19c4bf009a69489fcdd2e0b8c84a104a15
dir: hmap/hash.c

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

typedef struct Hnode Hnode;
struct Hnode {
	int filled;
	int next;
	void *key;
};

enum{
	Tagsize = sizeof(Hnode),
};

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

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

	h = store;
	h->nbs = nbuckets;
	h->nsz = nsz;
	h->hash = hash;
	h->cmp = cmp;
	h->len = h->cap = nbuckets;

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

int
hmapset(Hmap **store, void *key, void *new, void *old)
{
	Hnode *n;
	uchar *v;
	uchar *oldv;
	Hmap *h;
	int next;

	h = *store;
	oldv = nil;
	v = h->nodes + (h->hash(key)%h->nbs) * h->nsz;

	for(;;){
		n = (Hnode*)v;
		next = n->next;

		if(n->filled == 0)
			goto replace;
		if(h->cmp(n->key, key) == 0){
			oldv = v + Tagsize;
			goto replace;
		}
		if(next == 0)
			break;
		v = h->nodes + next*h->nsz;
	}

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

replace:
	memmove(v + Tagsize, new, h->nsz - Tagsize);
	n->filled++;
	n->key = key;
	n->next = next;
	if(old != nil && oldv != nil){
		memmove(old, oldv, h->nsz - Tagsize);
		return 1;
	}
	return 0;
}

void*
_hmapget(Hmap *h, void *key)
{
	Hnode *n;
	uchar *v;

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

int
hmapget(Hmap *h, void *key, void *dst)
{
	uchar *v;

	v = _hmapget(h, key);
	if(v == nil)
		return -1;
	if(dst != nil)
		memmove(dst, v + Tagsize, h->nsz - Tagsize);
	return 0;
}

int
hmapdel(Hmap *h, void *key, void *dst)
{
	uchar *v;
	Hnode *n;

	v = _hmapget(h, key);
	if(v == nil)
		return -1;

	n = (Hnode*)v;
	n->filled = 0;
	if(dst != nil)
		memmove(dst, v + Tagsize, h->nsz - Tagsize);
	return 0;
}

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

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

	new = hmapalloc(old->hash, old->cmp, buckets, old->nsz - Tagsize);
	for(i=0 ; i < old->len; i++){
		v = old->nodes + i*old->nsz;
		n = (Hnode*)v;
		hmapset(&new, n->key, v + Tagsize, nil);
	}
	free(old);
	return new;
}

int
hmapvals(Hmap *h, void *buf, int maxelem)
{
	Hnode *n;
	uchar *v;
	uchar *out;
	int i, valsz;

	out = buf;
	valsz = h->nsz - Tagsize;
	for(i=0; i <= maxelem && i < h->len; i++){
		v = h->nodes + i*h->nsz;
		n = (Hnode*)v;
		if(n->filled == 0)
			continue;
		v += Tagsize;
		memmove(out, v, valsz);
		out += valsz;
	}
	return (out - (uchar*)buf)/valsz;
}