Merge branch 'jc/dirwalk-n-cache-tree' into jc/cache-tree

* jc/dirwalk-n-cache-tree: (212 commits)
  builtin-rm: squelch compiler warnings.
  Add builtin "git rm" command
  Move pathspec matching from builtin-add.c into dir.c
  Prevent bogus paths from being added to the index.
  builtin-add: fix unmatched pathspec warnings.
  Remove old "git-add.sh" remnants
  builtin-add: warn on unmatched pathspecs
  Do "git add" as a builtin
  Clean up git-ls-file directory walking library interface
  libify git-ls-files directory traversal
  Add a conversion tool to migrate remote information into the config
  fetch, pull: ask config for remote information
  Fix build procedure for builtin-init-db
  read-tree -m -u: do not overwrite or remove untracked working tree files.
  apply --cached: do not check newly added file in the working tree
  Implement a --dry-run option to git-quiltimport
  Implement git-quiltimport
  Revert "builtin-grep: workaround for non GNU grep."
  builtin-grep: workaround for non GNU grep.
  builtin-grep: workaround for non GNU grep.
  ...

1 files changed, 52 insertions, 42 deletions

diff --git a/pack-objects.c b/pack-objects.c
index c0acc460bb..77284cfdba 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -156,7 +156,7 @@ static void prepare_pack_revindex(struct pack_revindex *rix)
 
 	rix->revindex = xmalloc(sizeof(unsigned long) * (num_ent + 1));
 	for (i = 0; i < num_ent; i++) {
-		long hl = *((long *)(index + 24 * i));
+		unsigned int hl = *((unsigned int *)(index + 24 * i));
 		rix->revindex[i] = ntohl(hl);
 	}
 	/* This knows the pack format -- the 20-byte trailer
@@ -994,6 +994,7 @@ static int type_size_sort(const struct object_entry *a, const struct object_entr
 struct unpacked {
 	struct object_entry *entry;
 	void *data;
+	struct delta_index *index;
 };
 
 /*
@@ -1004,64 +1005,59 @@ struct unpacked {
  * more importantly, the bigger file is likely the more recent
  * one.
  */
-static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)
+static int try_delta(struct unpacked *trg, struct unpacked *src,
+		     struct delta_index *src_index, unsigned max_depth)
 {
-	struct object_entry *cur_entry = cur->entry;
-	struct object_entry *old_entry = old->entry;
-	unsigned long size, oldsize, delta_size, sizediff;
-	long max_size;
+	struct object_entry *trg_entry = trg->entry;
+	struct object_entry *src_entry = src->entry;
+	unsigned long size, src_size, delta_size, sizediff, max_size;
 	void *delta_buf;
 
 	/* Don't bother doing diffs between different types */
-	if (cur_entry->type != old_entry->type)
+	if (trg_entry->type != src_entry->type)
 		return -1;
 
 	/* We do not compute delta to *create* objects we are not
 	 * going to pack.
 	 */
-	if (cur_entry->preferred_base)
+	if (trg_entry->preferred_base)
 		return -1;
 
-	/* If the current object is at pack edge, take the depth the
+	/*
+	 * If the current object is at pack edge, take the depth the
 	 * objects that depend on the current object into account --
 	 * otherwise they would become too deep.
 	 */
-	if (cur_entry->delta_child) {
-		if (max_depth <= cur_entry->delta_limit)
+	if (trg_entry->delta_child) {
+		if (max_depth <= trg_entry->delta_limit)
 			return 0;
-		max_depth -= cur_entry->delta_limit;
+		max_depth -= trg_entry->delta_limit;
 	}
-
-	size = cur_entry->size;
-	oldsize = old_entry->size;
-	sizediff = oldsize > size ? oldsize - size : size - oldsize;
-
-	if (size < 50)
-		return -1;
-	if (old_entry->depth >= max_depth)
+	if (src_entry->depth >= max_depth)
 		return 0;
 
-	/*
-	 * NOTE!
-	 *
-	 * We always delta from the bigger to the smaller, since that's
-	 * more space-efficient (deletes don't have to say _what_ they
-	 * delete).
-	 */
-	max_size = size / 2 - 20;
-	if (cur_entry->delta)
-		max_size = cur_entry->delta_size-1;
+	/* Now some size filtering heuristics. */
+	size = trg_entry->size;
+	max_size = size/2 - 20;
+	max_size = max_size * (max_depth - src_entry->depth) / max_depth;
+	if (max_size == 0)
+		return 0;
+	if (trg_entry->delta && trg_entry->delta_size <= max_size)
+		max_size = trg_entry->delta_size-1;
+	src_size = src_entry->size;
+	sizediff = src_size < size ? size - src_size : 0;
 	if (sizediff >= max_size)
 		return 0;
-	delta_buf = diff_delta(old->data, oldsize,
-			       cur->data, size, &delta_size, max_size);
+
+	delta_buf = create_delta(src_index, trg->data, size, &delta_size, max_size);
 	if (!delta_buf)
 		return 0;
-	cur_entry->delta = old_entry;
-	cur_entry->delta_size = delta_size;
-	cur_entry->depth = old_entry->depth + 1;
+
+	trg_entry->delta = src_entry;
+	trg_entry->delta_size = delta_size;
+	trg_entry->depth = src_entry->depth + 1;
 	free(delta_buf);
-	return 0;
+	return 1;
 }
 
 static void progress_interval(int signum)
@@ -1109,11 +1105,16 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 			 */
 			continue;
 
+		if (entry->size < 50)
+			continue;
+		free_delta_index(n->index);
+		n->index = NULL;
 		free(n->data);
 		n->entry = entry;
 		n->data = read_sha1_file(entry->sha1, type, &size);
 		if (size != entry->size)
-			die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
+			die("object %s inconsistent object length (%lu vs %lu)",
+			    sha1_to_hex(entry->sha1), size, entry->size);
 
 		j = window;
 		while (--j > 0) {
@@ -1124,18 +1125,20 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 			m = array + other_idx;
 			if (!m->entry)
 				break;
-			if (try_delta(n, m, depth) < 0)
+			if (try_delta(n, m, m->index, depth) < 0)
 				break;
 		}
-#if 0
 		/* if we made n a delta, and if n is already at max
 		 * depth, leaving it in the window is pointless.  we
 		 * should evict it first.
-		 * ... in theory only; somehow this makes things worse.
 		 */
 		if (entry->delta && depth <= entry->depth)
 			continue;
-#endif
+
+		n->index = create_delta_index(n->data, size);
+		if (!n->index)
+			die("out of memory");
+
 		idx++;
 		if (idx >= window)
 			idx = 0;
@@ -1144,8 +1147,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_delta_index(array[i].index);
 		free(array[i].data);
+	}
 	free(array);
 }
 
@@ -1239,6 +1244,7 @@ int main(int argc, char **argv)
 
 	setup_git_directory();
 
+	progress = isatty(2);
 	for (i = 1; i < argc; i++) {
 		const char *arg = argv[i];
 
@@ -1269,6 +1275,10 @@ int main(int argc, char **argv)
 					usage(pack_usage);
 				continue;
 			}
+			if (!strcmp("--progress", arg)) {
+				progress = 1;
+				continue;
+			}
 			if (!strcmp("-q", arg)) {
 				progress = 0;
 				continue;