ref: d789157f513b2c3f324e00401f7e72e6010b6211
parent: d3298a0f73f8d45249df6b45b167ae17bea22167
author: Jacob Moody <moody@posixcafe.org>
date: Sat May 21 16:43:43 EDT 2022
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);}