Move memory and stack to own files and sort before hash.

6 files changed, 135 insertions, 44 deletions

diff --git a/Makefile b/Makefile
index 9104cae..0d0f616 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 CC = cc
 TARGET = cvn
 
-SRC = main.c
+SRC = main.c mem.c stack.c
 OBJ = $(SRC:.c=.o)
 
 CFLAGS  = -std=c99 -O3 -Wall -I/usr/local/include
diff --git a/main.c b/main.c
index f6eff2f..d639f07 100644
--- a/main.c
+++ b/main.c
@@ -8,6 +8,9 @@
 #include <string.h>
 #include <unistd.h>
 
+#include "mem.h"
+#include "stack.h"
+
 #define MAX_DEPTH  256
 
 #define CVN_DIR    ".cvn"
@@ -16,18 +19,12 @@
 #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__)
-
 static inline void init(int argc, char *argv[]);
 static inline void status(int argc, char *argv[]);
 
 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);
-static inline void *_xrealloc(void *ptr, size_t s, const char *file, int line);
-
 struct command {
 	char *name;
 	void (*func)(int argc, char *argv[]);
@@ -98,8 +95,13 @@ static inline void status(int argc, char *argv[])
 	update_index();
 }
 
+struct hashed_file {
+	char *name;
+	uint8_t hash[HASH_LEN];
+};
+
 static char hash_input[HASH_INPUT_LEN];
-static uint8_t *hash_at_level[MAX_DEPTH] = {0};
+static struct stack *hash_at_level[MAX_DEPTH] = {0};
 
 static inline void print_hash(const uint8_t hash[HASH_LEN], 
 	const char *path)
@@ -110,19 +112,24 @@ static inline void print_hash(const uint8_t hash[HASH_LEN],
 	printf(": %s\n", path);
 }
 
-void update_hash_at(size_t level, const uint8_t *hash)
+static inline void insert_hash(size_t level, const char *filename,
+	const uint8_t *hash)
 {
-	SHA1_CTX ctx;
+	struct stack *st;
+	struct hashed_file *hf;
 
 	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);
+		hf = MALLOC(sizeof(struct hashed_file));
+		hf->name = strdup(filename);
+		memcpy(hf->hash, hash, HASH_LEN);
+		st = hash_at_level[level];
+		if (st)
+			push(st, (void *)hf);
+		else {
+			st = MALLOC(sizeof(struct stack));
+			stack_alloc(st);
+			push(st, (void *)hf);
+			hash_at_level[level] = st;
 		}
 	}
 }
@@ -161,11 +168,36 @@ void hash_path(const char *path, uint8_t *hash)
 	SHA1Final(hash, &ctx);
 }
 
+int compare_items(const void *a, const void *b) {
+	const void *pa = *(const void **)a;
+	const void *pb = *(const void **)b;
+
+	const struct hashed_file *hfa = (const struct hashed_file *)pa;
+	const struct hashed_file *hfb = (const struct hashed_file *)pb;
+
+	return strcmp(hfb->name, hfa->name);
+}
+
 static inline void hash_dir(size_t level, uint8_t *hash)
 {
-	memcpy(hash, hash_at_level[level], HASH_LEN);
-	free(hash_at_level[level]);
-	hash_at_level[level] = NULL;
+	SHA1_CTX ctx;
+	struct stack *st;
+	struct hashed_file *hf;
+
+	st = hash_at_level[level];
+	if (st && st->len > 0) {
+		SHA1Init(&ctx);
+		qsort(st->items, st->len, sizeof(st->items[0]), compare_items);
+		while (st->len > 0) {
+			hf = pop(st);
+			SHA1Update(&ctx, hf->hash, HASH_LEN);
+			free(hf->name);
+			free(hf);
+		}
+		SHA1Final(hash, &ctx);
+		stack_free(st);
+		hash_at_level[level] = NULL;
+	}
 }
 
 int compute_hash(const char * path, const struct stat *st, 
@@ -175,8 +207,8 @@ int compute_hash(const char * path, const struct stat *st,
 	mode_t mode;
 	unsigned char hash[HASH_LEN];
 
-	const char *file_name = path + ftwbuf->base;
-	if (ignore(file_name))
+	const char *filename = path + ftwbuf->base;
+	if (ignore(filename))
 		return 0;
 
 	mode = st->st_mode;
@@ -187,12 +219,11 @@ int compute_hash(const char * path, const struct stat *st,
 			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);
 	}
 
+	insert_hash(level - 1, filename, hash);
 	print_hash(hash, path);
 	return 0;
 }
@@ -208,22 +239,3 @@ static inline int ignore(const char *path)
 	return strcmp(path, CVN_DIR) == 0;
 }
 
-static inline void *_xmalloc(size_t s, const char *file, int line)
-{
-	void *p;
-
-	if (!(p = malloc(s)))
-		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;
-
-	if (!(p = realloc(ptr, s)))
-		err(1, "%s:%d: realloc", file, line);
-	return p;
-}
-
diff --git a/mem.c b/mem.c
new file mode 100644
index 0000000..c1b1216
--- /dev/null
+++ b/mem.c
@@ -0,0 +1,22 @@
+#include <err.h>
+#include <stdlib.h>
+
+#include "mem.h"
+
+void *_xmalloc(size_t s, const char *file, int line)
+{
+	void *p;
+
+	if (!(p = malloc(s)))
+		err(1, "%s:%d: malloc", file, line);
+	return p;
+}
+
+void *_xrealloc(void *ptr, size_t s, const char *file, int line)
+{
+	void *p;
+
+	if (!(p = realloc(ptr, s)))
+		err(1, "%s:%d: realloc", file, line);
+	return p;
+}
diff --git a/mem.h b/mem.h
new file mode 100644
index 0000000..546b004
--- /dev/null
+++ b/mem.h
@@ -0,0 +1,10 @@
+#ifndef MEM_H
+#define MEM_H
+
+#define MALLOC(s) _xmalloc((s), __FILE__, __LINE__)
+#define REALLOC(p, s) _xrealloc((p), (s), __FILE__, __LINE__)
+
+void *_xmalloc(size_t s, const char *file, int line);
+void *_xrealloc(void *ptr, size_t s, const char *file, int line);
+
+#endif /* MEM_H */
diff --git a/stack.c b/stack.c
new file mode 100644
index 0000000..69ccb13
--- /dev/null
+++ b/stack.c
@@ -0,0 +1,32 @@
+#include <err.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include "mem.h"
+#include "stack.h"
+
+void stack_alloc(struct stack *st)
+{
+	st->len = 0;
+	st->cap = 512;
+	st->items = MALLOC(sizeof(st->items[0]) * st->cap);
+}
+
+void *pop(struct stack *st)
+{
+	return st->items[--(st->len)];
+}
+
+void push(struct stack *st, void *item)
+{
+	if (st->len >= st->cap) {
+		st->cap <<= 1;
+		st->items = REALLOC(st->items, sizeof(st->items[0]) * st->cap);
+	}
+	st->items[st->len++] = item;
+}
+
+void stack_free(struct stack *st)
+{
+	free(st->items);
+}
diff --git a/stack.h b/stack.h
new file mode 100644
index 0000000..2c062f5
--- /dev/null
+++ b/stack.h
@@ -0,0 +1,15 @@
+#ifndef STACK_H
+#define STACK_H
+
+struct stack {
+	size_t len;
+	size_t cap;
+	void **items;
+};
+
+void stack_alloc(struct stack *st);
+void *pop(struct stack *st);
+void push(struct stack *st, void *item);
+void stack_free(struct stack *st);
+
+#endif /* STACK_H */