Re: [PATCH] fast-import: use binary search in tree_content_remove

["Shawn O. Pearce" <spearce@spearce.org>]

Jeff King <peff@peff.net> wrote:
> And here it is. However, I should note that this patch is _not_
> necessary.

Well, its not necessary for you, as you aren't trying to remove
something from your huge tree.  ;-)

> I had originally thought that removal might destroy the
> sorting that I added in the last patch, but it looks like the entry
> isn't actually removed. Shawn, can you sanity check this?

Your patch is fine.  fast-import takes an "optimization" here and
does not bother to actually delete entries from a tree until *after*
we have written the tree data out to the packfile.  The reason
is we need to retain the version 0 tree entry objects to recreate
the delta base.  Since these are combined with the version 1 data
(the "new" data) we have to delay the actual deletes until after
we store the tree and have its SHA-1.

It turns out however that your entire series was broken. I had to
commit the following on top of it to fix it:

-->8--
From 0af148553a94f7e856089fa68395524932240145 Mon Sep 17 00:00:00 2001
From: Shawn O. Pearce <spearce@spearce.org>
Date: Sat, 10 Mar 2007 22:34:12 -0500
Subject: [PATCH] fast-import: Brown paper bag fix tree sorting

Jeff King's recent changes to sort trees by strictly name (and binary
search to locate an entry) works OK up until we have to write a
tree out that uses the funny name/mode sorting that native Git uses:

  b.
  b/
  ba

Here the subtree "b" must sort between files "b." and "ba", but
Jeff's changes have it sorting before "b.".  This means we would fail
to find entries during future modifications to that tree as Jeff's
binary search algorithm won't find subtree "b" between b.  and ba.

I'm plastering over the problem by resorting a tree strictly by
name after it has been written out and the deleted entries have
been filtered out.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 fast-import.c |    8 ++++++++
 1 files changed, 8 insertions(+), 0 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 716819f..fa3b766 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1136,6 +1136,13 @@ static int tecmp1 (const void *_a, const void *_b)
 		b->name->str_dat, b->name->str_len, b->versions[1].mode);
 }
 
+static int nmcmp (const void *_a, const void *_b)
+{
+	struct tree_entry *a = *((struct tree_entry**)_a);
+	struct tree_entry *b = *((struct tree_entry**)_b);
+	return strcmp(a->name->str_dat, b->name->str_dat);
+}
+
 static void mktree(struct tree_content *t,
 	int v,
 	unsigned long *szp,
@@ -1218,6 +1225,7 @@ static void store_tree(struct tree_entry *root)
 		}
 	}
 	t->entry_count -= del;
+	qsort(t->entries, t->entry_count, sizeof(t->entries[0]), nmcmp);
 }
 
 static int tree_content_set(
-- 
1.5.0.3.942.g299f