commit db4cc51666ac8f7a698d6f9989df882f5a1f82c7
parent 4a078d7bc922a6eb56a9e32c75dda0a90d06808f
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 17 Mar 2023 19:27:50 +0100
Fixup day 6
Diffstat:
18 files changed, 73 insertions(+), 521 deletions(-)
diff --git a/.gdb_history b/.gdb_history
@@ -1,5 +0,0 @@
-c
-r
-context
-set follow-fork-mode child
-r
diff --git a/.gitignore b/.gitignore
@@ -4,3 +4,4 @@ main
.cache
build
vgcore*
+.gdb_history
diff --git a/.gitmodules b/.gitmodules
@@ -1,9 +1,12 @@
[submodule "lib/libdvec"]
- path = src/lib/libdvec
+ path = lib/libdvec
url = git@sinitax.com:snx/libdvec
-[submodule "lib/libhashmap"]
- path = src/lib/libhashmap
- url = git@sinitax.com:snx/libhashmap
[submodule "lib/libmaxint"]
- path = src/lib/libmaxint
+ path = lib/libmaxint
url = git@sinitax.com:snx/libmaxint
+[submodule "lib/libhashmap"]
+ path = lib/libhashmap
+ url = git@sinitax.com:snx/libhashmap
+[submodule "lib/liballoc"]
+ path = lib/liballoc
+ url = git@sinitax.com:snx/liballoc
diff --git a/04/.gdb_history b/04/.gdb_history
@@ -1,2 +0,0 @@
-r
-f 399
diff --git a/06/Makefile b/06/Makefile
@@ -1,12 +0,0 @@
-CFLAGS = -g -I ../../libs/include -L ../../libs/build
-LDLIBS = -laoc
-
-all: lib main
-
-clean:
- rm main
-
-lib:
- make -C ../../libs
-
-main: main.c ../../libs/build/libaoc.a
diff --git a/06/info.mk b/06/info.mk
@@ -0,0 +1,4 @@
+06_SRC = 06/main.c common/main.c common/aoc.c common/util.c
+06_SRC += lib/libdvec/build/libdvec.a lib/libhashmap/build/libhashmap.a
+06_SRC += lib/liballoc/build/liballoc.a
+06_HDR = common/aoc.h common/util.h
diff --git a/06/main.c b/06/main.c
@@ -1,16 +1,19 @@
#include "aoc.h"
-#include "memvec.h"
+#include "dvec.h"
#include "hashmap.h"
+#include "allocator.h"
+#include "util.h"
-#include <stdlib.h>
+#include <errno.h>
#include <stdio.h>
-#include <stdint.h>
#include <string.h>
+#include <stdint.h>
+#include <stdlib.h>
struct planet {
char *name;
struct planet *parent;
- struct memvec children;
+ struct dvec children;
};
struct hashmap planets;
@@ -21,8 +24,8 @@ get_planet(const char *name)
struct hashmap_link *link;
int status;
- status = hashmap_get(&planets, HASHMAP_KEY(name, strlen(name)), &link);
- return status ? link->value : NULL;
+ link = hashmap_get(&planets, name, strlen(name));
+ return link ? link->value : NULL;
}
struct planet *
@@ -30,11 +33,15 @@ add_planet(const char *name)
{
struct planet *p;
- p = CHKP(malloc(sizeof(struct planet)));
- p->name = CHKP(strdup(name));
+ p = malloc(sizeof(struct planet));
+ if (!p) die("main: add_planet: malloc");
+
+ p->name = aprintf("%s", name);
p->parent = NULL;
- ASSERT(memvec_init(&p->children, 3, sizeof(struct planet *)) == OK);
- hashmap_set(&planets, HASHMAP_KEY(CHKP(strdup(name)), strlen(name)), p);
+ dvec_init(&p->children, sizeof(struct planet *), 3);
+
+ hashmap_set(&planets, aprintf("%s", name), strlen(name),
+ p, sizeof(struct planet));
return p;
}
@@ -42,48 +49,48 @@ add_planet(const char *name)
void
init_planets()
{
- char *tok, *sep, *next;
- struct planet *parent, *child;
+ struct planet *parent, *child, **slot;
+ const char *pos, *end;
+ char buf[256], *sep;
+ int rc;
- hashmap_init(&planets, 100, hashmap_string_hasher);
+ hashmap_init(&planets, 100, hashmap_str_hasher, &stdlib_heap_allocator);
- tok = aoc.input;
- do {
- next = strchr(tok, '\n');
- if (!next) break;
+ pos = aoc.input;
+ end = aoc.input + aoc.input_size;
+ while (readtok(buf, sizeof(buf), '\n', &pos, end)) {
+ sep = strchr(buf, ')');
+ if (!sep) die("main: bad format");
+ *sep = '\0';
- sep = CHKP(strchr(tok, ')'));
- *next = *sep = '\0';
+ parent = get_planet(buf);
+ if (!parent) parent = add_planet(buf);
- parent = get_planet(tok);
- if (!parent) parent = add_planet(tok);
+ child = get_planet(sep + 1);
+ if (!child) child = add_planet(sep + 1);
- child = get_planet(sep+1);
- if (!child) child = add_planet(sep+1);
+ slot = dvec_add_slot(&parent->children, &rc);
+ if (rc) die("main: dvec_add_slot");
+ *slot = child;
- CHKP(memvec_add(&parent->children, child));
- ASSERT(child->parent == NULL);
+ if (child->parent) die("main unexpected parent");
child->parent = parent;
-
- tok = next + 1;
- } while (next);
+ }
}
void
-free_planets()
+deinit_planets()
{
struct hashmap_iter iter;
struct planet *p;
- iter = hashmap_iter();
- while (hashmap_next(&planets, &iter)) {
+ for (HASHMAP_ITER(&planets, &iter)) {
p = iter.link->value;
- memvec_free(&p->children);
+ dvec_deinit(&p->children);
free(p->name);
- free(p);
}
- hashmap_free(&planets);
+ hashmap_deinit(&planets);
}
void
@@ -96,8 +103,7 @@ part1(void)
init_planets();
orbits = 0;
- iter = hashmap_iter();
- while (hashmap_next(&planets, &iter)) {
+ for (HASHMAP_ITER(&planets, &iter)) {
p = iter.link->value;
while (p->parent) {
orbits += 1;
@@ -105,10 +111,10 @@ part1(void)
}
}
- aoc.answer = CHKP(aprintf("%i", orbits));
+ aoc.answer = aprintf("%i", orbits);
aoc.solution = "119831";
- free_planets();
+ deinit_planets();
}
void
@@ -119,8 +125,10 @@ part2(void)
init_planets();
- san = CHKP(get_planet("SAN"));
- you = CHKP(get_planet("YOU"));
+ san = get_planet("SAN");
+ if (!san) die("main: missing planet SAN");
+ you = get_planet("YOU");
+ if (!you) die("main: missing planet YOU");
for (s1 = 0, p1 = you; p1; p1 = p1->parent, s1++) {
for (s2 = 0, p2 = san; p2; p2 = p2->parent, s2++) {
@@ -130,8 +138,8 @@ part2(void)
}
exit:
- aoc.answer = CHKP(aprintf("%i", s1 + s2 - 2));
+ aoc.answer = aprintf("%i", s1 + s2 - 2);
aoc.solution = "322";
- free_planets();
+ deinit_planets();
}
diff --git a/Makefile b/Makefile
@@ -1,5 +1,6 @@
CFLAGS = -I lib/libdvec/include -I lib/libhashmap/include
-CFLAGS += -I lib/libmaxint/include -I common -g
+CFLAGS += -I lib/libmaxint/include -I lib/liballoc/include
+CFLAGS += -I common -g
DAYS = $(shell seq 1 24 | xargs printf "%02i\n")
@@ -7,14 +8,17 @@ all::
include */info.mk
+lib/liballoc/build/liballoc.a:
+ make -C lib/liballoc build/liballoc.a DEBUG=1
+
lib/libdvec/build/libdvec.a:
- make -C lib/libdvec build/libdvec.a
+ make -C lib/libdvec build/libdvec.a DEBUG=1
lib/libhashmap/build/libhashmap.a:
- make -C lib/libhashmap build/libhashmap.a
+ make -C lib/libhashmap build/libhashmap.a DEBUG=1
lib/libmaxint/build/libmaxint.a:
- make -C lib/libmaxint build/libmaxint.a
+ make -C lib/libmaxint build/libmaxint.a DEBUG=1
define make-day
all:: $1/main
diff --git a/lib/liballoc b/lib/liballoc
@@ -0,0 +1 @@
+Subproject commit 22d274eb7a43de119af51cf46a892aa6be6a7d91
diff --git a/lib/libhashmap b/lib/libhashmap
@@ -0,0 +1 @@
+Subproject commit 2cc02a318e3c42e536715e1af1213f25a2440da2
diff --git a/lib/libhashmap/.gitignore b/lib/libhashmap/.gitignore
@@ -1,5 +0,0 @@
-compile_commands.json
-build
-.cache
-vgcore*
-test
diff --git a/lib/libhashmap/LICENSE b/lib/libhashmap/LICENSE
@@ -1,21 +0,0 @@
-MIT License
-
-Copyright (c) 2023 Louis Burda
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in all
-copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-SOFTWARE.
diff --git a/lib/libhashmap/Makefile b/lib/libhashmap/Makefile
@@ -1,42 +0,0 @@
-PREFIX ?= /usr/local
-INCLDIR ?= /include
-LIBDIR ?= /lib
-
-CFLAGS = -I include -Wno-prototype -Wunused-function
-CFLAGS += -Wunused-variable -Wconversion
-
-ifeq "$(DEBUG)" "1"
-CFLAGS += -g -Dlibhashmap_CHECK_ENABLE=1
-endif
-
-all: build/libhashmap.so build/libhashmap.a build/test
-
-clean:
- rm -rf build
-
-build:
- mkdir build
-
-build/libhashmap.a: src/hashmap.c include/hashmap.h | build
- $(CC) -o build/tmp.o src/hashmap.c $(CFLAGS) -r
- objcopy --keep-global-symbols=libhashmap.api build/tmp.o build/fixed.o
- $(AR) rcs $@ build/fixed.o
-
-build/libhashmap.so: src/hashmap.c include/hashmap.h | build
- $(CC) -o $@ src/hashmap.c -fPIC $(CFLAGS) -shared \
- -Wl,-version-script libhashmap.lds
-
-build/test: src/test.c build/libhashmap.a | build
- $(CC) -o $@ $^ -I include -g
-
-install:
- install -m 644 include/hashmap.h -t "$(DESTDIR)$(PREFIX)$(INCLDIR)"
- install -m 755 build/libhashmap.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
- install -m 755 build/libhashmap.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
-
-uninstall:
- rm -f "$(DESTDIR)$(PREFIX)$(INCLDIR)/hashmap.h"
- rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libhashmap.a"
- rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libhashmap.so"
-
-.PHONY: all clean install uninstall
diff --git a/lib/libhashmap/include/hashmap.h b/lib/libhashmap/include/hashmap.h
@@ -1,53 +0,0 @@
-#pragma once
-
-#include <stdint.h>
-#include <stdbool.h>
-#include <stdlib.h>
-
-#define HASHMAP_ITER(map, iter) \
- hashmap_iter_init(iter); hashmap_iter_next(map, iter);
-
-typedef uint32_t (*map_hash_func)(const void *data, size_t size);
-
-struct hashmap_link {
- uint8_t *key;
- size_t key_size;
- uint8_t *value;
- size_t value_size;
- struct hashmap_link *next;
-};
-
-struct hashmap_iter {
- struct hashmap_link *link;
- size_t bucket;
-};
-
-struct hashmap {
- map_hash_func hash;
- struct hashmap_link **buckets;
- size_t size;
-};
-
-int hashmap_init(struct hashmap *map, size_t size, map_hash_func hasher);
-void hashmap_deinit(struct hashmap *map);
-
-int hashmap_alloc(struct hashmap **map, size_t size, map_hash_func hasher);
-void hashmap_free(struct hashmap *map);
-
-void hashmap_clear(struct hashmap *map);
-
-struct hashmap_link *hashmap_get(struct hashmap *map,
- const void *key, size_t size);
-struct hashmap_link *hashmap_pop(struct hashmap *map,
- const void *key, size_t size);
-
-void hashmap_link_set(struct hashmap_link *link, void *key, size_t key_size,
- void *value, size_t value_size);
-int hashmap_set(struct hashmap *map, void *key, size_t key_size,
- void *value, size_t value_size);
-
-void hashmap_iter_init(struct hashmap_iter *iter);
-bool hashmap_iter_next(struct hashmap *map, struct hashmap_iter *iter);
-
-uint32_t hashmap_str_hasher(const void *data, size_t size);
-
diff --git a/lib/libhashmap/libhashmap.api b/lib/libhashmap/libhashmap.api
@@ -1,15 +0,0 @@
-hashmap_init
-hashmap_deinit
-
-hashmap_clear
-
-hashmap_get
-hashmap_pop
-
-hashmap_link_set
-hashmap_set
-
-hashmap_iter_init
-hashmap_iter_next
-
-hashmap_str_hasher
diff --git a/lib/libhashmap/libhashmap.lds b/lib/libhashmap/libhashmap.lds
@@ -1,17 +0,0 @@
-LIBHASHMAP_1.1 {
- hashmap_init;
- hashmap_deinit;
-
- hashmap_clear;
-
- hashmap_get;
- hashmap_pop;
-
- hashmap_link_set;
- hashmap_set;
-
- hashmap_iter_init;
- hashmap_iter_next;
-
- hashmap_str_hasher;
-};
diff --git a/lib/libhashmap/src/hashmap.c b/lib/libhashmap/src/hashmap.c
@@ -1,264 +0,0 @@
-#include "hashmap.h"
-
-#include <errno.h>
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-
-#ifdef LIBHASHMAP_CHECK_ENABLE
-#define LIBHASHMAP_CHECK(x) libhashmap_assert((x), __FILE__, __LINE__, #x)
-#else
-#define LIBHASHMAP_CHECK(x)
-#endif
-
-static struct hashmap_link **hashmap_get_linkp(struct hashmap *map,
- const void *key, size_t size);
-static int hashmap_link_alloc(struct hashmap_link **link,
- void *key, size_t key_size, void *value, size_t value_size);
-
-static inline void libhashmap_assert(int cond,
- const char *file, int line, const char *condstr)
-{
- if (cond) return;
-
- fprintf(stderr, "libhashmap: Assertion failed at %s:%i (%s)\n",
- file, line, condstr);
- abort();
-}
-
-static inline size_t
-hashmap_key_bucket(struct hashmap *map, const void *key, size_t size)
-{
- return map->hash(key, size) % map->size;
-}
-
-static inline bool
-hashmap_key_cmp(const void *a, size_t asize, const void *b, size_t bsize)
-{
- return asize == bsize && !memcmp(a, b, asize);
-}
-
-struct hashmap_link **
-hashmap_get_linkp(struct hashmap *map, const void *key, size_t size)
-{
- struct hashmap_link **iter, *link;
-
- LIBHASHMAP_CHECK(map != NULL && key != NULL && size != 0);
-
- iter = &map->buckets[hashmap_key_bucket(map, key, size)];
- while (*iter != NULL) {
- link = *iter;
- if (hashmap_key_cmp(link->key, link->key_size, key, size))
- return iter;
- iter = &(*iter)->next;
- }
-
- return NULL;
-}
-
-int
-hashmap_link_alloc(struct hashmap_link **out, void *key, size_t key_size,
- void *value, size_t value_size)
-{
- struct hashmap_link *link;
-
- LIBHASHMAP_CHECK(key != NULL && value != NULL);
-
- link = malloc(sizeof(struct hashmap_link));
- if (!link) return -errno;
- link->key = key;
- link->key_size = key_size;
- link->value = value;
- link->value_size = value_size;
- link->next = NULL;
- *out = link;
-
- return 0;
-}
-
-int
-hashmap_init(struct hashmap *map, size_t size, map_hash_func hasher)
-{
- LIBHASHMAP_CHECK(map != NULL && size != 0 && hasher != NULL);
-
- map->buckets = calloc(size, sizeof(struct hashmap_link *));
- if (!map->buckets) return -errno;
- map->size = size;
- map->hash = hasher;
-
- return 0;
-}
-
-void
-hashmap_deinit(struct hashmap *map)
-{
- LIBHASHMAP_CHECK(map != NULL);
-
- hashmap_clear(map);
- free(map->buckets);
-}
-
-int
-hashmap_alloc(struct hashmap **map, size_t size, map_hash_func hasher)
-{
- int rc;
-
- *map = malloc(sizeof(struct hashmap));
- if (!*map) return -errno;
-
- rc = hashmap_init(*map, size, hasher);
- if (rc) {
- free(*map);
- return rc;
- }
-
- return 0;
-}
-
-void
-hashmap_free(struct hashmap *map)
-{
- hashmap_deinit(map);
- free(map);
-}
-
-void
-hashmap_clear(struct hashmap *map)
-{
- struct hashmap_iter iter;
- struct hashmap_link *prev;
- size_t i;
-
- LIBHASHMAP_CHECK(map != NULL);
-
- prev = NULL;
- for (HASHMAP_ITER(map, &iter)) {
- free(iter.link->key);
- free(iter.link->value);
- free(prev);
- prev = iter.link;
- }
- free(prev);
-
- for (i = 0; i < map->size; i++)
- map->buckets[i] = NULL;
-}
-
-struct hashmap_link *
-hashmap_get(struct hashmap *map, const void *key, size_t size)
-{
- struct hashmap_link **iter;
-
- LIBHASHMAP_CHECK(map != NULL);
-
- iter = hashmap_get_linkp(map, key, size);
-
- return iter ? *iter : NULL;
-}
-
-struct hashmap_link *
-hashmap_pop(struct hashmap *map, const void *key, size_t size)
-{
- struct hashmap_link **iter;
-
- LIBHASHMAP_CHECK(map != NULL);
-
- iter = hashmap_get_linkp(map, key, size);
- if (iter) {
- *iter = (*iter)->next;
- return *iter;
- }
-
- return NULL;
-}
-
-void
-hashmap_link_set(struct hashmap_link *link, void *key, size_t key_size,
- void *value, size_t value_size)
-{
- LIBHASHMAP_CHECK(link != NULL);
-
- free(link->key);
- link->key = key;
- link->key_size = key_size;
-
- free(link->value);
- link->value = value;
- link->value_size = value_size;
-}
-
-int
-hashmap_set(struct hashmap *map, void *key, size_t key_size,
- void *value, size_t value_size)
-{
- struct hashmap_link **iter;
- int rc;
-
- LIBHASHMAP_CHECK(map != NULL);
-
- iter = hashmap_get_linkp(map, key, key_size);
- if (iter == NULL) {
- iter = &map->buckets[hashmap_key_bucket(map, key, key_size)];
- while (*iter) iter = &((*iter)->next);
- }
-
- if (*iter) {
- hashmap_link_set(*iter, key, key_size, value, value_size);
- } else {
- rc = hashmap_link_alloc(iter, key, key_size, value, value_size);
- if (rc) return rc;
- }
-
- return 0;
-}
-
-void
-hashmap_iter_init(struct hashmap_iter *iter)
-{
- LIBHASHMAP_CHECK(iter != NULL);
-
- iter->bucket = 0;
- iter->link = NULL;
-}
-
-bool
-hashmap_iter_next(struct hashmap *map, struct hashmap_iter *iter)
-{
- size_t i;
-
- LIBHASHMAP_CHECK(map != NULL && iter != NULL);
-
- if (iter->link && iter->link->next) {
- iter->link = iter->link->next;
- return true;
- }
-
- i = iter->bucket + (iter->link ? 1 : 0);
- for (; i < map->size; i++) {
- if (map->buckets[i]) {
- iter->bucket = i;
- iter->link = map->buckets[i];
- return true;
- }
- }
-
- iter->link = NULL;
-
- return false;
-}
-
-uint32_t
-hashmap_str_hasher(const void *data, size_t size)
-{
- uint32_t hash;
- size_t i;
-
- LIBHASHMAP_CHECK(data != NULL && size > 0);
-
- hash = 5381;
- for (i = 0; i < size; i++)
- hash = 33 * hash + ((uint8_t *) data)[i];
-
- return hash;
-}
-
diff --git a/lib/libhashmap/src/test.c b/lib/libhashmap/src/test.c
@@ -1,34 +0,0 @@
-#include "hashmap.h"
-
-#include <err.h>
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-
-#define LIBHASHMAP_ERR(rc) errx(1, "libhashmap: %s", rc < 0 ? strerror(-rc) : "???")
-
-int
-main(int argc, const char **argv)
-{
- struct hashmap hashmap;
- struct hashmap_iter iter;
- void *key, *value;
- int i, rc;
-
- rc = hashmap_init(&hashmap, 10, hashmap_str_hasher);
- if (rc) LIBHASHMAP_ERR(rc);
-
- for (i = 1; i < argc; i++) {
- key = strdup(argv[i]);
- value = malloc(sizeof(int));
- memcpy(value, &i, sizeof(int));
- rc = hashmap_set(&hashmap, key, strlen(key) + 1,
- value, sizeof(int));
- if (rc) LIBHASHMAP_ERR(rc);
- }
-
- for (HASHMAP_ITER(&hashmap, &iter))
- printf("%s: %i\n", iter.link->key, *(int*)iter.link->value);
-
- hashmap_deinit(&hashmap);
-}
