mailing list mirror (one of many)
 help / Atom feed
From: "Shawn O. Pearce" <>
To: Jeff King <>
Cc:, Junio C Hamano <>
Subject: Re: [PATCH] fast-import: use binary search in tree_content_remove
Date: Sat, 10 Mar 2007 22:38:33 -0500
Message-ID: <> (raw)
In-Reply-To: <>

Jeff King <> 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:

From 0af148553a94f7e856089fa68395524932240145 Mon Sep 17 00:00:00 2001
From: Shawn O. Pearce <>
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:


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 <>
 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(

  reply index

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <<>
2007-03-10 19:16 ` [PATCH 1/3] fast-import: grow tree storage more aggressively Jeff King
2007-03-10 19:21 ` [PATCH 2/3] fast-import: tree allocation cleanups Jeff King
2007-03-11  3:21   ` Shawn O. Pearce
2007-03-11 15:51     ` Jeff King
2007-03-11 15:59       ` Jeff King
2007-03-12 19:16       ` Shawn O. Pearce
2007-03-10 19:21 ` [PATCH 3/3] fast-import: improve efficiency of tree_content_set Jeff King
2007-03-10 19:23   ` Jeff King
2007-03-10 19:40     ` [PATCH] fast-import: use binary search in tree_content_remove Jeff King
2007-03-11  3:38       ` Shawn O. Pearce [this message]
2007-03-11 16:34         ` Jeff King
2007-03-11 16:54           ` Jeff King
2007-03-11 20:19             ` Shawn O. Pearce
2007-03-12 19:13           ` Shawn O. Pearce

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

  List information:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link mailing list mirror (one of many)

Archives are clonable:
	git clone --mirror
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:

 note: .onion URLs require Tor:
       or Tor2web:

AGPL code for this site: git clone public-inbox