ref: d3298a0f73f8d45249df6b45b167ae17bea22167
author: Jacob Moody <moody@posixcafe.org>
date: Mon Aug 9 09:49:22 EDT 2021
first pass
--- /dev/null
+++ b/hash.c
@@ -1,0 +1,127 @@
+#include <u.h>
+#include <libc.h>
+#include "hash.h"
+
+Hmap*
+allochmap(uvlong (*hash)(Hnode*), int (*cmp)(Hnode*,Hnode*), int nbuckets, usize size)
+{+ Hmap *h = mallocz(sizeof(Hmap), 1);
+ if(h == nil)
+ return nil;
+ 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;
+}
+
+void
+hmapset(Hmap *h, Hnode *new)
+{+ Hnode *n, *tmp;
+
+ tmp = nil;
+ wlock(h);
+ n = (Hnode*)(h->nodes + (h->hash(new)%h->size)*h->nsize);
+
+ for(;;){+ if(n->filled == 0)
+ goto replace;
+ if(h->cmp(n, new) == 0){+ tmp = n->next;
+ goto replace;
+ }
+ if(n->next == nil)
+ break;
+ n = n->next;
+ }
+
+ if(h->cap == h->len){+ h->cap *= 2;
+ h->nodes = realloc(h->nodes, h->cap*h->nsize);
+ memset(h->nodes + h->len*h->nsize, 0, h->nsize);
+ }
+ n->next = (Hnode*)(h->nodes + h->len*h->nsize);
+ h->len++;
+ assert(h->len < h->cap);
+ n = n->next;
+
+replace:
+ memmove(n, new, h->nsize);
+ n->filled++;
+ n->next = tmp;
+ wunlock(h);
+}
+
+Hnode*
+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);
+ return n;
+ }
+
+ runlock(h);
+ return nil;
+}
+
+void
+hmapmark(Hmap *h, Hnode *n)
+{+ wlock(h);
+ n->filled = 0;
+ wunlock(h);
+}
+
+Hnode*
+hmapdel(Hmap *h, Hnode *q)
+{+ Hnode *n;
+
+ n = hmapget(h, q);
+ if(n == nil)
+ return nil;
+ hmapmark(h, n);
+ return n;
+}
+
+void
+hmapfree(Hmap *h)
+{+ free(h->nodes);
+ free(h);
+}
+
+int
+hmapfmt(Fmt *f)
+{+ 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);
+ 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)
+ len += fmtprint(f, (char*)fmt, o);
+ }
+ runlock(h);
+ return len;
+}
+
--- /dev/null
+++ b/hash.h
@@ -1,0 +1,20 @@
+typedef struct Hnode Hnode;
+struct Hnode {+ Hnode *next;
+ int filled;
+};
+
+typedef struct Hmap Hmap;
+struct Hmap {+ RWLock;
+ uvlong (*hash)(Hnode*);
+ int (*cmp)(Hnode*,Hnode*);
+ int nodeverb;
+
+ int size;
+ usize nsize;
+
+ uchar *nodes;
+ int len;
+ int cap;
+};
--- /dev/null
+++ b/test.c
@@ -1,0 +1,76 @@
+#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(Hnode *h)
+{+ Tnode *t;
+ uvlong hash;
+ char *s;
+
+ t = (Tnode*)h;
+ hash = 7;
+ s = t->key;
+ for(; *s;s++)
+ hash = hash*31 + *s;
+ return hash;
+}
+
+int
+tcmp(Hnode *ha, Hnode *hb)
+{+ Tnode *a, *b;
+
+ a = (Tnode*)ha;
+ b = (Tnode*)hb;
+ return strcmp(a->key, b->key);
+}
+
+void
+main(int argc, char **argv)
+{+ Hmap *h;
+ Tnode a, b;
+ Tnode *r;
+
+ 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);
+ print("%H", h);+ hmapfree(h);
+ print("len, cap: %d %d\n", h->len, h->cap);+ print("pass\n");+}