From b1d0e0e97ce747534a945a6fe0c3a15ccd8dbf00 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Wed, 6 Mar 2019 22:25:56 -0800
Subject: parse: Use a trie to hold currently open files

---
 cmdline.h |  8 ++------
 eval.c    |  6 ++----
 parse.c   | 39 ++++++++++++++++++---------------------
 stat.c    |  5 +++++
 stat.h    | 10 ++++++++++
 5 files changed, 37 insertions(+), 31 deletions(-)

diff --git a/cmdline.h b/cmdline.h
index 3a8c064..06b8725 100644
--- a/cmdline.h
+++ b/cmdline.h
@@ -22,6 +22,7 @@
 #define BFS_CMDLINE_H
 
 #include "color.h"
+#include "trie.h"
 
 /**
  * Various debugging flags.
@@ -55,11 +56,6 @@ struct root {
 	struct root *next;
 };
 
-/**
- * An open file for the command line.
- */
-struct open_file;
-
 /**
  * The parsed command line.
  */
@@ -103,7 +99,7 @@ struct cmdline {
 	struct expr *expr;
 
 	/** All the open files owned by the command line. */
-	struct open_file *open_files;
+	struct trie open_files;
 	/** The number of open files owned by the command line. */
 	int nopen_files;
 };
diff --git a/eval.c b/eval.c
index d4097ef..53eacf8 100644
--- a/eval.c
+++ b/eval.c
@@ -1142,10 +1142,8 @@ static bool eval_file_unique(struct eval_state *state, struct trie *seen) {
 		return false;
 	}
 
-	// Glue the device and inode numbers together as a unique ID
-	unsigned char id[sizeof(statbuf->dev) + sizeof(statbuf->ino)];
-	memcpy(id, &statbuf->dev, sizeof(statbuf->dev));
-	memcpy(id + sizeof(statbuf->dev), &statbuf->ino, sizeof(statbuf->ino));
+	bfs_file_id id;
+	bfs_stat_id(statbuf, &id);
 
 	struct trie_leaf *leaf = trie_insert_mem(seen, id, sizeof(id));
 	if (!leaf) {
diff --git a/parse.c b/parse.c
index 780f678..f58b716 100644
--- a/parse.c
+++ b/parse.c
@@ -246,12 +246,6 @@ struct open_file {
 	CFILE *cfile;
 	/** The path to the file (for diagnostics). */
 	const char *path;
-	/** Device number (for deduplication). */
-	dev_t dev;
-	/** Inode number (for deduplication). */
-	ino_t ino;
-	/** The next open file in the chain. */
-	struct open_file *next;
 };
 
 /**
@@ -268,9 +262,9 @@ int free_cmdline(struct cmdline *cmdline) {
 
 		free_bfs_mtab(cmdline->mtab);
 
-		struct open_file *ofile = cmdline->open_files;
-		while (ofile) {
-			struct open_file *next = ofile->next;
+		struct trie_leaf *leaf;
+		while ((leaf = trie_first_leaf(&cmdline->open_files))) {
+			struct open_file *ofile = (struct open_file *)leaf->value;
 
 			if (cfclose(ofile->cfile) != 0) {
 				if (cerr) {
@@ -280,8 +274,9 @@ int free_cmdline(struct cmdline *cmdline) {
 			}
 
 			free(ofile);
-			ofile = next;
+			trie_remove_mem(&cmdline->open_files, leaf->key, leaf->length);
 		}
+		trie_destroy(&cmdline->open_files);
 
 		if (cout && fflush(cout->file) != 0) {
 			if (cerr) {
@@ -429,26 +424,27 @@ static int expr_open(struct parser_state *state, struct expr *expr, const char *
 		goto out_close;
 	}
 
-	for (struct open_file *ofile = cmdline->open_files; ofile; ofile = ofile->next) {
-		if (ofile->dev == sb.dev && ofile->ino == sb.ino) {
-			expr->cfile = ofile->cfile;
-			ret = 0;
-			goto out_close;
-		}
+	bfs_file_id id;
+	bfs_stat_id(&sb, &id);
+
+	struct trie_leaf *leaf = trie_insert_mem(&cmdline->open_files, id, sizeof(id));
+	if (leaf->value) {
+		struct open_file *ofile = (struct open_file *)leaf->value;
+		expr->cfile = ofile->cfile;
+		ret = 0;
+		goto out_close;
 	}
 
 	struct open_file *ofile = malloc(sizeof(*ofile));
 	if (!ofile) {
 		perror("malloc()");
+		trie_remove_mem(&cmdline->open_files, leaf->key, leaf->length);
 		goto out_close;
 	}
 
 	ofile->cfile = cfile;
 	ofile->path = path;
-	ofile->dev = sb.dev;
-	ofile->ino = sb.ino;
-	ofile->next = cmdline->open_files;
-	cmdline->open_files = ofile;
+	leaf->value = ofile;
 	++cmdline->nopen_files;
 
 	expr->cfile = cfile;
@@ -3139,9 +3135,10 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
 	cmdline->ignore_races = false;
 	cmdline->unique = false;
 	cmdline->expr = &expr_true;
-	cmdline->open_files = NULL;
 	cmdline->nopen_files = 0;
 
+	trie_init(&cmdline->open_files);
+
 	static char* default_argv[] = {"bfs", NULL};
 	if (argc < 1) {
 		argc = 1;
diff --git a/stat.c b/stat.c
index d223ff8..d94ddb0 100644
--- a/stat.c
+++ b/stat.c
@@ -334,3 +334,8 @@ const struct timespec *bfs_stat_time(const struct bfs_stat *buf, enum bfs_stat_f
 		return NULL;
 	}
 }
+
+void bfs_stat_id(const struct bfs_stat *buf, bfs_file_id *id) {
+	memcpy(*id, &buf->dev, sizeof(buf->dev));
+	memcpy(*id + sizeof(buf->dev), &buf->ino, sizeof(buf->ino));
+}
diff --git a/stat.h b/stat.h
index 3887db4..59a9712 100644
--- a/stat.h
+++ b/stat.h
@@ -126,4 +126,14 @@ int bfs_fstat(int fd, struct bfs_stat *buf);
  */
 const struct timespec *bfs_stat_time(const struct bfs_stat *buf, enum bfs_stat_field field);
 
+/**
+ * A unique ID for a file.
+ */
+typedef unsigned char bfs_file_id[sizeof(dev_t) + sizeof(ino_t)];
+
+/**
+ * Compute a unique ID for a file.
+ */
+void bfs_stat_id(const struct bfs_stat *buf, bfs_file_id *id);
+
 #endif // BFS_STAT_H
-- 
cgit v1.2.3