From e29e1147e485654d90a0ea0fd5fb7151bb194265 Mon Sep 17 00:00:00 2001
From: Junio C Hamano <junkio@cox.net>
Date: Tue, 28 Feb 2006 20:16:41 -0800
Subject: [PATCH] diffcore-delta: stop using deltifier for packing.

This switches the change estimation logic used by break, rename
and copy detection from delta packing code to a more line
oriented one.  This way, thee performance-density tradeoff by
delta packing code can be made without worrying about breaking
the rename detection.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 diffcore-delta.c | 141 ++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 113 insertions(+), 28 deletions(-)

diff --git a/diffcore-delta.c b/diffcore-delta.c
index 1e6a6911..d03787be 100644
--- a/diffcore-delta.c
+++ b/diffcore-delta.c
@@ -1,43 +1,128 @@
 #include "cache.h"
 #include "diff.h"
 #include "diffcore.h"
-#include "delta.h"
-#include "count-delta.h"
-
-static int diffcore_count_changes_1(void *src, unsigned long src_size,
-				    void *dst, unsigned long dst_size,
-				    unsigned long delta_limit,
-				    unsigned long *src_copied,
-				    unsigned long *literal_added)
-{
-	void *delta;
-	unsigned long delta_size;
-
-	delta = diff_delta(src, src_size,
-			   dst, dst_size,
-			   &delta_size, delta_limit);
-	if (!delta)
-		/* If delta_limit is exceeded, we have too much differences */
-		return -1;
 
-	/* Estimate the edit size by interpreting delta. */
-	if (count_delta(delta, delta_size, src_copied, literal_added)) {
-		free(delta);
-		return -1;
+struct linehash {
+	unsigned long bytes;
+	unsigned long hash;
+};
+
+static unsigned long hash_extended_line(const unsigned char **buf_p,
+					unsigned long left)
+{
+	/* An extended line is zero or more whitespace letters (including LF)
+	 * followed by one non whitespace letter followed by zero or more
+	 * non LF, and terminated with by a LF (or EOF).
+	 */
+	const unsigned char *bol = *buf_p;
+	const unsigned char *buf = bol;
+	unsigned long hashval = 0;
+	while (left) {
+		unsigned c = *buf++;
+		if (!c)
+			goto binary;
+		left--;
+		if (' ' < c) {
+			hashval = c;
+			break;
+		}
+	}
+	while (left) {
+		unsigned c = *buf++;
+		if (!c)
+			goto binary;
+		left--;
+		if (c == '\n')
+			break;
+		if (' ' < c)
+			hashval = hashval * 11 + c;
 	}
-	free(delta);
+	*buf_p = buf;
+	return hashval;
+
+ binary:
+	*buf_p = NULL;
+	return 0;
+}
+
+static int linehash_compare(const void *a_, const void *b_)
+{
+	struct linehash *a = (struct linehash *) a_;
+	struct linehash *b = (struct linehash *) b_;
+	if (a->hash < b->hash) return -1;
+	if (a->hash > b->hash) return 1;
 	return 0;
 }
 
+static struct linehash *hash_lines(const unsigned char *buf,
+				   unsigned long size)
+{
+	const unsigned char *eobuf = buf + size;
+	struct linehash *line = NULL;
+	int alloc = 0, used = 0;
+
+	while (buf < eobuf) {
+		const unsigned char *ptr = buf;
+		unsigned long hash = hash_extended_line(&buf, eobuf-ptr);
+		if (!buf) {
+			free(line);
+			return NULL;
+		}
+		if (alloc <= used) {
+			alloc = alloc_nr(alloc);
+			line = xrealloc(line, sizeof(*line) * alloc);
+		}
+		line[used].bytes = buf - ptr;
+		line[used].hash = hash;
+		used++;
+	}
+	qsort(line, used, sizeof(*line), linehash_compare);
+
+	/* Terminate the list */
+	if (alloc <= used)
+		line = xrealloc(line, sizeof(*line) * (used+1));
+	line[used].bytes = line[used].hash = 0;
+	return line;
+}
+
 int diffcore_count_changes(void *src, unsigned long src_size,
 			   void *dst, unsigned long dst_size,
 			   unsigned long delta_limit,
 			   unsigned long *src_copied,
 			   unsigned long *literal_added)
 {
-	return diffcore_count_changes_1(src, src_size,
-					dst, dst_size,
-					delta_limit,
-					src_copied,
-					literal_added);
+	struct linehash *src_lines, *dst_lines;
+	unsigned long sc, la;
+
+	src_lines = hash_lines(src, src_size);
+	if (!src_lines)
+		return -1;
+	dst_lines = hash_lines(dst, dst_size);
+	if (!dst_lines) {
+		free(src_lines);
+		return -1;
+	}
+	sc = la = 0;
+	while (src_lines->bytes && dst_lines->bytes) {
+		int cmp = linehash_compare(src_lines, dst_lines);
+		if (!cmp) {
+			sc += src_lines->bytes;
+			src_lines++;
+			dst_lines++;
+			continue;
+		}
+		if (cmp < 0) {
+			src_lines++;
+			continue;
+		}
+		la += dst_lines->bytes;
+		dst_lines++;
+	}
+	while (dst_lines->bytes) {
+		la += dst_lines->bytes;
+		dst_lines++;
+	}
+	*src_copied = sc;
+	*literal_added = la;
+	return 0;
 }
-- 
2.11.0