Merge branch 'np/delta' into next

* np/delta:
  diff-delta: allow reusing of the reference buffer index
  diff-delta: bound hash list length to avoid O(m*n) behavior
  diff-delta: produce optimal pack data
  Merge branch 'kh/svnimport'
  Merge branch 'js/refs'
  annotate: fix -S parameter to take a string
  annotate: Add a basic set of test cases.
  annotate: handle \No newline at end of file.
  gitview: Use horizontal scroll bar in the tree view

7 files changed, 137 insertions, 25 deletions

diff --git a/contrib/gitview/gitview b/contrib/gitview/gitview
index ea05cd424..de9f3f3c7 100755
--- a/contrib/gitview/gitview
+++ b/contrib/gitview/gitview
@@ -513,7 +513,7 @@ class GitView:
 
 
 		scrollwin = gtk.ScrolledWindow()
-		scrollwin.set_policy(gtk.POLICY_NEVER, gtk.POLICY_AUTOMATIC)
+		scrollwin.set_policy(gtk.POLICY_AUTOMATIC, gtk.POLICY_AUTOMATIC)
 		scrollwin.set_shadow_type(gtk.SHADOW_IN)
 		vbox.pack_start(scrollwin, expand=True, fill=True)
 		scrollwin.show()
@@ -526,9 +526,6 @@ class GitView:
 		self.treeview.show()
 
 		cell = CellRendererGraph()
-		#  Set the default width to 265
-		#  This make sure that we have nice display with large tag names
-		cell.set_property("width", 265)
 		column = gtk.TreeViewColumn()
 		column.set_resizable(True)
 		column.pack_start(cell, expand=True)
diff --git a/delta.h b/delta.h
index a15350dab..00fef0b8d 100644
--- a/delta.h
+++ b/delta.h
@@ -4,7 +4,8 @@
 /* handling of delta buffers */
 extern void *diff_delta(void *from_buf, unsigned long from_size,
 			void *to_buf, unsigned long to_size,
-		        unsigned long *delta_size, unsigned long max_size);
+		        unsigned long *delta_size, unsigned long max_size,
+			void **from_index);
 extern void *patch_delta(void *src_buf, unsigned long src_size,
 			 void *delta_buf, unsigned long delta_size,
 			 unsigned long *dst_size);
diff --git a/diff-delta.c b/diff-delta.c
index 0730b24df..dcd3f5572 100644
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -30,8 +30,7 @@ struct index {
 
 static struct index ** delta_index(const unsigned char *buf,
 				   unsigned long bufsize,
-				   unsigned long trg_bufsize,
-				   unsigned int *hash_shift)
+				   unsigned long trg_bufsize)
 {
 	unsigned long hsize;
 	unsigned int i, hshift, hlimit, *hash_count;
@@ -44,14 +43,17 @@ static struct index ** delta_index(const unsigned char *buf,
 	for (i = 8; (1 << i) < hsize && i < 24; i += 2);
 	hsize = 1 << i;
 	hshift = (i - 8) / 2;
-	*hash_shift = hshift;
 
-	/* allocate lookup index */
-	mem = malloc(hsize * sizeof(*hash) + bufsize * sizeof(*entry));
+	/*
+	 * Allocate lookup index.  Note the first hash pointer
+	 * is used to store the hash shift value.
+	 */
+	mem = malloc((1 + hsize) * sizeof(*hash) + bufsize * sizeof(*entry));
 	if (!mem)
 		return NULL;
 	hash = mem;
-	entry = mem + hsize * sizeof(*hash);
+	*hash++ = (void *)hshift;
+	entry = mem + (1 + hsize) * sizeof(*hash);
 	memset(hash, 0, hsize * sizeof(*hash));
 
 	/* allocate an array to count hash entries */
@@ -107,7 +109,7 @@ static struct index ** delta_index(const unsigned char *buf,
 	}
 	free(hash_count);
 
-	return hash;
+	return hash-1;
 }
 
 /* provide the size of the copy opcode given the block offset and size */
@@ -121,7 +123,8 @@ static struct index ** delta_index(const unsigned char *buf,
 void *diff_delta(void *from_buf, unsigned long from_size,
 		 void *to_buf, unsigned long to_size,
 		 unsigned long *delta_size,
-		 unsigned long max_size)
+		 unsigned long max_size,
+		 void **from_index)
 {
 	unsigned int i, outpos, outsize, inscnt, hash_shift;
 	const unsigned char *ref_data, *ref_top, *data, *top;
@@ -130,9 +133,16 @@ void *diff_delta(void *from_buf, unsigned long from_size,
 
 	if (!from_size || !to_size)
 		return NULL;
-	hash = delta_index(from_buf, from_size, to_size, &hash_shift);
-	if (!hash)
-		return NULL;
+	if (from_index && *from_index) {
+		hash = *from_index;
+	} else {
+		hash = delta_index(from_buf, from_size, to_size);
+		if (!hash)
+			return NULL;
+		if (from_index)
+			*from_index = hash;
+	}
+	hash_shift = (unsigned int)(*hash++);
 
 	outpos = 0;
 	outsize = 8192;
@@ -140,7 +150,8 @@ void *diff_delta(void *from_buf, unsigned long from_size,
 		outsize = max_size + MAX_OP_SIZE + 1;
 	out = malloc(outsize);
 	if (!out) {
-		free(hash);
+		if (!from_index)
+			free(hash-1);
 		return NULL;
 	}
 
@@ -241,7 +252,8 @@ void *diff_delta(void *from_buf, unsigned long from_size,
 				out = realloc(out, outsize);
 			if (!out) {
 				free(tmp);
-				free(hash);
+				if (!from_index)
+					free(hash-1);
 				return NULL;
 			}
 		}
@@ -250,7 +262,8 @@ void *diff_delta(void *from_buf, unsigned long from_size,
 	if (inscnt)
 		out[outpos - inscnt - 1] = inscnt;
 
-	free(hash);
+	if (!from_index)
+		free(hash-1);
 	*delta_size = outpos;
 	return out;
 }
diff --git a/git-annotate.perl b/git-annotate.perl
index f9c2c6caf..cd476c762 100755
--- a/git-annotate.perl
+++ b/git-annotate.perl
@@ -31,7 +31,7 @@ our ($help, $longrev, $rename, $starting_rev, $rev_file) = (0, 0, 1);
 my $rc = GetOptions(	"long|l" => \$longrev,
 			"help|h" => \$help,
 			"rename|r" => \$rename,
-			"rev-file|S" => \$rev_file);
+			"rev-file|S=s" => \$rev_file);
 if (!$rc or $help) {
 	usage();
 }
@@ -174,7 +174,8 @@ sub git_rev_list {
 
 	my $revlist;
 	if ($rev_file) {
-		open($revlist, '<' . $rev_file);
+		open($revlist, '<' . $rev_file)
+		    or die "Failed to open $rev_file : $!";
 	} else {
 		$revlist = open_pipe("git-rev-list","--parents","--remove-empty",$rev,"--",$file)
 			or die "Failed to exec git-rev-list: $!";
@@ -304,6 +305,12 @@ sub _git_diff_parse {
 			}
 			$ri++;
 
+		} elsif (m/^\\/) {
+			;
+			# Skip \No newline at end of file.
+			# But this can be internationalized, so only look
+			# for an initial \
+
 		} else {
 			if (substr($_,1) ne get_line($slines,$ri) ) {
 				die sprintf("Line %d (%d) does not match:\n|%s\n|%s\n%s => %s\n",
diff --git a/pack-objects.c b/pack-objects.c
index 136a7f5aa..d6a346360 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -204,7 +204,7 @@ static void *delta_against(void *buf, unsigned long size, struct object_entry *e
 	if (!otherbuf)
 		die("unable to read %s", sha1_to_hex(entry->delta->sha1));
         delta_buf = diff_delta(otherbuf, othersize,
-			       buf, size, &delta_size, 0);
+			       buf, size, &delta_size, 0, NULL);
         if (!delta_buf || delta_size != entry->delta_size)
         	die("delta size changed");
         free(buf);
@@ -810,6 +810,7 @@ static int type_size_sort(const struct object_entry *a, const struct object_entr
 struct unpacked {
 	struct object_entry *entry;
 	void *data;
+	void **delta_index;
 };
 
 /*
@@ -891,7 +892,8 @@ static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_de
 	if (sizediff >= max_size)
 		return -1;
 	delta_buf = diff_delta(old->data, oldsize,
-			       cur->data, size, &delta_size, max_size);
+			       cur->data, size, &delta_size,
+			       max_size, old->delta_index);
 	if (!delta_buf)
 		return 0;
 	cur_entry->delta = old_entry;
@@ -948,6 +950,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 			 */
 			continue;
 
+		free(n->delta_index);
 		free(n->data);
 		n->entry = entry;
 		n->data = read_sha1_file(entry->sha1, type, &size);
@@ -974,8 +977,10 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 	if (progress)
 		fputc('\n', stderr);
 
-	for (i = 0; i < window; ++i)
+	for (i = 0; i < window; ++i) {
+		free(array[i].delta_index);
 		free(array[i].data);
+	}
 	free(array);
 }
 
diff --git a/t/t8001-annotate.sh b/t/t8001-annotate.sh
new file mode 100755
index 000000000..cae179436
--- /dev/null
+++ b/t/t8001-annotate.sh
@@ -0,0 +1,89 @@
+#!/bin/sh
+
+test_description='git-annotate'
+. ./test-lib.sh
+
+test_expect_success \
+    'prepare reference tree' \
+    'echo "1A quick brown fox jumps over the" >file &&
+     echo "lazy dog" >>file &&
+     git add file
+     GIT_AUTHOR_NAME="A" git commit -a -m "Initial."'
+
+test_expect_success \
+    'check all lines blamed on A' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "A") == 2 ]'
+
+test_expect_success \
+    'Setup new lines blamed on B' \
+    'echo "2A quick brown fox jumps over the" >>file &&
+     echo "lazy dog" >> file &&
+     GIT_AUTHOR_NAME="B" git commit -a -m "Second."'
+
+test_expect_success \
+    'Two lines blamed on A' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "A") == 2 ]'
+
+test_expect_success \
+    'Two lines blamed on B' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "B") == 2 ]'
+
+test_expect_success \
+    'merge-setup part 1' \
+    'git checkout -b branch1 master &&
+     echo "3A slow green fox jumps into the" >> file &&
+     echo "well." >> file &&
+     GIT_AUTHOR_NAME="B1" git commit -a -m "Branch1-1"'
+
+test_expect_success \
+    'Two lines blamed on A' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^A$") == 2 ]'
+
+test_expect_success \
+    'Two lines blamed on B' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^B$") == 2 ]'
+
+test_expect_success \
+    'Two lines blamed on B1' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^B1$") == 2 ]'
+
+test_expect_success \
+    'merge-setup part 2' \
+    'git checkout -b branch2 master &&
+     sed -i -e "s/2A quick brown/4A quick brown lazy dog/" file &&
+     GIT_AUTHOR_NAME="B2" git commit -a -m "Branch2-1"'
+
+test_expect_success \
+    'Two lines blamed on A' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^A$") == 2 ]'
+
+test_expect_success \
+    'One line blamed on B' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^B$") == 1 ]'
+
+test_expect_success \
+    'One line blamed on B2' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^B2$") == 1 ]'
+
+
+test_expect_success \
+    'merge-setup part 3' \
+    'git pull . branch1'
+
+test_expect_success \
+    'Two lines blamed on A' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^A$") == 2 ]'
+
+test_expect_success \
+    'One line blamed on B' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^B$") == 1 ]'
+
+test_expect_success \
+    'Two lines blamed on B1' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^B1$") == 2 ]'
+
+test_expect_success \
+    'One line blamed on B2' \
+    '[ $(git annotate file | awk "{print \$3}" | grep -c "^B2$") == 1 ]'
+
+test_done
diff --git a/test-delta.c b/test-delta.c
index 1be8ee0c7..89eb68ed2 100644
--- a/test-delta.c
+++ b/test-delta.c
@@ -63,7 +63,7 @@ int main(int argc, char *argv[])
 	if (argv[1][1] == 'd')
 		out_buf = diff_delta(from_buf, from_size,
 				     data_buf, data_size,
-				     &out_size, 0);
+				     &out_size, 0, NULL);
 	else
 		out_buf = patch_delta(from_buf, from_size,
 				      data_buf, data_size,