Replace manual traverse() with nftw().

1 files changed, 93 insertions, 165 deletions

diff --git a/main.c b/main.c
index 035c7d3..f6eff2f 100644
--- a/main.c
+++ b/main.c
@@ -1,23 +1,20 @@
-#include <dirent.h>
 #include <err.h>
 #include <errno.h>
 #include <fcntl.h>
-#include <limits.h>
+#include <ftw.h>
 #include <sha1.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
-#include <sys/stat.h>
-#include <sys/types.h>
 
-#define REPO      ".cvn"
-#define INDEX     "index"
-#define HASH_LEN  SHA1_DIGEST_LENGTH
+#define MAX_DEPTH  256
 
-#define FLAG_DIR  (1 << 0) // 0x01
-#define FLAG_EXE  (1 << 1) // 0x02
-#define FLAG_LNK  (1 << 2) // 0x04
+#define CVN_DIR    ".cvn"
+#define INDEX_FILE "index"
+
+#define HASH_LEN        SHA1_DIGEST_LENGTH
+#define HASH_INPUT_LEN  4096
 
 #define MALLOC(s) _xmalloc((s), __FILE__, __LINE__)
 #define REALLOC(p, s) _xrealloc((p), (s), __FILE__, __LINE__)
@@ -25,15 +22,7 @@
 static inline void init(int argc, char *argv[]);
 static inline void status(int argc, char *argv[]);
 
-struct stack;
-struct stack_ent;
-static inline void stack_alloc(struct stack *st);
-static inline struct stack_ent *pop(struct stack *st);
-static inline void push(struct stack *st, struct stack_ent *new_ent);
-static inline void stack_free(struct stack *st);
-
-static inline void traverse(void);
-static inline void hash(struct stack *st);
+static inline void update_index(void);
 static inline int ignore(const char *path);
 
 static inline void *_xmalloc(size_t s, const char *file, int line);
@@ -83,15 +72,15 @@ static inline void init(int argc, char *argv[])
 		}
 	}
 
-	if (mkdir(REPO, 0755) == -1) {
+	if (mkdir(CVN_DIR, 0755) == -1) {
 		if (errno != EEXIST)
 			err(1, "Failed to create repository");
 	}
 
-	if ((repo_fd = open(REPO, O_RDONLY | O_DIRECTORY)) == -1)
+	if ((repo_fd = open(CVN_DIR, O_RDONLY | O_DIRECTORY)) == -1)
 		err(1, "Failed to open repository");
 
-	if ((idx_fd = openat(repo_fd, INDEX, 
+	if ((idx_fd = openat(repo_fd, INDEX_FILE, 
 		O_WRONLY | O_CREAT | O_EXCL, 0644)) == -1) {
 		if (errno != EEXIST) {
 			close(repo_fd);
@@ -101,183 +90,122 @@ static inline void init(int argc, char *argv[])
 		close(idx_fd);
 
 	close(repo_fd);
-	printf("Initialized repository in %s\n", REPO);
+	printf("Initialized repository in %s\n", CVN_DIR);
 }
 
 static inline void status(int argc, char *argv[])
 {
-	traverse();
+	update_index();
 }
 
-struct stack_ent {
-	char *path;
-	unsigned char flags;
-	unsigned char hash[HASH_LEN];
-	struct stack_ent *parent;
-};
+static char hash_input[HASH_INPUT_LEN];
+static uint8_t *hash_at_level[MAX_DEPTH] = {0};
 
-struct stack {
-	struct stack_ent **ents;
-	size_t len;
-	size_t cap;
-};
+static inline void print_hash(const uint8_t hash[HASH_LEN], 
+	const char *path)
+{
+	printf("0x");
+	for (int i = 0; i < HASH_LEN; i++)
+		printf("%02x", hash[i]);
+	printf(": %s\n", path);
+}
 
-static inline void traverse(void)
+void update_hash_at(size_t level, const uint8_t *hash)
 {
-	DIR *dir;
-	char *rel_path;
-	struct stat st;
-	struct dirent *entry;
-	struct stack work_tree, stk;
-	struct stack_ent *cur_dir, *root, *new_ent;
-
-	stack_alloc(&stk);
-	stack_alloc(&work_tree);
-	
-	root = MALLOC(sizeof(struct stack_ent));
-	root->path = strdup(".");
-	root->flags = FLAG_DIR;
-	root->parent = NULL;
-	push(&stk, root);
-
-	while (stk.len > 0) {
-		cur_dir = pop(&stk);
-		if (!(dir = opendir(cur_dir->path))) {
-			warn("Failed to open directory %s", cur_dir->path);
-			continue;
-		}
+	SHA1_CTX ctx;
 
-		push(&work_tree, cur_dir);
-
-		while ((entry = readdir(dir))) {
-			if (ignore(entry->d_name))
-				continue;
-			if (asprintf(&rel_path, "%s/%s", cur_dir->path, entry->d_name) == -1)
-				err(1, "asprintf() failed");
-			if (lstat(rel_path, &st) == -1) {
-				warn("lstat() failed: %s", rel_path);
-				free(rel_path);
-				continue;
-			}
-			
-			if (S_ISREG(st.st_mode) || S_ISDIR(st.st_mode) || 
-			    S_ISLNK(st.st_mode)) {
-				new_ent = MALLOC(sizeof(struct stack_ent));
-				new_ent->path = rel_path;
-				new_ent->flags = 0;
-				new_ent->parent = cur_dir;
-
-				if (S_ISLNK(st.st_mode))
-					new_ent->flags |= FLAG_LNK;
-
-				if (S_ISDIR(st.st_mode)) {
-					new_ent->flags |= FLAG_DIR;
-					push(&stk, new_ent);
-				} else 
-					push(&work_tree, new_ent);
-			}
+	if (level >= 0) { 
+		if (hash_at_level[level]) {
+			SHA1Init(&ctx);
+			SHA1Update(&ctx, hash_at_level[level], HASH_LEN);
+			SHA1Update(&ctx, hash, HASH_LEN);
+			SHA1Final(hash_at_level[level], &ctx);
+		} else {
+			hash_at_level[level] = MALLOC(sizeof(uint8_t) * HASH_LEN);
+			memcpy(hash_at_level[level], hash, HASH_LEN);
 		}
-		closedir(dir);
 	}
-
-	hash(&work_tree);
-
-	for (ssize_t i = work_tree.len - 1; i >= 0; i--) {
-		printf("Entry: %s (p: %s): 0x", 
-		       work_tree.ents[i]->path, 
-		       work_tree.ents[i]->parent ? work_tree.ents[i]->parent->path : "NONE");
-		for (int j = 0; j < HASH_LEN; j++)
-			printf("%02x", work_tree.ents[i]->hash[j]);
-		putchar('\n');
-	}
-
-	stack_free(&stk);
-	stack_free(&work_tree);
 }
 
-static inline void hash(struct stack *st)
+void hash_file(const char *path, uint8_t *hash)
 {
 	int fd;
-	ssize_t i, j;
 	SHA1_CTX ctx;
-	unsigned char *buf;
-	ssize_t bytes_read, lnk_len;
-	struct stack_ent *ent, *prev_ent;
-
-	const int buflen = 8192 > PATH_MAX ? 8192 : PATH_MAX;
-	buf = MALLOC(sizeof(buf[0]) * buflen);
-
-	for (i = st->len - 1; i >= 0; i--) {
-		SHA1Init(&ctx);
-		ent = st->ents[i];
-		if (!ent->flags) {  /* regular file */
-			if ((fd = open(ent->path, O_RDONLY)) == -1)
-				err(1, "Cannot open %s", ent->path);
-			while ((bytes_read = read(fd, buf, buflen)) > 0)
-				SHA1Update(&ctx, buf, (size_t)bytes_read);
-			if (bytes_read == -1)
-				err(1, "Read error on %s", ent->path);
-			close(fd);
-		} else if ((ent->flags & FLAG_LNK)) {
-			lnk_len = readlink(ent->path, buf, buflen - 1);
-			if (lnk_len != -1) {
-				buf[lnk_len] = '\0';
-				SHA1Update(&ctx, buf, lnk_len);
-			} else
-				err(1, "readlink error on %s", ent->path);
-		} else {
-			// directory: walk the stack backwards and collect 
-			// hashes from children
-			for (j = i + 1; j < st->len; j++) {
-				prev_ent = st->ents[j];
-				if (prev_ent->parent != ent)
-					break;
-				SHA1Update(&ctx, prev_ent->hash, HASH_LEN);
-			}
-		}
-		SHA1Final(ent->hash, &ctx);
-	}
-	free(buf);
+	ssize_t bytes_read;
+
+	if ((fd = open(path, O_RDONLY)) == -1)
+		err(1, "Failed to open %s", path);
+
+	SHA1Init(&ctx);
+	while ((bytes_read = read(fd, hash_input, sizeof(hash_input))) > 0)
+		SHA1Update(&ctx, hash_input, (size_t)bytes_read);
+	if (bytes_read == -1)
+		err(1, "Failed to read %s", path);
+
+	SHA1Final(hash, &ctx);
+	close(fd);
 }
 
-static inline void stack_alloc(struct stack *st)
+void hash_path(const char *path, uint8_t *hash)
 {
-	st->len = 0;
-	st->cap = 512;
-	st->ents = MALLOC(sizeof(st->ents[0]) * st->cap);
+	SHA1_CTX ctx;
+	ssize_t lnk_len;
+
+	lnk_len = readlink(path, hash_input, HASH_INPUT_LEN - 1);
+	if (lnk_len == -1)
+		err(1, "readlink failed for %s", path);
+	hash_input[lnk_len] = '\0';
+
+	SHA1Init(&ctx);
+	SHA1Update(&ctx, hash_input, lnk_len);
+	SHA1Final(hash, &ctx);
 }
 
-static inline struct stack_ent *pop(struct stack *st)
+static inline void hash_dir(size_t level, uint8_t *hash)
 {
-	return st->ents[--(st->len)];
+	memcpy(hash, hash_at_level[level], HASH_LEN);
+	free(hash_at_level[level]);
+	hash_at_level[level] = NULL;
 }
 
-static inline void push(struct stack *st, struct stack_ent *new_ent)
+int compute_hash(const char * path, const struct stat *st, 
+	int tflag, struct FTW *ftwbuf)
 {
-	if (st->len >= st->cap) {
-		st->cap <<= 1;
-		st->ents = REALLOC(st->ents, 
-			sizeof(struct stack_ent *) * st->cap);
+	int level;
+	mode_t mode;
+	unsigned char hash[HASH_LEN];
+
+	const char *file_name = path + ftwbuf->base;
+	if (ignore(file_name))
+		return 0;
+
+	mode = st->st_mode;
+	level = ftwbuf->level;
+
+	if (tflag == FTW_F) {
+		if (S_ISREG(mode))
+			hash_file(path, hash);
+		else if (S_ISLNK(mode))
+			hash_path(path, hash);
+		update_hash_at(level - 1, hash);
+	} else if (tflag == FTW_DP) {
+		hash_dir(level, hash);
+		update_hash_at(level - 1, hash);
 	}
-	st->ents[st->len++] = new_ent;
+
+	print_hash(hash, path);
+	return 0;
 }
 
-static inline void stack_free(struct stack *st)
+static inline void update_index(void)
 {
-	size_t i;
-
-	for (i = 0; i < st->len; i++) {
-		free(st->ents[i]->path);
-		free(st->ents[i]);
-	}
-	free(st->ents);
+	if (nftw(".", compute_hash, MAX_DEPTH, FTW_DEPTH | FTW_PHYS) == -1)
+		err(1, "nftw");
 }
 
 static inline int ignore(const char *path)
 {
-	return strcmp(path, ".")  == 0 || 
-	       strcmp(path, "..") == 0 || 
-	       strcmp(path, REPO) == 0;
+	return strcmp(path, CVN_DIR) == 0;
 }
 
 static inline void *_xmalloc(size_t s, const char *file, int line)