* Re: git log -S not finding all commits?
From: Matthieu Moy @ 2009-10-09 14:26 UTC (permalink / raw)
To: Randal L. Schwartz; +Cc: Daniel, Andreas Ericsson, git
In-Reply-To: <864oq8r795.fsf@blue.stonehenge.com>
merlyn@stonehenge.com (Randal L. Schwartz) writes:
> .. | perl -ln0e 'print if /this/'
Ah, good. I would have done this with 3 lines of code, glad to see a
solution with a single more character ;-).
Just updated the FAQ.
--
Matthieu Moy
http://www-verimag.imag.fr/~moy/
^ permalink raw reply
* Re: [PATCH 1/2] completion: fix completion of git <TAB><TAB>
From: Shawn O. Pearce @ 2009-10-09 14:26 UTC (permalink / raw)
To: Stephen Boyd; +Cc: Junio C Hamano, git, Johannes Sixt
In-Reply-To: <1255069304-8953-1-git-send-email-bebarino@gmail.com>
Stephen Boyd <bebarino@gmail.com> wrote:
> After commit 511a3fc (wrap git's main usage string., 2009-09-12), the
> bash completion for git commands includes COMMAND and [ARGS] when it
> shouldn't. Fix this by grepping more strictly for a line with git
> commands. It's doubtful whether git will ever have commands starting
> with anything besides numbers and letters so this should be fine. At
> least by being stricter we'll know when we break the completion earlier.
>
> Signed-off-by: Stephen Boyd <bebarino@gmail.com>
Acked-by: Shawn O. Pearce <spearce@spearce.org>
--
Shawn.
^ permalink raw reply
* Re: [RFC/PATCHv7 22/22] fast-import: Proper notes tree manipulation using the notes API
From: Shawn O. Pearce @ 2009-10-09 14:25 UTC (permalink / raw)
To: Johan Herland
Cc: git, gitster, Johannes.Schindelin, trast, tavestbo, git,
chriscool, sam
In-Reply-To: <1255083738-23263-24-git-send-email-johan@herland.net>
Johan Herland <johan@herland.net> wrote:
> This patch teaches 'git fast-import' to use the notes API to organize
> the manipulation of note objects through a fast-import stream. Note
> objects are added to the notes tree through the 'N' command, and when
> we're about to store the tree object for the current commit, we walk
> through the notes tree and insert all the notes into the stored tree.
Some high level comments about this patch:
- You don't destroy the struct notes_tree during unload_one_branch()
which means notes trees stay in memory even if the branch table
is overflowing. I think you should discard the notes tree when
a branch unloads, and recreate it when the branch loads.
- Destroying and adding back all notes is OK with ~20k notes, but
doing that with ~150k-~800k notes is going to slow down a lot,
losing the "fast" part.
--
Shawn.
^ permalink raw reply
* Re: git log -S not finding all commits?
From: Randal L. Schwartz @ 2009-10-09 14:07 UTC (permalink / raw)
To: Matthieu Moy; +Cc: Daniel, Andreas Ericsson, git
In-Reply-To: <vpq1vldx7xx.fsf@bauges.imag.fr>
>>>>> "Matthieu" == Matthieu Moy <Matthieu.Moy@grenoble-inp.fr> writes:
Matthieu> merlyn@stonehenge.com (Randal L. Schwartz) writes:
>>>>>>> "Matthieu" == Matthieu Moy <Matthieu.Moy@grenoble-inp.fr> writes:
>>
Matthieu> Matthieu Moy <Matthieu.Moy@grenoble-inp.fr> writes:
>>>> git log -p --format="%s\n%x00" | perl -0 -ne 'print if(/whatever-you-search/);'
>>
>> That "if" is noisier than it needs to be:
>>
>> perl -0 -ne 'print if /this/'
Matthieu> Also, this seems to actually print the \0 character. Perhaps a perl
Matthieu> guru can give a simple solution to replace the \0 by a \n?
Just a matter of one more switch. Sorry for forgetting it earlier.
.. | perl -ln0e 'print if /this/'
print "Just another Perl hacker,"; # the original
--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<merlyn@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion
^ permalink raw reply
* Re: [PATCH] import-tars: Add missing closing bracket
From: Peter Krefting @ 2009-10-09 12:52 UTC (permalink / raw)
To: Ingmar Vanhassel; +Cc: Git Mailing List, Junio C Hamano
In-Reply-To: <1255090111-32612-1-git-send-email-ingmar@exherbo.org>
Ingmar Vanhassel:
> This fixes an obvious syntax error that snuck in commit 7e787953:
Now, that is embarrassing... :-/ Sorry.
> Signed-off-by: Ingmar Vanhassel <ingmar@exherbo.org>
Tested-by: Peter Krefting <peter@softwolves.pp.se>
--
\\// Peter - http://www.softwolves.pp.se/
^ permalink raw reply
* Re: Git archive and trailing "/" in prefix
From: René Scharfe @ 2009-10-09 12:49 UTC (permalink / raw)
To: Sergio Callegari; +Cc: Junio C Hamano, git
In-Reply-To: <4ACE62B1.8070801@gmail.com>
Sergio Callegari schrieb:
> I guess the bug in using --prefix on a worktree with subdirs without
> specifying a path is not specific to git archive, then.
The bug should be limited to archive; after my patch all calls to
read_tree_recursive() specify an empty base parameter (except in tree.c,
where the function itself lives).
René
^ permalink raw reply
* Re: git log -S not finding all commits?
From: Scott Wiersdorf @ 2009-10-09 12:41 UTC (permalink / raw)
To: git
In-Reply-To: <vpq1vldx7xx.fsf@bauges.imag.fr>
On Fri, Oct 09, 2009 at 10:55:38AM +0200, Matthieu Moy wrote:
> >
> > perl -0 -ne 'print if /this/'
>
> Also, this seems to actually print the \0 character. Perhaps a perl
> guru can give a simple solution to replace the \0 by a \n?
If you want some indication that there is a null character:
perl -0 -ne '/this/ or next; s/\0/{NULL}/g; print'
otherwise:
perl -0 -ne '/this/ or next; s/\0/\n/g; print'
Scott
--
Scott Wiersdorf
<scott@perlcode.org>
^ permalink raw reply
* [PATCH] import-tars: Add missing closing bracket
From: Ingmar Vanhassel @ 2009-10-09 12:08 UTC (permalink / raw)
To: git; +Cc: Peter Krefting, Junio C Hamano, Ingmar Vanhassel
This fixes an obvious syntax error that snuck in commit 7e787953:
syntax error at /home/ingmar/bin//git-import-tars line 143, near "/^$/ { "
syntax error at /home/ingmar/bin//git-import-tars line 145, near "} else"
syntax error at /home/ingmar/bin//git-import-tars line 152, near "}"
Signed-off-by: Ingmar Vanhassel <ingmar@exherbo.org>
---
contrib/fast-import/import-tars.perl | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/contrib/fast-import/import-tars.perl b/contrib/fast-import/import-tars.perl
index a909716..7001862 100755
--- a/contrib/fast-import/import-tars.perl
+++ b/contrib/fast-import/import-tars.perl
@@ -140,7 +140,7 @@ foreach my $tar_file (@ARGV)
} elsif (!$header_done && /^Author:\s+([^<>]*)\s+<(.*)>\s*$/i) {
$this_author_name = $1;
$this_author_email = $2;
- } elsif (!$header_done && /^$/ { # empty line ends header.
+ } elsif (!$header_done && /^$/) { # empty line ends header.
$header_done = 1;
} else {
$commit_msg .= $_;
--
1.6.5.rc3.193.gdf7a
^ permalink raw reply related
* [PATCH] git-svn: hide find_parent_branch output in double quiet mode
From: Simon Arlott @ 2009-10-09 12:21 UTC (permalink / raw)
To: gitster; +Cc: git
Hide find_parent_branch logging when -qq is specified.
This eliminates more unnecessary output when run from cron, e.g.:
Found possible branch point:
http://undernet-ircu.svn.sourceforge.net/svnroot/undernet-ircu/ircu2/trunk =>
http://undernet-ircu.svn.sourceforge.net/svnroot/undernet-ircu/ircu2/branches/authz,
1919
Found branch parent: (authz) ea061d76aea985dc0208d36fa5e0b2249b698557
Following parent with do_switch
Successfully followed parent
Signed-off-by: Simon Arlott <simon@fire.lp0.eu>
---
git-svn.perl | 19 ++++++++++++-------
1 files changed, 12 insertions(+), 7 deletions(-)
diff --git a/git-svn.perl b/git-svn.perl
index e0ec258..fd36270 100755
--- a/git-svn.perl
+++ b/git-svn.perl
@@ -2626,7 +2626,8 @@ sub find_parent_branch {
my $url = $self->ra->{url};
my $new_url = $url . $branch_from;
print STDERR "Found possible branch point: ",
- "$new_url => ", $self->full_url, ", $r\n";
+ "$new_url => ", $self->full_url, ", $r\n"
+ unless $::_q > 1;
$branch_from =~ s#^/##;
my $gs = $self->other_gs($new_url, $url,
$branch_from, $r, $self->{ref_id});
@@ -2647,11 +2648,13 @@ sub find_parent_branch {
($r0, $parent) = $gs->find_rev_before($r, 1);
}
if (defined $r0 && defined $parent) {
- print STDERR "Found branch parent: ($self->{ref_id}) $parent\n";
+ print STDERR "Found branch parent: ($self->{ref_id}) $parent\n"
+ unless $::_q > 1;
my $ed;
if ($self->ra->can_do_switch) {
$self->assert_index_clean($parent);
- print STDERR "Following parent with do_switch\n";
+ print STDERR "Following parent with do_switch\n"
+ unless $::_q > 1;
# do_switch works with svn/trunk >= r22312, but that
# is not included with SVN 1.4.3 (the latest version
# at the moment), so we can't rely on it
@@ -2666,18 +2669,20 @@ sub find_parent_branch {
print STDERR "Trees match:\n",
" $new_url\@$r0\n",
" ${\$self->full_url}\@$rev\n",
- "Following parent with no changes\n";
+ "Following parent with no changes\n"
+ unless $::_q > 1;
$self->tmp_index_do(sub {
command_noisy('read-tree', $parent);
});
$self->{last_commit} = $parent;
} else {
- print STDERR "Following parent with do_update\n";
+ print STDERR "Following parent with do_update\n"
+ unless $::_q > 1;
$ed = SVN::Git::Fetcher->new($self);
$self->ra->gs_do_update($rev, $rev, $self, $ed)
or die "SVN connection failed somewhere...\n";
}
- print STDERR "Successfully followed parent\n";
+ print STDERR "Successfully followed parent\n" unless $::_q > 1;
return $self->make_log_entry($rev, [$parent], $ed);
}
return undef;
@@ -2822,7 +2827,7 @@ sub other_gs {
$ref_id .= "\@$r";
# just grow a tail if we're not unique enough :x
$ref_id .= '-' while find_ref($ref_id);
- print STDERR "Initializing parent: $ref_id\n";
+ print STDERR "Initializing parent: $ref_id\n" unless $::_q > 1;
my ($u, $p, $repo_id) = ($new_url, '', $ref_id);
if ($u =~ s#^\Q$url\E(/|$)##) {
$p = $u;
--
1.6.3.3
--
Simon Arlott
^ permalink raw reply related
* [PATCH v2 (amend)] gitweb: Do not show 'patch' link for merge commits
From: Jakub Narebski @ 2009-10-09 12:26 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio Hamano
In-Reply-To: <200910091423.51286.jnareb@gmail.com>
The 'patch' view is about generating text/plain patch that can be
given to "git am", and "git am" doesn't understand merges anyway.
Therefore link to 'patch' view should not be shown for merge commits.
Also call to git-format-patch inside the 'patch' action would fail
when 'patch' action is called for a merge commit, with "Reading
git-format-patch failed" text as 'patch' view body.
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
Changes since v1:
* Do not show 'patch' link for merge commits not only in 'commit'
view, but also in 'commitdiff' view (more complete)
* 'patch' link is shown also for root (parentless) commits; it
works correctly thanks to passing '--root' option to git-format-patch
(remove unnecessary restriction)
* better commit message thanks to discussion with Jeff King
gitweb/gitweb.perl | 6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)
diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 24b2193..14f31dc 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -5328,7 +5328,7 @@ sub git_commit {
} @$parents ) .
')';
}
- if (gitweb_check_feature('patches')) {
+ if (gitweb_check_feature('patches') && @$parents <= 1) {
$formats_nav .= " | " .
$cgi->a({-href => href(action=>"patch", -replay=>1)},
"patch");
@@ -5616,7 +5616,7 @@ sub git_commitdiff {
$formats_nav =
$cgi->a({-href => href(action=>"commitdiff_plain", -replay=>1)},
"raw");
- if ($patch_max) {
+ if ($patch_max && @{$co{'parents'}} <= 1) {
$formats_nav .= " | " .
$cgi->a({-href => href(action=>"patch", -replay=>1)},
"patch");
@@ -5824,7 +5824,7 @@ sub git_commitdiff_plain {
# format-patch-style patches
sub git_patch {
- git_commitdiff(-format => 'patch', -single=> 1);
+ git_commitdiff(-format => 'patch', -single => 1);
}
sub git_patches {
--
1.6.4.2
^ permalink raw reply related
* Re: [PATCH v2] gitweb: Do not show 'patch' link for merge commits
From: Jakub Narebski @ 2009-10-09 12:23 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio Hamano
In-Reply-To: <200910091410.15904.jnareb@gmail.com>
Jakub Narebski wrote:
> @@ -5616,7 +5616,7 @@ sub git_commitdiff {
> $formats_nav =
> $cgi->a({-href => href(action=>"commitdiff_plain", -replay=>1)},
> "raw");
> - if ($patch_max) {
> + if ($patch_max && && @{$co{'parents'}} <= 1) {
Gaaaah. It should be "&&", not "&& &&". I'm extremely sorry!
> $formats_nav .= " | " .
> $cgi->a({-href => href(action=>"patch", -replay=>1)},
> "patch");
--
Jakub Narebski
Poland
^ permalink raw reply
* [PATCH v2] gitweb: Do not show 'patch' link for merge commits
From: Jakub Narebski @ 2009-10-09 12:10 UTC (permalink / raw)
To: git; +Cc: Jeff King, Junio Hamano
In-Reply-To: <200910011118.02875.jnareb@gmail.com>
The 'patch' view is about generating text/plain patch that can be
given to "git am", and "git am" doesn't understand merges anyway.
Therefore link to 'patch' view should not be shown for merge commits.
Also call to git-format-patch inside the 'patch' action would fail
when 'patch' action is called for a merge commit, with "Reading
git-format-patch failed" text as 'patch' view body.
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
On Thu, 1 Oct 2009, Jakub Narebski wrote:
> I'll send v2 of this patch in a bit.
Here it is.
Changes since v1:
* Do not show 'patch' link for merge commits not only in 'commit'
view, but also in 'commitdiff' view (more complete)
* 'patch' link is shown also for root (parentless) commits; it
works correctly thanks to passing '--root' option to git-format-patch
(remove unnecessary restriction)
* better commit message thanks to discussion with Jeff King
gitweb/gitweb.perl | 6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)
diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 24b2193..14f31dc 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -5328,7 +5328,7 @@ sub git_commit {
} @$parents ) .
')';
}
- if (gitweb_check_feature('patches')) {
+ if (gitweb_check_feature('patches') && @$parents <= 1) {
$formats_nav .= " | " .
$cgi->a({-href => href(action=>"patch", -replay=>1)},
"patch");
@@ -5616,7 +5616,7 @@ sub git_commitdiff {
$formats_nav =
$cgi->a({-href => href(action=>"commitdiff_plain", -replay=>1)},
"raw");
- if ($patch_max) {
+ if ($patch_max && && @{$co{'parents'}} <= 1) {
$formats_nav .= " | " .
$cgi->a({-href => href(action=>"patch", -replay=>1)},
"patch");
@@ -5824,7 +5824,7 @@ sub git_commitdiff_plain {
# format-patch-style patches
sub git_patch {
- git_commitdiff(-format => 'patch', -single=> 1);
+ git_commitdiff(-format => 'patch', -single => 1);
}
sub git_patches {
--
1.6.4.2
^ permalink raw reply related
* Re: [RFC/PATCHv7 00/22] git notes
From: Johan Herland @ 2009-10-09 10:32 UTC (permalink / raw)
To: git
Cc: gitster, Johannes.Schindelin, trast, tavestbo, git, chriscool,
spearce, sam
In-Reply-To: <1255083738-23263-2-git-send-email-johan@herland.net>
On Friday 09 October 2009, Johan Herland wrote:
> Hi,
>
> Here is the 7th iteration of the git-notes series. Changes in this
> iteration are as follows:
Oops... Diregard this one. Seems I had a stray 0000-*.patch.bak lying
around...
...Johan
^ permalink raw reply
* [RFC/PATCHv7 20/22] Notes API: Allow multiple concurrent notes trees with new struct notes_tree
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
The new struct notes_tree encapsulates access to a specific notes tree.
It is provided to allow callers to interface with several different notes
trees simultaneously.
A struct notes_tree * parameter is added to every function in the notes API.
In all cases, NULL can be passed, in which case, a falback "default" notes
tree (declared in notes.c) is used.
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 67 ++++++++++++++++++++++++++++++++++++++-----------------------
notes.h | 57 +++++++++++++++++++++++++++++++++++++--------------
pretty.c | 4 +-
3 files changed, 85 insertions(+), 43 deletions(-)
diff --git a/notes.c b/notes.c
index 9581b98..a5d9736 100644
--- a/notes.c
+++ b/notes.c
@@ -50,9 +50,7 @@ struct leaf_node {
#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
(memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
-static struct int_node root_node;
-
-static int initialized;
+static struct notes_tree default_tree;
static void load_subtree(struct leaf_node *subtree, struct int_node *node,
unsigned int n);
@@ -434,14 +432,15 @@ redo:
return 0;
}
-void init_notes(const char *notes_ref, int flags)
+void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
{
unsigned char sha1[20], object_sha1[20];
unsigned mode;
struct leaf_node root_tree;
- assert(!initialized);
- initialized = 1;
+ if (!t)
+ t = &default_tree;
+ assert(!t->initialized);
if (!notes_ref) {
const char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);
@@ -451,6 +450,10 @@ void init_notes(const char *notes_ref, int flags)
notes_ref = GIT_NOTES_DEFAULT_REF;
}
+ t->root = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
+ t->ref = notes_ref ? xstrdup(notes_ref) : NULL;
+ t->initialized = 1;
+
if (flags & NOTES_INIT_EMPTY || !notes_ref ||
read_ref(notes_ref, object_sha1) ||
get_tree_entry(object_sha1, "", sha1, &mode))
@@ -458,44 +461,56 @@ void init_notes(const char *notes_ref, int flags)
hashclr(root_tree.key_sha1);
hashcpy(root_tree.val_sha1, sha1);
- load_subtree(&root_tree, &root_node, 0);
+ load_subtree(&root_tree, t->root, 0);
}
-void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)
+void add_note(struct notes_tree *t, const unsigned char *object_sha1,
+ const unsigned char *note_sha1)
{
struct leaf_node *l;
- assert(initialized);
+ if (!t)
+ t = &default_tree;
+ assert(t->initialized);
l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
hashcpy(l->key_sha1, object_sha1);
hashcpy(l->val_sha1, note_sha1);
- note_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);
+ note_tree_insert(t->root, 0, l, PTR_TYPE_NOTE);
}
-const unsigned char *get_note(const unsigned char *object_sha1)
+const unsigned char *get_note(struct notes_tree *t,
+ const unsigned char *object_sha1)
{
struct leaf_node *found;
- assert(initialized);
- found = note_tree_find(&root_node, 0, object_sha1);
+ if (!t)
+ t = &default_tree;
+ assert(t->initialized);
+ found = note_tree_find(t->root, 0, object_sha1);
return found ? found->val_sha1 : NULL;
}
-int for_each_note(each_note_fn fn, void *cb_data)
+int for_each_note(struct notes_tree *t, each_note_fn fn, void *cb_data)
{
- assert(initialized);
- return for_each_note_helper(&root_node, 0, 0, fn, cb_data);
+ if (!t)
+ t = &default_tree;
+ assert(t->initialized);
+ return for_each_note_helper(t->root, 0, 0, fn, cb_data);
}
-void free_notes(void)
+void free_notes(struct notes_tree *t)
{
- note_tree_free(&root_node);
- memset(&root_node, 0, sizeof(struct int_node));
- initialized = 0;
+ if (!t)
+ t = &default_tree;
+ if (t->root)
+ note_tree_free(t->root);
+ free(t->root);
+ free(t->ref);
+ memset(t, 0, sizeof(struct notes_tree));
}
-void format_note(const unsigned char *object_sha1, struct strbuf *sb,
- const char *output_encoding, int flags)
+void format_note(struct notes_tree *t, const unsigned char *object_sha1,
+ struct strbuf *sb, const char *output_encoding, int flags)
{
static const char utf8[] = "utf-8";
const unsigned char *sha1;
@@ -503,10 +518,12 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,
unsigned long linelen, msglen;
enum object_type type;
- if (!initialized)
- init_notes(NULL, 0);
+ if (!t)
+ t = &default_tree;
+ if (!t->initialized)
+ init_notes(t, NULL, 0);
- sha1 = get_note(object_sha1);
+ sha1 = get_note(t, object_sha1);
if (!sha1)
return;
diff --git a/notes.h b/notes.h
index 28648fd..181c3d6 100644
--- a/notes.h
+++ b/notes.h
@@ -2,6 +2,21 @@
#define NOTES_H
/*
+ * Notes tree object
+ *
+ * Encapsulates the internal notes tree structure associated with a notes ref.
+ * Whenever a struct notes_tree pointer is required below, you may pass NULL in
+ * order to use the default/internal notes tree. E.g. you only need to pass a
+ * non-NULL value if you need to refer to several different notes trees
+ * simultaneously.
+ */
+struct notes_tree {
+ struct int_node *root;
+ char *ref;
+ int initialized;
+};
+
+/*
* Flags controlling behaviour of notes tree initialization
*
* Default behaviour is to initialize the notes tree from the tree object
@@ -10,35 +25,43 @@
#define NOTES_INIT_EMPTY 1
/*
- * Initialize internal notes tree structure with the notes tree at the given
+ * Initialize the given notes_tree with the notes tree structure at the given
* ref. If given ref is NULL, the value of the $GIT_NOTES_REF environment
* variable is used, and if that is missing, the default notes ref is used
* ("refs/notes/commits").
*
- * If you need to re-intialize the internal notes tree structure (e.g. loading
- * from a different notes ref), please first de-initialize the current notes
- * tree by calling free_notes().
+ * If you need to re-intialize a notes_tree structure (e.g. when switching from
+ * one notes ref to another), you must first de-initialize the notes_tree
+ * structure by calling free_notes(struct notes_tree *).
+ *
+ * If you pass t == NULL, the default internal notes_tree will be initialized.
+ *
+ * Precondition: The notes_tree structure is zeroed (this can be achieved with
+ * memset(t, 0, sizeof(struct notes_tree)))
*/
-void init_notes(const char *notes_ref, int flags);
+void init_notes(struct notes_tree *t, const char *notes_ref, int flags);
-/* Add the given note object to the internal notes tree structure */
-void add_note(const unsigned char *object_sha1,
+/* Add the given note object to the given notes_tree structure */
+void add_note(struct notes_tree *t, const unsigned char *object_sha1,
const unsigned char *note_sha1);
/* Get the note object SHA1 containing the note data for the given object */
-const unsigned char *get_note(const unsigned char *object_sha1);
+const unsigned char *get_note(struct notes_tree *t,
+ const unsigned char *object_sha1);
/*
- * Calls the specified function for each note until it returns nonzero,
- * and returns the value
+ * Calls the specified function for each note in the given notes_tree
+ *
+ * If the callback returns nonzero, the note walk is aborted, and the return
+ * value from the callback is returned from for_each_note().
*/
typedef int each_note_fn(const unsigned char *object_sha1,
const unsigned char *note_sha1, const char *note_tree_path,
void *cb_data);
-int for_each_note(each_note_fn fn, void *cb_data);
+int for_each_note(struct notes_tree *t, each_note_fn fn, void *cb_data);
-/* Free (and de-initialize) the internal notes tree structure */
-void free_notes(void);
+/* Free (and de-initialize) the give notes_tree structure */
+void free_notes(struct notes_tree *t);
/* Flags controlling how notes are formatted */
#define NOTES_SHOW_HEADER 1
@@ -47,12 +70,14 @@ void free_notes(void);
/*
* Fill the given strbuf with the notes associated with the given object.
*
- * If the internal notes structure is not initialized, it will be auto-
+ * If the given notes_tree structure is not initialized, it will be auto-
* initialized to the default value (see documentation for init_notes() above).
+ * If the given notes_tree is NULL, the internal/default notes_tree will be
+ * used instead.
*
* 'flags' is a bitwise combination of the above formatting flags.
*/
-void format_note(const unsigned char *object_sha1, struct strbuf *sb,
- const char *output_encoding, int flags);
+void format_note(struct notes_tree *t, const unsigned char *object_sha1,
+ struct strbuf *sb, const char *output_encoding, int flags);
#endif
diff --git a/pretty.c b/pretty.c
index 81791f5..5ceb702 100644
--- a/pretty.c
+++ b/pretty.c
@@ -703,7 +703,7 @@ static size_t format_commit_item(struct strbuf *sb, const char *placeholder,
format_decoration(sb, commit);
return 1;
case 'N':
- format_note(commit->object.sha1, sb, git_log_output_encoding ?
+ format_note(NULL, commit->object.sha1, sb, git_log_output_encoding ?
git_log_output_encoding : git_commit_encoding, 0);
return 1;
}
@@ -982,7 +982,7 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,
strbuf_addch(sb, '\n');
if (fmt != CMIT_FMT_ONELINE)
- format_note(commit->object.sha1, sb, encoding,
+ format_note(NULL, commit->object.sha1, sb, encoding,
NOTES_SHOW_HEADER | NOTES_INDENT);
free(reencoded);
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 19/22] Notes API: for_each_note(): Traverse the entire notes tree with a callback
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
This includes a first attempt at creating an optimal fanout scheme (which
is created on-the-fly, while traversing).
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 101 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
notes.h | 9 +++++
2 files changed, 110 insertions(+), 0 deletions(-)
diff --git a/notes.c b/notes.c
index 2196a5f..9581b98 100644
--- a/notes.c
+++ b/notes.c
@@ -339,6 +339,101 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
free(buf);
}
+/*
+ * Determine optimal on-disk fanout for this part of the notes tree
+ *
+ * Given a (sub)tree and the level in the internal tree structure, determine
+ * whether or not the given existing fanout should be expanded for this
+ * (sub)tree.
+ *
+ * Values of the 'fanout' variable:
+ * - 0: No fanout (all notes are stored directly in the root notes tree)
+ * - 1: 2/38 fanout
+ * - 2: 2/2/36 fanout
+ * - 3: 2/2/2/34 fanout
+ * etc.
+ */
+static unsigned char determine_fanout(struct int_node *tree, unsigned char n,
+ unsigned char fanout)
+{
+ /*
+ * The following is a simple heuristic that works well in practice:
+ * For each even-numbered 16-tree level (remember that each on-disk
+ * fanout level corresponds to two 16-tree levels), peek at all 16
+ * entries at that tree level. If any of them are subtree entries, then
+ * there are likely plenty of notes below this level, so we return an
+ * incremented fanout immediately. Otherwise, we return an incremented
+ * fanout only if all of the entries at this level are int_nodes.
+ */
+ unsigned int i;
+ if ((n % 2) || (n > 2 * fanout))
+ return fanout;
+ for (i = 0; i < 16; i++) {
+ switch(GET_PTR_TYPE(tree->a[i])) {
+ case PTR_TYPE_SUBTREE:
+ return fanout + 1;
+ case PTR_TYPE_INTERNAL:
+ continue;
+ default:
+ return fanout;
+ }
+ }
+ return fanout + 1;
+}
+
+static void construct_path_with_fanout(const unsigned char *sha1,
+ unsigned char fanout, char *path)
+{
+ unsigned int i = 0, j = 0;
+ const char *hex_sha1 = sha1_to_hex(sha1);
+ assert(fanout < 20);
+ while (fanout) {
+ path[i++] = hex_sha1[j++];
+ path[i++] = hex_sha1[j++];
+ path[i++] = '/';
+ fanout--;
+ }
+ strcpy(path + i, hex_sha1 + j);
+}
+
+static int for_each_note_helper(struct int_node *tree, unsigned char n,
+ unsigned char fanout, each_note_fn fn, void *cb_data)
+{
+ unsigned int i;
+ void *p;
+ int ret = 0;
+ struct leaf_node *l;
+ static char path[40 + 19 + 1]; /* hex SHA1 + 19 * '/' + NUL */
+
+ fanout = determine_fanout(tree, n, fanout);
+ for (i = 0; i < 16; i++) {
+redo:
+ p = tree->a[i];
+ switch(GET_PTR_TYPE(p)) {
+ case PTR_TYPE_INTERNAL:
+ /* recurse into int_node */
+ ret = for_each_note_helper(
+ CLR_PTR_TYPE(p), n + 1, fanout, fn, cb_data);
+ break;
+ case PTR_TYPE_SUBTREE:
+ /* unpack subtree and resume traversal */
+ l = (struct leaf_node *) CLR_PTR_TYPE(p);
+ tree->a[i] = NULL;
+ load_subtree(l, tree, n);
+ free(l);
+ goto redo;
+ case PTR_TYPE_NOTE:
+ l = (struct leaf_node *) CLR_PTR_TYPE(p);
+ construct_path_with_fanout(l->key_sha1, fanout, path);
+ ret = fn(l->key_sha1, l->val_sha1, path, cb_data);
+ break;
+ }
+ if (ret)
+ return ret;
+ }
+ return 0;
+}
+
void init_notes(const char *notes_ref, int flags)
{
unsigned char sha1[20], object_sha1[20];
@@ -386,6 +481,12 @@ const unsigned char *get_note(const unsigned char *object_sha1)
return found ? found->val_sha1 : NULL;
}
+int for_each_note(each_note_fn fn, void *cb_data)
+{
+ assert(initialized);
+ return for_each_note_helper(&root_node, 0, 0, fn, cb_data);
+}
+
void free_notes(void)
{
note_tree_free(&root_node);
diff --git a/notes.h b/notes.h
index 21a8930..28648fd 100644
--- a/notes.h
+++ b/notes.h
@@ -28,6 +28,15 @@ void add_note(const unsigned char *object_sha1,
/* Get the note object SHA1 containing the note data for the given object */
const unsigned char *get_note(const unsigned char *object_sha1);
+/*
+ * Calls the specified function for each note until it returns nonzero,
+ * and returns the value
+ */
+typedef int each_note_fn(const unsigned char *object_sha1,
+ const unsigned char *note_sha1, const char *note_tree_path,
+ void *cb_data);
+int for_each_note(each_note_fn fn, void *cb_data);
+
/* Free (and de-initialize) the internal notes tree structure */
void free_notes(void);
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 21/22] Refactor notes concatenation into a flexible interface for combining notes
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
When adding a note to an object that already has an existing note, the
current solution is to concatenate the contents of the two notes. However,
the caller may instead wish to _overwrite_ the existing note with the new
note, or maybe even _ignore_ the new note, and keep the existing one. There
might also be other ways of combining notes that are only known to the
caller.
Therefore, instead of unconditionally concatenating notes, we let the caller
specify how to combine notes, by passing in a pointer to a function for
combining notes. The caller may choose to implement its own function for
notes combining, but normally one of the following three conveniently
supplied notes combination functions will be sufficient:
- combine_notes_concatenate() combines the two notes by appending the
contents of the new note to the contents of the existing note.
- combine_notes_overwrite() replaces the existing note with the new note.
- combine_notes_ignore() keeps the existing note, and ignores the new note.
A combine_notes function can be passed to init_notes() to choose a default
combine_notes function for that notes tree. If NULL is given, the notes tree
falls back to combine_notes_concatenate() as the ultimate default.
A combine_notes function can also be passed directly to add_note(), to
control the notes combining behaviour for a note addition in particular.
If NULL is passed, the combine_notes function registered for the given
notes tree is used.
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 132 +++++++++++++++++++++++++++++++++++---------------------------
notes.h | 34 +++++++++++++++-
2 files changed, 106 insertions(+), 60 deletions(-)
diff --git a/notes.c b/notes.c
index a5d9736..19ae492 100644
--- a/notes.c
+++ b/notes.c
@@ -127,55 +127,12 @@ static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
return NULL;
}
-/* Create a new blob object by concatenating the two given blob objects */
-static int concatenate_notes(unsigned char *cur_sha1,
- const unsigned char *new_sha1)
-{
- char *cur_msg, *new_msg, *buf;
- unsigned long cur_len, new_len, buf_len;
- enum object_type cur_type, new_type;
- int ret;
-
- /* read in both note blob objects */
- new_msg = read_sha1_file(new_sha1, &new_type, &new_len);
- if (!new_msg || !new_len || new_type != OBJ_BLOB) {
- free(new_msg);
- return 0;
- }
- cur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);
- if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
- free(cur_msg);
- free(new_msg);
- hashcpy(cur_sha1, new_sha1);
- return 0;
- }
-
- /* we will separate the notes by a newline anyway */
- if (cur_msg[cur_len - 1] == '\n')
- cur_len--;
-
- /* concatenate cur_msg and new_msg into buf */
- buf_len = cur_len + 1 + new_len;
- buf = (char *) xmalloc(buf_len);
- memcpy(buf, cur_msg, cur_len);
- buf[cur_len] = '\n';
- memcpy(buf + cur_len + 1, new_msg, new_len);
-
- free(cur_msg);
- free(new_msg);
-
- /* create a new blob object from buf */
- ret = write_sha1_file(buf, buf_len, "blob", cur_sha1);
- free(buf);
- return ret;
-}
-
/*
* To insert a leaf_node:
* Search to the tree location appropriate for the given leaf_node's key:
* - If location is unused (NULL), store the tweaked pointer directly there
* - If location holds a note entry that matches the note-to-be-inserted, then
- * concatenate the two notes.
+ * combine the two notes (by calling the given combine_notes function).
* - If location holds a note entry that matches the subtree-to-be-inserted,
* then unpack the subtree-to-be-inserted into the location.
* - If location holds a matching subtree entry, unpack the subtree at that
@@ -184,7 +141,8 @@ static int concatenate_notes(unsigned char *cur_sha1,
* node-to-be-inserted, and store the new int_node into the location.
*/
static void note_tree_insert(struct int_node *tree, unsigned char n,
- struct leaf_node *entry, unsigned char type)
+ struct leaf_node *entry, unsigned char type,
+ combine_notes_fn combine_notes)
{
struct int_node *new_node;
struct leaf_node *l;
@@ -205,12 +163,11 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,
if (!hashcmp(l->val_sha1, entry->val_sha1))
return;
- if (concatenate_notes(l->val_sha1,
- entry->val_sha1))
- die("failed to concatenate note %s "
- "into note %s for object %s",
- sha1_to_hex(entry->val_sha1),
+ if (combine_notes(l->val_sha1, entry->val_sha1))
+ die("failed to combine notes %s and %s"
+ " for object %s",
sha1_to_hex(l->val_sha1),
+ sha1_to_hex(entry->val_sha1),
sha1_to_hex(l->key_sha1));
free(entry);
return;
@@ -233,7 +190,7 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,
*p = NULL;
load_subtree(l, tree, n);
free(l);
- note_tree_insert(tree, n, entry, type);
+ note_tree_insert(tree, n, entry, type, combine_notes);
return;
}
break;
@@ -243,9 +200,9 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,
assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||
GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);
new_node = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
- note_tree_insert(new_node, n + 1, l, GET_PTR_TYPE(*p));
+ note_tree_insert(new_node, n + 1, l, GET_PTR_TYPE(*p), combine_notes);
*p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
- note_tree_insert(new_node, n + 1, entry, type);
+ note_tree_insert(new_node, n + 1, entry, type, combine_notes);
}
/* Free the entire notes data contained in the given tree */
@@ -331,7 +288,8 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
l->key_sha1[19] = (unsigned char) len;
type = PTR_TYPE_SUBTREE;
}
- note_tree_insert(node, n, l, type);
+ note_tree_insert(node, n, l, type,
+ combine_notes_concatenate);
}
}
free(buf);
@@ -432,7 +390,59 @@ redo:
return 0;
}
-void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
+int combine_notes_concatenate(unsigned char *cur_sha1, const unsigned char *new_sha1)
+{
+ char *cur_msg, *new_msg, *buf;
+ unsigned long cur_len, new_len, buf_len;
+ enum object_type cur_type, new_type;
+ int ret;
+
+ /* read in both note blob objects */
+ new_msg = read_sha1_file(new_sha1, &new_type, &new_len);
+ if (!new_msg || !new_len || new_type != OBJ_BLOB) {
+ free(new_msg);
+ return 0;
+ }
+ cur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);
+ if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
+ free(cur_msg);
+ free(new_msg);
+ hashcpy(cur_sha1, new_sha1);
+ return 0;
+ }
+
+ /* we will separate the notes by a newline anyway */
+ if (cur_msg[cur_len - 1] == '\n')
+ cur_len--;
+
+ /* concatenate cur_msg and new_msg into buf */
+ buf_len = cur_len + 1 + new_len;
+ buf = (char *) xmalloc(buf_len);
+ memcpy(buf, cur_msg, cur_len);
+ buf[cur_len] = '\n';
+ memcpy(buf + cur_len + 1, new_msg, new_len);
+ free(cur_msg);
+ free(new_msg);
+
+ /* create a new blob object from buf */
+ ret = write_sha1_file(buf, buf_len, "blob", cur_sha1);
+ free(buf);
+ return ret;
+}
+
+int combine_notes_overwrite(unsigned char *cur_sha1, const unsigned char *new_sha1)
+{
+ hashcpy(cur_sha1, new_sha1);
+ return 0;
+}
+
+int combine_notes_ignore(unsigned char *cur_sha1, const unsigned char *new_sha1)
+{
+ return 0;
+}
+
+void init_notes(struct notes_tree *t, const char *notes_ref,
+ combine_notes_fn combine_notes, int flags)
{
unsigned char sha1[20], object_sha1[20];
unsigned mode;
@@ -450,8 +460,12 @@ void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
notes_ref = GIT_NOTES_DEFAULT_REF;
}
+ if (!combine_notes)
+ combine_notes = combine_notes_concatenate;
+
t->root = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
t->ref = notes_ref ? xstrdup(notes_ref) : NULL;
+ t->combine_notes = combine_notes;
t->initialized = 1;
if (flags & NOTES_INIT_EMPTY || !notes_ref ||
@@ -465,17 +479,19 @@ void init_notes(struct notes_tree *t, const char *notes_ref, int flags)
}
void add_note(struct notes_tree *t, const unsigned char *object_sha1,
- const unsigned char *note_sha1)
+ const unsigned char *note_sha1, combine_notes_fn combine_notes)
{
struct leaf_node *l;
if (!t)
t = &default_tree;
assert(t->initialized);
+ if (!combine_notes)
+ combine_notes = t->combine_notes;
l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
hashcpy(l->key_sha1, object_sha1);
hashcpy(l->val_sha1, note_sha1);
- note_tree_insert(t->root, 0, l, PTR_TYPE_NOTE);
+ note_tree_insert(t->root, 0, l, PTR_TYPE_NOTE, combine_notes);
}
const unsigned char *get_note(struct notes_tree *t,
@@ -521,7 +537,7 @@ void format_note(struct notes_tree *t, const unsigned char *object_sha1,
if (!t)
t = &default_tree;
if (!t->initialized)
- init_notes(t, NULL, 0);
+ init_notes(t, NULL, NULL, 0);
sha1 = get_note(t, object_sha1);
if (!sha1)
diff --git a/notes.h b/notes.h
index 181c3d6..f5d4ccd 100644
--- a/notes.h
+++ b/notes.h
@@ -2,6 +2,30 @@
#define NOTES_H
/*
+ * Function type for combining two notes annotating the same object.
+ *
+ * When adding a new note annotating the same object as an existing note, it is
+ * up to the caller to decide how to combine the two notes. The decision is
+ * made by passing in a function of the following form. The function accepts
+ * two SHA1s -- of the existing note and the new note, respectively. The
+ * function then combines the notes in whatever way it sees fit, and writes the
+ * resulting SHA1 into the first SHA1 argument (cur_sha1). A non-zero return
+ * value indicates failure.
+ *
+ * The two given SHA1s are guaranteed to be non-NULL and different.
+ *
+ * The default combine_notes function (you get this when passing NULL) is
+ * combine_notes_concatenate(), which appends the contents of the new note to
+ * the contents of the existing note.
+ */
+typedef int combine_notes_fn(unsigned char *cur_sha1, const unsigned char *new_sha1);
+
+/* Common notes combinators */
+int combine_notes_concatenate(unsigned char *cur_sha1, const unsigned char *new_sha1);
+int combine_notes_overwrite(unsigned char *cur_sha1, const unsigned char *new_sha1);
+int combine_notes_ignore(unsigned char *cur_sha1, const unsigned char *new_sha1);
+
+/*
* Notes tree object
*
* Encapsulates the internal notes tree structure associated with a notes ref.
@@ -13,6 +37,7 @@
struct notes_tree {
struct int_node *root;
char *ref;
+ combine_notes_fn *combine_notes;
int initialized;
};
@@ -36,14 +61,19 @@ struct notes_tree {
*
* If you pass t == NULL, the default internal notes_tree will be initialized.
*
+ * The combine_notes function that is passed becomes the default combine_notes
+ * function for the given notes_tree. If NULL is passed, the default
+ * combine_notes function is combine_notes_concatenate().
+ *
* Precondition: The notes_tree structure is zeroed (this can be achieved with
* memset(t, 0, sizeof(struct notes_tree)))
*/
-void init_notes(struct notes_tree *t, const char *notes_ref, int flags);
+void init_notes(struct notes_tree *t, const char *notes_ref,
+ combine_notes_fn combine_notes, int flags);
/* Add the given note object to the given notes_tree structure */
void add_note(struct notes_tree *t, const unsigned char *object_sha1,
- const unsigned char *note_sha1);
+ const unsigned char *note_sha1, combine_notes_fn combine_notes);
/* Get the note object SHA1 containing the note data for the given object */
const unsigned char *get_note(struct notes_tree *t,
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 18/22] Notes API: get_note(): Return the note annotating the given object
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
Created by a simple cleanup and rename of lookup_notes().
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 15 ++++++++-------
notes.h | 3 +++
2 files changed, 11 insertions(+), 7 deletions(-)
diff --git a/notes.c b/notes.c
index 49a3e86..2196a5f 100644
--- a/notes.c
+++ b/notes.c
@@ -377,12 +377,13 @@ void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)
note_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);
}
-static unsigned char *lookup_notes(const unsigned char *object_sha1)
+const unsigned char *get_note(const unsigned char *object_sha1)
{
- struct leaf_node *found = note_tree_find(&root_node, 0, object_sha1);
- if (found)
- return found->val_sha1;
- return NULL;
+ struct leaf_node *found;
+
+ assert(initialized);
+ found = note_tree_find(&root_node, 0, object_sha1);
+ return found ? found->val_sha1 : NULL;
}
void free_notes(void)
@@ -396,7 +397,7 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,
const char *output_encoding, int flags)
{
static const char utf8[] = "utf-8";
- unsigned char *sha1;
+ const unsigned char *sha1;
char *msg, *msg_p;
unsigned long linelen, msglen;
enum object_type type;
@@ -404,7 +405,7 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,
if (!initialized)
init_notes(NULL, 0);
- sha1 = lookup_notes(object_sha1);
+ sha1 = get_note(object_sha1);
if (!sha1)
return;
diff --git a/notes.h b/notes.h
index 5f22852..21a8930 100644
--- a/notes.h
+++ b/notes.h
@@ -25,6 +25,9 @@ void init_notes(const char *notes_ref, int flags);
void add_note(const unsigned char *object_sha1,
const unsigned char *note_sha1);
+/* Get the note object SHA1 containing the note data for the given object */
+const unsigned char *get_note(const unsigned char *object_sha1);
+
/* Free (and de-initialize) the internal notes tree structure */
void free_notes(void);
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 22/22] fast-import: Proper notes tree manipulation using the notes API
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
This patch teaches 'git fast-import' to use the notes API to organize
the manipulation of note objects through a fast-import stream. Note
objects are added to the notes tree through the 'N' command, and when
we're about to store the tree object for the current commit, we walk
through the notes tree and insert all the notes into the stored tree.
Signed-off-by: Johan Herland <johan@herland.net>
---
fast-import.c | 98 ++++++++++++++++++++++++++++--
t/t9300-fast-import.sh | 156 ++++++++++++++++++++++++++++++++++++++++++++----
2 files changed, 235 insertions(+), 19 deletions(-)
diff --git a/fast-import.c b/fast-import.c
index fcdcfaa..5837875 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -156,6 +156,7 @@ Format of STDIN stream:
#include "csum-file.h"
#include "quote.h"
#include "exec_cmd.h"
+#include "notes.h"
#define PACK_ID_BITS 16
#define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
@@ -246,6 +247,7 @@ struct branch
struct tree_entry branch_tree;
uintmax_t last_commit;
unsigned active : 1;
+ unsigned has_notes : 1;
unsigned pack_id : PACK_ID_BITS;
unsigned char sha1[20];
};
@@ -277,6 +279,11 @@ struct recent_command
char *buf;
};
+struct notes_tree_list {
+ struct notes_tree tree;
+ struct notes_tree_list *next;
+};
+
/* Configured limits on output */
static unsigned long max_depth = 10;
static off_t max_packsize = (1LL << 32) - 1;
@@ -345,6 +352,9 @@ static struct branch *active_branches;
static struct tag *first_tag;
static struct tag *last_tag;
+/* Notes data */
+static struct notes_tree_list *notes_trees;
+
/* Input stream parsing */
static whenspec_type whenspec = WHENSPEC_RAW;
static struct strbuf command_buf = STRBUF_INIT;
@@ -2060,7 +2070,7 @@ static void file_change_cr(struct branch *b, int rename)
leaf.tree);
}
-static void note_change_n(struct branch *b)
+static void note_change_n(struct branch *b, struct notes_tree *notes)
{
const char *p = command_buf.buf + 2;
static struct strbuf uq = STRBUF_INIT;
@@ -2130,8 +2140,8 @@ static void note_change_n(struct branch *b)
typename(type), command_buf.buf);
}
- tree_content_set(&b->branch_tree, sha1_to_hex(commit_sha1), sha1,
- S_IFREG | 0644, NULL);
+ assert(notes);
+ add_note(notes, commit_sha1, sha1, NULL);
}
static void file_change_deleteall(struct branch *b)
@@ -2254,6 +2264,68 @@ static struct hash_list *parse_merge(unsigned int *count)
return list;
}
+static struct notes_tree *new_notes_tree(struct branch *b)
+{
+ struct notes_tree_list *ret = (struct notes_tree_list *)
+ xcalloc(sizeof(struct notes_tree_list), 1);
+ init_notes(&ret->tree, b->name, combine_notes_overwrite, NOTES_INIT_EMPTY);
+ ret->next = notes_trees;
+ notes_trees = ret;
+ b->has_notes = 1;
+ return &ret->tree;
+}
+
+static struct notes_tree *get_notes_tree(struct branch *b)
+{
+ struct notes_tree_list *cur = notes_trees;
+ if (!b->has_notes)
+ return NULL;
+ while (cur && strcmp(cur->tree.ref, b->name))
+ cur = cur->next;
+ assert(cur);
+ return &cur->tree;
+}
+
+static void delete_notes_tree(struct branch *b, struct notes_tree **tree)
+{
+ struct notes_tree_list *cur = notes_trees, *prev = NULL;
+ while (cur && strcmp(cur->tree.ref, b->name)) {
+ prev = cur;
+ cur = cur->next;
+ }
+ assert(cur && &cur->tree == *tree);
+ if (prev)
+ prev->next = cur->next;
+ else
+ notes_trees = cur->next;
+ free_notes(&cur->tree);
+ free(cur);
+ *tree = NULL;
+ b->has_notes = 0;
+}
+
+static int write_notes_set_helper(
+ const unsigned char *object_sha1,
+ const unsigned char *note_sha1,
+ const char *note_tree_path,
+ void *cb_data)
+{
+ struct tree_entry *t = (struct tree_entry *) cb_data;
+ tree_content_set(t, note_tree_path, note_sha1, S_IFREG | 0644, NULL);
+ return 0;
+}
+
+static int write_notes_remove_helper(
+ const unsigned char *object_sha1,
+ const unsigned char *note_sha1,
+ const char *note_tree_path,
+ void *cb_data)
+{
+ struct tree_entry *t = (struct tree_entry *) cb_data;
+ tree_content_remove(t, note_tree_path, NULL);
+ return 0;
+}
+
static void parse_new_commit(void)
{
static struct strbuf msg = STRBUF_INIT;
@@ -2263,6 +2335,7 @@ static void parse_new_commit(void)
char *committer = NULL;
struct hash_list *merge_list = NULL;
unsigned int merge_count;
+ struct notes_tree *notes;
/* Obtain the branch name from the rest of our command */
sp = strchr(command_buf.buf, ' ') + 1;
@@ -2293,6 +2366,11 @@ static void parse_new_commit(void)
load_branch(b);
}
+ /* Retrieve notes tree, if needed */
+ notes = get_notes_tree(b);
+ if (notes)
+ for_each_note(notes, write_notes_remove_helper, &b->branch_tree);
+
/* file_change* */
while (command_buf.len > 0) {
if (!prefixcmp(command_buf.buf, "M "))
@@ -2303,10 +2381,16 @@ static void parse_new_commit(void)
file_change_cr(b, 1);
else if (!prefixcmp(command_buf.buf, "C "))
file_change_cr(b, 0);
- else if (!prefixcmp(command_buf.buf, "N "))
- note_change_n(b);
- else if (!strcmp("deleteall", command_buf.buf))
+ else if (!prefixcmp(command_buf.buf, "N ")) {
+ if (!notes)
+ notes = new_notes_tree(b);
+ note_change_n(b, notes);
+ }
+ else if (!strcmp("deleteall", command_buf.buf)) {
+ if (notes)
+ delete_notes_tree(b, ¬es);
file_change_deleteall(b);
+ }
else {
unread_command_buf = 1;
break;
@@ -2316,6 +2400,8 @@ static void parse_new_commit(void)
}
/* build the tree and the commit */
+ if (notes)
+ for_each_note(notes, write_notes_set_helper, &b->branch_tree);
store_tree(&b->branch_tree);
hashcpy(b->branch_tree.versions[0].sha1,
b->branch_tree.versions[1].sha1);
diff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh
index 2f5c323..50a2b8a 100755
--- a/t/t9300-fast-import.sh
+++ b/t/t9300-fast-import.sh
@@ -1092,9 +1092,12 @@ test_expect_success 'P: fail on blob mark in gitlink' '
### series Q (notes)
###
-note1_data="Note for the first commit"
-note2_data="Note for the second commit"
-note3_data="Note for the third commit"
+note1_data="The first note for the first commit"
+note2_data="The first note for the second commit"
+note3_data="The first note for the third commit"
+note1b_data="The second note for the first commit"
+note1c_data="The third note for the first commit"
+note2b_data="The second note for the second commit"
test_tick
cat >input <<INPUT_END
@@ -1169,7 +1172,45 @@ data <<EOF
$note3_data
EOF
+commit refs/notes/foobar
+mark :10
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes (:10)
+COMMIT
+
+N inline :3
+data <<EOF
+$note1b_data
+EOF
+
+commit refs/notes/foobar2
+mark :11
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes (:11)
+COMMIT
+
+N inline :3
+data <<EOF
+$note1c_data
+EOF
+
+commit refs/notes/foobar
+mark :12
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+notes (:12)
+COMMIT
+
+deleteall
+N inline :5
+data <<EOF
+$note2b_data
+EOF
+
INPUT_END
+
test_expect_success \
'Q: commit notes' \
'git fast-import <input &&
@@ -1224,8 +1265,8 @@ committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
notes (:9)
EOF
test_expect_success \
- 'Q: verify notes commit' \
- 'git cat-file commit refs/notes/foobar | sed 1d >actual &&
+ 'Q: verify first notes commit' \
+ 'git cat-file commit refs/notes/foobar~2 | sed 1d >actual &&
test_cmp expect actual'
cat >expect.unsorted <<EOF
@@ -1235,24 +1276,113 @@ cat >expect.unsorted <<EOF
EOF
cat expect.unsorted | sort >expect
test_expect_success \
- 'Q: verify notes tree' \
- 'git cat-file -p refs/notes/foobar^{tree} | sed "s/ [0-9a-f]* / /" >actual &&
+ 'Q: verify first notes tree' \
+ 'git cat-file -p refs/notes/foobar~2^{tree} | sed "s/ [0-9a-f]* / /" >actual &&
test_cmp expect actual'
echo "$note1_data" >expect
test_expect_success \
- 'Q: verify note for first commit' \
- 'git cat-file blob refs/notes/foobar:$commit1 >actual && test_cmp expect actual'
+ 'Q: verify first note for first commit' \
+ 'git cat-file blob refs/notes/foobar~2:$commit1 >actual && test_cmp expect actual'
echo "$note2_data" >expect
test_expect_success \
- 'Q: verify note for second commit' \
- 'git cat-file blob refs/notes/foobar:$commit2 >actual && test_cmp expect actual'
+ 'Q: verify first note for second commit' \
+ 'git cat-file blob refs/notes/foobar~2:$commit2 >actual && test_cmp expect actual'
+
+echo "$note3_data" >expect
+test_expect_success \
+ 'Q: verify first note for third commit' \
+ 'git cat-file blob refs/notes/foobar~2:$commit3 >actual && test_cmp expect actual'
+
+cat >expect <<EOF
+parent `git rev-parse --verify refs/notes/foobar~2`
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+notes (:10)
+EOF
+test_expect_success \
+ 'Q: verify second notes commit' \
+ 'git cat-file commit refs/notes/foobar^ | sed 1d >actual &&
+ test_cmp expect actual'
+
+cat >expect.unsorted <<EOF
+100644 blob $commit1
+100644 blob $commit2
+100644 blob $commit3
+EOF
+cat expect.unsorted | sort >expect
+test_expect_success \
+ 'Q: verify second notes tree' \
+ 'git cat-file -p refs/notes/foobar^^{tree} | sed "s/ [0-9a-f]* / /" >actual &&
+ test_cmp expect actual'
+
+echo "$note1b_data" >expect
+test_expect_success \
+ 'Q: verify second note for first commit' \
+ 'git cat-file blob refs/notes/foobar^:$commit1 >actual && test_cmp expect actual'
+
+echo "$note2_data" >expect
+test_expect_success \
+ 'Q: verify first note for second commit' \
+ 'git cat-file blob refs/notes/foobar^:$commit2 >actual && test_cmp expect actual'
echo "$note3_data" >expect
test_expect_success \
- 'Q: verify note for third commit' \
- 'git cat-file blob refs/notes/foobar:$commit3 >actual && test_cmp expect actual'
+ 'Q: verify first note for third commit' \
+ 'git cat-file blob refs/notes/foobar^:$commit3 >actual && test_cmp expect actual'
+
+cat >expect <<EOF
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+notes (:11)
+EOF
+test_expect_success \
+ 'Q: verify third notes commit' \
+ 'git cat-file commit refs/notes/foobar2 | sed 1d >actual &&
+ test_cmp expect actual'
+
+cat >expect.unsorted <<EOF
+100644 blob $commit1
+EOF
+cat expect.unsorted | sort >expect
+test_expect_success \
+ 'Q: verify third notes tree' \
+ 'git cat-file -p refs/notes/foobar2^{tree} | sed "s/ [0-9a-f]* / /" >actual &&
+ test_cmp expect actual'
+
+echo "$note1c_data" >expect
+test_expect_success \
+ 'Q: verify third note for first commit' \
+ 'git cat-file blob refs/notes/foobar2:$commit1 >actual && test_cmp expect actual'
+
+cat >expect <<EOF
+parent `git rev-parse --verify refs/notes/foobar^`
+author $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+
+notes (:12)
+EOF
+test_expect_success \
+ 'Q: verify fourth notes commit' \
+ 'git cat-file commit refs/notes/foobar | sed 1d >actual &&
+ test_cmp expect actual'
+
+cat >expect.unsorted <<EOF
+100644 blob $commit2
+EOF
+cat expect.unsorted | sort >expect
+test_expect_success \
+ 'Q: verify fourth notes tree' \
+ 'git cat-file -p refs/notes/foobar^{tree} | sed "s/ [0-9a-f]* / /" >actual &&
+ test_cmp expect actual'
+
+echo "$note2b_data" >expect
+test_expect_success \
+ 'Q: verify second note for second commit' \
+ 'git cat-file blob refs/notes/foobar:$commit2 >actual && test_cmp expect actual'
###
### series R (feature and option)
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 17/22] Notes API: add_note(): Add note objects to the internal notes tree structure
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 11 +++++++++++
notes.h | 4 ++++
2 files changed, 15 insertions(+), 0 deletions(-)
diff --git a/notes.c b/notes.c
index f2bacbb..49a3e86 100644
--- a/notes.c
+++ b/notes.c
@@ -366,6 +366,17 @@ void init_notes(const char *notes_ref, int flags)
load_subtree(&root_tree, &root_node, 0);
}
+void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1)
+{
+ struct leaf_node *l;
+
+ assert(initialized);
+ l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
+ hashcpy(l->key_sha1, object_sha1);
+ hashcpy(l->val_sha1, note_sha1);
+ note_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE);
+}
+
static unsigned char *lookup_notes(const unsigned char *object_sha1)
{
struct leaf_node *found = note_tree_find(&root_node, 0, object_sha1);
diff --git a/notes.h b/notes.h
index 6b52799..5f22852 100644
--- a/notes.h
+++ b/notes.h
@@ -21,6 +21,10 @@
*/
void init_notes(const char *notes_ref, int flags);
+/* Add the given note object to the internal notes tree structure */
+void add_note(const unsigned char *object_sha1,
+ const unsigned char *note_sha1);
+
/* Free (and de-initialize) the internal notes tree structure */
void free_notes(void);
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 15/22] Notes API: get_commit_notes() -> format_note() + remove the commit restriction
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
There is really no reason why only commit objects can be annotated. By
changing the struct commit parameter to get_commit_notes() into a sha1 we
gain the ability to annotate any object type. To reflect this in the function
naming as well, we rename get_commit_notes() to format_note().
This patch also fixes comments and variable names throughout notes.c as a
consequence of the removal of the unnecessary 'commit' restriction.
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 33 ++++++++++++++++-----------------
notes.h | 11 ++++++++++-
pretty.c | 8 ++++----
3 files changed, 30 insertions(+), 22 deletions(-)
diff --git a/notes.c b/notes.c
index 50a4672..0f7082f 100644
--- a/notes.c
+++ b/notes.c
@@ -1,5 +1,4 @@
#include "cache.h"
-#include "commit.h"
#include "notes.h"
#include "refs.h"
#include "utf8.h"
@@ -25,10 +24,10 @@ struct int_node {
/*
* 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
+ * As a note entry, the key is the SHA1 of the referenced object, 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
+ * referenced object, 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.
*/
@@ -211,7 +210,7 @@ static void note_tree_insert(struct int_node *tree, unsigned char n,
if (concatenate_notes(l->val_sha1,
entry->val_sha1))
die("failed to concatenate note %s "
- "into note %s for commit %s",
+ "into note %s for object %s",
sha1_to_hex(entry->val_sha1),
sha1_to_hex(l->val_sha1),
sha1_to_hex(l->key_sha1));
@@ -299,7 +298,7 @@ static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,
static void load_subtree(struct leaf_node *subtree, struct int_node *node,
unsigned int n)
{
- unsigned char commit_sha1[20];
+ unsigned char object_sha1[20];
unsigned int prefix_len;
void *buf;
struct tree_desc desc;
@@ -312,23 +311,23 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
prefix_len = subtree->key_sha1[19];
assert(prefix_len * 2 >= n);
- memcpy(commit_sha1, subtree->key_sha1, prefix_len);
+ memcpy(object_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);
+ object_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 object SHA1 is complete (len == 20), assume note object
+ * If object 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->key_sha1, object_sha1);
hashcpy(l->val_sha1, entry.sha1);
if (len < 20) {
l->key_sha1[19] = (unsigned char) len;
@@ -342,12 +341,12 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
static void initialize_notes(const char *notes_ref_name)
{
- unsigned char sha1[20], commit_sha1[20];
+ unsigned char sha1[20], object_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))
+ if (!notes_ref_name || read_ref(notes_ref_name, object_sha1) ||
+ get_tree_entry(object_sha1, "", sha1, &mode))
return;
hashclr(root_tree.key_sha1);
@@ -355,9 +354,9 @@ static void initialize_notes(const char *notes_ref_name)
load_subtree(&root_tree, &root_node, 0);
}
-static unsigned char *lookup_notes(const unsigned char *commit_sha1)
+static unsigned char *lookup_notes(const unsigned char *object_sha1)
{
- struct leaf_node *found = note_tree_find(&root_node, 0, commit_sha1);
+ struct leaf_node *found = note_tree_find(&root_node, 0, object_sha1);
if (found)
return found->val_sha1;
return NULL;
@@ -370,7 +369,7 @@ void free_notes(void)
initialized = 0;
}
-void get_commit_notes(const struct commit *commit, struct strbuf *sb,
+void format_note(const unsigned char *object_sha1, struct strbuf *sb,
const char *output_encoding, int flags)
{
static const char utf8[] = "utf-8";
@@ -389,7 +388,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
initialized = 1;
}
- sha1 = lookup_notes(commit->object.sha1);
+ sha1 = lookup_notes(object_sha1);
if (!sha1)
return;
diff --git a/notes.h b/notes.h
index a1421e3..d745ed1 100644
--- a/notes.h
+++ b/notes.h
@@ -4,10 +4,19 @@
/* Free (and de-initialize) the internal notes tree structure */
void free_notes(void);
+/* Flags controlling how notes are formatted */
#define NOTES_SHOW_HEADER 1
#define NOTES_INDENT 2
-void get_commit_notes(const struct commit *commit, struct strbuf *sb,
+/*
+ * Fill the given strbuf with the notes associated with the given object.
+ *
+ * If the internal notes structure is not initialized, it will be auto-
+ * initialized to the default value (see documentation for init_notes() above).
+ *
+ * 'flags' is a bitwise combination of the above formatting flags.
+ */
+void format_note(const unsigned char *object_sha1, struct strbuf *sb,
const char *output_encoding, int flags);
#endif
diff --git a/pretty.c b/pretty.c
index 7f350bb..81791f5 100644
--- a/pretty.c
+++ b/pretty.c
@@ -703,8 +703,8 @@ static size_t format_commit_item(struct strbuf *sb, const char *placeholder,
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);
+ format_note(commit->object.sha1, sb, git_log_output_encoding ?
+ git_log_output_encoding : git_commit_encoding, 0);
return 1;
}
@@ -982,8 +982,8 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,
strbuf_addch(sb, '\n');
if (fmt != CMIT_FMT_ONELINE)
- get_commit_notes(commit, sb, encoding,
- NOTES_SHOW_HEADER | NOTES_INDENT);
+ format_note(commit->object.sha1, sb, encoding,
+ NOTES_SHOW_HEADER | NOTES_INDENT);
free(reencoded);
}
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 16/22] Notes API: init_notes(): Initialize the notes tree from the given notes ref
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
Created by a simple refactoring of initialize_notes().
Also add a new 'flags' parameter, which is a bitwise combination of notes
initialization flags. For now, there is only one flag - NOTES_INIT_EMPTY -
which indicates that the notes tree should not auto-load the contents of
the given (or default) notes ref, but rather should leave the notes tree
initialized to an empty state. This will become useful in the future when
manipulating the notes tree through the notes API.
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 27 ++++++++++++++++-----------
notes.h | 20 ++++++++++++++++++++
2 files changed, 36 insertions(+), 11 deletions(-)
diff --git a/notes.c b/notes.c
index 0f7082f..f2bacbb 100644
--- a/notes.c
+++ b/notes.c
@@ -339,13 +339,25 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
free(buf);
}
-static void initialize_notes(const char *notes_ref_name)
+void init_notes(const char *notes_ref, int flags)
{
unsigned char sha1[20], object_sha1[20];
unsigned mode;
struct leaf_node root_tree;
- if (!notes_ref_name || read_ref(notes_ref_name, object_sha1) ||
+ assert(!initialized);
+ initialized = 1;
+
+ if (!notes_ref) {
+ const char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);
+ if (env)
+ notes_ref = getenv(GIT_NOTES_REF_ENVIRONMENT);
+ else
+ notes_ref = GIT_NOTES_DEFAULT_REF;
+ }
+
+ if (flags & NOTES_INIT_EMPTY || !notes_ref ||
+ read_ref(notes_ref, object_sha1) ||
get_tree_entry(object_sha1, "", sha1, &mode))
return;
@@ -378,15 +390,8 @@ void format_note(const unsigned char *object_sha1, struct strbuf *sb,
unsigned long linelen, msglen;
enum object_type type;
- if (!initialized) {
- const char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);
- if (env)
- notes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);
- else if (!notes_ref_name)
- notes_ref_name = GIT_NOTES_DEFAULT_REF;
- initialize_notes(notes_ref_name);
- initialized = 1;
- }
+ if (!initialized)
+ init_notes(NULL, 0);
sha1 = lookup_notes(object_sha1);
if (!sha1)
diff --git a/notes.h b/notes.h
index d745ed1..6b52799 100644
--- a/notes.h
+++ b/notes.h
@@ -1,6 +1,26 @@
#ifndef NOTES_H
#define NOTES_H
+/*
+ * Flags controlling behaviour of notes tree initialization
+ *
+ * Default behaviour is to initialize the notes tree from the tree object
+ * specified by the given (or default) notes ref.
+ */
+#define NOTES_INIT_EMPTY 1
+
+/*
+ * Initialize internal notes tree structure with the notes tree at the given
+ * ref. If given ref is NULL, the value of the $GIT_NOTES_REF environment
+ * variable is used, and if that is missing, the default notes ref is used
+ * ("refs/notes/commits").
+ *
+ * If you need to re-intialize the internal notes tree structure (e.g. loading
+ * from a different notes ref), please first de-initialize the current notes
+ * tree by calling free_notes().
+ */
+void init_notes(const char *notes_ref, int flags);
+
/* Free (and de-initialize) the internal notes tree structure */
void free_notes(void);
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 11/22] Teach the notes lookup code to parse notes trees with various fanout schemes
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam, Johannes Schindelin
In-Reply-To: <1255083738-23263-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.
Cc: Johannes Schindelin <johannes.schindelin@gmx.de>
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 a5d888d..210c4b2 100644
--- a/notes.c
+++ b/notes.c
@@ -6,109 +6,288 @@
#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 free_notes(void)
{
- 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;
}
@@ -127,7 +306,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;
}
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 14/22] Add selftests verifying concatenation of multiple notes for the same commit
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
Also verify that multiple references to the _same_ note blob are _not_
concatenated.
Signed-off-by: Johan Herland <johan@herland.net>
---
t/t3303-notes-subtrees.sh | 84 +++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 84 insertions(+), 0 deletions(-)
diff --git a/t/t3303-notes-subtrees.sh b/t/t3303-notes-subtrees.sh
index cbb9d35..edc4bc8 100755
--- a/t/t3303-notes-subtrees.sh
+++ b/t/t3303-notes-subtrees.sh
@@ -101,4 +101,88 @@ 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_same_notes () {
+ (
+ start_note_commit &&
+ nr=$number_of_commits &&
+ git rev-list refs/heads/master |
+ while read sha1; do
+ first_note_path=$(echo "$sha1" | sed "$1")
+ second_note_path=$(echo "$sha1" | sed "$2")
+ cat <<INPUT_END &&
+M 100644 inline $second_note_path
+data <<EOF
+note for commit #$nr
+EOF
+
+M 100644 inline $first_note_path
+data <<EOF
+note for commit #$nr
+EOF
+
+INPUT_END
+
+ nr=$(($nr-1))
+ done
+ ) |
+ git fast-import --quiet
+}
+
+test_expect_success 'test same notes in 4/36-fanout and 2/38-fanout' 'test_same_notes "s|^..|&/|" "s|^....|&/|"'
+test_expect_success 'verify same notes in 4/36-fanout and 2/38-fanout' 'verify_notes'
+
+test_expect_success 'test same notes in 2/38-fanout and 2/2/36-fanout' 'test_same_notes "s|^\(..\)\(..\)|\1/\2/|" "s|^..|&/|"'
+test_expect_success 'verify same notes in 2/38-fanout and 2/2/36-fanout' 'verify_notes'
+
+test_expect_success 'test same notes in 4/36-fanout and 2/2/36-fanout' 'test_same_notes "s|^\(..\)\(..\)|\1/\2/|" "s|^....|&/|"'
+test_expect_success 'verify same notes in 4/36-fanout and 2/2/36-fanout' 'verify_notes'
+
+test_concatenated_notes () {
+ (
+ start_note_commit &&
+ nr=$number_of_commits &&
+ git rev-list refs/heads/master |
+ while read sha1; do
+ first_note_path=$(echo "$sha1" | sed "$1")
+ second_note_path=$(echo "$sha1" | sed "$2")
+ cat <<INPUT_END &&
+M 100644 inline $second_note_path
+data <<EOF
+second note for commit #$nr
+EOF
+
+M 100644 inline $first_note_path
+data <<EOF
+first note for commit #$nr
+EOF
+
+INPUT_END
+
+ nr=$(($nr-1))
+ done
+ ) |
+ git fast-import --quiet
+}
+
+verify_concatenated_notes () {
+ git log | grep "^ " > output &&
+ i=$number_of_commits &&
+ while [ $i -gt 0 ]; do
+ echo " commit #$i" &&
+ echo " first note for commit #$i" &&
+ echo " second note for commit #$i" &&
+ i=$(($i-1));
+ done > expect &&
+ test_cmp expect output
+}
+
+test_expect_success 'test notes in 4/36-fanout concatenated with 2/38-fanout' 'test_concatenated_notes "s|^..|&/|" "s|^....|&/|"'
+test_expect_success 'verify notes in 4/36-fanout concatenated with 2/38-fanout' 'verify_concatenated_notes'
+
+test_expect_success 'test notes in 2/38-fanout concatenated with 2/2/36-fanout' 'test_concatenated_notes "s|^\(..\)\(..\)|\1/\2/|" "s|^..|&/|"'
+test_expect_success 'verify notes in 2/38-fanout concatenated with 2/2/36-fanout' 'verify_concatenated_notes'
+
+test_expect_success 'test notes in 4/36-fanout concatenated with 2/2/36-fanout' 'test_concatenated_notes "s|^\(..\)\(..\)|\1/\2/|" "s|^....|&/|"'
+test_expect_success 'verify notes in 4/36-fanout concatenated with 2/2/36-fanout' 'verify_concatenated_notes'
+
test_done
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 12/22] Add selftests verifying that we can parse notes trees with various fanouts
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
Signed-off-by: Johan Herland <johan@herland.net>
---
t/t3303-notes-subtrees.sh | 104 +++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 104 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..cbb9d35
--- /dev/null
+++ b/t/t3303-notes-subtrees.sh
@@ -0,0 +1,104 @@
+#!/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_done
--
1.6.4.304.g1365c.dirty
^ permalink raw reply related
* [RFC/PATCHv7 13/22] Refactor notes code to concatenate multiple notes annotating the same object
From: Johan Herland @ 2009-10-09 10:22 UTC (permalink / raw)
To: git
Cc: gitster, johan, Johannes.Schindelin, trast, tavestbo, git,
chriscool, spearce, sam
In-Reply-To: <1255083738-23263-1-git-send-email-johan@herland.net>
Currently, having multiple notes referring to the same commit from various
locations in the notes tree is strongly discouraged, since only one of those
notes will be parsed and shown.
This patch teaches the notes code to _concatenate_ multiple notes that
annotate the same commit. Notes are concatenated by creating a new blob
object containing the concatenation of the notes in question, and
replacing them with the concatenated note in the internal notes tree
structure.
Getting the concatenation right requires being more proactive in unpacking
subtree entries in the internal notes tree structure, so that we don't return
a note prematurely (i.e. before having found all other notes that annotate
the same object). As such, this patch may incur a small performance penalty.
Suggested-by: Sam Vilain <sam@vilain.net>
Re-suggested-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Johan Herland <johan@herland.net>
---
notes.c | 243 +++++++++++++++++++++++++++++++++++++++++---------------------
1 files changed, 161 insertions(+), 82 deletions(-)
diff --git a/notes.c b/notes.c
index 210c4b2..50a4672 100644
--- a/notes.c
+++ b/notes.c
@@ -59,115 +59,196 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
unsigned int n);
/*
- * To find a leaf_node:
+ * Search the tree until the appropriate location for the given key is found:
* 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)
+ * 2. 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.
+ * 3. Use the nth nibble of the key as an index into a:
+ * - If a[n] is an int_node, recurse from #2 into that node and increment n
* - 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.
+ * - Otherwise, we have found one of the following:
+ * - a subtree entry which does not match the key
+ * - a note entry which may or may not match the key
+ * - an unused leaf node (NULL)
+ * In any case, set *tree and *n, and return pointer to the tree location.
*/
-static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
- const unsigned char *key_sha1)
+static void **note_tree_search(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];
+ unsigned char i;
+ void *p = (*tree)->a[0];
+ if (GET_PTR_TYPE(p) == 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[0] = NULL;
+ load_subtree(l, *tree, *n);
+ free(l);
+ return note_tree_search(tree, n, key_sha1);
+ }
+ }
+
+ i = GET_NIBBLE(*n, key_sha1);
+ 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;
+ *tree = CLR_PTR_TYPE(p);
+ (*n)++;
+ return note_tree_search(tree, n, key_sha1);
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);
+ (*tree)->a[i] = NULL;
+ load_subtree(l, *tree, *n);
free(l);
- return note_tree_find(tree, n, key_sha1);
+ return note_tree_search(tree, n, key_sha1);
}
- break;
- case PTR_TYPE_NULL:
+ /* fall through */
default:
- assert(!p);
- break;
+ return &((*tree)->a[i]);
}
+}
- /*
- * 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);
+/*
+ * To find a leaf_node:
+ * Search to the tree location appropriate for the given key:
+ * If a note entry with matching key, return the note entry, else return NULL.
+ */
+static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
+ const unsigned char *key_sha1)
+{
+ void **p = note_tree_search(&tree, &n, key_sha1);
+ if (GET_PTR_TYPE(*p) == PTR_TYPE_NOTE) {
+ struct leaf_node *l = (struct leaf_node *) CLR_PTR_TYPE(*p);
+ if (!hashcmp(key_sha1, l->key_sha1))
+ return l;
}
return NULL;
}
+/* Create a new blob object by concatenating the two given blob objects */
+static int concatenate_notes(unsigned char *cur_sha1,
+ const unsigned char *new_sha1)
+{
+ char *cur_msg, *new_msg, *buf;
+ unsigned long cur_len, new_len, buf_len;
+ enum object_type cur_type, new_type;
+ int ret;
+
+ /* read in both note blob objects */
+ new_msg = read_sha1_file(new_sha1, &new_type, &new_len);
+ if (!new_msg || !new_len || new_type != OBJ_BLOB) {
+ free(new_msg);
+ return 0;
+ }
+ cur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);
+ if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
+ free(cur_msg);
+ free(new_msg);
+ hashcpy(cur_sha1, new_sha1);
+ return 0;
+ }
+
+ /* we will separate the notes by a newline anyway */
+ if (cur_msg[cur_len - 1] == '\n')
+ cur_len--;
+
+ /* concatenate cur_msg and new_msg into buf */
+ buf_len = cur_len + 1 + new_len;
+ buf = (char *) xmalloc(buf_len);
+ memcpy(buf, cur_msg, cur_len);
+ buf[cur_len] = '\n';
+ memcpy(buf + cur_len + 1, new_msg, new_len);
+
+ free(cur_msg);
+ free(new_msg);
+
+ /* create a new blob object from buf */
+ ret = write_sha1_file(buf, buf_len, "blob", cur_sha1);
+ free(buf);
+ return ret;
+}
+
/*
* 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].
+ * Search to the tree location appropriate for the given leaf_node's key:
+ * - If location is unused (NULL), store the tweaked pointer directly there
+ * - If location holds a note entry that matches the note-to-be-inserted, then
+ * concatenate the two notes.
+ * - If location holds a note entry that matches the subtree-to-be-inserted,
+ * then unpack the subtree-to-be-inserted into the location.
+ * - If location holds a matching subtree entry, unpack the subtree at that
+ * location, and restart the insert operation from that level.
+ * - Else, create a new int_node, holding both the node-at-location and the
+ * node-to-be-inserted, and store the new int_node into the location.
*/
-static int note_tree_insert(struct int_node *tree, unsigned char n,
- const struct leaf_node *entry, unsigned char type)
+static void note_tree_insert(struct int_node *tree, unsigned char n,
+ struct leaf_node *entry, unsigned char type)
{
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)) {
+ struct leaf_node *l;
+ void **p = note_tree_search(&tree, &n, entry->key_sha1);
+
+ assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
+ l = (struct leaf_node *) CLR_PTR_TYPE(*p);
+ 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;
+ assert(!*p);
+ *p = SET_PTR_TYPE(entry, type);
+ return;
+ case PTR_TYPE_NOTE:
+ switch (type) {
+ case PTR_TYPE_NOTE:
+ if (!hashcmp(l->key_sha1, entry->key_sha1)) {
+ /* skip concatenation if l == entry */
+ if (!hashcmp(l->val_sha1, entry->val_sha1))
+ return;
+
+ if (concatenate_notes(l->val_sha1,
+ entry->val_sha1))
+ die("failed to concatenate note %s "
+ "into note %s for commit %s",
+ sha1_to_hex(entry->val_sha1),
+ sha1_to_hex(l->val_sha1),
+ sha1_to_hex(l->key_sha1));
+ free(entry);
+ return;
+ }
+ break;
+ case PTR_TYPE_SUBTREE:
+ if (!SUBTREE_SHA1_PREFIXCMP(l->key_sha1,
+ entry->key_sha1)) {
+ /* unpack 'entry' */
+ load_subtree(entry, tree, n);
+ free(entry);
+ return;
+ }
+ break;
+ }
+ break;
+ case PTR_TYPE_SUBTREE:
+ if (!SUBTREE_SHA1_PREFIXCMP(entry->key_sha1, l->key_sha1)) {
+ /* unpack 'l' and restart insert */
+ *p = NULL;
+ load_subtree(l, tree, n);
+ free(l);
+ note_tree_insert(tree, n, entry, type);
+ return;
}
- tree->a[i] = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
- return note_tree_insert(new_node, n + 1, entry, type);
+ break;
}
+
+ /* non-matching leaf_node */
+ assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||
+ GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);
+ new_node = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
+ note_tree_insert(new_node, n + 1, l, GET_PTR_TYPE(*p));
+ *p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
+ note_tree_insert(new_node, n + 1, entry, type);
}
/* Free the entire notes data contained in the given tree */
@@ -220,7 +301,6 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
{
unsigned char commit_sha1[20];
unsigned int prefix_len;
- int status;
void *buf;
struct tree_desc desc;
struct name_entry entry;
@@ -254,8 +334,7 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
l->key_sha1[19] = (unsigned char) len;
type = PTR_TYPE_SUBTREE;
}
- status = note_tree_insert(node, n, l, type);
- assert(!status);
+ note_tree_insert(node, n, l, type);
}
}
free(buf);
--
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