commit 621ce7dc93cd7d4ad8ace0842b910ecb2feb151b
parent c8754bf04f3274926474b81b7e28dba748a53eb4
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 5 Nov 2021 22:34:34 +0100
Add hashmap implementation
Diffstat:
5 files changed, 186 insertions(+), 58 deletions(-)
diff --git a/libs/Makefile b/libs/Makefile
@@ -15,7 +15,7 @@ build/%.o: src/%.c include/%.h | build
build/wrapper.o: src/wrapper.c
$(CC) -c -o $@ $< $(CFLAGS) $(LDLIBS)
-build/libaoc.a: build/util.o build/aoc.o build/wrapper.o build/memvec.o build/icc.o
+build/libaoc.a: build/util.o build/aoc.o build/wrapper.o build/memvec.o build/icc.o build/hashmap.o
ar rcs $@ $^
build/test_%: tests/%.c
diff --git a/libs/include/hashmap.h b/libs/include/hashmap.h
@@ -0,0 +1,43 @@
+#include "util.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+
+#define HASHMAP_KEY(v, len) ((struct hashmap_key) { (void*) (v), (len) })
+
+struct hashmap_key {
+ void *key;
+ int len;
+};
+
+struct hashmap_link {
+ struct hashmap_key key;
+ void *value;
+
+ struct hashmap_link *next;
+};
+
+struct hashmap_iter {
+ struct hashmap_link *link;
+ int bucket;
+};
+
+struct hashmap {
+ struct hashmap_link **buckets;
+ int size;
+
+ uint32_t (*hash)(void *key, int len);
+};
+
+void hashmap_init(struct hashmap *hm, int size, uint32_t (*hasher)(void *key, int len));
+void hashmap_free(struct hashmap *hm);
+
+void hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value);
+void * hashmap_get(struct hashmap *hm, struct hashmap_key key);
+void * hashmap_pop(struct hashmap *hm, struct hashmap_key key);
+
+struct hashmap_iter hashmap_iter(void);
+int hashmap_next(struct hashmap *hm, struct hashmap_iter *next);
+
+uint32_t hashmap_string_hasher(void *key, int len);
diff --git a/libs/src/hashmap.c b/libs/src/hashmap.c
@@ -0,0 +1,125 @@
+#include "hashmap.h"
+
+void
+hashmap_init(struct hashmap *hm, int size, uint32_t (*hasher)(void *key, int len))
+{
+ if (!size) size = 20;
+ hm->size = size;
+ hm->buckets = CHKP(malloc(hm->size * sizeof(struct hashmap_link *)));
+ hm->hash = hasher;
+ memset(hm->buckets, 0, hm->size * sizeof(struct hashmap_link *));
+}
+
+void
+hashmap_free(struct hashmap *hm)
+{
+ struct hashmap_iter iter;
+ struct hashmap_link *prev;
+
+ prev = NULL;
+ iter = hashmap_iter();
+ while (hashmap_next(hm, &iter)) {
+ free(iter.link->key.key);
+ free(prev);
+ prev = iter.link;
+ }
+ free(prev);
+ free(hm->buckets);
+ hm->buckets = NULL;
+}
+
+void
+hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value)
+{
+ struct hashmap_link **iter;
+
+ iter = &hm->buckets[hm->hash(key.key, key.len) % hm->size];
+ while (*iter) iter = &((*iter)->next);
+
+ *iter = CHKP(malloc(sizeof(struct hashmap_link)));
+ (*iter)->key = key;
+ (*iter)->value = value;
+ (*iter)->next = NULL;
+}
+
+void *
+hashmap_get(struct hashmap *hm, struct hashmap_key key)
+{
+ struct hashmap_link **iter;
+ struct hashmap_key ckey;
+
+ iter = &hm->buckets[hm->hash(key.key, key.len) % hm->size];
+ while (*iter) {
+ ckey = (*iter)->key;
+ if (ckey.len == key.len && !memcmp(ckey.key, key.key, key.len))
+ return (*iter)->value;
+ iter = &((*iter)->next);
+ }
+
+ return NULL;
+}
+
+void *
+hashmap_pop(struct hashmap *hm, struct hashmap_key key)
+{
+ struct hashmap_link **iter;
+ struct hashmap_key ckey;
+ void *value;
+
+ iter = &hm->buckets[hm->hash(key.key, key.len) % hm->size];
+ while (*iter) {
+ ckey = (*iter)->key;
+ if (ckey.len == key.len && !memcmp(ckey.key, key.key, key.len)) {
+ *iter = (*iter)->next;
+ value = (*iter)->value;
+ free(*iter);
+ return value;
+ }
+ iter = &((*iter)->next);
+ }
+
+ return NULL;
+}
+
+struct hashmap_iter
+hashmap_iter(void)
+{
+ return (struct hashmap_iter) { NULL, -1 };
+}
+
+int
+hashmap_next(struct hashmap *hm, struct hashmap_iter *iter)
+{
+ int i;
+
+ if (iter->link && iter->link->next) {
+ iter->link = iter->link->next;
+ return 1;
+ }
+
+ for (i = iter->bucket + 1; i < hm->size; i++) {
+ if (hm->buckets[i]) {
+ iter->bucket = i;
+ iter->link = hm->buckets[i];
+ return 1;
+ }
+ }
+
+ iter->link = NULL;
+ return 0;
+}
+
+uint32_t
+hashmap_string_hasher(void *key, int len)
+{
+ uint32_t hash;
+ uint8_t *data;
+ int i;
+
+ hash = 0;
+ data = key;
+ for (i = 0; i < len; i++)
+ hash = 31 * hash + data[i];
+
+ return hash;
+}
diff --git a/src/day6/main.c b/src/day6/main.c
@@ -1,8 +1,10 @@
#include "aoc.h"
#include "memvec.h"
+#include "hashmap.h"
#include <stdlib.h>
#include <stdio.h>
+#include <stdint.h>
#include <string.h>
struct planet {
@@ -11,23 +13,12 @@ struct planet {
struct memvec children;
};
-struct memvec planets;
-
-// TODO: implement hashmap to replace array search
+struct hashmap planets;
struct planet *
get_planet(const char *name)
{
- struct planet *p;
- int i;
-
- for (i = 0; i < memvec_len(&planets); i++) {
- p = MEMVEC_GET(&planets, i, struct planet *);
- if (!strcmp(p->name, name))
- return p;
- }
-
- return NULL;
+ return hashmap_get(&planets, HASHMAP_KEY(name, strlen(name)));
}
struct planet *
@@ -39,7 +30,7 @@ add_planet(const char *name)
p->name = CHKP(strdup(name));
p->parent = NULL;
ASSERT(memvec_init(&p->children, 3, sizeof(struct planet *)) == OK);
- CHKP(memvec_add(&planets, &p));
+ hashmap_set(&planets, HASHMAP_KEY(CHKP(strdup(name)), strlen(name)), p);
return p;
}
@@ -50,7 +41,7 @@ init_planets()
char *tok, *sep, *next;
struct planet *parent, *child;
- memvec_init(&planets, 100, sizeof(struct planet *));
+ hashmap_init(&planets, 100, hashmap_string_hasher);
tok = aoc.input;
do {
@@ -77,29 +68,33 @@ init_planets()
void
free_planets()
{
+ struct hashmap_iter iter;
struct planet *p;
- int i;
- for (i = 0; i < memvec_len(&planets); i++) {
- p = MEMVEC_GET(&planets, i, struct planet *);
+ iter = hashmap_iter();
+ while (hashmap_next(&planets, &iter)) {
+ p = iter.link->value;
memvec_free(&p->children);
free(p->name);
free(p);
}
- memvec_free(&planets);
+
+ hashmap_free(&planets);
}
void
part1(void)
{
+ struct hashmap_iter iter;
struct planet *p;
- int i, orbits;
+ int orbits;
init_planets();
orbits = 0;
- for (i = 0; i < memvec_len(&planets); i++) {
- p = MEMVEC_GET(&planets, i, struct planet *);
+ iter = hashmap_iter();
+ while (hashmap_next(&planets, &iter)) {
+ p = iter.link->value;
while (p->parent) {
orbits += 1;
p = p->parent;
diff --git a/src/day7/2 b/src/day7/2
@@ -1,35 +0,0 @@
-#include "aoc.h"
-#include "icc.h"
-
-#include <stdlib.h>
-#include <stdio.h>
-
-void
-run_amp(int phase, int input, int *out)
-{
-
-}
-
-void
-part1(void)
-{
- struct icc icc;
- void *inst;
-
- ASSERT(icc_init(&icc) == OK);
- ASSERT(icc_parse_inst(&icc, aoc.input, aoc.input_size) == OK);
- inst = icc_inst_copy(&icc);
-
-
- icc_reset(&icc, inst);
- while (icc.status != ICC_HALT)
- icc_step_inst(&icc);
-
- icc_free(&icc);
-}
-
-void
-part2(void)
-{
-
-}
