commit 49719f031078c344de3c21a8ed4ed94f6e3705bb
parent f4aee9ea236a3793e55a2133c53d4565760d2085
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 9 Apr 2023 10:19:31 -0400
Enforce C99 compliance and no memory leaks
Diffstat:
18 files changed, 123 insertions(+), 59 deletions(-)
diff --git a/README.md b/README.md
@@ -1,3 +1,5 @@
## Advent Of Code 2019
-Solutions to the annual [coding advent calendar](https://adventofcode.com) written in C.
+Solutions to the annual [coding advent calendar](https://adventofcode.com) written in [C](https://en.wikipedia.org/wiki/C_(programming_language)).
+
+The version of the C standard used to compile the code is `C99`.
diff --git a/src/03/main.c b/src/03/main.c
@@ -75,6 +75,18 @@ parse_lines(const char **pos, const char *end)
return start;
}
+void
+free_lines(struct line *line)
+{
+ struct line *next;
+
+ while (line) {
+ next = line->next;
+ free(line);
+ line = next;
+ }
+}
+
int
do_intersect(struct line *l1, struct line *l2)
{
@@ -184,6 +196,9 @@ part1(void)
aoc_debug("dist(%i, %i) = %i\n", x, y, ABS(x) + ABS(y));
aoc.answer = aprintf("%i", ABS(x) + ABS(y));
aoc.solution = "209";
+
+ free_lines(lines1);
+ free_lines(lines2);
}
void
@@ -219,4 +234,7 @@ part2(void)
aoc_debug("steps(%i, %i) = %i\n", x, y, d);
aoc.answer = aprintf("%i", d);
aoc.solution = "43258";
+
+ free_lines(lines1);
+ free_lines(lines2);
}
diff --git a/src/10/main.c b/src/10/main.c
@@ -156,7 +156,7 @@ float
angle(const struct asteroid *a, const struct asteroid *base)
{
if (a->x == base->x)
- return a->y > base->y ? 0 : -(float)M_PI;
+ return a->y > base->y ? 0 : -(float) 3.1415926;
return (float) atan2(base->x - a->x, a->y - base->y);
}
diff --git a/src/18/main.c b/src/18/main.c
@@ -463,7 +463,7 @@ state_alloc(const struct vec2i *pos, size_t dist, uint32_t acquired)
}
bool
-state_dist_ordering(struct list_link *_a, struct list_link *_b)
+state_dist_ordering(const struct list_link *_a, const struct list_link *_b)
{
struct state *a, *b;
@@ -535,6 +535,7 @@ min_dist_all_keys(struct hmap *graph, const struct vec2i *start, size_t keycnt)
struct prog *prog;
struct node *node;
struct vec2i *pos;
+ size_t mdist;
/*
* - dijkstra from starting node
@@ -550,7 +551,7 @@ min_dist_all_keys(struct hmap *graph, const struct vec2i *start, size_t keycnt)
&stdlib_strict_heap_allocator);
cstate = state_alloc(start, 0, 0);
- list_push_back(&active, &cstate->link);
+ list_insert_back(&active, &cstate->link);
pos = memdup(start, sizeof(struct vec2i));
dvec_alloc(&progs, sizeof(struct prog), 1,
@@ -566,11 +567,14 @@ min_dist_all_keys(struct hmap *graph, const struct vec2i *start, size_t keycnt)
sort_edges(&node->edges);
}
+ mdist = 0;
while (!list_empty(&active)) {
list_link = list_front(&active);
cstate = LIST_UPCAST(list_link, struct state, link);
- if (cstate->acquired == (1U << keycnt) - 1)
- return cstate->dist;
+ if (cstate->acquired == (1U << keycnt) - 1) {
+ mdist = cstate->dist;
+ goto exit;
+ }
list_link_pop(list_link);
@@ -601,6 +605,7 @@ min_dist_all_keys(struct hmap *graph, const struct vec2i *start, size_t keycnt)
free(cstate);
}
+exit:
for (HMAP_ITER(&distmap, &iter)) {
free(iter.link->key._p);
dvec_free(iter.link->value._p);
@@ -608,7 +613,7 @@ min_dist_all_keys(struct hmap *graph, const struct vec2i *start, size_t keycnt)
hmap_deinit(&distmap);
list_free_items(&active, free, LIST_OFFSET(struct state, link));
- return 0;
+ return mdist;
}
void
@@ -638,7 +643,7 @@ state_multi_alloc(const struct vec2i *pos, size_t dist, uint32_t acquired)
}
bool
-state_multi_dist_ordering(struct list_link *_a, struct list_link *_b)
+state_multi_dist_ordering(const struct list_link *_a, const struct list_link *_b)
{
struct state_multi *a, *b;
@@ -721,6 +726,7 @@ min_dist_all_keys_multi(struct hmap *graphs, const struct vec2i *starts, size_t
struct prog *prog;
struct node *node;
struct vec2i *pos;
+ size_t mdist;
size_t i;
/*
@@ -737,7 +743,7 @@ min_dist_all_keys_multi(struct hmap *graphs, const struct vec2i *starts, size_t
&stdlib_strict_heap_allocator);
cstate = state_multi_alloc(starts, 0, 0);
- list_push_back(&active, &cstate->link);
+ list_insert_back(&active, &cstate->link);
pos = memdup(starts, sizeof(struct vec2i) * 4);
dvec_alloc(&progs, sizeof(struct prog), 1,
@@ -755,11 +761,14 @@ min_dist_all_keys_multi(struct hmap *graphs, const struct vec2i *starts, size_t
}
}
+ mdist = 0;
while (!list_empty(&active)) {
list_link = list_front(&active);
cstate = LIST_UPCAST(list_link, struct state_multi, link);
- if (cstate->acquired == (1U << keycnt) - 1)
- return cstate->dist;
+ if (cstate->acquired == (1U << keycnt) - 1) {
+ mdist = cstate->dist;
+ goto exit;
+ }
list_link_pop(list_link);
@@ -793,6 +802,7 @@ min_dist_all_keys_multi(struct hmap *graphs, const struct vec2i *starts, size_t
free(cstate);
}
+exit:
for (HMAP_ITER(&distmap, &hmap_iter)) {
free(hmap_iter.link->key._p);
dvec_free(hmap_iter.link->value._p);
@@ -800,7 +810,7 @@ min_dist_all_keys_multi(struct hmap *graphs, const struct vec2i *starts, size_t
hmap_deinit(&distmap);
list_free_items(&active, free, LIST_OFFSET(struct state_multi, link));
- return 0;
+ return mdist;
}
void
@@ -837,9 +847,8 @@ part1(void)
}
hmap_deinit(&graph);
- for (HMAP_ITER(&map, &iter)) {
+ for (HMAP_ITER(&map, &iter))
free(iter.link->key._p);
- }
hmap_deinit(&map);
}
@@ -891,8 +900,7 @@ part2(void)
hmap_deinit(&graphs[i]);
}
- for (HMAP_ITER(&map, &hmap_iter)) {
+ for (HMAP_ITER(&map, &hmap_iter))
free(hmap_iter.link->key._p);
- }
hmap_deinit(&map);
}
diff --git a/src/19/main.c b/src/19/main.c
@@ -78,6 +78,7 @@ part1(void)
aoc.answer = aprintf("%lu", answer);
aoc.solution = "141";
+ icc_deinit(&save);
icc_deinit(&icc);
}
@@ -148,6 +149,7 @@ skip:
exit:
aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "15641348";
dvec_deinit(&ends);
icc_deinit(&save);
diff --git a/src/20/part1.c b/src/20/part1.c
@@ -168,7 +168,7 @@ min_dist(struct hmap *map, struct hmap *portals,
struct hmap_iter hmap_iter;
struct djk_state *state;
struct vec2i *key, npos;
- size_t i;
+ size_t mdist, i;
list_init(&active);
hmap_init(&distmap, 256, vec2i_hmap_hash, vec2i_hmap_keycmp,
@@ -183,12 +183,16 @@ min_dist(struct hmap *map, struct hmap *portals,
hmap_add(&distmap, (struct hmap_key) {.p = key},
(struct hmap_val) {.s = 0});
+ mdist = 0;
while (!list_empty(&active)) {
- list_link = list_pop_front(&active);
+ list_link = list_front(&active);
state = LIST_UPCAST(list_link, struct djk_state, link);
+ if (vec2i_eql(&state->pos, end)) {
+ mdist = state->dist;
+ goto exit;
+ }
- if (vec2i_eql(&state->pos, end))
- return state->dist;
+ list_link_pop(list_link);
hmap_link = hmap_get(&distmap, (struct hmap_key) {.p = &state->pos});
assert(hmap_link);
@@ -215,13 +219,13 @@ min_dist(struct hmap *map, struct hmap *portals,
free(state);
}
- for (HMAP_ITER(&distmap, &hmap_iter)) {
+exit:
+ for (HMAP_ITER(&distmap, &hmap_iter))
free(hmap_iter.link->key._p);
- }
hmap_deinit(&distmap);
list_free_items(&active, free, LIST_OFFSET(struct djk_state, link));
- return 0;
+ return mdist;
}
void
@@ -246,6 +250,7 @@ part1(void)
answer = min_dist(&map, &portals, &start, &end);
aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "656";
for (HMAP_ITER(&portals, &iter))
free(iter.link->key._p);
diff --git a/src/20/part2.c b/src/20/part2.c
@@ -195,7 +195,7 @@ min_dist(struct hmap *map, struct hmap *portals,
struct hmap_iter hmap_iter;
struct djk_state *state;
struct vec3i *key, npos;
- size_t i, id;
+ size_t mdist, i, id;
list_init(&active);
hmap_init(&distmap, 256, vec3i_hmap_hash, vec3i_hmap_keycmp,
@@ -210,11 +210,15 @@ min_dist(struct hmap *map, struct hmap *portals,
hmap_add(&distmap, (struct hmap_key) {.p = key},
(struct hmap_val) {.s = 0});
+ mdist = 0;
while (!list_empty(&active)) {
list_link = list_front(&active);
state = LIST_UPCAST(list_link, struct djk_state, link);
- if (vec3i_eql(&state->pos, end))
- return state->dist;
+ if (vec3i_eql(&state->pos, end)) {
+ mdist = state->dist;
+ goto exit;
+ }
+
list_link_pop(list_link);
aoc_debug("ACTIVE (%lu) %li %li %li\n",
@@ -266,13 +270,13 @@ min_dist(struct hmap *map, struct hmap *portals,
free(state);
}
- for (HMAP_ITER(&distmap, &hmap_iter)) {
+exit:
+ for (HMAP_ITER(&distmap, &hmap_iter))
free(hmap_iter.link->key._p);
- }
hmap_deinit(&distmap);
list_free_items(&active, free, LIST_OFFSET(struct djk_state, link));
- return 0;
+ return mdist;
}
void
@@ -298,6 +302,7 @@ part2(void)
answer = min_dist(&map, &portals, &start, &end);
aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "7114";
for (HMAP_ITER(&portals, &iter))
free(iter.link->key._p);
diff --git a/src/21/main.c b/src/21/main.c
@@ -72,6 +72,7 @@ part1(void)
assert(icc.state == ICC_OUTPUT);
aoc.answer = aprintf("%lu", mi_cast_ul(&icc.out));
+ aoc.solution = "19358262";
icc_deinit(&icc);
}
@@ -97,6 +98,7 @@ part2(void)
assert(icc.state == ICC_OUTPUT);
aoc.answer = aprintf("%lu", mi_cast_ul(&icc.out));
+ aoc.solution = "1142686742";
icc_deinit(&icc);
}
diff --git a/src/22/part2.c b/src/22/part2.c
@@ -97,4 +97,5 @@ part2(void)
answer = imul((target + count - off) % count, modinv(mul, count), count);
aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "73394009116480";
}
diff --git a/src/23/main.c b/src/23/main.c
@@ -32,8 +32,11 @@ feed_input(struct icc *icc, mi_ul imm)
}
void
-free_packet(struct packet *packet)
+free_packet(void *p)
{
+ struct packet *packet;
+
+ packet = p;
mi_deinit(&packet->x);
mi_deinit(&packet->y);
free(packet);
@@ -149,23 +152,18 @@ nic_tick(struct icc *icc, struct list *queues, size_t ip)
void
part1(void)
{
- struct list queues[256];
+ struct list queues[50];
struct icc icc[50];
- struct list_link *link;
- struct packet *packet;
char buf[64];
size_t i;
for (i = 0; i < 50; i++) {
+ list_init(&queues[i]);
icc_init(&icc[i]);
icc_parse_inst(&icc[i], aoc.input, aoc.input_size);
feed_input(&icc[i], (mi_ul) i);
}
- for (i = 0; i < 256; i++) {
- list_init(&queues[i]);
- }
-
while (!nat_avail) {
aoc_debug("-- TICK --\n");
for (i = 0; i < 50; i++)
@@ -176,16 +174,13 @@ part1(void)
aoc.answer = aprintf("%s", buf);
aoc.solution = "20225";
- for (i = 0; i < 256; i++) {
- for (LIST_ITER(&queues[i], link)) {
- packet = LIST_UPCAST(link, struct packet, link);
- free_packet(packet);
- }
- list_clear(&queues[i]);
- }
-
- for (i = 0; i < 50; i++)
+ mi_deinit(&nat_packet.x);
+ mi_deinit(&nat_packet.y);
+ for (i = 0; i < 50; i++) {
+ list_free_items(&queues[i], free_packet,
+ LIST_OFFSET(struct packet, link));
icc_deinit(&icc[i]);
+ }
}
void
@@ -193,7 +188,6 @@ part2(void)
{
struct list queues[256];
struct icc icc[50];
- struct list_link *link;
struct packet *packet;
size_t answer;
size_t last;
@@ -230,13 +224,13 @@ part2(void)
}
aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "14348";
+ mi_deinit(&nat_packet.x);
+ mi_deinit(&nat_packet.y);
for (i = 0; i < 50; i++) {
- for (LIST_ITER(&queues[i], link)) {
- packet = LIST_UPCAST(link, struct packet, link);
- free_packet(packet);
- }
- list_clear(&queues[i]);
+ list_free_items(&queues[i], free_packet,
+ LIST_OFFSET(struct packet, link));
icc_deinit(&icc[i]);
}
}
diff --git a/src/24/part1.c b/src/24/part1.c
@@ -140,6 +140,7 @@ part1(void)
}
aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "30446641";
dvec_deinit(&ids);
free(next);
diff --git a/src/24/part2.c b/src/24/part2.c
@@ -281,6 +281,7 @@ part2(void)
answer = map_count(&map);
aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "1985";
for (HMAP_ITER(&map, &iter))
free(iter.link->value._p);
diff --git a/src/25/main.c b/src/25/main.c
@@ -518,7 +518,12 @@ part1(void)
exit:
for (HMAP_ITER(&map, &iter)) {
free(iter.link->key._p);
- free(iter.link->value._p);
+ room = iter.link->value._p;
+ free(room->name);
+ for (DVEC_ITER(&room->items, name))
+ free(*name);
+ dvec_deinit(&room->items);
+ free(room);
}
hmap_deinit(&map);
@@ -528,8 +533,7 @@ exit:
}
hmap_deinit(&states);
- for (DVEC_ITER(&items, name))
- free(*name);
+ dvec_deinit(&taken);
dvec_deinit(&items);
dvec_deinit(&out);
diff --git a/src/Makefile b/src/Makefile
@@ -4,7 +4,7 @@ CFLAGS += -I lib/liblist/include
CFLAGS += -Wunused-variable -Wunused-function -Wformat
CFLAGS += -Wconversion -Wsign-compare
-CFLAGS += -I common -g -Werror
+CFLAGS += -I common -g -Werror -std=c99
ifeq "$(DEBUG)" "1"
CFLAGS += -DLIBDVEC_ASSERT_ARGS -DLIBDVEC_ASSERT_ALLOC
@@ -45,6 +45,7 @@ lib/libpq/build/libpq.a:
define make-day
all:: $1/main
run:: $1/run
+debug:: $1/debug
$1/main: $($(1)_SRC) $($(1)_HDR)
$(CC) -o $1/main $($(1)_SRC) $(CFLAGS) $($(1)_CFLAGS) \
$(LDFLAGS) $($(1)_LDFLAGS) $(LDLIBS) $($(1)_LDLIBS)
@@ -53,6 +54,13 @@ $1/run: $1/main
@echo -en "\npart 1: " && cd $1 && time ./main 1
@echo -en "\npart 2: " && cd $1 && time ./main 2
@echo ""
+$1/debug: $1/main
+ @echo "== day $1 part 1 =="
+ @cd $1 && valgrind --error-exitcode=1 --leak-check=full \
+ --show-leak-kinds=all ./main 1
+ @echo "== day $1 part 2 =="
+ @cd $1 && valgrind --error-exitcode=1 --leak-check=full \
+ --show-leak-kinds=all ./main 2
endef
$(foreach day,$(DAYS),$(eval $(call make-day,$(day))))
@@ -65,4 +73,4 @@ cleanall: clean
make -C lib/libmaxint clean
make -C lib/liballoc clean
-.PHONY: all clean cleanall
+.PHONY: all run debug clean cleanall
diff --git a/src/common/dvec_s.h b/src/common/dvec_s.h
@@ -30,7 +30,7 @@ dvec_rm_slot(struct dvec *dvec, void *slot)
dvec_rm_slots(dvec, slot, 1);
}
-static ssize_t
+static inline ssize_t
dvec_sprintf(struct dvec *dvec, const char *fmtstr, ...)
{
va_list ap, cpy;
diff --git a/src/common/util.c b/src/common/util.c
@@ -80,6 +80,17 @@ aprintf(const char *fmtstr, ...)
}
char *
+strdup(const char *str)
+{
+ char *alloc;
+
+ alloc = malloc(strlen(str) + 1);
+ strcpy(alloc, str);
+
+ return alloc;
+}
+
+char *
apprintf(char *str, const char *fmtstr, ...)
{
va_list ap, cpy;
diff --git a/src/common/util.h b/src/common/util.h
@@ -5,6 +5,7 @@
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
+#include <stdint.h>
#include <stdlib.h>
#define ARRLEN(x) (sizeof(x) / sizeof(*(x)))
@@ -25,6 +26,7 @@ bool readtok(char *buf, size_t buflen,
int64_t parsei64(const char *str);
char *aprintf(const char *fmtstr, ...);
+char *strdup(const char *str);
char *apprintf(char *alloc, const char *fmtstr, ...);
void *memdup(const void *data, size_t size);
diff --git a/src/common/vec.h b/src/common/vec.h
@@ -1,6 +1,6 @@
#include <string.h>
#include <stdbool.h>
-#include <stdlib.h>
+#include <sys/types.h>
#define VEC_ABS(x) ((x) > 0 ? (x) : -(x))
