shithub: hmap

Info  •  Files  •  Log

second pass

--- a/hash.c

+++ b/hash.c

@@ -3,29 +3,36 @@

 #include "hash.h"

 Hmap*

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

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

 {

-	Hmap *h = mallocz(sizeof(Hmap), 1);

-	if(h == nil)

+	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 = mallocz(h->cap*h->nsize, 1);

-	if(h->nodes == nil)

-		return nil;

-	return h;

+

+	h->nodes = store;

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

+	return store;

 }

 void

-hmapset(Hmap *h, Hnode *new)

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

 {

-	Hnode *n, *tmp;

+	Hnode *n;

+	Hmap *h;

+	int tmp;

-	tmp = nil;

-	wlock(h);

+	tmp = 0;

+	h = *store;

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

 	for(;;){

@@ -35,42 +42,42 @@

 			tmp = n->next;

 			goto replace;

 		}

-		if(n->next == nil)

+		if(n->next == 0)

 			break;

-		n = n->next;

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

 	}

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

 		h->cap *= 2;

-		h->nodes = realloc(h->nodes, h->cap*h->nsize);

+		*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 = (Hnode*)(h->nodes + h->len*h->nsize);

+	n->next = h->len;

 	h->len++;

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

-	n = n->next;

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

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

 replace:

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

 	n->filled++;

 	n->next = tmp;

-	wunlock(h);

 }

-Hnode*

+void*

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

+	for(;;){

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

 			return n;

-		}

-

-	runlock(h);

+		if(n->next == 0)

+			break;

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

+	}

 	return nil;

 }

@@ -77,12 +84,10 @@

 void

 hmapmark(Hmap *h, Hnode *n)

 {

-	wlock(h);

 	n->filled = 0;

-	wunlock(h);

 }

-Hnode*

+void*

 hmapdel(Hmap *h, Hnode *q)

 {

 	Hnode *n;

@@ -90,15 +95,28 @@

 	n = hmapget(h, q);

 	if(n == nil)

 		return nil;

-	hmapmark(h, n);

+

+	n->filled = 0;

 	return n;

 }

-void

-hmapfree(Hmap *h)

+Hmap*

+hmaprehash(Hmap *old, int buckets)

 {

-	free(h->nodes);

-	free(h);

+	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

@@ -106,22 +124,23 @@

 {

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

+	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; o != nil; o = o->next)

-			if(n->filled != 0)

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

+		}		

 	}

-	runlock(h);

 	return len;

 }

--- a/hash.h

+++ b/hash.h

@@ -1,20 +1,19 @@

 typedef struct Hnode Hnode;

 struct Hnode {

-	Hnode *next;

+	int next;

 	int filled;

 };

 typedef struct Hmap Hmap;

 struct Hmap {

-	RWLock;

-	uvlong (*hash)(Hnode*);

-	int (*cmp)(Hnode*,Hnode*);

-	int nodeverb;

+	uvlong (*hash)(void*);

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

+	Rune nodeverb;

 	int size;

 	usize nsize;

-	uchar *nodes;

 	int len;

 	int cap;

+	uchar *nodes;

 };

--- a/test.c

+++ b/test.c

@@ -16,27 +16,27 @@

 }

 uvlong

-thash(Hnode *h)

+thash(void *n)

 {

 	Tnode *t;

 	uvlong hash;

 	char *s;

-	t = (Tnode*)h;

+	t = n;

 	hash = 7;

 	s = t->key;

-	for(; *s;s++)

+	for(; *s; s++)

 		hash = hash*31  + *s;

 	return hash;

 }

 int

-tcmp(Hnode *ha, Hnode *hb)

+tcmp(void *_a, void *_b)

 {

 	Tnode *a, *b;

-	a = (Tnode*)ha;

-	b = (Tnode*)hb;

+	a = _a;

+	b = _b;

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

 }

@@ -43,34 +43,45 @@

 void

 main(int argc, char **argv)

 {

+	int i;

 	Hmap *h;

-	Tnode a, b;

-	Tnode *r;

+	Tnode t, *r;

+	Tnode tab[] = {

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

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

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

+		{.key "key4", .value "value4" },

+		{.key "key5", .value "value5" },

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

+	};

 	fmtinstall('T', tfmt);

 	fmtinstall('H', hmapfmt);

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

 	h->nodeverb = 'T';

-	a.key = "key";

-	a.value = "value";

-	hmapset(h, &a);

-	b.key = "key2";

-	b.value = "value2";

-	hmapset(h, &b);

-	b.key = "key3";

-	b.value = "value3";

-	hmapset(h, &b);

-	a.value = "";

-	r = (Tnode*)hmapget(h, &a);

-	assert(strcmp(r->key, a.key) == 0);

-	if(strcmp(r->value, "value") != 0)

-		sysfatal("fail");

-	b.key = "key3";

-	r = (Tnode*)hmapget(h, &b);

-	assert(strcmp(r->key, b.key) == 0);

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

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

+

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

+	}

+

 	print("%H", h);

-	hmapfree(h);

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

-	print("pass\n");

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

+	}

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

 }