Fix traverse() order.

2 files changed, 101 insertions, 54 deletions

diff --git a/.gitignore b/.gitignore
index d6c576f..6714024 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,6 +1,6 @@
 cvn
 .cvn/
-top_dir/
+test_env/
 
 **/*.o
 **/*.out
diff --git a/main.c b/main.c
index a8e02b7..078a984 100644
--- a/main.c
+++ b/main.c
@@ -18,11 +18,12 @@
 static inline void init(int argc, char *argv[]);
 static inline void status(int argc, char *argv[]);
 
-static inline void *_xmalloc(size_t s, const char *file, int line);
-static inline void *_xrealloc(void *ptr, size_t s, const char *file, int line);
-
 static inline void traverse(void);
 static inline uint8_t ignore(const char *path);
+static inline int cmp(const void *a, const void *b);
+
+static inline void *_xmalloc(size_t s, const char *file, int line);
+static inline void *_xrealloc(void *ptr, size_t s, const char *file, int line);
 
 struct command {
 	char *name;
@@ -54,32 +55,12 @@ int main(int argc, char *argv[])
 	return 0;
 }
 
-
-static inline void *_xmalloc(size_t s, const char *file, int line)
-{
-	void *p = malloc(s);
-	if (!p)
-		err(1, "%s:%d: malloc", file, line);
-	return p;
-}
-
-static inline void *_xrealloc(void *ptr, size_t s,
-	const char *file, int line)
-{
-	void *p = realloc(ptr, s);
-	if (!p)
-		err(1, "%s:%d: realloc", file, line);
-	return p;
-}
-
 static inline void init(int argc, char *argv[])
 {
 	char *branch;
 	int opt, repo_fd, idx_fd;
 
 	optind = 1; 
-	branch = "master";
-
 	while ((opt = getopt(argc, argv, "b:")) != -1) {
 		switch (opt) {
 			case 'b': 
@@ -121,58 +102,124 @@ static inline void status(int argc, char *argv[])
 	traverse();
 }
 
-static inline uint8_t ignore(const char *path)
-{
-	return strcmp(path, ".") == 0 || 
-	       strcmp(path, "..") == 0 || 
-	       strcmp(path, REPO) == 0;
-}
+struct node {
+	char *path;
+	unsigned char is_dir;
+	struct node *parent;
+};
 
 static inline void traverse(void)
 {
 	DIR *dir;
-	char *path, *rel_path;
+	char *rel_path;
 	struct stat st;
 	struct dirent *entry;
-	char **subdirs, levels;
-	int i, subdirs_len, levels_len;
-
-	i = 0;
-	subdirs_len = 512, levels_len = 512;
-	subdirs = MALLOC(sizeof(subdirs[0]) * subdirs_len);
-	subdirs[i++] = strdup(".");
-
-	while (i > 0) {
-		path = subdirs[--i];
-		if (!(dir = opendir(path))) {
-			warn("Failed to open directory %s", path);
-			free(path);
+	struct node *cur_dir, *root, *new_node;
+	struct node **dirs, **tree;
+	size_t dirs_len, tree_len;
+	size_t dirs_cap, tree_cap;
+
+	tree_len = 0, tree_cap = 512;
+	tree = MALLOC(sizeof(tree[0]) * tree_cap);
+
+	dirs_len = 0, dirs_cap = 512;
+	dirs = MALLOC(sizeof(dirs[0]) * dirs_cap);
+	
+	root = MALLOC(sizeof(struct node));
+	root->path = strdup(".");
+	root->is_dir = 1;
+	root->parent = NULL;
+	dirs[dirs_len++] = root;
+
+	while (dirs_len > 0) {
+		cur_dir = dirs[--dirs_len];
+		if (!(dir = opendir(cur_dir->path))) {
+			warn("Failed to open directory %s", cur_dir->path);
 			continue;
 		}
 
-		while ((entry = readdir(dir)) != NULL) {
+		if (tree_len >= tree_cap - 1) {
+			tree_cap <<= 1;
+			tree = REALLOC(tree, sizeof(tree[0]) * tree_cap);
+		}
+		tree[tree_len++] = cur_dir;
+
+		while ((entry = readdir(dir))) {
 			if (ignore(entry->d_name))
 				continue;
-			if (asprintf(&rel_path, "%s/%s", path, entry->d_name) == -1)
+			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_ISDIR(st.st_mode)) {
-				if (i >= subdirs_len) {
-					subdirs_len <<= 1;
-					subdirs = REALLOC(subdirs, sizeof(subdirs[0]) * subdirs_len);
+				if (dirs_len >= dirs_cap) {
+					dirs_cap <<= 1;
+					dirs = REALLOC(dirs, sizeof(dirs[0]) * dirs_cap);
 				}
-				subdirs[i++] = rel_path;
+				new_node = MALLOC(sizeof(struct node));
+				new_node->path = rel_path;
+				new_node->is_dir = 1;
+				new_node->parent = cur_dir;
+				dirs[dirs_len++] = new_node;
 			} else {
-				printf("File: %s\n", rel_path);
-				free(rel_path);
+				if (tree_len >= tree_cap) {
+					tree_cap <<= 1;
+					tree = REALLOC(tree, sizeof(tree[0]) * tree_cap);
+				}
+				new_node = MALLOC(sizeof(struct node));
+				new_node->path = rel_path;
+				new_node->is_dir = 0;
+				new_node->parent = cur_dir;
+				tree[tree_len++] = new_node;
 			}
 		}
-		free(path);
 		closedir(dir);
 	}
-	free(subdirs);
+
+	for (int i = (int)tree_len - 1; i >= 0; i--) {
+		printf("Entry: %s, parent: %s\n", 
+		       tree[i]->path, 
+		       tree[i]->parent ? tree[i]->parent->path : "NONE");
+	}
+
+	for (size_t i = 0; i < tree_len; i++) {
+		free(tree[i]->path);
+		free(tree[i]);
+	}
+	free(tree);
+	free(dirs);
 }
+
+static inline int cmp(const void *a, const void *b) 
+{
+	return strcmp(*(const char **)a, *(const char **)b);
+}
+
+static inline unsigned char ignore(const char *path)
+{
+	return strcmp(path, ".")  == 0 || 
+	       strcmp(path, "..") == 0 || 
+	       strcmp(path, REPO) == 0;
+}
+
+static inline void *_xmalloc(size_t s, const char *file, int line)
+{
+	void *p = malloc(s);
+	if (!p)
+		err(1, "%s:%d: malloc", file, line);
+	return p;
+}
+
+static inline void *_xrealloc(void *ptr, size_t s,
+	const char *file, int line)
+{
+	void *p = realloc(ptr, s);
+	if (!p)
+		err(1, "%s:%d: realloc", file, line);
+	return p;
+}
+