Solve puzzle 7 part 1

2 files changed, 335 insertions, 1 deletions

diff --git a/7.c b/7.c
new file mode 100644
index 0000000..d19b51d
--- /dev/null
+++ b/7.c
@@ -0,0 +1,333 @@
+
+#include <dirent.h>
+#include <regex.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+//#define DENT_DUMP
+
+struct dent {
+	int type;
+	size_t size;
+	struct dent * parent;
+	struct dent * next;
+	struct dent * child;
+	char name[];
+};
+
+
+// Create a new directory entry. Insert it into the tree if parent is given.
+struct dent *
+dent_create(int type, size_t size, struct dent * parent, char const * name)
+{
+	int namelen;
+	struct dent * d;
+
+	if (!name)
+		return NULL;
+
+	namelen = strlen(name);
+	d = malloc(sizeof(struct dent) + namelen + 1);
+	if (!d)
+		return NULL;
+
+	d->type = type;
+	d->size = size;
+	d->parent = parent;
+	if (parent) {
+		d->next = d->parent->child;
+		d->parent->child = d;
+	}
+	else {
+		d->next = NULL;
+	}
+	d->child = NULL;
+	memcpy(d->name, name, namelen + 1);
+
+	return d;
+}
+
+
+// Free a directory entry and its children
+void
+dent_free(struct dent * d)
+{
+	if (!d)
+		return;
+
+	dent_free(d->child);
+	dent_free(d->next);
+	free(d);
+}
+
+
+// Find a directory entry by name, in parent only (not recursive)
+struct dent *
+dent_find(struct dent * parent, char const * name)
+{
+	struct dent * d;
+
+	for (d = parent->child; d != NULL; d = d->next) {
+		if (strcmp(d->name, name) == 0) {
+			return d;
+		}
+	}
+
+	return NULL;
+}
+
+
+// Find the next entry for walking an entire directory tree.
+struct dent *
+dent_next(struct dent * d)
+{
+	if (!d)
+		return NULL;
+
+	if (d->child)
+		return d->child;
+	if (d->next)
+		return d->next;
+
+	while ((d = d->parent) != NULL)
+		if (d->next)
+			return d->next;
+
+	return NULL;
+}
+
+
+// Get the recursive usage of a directory entry.
+//
+// This caches directory sizes in their dents.
+size_t
+dent_du(struct dent * d)
+{
+	struct dent * child;
+
+	switch (d->type) {
+	case DT_REG:
+		return d->size;
+
+	case DT_DIR:
+		d->size = 0;
+		for (child = d->child; child != NULL; child = child->next) {
+			d->size += dent_du(child);
+		}
+		return d->size;
+	}
+
+	return 0;
+}
+
+
+#ifdef DENT_DUMP
+void
+dent_dump(FILE * out, struct dent * d, int depth)
+{
+	struct dent * child;
+
+	if (!d)
+		return;
+
+	fprintf(out, "%*s %s", depth * 2, "-", d->name);
+	switch (d->type) {
+	case DT_DIR:
+		fprintf(out, " (dir)");
+		break;
+	case DT_REG:
+		fprintf(out, " (file, size=%zu)", d->size);
+		break;
+	default:
+		fprintf(out, " (unknown!)");
+		break;
+	}
+	fprintf(out, "\n");
+
+	for (child = d->child; child != NULL; child = child->next) {
+		dent_dump(out, child, depth + 1);
+	}
+}
+#endif
+
+
+// Parse an `ls` command.
+int
+cmd_ls(struct dent ** cwd, char * buf, size_t bufsiz, FILE * in, char const * arg)
+{
+	static regex_t dir, file;
+	static int init = 0;
+
+	if (init == 0) {
+		init = 1;
+		if (regcomp(&dir, "^(dir) ([[:alnum:].]+)\n?$", REG_EXTENDED) != 0
+				|| regcomp(&file, "^([[:digit:]]+) ([[:alnum:].]+)\n?$", REG_EXTENDED) != 0)
+		{
+			fprintf(stderr, "ls: Unable to compile regexes");
+			init = -1;
+		}
+	}
+	if (init == -1) {
+		return -1;
+	}
+	if (!buf && !in) {
+		regfree(&dir);
+		regfree(&file);
+		init = 0;
+		return 0;
+	}
+
+	if (arg) {
+		fprintf(stderr, "%s: Unexpected arg to `ls`\n", __FUNCTION__);
+		return -1;
+	}
+
+	while (fgets(buf, bufsiz, in)) {
+		regmatch_t matches[3];
+		struct dent * d;
+
+		if (buf[0] == '$') {
+			return 0;
+		}
+		else if (regexec(&dir, buf, 3, matches, 0) == 0) {
+			buf[matches[2].rm_eo] = '\0';
+			if ((d = dent_find(*cwd, buf + matches[2].rm_so)) == NULL) {
+				d = dent_create(DT_DIR, 0, *cwd, buf + matches[2].rm_so);
+			}
+			if (d->type != DT_DIR) {
+				fprintf(stderr, "%s: Mismatched type for %s\n", __FUNCTION__, d->name);
+			}
+		}
+		else if (regexec(&file, buf, 3, matches, 0) == 0) {
+			buf[matches[2].rm_eo] = '\0';
+			if ((d = dent_find(*cwd, buf + matches[2].rm_so)) == NULL) {
+				d = dent_create(DT_REG, atoi(buf + matches[1].rm_so),
+						*cwd, buf + matches[2].rm_so);
+			}
+
+			if (d->type != DT_REG) {
+				fprintf(stderr, "%s: Mismatched type for %s\n", __FUNCTION__, d->name);
+			}
+		}
+		else {
+			fprintf(stderr, "%s: Unexpected output: %s\n", __FUNCTION__, buf);
+			return -1;
+		}
+	}
+
+	buf[0] = '\0';
+	return -1;
+}
+
+
+// Parse a `cd` command.
+int
+cmd_cd(struct dent ** cwd, char * buf, size_t bufsiz, FILE * in, char const * arg)
+{
+	if (!arg) {
+		fprintf(stderr, "%s: Missing parameter\n", __FUNCTION__);
+		return -1;
+	}
+
+	if (strcmp(arg, "/") == 0) {
+		if (!*cwd)
+			*cwd = dent_create(DT_DIR, 0, NULL, "/");
+
+		while (*cwd && (*cwd)->parent)
+			*cwd = (*cwd)->parent;
+	}
+	else if (strcmp(arg, "..") == 0) {
+		if (!*cwd) {
+			fprintf(stderr, "%s: No cwd!\n", __FUNCTION__);
+			return -1;
+		}
+		if (!(*cwd)->parent) {
+			fprintf(stderr, "%s: No parent dir!\n", __FUNCTION__);
+			return -1;
+		}
+		*cwd = (*cwd)->parent;
+	}
+	else {
+		struct dent * d = dent_find(*cwd, arg);
+		if (!d) {
+			fprintf(stderr, "%s: No subdirectory: %s\n", __FUNCTION__, arg);
+			return -1;
+		}
+		if (d->type != DT_DIR) {
+			fprintf(stderr, "%s: Is not a directory: %s\n", __FUNCTION__, arg);
+			return -1;
+		}
+		*cwd = d;
+	}
+
+	return fgets(buf, bufsiz, in) ? 0 : -1;
+}
+
+
+int
+main()
+{
+	char buf[BUFSIZ];
+	struct dent * cwd = NULL, * root, * d;
+	int i;
+	size_t s;
+
+	i = fgets(buf, sizeof(buf), stdin) ? 0 : -1;
+	while (i == 0) {
+		char * tok, * toksave = NULL;
+
+		tok = strtok_r(buf, " \n", &toksave);
+		if (strcmp(tok, "$") != 0) {
+			fprintf(stderr, "Not a command: %s\n", buf);
+			return -1;
+		}
+
+		// Get the next command.
+		//
+		// Command parsers are responsible for parsing the command argument,
+		// and any output of the command, and reading the line containing the
+		// next command into `buf`.
+		//
+		// They should return 0 for success, -1 on error.
+		tok = strtok_r(NULL, " \n", &toksave);
+		if (strcmp(tok, "cd") == 0) {
+			tok = strtok_r(NULL, "\n", &toksave);
+			i = cmd_cd(&cwd, buf, sizeof(buf), stdin, tok);
+		}
+		else if (strcmp(tok, "ls") == 0) {
+			tok = strtok_r(NULL, "\n", &toksave);
+			i = cmd_ls(&cwd, buf, sizeof(buf), stdin, tok);
+		}
+		else {
+			fprintf(stderr, "Unexpected command: %s\n", tok);
+			return -1;
+		}
+	}
+
+	root = cwd;
+	while (root && root->parent)
+		root = root->parent;
+
+#ifdef DENT_DUMP
+	dent_dump(stderr, root, 0);
+#endif
+
+	// Calculate disk usage sizes;
+	dent_du(root);
+
+	// Find directories whose size is less than a limit, and sum them.
+	s = 0;
+	for (d = root; d != NULL; d = dent_next(d)) {
+		if (d->type == DT_DIR && d->size <= 100000)
+			s += d->size;
+	}
+	printf("Sum of dir sizes where size <= 100000: %zu\n", s);
+
+	// Tidy up
+	dent_free(root);
+	cmd_ls(NULL, NULL, 0, NULL, NULL);
+
+	return 0;
+}
+
diff --git a/makefile b/makefile
index b00a363..c064ff3 100644
--- a/makefile
+++ b/makefile
@@ -1,5 +1,5 @@
 
-CFLAGS=-Wall
+CFLAGS=-Wall -O2
 
 all: bin \
 	bin/1a bin/1b \
@@ -8,6 +8,7 @@ all: bin \
 	bin/4a bin/4b \
 	bin/5 \
 	bin/6 \
+	bin/7 \
 
 bin:
 	mkdir -p $@