ref: f0ee06d3ea3901d66c2be3e8d4b48511f82a9b84
parent: 322c0644767d483159be5a07002d36f07ef0172d
author: qwx <qwx@sciops.net>
date: Sun May 29 20:17:56 EDT 2022
add hash/knr: simplest string hashing, from k&r 2e
--- /dev/null
+++ b/hash/knr.c
@@ -1,0 +1,56 @@
+#include <u.h>
+#include <libc.h>
+#include "asif.h"
+
+/* k&r 2e pp.143-145 */
+
+static int
+hash(char *s)
+{+ char c;
+ uint h;
+
+ for(h=0, c=*s++; c!=0; c=*s++)
+ h = c + 31 * h;
+ return h;
+}
+
+void *
+htget(HTab *ht, char *key)
+{+ HPair *k;
+
+ if(ht == nil)
+ return nil;
+ for(k=ht->b[hash(key)].next; k!=nil; k=k->next)
+ if(strcmp(key, k->key) == 0)
+ return k->val;
+ return nil;
+}
+
+void
+htput(HTab *ht, char *key, void *val)
+{+ HPair *kp, *k;
+
+ if(ht == nil)
+ return;
+ for(kp=&ht->b[hash(key)], k=kp->next; k!=nil; kp=k, k=k->next)
+ if(strcmp(key, k->key) == 0){+ k->val = val;
+ return;
+ }
+ k = emalloc(sizeof *k);
+ k->key = estrdup(key);
+ k->val = val;
+ kp->next = k;
+}
+
+HTab *
+htalloc(void)
+{+ HTab *ht;
+
+ ht = emalloc(sizeof *ht);
+ return ht;
+}