shithub: hmap

Info  •  Files  •  Log

fourth pass

--- a/hash.c

+++ b/hash.c

@@ -2,6 +2,13 @@

 #include <libc.h>

 #include "hash.h"

+typedef struct Hnode Hnode;

+struct Hnode {

+	int filled;

+	int next;

+	void *key;

+};

+

 enum{

 	Tagsize = sizeof(Hnode),

 };

@@ -31,7 +38,7 @@

 }

 void

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

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

 {

 	Hnode *n;

 	uchar *v;

@@ -39,7 +46,7 @@

 	int next;

 	h = *store;

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

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

 	for(;;){

 		n = (Hnode*)v;

@@ -47,7 +54,7 @@

 		if(n->filled == 0)

 			goto replace;

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

+		if(h->cmp(n->key, key) == 0)

 			goto replace;

 		if(next == 0)

 			break;

@@ -70,19 +77,20 @@

 replace:

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

 	n->filled++;

+	n->key = key;

 	n->next = next;

 }

 void*

-hmapget(Hmap *h, void *q)

+hmapget(Hmap *h, void *key)

 {

 	Hnode *n;

 	uchar *v;

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

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

 	for(;;){

 		n = (Hnode*)v;

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

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

 			return v + Tagsize;

 		if(n->next == 0)

 			break;

@@ -93,13 +101,13 @@

 void*

-hmapdel(Hmap *h, Hnode *q)

+hmapdel(Hmap *h, void *key)

 {

 	uchar *v;

 	Hnode *n;

-	v = hmapget(h, q);

-	if(n == nil)

+	v = hmapget(h, key);

+	if(v == nil)

 		return nil;

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

@@ -112,15 +120,17 @@

 {

 	int i;

 	uchar *v;

+	Hnode *n;

 	Hmap *new;

 	if(buckets == 0)

 		buckets = old->len;

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

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

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

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

-		hmapset(&new, v + Tagsize);

+		n = (Hnode*)v;

+		hmapset(&new, n->key, v + Tagsize);

 	}

 	free(old);

 	return new;

--- a/hash.h

+++ b/hash.h

@@ -1,14 +1,11 @@

-typedef struct Hnode Hnode;

-struct Hnode {

-	int filled;

-	int next;

+typedef union Hkey Hkey;

+union Hkey {

+	void *p;

+	int v;

 };

 typedef struct Hmap Hmap;

 struct Hmap {

-	int (*fmt)(Fmt*);

-	Rune fmtsep;

-

 	uvlong (*hash)(void*);

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

 	int nbs;

--- a/test.c

+++ b/test.c

@@ -1,42 +1,27 @@

 #include "hash.c"

-typedef struct Tnode {

-	char *key;

-	char *value;

-} Tnode;

-

 uvlong

-thash(void *n)

+thash(char *s)

 {

-	Tnode *t;

 	uvlong hash;

-	char *s;

-	t = n;

 	hash = 7;

-	s = t->key;

 	for(; *s; s++)

 		hash = hash*31  + *s;

 	return hash;

 }

-int

-tcmp(void *_a, void *_b)

-{

-	Tnode *a, *b;

-

-	a = _a;

-	b = _b;

-	return strcmp(a->key, b->key);

-}

-

 void

-main(int argc, char **argv)

+testbasic(void)

 {

 	int i;

 	Hmap *h;

-	Tnode t, *r;

-	Tnode tab[] = {

+	char **v;

+

+	struct {

+		char *key;

+		char *value;

+	} tab[] = {

 		{.key "key1", .value "value1" },

 		{.key "key2", .value "value2" },

 		{.key "key3", .value "value3" },

@@ -45,35 +30,76 @@

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

 	};

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

+	h = allochmap(thash, strcmp, 1, sizeof(char*));

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

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

+		hmapset(&h, tab[i].key, &tab[i].value);

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

-		t = tab[i];

-		t.value = "";

-		r = hmapget(h, &t);

-		assert(r);

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

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

+		v = hmapget(h, tab[i].key);

+		assert(v);

+		assert(strcmp(*v, tab[i].value) == 0);

 	}

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

-	r = mallocz(sizeof tab, 1);

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

+

+	v = mallocz(nelem(tab)*sizeof(char*), 1);

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

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

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

+		print("%s\n", v[i]);

 	}

 	h = hmaprehash(h, 0);

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

-		t = tab[i];

-		t.value = "";

-		r = hmapget(h, &t);

-		assert(r);

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

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

+		v = hmapget(h, tab[i].key);

+		assert(v);

+		assert(strcmp(*v, tab[i].value) == 0);

 	}

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

+	free(h);

+}

+

+uvlong

+runehash(void *p)

+{

+	Hkey k;

+	k.p = p;

+	return k.v * 0xdeece66d + 0xb;

+}

+

+int

+runecmp(void *_a, void *_b)

+{

+	Hkey a, b;

+	a.p = _a, b.p = _b;

+	return !(a.v == b.v);

+}

+

+void

+testrunekey(void)

+{

+	Hkey k;

+	Hmap *h;

+	char *v;

+	char **p;

+

+	h = allochmap(runehash, runecmp, 16, sizeof(char*));

+

+	k.v = 'p';

+	v = "hello";

+	hmapset(&h, k.p, &v);

+	hmapset(&h, k.p, &v);

+

+	p = hmapget(h, k.p);

+	assert(p && *p);

+	assert(*p == v);

+}

+

+void

+main(int argc, char **argv)

+{

+	USED(argc);

+	USED(argv);

+	testbasic();

+	testrunekey();

 }