* Re: Improving merge failure message
From: Junio C Hamano @ 2009-09-08 7:15 UTC (permalink / raw)
To: Nanako Shiraishi; +Cc: git
In-Reply-To: <7vbplmhr0i.fsf@alter.siamese.dyndns.org>
Junio C Hamano <gitster@pobox.com> writes:
> Nanako Shiraishi <nanako3@lavabit.com> writes:
>
>> [2]% git merge feature
>> error: Entry 'cool' not uptodate. Cannot merge.
>> fatal: merging of trees 8ec1d96451ff05451720e4e8968812c46b35e5e4 and aad8d5cef3915ab78b3227abaaac99b62db9eb54 failed
>>
>> ... the messages look unnecessarily scary, with two
>> "error" and "fatal" comments, and long sha1 commit names.
>
> Just a technical nit. I think these are tree object names.
>
>> Those of us who used git for some time can tell what it wants to say.
>> The merge checked the files in the working tree before doing anything,
>> found that the user has uncommitted change to a file that is involved in
>> the merge, and it stopped. And it didn't change anything. It may be "fatal"
>> but the user has much less reason to be scared about this failure than
>> the conflicting case.
>>
>> It would be nice if the message in the latter case can be toned down.
>
> Yeah, it would be nice. This actually was something that bothered me as
> well while trying to explain the recovery procedure for these two cases.
> Give me half an hour or so to cook up something...
It turns out to be a lot simpler than I thought, because 8ccba00
(unpack-trees: allow Porcelain to give different error messages,
2008-05-17) already laid enough groundwork for doing this kind of thing
easily.
Notable points are:
- End the messages with "Aborting."; they are given when the three-way
merge stops without harming the work tree;
- Do not give the extra message after unpack_trees() already errored out.
This "merging of trees failed" message was primarily for debugging
merge-recursive itself, and the end user cannot do much with the object
names given in the message anyway.
But do give it under higher verbosity level, or when it happens during
the inner merge (the "recursive" one), as unpack_trees() should not
fail for the inner merge under normal conditions.
We could later add instructions on how to recover (i.e. "stash changes
away or commit on a side branch and retry") instead of the silent
exit(128) I have down there, and then use Peff's advice.* mechanism to
squelch it (e.g. "advice.mergeindirtytree"), but they are separate topics.
merge-recursive.c | 25 +++++++++++++++++++++----
1 files changed, 21 insertions(+), 4 deletions(-)
diff --git a/merge-recursive.c b/merge-recursive.c
index 10d7913..a237240 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -170,6 +170,18 @@ static int git_merge_trees(int index_only,
int rc;
struct tree_desc t[3];
struct unpack_trees_options opts;
+ static struct unpack_trees_error_msgs msgs = {
+ /* would_overwrite */
+ "Your local changes to '%s' will be clobbered by merge. Aborting.",
+ /* not_uptodate_file */
+ "Your local changes to '%s' will be clobbered by merge. Aborting.",
+ /* not_uptodate_dir */
+ "Updating '%s' would lose untracked files in it. Aborting.",
+ /* would_lose_untracked */
+ "Untracked working tree file '%s' would be %s by merge. Aborting",
+ /* bind_overlap -- will not happen here */
+ NULL,
+ };
memset(&opts, 0, sizeof(opts));
if (index_only)
@@ -181,6 +193,7 @@ static int git_merge_trees(int index_only,
opts.fn = threeway_merge;
opts.src_index = &the_index;
opts.dst_index = &the_index;
+ opts.msgs = msgs;
init_tree_desc_from_tree(t+0, common);
init_tree_desc_from_tree(t+1, head);
@@ -1188,10 +1201,14 @@ int merge_trees(struct merge_options *o,
code = git_merge_trees(o->call_depth, common, head, merge);
- if (code != 0)
- die("merging of trees %s and %s failed",
- sha1_to_hex(head->object.sha1),
- sha1_to_hex(merge->object.sha1));
+ if (code != 0) {
+ if (show(o, 4) || o->call_depth)
+ die("merging of trees %s and %s failed",
+ sha1_to_hex(head->object.sha1),
+ sha1_to_hex(merge->object.sha1));
+ else
+ exit(128);
+ }
if (unmerged_cache()) {
struct string_list *entries, *re_head, *re_merge;
^ permalink raw reply related
* Re: [PATCHv2 2/2] Add url.<base>.pushInsteadOf: URL rewriting for push only
From: Josh Triplett @ 2009-09-08 7:15 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7vws49gbql.fsf@alter.siamese.dyndns.org>
On Tue, Sep 08, 2009 at 12:02:42AM -0700, Junio C Hamano wrote:
> Josh Triplett <josh@joshtriplett.org> writes:
>
> > This configuration option allows systematically rewriting fetch-only
> > URLs to push-capable URLs when used with push. For instance:
> >
> > [url "ssh://example.org/"]
> > pushInsteadOf = "git://example.org/"
> >
> > This will allow clones of "git://example.org/path/to/repo" to
> > subsequently push to "ssh://example.org/path/to/repo", without manually
> > configuring pushurl for that remote.
> >
> > Includes documentation for the new option, bash completion updates, and
> > test cases (both that pushInsteadOf applies to push and that it does
> > *not* apply to fetch).
>
> Thanks.
>
> I will queue these patches, but I presume you would also want to add a
> test that pushInsteadOf is ignored for remotes with an explicit pushURL?
Will do.
- Josh Triplett
^ permalink raw reply
* Re: [PATCH resend] git-pull: fix fetch-options.txt to not document --quiet and --verbose twice in git-pull.txt
From: Emmanuel Trillaud @ 2009-09-08 7:07 UTC (permalink / raw)
To: Matthieu Moy; +Cc: Git Mailing List
In-Reply-To: <vpqd462kl4p.fsf@bauges.imag.fr>
Thank you for your patience.
Because I want to be kind to our maintainer :-), I've just finish a
complete reading of SubmitingPatches. Next time I promise : no more
whistespace mess and a commit message were it is meant to be.
Best regards
Emmanuel Trillaud
^ permalink raw reply
* Re: [PATCH] git-rebase-interactive: avoid breaking when GREP_OPTIONS="-H"
From: Junio C Hamano @ 2009-09-08 7:02 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Carlo Marcelo Arenas Belon, git
In-Reply-To: <7v7hwar1fp.fsf@alter.siamese.dyndns.org>
Junio C Hamano <gitster@pobox.com> writes:
> Carlo Marcelo Arenas Belon <carenas@sajinet.com.pe> writes:
>
>> if GREP_OPTIONS is set and includes -H, using `grep -c` will fail
>> to generate a numeric count and result in the following error :
>>
>> /usr/libexec/git-core/git-rebase--interactive: line 110: (standard
>> input):1+(standard input):0: missing `)' (error token is
>> "input):1+(standard input):0")
>>
>> instead of grep counting use `wc -l` to return the line count.
>
> Thanks.
>
> How does your patch help when the user has GREP_OPTIONS=-C3 in the
> environment?
>
> I think a saner workaround for this user environment bug (or GNU grep
> misfeature) is to unset GREP_OPTIONS at the beginning of the script, or
> even in git-sh-setup.
Or even this.
git.c | 13 +++++++++++++
1 files changed, 13 insertions(+), 0 deletions(-)
diff --git a/git.c b/git.c
index 0b22595..3548154 100644
--- a/git.c
+++ b/git.c
@@ -450,11 +450,24 @@ static int run_argv(int *argcp, const char ***argv)
return done_alias;
}
+static void sanitize_env(void) {
+ static const char *vars[] = {
+ "GREP_OPTIONS",
+ "GREP_COLOR",
+ "GREP_COLORS",
+ NULL,
+ };
+ const char **p;
+
+ for (p = vars; *p; p++)
+ unsetenv(*p);
+}
int main(int argc, const char **argv)
{
const char *cmd;
+ sanitize_env();
cmd = git_extract_argv0_path(argv[0]);
if (!cmd)
cmd = "git-help";
^ permalink raw reply related
* Re: [PATCHv2 2/2] Add url.<base>.pushInsteadOf: URL rewriting for push only
From: Junio C Hamano @ 2009-09-08 7:02 UTC (permalink / raw)
To: Josh Triplett; +Cc: git
In-Reply-To: <5e58748923d9b4a182499a6ba8fa4636bce4810e.1252313313.git.josh@joshtriplett.org>
Josh Triplett <josh@joshtriplett.org> writes:
> This configuration option allows systematically rewriting fetch-only
> URLs to push-capable URLs when used with push. For instance:
>
> [url "ssh://example.org/"]
> pushInsteadOf = "git://example.org/"
>
> This will allow clones of "git://example.org/path/to/repo" to
> subsequently push to "ssh://example.org/path/to/repo", without manually
> configuring pushurl for that remote.
>
> Includes documentation for the new option, bash completion updates, and
> test cases (both that pushInsteadOf applies to push and that it does
> *not* apply to fetch).
Thanks.
I will queue these patches, but I presume you would also want to add a
test that pushInsteadOf is ignored for remotes with an explicit pushURL?
^ permalink raw reply
* [PATCH] completion: complete --scissors option of git-am
From: Stephen Boyd @ 2009-09-08 6:57 UTC (permalink / raw)
To: Shawn O. Pearce; +Cc: Junio C Hamano, git
Signed-off-by: Stephen Boyd <bebarino@gmail.com>
---
contrib/completion/git-completion.bash | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index bf688e1..226e3ea 100755
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -676,7 +676,7 @@ _git_am ()
--3way --committer-date-is-author-date --ignore-date
--ignore-whitespace --ignore-space-change
--interactive --keep --no-utf8 --signoff --utf8
- --whitespace=
+ --whitespace= --scissors
"
return
esac
--
1.6.5.rc0
^ permalink raw reply related
* Re: [PATCH] git-rebase-interactive: avoid breaking when GREP_OPTIONS="-H"
From: Junio C Hamano @ 2009-09-08 6:54 UTC (permalink / raw)
To: Carlo Marcelo Arenas Belon; +Cc: git
In-Reply-To: <20090908064756.GA14155@sajinet.com.pe>
Carlo Marcelo Arenas Belon <carenas@sajinet.com.pe> writes:
> On Mon, Sep 07, 2009 at 12:37:30PM -0700, Junio C Hamano wrote:
>>
>> How does your patch help when the user has GREP_OPTIONS=-C3 in the
>> environment?
>
> It wouldn't help but at least wouldn't break aborting with an script
> error since you will always get a number.
That's actually worse, don't you think?
It is trying to count how many actions are done and how many are
remaining, and if you miscount it in that shell function, you will get
incorrect result. The function happens to be merely for reporting, but
the point is that it is better to fail loudly than doing wrong thing.
>> I think a saner workaround for this user environment bug (or GNU grep
>> misfeature) is to unset GREP_OPTIONS at the beginning of the script, or
>> even in git-sh-setup.
>
> agree, and since grep is used almost everywhere filtering in git-sh-setup
> like CDPATH is makes sense, with the only user of grep that wouldn't
> benefit from that being git-mergetool--lib.sh AFAIK.
Not at all. "git grep" itself will be broken. See my other patch for a
possible alternative approach.
^ permalink raw reply
* Re: What's cooking in git.git (Sep 2009, #02; Mon, 07)
From: Junio C Hamano @ 2009-09-08 6:48 UTC (permalink / raw)
To: Nanako Shiraishi; +Cc: git
In-Reply-To: <20090908153109.6117@nanako3.lavabit.com>
Nanako Shiraishi <nanako3@lavabit.com> writes:
> Quoting Junio C Hamano <gitster@pobox.com>
>
>> ... I'm also hoping to tag the real 1.6.5 before I vanish for
>> about a week and half later in the month....
>
> Are you coming to Japan to promote your book, perhaps giving autographs at bookstores?
It will come out around 19th if things go as planned, but I'll be arriving
the week after that so I'll be too late for that kind of thing.
Besides, who would want an autographed copy of a technical book?
I should start asking the usual suspect to take things over while I'm
offline...
^ permalink raw reply
* Re: [PATCH] git-rebase-interactive: avoid breaking when GREP_OPTIONS="-H"
From: Carlo Marcelo Arenas Belon @ 2009-09-08 6:47 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7v7hwar1fp.fsf@alter.siamese.dyndns.org>
On Mon, Sep 07, 2009 at 12:37:30PM -0700, Junio C Hamano wrote:
>
> How does your patch help when the user has GREP_OPTIONS=-C3 in the
> environment?
It wouldn't help but at least wouldn't break aborting with an script
error since you will always get a number.
> I think a saner workaround for this user environment bug (or GNU grep
> misfeature) is to unset GREP_OPTIONS at the beginning of the script, or
> even in git-sh-setup.
agree, and since grep is used almost everywhere filtering in git-sh-setup
like CDPATH is makes sense, with the only user of grep that wouldn't
benefit from that being git-mergetool--lib.sh AFAIK.
will test and submit a fix for that later, but still think the original
patch at least improves the status quo (will protect also when using
custom grep wrappers as reported earlier) and doesn't do any harm as wc
is already a dependency as well and was part of the original code as well.
Carlo
^ permalink raw reply
* Re: Improving merge failure message
From: Junio C Hamano @ 2009-09-08 6:47 UTC (permalink / raw)
To: Nanako Shiraishi; +Cc: git
In-Reply-To: <20090908153101.6117@nanako3.lavabit.com>
Nanako Shiraishi <nanako3@lavabit.com> writes:
> [2]% git merge feature
> error: Entry 'cool' not uptodate. Cannot merge.
> fatal: merging of trees 8ec1d96451ff05451720e4e8968812c46b35e5e4 and aad8d5cef3915ab78b3227abaaac99b62db9eb54 failed
>
> ... the messages look unnecessarily scary, with two
> "error" and "fatal" comments, and long sha1 commit names.
Just a technical nit. I think these are tree object names.
> Those of us who used git for some time can tell what it wants to say.
> The merge checked the files in the working tree before doing anything,
> found that the user has uncommitted change to a file that is involved in
> the merge, and it stopped. And it didn't change anything. It may be "fatal"
> but the user has much less reason to be scared about this failure than
> the conflicting case.
>
> It would be nice if the message in the latter case can be toned down.
Yeah, it would be nice. This actually was something that bothered me as
well while trying to explain the recovery procedure for these two cases.
Give me half an hour or so to cook up something...
^ permalink raw reply
* Re: What's cooking in git.git (Sep 2009, #02; Mon, 07)
From: Nanako Shiraishi @ 2009-09-08 6:31 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7vtyzexnhm.fsf@alter.siamese.dyndns.org>
Quoting Junio C Hamano <gitster@pobox.com>
> I tagged and pushed out 1.6.5-rc0. There are still some topics cooking in
> 'next' I would rather not leave out, but I've been hoping to keep this
> cycle short, and I'm also hoping to tag the real 1.6.5 before I vanish for
> about a week and half later in the month. so in the worst case there may
> have to be a 1.6.6 to include the leftover topics.
Are you coming to Japan to promote your book, perhaps giving autographs at bookstores?
--
Nanako Shiraishi
http://ivory.ap.teacup.com/nanako3/
^ permalink raw reply
* Improving merge failure message
From: Nanako Shiraishi @ 2009-09-08 6:31 UTC (permalink / raw)
To: git
I often see my students confused after a failed merge and they can't
figure out what to do next. Two typical error messages they get are
[1]% git merge master
Auto-merging cool
CONFLICT (content): Merge conflict in cool
Automatic merge failed; fix conflicts and then commit the result.
[2]% git merge feature
error: Entry 'cool' not uptodate. Cannot merge.
fatal: merging of trees 8ec1d96451ff05451720e4e8968812c46b35e5e4 and aad8d5cef3915ab78b3227abaaac99b62db9eb54 failed
In the former case, the merge command gives a helpful message that
automatic merge failed because it found a conflict and tells enough
instruction to the user.
But in the latter case, the messages look unnecessarily scary, with two
"error" and "fatal" comments, and long sha1 commit names.
Those of us who used git for some time can tell what it wants to say.
The merge checked the files in the working tree before doing anything,
found that the user has uncommitted change to a file that is involved in
the merge, and it stopped. And it didn't change anything. It may be "fatal"
but the user has much less reason to be scared about this failure than
the conflicting case.
It would be nice if the message in the latter case can be toned down.
--
Nanako Shiraishi
http://ivory.ap.teacup.com/nanako3/
^ permalink raw reply
* Re: [PATCH resend] git-pull: fix fetch-options.txt to not document --quiet and --verbose twice in git-pull.txt
From: Matthieu Moy @ 2009-09-08 6:26 UTC (permalink / raw)
To: Emmanuel Trillaud; +Cc: Git Mailing List
In-Reply-To: <9f50533b0909070534q2375a793mf5d676b519eae69@mail.gmail.com>
Emmanuel Trillaud <etrillaud@gmail.com> writes:
> Hello all,
> In git-pull(1) we can read :
[...]
> Best regard
I guess this part of your message is not meant to appear in the commit
message. If you leave it here, Junio will have to edit it manually,
whereas if you put it where Documentation/SubmitingPatches suggests,
i.e.
> ---
here (between --- and diffstat), it's done automatically. Be nice to
our maintainer, and our mainainer will be nice to you ;-).
> Documentation/fetch-options.txt | 2 ++
> 1 files changed, 2 insertions(+), 0 deletions(-)
--
Matthieu Moy
http://www-verimag.imag.fr/~moy/
^ permalink raw reply
* Re: [PATCH] Add more instructions about how to install git.
From: Matthieu Moy @ 2009-09-08 6:20 UTC (permalink / raw)
To: Alex Riesen; +Cc: Thiago Farina, git
In-Reply-To: <81b0412b0909072244k21a4ddf6vdc38d9f713a4a084@mail.gmail.com>
Alex Riesen <raa.lkml@gmail.com> writes:
> On Tue, Sep 8, 2009 at 07:11, Thiago Farina<tfransosi@gmail.com> wrote:
>> Signed-off-by: Thiago Farina <tfransosi@gmail.com>
>> ---
>> INSTALL | 9 +++++++++
>> 1 files changed, 9 insertions(+), 0 deletions(-)
>>
>> diff --git a/INSTALL b/INSTALL
>> index ae7f750..67abfc7 100644
>> --- a/INSTALL
>> +++ b/INSTALL
>> @@ -1,6 +1,15 @@
>>
>> Git installation
>>
>> +To install git follow these 4 steps inside your git directory:
>> +$ autoconf # Generates the configure file from configure.ac
>> +$ ./configure # Configures everything needed to build git
>> +$ make all # Compiles git based in the Makefile
>> +$ make install # Installs git in your own ~/bin directory
Your commit message doesn't say what's wrong with
| Alternatively you can use autoconf generated ./configure script to
| set up install paths (via config.mak.autogen), so you can write
| instead
|
| $ make configure ;# as yourself
| $ ./configure --prefix=/usr ;# as yourself
| $ make all doc ;# as yourself
| # make install install-doc install-html;# as root
which is already in INSTALL a few lines after what your patch adds.
>> +If you don't have autoconf installed, you can do this by:
>> +$ sudo apt-get install autoconf
>
> ... if you're on a Debian-derived system.
and if you have sudo configured.
BTW, apt-get is anyway somehow deprecaded, you should
s/apt-get/aptitude/.
--
Matthieu Moy
http://www-verimag.imag.fr/~moy/
^ permalink raw reply
* Re: [PATCH] Add more instructions about how to install git.
From: Alex Riesen @ 2009-09-08 5:44 UTC (permalink / raw)
To: Thiago Farina; +Cc: git
In-Reply-To: <1252386686-15689-1-git-send-email-tfransosi@gmail.com>
On Tue, Sep 8, 2009 at 07:11, Thiago Farina<tfransosi@gmail.com> wrote:
> Signed-off-by: Thiago Farina <tfransosi@gmail.com>
> ---
> INSTALL | 9 +++++++++
> 1 files changed, 9 insertions(+), 0 deletions(-)
>
> diff --git a/INSTALL b/INSTALL
> index ae7f750..67abfc7 100644
> --- a/INSTALL
> +++ b/INSTALL
> @@ -1,6 +1,15 @@
>
> Git installation
>
> +To install git follow these 4 steps inside your git directory:
> +$ autoconf # Generates the configure file from configure.ac
> +$ ./configure # Configures everything needed to build git
> +$ make all # Compiles git based in the Makefile
> +$ make install # Installs git in your own ~/bin directory
> +
> +If you don't have autoconf installed, you can do this by:
> +$ sudo apt-get install autoconf
... if you're on a Debian-derived system. The other half of the
world, which is RedHat-derived, uses RPM. And there are
other package management tools. Maybe that was a reason
why the instructions weren't included before.
^ permalink raw reply
* [PATCH] Add more instructions about how to install git.
From: Thiago Farina @ 2009-09-08 5:11 UTC (permalink / raw)
To: git; +Cc: Thiago Farina
Signed-off-by: Thiago Farina <tfransosi@gmail.com>
---
INSTALL | 9 +++++++++
1 files changed, 9 insertions(+), 0 deletions(-)
diff --git a/INSTALL b/INSTALL
index ae7f750..67abfc7 100644
--- a/INSTALL
+++ b/INSTALL
@@ -1,6 +1,15 @@
Git installation
+To install git follow these 4 steps inside your git directory:
+$ autoconf # Generates the configure file from configure.ac
+$ ./configure # Configures everything needed to build git
+$ make all # Compiles git based in the Makefile
+$ make install # Installs git in your own ~/bin directory
+
+If you don't have autoconf installed, you can do this by:
+$ sudo apt-get install autoconf
+
Normally you can just do "make" followed by "make install", and that
will install the git programs in your own ~/bin/ directory. If you want
to do a global install, you can do
--
1.6.0.4
^ permalink raw reply related
* Re: [PATCHv5 00/14] git notes
From: Junio C Hamano @ 2009-09-08 4:16 UTC (permalink / raw)
To: Johan Herland
Cc: git, gitster, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce
In-Reply-To: <200909080512.34634.johan@herland.net>
Johan Herland <johan@herland.net> writes:
> Furthermore, the following notes tree structures were tested:
>
> - "no-notes": Testing without any notes at all. This is only present as a
> baseline, and to verify that the notes code does not negatively affect
> performance when not in use.
Minor nit.
For this to be a baseline, you would need to have another algorithm before
"before", i.e., without any of these notes implementation.
Comparison with "before" alone is not meaningful. That is like starting
with a state with unknown performance regression compared to the stock
version, and then boast improvements made by various variations.
You would need to compare overhead of various "algorithms" with the stock
git in "no-notes" case as well. It would give us the true performance
cost of supporting notes.
^ permalink raw reply
* Re: [PATCHv5 00/14] git notes
From: Johan Herland @ 2009-09-08 3:12 UTC (permalink / raw)
To: git; +Cc: gitster, Johannes.Schindelin, trast, tavestbo, git, chriscool,
spearce
In-Reply-To: <1252376822-6138-1-git-send-email-johan@herland.net>
[-- Attachment #1: Type: Text/Plain, Size: 4066 bytes --]
On Tuesday 08 September 2009, Johan Herland wrote:
> I have some performance numbers that I will send in a separate email.
Ok, here we go:
Test scenario:
Linux kernel repo with 157118 commits, 1 note per commit, with notes
organized into various fanout schemes.
Hardware is Intel Core 2 Quad with 4GB RAM.
The tests were done on the following algorithms:
- "before": This is the state of the notes code after applying patches 1-9.
It uses the original notes-in-hash-map implementation, and does not grok
any fanout scheme.
- "16tree": This is the state of the notes code after applying patch 10.
It uses the 16-tree data structure that parses the SHA-1 based fanout
schemes.
- "flexible": This is the state of the notes code after applying the entire
patch series. This code parses a variety of date- and SHA1-based fanout
schemes.
Furthermore, the following notes tree structures were tested:
- "no-notes": Testing without any notes at all. This is only present as a
baseline, and to verify that the notes code does not negatively affect
performance when not in use.
- "no-fanout": All notes stored directly inside the root notes tree object.
- "2_38": All notes stored in a SHA1-based 2/38 fanout scheme.
- "2_2_36": All notes stored in a SHA1-based 2/2/36 fanout scheme.
- "ym": Notes are organized within "yYYYYmMM"-named subtrees, where "YYYY"
and "MM" are the year and month (respectively) from the annotated commit's
commit date.
- "ym_2_38": Same as above, but with a 2/38 SHA1-based fanout scheme within
the "yYYYYmMM"-named subtrees.
- "ymd": Notes are organized within "yYYYYmMMdDD"-named subtrees.
- "ymd_2_38": Same as above, but with a 2/38 SHA1-based fanout scheme within
the "yYYYYmMMdDD"-named subtrees.
- "y_m": Notes are organized within two-level "yYYYY/mMM" subtrees.
- "y_m_2_38": Same as above, but with a 2/38 SHA1-based fanout scheme within
the "yYYYY/mMM"-named subtrees.
- "y_m_d": Notes are organized within three-level "yYYYY/mMM/dDD" subtrees.
- "y_m_d_2_38": Same as above, but with a 2/38 SHA1-based fanout scheme
within the "yYYYY/mMM/dDD"-named subtrees.
Here are the runtime numbers, the first column shows the runtime for 100
repetitions of "git log -n10" (which we assume to be a common use case),
and the second column shows the runtime from a single run of
"git log --all" (which is somewhat closer to a worst case).
Algorithm / Notes tree git log -n10 (x100) git log --all
------------------------------------------------------------
before / no-notes 4.78s 63.90s
before / no-fanout 56.85s 65.69s
16tree / no-notes 4.77s 64.18s
16tree / no-fanout 30.35s 65.39s
16tree / 2_38 5.57s 65.42s
16tree / 2_2_36 5.19s 65.76s
flexible / no-notes 4.78s 63.91s
flexible / no-fanout 30.34s 65.57s
flexible / 2_38 5.57s 65.46s
flexible / 2_2_36 5.18s 65.72s
flexible / ym 5.13s 65.66s
flexible / ym_2_38 5.08s 65.63s
flexible / ymd 5.30s 65.45s
flexible / ymd_2_38 5.29s 65.90s
flexible / y_m 5.11s 65.72s
flexible / y_m_2_38 5.08s 65.67s
flexible / y_m_d 5.06s 65.50s
flexible / y_m_d_2_38 5.07s 65.79s
Finally, I have also looked at the memory consumption of the various
algorithms and fanout schemes:
The memory usage was measured by calculating the #bytes dynamically
allocated for the notes data structure, and printing the current
usage every time get_commit_notes() was called during a complete run
of "git log --all".
The results are attached as two gnuplot graphs, one with regular
axes, and one with logarithmic axes.
Have fun! :)
...Johan
--
Johan Herland, <johan@herland.net>
www.herland.net
[-- Attachment #2: memusage_gnuplot.png --]
[-- Type: image/png, Size: 18323 bytes --]
[-- Attachment #3: memusage_gnuplot_log.png --]
[-- Type: image/png, Size: 28646 bytes --]
^ permalink raw reply
* [PATCHv5 10/14] Teach notes code to free its internal data structures on request.
From: Johan Herland @ 2009-09-08 2:26 UTC (permalink / raw)
To: gitster
Cc: git, johan, Johannes.Schindelin, trast, tavestbo, git, chriscool,
spearce
In-Reply-To: <1252376822-6138-1-git-send-email-johan@herland.net>
There's no need to be rude to memory-concious callers...
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 7 +++++++
notes.h | 2 ++
2 files changed, 9 insertions(+), 0 deletions(-)
diff --git a/notes.c b/notes.c
index 84c30c1..008c3d4 100644
--- a/notes.c
+++ b/notes.c
@@ -160,3 +160,10 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
free(msg);
}
+
+void free_commit_notes()
+{
+ free(hash_map.entries);
+ memset(&hash_map, 0, sizeof(struct hash_map));
+ initialized = 0;
+}
diff --git a/notes.h b/notes.h
index 7f3eed4..41802e5 100644
--- a/notes.h
+++ b/notes.h
@@ -7,4 +7,6 @@
void get_commit_notes(const struct commit *commit, struct strbuf *sb,
const char *output_encoding, int flags);
+void free_commit_notes();
+
#endif
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [PATCHv5 09/14] Add '%N'-format for pretty-printing commit notes
From: Johan Herland @ 2009-09-08 2:26 UTC (permalink / raw)
To: gitster
Cc: git, johan, Johannes.Schindelin, trast, tavestbo, git, chriscool,
spearce
In-Reply-To: <1252376822-6138-1-git-send-email-johan@herland.net>
From: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Johan Herland <johan@herland.net>
---
Documentation/pretty-formats.txt | 1 +
pretty.c | 4 ++++
2 files changed, 5 insertions(+), 0 deletions(-)
diff --git a/Documentation/pretty-formats.txt b/Documentation/pretty-formats.txt
index 2a845b1..5fb10b3 100644
--- a/Documentation/pretty-formats.txt
+++ b/Documentation/pretty-formats.txt
@@ -123,6 +123,7 @@ The placeholders are:
- '%s': subject
- '%f': sanitized subject line, suitable for a filename
- '%b': body
+- '%N': commit notes
- '%Cred': switch color to red
- '%Cgreen': switch color to green
- '%Cblue': switch color to blue
diff --git a/pretty.c b/pretty.c
index 01eadd0..7f350bb 100644
--- a/pretty.c
+++ b/pretty.c
@@ -702,6 +702,10 @@ static size_t format_commit_item(struct strbuf *sb, const char *placeholder,
case 'd':
format_decoration(sb, commit);
return 1;
+ case 'N':
+ get_commit_notes(commit, sb, git_log_output_encoding ?
+ git_log_output_encoding : git_commit_encoding, 0);
+ return 1;
}
/* For the rest we have to parse the commit header. */
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [PATCHv5 13/14] Allow flexible organization of notes trees, using both commit date and SHA1
From: Johan Herland @ 2009-09-08 2:27 UTC (permalink / raw)
To: gitster
Cc: git, johan, Johannes.Schindelin, trast, tavestbo, git, chriscool,
spearce
In-Reply-To: <1252376822-6138-1-git-send-email-johan@herland.net>
This is a major expansion of the notes lookup code to allow for variations
in the notes tree organization. The variations allowed include mixing fanout
schemes based on the commit dates of the annotated commits (aka. date-based
fanout) with fanout schemes based on the SHA1 of the annotated commits (aka.
SHA1-based fanout).
Using date-based fanout in the notes tree structure enables considerable
speedup in the notes lookup process, since notes are almost always looked up
sequentially in the (reverse) chronological order of their associated commits.
Furthermore, organizing notes in a way that allow (near) sequential lookup,
enables us to decrease memory consumption both by lazily loading parts of the
notes tree structure on-demand, and freeing parts of the notes structure that
are unlikely to be used again soon.
The new flexible organization of the notes tree changes the rules for valid
note tree entries. The new rules are as follows:
1. Note objects are named by the SHA1 of the commit they annotate, possibly
split across several SHA1-based fanout levels (this is the same as is
implemented earlier in this series).
2. Note entries are located within zero or more date-based fanout levels.
3. Date-based fanout schemes may use the year, month and day values of the
associated commit's timestamp. The values must be prefixed by 'y', 'm'
and 'd' (respectively) in the notes tree.
4. The date-based components can be combined in one fanout level, or split
across multiple fanout levels. Individual components may not be split
across multiple fanout levels.
5. The year/month/date values must be specified in that order, and month or
date values may not occur without the preceding year or month value.
6. All entries of a tree object in the notes tree structure must follow the
same scheme used at that level.
Thus, the following example note entries are all valid locations for a note
annotating commit 123456789abcdef0123456789abcdef0123456789 at 2009-09-01:
- 123456789abcdef0123456789abcdef0123456789
- 12/3456789abcdef0123456789abcdef0123456789
- 1234/56789abcdef0123456789abcdef0123456789
- 12/34/56789abcdef0123456789abcdef0123456789
- 1234/5678/9abcdef0123456789abcdef0123456789
- 1234/56/78/9abcdef0123456789abcdef0123456789
- y2009/123456789abcdef0123456789abcdef0123456789
- y2009/m09/12/3456789abcdef0123456789abcdef0123456789
- y2009/m09/d01/123456789abcdef0123456789abcdef0123456789
- y2009m09/12/34/56789abcdef0123456789abcdef0123456789
- y2009m09/d01/1234/567/89abcdef0123456789abcdef0123456789
- y2009/m09d01/12/34/56/78/9abcdef0123456789abcdef0123456789
- y2009m09d01/123456789abcdef0123456789abcdef0123456789
Conversely, the following example note entries are all invalid:
- 1/23456789abcdef0123456789abcdef0123456789 (violates #1)
- 123/456789abcdef0123456789abcdef0123456789 (violates #1)
- 12/345/6789abcdef0123456789abcdef0123456789 (violates #1)
- y2009123456789abcdef0123456789abcdef0123456789 (violates #2)
- 2009/09/01/123456789abcdef0123456789abcdef0123456789 (violates #3)
- y20/09/m09/12/3456789abcdef0123456789abcdef0123456789 (violates #4)
- y20/09m09/d01/123456789abcdef0123456789abcdef0123456789 (violates #4)
- y2009m/09/12/34/56789abcdef0123456789abcdef0123456789 (violates #4)
- y2009/d01/1234/5678/9abcdef0123456789abcdef0123456789 (violates #5)
- m09/y2009/d01/12/34/56/78/9abcdef0123456789abcdef0123456789 (violates #5)
>From rule #6, we see that the following example notes tree is valid:
- y2009m09/0123456789abcdef0123456789abcdef012345678
- y2009m09/123456789abcdef0123456789abcdef0123456789
- y2008m01/d31/23/456789abcdef0123456789abcdef0123456789a
- y2008m01/d31/34/56789abcdef0123456789abcdef0123456789ab
- y2008m01/d16/4567/89abcdef0123456789abcdef0123456789abc
- y2008m01/d16/5678/9abcdef0123456789abcdef0123456789abcd
Conversely the following structure is invalid (violates rule #6):
- y2009m09/0123456789abcdef0123456789abcdef012345678
- y2009m09/12/3456789abcdef0123456789abcdef0123456789
- y2008m01/d31/23/456789abcdef0123456789abcdef0123456789a
- y2008m01/34/56789abcdef0123456789abcdef0123456789ab
- y2008m01/d16/45/6789abcdef0123456789abcdef0123456789abc
- y2008/m01d16/5678/9abcdef0123456789abcdef0123456789abcd
The flexibility added by this patch adds considerable complexity to the notes
tree parser, but the runtime and memory usage is not significantly affected
(except for the effects introduced by the chosen notes tree structure).
Internally, the 16-tree data structure introduced in earlier patches is still
used to hold the SHA1-based fanout levels and the note entries themselves.
However, this patch adds a hierarchical date-based linked-list structure
around the 16-tree structure that mirrors the fanout scheme used in the
actual notes tree.
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 403 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
1 files changed, 364 insertions(+), 39 deletions(-)
diff --git a/notes.c b/notes.c
index 6926aa6..a3e3f83 100644
--- a/notes.c
+++ b/notes.c
@@ -7,6 +7,70 @@
#include "tree-walk.h"
/*
+ * Format of entries in the notes tree structure:
+ *
+ * note-entry ::= (period sep)? sha1-spec
+ * period ::= year sep?
+ * (month sep?
+ * (date sep?)?
+ * )?;
+ * year ::= 'y' yearnum;
+ * month ::= 'm' monthnum;
+ * date ::= 'd' datenum;
+ * yearnum ::= # 4-digit decimal year, from annotated commit's timestamp;
+ * monthnum ::= # 2-digit decimal month, from annotated commit's timestamp;
+ * datenum ::= # 2-digit decimal date, from annotated commit's timestamp;
+ * sha1-spec ::= (hex-fragment sep?){20}
+ * sep ::= '/';
+ * hex-fragment ::= # Fragment of hexsha1 (2 bytes);
+ * hexsha1 ::= # SHA1 of annotated commit in hex format (40 bytes);
+ *
+ * Thus, the following example note entries are all valid:
+ * - 0123456789abcdef0123456789abcdef012345678
+ * - 01/23456789abcdef0123456789abcdef012345678
+ * - 0123/456789abcdef0123456789abcdef012345678
+ * - 01/23/456789abcdef0123456789abcdef012345678
+ * - 0123/4567/89abcdef0123456789abcdef012345678
+ * - 0123/45/67/89abcdef0123456789abcdef012345678
+ * - y2009/0123456789abcdef0123456789abcdef012345678
+ * - y2009/m09/01/23456789abcdef0123456789abcdef012345678
+ * - y2009/m09/d01/0123456789abcdef0123456789abcdef012345678
+ * - y2009m09/01/23/456789abcdef0123456789abcdef012345678
+ * - y2009m09/d01/0123/4567/89abcdef0123456789abcdef012345678
+ * - y2009/m09d01/01/23/45/67/89abcdef0123456789abcdef012345678
+ * - y2009m09d01/0123456789abcdef0123456789abcdef012345678
+ *
+ * and the following example note entries are all invalid:
+ * - 0/123456789abcdef0123456789abcdef012345678
+ * - 012/3456789abcdef0123456789abcdef012345678
+ * - 01/234/56789abcdef0123456789abcdef012345678
+ * - y20090123456789abcdef0123456789abcdef012345678
+ * - y20/09/m09/01/23456789abcdef0123456789abcdef012345678
+ * - y20/09m09/d01/0123456789abcdef0123456789abcdef012345678
+ * - y2009m/09/01/23/456789abcdef0123456789abcdef012345678
+ * - y2009/d01/0123/4567/89abcdef0123456789abcdef012345678
+ * - m09/y2009/d01/01/23/45/67/89abcdef0123456789abcdef012345678
+ *
+ * In addition to the above per-entry rules, we require that _all_ entries at
+ * a given level in the notes tree (levels are separated by '/') follow the
+ * exact same format at that level. Thus the following structure is valid:
+ * - y2009m09/0123456789abcdef0123456789abcdef012345678
+ * - y2009m09/123456789abcdef0123456789abcdef0123456789
+ * - y2008m01/d31/23/456789abcdef0123456789abcdef0123456789a
+ * - y2008m01/d31/34/56789abcdef0123456789abcdef0123456789ab
+ * - y2008m01/d16/4567/89abcdef0123456789abcdef0123456789abc
+ * - y2008m01/d16/5678/9abcdef0123456789abcdef0123456789abcd
+ *
+ * but the following structure is invalid:
+ * - y2009m09/0123456789abcdef0123456789abcdef012345678
+ * - y2009m09/12/3456789abcdef0123456789abcdef0123456789
+ * - y2008m01/d31/23/456789abcdef0123456789abcdef0123456789a
+ * - y2008m01/34/56789abcdef0123456789abcdef0123456789ab
+ * - y2008m01/d16/45/6789abcdef0123456789abcdef0123456789abc
+ * - y2008/m01d16/5678/9abcdef0123456789abcdef0123456789abcd
+ */
+
+/*
* Use a non-balancing simple 16-tree structure with struct int_node as
* internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
* 16-array of pointers to its children.
@@ -17,9 +81,45 @@
* - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
*
* The root node is a statically allocated struct int_node.
+ *
+ * In order to allow date-based fanout schemes in addition to the original
+ * SHA1-based fanout schemes, we need to overload this structure, as follows:
+ * If the first pointer in the 16-array is ~0 (i.e. 0xffffffff on 32-bit
+ * systems and 0xffffffffffffffff on 64-bit systems), then the int_node is NOT
+ * to be interpreted as a 16-array of child node pointers. Rather, the int_node
+ * now represents a period-based node with the following properties:
+ * - The node has a pointer to a "child" node of type struct int_node, which is
+ * EITHER a "regular" int_node object representing the root node of a 16-tree
+ * structure holding notes associated with commits with timestamps within
+ * that time period, OR another period-based int_node representing some
+ * subdivision of the time period.
+ * - The node also has a pointer to a "previous" period-based int_node, which
+ * represents the previous time period for which there exist note objects.
+ * - The node has a pointer to a "parent" node, which is the period-based
+ * int_node that has this int_node as one of its children. This is needed
+ * when traversing the date-based int_nodes looking for a period matching the
+ * given commit. For top-level objects, this is set to NULL.
+ * - The node stores the SHA1 sum of the tree object that represents its child
+ * (within the notes tree structure). Thus, we keep a reference to the child
+ * structure that without necessarily allocating the child node (and
+ * underlying structure).
+ * - Finally, the node has a period string, which indicates the time period of
+ * the notes contained within, typically of the form "YYYY", "YYYY-MM" or
+ * "YYYY-MM-DD", depending on the granularity of the corresponding
+ * period-based entries in the notes tree structure.
*/
struct int_node {
- void *a[16];
+ union {
+ void *a[16];
+ struct {
+ void *magic; /* ~0 "enables" this part of the union */
+ struct int_node *child;
+ struct int_node *prev;
+ struct int_node *parent;
+ unsigned char tree_sha1[20];
+ char period[11]; /* Enough to hold "YYYY-MM-DD" */
+ };
+ };
};
/*
@@ -51,12 +151,18 @@ struct leaf_node {
#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
(memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
+#define SUBTREE_DATE_PREFIXCMP(commit_date, subtree_date) \
+ (prefixcmp(commit_date, subtree_date))
+
static struct int_node root_node;
+static struct int_node *cur_node;
+
static int initialized;
-static void load_subtree(struct leaf_node *subtree, struct int_node *node,
- unsigned int n);
+static void load_subtree(const unsigned char *sha1,
+ const unsigned char *prefix, unsigned int prefix_len,
+ struct int_node *node, struct int_node *parent, int n);
/*
* To find a leaf_node:
@@ -94,7 +200,8 @@ static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
/* unpack tree and resume search */
tree->a[i] = NULL;
- load_subtree(l, tree, n);
+ load_subtree(l->val_sha1, l->key_sha1, l->key_sha1[19],
+ tree, NULL, (int) n);
free(l);
return note_tree_find(tree, n, key_sha1);
}
@@ -117,7 +224,8 @@ static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
/* unpack tree and resume search */
tree->a[0] = NULL;
- load_subtree(l, tree, n);
+ load_subtree(l->val_sha1, l->key_sha1, l->key_sha1[19], tree,
+ NULL, (int) n);
free(l);
return note_tree_find(tree, n, key_sha1);
}
@@ -173,16 +281,28 @@ static int note_tree_insert(struct int_node *tree, unsigned char n,
/* Free the entire notes data contained in the given tree */
static void note_tree_free(struct int_node *tree)
{
- unsigned int i;
- for (i = 0; i < 16; i++) {
- void *p = tree->a[i];
- switch(GET_PTR_TYPE(p)) {
- case PTR_TYPE_INTERNAL:
- note_tree_free(CLR_PTR_TYPE(p));
- /* fall through */
- case PTR_TYPE_NOTE:
- case PTR_TYPE_SUBTREE:
- free(CLR_PTR_TYPE(p));
+ if (tree->magic == (void *) ~0) {
+ if (tree->prev) {
+ note_tree_free(tree->prev);
+ free(tree->prev);
+ }
+ if (tree->child) {
+ note_tree_free(tree->child);
+ free(tree->child);
+ }
+ }
+ else {
+ unsigned int i;
+ for (i = 0; i < 16; i++) {
+ void *p = tree->a[i];
+ switch(GET_PTR_TYPE(p)) {
+ case PTR_TYPE_INTERNAL:
+ note_tree_free(CLR_PTR_TYPE(p));
+ /* fall through */
+ case PTR_TYPE_NOTE:
+ case PTR_TYPE_SUBTREE:
+ free(CLR_PTR_TYPE(p));
+ }
}
}
}
@@ -215,29 +335,139 @@ static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,
return len;
}
-static void load_subtree(struct leaf_node *subtree, struct int_node *node,
- unsigned int n)
+/*
+ * Parse year/month/date strings, and generate the corresponding period string
+ * for the given path entry:
+ * - prefix must follow one of these forms: "", "YYYY", "YYYY-MM"
+ * - path should follow one of these forms: "yYYYY", "yYYYYmMM", "yYYYYmMMdDD",
+ * "mMMdDD", "mMM" or "dDD"
+ * The resulting string (which follows the form "YYYY", "YYYY-MM" or
+ * "YYYY-MM-DD") is returned as a static string. If path is not valid in the
+ * given (prefix) context, NULL is returned.
+ */
+static const char *parse_period(const char *prefix, unsigned int prefix_len,
+ const char *path, unsigned int path_len)
+{
+ static char result[11];
+ char expect_type; /* y/m/d for year/month/day-based fanout */
+ unsigned int expect_len, value;
+ char *endptr, *target = result;
+
+ switch (prefix_len) {
+ case 0:
+ /* No prefix, expect year-based fanout in path */
+ expect_type = 'y';
+ expect_len = 4;
+ break;
+ case 4:
+ /* Year in prefix, expect month-based fanout in path */
+ expect_type = 'm';
+ expect_len = 2;
+ break;
+ case 7:
+ /* "YYYY-MM" in prefix, expect day-based fanout in path */
+ expect_type = 'd';
+ expect_len = 2;
+ break;
+ default:
+ die("Date-based notes tree loading invoked with invalid "
+ "prefix '%.*s'", prefix_len, prefix);
+ }
+
+ if (path[0] != expect_type) {
+ warning("Unexpected entry path in date-based notes tree: '%s' "
+ "(skipping)", path);
+ return NULL;
+ }
+ value = (unsigned int) strtoul(path + 1, &endptr, 10);
+ switch (expect_type) {
+ case 'y':
+ if (value < 1969 || value >= 3000) {
+ warning("Invalid year value in date-based notes tree:"
+ " '%s' (skipping)", path);
+ return NULL;
+ }
+ break;
+ case 'm':
+ if (value < 1 || value > 12) {
+ warning("Invalid month value in date-based notes tree:"
+ " '%s' (skipping)", path);
+ return NULL;
+ }
+ break;
+ case 'd':
+ if (value < 1 || value > 31) {
+ warning("Invalid day value in date-based notes tree:"
+ " '%s' (skipping)", path);
+ return NULL;
+ }
+ break;
+ }
+
+ if (prefix == result) {
+ target = result + prefix_len;
+ prefix = NULL;
+ prefix_len = 0;
+ }
+ prefix_len = snprintf(target, 11, "%.*s%s%0*u", prefix_len, prefix,
+ expect_len == 2 ? "-" : "", expect_len, value);
+ prefix_len += target - result;
+ assert(prefix_len < 11);
+
+ if (*endptr) /* there are more components in this path */
+ return parse_period(result, prefix_len, endptr,
+ path_len - (endptr - path));
+ return result;
+}
+
+static void load_date_subtree(struct tree_desc *tree_desc,
+ const char *prefix, unsigned int prefix_len,
+ struct int_node *node, struct int_node *parent)
+{
+ struct name_entry entry;
+ struct int_node *cur_node = NULL;
+ struct int_node *new_node;
+
+ while (tree_entry(tree_desc, &entry)) {
+ const char *period = parse_period(
+ prefix, prefix_len, entry.path, strlen(entry.path));
+ if (!period)
+ continue;
+ if (tree_desc->size) /* this is not the last tree entry */
+ new_node = (struct int_node *)
+ xmalloc(sizeof(struct int_node));
+ else /* this is the last entry, store directly into node */
+ new_node = node;
+
+ new_node->magic = (void *) ~0;
+ new_node->child = NULL;
+ new_node->prev = cur_node;
+ new_node->parent = parent;
+ hashcpy(new_node->tree_sha1, entry.sha1);
+ strcpy(new_node->period, period);
+ cur_node = new_node;
+ }
+ assert(!cur_node || cur_node == node);
+}
+
+static void load_sha1_subtree(struct tree_desc *tree_desc,
+ const unsigned char *prefix, unsigned int prefix_len,
+ struct int_node *node, unsigned char n)
{
unsigned char commit_sha1[20];
- unsigned int prefix_len;
int status;
- void *buf;
- struct tree_desc desc;
struct name_entry entry;
- buf = fill_tree_descriptor(&desc, subtree->val_sha1);
- if (!buf)
- die("Could not read %s for notes-index",
- sha1_to_hex(subtree->val_sha1));
-
- prefix_len = subtree->key_sha1[19];
assert(prefix_len * 2 >= n);
- memcpy(commit_sha1, subtree->key_sha1, prefix_len);
- while (tree_entry(&desc, &entry)) {
+ memcpy(commit_sha1, prefix, prefix_len);
+ while (tree_entry(tree_desc, &entry)) {
int len = get_sha1_hex_segment(entry.path, strlen(entry.path),
commit_sha1 + prefix_len, 20 - prefix_len);
- if (len < 0)
+ if (len < 0) {
+ warning("Invalid value in notes tree: '%s' (skipping)",
+ entry.path);
continue; /* entry.path is not a SHA1 sum. Skip */
+ }
len += prefix_len;
/*
@@ -258,6 +488,42 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
assert(!status);
}
}
+}
+
+static void load_subtree(const unsigned char *sha1,
+ const unsigned char *prefix, unsigned int prefix_len,
+ struct int_node *node, struct int_node *parent, int n)
+{
+ void *buf;
+ struct tree_desc desc;
+
+ buf = fill_tree_descriptor(&desc, sha1);
+ if (!buf)
+ die("Could not read notes subtree at %s", sha1_to_hex(sha1));
+ /*
+ * After fill_tree_descriptor(), we can peek at the first tree entry
+ * in desc.entry.
+ */
+ switch (desc.entry.path[0]) {
+ case 'd':
+ if (strlen(desc.entry.path) != 3)
+ break;
+ /* fall-through */
+ case 'm':
+ case 'y':
+ /* path cannot be a SHA1 fragment */
+ load_date_subtree(&desc, (const char *) prefix, prefix_len,
+ node, parent);
+ free(buf);
+ return;
+ }
+ if (n < 0) {
+ /* Arriving from a date-based subtree; reset prefix */
+ n = 0;
+ prefix = NULL;
+ prefix_len = 0;
+ }
+ load_sha1_subtree(&desc, prefix, prefix_len, node, n);
free(buf);
}
@@ -265,23 +531,81 @@ static void initialize_notes(const char *notes_ref_name)
{
unsigned char sha1[20], commit_sha1[20];
unsigned mode;
- struct leaf_node root_tree;
if (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||
get_tree_entry(commit_sha1, "", sha1, &mode))
return;
- hashclr(root_tree.key_sha1);
- hashcpy(root_tree.val_sha1, sha1);
- load_subtree(&root_tree, &root_node, 0);
+ load_subtree(sha1, NULL, 0, &root_node, NULL, 0);
+ cur_node = &root_node;
}
-static unsigned char *lookup_notes(const unsigned char *commit_sha1)
+static unsigned char *lookup_notes(const struct commit *commit)
{
- struct leaf_node *found = note_tree_find(&root_node, 0, commit_sha1);
- if (found)
- return found->val_sha1;
- return NULL;
+ struct int_node *node = cur_node, *seen_node = cur_node;
+ struct leaf_node *found;
+ const char *short_date;
+
+ if (!node)
+ return NULL;
+
+ /* Convert commit->date to YYYY-MM-DD format */
+ short_date = show_date(commit->date, 0, DATE_SHORT);
+
+ while (node->magic == (void *) ~0) { /* date-based node */
+ int cmp = SUBTREE_DATE_PREFIXCMP(short_date, node->period);
+ if (cmp == 0) {
+ /* Search inside child node */
+ if (!node->child) {
+ /* Must unpack child node first */
+ node->child = (struct int_node *)
+ xcalloc(sizeof(struct int_node), 1);
+ load_subtree(node->tree_sha1,
+ (const unsigned char *) node->period,
+ strlen(node->period), node->child,
+ node, -1);
+ }
+ seen_node = node;
+ node = node->child;
+ }
+ else if (cmp > 0) {
+ /* Search in past node */
+ if (node->prev)
+ node = node->prev;
+ else
+ node = node->parent;
+ }
+ else {
+ /* Search in future node */
+ if (!node->parent) {
+ /* Restart from root_node */
+ seen_node = node;
+ node = &root_node;
+ }
+ else
+ node = node->parent;
+ }
+ if (!node || node == seen_node) {
+ /* We've been here before, give up search */
+ return NULL;
+ }
+ }
+ while (cur_node &&
+ SUBTREE_DATE_PREFIXCMP(cur_node->period, seen_node->period) < 0)
+ {
+ /*
+ * We're about to move cur_node backwards in history. We are
+ * unlikely to need this cur_node in the future, so free() it.
+ */
+ note_tree_free(cur_node->child);
+ cur_node->child = NULL;
+ cur_node = cur_node->parent;
+ }
+ cur_node = seen_node;
+
+ /* Drill down further with SHA1-based lookup */
+ found = note_tree_find(node, 0, commit->object.sha1);
+ return found ? found->val_sha1 : NULL;
}
void get_commit_notes(const struct commit *commit, struct strbuf *sb,
@@ -303,7 +627,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
initialized = 1;
}
- sha1 = lookup_notes(commit->object.sha1);
+ sha1 = lookup_notes(commit);
if (!sha1)
return;
@@ -342,6 +666,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
void free_commit_notes()
{
+ cur_node = NULL;
note_tree_free(&root_node);
memset(&root_node, 0, sizeof(struct int_node));
initialized = 0;
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [PATCHv5 14/14] Add test cases for date-based fanouts
From: Johan Herland @ 2009-09-08 2:27 UTC (permalink / raw)
To: gitster
Cc: git, johan, Johannes.Schindelin, trast, tavestbo, git, chriscool,
spearce
In-Reply-To: <1252376822-6138-1-git-send-email-johan@herland.net>
Signed-off-by: Johan Herland <johan@herland.net>
---
t/t3303-notes-subtrees.sh | 64 +++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 64 insertions(+), 0 deletions(-)
diff --git a/t/t3303-notes-subtrees.sh b/t/t3303-notes-subtrees.sh
index d24203e..d3cbf6d 100755
--- a/t/t3303-notes-subtrees.sh
+++ b/t/t3303-notes-subtrees.sh
@@ -134,4 +134,68 @@ test_expect_success 'verify notes in 4/36-fanout overriding 2/38-fanout' 'verify
test_expect_success 'test notes in 2/38-fanout overriding 2/2/36-fanout' 'test_preferred "s|^..|&/|" "s|^\(..\)\(..\)|\1/\2/|"'
test_expect_success 'verify notes in 2/38-fanout overriding 2/2/36-fanout' 'verify_notes'
+test_date_based () {
+ (
+ start_note_commit &&
+ nr=$number_of_commits &&
+ git log --format="%H %ct" refs/heads/master |
+ while read sha1 date_t; do
+ date=$(date -u -d "@$date_t" +"$1")
+ note_path="$date/$(echo "$sha1" | sed "$2")"
+ cat <<INPUT_END &&
+M 100644 inline $note_path
+data <<EOF
+note for commit #$nr
+EOF
+
+INPUT_END
+
+ nr=$(($nr-1))
+ done
+ ) |
+ git fast-import --quiet
+}
+
+test_expect_success 'test notes in y/40-fanout' 'test_date_based "y%Y" ""'
+test_expect_success 'verify notes in y/40-fanout' 'verify_notes'
+
+test_expect_success 'test notes in y/2/38-fanout' 'test_date_based "y%Y" "s|^..|&/|"'
+test_expect_success 'verify notes in y/2/38-fanout' 'verify_notes'
+
+test_expect_success 'test notes in ym/40-fanout' 'test_date_based "y%Ym%m" ""'
+test_expect_success 'verify notes in ym/40-fanout' 'verify_notes'
+
+test_expect_success 'test notes in ym/2/38-fanout' 'test_date_based "y%Ym%m" "s|^..|&/|"'
+test_expect_success 'verify notes in ym/2/38-fanout' 'verify_notes'
+
+test_expect_success 'test notes in ymd/40-fanout' 'test_date_based "y%Ym%md%d" ""'
+test_expect_success 'verify notes in ymd/40-fanout' 'verify_notes'
+
+test_expect_success 'test notes in ymd/2/38-fanout' 'test_date_based "y%Ym%md%d" "s|^..|&/|"'
+test_expect_success 'verify notes in ymd/2/38-fanout' 'verify_notes'
+
+test_expect_success 'test notes in y/m/40-fanout' 'test_date_based "y%Y/m%m" ""'
+test_expect_success 'verify notes in y/m/40-fanout' 'verify_notes'
+
+test_expect_success 'test notes in y/m/2/38-fanout' 'test_date_based "y%Y/m%m" "s|^..|&/|"'
+test_expect_success 'verify notes in y/m/2/38-fanout' 'verify_notes'
+
+test_expect_success 'test notes in y/md/40-fanout' 'test_date_based "y%Y/m%md%d" ""'
+test_expect_success 'verify notes in y/md/40-fanout' 'verify_notes'
+
+test_expect_success 'test notes in y/md/2/38-fanout' 'test_date_based "y%Y/m%md%d" "s|^..|&/|"'
+test_expect_success 'verify notes in y/md/2/38-fanout' 'verify_notes'
+
+test_expect_success 'test notes in ym/d/40-fanout' 'test_date_based "y%Ym%m/d%d" ""'
+test_expect_success 'verify notes in ym/d/40-fanout' 'verify_notes'
+
+test_expect_success 'test notes in ym/d/2/38-fanout' 'test_date_based "y%Ym%m/d%d" "s|^..|&/|"'
+test_expect_success 'verify notes in ym/d/2/38-fanout' 'verify_notes'
+
+test_expect_success 'test notes in y/m/d/40-fanout' 'test_date_based "y%Y/m%m/d%d" ""'
+test_expect_success 'verify notes in y/m/d/40-fanout' 'verify_notes'
+
+test_expect_success 'test notes in y/m/d/2/38-fanout' 'test_date_based "y%Y/m%m/d%d" "s|^..|&/|"'
+test_expect_success 'verify notes in y/m/d/2/38-fanout' 'verify_notes'
+
test_done
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [PATCHv5 12/14] Selftests verifying semantics when loading notes trees with various fanouts
From: Johan Herland @ 2009-09-08 2:27 UTC (permalink / raw)
To: gitster
Cc: git, johan, Johannes.Schindelin, trast, tavestbo, git, chriscool,
spearce
In-Reply-To: <1252376822-6138-1-git-send-email-johan@herland.net>
Add selftests verifying:
- that we are able to parse notes trees with various fanout schemes
- that notes trees with conflicting fanout schemes are parsed as expected
Signed-off-by: Johan Herland <johan@herland.net>
---
t/t3303-notes-subtrees.sh | 137 +++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 137 insertions(+), 0 deletions(-)
create mode 100755 t/t3303-notes-subtrees.sh
diff --git a/t/t3303-notes-subtrees.sh b/t/t3303-notes-subtrees.sh
new file mode 100755
index 0000000..d24203e
--- /dev/null
+++ b/t/t3303-notes-subtrees.sh
@@ -0,0 +1,137 @@
+#!/bin/sh
+
+test_description='Test commit notes organized in subtrees'
+
+. ./test-lib.sh
+
+number_of_commits=100
+
+start_note_commit () {
+ test_tick &&
+ cat <<INPUT_END
+commit refs/notes/commits
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes
+COMMIT
+
+from refs/notes/commits^0
+deleteall
+INPUT_END
+
+}
+
+verify_notes () {
+ git log | grep "^ " > output &&
+ i=$number_of_commits &&
+ while [ $i -gt 0 ]; do
+ echo " commit #$i" &&
+ echo " note for commit #$i" &&
+ i=$(($i-1));
+ done > expect &&
+ test_cmp expect output
+}
+
+test_expect_success "setup: create $number_of_commits commits" '
+
+ (
+ nr=0 &&
+ while [ $nr -lt $number_of_commits ]; do
+ nr=$(($nr+1)) &&
+ test_tick &&
+ cat <<INPUT_END
+commit refs/heads/master
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+commit #$nr
+COMMIT
+
+M 644 inline file
+data <<EOF
+file in commit #$nr
+EOF
+
+INPUT_END
+
+ done &&
+ test_tick &&
+ cat <<INPUT_END
+commit refs/notes/commits
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+no notes
+COMMIT
+
+deleteall
+
+INPUT_END
+
+ ) |
+ git fast-import --quiet &&
+ git config core.notesRef refs/notes/commits
+'
+
+test_sha1_based () {
+ (
+ start_note_commit &&
+ nr=$number_of_commits &&
+ git rev-list refs/heads/master |
+ while read sha1; do
+ note_path=$(echo "$sha1" | sed "$1")
+ cat <<INPUT_END &&
+M 100644 inline $note_path
+data <<EOF
+note for commit #$nr
+EOF
+
+INPUT_END
+
+ nr=$(($nr-1))
+ done
+ ) |
+ git fast-import --quiet
+}
+
+test_expect_success 'test notes in 2/38-fanout' 'test_sha1_based "s|^..|&/|"'
+test_expect_success 'verify notes in 2/38-fanout' 'verify_notes'
+
+test_expect_success 'test notes in 4/36-fanout' 'test_sha1_based "s|^....|&/|"'
+test_expect_success 'verify notes in 4/36-fanout' 'verify_notes'
+
+test_expect_success 'test notes in 2/2/36-fanout' 'test_sha1_based "s|^\(..\)\(..\)|\1/\2/|"'
+test_expect_success 'verify notes in 2/2/36-fanout' 'verify_notes'
+
+test_preferred () {
+ (
+ start_note_commit &&
+ nr=$number_of_commits &&
+ git rev-list refs/heads/master |
+ while read sha1; do
+ preferred_note_path=$(echo "$sha1" | sed "$1")
+ ignored_note_path=$(echo "$sha1" | sed "$2")
+ cat <<INPUT_END &&
+M 100644 inline $ignored_note_path
+data <<EOF
+IGNORED note for commit #$nr
+EOF
+
+M 100644 inline $preferred_note_path
+data <<EOF
+note for commit #$nr
+EOF
+
+INPUT_END
+
+ nr=$(($nr-1))
+ done
+ ) |
+ git fast-import --quiet
+}
+
+test_expect_success 'test notes in 4/36-fanout overriding 2/38-fanout' 'test_preferred "s|^....|&/|" "s|^..|&/|"'
+test_expect_success 'verify notes in 4/36-fanout overriding 2/38-fanout' 'verify_notes'
+
+test_expect_success 'test notes in 2/38-fanout overriding 2/2/36-fanout' 'test_preferred "s|^..|&/|" "s|^\(..\)\(..\)|\1/\2/|"'
+test_expect_success 'verify notes in 2/38-fanout overriding 2/2/36-fanout' 'verify_notes'
+
+test_done
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [PATCHv5 11/14] Teach the notes lookup code to parse notes trees with various fanout schemes
From: Johan Herland @ 2009-09-08 2:26 UTC (permalink / raw)
To: gitster
Cc: git, johan, Johannes.Schindelin, trast, tavestbo, git, chriscool,
spearce
In-Reply-To: <1252376822-6138-1-git-send-email-johan@herland.net>
The semantics used when parsing notes trees (with regards to fanout subtrees)
follow Dscho's proposal fairly closely:
- No concatenation/merging of notes is performed. If there are several notes
objects referencing a given commit, only one of those objects are used.
- If a notes object for a given commit is present in the "root" notes tree,
no subtrees are consulted; the object in the root tree is used directly.
- If there are more than one subtree that prefix-matches the given commit,
only the subtree with the longest matching prefix is consulted. This
means that if the given commit is e.g. "deadbeef", and the notes tree have
subtrees "de" and "dead", then the following paths in the notes tree are
searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched.
- Fanout directories (subtrees) must references a whole number of bytes
from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are
acceptable; "d" and "dea" are not.
- Multiple levels of fanout are allowed. All the above rules apply
recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc.
This patch changes the in-memory datastructure for holding parsed notes:
Instead of holding all note (and subtree) entries in a hash table, a
simple 16-tree structure is used instead. The tree structure consists of
16-arrays as internal nodes, and note/subtree entries as leaf nodes. The
tree is traversed by indexing subsequent nibbles of the search key until
a leaf node is encountered. If a subtree entry is encountered while
searching for a note, the subtree is unpacked into the 16-tree structure,
and the search continues into that subtree.
The new algorithm performs significantly better in the cases where only
a fraction of the notes need to be looked up (this is assumed to be the
common case for notes lookup). The new code even performs marginally
better in the worst case (where _all_ the notes are looked up).
In addition to this, comes the massive performance win associated with
organizing the notes tree according to some fanout scheme. Even a simple
2/38 fanout scheme is dramatically quicker to traverse (going from tens of
seconds to sub-second runtimes).
As for memory usage, the new code is marginally better than the old code in
the worst case, but in the case of looking up only some notes from a notes
tree with proper fanout, the new code uses only a small fraction of the
memory needed to hold the entire notes tree.
However, there is one casualty of this patch. The old notes lookup code was
able to parse notes that were associated with non-SHA1s (e.g. refs). The new
code requires the referenced object to be named by a SHA1 sum. Still, this
is not considered a major setback, since the notes infrastructure was not
originally intended to annotate objects outside the Git object database.
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 317 +++++++++++++++++++++++++++++++++++++++++++++++++--------------
1 files changed, 248 insertions(+), 69 deletions(-)
diff --git a/notes.c b/notes.c
index 008c3d4..6926aa6 100644
--- a/notes.c
+++ b/notes.c
@@ -6,103 +6,282 @@
#include "strbuf.h"
#include "tree-walk.h"
-struct entry {
- unsigned char commit_sha1[20];
- unsigned char notes_sha1[20];
+/*
+ * Use a non-balancing simple 16-tree structure with struct int_node as
+ * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
+ * 16-array of pointers to its children.
+ * The bottom 2 bits of each pointer is used to identify the pointer type
+ * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
+ * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
+ * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
+ * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
+ *
+ * The root node is a statically allocated struct int_node.
+ */
+struct int_node {
+ void *a[16];
};
-struct hash_map {
- struct entry *entries;
- off_t count, size;
+/*
+ * Leaf nodes come in two variants, note entries and subtree entries,
+ * distinguished by the LSb of the leaf node pointer (see above).
+ * As a note entry, the key is the SHA1 of the referenced commit, and the
+ * value is the SHA1 of the note object.
+ * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
+ * referenced commit, using the last byte of the key to store the length of
+ * the prefix. The value is the SHA1 of the tree object containing the notes
+ * subtree.
+ */
+struct leaf_node {
+ unsigned char key_sha1[20];
+ unsigned char val_sha1[20];
};
-static int initialized;
-static struct hash_map hash_map;
+#define PTR_TYPE_NULL 0
+#define PTR_TYPE_INTERNAL 1
+#define PTR_TYPE_NOTE 2
+#define PTR_TYPE_SUBTREE 3
-static int hash_index(struct hash_map *map, const unsigned char *sha1)
-{
- int i = ((*(unsigned int *)sha1) % map->size);
+#define GET_PTR_TYPE(ptr) ((uintptr_t) (ptr) & 3)
+#define CLR_PTR_TYPE(ptr) ((void *) ((uintptr_t) (ptr) & ~3))
+#define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
- for (;;) {
- unsigned char *current = map->entries[i].commit_sha1;
+#define GET_NIBBLE(n, sha1) (((sha1[n >> 1]) >> ((n & 0x01) << 2)) & 0x0f)
- if (!hashcmp(sha1, current))
- return i;
+#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
+ (memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
- if (is_null_sha1(current))
- return -1 - i;
+static struct int_node root_node;
- if (++i == map->size)
- i = 0;
+static int initialized;
+
+static void load_subtree(struct leaf_node *subtree, struct int_node *node,
+ unsigned int n);
+
+/*
+ * To find a leaf_node:
+ * 1. Start at the root node, with n = 0
+ * 2. Use the nth nibble of the key as an index into a:
+ * - If a[n] is an int_node, recurse into that node and increment n
+ * - If a leaf_node with matching key, return leaf_node (assert note entry)
+ * - If a matching subtree entry, unpack that subtree entry (and remove it);
+ * restart search at the current level.
+ * - Otherwise, we end up at a NULL pointer, or a non-matching leaf_node.
+ * Backtrack out of the recursion, one level at a time and check a[0]:
+ * - If a[0] at the current level is a matching subtree entry, unpack that
+ * subtree entry (and remove it); restart search at the current level.
+ */
+static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
+ const unsigned char *key_sha1)
+{
+ struct leaf_node *l;
+ unsigned char i = GET_NIBBLE(n, key_sha1);
+ void *p = tree->a[i];
+
+ switch(GET_PTR_TYPE(p)) {
+ case PTR_TYPE_INTERNAL:
+ l = note_tree_find(CLR_PTR_TYPE(p), n + 1, key_sha1);
+ if (l)
+ return l;
+ break;
+ case PTR_TYPE_NOTE:
+ l = (struct leaf_node *) CLR_PTR_TYPE(p);
+ if (!hashcmp(key_sha1, l->key_sha1))
+ return l; /* return note object matching given key */
+ break;
+ case PTR_TYPE_SUBTREE:
+ l = (struct leaf_node *) CLR_PTR_TYPE(p);
+ if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
+ /* unpack tree and resume search */
+ tree->a[i] = NULL;
+ load_subtree(l, tree, n);
+ free(l);
+ return note_tree_find(tree, n, key_sha1);
+ }
+ break;
+ case PTR_TYPE_NULL:
+ default:
+ assert(!p);
+ break;
}
+
+ /*
+ * Did not find key at this (or any lower) level.
+ * Check if there's a matching subtree entry in tree->a[0].
+ * If so, unpack tree and resume search.
+ */
+ p = tree->a[0];
+ if (GET_PTR_TYPE(p) != PTR_TYPE_SUBTREE)
+ return NULL;
+ l = (struct leaf_node *) CLR_PTR_TYPE(p);
+ if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
+ /* unpack tree and resume search */
+ tree->a[0] = NULL;
+ load_subtree(l, tree, n);
+ free(l);
+ return note_tree_find(tree, n, key_sha1);
+ }
+ return NULL;
}
-static void add_entry(const unsigned char *commit_sha1,
- const unsigned char *notes_sha1)
+/*
+ * To insert a leaf_node:
+ * 1. Start at the root node, with n = 0
+ * 2. Use the nth nibble of the key as an index into a:
+ * - If a[n] is NULL, store the tweaked pointer directly into a[n]
+ * - If a[n] is an int_node, recurse into that node and increment n
+ * - If a[n] is a leaf_node:
+ * 1. Check if they're equal, and handle that (abort? overwrite?)
+ * 2. Create a new int_node, and store both leaf_nodes there
+ * 3. Store the new int_node into a[n].
+ */
+static int note_tree_insert(struct int_node *tree, unsigned char n,
+ const struct leaf_node *entry, unsigned char type)
{
- int index;
-
- if (hash_map.count + 1 > hash_map.size >> 1) {
- int i, old_size = hash_map.size;
- struct entry *old = hash_map.entries;
-
- hash_map.size = old_size ? old_size << 1 : 64;
- hash_map.entries = (struct entry *)
- xcalloc(sizeof(struct entry), hash_map.size);
-
- for (i = 0; i < old_size; i++)
- if (!is_null_sha1(old[i].commit_sha1)) {
- index = -1 - hash_index(&hash_map,
- old[i].commit_sha1);
- memcpy(hash_map.entries + index, old + i,
- sizeof(struct entry));
- }
- free(old);
+ struct int_node *new_node;
+ const struct leaf_node *l;
+ int ret;
+ unsigned char i = GET_NIBBLE(n, entry->key_sha1);
+ void *p = tree->a[i];
+ assert(GET_PTR_TYPE(entry) == PTR_TYPE_NULL);
+ switch(GET_PTR_TYPE(p)) {
+ case PTR_TYPE_NULL:
+ assert(!p);
+ tree->a[i] = SET_PTR_TYPE(entry, type);
+ return 0;
+ case PTR_TYPE_INTERNAL:
+ return note_tree_insert(CLR_PTR_TYPE(p), n + 1, entry, type);
+ default:
+ assert(GET_PTR_TYPE(p) == PTR_TYPE_NOTE ||
+ GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE);
+ l = (const struct leaf_node *) CLR_PTR_TYPE(p);
+ if (!hashcmp(entry->key_sha1, l->key_sha1))
+ return -1; /* abort insert on matching key */
+ new_node = (struct int_node *)
+ xcalloc(sizeof(struct int_node), 1);
+ ret = note_tree_insert(new_node, n + 1,
+ CLR_PTR_TYPE(p), GET_PTR_TYPE(p));
+ if (ret) {
+ free(new_node);
+ return -1;
+ }
+ tree->a[i] = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
+ return note_tree_insert(new_node, n + 1, entry, type);
}
+}
- index = hash_index(&hash_map, commit_sha1);
- if (index < 0) {
- index = -1 - index;
- hash_map.count++;
+/* Free the entire notes data contained in the given tree */
+static void note_tree_free(struct int_node *tree)
+{
+ unsigned int i;
+ for (i = 0; i < 16; i++) {
+ void *p = tree->a[i];
+ switch(GET_PTR_TYPE(p)) {
+ case PTR_TYPE_INTERNAL:
+ note_tree_free(CLR_PTR_TYPE(p));
+ /* fall through */
+ case PTR_TYPE_NOTE:
+ case PTR_TYPE_SUBTREE:
+ free(CLR_PTR_TYPE(p));
+ }
}
+}
- hashcpy(hash_map.entries[index].commit_sha1, commit_sha1);
- hashcpy(hash_map.entries[index].notes_sha1, notes_sha1);
+/*
+ * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.
+ * - hex - Partial SHA1 segment in ASCII hex format
+ * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40
+ * - sha1 - Partial SHA1 value is written here
+ * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20
+ * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format).
+ * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).
+ * Pads sha1 with NULs up to sha1_len (not included in returned length).
+ */
+static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,
+ unsigned char *sha1, unsigned int sha1_len)
+{
+ unsigned int i, len = hex_len >> 1;
+ if (hex_len % 2 != 0 || len > sha1_len)
+ return -1;
+ for (i = 0; i < len; i++) {
+ unsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);
+ if (val & ~0xff)
+ return -1;
+ *sha1++ = val;
+ hex += 2;
+ }
+ for (; i < sha1_len; i++)
+ *sha1++ = 0;
+ return len;
}
-static void initialize_hash_map(const char *notes_ref_name)
+static void load_subtree(struct leaf_node *subtree, struct int_node *node,
+ unsigned int n)
{
- unsigned char sha1[20], commit_sha1[20];
- unsigned mode;
+ unsigned char commit_sha1[20];
+ unsigned int prefix_len;
+ int status;
+ void *buf;
struct tree_desc desc;
struct name_entry entry;
- void *buf;
+
+ buf = fill_tree_descriptor(&desc, subtree->val_sha1);
+ if (!buf)
+ die("Could not read %s for notes-index",
+ sha1_to_hex(subtree->val_sha1));
+
+ prefix_len = subtree->key_sha1[19];
+ assert(prefix_len * 2 >= n);
+ memcpy(commit_sha1, subtree->key_sha1, prefix_len);
+ while (tree_entry(&desc, &entry)) {
+ int len = get_sha1_hex_segment(entry.path, strlen(entry.path),
+ commit_sha1 + prefix_len, 20 - prefix_len);
+ if (len < 0)
+ continue; /* entry.path is not a SHA1 sum. Skip */
+ len += prefix_len;
+
+ /*
+ * If commit SHA1 is complete (len == 20), assume note object
+ * If commit SHA1 is incomplete (len < 20), assume note subtree
+ */
+ if (len <= 20) {
+ unsigned char type = PTR_TYPE_NOTE;
+ struct leaf_node *l = (struct leaf_node *)
+ xcalloc(sizeof(struct leaf_node), 1);
+ hashcpy(l->key_sha1, commit_sha1);
+ hashcpy(l->val_sha1, entry.sha1);
+ if (len < 20) {
+ l->key_sha1[19] = (unsigned char) len;
+ type = PTR_TYPE_SUBTREE;
+ }
+ status = note_tree_insert(node, n, l, type);
+ assert(!status);
+ }
+ }
+ free(buf);
+}
+
+static void initialize_notes(const char *notes_ref_name)
+{
+ unsigned char sha1[20], commit_sha1[20];
+ unsigned mode;
+ struct leaf_node root_tree;
if (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||
get_tree_entry(commit_sha1, "", sha1, &mode))
return;
- buf = fill_tree_descriptor(&desc, sha1);
- if (!buf)
- die("Could not read %s for notes-index", sha1_to_hex(sha1));
-
- while (tree_entry(&desc, &entry))
- if (!get_sha1(entry.path, commit_sha1))
- add_entry(commit_sha1, entry.sha1);
- free(buf);
+ hashclr(root_tree.key_sha1);
+ hashcpy(root_tree.val_sha1, sha1);
+ load_subtree(&root_tree, &root_node, 0);
}
static unsigned char *lookup_notes(const unsigned char *commit_sha1)
{
- int index;
-
- if (!hash_map.size)
- return NULL;
-
- index = hash_index(&hash_map, commit_sha1);
- if (index < 0)
- return NULL;
- return hash_map.entries[index].notes_sha1;
+ struct leaf_node *found = note_tree_find(&root_node, 0, commit_sha1);
+ if (found)
+ return found->val_sha1;
+ return NULL;
}
void get_commit_notes(const struct commit *commit, struct strbuf *sb,
@@ -120,7 +299,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
notes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);
else if (!notes_ref_name)
notes_ref_name = GIT_NOTES_DEFAULT_REF;
- initialize_hash_map(notes_ref_name);
+ initialize_notes(notes_ref_name);
initialized = 1;
}
@@ -163,7 +342,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
void free_commit_notes()
{
- free(hash_map.entries);
- memset(&hash_map, 0, sizeof(struct hash_map));
+ note_tree_free(&root_node);
+ memset(&root_node, 0, sizeof(struct int_node));
initialized = 0;
}
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [PATCHv5 03/14] Speed up git notes lookup
From: Johan Herland @ 2009-09-08 2:26 UTC (permalink / raw)
To: gitster
Cc: git, johan, Johannes.Schindelin, trast, tavestbo, git, chriscool,
spearce, Johannes Schindelin
In-Reply-To: <1252376822-6138-1-git-send-email-johan@herland.net>
From: Johannes Schindelin <Johannes.Schindelin@gmx.de>
To avoid looking up each and every commit in the notes ref's tree
object, which is very expensive, speed things up by slurping the tree
object's contents into a hash_map.
The idea for the hashmap singleton is from David Reiss, initial
benchmarking by Jeff King.
Note: the implementation allows for arbitrary entries in the notes
tree object, ignoring those that do not reference a valid object. This
allows you to annotate arbitrary branches, or objects.
This patch has been improved by the following contributions:
- Junio C Hamano: fixed an obvious error in initialize_hash_map()
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
notes.c | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
1 files changed, 102 insertions(+), 10 deletions(-)
diff --git a/notes.c b/notes.c
index 401966d..9172154 100644
--- a/notes.c
+++ b/notes.c
@@ -4,15 +4,112 @@
#include "refs.h"
#include "utf8.h"
#include "strbuf.h"
+#include "tree-walk.h"
+
+struct entry {
+ unsigned char commit_sha1[20];
+ unsigned char notes_sha1[20];
+};
+
+struct hash_map {
+ struct entry *entries;
+ off_t count, size;
+};
static int initialized;
+static struct hash_map hash_map;
+
+static int hash_index(struct hash_map *map, const unsigned char *sha1)
+{
+ int i = ((*(unsigned int *)sha1) % map->size);
+
+ for (;;) {
+ unsigned char *current = map->entries[i].commit_sha1;
+
+ if (!hashcmp(sha1, current))
+ return i;
+
+ if (is_null_sha1(current))
+ return -1 - i;
+
+ if (++i == map->size)
+ i = 0;
+ }
+}
+
+static void add_entry(const unsigned char *commit_sha1,
+ const unsigned char *notes_sha1)
+{
+ int index;
+
+ if (hash_map.count + 1 > hash_map.size >> 1) {
+ int i, old_size = hash_map.size;
+ struct entry *old = hash_map.entries;
+
+ hash_map.size = old_size ? old_size << 1 : 64;
+ hash_map.entries = (struct entry *)
+ xcalloc(sizeof(struct entry), hash_map.size);
+
+ for (i = 0; i < old_size; i++)
+ if (!is_null_sha1(old[i].commit_sha1)) {
+ index = -1 - hash_index(&hash_map,
+ old[i].commit_sha1);
+ memcpy(hash_map.entries + index, old + i,
+ sizeof(struct entry));
+ }
+ free(old);
+ }
+
+ index = hash_index(&hash_map, commit_sha1);
+ if (index < 0) {
+ index = -1 - index;
+ hash_map.count++;
+ }
+
+ hashcpy(hash_map.entries[index].commit_sha1, commit_sha1);
+ hashcpy(hash_map.entries[index].notes_sha1, notes_sha1);
+}
+
+static void initialize_hash_map(const char *notes_ref_name)
+{
+ unsigned char sha1[20], commit_sha1[20];
+ unsigned mode;
+ struct tree_desc desc;
+ struct name_entry entry;
+ void *buf;
+
+ if (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||
+ get_tree_entry(commit_sha1, "", sha1, &mode))
+ return;
+
+ buf = fill_tree_descriptor(&desc, sha1);
+ if (!buf)
+ die("Could not read %s for notes-index", sha1_to_hex(sha1));
+
+ while (tree_entry(&desc, &entry))
+ if (!get_sha1(entry.path, commit_sha1))
+ add_entry(commit_sha1, entry.sha1);
+ free(buf);
+}
+
+static unsigned char *lookup_notes(const unsigned char *commit_sha1)
+{
+ int index;
+
+ if (!hash_map.size)
+ return NULL;
+
+ index = hash_index(&hash_map, commit_sha1);
+ if (index < 0)
+ return NULL;
+ return hash_map.entries[index].notes_sha1;
+}
void get_commit_notes(const struct commit *commit, struct strbuf *sb,
const char *output_encoding)
{
static const char utf8[] = "utf-8";
- struct strbuf name = STRBUF_INIT;
- unsigned char sha1[20];
+ unsigned char *sha1;
char *msg, *msg_p;
unsigned long linelen, msglen;
enum object_type type;
@@ -23,17 +120,12 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
notes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);
else if (!notes_ref_name)
notes_ref_name = GIT_NOTES_DEFAULT_REF;
- if (notes_ref_name && read_ref(notes_ref_name, sha1))
- notes_ref_name = NULL;
+ initialize_hash_map(notes_ref_name);
initialized = 1;
}
- if (!notes_ref_name)
- return;
-
- strbuf_addf(&name, "%s:%s", notes_ref_name,
- sha1_to_hex(commit->object.sha1));
- if (get_sha1(name.buf, sha1))
+ sha1 = lookup_notes(commit->object.sha1);
+ if (!sha1)
return;
if (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen ||
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox