[dev] [PATCH] diff: optimisations

From: <maandree_AT_kth.se>
Date: Wed, 27 Jan 2016 22:45:49 +0100

Signed-off-by: Mattias Andrée <maandree_AT_kth.se>

---
 diff.c | 48 ++++++++++++++++++++----------------------------
 1 file changed, 20 insertions(+), 28 deletions(-)
diff --git a/diff.c b/diff.c
index 21f9849..b6da7b9 100644
--- a/diff.c
+++ b/diff.c
_AT_@ -4,6 +4,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
+#include <stdint.h>
 
 #include "util.h"
 
_AT_@ -22,9 +23,6 @@ struct output {
 	char* text;
 };
 
-static struct output *red = 0;
-static struct output *green = 0;
-
 static struct file_data *
 load_lines(const char *pathname)
 {
_AT_@ -87,14 +85,14 @@ load_lines(const char *pathname)
 static char *
 diff2(char **a, char **b, size_t an, size_t bn)
 {
-	size_t **matrix = emalloc((an + 1) * sizeof(size_t *) + (an + 1) * (bn + 1) * sizeof(size_t));
-	char   **map    = emalloc((an + 1) * sizeof(char   *) + (an + 1) * (bn + 1) * sizeof(char));
-	size_t ai, bi, ri = 0;
+	size_t **matrix = emalloc((an + 2) * sizeof(size_t *) + (an + 2) * (bn + 1) * sizeof(size_t));
+	char   **map    = emalloc((an + 2) * sizeof(char   *) + (an + 2) * (bn + 1) * sizeof(char));
+	size_t ai, bi, ri = 0, boff = 1;
 	char *rc;
 
-	for (ai = 0; ai <= an; ai++) {
-		matrix[ai] = (size_t *)(matrix + an + 1) + ai * (bn + 1);
-		map   [ai] = (char   *)(map    + an + 1) + ai * (bn + 1);
+	for (ai = 0; ai <= an + 1; ai++) {
+		matrix[ai] = (size_t *)(matrix + an + 2) + ai * (bn + 1);
+		map   [ai] = (char   *)(map    + an + 2) + ai * (bn + 1);
 		matrix[ai][0] = ai;
 		map   [ai][0] = 1;
 	}
_AT_@ -107,14 +105,18 @@ diff2(char **a, char **b, size_t an, size_t bn)
 	a--, b--;
 
 	for (ai = 1; ai <= an; ai++) {
-		for (bi = 1; bi <= bn; bi++) {
+		for (bi = boff; bi <= bn; bi++) {
 			size_t d = matrix[ai - 1][bi - 1];
 			size_t u = matrix[ai - 1][bi    ];
 			size_t l = matrix[ai    ][bi - 1];
 			size_t lu = 1 + (l < u ? l : u);
 			int ch = strcmp(a[ai], b[bi]); /* remember !! if using d += ch */
-			matrix[ai][bi] = (lu < d || ch) ? lu : d;
 			map   [ai][bi] = (lu < d || ch) ? 1 + (l < u) : 0;
+			matrix[ai][bi] = (lu < d || ch) ? lu : d;
+			if (matrix[ai][bi] < matrix[ai][boff]) {
+				boff = bi - 1;
+				matrix[ai + 1][boff - 1] = SSIZE_MAX; /* sic! */
+			}
 		}
 	}
 
_AT_@ -134,28 +136,20 @@ diff2(char **a, char **b, size_t an, size_t bn)
 static void
 flush_output(struct output *output, size_t n)
 {
+	size_t i;
+
 	if (!n)
 		return;
 
 	if (output->colour == 0) {
 		printf("%s%s\n", " ", output->text);
 	} else {
-		size_t colour_n[] = { [1] = 0, [2] = 0 }, i;
-		static size_t last_size = 0;
-
-		if (last_size < n) {
-			red   = erealloc(red,   n * sizeof(*red));
-			green = erealloc(green, n * sizeof(*green));
-			last_size = n;
-		}
-
 		for (i = 0; i < n; i++)
-			(output[i].colour == 1 ? red : green)[colour_n[(int)(output[i].colour)]++] = output[i];
-
-		for (i = 0, n = colour_n[1]; i < n; i++)
-			printf("\033[31m-%s\033[m\n", red[i].text);
-		for (i = 0, n = colour_n[2]; i < n; i++)
-			printf("\033[32m+%s\033[m\n", green[i].text);
+			if (output[i].colour == 1)
+				printf("\033[31m-%s\033[m\n", output[i].text);
+		for (i = 0; i < n; i++)
+			if (output[i].colour == 2)
+				printf("\033[32m+%s\033[m\n", output[i].text);
 	}
 }
 
_AT_@ -197,8 +191,6 @@ main(int argc, char *argv[])
 	if (fshut(stdout, "<stdout>"))
 		ret = 2;
 
-	free(red);
-	free(green);
 	free(old);
 	free(new);
 	free(path);
-- 
2.7.0

Received on Wed Jan 27 2016 - 22:45:49 CET