shithub: hmap

Info  •  Files  •  Log

third pass

--- a/hash.c

+++ b/hash.c

@@ -2,19 +2,25 @@

 #include <libc.h>

 #include "hash.h"

+enum{

+	Tagsize = sizeof(Hnode),

+};

+

 Hmap*

-allochmap(uvlong (*hash)(void*), int (*cmp)(void*,void*), int nbuckets, usize size)

+allochmap(uvlong (*hash)(void*), int (*cmp)(void*,void*), int nbuckets, int size)

 {

 	void *store;

 	Hmap *h;

+	int nsz;

-	store = mallocz(sizeof(*h) + (nbuckets * size), 1);

+	nsz = Tagsize + size;

+	store = mallocz(sizeof(*h) + (nbuckets * nsz), 1);

 	if(store == nil)

 		return nil;

 	h = store;

-	h->size = nbuckets;

-	h->nsize = size;

+	h->nbs = nbuckets;

+	h->nsz = nsz;

 	h->hash = hash;

 	h->cmp = cmp;

 	h->len = h->cap = nbuckets;

@@ -25,79 +31,80 @@

 }

 void

-hmapset(Hmap **store, Hnode *new)

+hmapset(Hmap **store, void *new)

 {

 	Hnode *n;

+	uchar *v;

 	Hmap *h;

-	int tmp;

+	int next;

-	tmp = 0;

 	h = *store;

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

+	v = h->nodes + (h->hash(new)%h->nbs) * h->nsz;

 	for(;;){

+		n = (Hnode*)v;

+		next = n->next;

+

 		if(n->filled == 0)

 			goto replace;

-		if(h->cmp(n, new) == 0){

-			tmp = n->next;

+		if(h->cmp(v + Tagsize, new) == 0)

 			goto replace;

-		}

-		if(n->next == 0)

+		if(next == 0)

 			break;

-		n = (Hnode*)(h->nodes + n->next*h->nsize);

+		v = h->nodes + next*h->nsz;

 	}

 	if(h->cap == h->len){

 		h->cap *= 2;

-		*store = realloc(*store, sizeof(*h) + h->cap*h->nsize);

+		*store = realloc(*store, sizeof(*h) + h->cap*h->nsz);

 		h = *store;

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

-		memset(h->nodes + h->len*h->nsize, 0, h->nsize);

+		memset(h->nodes + h->len*h->nsz, 0, h->nsz);

 	}

 	n->next = h->len;

 	h->len++;

 	assert(h->len <= h->cap);

-	n = (Hnode*)(h->nodes + n->next*h->nsize);

+	v = h->nodes + n->next*h->nsz;

+	n = (Hnode*)v;

 replace:

-	memmove(n, new, h->nsize);

+	memmove(v + Tagsize, new, h->nsz - Tagsize);

 	n->filled++;

-	n->next = tmp;

+	n->next = next;

 }

 void*

-hmapget(Hmap *h, Hnode *q)

+hmapget(Hmap *h, void *q)

 {

 	Hnode *n;

+	uchar *v;

-	n = (Hnode*)(h->nodes + (h->hash(q)%h->size)*h->nsize);

+	v = h->nodes + (h->hash(q)%h->nbs)*h->nsz;

 	for(;;){

-		if(n->filled != 0 && h->cmp(n, q) == 0)

-			return n;

+		n = (Hnode*)v;

+		if(n->filled != 0 && h->cmp(v + Tagsize, q) == 0)

+			return v + Tagsize;

 		if(n->next == 0)

 			break;

-		n = (Hnode*)(h->nodes + n->next*h->nsize);

+		v = h->nodes + n->next*h->nsz;

 	}

 	return nil;

 }

-void

-hmapmark(Hmap *h, Hnode *n)

-{

-	n->filled = 0;

-}

 void*

 hmapdel(Hmap *h, Hnode *q)

 {

+	uchar *v;

 	Hnode *n;

-	n = hmapget(h, q);

+	v = hmapget(h, q);

 	if(n == nil)

 		return nil;

+	n = (Hnode*)(v - Tagsize);

 	n->filled = 0;

-	return n;

+	return v;

 }

 Hmap*

@@ -104,16 +111,16 @@

 hmaprehash(Hmap *old, int buckets)

 {

 	int i;

-	Hnode *n;

+	uchar *v;

 	Hmap *new;

 	if(buckets == 0)

 		buckets = old->len;

-	new = allochmap(old->hash, old->cmp, buckets, old->nsize);

+	new = allochmap(old->hash, old->cmp, buckets, old->nsz);

 	for(i=0 ; i < old->len; i++){

-		n = (Hnode*)(old->nodes + i*old->nsize);

-		hmapset(&new, n);

+		v = old->nodes + i*old->nsz;

+		hmapset(&new, v + Tagsize);

 	}

 	free(old);

 	return new;

@@ -120,27 +127,23 @@

 }

 int

-hmapfmt(Fmt *f)

+hmapvals(Hmap *h, void *buf, int maxelem)

 {

-	Hmap *h;

-	Hnode *n, *o;

-	char fmt[16];

-	int i, len;

+	Hnode *n;

+	uchar *v;

+	uchar *out;

+	int i, valsz;

-	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);

-		}		

+	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 len;

+	return (out - (uchar*)buf)/valsz;

 }

-

--- a/hash.h

+++ b/hash.h

@@ -1,17 +1,18 @@

 typedef struct Hnode Hnode;

 struct Hnode {

-	int next;

 	int filled;

+	int next;

 };

 typedef struct Hmap Hmap;

 struct Hmap {

+	int (*fmt)(Fmt*);

+	Rune fmtsep;

+

 	uvlong (*hash)(void*);

 	int (*cmp)(void*,void*);

-	Rune nodeverb;

-

-	int size;

-	usize nsize;

+	int nbs;

+	int nsz;

 	int len;

 	int cap;

--- a/test.c

+++ b/test.c

@@ -1,20 +1,10 @@

 #include "hash.c"

 typedef struct Tnode {

-	Hnode;

 	char *key;

 	char *value;

 } Tnode;

-int

-tfmt(Fmt *f)

-{

-	Tnode *t;

-

-	t = va_arg(f->args, Tnode*);

-	return fmtprint(f, "%s %s\n", t->key, t->value);

-}

-

 uvlong

 thash(void *n)

 {

@@ -55,10 +45,7 @@

 		{.key "key6", .value "value6" },

 	};

-	fmtinstall('T', tfmt);

-	fmtinstall('H', hmapfmt);

 	h = allochmap(thash, tcmp, 2, sizeof(Tnode));

-	h->nodeverb = 'T';

 	for(i=0; i < nelem(tab); i++)

 		hmapset(&h, &tab[i]);

@@ -72,8 +59,13 @@

 		assert(strcmp(r->value, tab[i].value) == 0);

 	}

-	print("%H", h);

 	print("len, cap: %d %d\n", h->len, h->cap);

+	r = mallocz(sizeof tab, 1);

+	assert(hmapvals(h, r, nelem(tab)) == nelem(tab));

+	for(i=0; i < nelem(tab); i++){

+		print("%s %s\n", r[i].key, r[i].value);

+	}

+

 	h = hmaprehash(h, 0);

 	for(i=0; i < nelem(tab); i++){

 		t = tab[i];