shithub: hmap

Info  •  Files  •  Log

fifth pass

--- a/hash.c

+++ b/hash.c

@@ -14,7 +14,7 @@

 };

 Hmap*

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

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

 {

 	void *store;

 	Hmap *h;

@@ -37,15 +37,17 @@

 	return store;

 }

-void

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

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

@@ -54,8 +56,10 @@

 		if(n->filled == 0)

 			goto replace;

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

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

+			oldv = v + Tagsize;

 			goto replace;

+		}

 		if(next == 0)

 			break;

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

@@ -79,10 +83,15 @@

 	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)

+_hmapget(Hmap *h, void *key)

 {

 	Hnode *n;

 	uchar *v;

@@ -91,7 +100,7 @@

 	for(;;){

 		n = (Hnode*)v;

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

-			return v + Tagsize;

+			return v;

 		if(n->next == 0)

 			break;

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

@@ -99,20 +108,34 @@

 	return nil;

 }

+int

+hmapget(Hmap *h, void *key, void *dst)

+{

+	uchar *v;

-void*

-hmapdel(Hmap *h, void *key)

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

+	v = _hmapget(h, key);

 	if(v == nil)

-		return nil;

+		return -1;

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

+	n = (Hnode*)v;

 	n->filled = 0;

-	return v;

+	if(dst != nil)

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

+	return 0;

 }

 Hmap*

@@ -126,11 +149,11 @@

 	if(buckets == 0)

 		buckets = old->len;

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

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

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

 	}

 	free(old);

 	return new;

--- a/test.c

+++ b/test.c

@@ -16,6 +16,7 @@

 {

 	int i;

 	Hmap *h;

+	char *p;

 	char **v;

 	struct {

@@ -30,15 +31,15 @@

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

 	};

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

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

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

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

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

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

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

-		assert(v);

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

+		hmapget(h, tab[i].key, &p);

+		assert(p);

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

 	}

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

@@ -45,15 +46,14 @@

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

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

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

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

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

-	}

 	h = hmaprehash(h, 0);

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

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

-		assert(v);

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

+		hmapget(h, tab[i].key, &p);

+		assert(p);

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

 	}

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

 	free(h);

@@ -64,7 +64,7 @@

 {

 	Hkey k;

 	k.p = p;

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

+	return k.v;

 }

 int

@@ -81,18 +81,20 @@

 	Hkey k;

 	Hmap *h;

 	char *v;

-	char **p;

+	char *p, *p2;

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

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

 	k.v = 'p';

 	v = "hello";

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

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

+	assert(hmapset(&h, k.p, &v, nil) == 0);

+	assert(hmapset(&h, k.p, &v, &p2) == 1);

+	assert(p2 == v);

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

+	assert(hmapget(h, k.p, &p) == 0);

 	assert(p && *p);

-	assert(*p == v);

+	assert(p == v);

+	free(h);

 }

 void