* Re: [PATCH] Allow INSTALL, bindir, mandir to be set in main Makefile
From: Junio C Hamano @ 2006-06-29 18:23 UTC (permalink / raw)
To: Jakub Narebski; +Cc: git
In-Reply-To: <200606291835.53788.jnareb@gmail.com>
Jakub Narebski <jnareb@gmail.com> writes:
> Part of autoconf series, but independent.
I'd like to take something like this, independently from
"optionally managing config.mak with autoconf" series.
> Should probably be split into two patches:
> * first with export + '?='
> * second renaming man1 and man7 to man1dir and man7dir
And I think it is probably a good idea to somehow keep people's
configurations that have been overriding man1 and man7 if
possible. Otherwise things would regress for them.
^ permalink raw reply
* Re: Improved three-way blob merging code
From: Davide Libenzi @ 2006-06-29 18:21 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0606282157210.12404@g5.osdl.org>
On Wed, 28 Jun 2006, Linus Torvalds wrote:
> It would be lovely if libxdiff did a 3-way merge on its own, but this
> basically approximates it within that three_way_filemerge() function
> using external functionality.
This is my todo-list, that unfortunately is pretty crowded nowadays. I'll
come graveling you main window once I have it ;)
- Davide
^ permalink raw reply
* Re: xdiff: generate "anti-diffs" aka what is common to two files
From: Davide Libenzi @ 2006-06-29 18:18 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0606282149060.12404@g5.osdl.org>
On Wed, 28 Jun 2006, Linus Torvalds wrote:
> Davide, I say it's a "fairly trivial patch", but quite frankly, I'm
> winging it. I'm not that comfortable with the libxdiff internal workings,
> so while this seems to work for me and make sense, can you please take a
> quick look.
Looks fine to me.
- Davide
^ permalink raw reply
* Re: [RFC] git --trace: trace command execution
From: Jakub Narebski @ 2006-06-29 18:06 UTC (permalink / raw)
To: git
In-Reply-To: <7v3bdtv4h3.fsf@assigned-by-dhcp.cox.net>
Junio C Hamano wrote:
> By the way "git cat-file -p" or "git verify-tag -v" might be
> more pleasant to view a tag since they make the tagger timestamp
> human readable.
Interesting, -p makes tagger timestamp human readable, but not author or
commiter:
$ git cat-file -p `cat .git/refs/tags/v1.4.0`
tagger Junio C Hamano <junkio@cox.net> Sat Jun 10 12:43:37 2006 -0700
$ git cat-file -p `cat .git/refs/heads/origin`
author Johannes Schindelin <Johannes.Schindelin@gmx.de> 1151491527 +0200
committer Junio C Hamano <junkio@cox.net> 1151492136 -0700
Is it intended, or a bug/missing feature (git 1.4.0)?
--
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
^ permalink raw reply
* Re: [RFC] Cache negative delta pairs
From: Jeff King @ 2006-06-29 18:07 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: git
In-Reply-To: <Pine.LNX.4.64.0606291154510.1213@localhost.localdomain>
On Thu, Jun 29, 2006 at 12:39:31PM -0400, Nicolas Pitre wrote:
> You do that lookup for every delta match attempt. Instead it could be
> done once for the whole window attempt, potentially reducing the cache
> size by a factor of 20, and it might be faster too.
I'm not convinced this will provide good cache hit characteristics, and
I'm not convinced it's semantically correct (see my other mail).
> You could simply recreate the cache on each run. Or just keep a bitmap
Yes, that would probably work and would be quite easy to do with the
existing code.
> First, I think it should be ignored (but still created) when
> --no-reuse-delta is passed. Then, it should not be created (but still
> looked up if it exists and --no-reuse-delta is not provided) when the
> pack index file is also not created. I don't think it is worth making
> this further configurable, and given the suggested strategy above the
> cache should remain fairly small.
Those suggestions make sense to me.
-Peff
^ permalink raw reply
* Re: [RFC] Cache negative delta pairs
From: Jeff King @ 2006-06-29 18:00 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.64.0606291053280.1213@localhost.localdomain>
On Thu, Jun 29, 2006 at 11:42:14AM -0400, Nicolas Pitre wrote:
> So the negative cache should not be O(N^2) either. It just has to be
> O(N*window).
Yes, unless we use the cache information to change the window (but I
don't think that's worth it, unless our window heuristics are bad).
The implementation I posted should already grow to O(N*window), since it
only saves what we try (and fail at).
> My past experiments showed that the best window size for compression is
> a bit larger than the current default of 10. It was rather around 15
> for the kernel repository, with higher values than 15 not providing
> significant improvements anymore. But that is clearly a function of the
> repository nature (the average number of revisions for each file). But
> the window size is directly connected to the computational cost.
Increasing the window, of course, has virtually no speed impact on later
repacks with the cache in effect. Packing with a window of 15 drops my
linux-2.6 pack to 108M from 122M. That helps offset the cache size
(though of course it takes longer on the initial pack).
> This is way suboptimal. First there is no reason for the cache to ever
> grow to N^2. At worst it should be N*10 where 10 is the current window
> size.
I assumed the window would change over time (though our total is still
likely to hang around N*10 rather than N^2).
> none of the objects found in a given window. Therefore we only have to
> compute a hash for the object names found in that window and store that
> in the cache. So the cache entries would then be a pair of sha1: first
> the sha1 of the victim object, and the sha1 of all sha1 names for the
> objects against which the victim object was found not to delta well
> against.
This will fail to hit the cache anytime the window changes. How often
does the window change? In my test case, I would think anytime I added a
bunch of new photos, it would be likely that one of them would make it
into the window, thus invalidating the cache entry and forcing me to try
against every object in the window (even though I've already tried
9/10).
Also, is it true to say "if this object did not delta against this
window, it will never delta?" What about interactions with the depth
parameter?
> So given my GIT repository such a cache would be 7610 * 40 = 304400
> bytes if we stick to the full 40 bytes of sha1 to hash bad combinations.
Keep in mind that it will grow every time the window changes.
-Peff
^ permalink raw reply
* [PATCH] autoconf: Set mandir in config.mak.in and export variables not in Makefile
From: Jakub Narebski @ 2006-06-29 17:47 UTC (permalink / raw)
To: git
In-Reply-To: <200606291835.53788.jnareb@gmail.com>
This patch with the previous "[PATCH] Allow INSTALL, bindir, mandir to
be set in main Makefile" patch allows ./configure script to set where
manpages will be installed using --mandir=DIR (./configure defaults to
PREFIX/man).
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
Uwe Zeisberger wrote:
> autoconf does to much things, even with that little configure.ac.
> (But I agree, it's much better than automake :-)
>
> E.g.
>
> ./configure --prefix=$HOME/usr --mandir=$HOME/usr/share/man
>
> is supported by the configure script, but the manpages are installed
> in $HOME/usr/man all the same.
>
> BTW: Even if I specify mandir=... in config.mak, it is not respected,
> because only the toplevel Makefile includes config.mak. (I didn't
> test it, but I think I could export mandir in config.mak ...)
This patch and previous one adressess this.
config.mak.in | 6 ++++++
1 files changed, 6 insertions(+), 0 deletions(-)
diff --git a/config.mak.in b/config.mak.in
index 82d80e2..82c9781 100644
--- a/config.mak.in
+++ b/config.mak.in
@@ -8,5 +8,11 @@ #gitexecdir = @libexecdir@/git-core/
template_dir = @datadir@/git-core/templates/
GIT_PYTHON_DIR = @datadir@/git-core/python
+mandir=@mandir@
+
srcdir = @srcdir@
VPATH = @srcdir@
+
+export exec_prefix mandir
+export srcdir VPATH
+
--
1.4.0
^ permalink raw reply related
* Re: Improved three-way blob merging code
From: Linus Torvalds @ 2006-06-29 17:45 UTC (permalink / raw)
To: Alex Riesen; +Cc: Junio C Hamano, Git Mailing List, Davide Libenzi
In-Reply-To: <81b0412b0606290043s15e19b9fl853627e815f009ff@mail.gmail.com>
On Thu, 29 Jun 2006, Alex Riesen wrote:
>
> On 6/29/06, Linus Torvalds <torvalds@osdl.org> wrote:
> > +static void *three_way_filemerge(mmfile_t *base, mmfile_t *our, mmfile_t
> > *their, unsigned long *size)
> > +{
> ...
> > + if (t1 && t2 && t3) {
> > + int code = run_command("merge", t2, t1, t3, NULL);
>
> This does not use the labels of merge(1) and the merged file will contain
> the names of temporary files at conflict places, which is very confusing if
> you happen to loose context while doing a merge with lots of conflicts.
Yes.
I was really really _really_ just hoping that I could do the nasty core
code that others might feel uncomfortable with, and get it working from a
_technical_ level well enough that others (hint hint) would decide that
they can fix up the details.
Getting the first version working is often the hardest. When you reach the
point of "it works, but I want to extend it to do X", you've usually
already gotten pretty far.
Anyway, all of this was really just preparatory work to show what
git-merge-tree does. A few more improvements to git-merge-tree, and
hopefully it can start being useful - perhaps not initially for actually
merging, but for doing a tree-level three-way diff between two branches.
In other words, my current goal is really do make it possible to get good
diffs out of git from two branches that aren't directly related. You and
Dscho seem to be doing well on the git-merge-recursive front, so my
personal goal is actually to be able to get a saner diff than what
git diff mine..theirs
gives you.
The above "git diff" is a perfectly fine thing to do, but it's usually not
what you actually _want_. Almost always, what you want a diff between two
branches, what you want is actually the diff after a merge of the
branches, not the raw _current_ differences.
For example, look at our current
Documentation/howto/using-topic-branches.txt
file, and realize that the current scripts it suggests are actually
broken:
To create diffstat and shortlog summaries of changes to include in
a "pleasepull" request to Linus you can use:
$ git-whatchanged -p release ^linus | diffstat -p1
and
$ git-whatchanged release ^linus | git-shortlog
where that "git-whatchanged -p release ^linus | diffstat -p1" won't
actually be what I see when I merge (although it will hopefully be close
enough). Also, there's no indication that the merge will fail when I pull,
something that _would_ be very useful.
IOW, what I'd like git-merge-tree to do is to be able to at a minimum say:
- will a merge succeed cleanly, and if not, show me where the problem
spots are.
- what will the result of the merge look like.
because that's actually what a downstream developer wants to do. He'd just
do
git fetch linus
git show-changes linus..my-branch
which would basically be the preparatory thing for sending me an email
saying "please merge 'my-branch', and you'll see this".
Now, obviously, I think that there's a _lot_ of overlap between doing this
and actually doing the merge itself, so hopefully the things I do will at
least have some things in common and perhaps help you do the proper
recursive merger.
But one thing I was actually hoping to do was to literally be able to do
this without either tree being checked out, exactly so that you can check
the status of a branch that you may not even _be_ on (eg that "my-branch"
in the example above may not even be your current HEAD: you might be on
your development branch when you actually ask me to pull from your stable
branch).
So the "show differences" has a lot in common with "merge them", but there
are literally a few stages missing. One thing missing in just showing
differences is that you can't actually fix up the merge clashes: if you
don't have a checked-out tree, you're not going to be able to do a real
merge. But you can see what a merge would _look_ like, and whether there
are any clashes that you will have to fix..
Linus
^ permalink raw reply
* Re: [RFC] Cache negative delta pairs
From: Nicolas Pitre @ 2006-06-29 16:39 UTC (permalink / raw)
To: Jeff King; +Cc: git
In-Reply-To: <20060629035849.GA30749@coredump.intra.peff.net>
On Wed, 28 Jun 2006, Jeff King wrote:
> >From repack to repack, we end up trying to delta many of the same object
> pairs, which is computationally expensive. This patch makes a
> persistent cache, $GIT_DIR/delta-cache, which contains pairs of sha1
> hashes (the presence of a pair indicates that it's not worth trying to
> delta those two objects).
I think this could be done differently to be even more space efficient
as I suggested earlier.
> Here are some of my thoughts:
>
> - speed. The implementation is quite fast. The sha1 pairs are stored
> sorted, and we mmap and binary search them. Certainly the extra time
> spent in lookup is justified by avoiding the delta attempts.
You do that lookup for every delta match attempt. Instead it could be
done once for the whole window attempt, potentially reducing the cache
size by a factor of 20, and it might be faster too.
> - size. The cache is a packed sequence of binary sha1 pairs. I was
> concerned that it would grow too large (obviously for n blobs you can
> end up with n^2/2 entries), but it doesn't seem unreasonable for most
> repos (either you don't have a lot of files, or if you do, they delta
> reasonably well). My test repo's cache is only 144K. The git cache is
> about 2.7M. The linux-2.6 cache is 22M.
See my previous email for comments about this.
> Theoretically, I could bound the cache size and boot old entries.
> However, that means storing age information, which increases the
> required size. I think keeping it simple is best.
You could simply recreate the cache on each run. Or just keep a bitmap
of referenced cache entries, and a list of new entries. At the end if
the new entry list is empty and the bitmap is all set (or clear) then
you just keep the current cache. ONce, say, more than 10% of cache
entries are not used anymore then you regenerate the cache. But since
you need to regenerate it when new entries are added then the 10% unused
entry criteria might not be used that often anyway, unless packs shrink
with time which might not be the case really often.
> - correctness. Currently the code uses the output of try_delta for
> negative caching. Should the cache checking be moved inside try_delta
> instead? This would give more control over which reasons to mark a
> delta negative (I believe right now hitting the depth limit will
> cause a negative mark; we should perhaps only do so if the content
> itself makes the delta unpalatable).
Like I said earlier I think this should be moved up a bit i.e. outside
the delta loop. In find_deltas() right before the ...
j = window;
while (--j > 0) {
loop, just insert another loop that compute the sha1 of the current
target object and window:
SHA1_Init(&c);
j = window;
while (j-- > 0) { /* postdec include the current object as well */
unsigned int other_idx = idx + j;
struct unpacked *m;
if (other_idx >= window)
other_idx -= window;
m = array + other_idx;
if (!m->entry)
break;
SHA1_Update(&c, m->entry.sha1, 20);
}
SHA1_Final(negative_delta_hash, &c);
Then you can skip over the whole of the delta loop right away if that
negative_delta_hash matches one entry in the cache since you already
know that this object with this window doesn't produce any delta result.
Otherwise, after the delta loop has proceeded, if there is no delta
found then you can add negative_delta_hash to the cache.
> - optionalness. Currently the delta-cache is always used. Since it is a
> space-time tradeoff, maybe it should be optional (it will have
> negligible performance and horrible size impact on a repo that
> consists of many very small but unrelated objects). Possible methods
> include:
> - enable cache saves only if .git/delta-cache is present; turn it
> on initially with 'touch .git/delta-cache'
> - config variable
First, I think it should be ignored (but still created) when
--no-reuse-delta is passed. Then, it should not be created (but still
looked up if it exists and --no-reuse-delta is not provided) when the
pack index file is also not created. I don't think it is worth making
this further configurable, and given the suggested strategy above the
cache should remain fairly small.
Nicolas
^ permalink raw reply
* [PATCH] Allow INSTALL, bindir, mandir to be set in main Makefile
From: Jakub Narebski @ 2006-06-29 16:35 UTC (permalink / raw)
To: git
In-Reply-To: <200606291704.27677.jnareb@gmail.com>
Makefiles in subdirectories now use existing value of INSTALL, bindir,
mandir if it is set, allowing those to be set in main Makefile or in
config.mak. Main Makefile exports variables which it sets.
Renames man1 and man7 variables to man1dir and man7dir, according to
"Makefile Conventions: Variables for Installation Directories" in
make.info of GNU Make. Renames bin to bindir (unused, perhaps to be
removed).
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
Part of autoconf series, but independent.
Should probably be split into two patches:
* first with export + '?='
* second renaming man1 and man7 to man1dir and man7dir
Documentation/Makefile | 14 +++++++-------
Makefile | 2 ++
contrib/emacs/Makefile | 4 ++--
contrib/git-svn/Makefile | 8 ++++----
4 files changed, 15 insertions(+), 13 deletions(-)
diff --git a/Documentation/Makefile b/Documentation/Makefile
index 2b0efe7..cc83610 100644
--- a/Documentation/Makefile
+++ b/Documentation/Makefile
@@ -25,10 +25,10 @@ DOC_MAN1=$(patsubst %.txt,%.1,$(MAN1_TXT
DOC_MAN7=$(patsubst %.txt,%.7,$(MAN7_TXT))
prefix?=$(HOME)
-bin=$(prefix)/bin
-mandir=$(prefix)/man
-man1=$(mandir)/man1
-man7=$(mandir)/man7
+bindir?=$(prefix)/bin
+mandir?=$(prefix)/man
+man1dir=$(mandir)/man1
+man7dir=$(mandir)/man7
# DESTDIR=
INSTALL?=install
@@ -52,9 +52,9 @@ man1: $(DOC_MAN1)
man7: $(DOC_MAN7)
install: man
- $(INSTALL) -d -m755 $(DESTDIR)$(man1) $(DESTDIR)$(man7)
- $(INSTALL) $(DOC_MAN1) $(DESTDIR)$(man1)
- $(INSTALL) $(DOC_MAN7) $(DESTDIR)$(man7)
+ $(INSTALL) -d -m755 $(DESTDIR)$(man1dir) $(DESTDIR)$(man7dir)
+ $(INSTALL) $(DOC_MAN1) $(DESTDIR)$(man1dir)
+ $(INSTALL) $(DOC_MAN7) $(DESTDIR)$(man7dir)
#
diff --git a/Makefile b/Makefile
index cde619c..b8fe669 100644
--- a/Makefile
+++ b/Makefile
@@ -100,6 +100,8 @@ template_dir = $(prefix)/share/git-core/
GIT_PYTHON_DIR = $(prefix)/share/git-core/python
# DESTDIR=
+export prefix bindir gitexecdir template_dir GIT_PYTHON_DIR
+
CC = gcc
AR = ar
TAR = tar
diff --git a/contrib/emacs/Makefile b/contrib/emacs/Makefile
index d3619db..350846d 100644
--- a/contrib/emacs/Makefile
+++ b/contrib/emacs/Makefile
@@ -3,9 +3,9 @@ ## Build and install stuff
EMACS = emacs
ELC = git.elc vc-git.elc
-INSTALL = install
+INSTALL ?= install
INSTALL_ELC = $(INSTALL) -m 644
-prefix = $(HOME)
+prefix ?= $(HOME)
emacsdir = $(prefix)/share/emacs/site-lisp
all: $(ELC)
diff --git a/contrib/git-svn/Makefile b/contrib/git-svn/Makefile
index 7c20946..8cac688 100644
--- a/contrib/git-svn/Makefile
+++ b/contrib/git-svn/Makefile
@@ -1,9 +1,9 @@
all: git-svn
prefix?=$(HOME)
-bindir=$(prefix)/bin
-mandir=$(prefix)/man
-man1=$(mandir)/man1
+bindir?=$(prefix)/bin
+mandir?=$(prefix)/man
+man1dir=$(mandir)/man1
INSTALL?=install
doc_conf=../../Documentation/asciidoc.conf
-include ../../config.mak
@@ -17,7 +17,7 @@ install: all
$(INSTALL) git-svn $(DESTDIR)$(bindir)
install-doc: doc
- $(INSTALL) git-svn.1 $(DESTDIR)$(man1)
+ $(INSTALL) git-svn.1 $(DESTDIR)$(man1dir)
doc: git-svn.1
git-svn.1 : git-svn.xml
--
1.4.0
^ permalink raw reply related
* Re: [RFC] Cache negative delta pairs
From: Nicolas Pitre @ 2006-06-29 16:35 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Jeff King, git
In-Reply-To: <Pine.LNX.4.64.0606291053280.1213@localhost.localdomain>
On Thu, 29 Jun 2006, Nicolas Pitre wrote:
> And this can be pushed even further by just including the sha1 of the
> victim object inside the list of objects therefore computing a hash of
> all objects (the victim and the window) for which no delta results. The
> cache is therefore a list of hash values corresponding to bad
> victim+window combinations.
>
> So given my GIT repository such a cache would be 7610 * 40 = 304400
> bytes if we stick to the full 40 bytes of sha1 to hash bad combinations.
Correction: the 40 bytes figure is for _ascii_ representation of sha1
values. The cache doesn't need ascii and therefore this number can be
reduced by half.
Nicolas
^ permalink raw reply
* Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive
From: Johannes Schindelin @ 2006-06-29 16:14 UTC (permalink / raw)
To: Alex Riesen; +Cc: git, Junio C Hamano, Fredrik Kuivinen, Linus Torvalds
In-Reply-To: <81b0412b0606290714v66a32976j531e2077ce6c1d77@mail.gmail.com>
Hi,
On Thu, 29 Jun 2006, Alex Riesen wrote:
> On 6/29/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> >
> > most of this patch is just a "sub-file rename", i.e. moving code
> > literally (sue me, SCO!) from merge-base.c to commit.c.
> >
>
> BTW, you probably want to post merge-recursive.c changes separately.
My point being: it makes no sense to split off get_merge_bases() if nobody
uses it except for git-merge-base.
Ciao,
Dscho
^ permalink raw reply
* Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive
From: Johannes Schindelin @ 2006-06-29 16:14 UTC (permalink / raw)
To: Alex Riesen; +Cc: git, Junio C Hamano, Fredrik Kuivinen, Linus Torvalds
In-Reply-To: <81b0412b0606290712h4960ee8et7ea219d4dd6428b4@mail.gmail.com>
Hi,
On Thu, 29 Jun 2006, Alex Riesen wrote:
> On 6/29/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> > Aargh! Of course this is [PATCH 2/2]. BTW, no signoff, since the whole
> > merge-recursive is not mergeable yet (passes the tests, but we have a
> > small way to go).
>
> How did you get it to pass the tests? Maybe you still have git-merge-recursive
> as default merge strategy?
Darn. Yes.
Sorry for the noise.
Ciao,
Dscho
^ permalink raw reply
* Re: [RFC] Cache negative delta pairs
From: Nicolas Pitre @ 2006-06-29 15:42 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Jeff King, git
In-Reply-To: <7v4py4y7wo.fsf@assigned-by-dhcp.cox.net>
On Wed, 28 Jun 2006, Junio C Hamano wrote:
> Interesting idea. I think this matters more because for a
> repository with many unrelated undeltifiable files, we do the
> computation for objects that results in _no_ delta. For normal
> nearly fully packed repositories, once an object is deltified
> against something else, subsequent repacking of the same set of
> objects (or a superset thereof) will very likely reuse the delta
> without recomputation, so as long as each object _can_ be
> deltified with at least _one_ other object, you should not see
> improvement on them.
>
> So I am curious where the speed-up comes from for "normal" repos
> in your experiments.
My GIT repo currently has 23622 objects and 7610 of them are currently
undeltified. Those objects are of course candidates for delta matching
each time git-repack is run.
> If it turns out that in "normal" repos the
> objects that hit your negative cache are stored undeltified,
> then that suggests that it might be worthwhile to consider using
> a cache of "inherently undeltifiable objects", In other words, a
> negative cache of O(N) entries, instead of O(N^2) entries,
Actually... I'm not so sure. Those objects are not "inherently
undeltifiable". They just happen to not have other objects to easily
delta against in the given set of objects. Think of a file with only
one revision for example. As soon as there is a second revision of that
file added to the set of objects then the former revision would have a
high probability of being deltifiable.
So the negative cache should not be O(N^2) either. It just has to be
O(N*window).
> Another interpretation of your result is that we may be using a
> delta window that is unnecessarily too deep, and your negative
> cache is collecting less optimum candidates that we attempt to
> deltify against "just in case". Can you easily instrument your
> code to see where in the sorted delta candidate list the pairs
> that hit your the negative cache are? That is, in find_deltas()
> function, we have "while (--j > 0)" loop that attempts to delta
> with the entry that is j (modulo window size) entries away from
> the current one, then j-1, j-2, ...; I am interested in the
> distribution of "j" value for the pair "n,m" that hits your
> negative cache for normal repositories, and I am speculating
> that the value would probably be small relative to the delta
> window size.
My past experiments showed that the best window size for compression is
a bit larger than the current default of 10. It was rather around 15
for the kernel repository, with higher values than 15 not providing
significant improvements anymore. But that is clearly a function of the
repository nature (the average number of revisions for each file). But
the window size is directly connected to the computational cost.
> Another idea is to have a cache of "paths at which inherently
> undeltifiable objects live in". For example, we currently do
> not delta OpenOffice documents (*.odt, *.odp, etc) very well.
> If one has a repository that tracks the history of "file.odp",
> we know each revision of "file.odp" would not delta against any
> other version anyway, and could skip attempting to deltify them.
I'm afraid this could lead to bad behavior eventually. Better to just
attempt a delta once, and when an object has not found any delta
base candidate then just write its sha1 and corresponding window to the
cache. This would imply an initial cost to create the cache the first
time, but after that the created cache could be relied upon as hard
information and not just as guess heuristics.
> > - size. The cache is a packed sequence of binary sha1 pairs. I was
> > concerned that it would grow too large (obviously for n blobs you can
> > end up with n^2/2 entries), but it doesn't seem unreasonable for most
> > repos (either you don't have a lot of files, or if you do, they delta
> > reasonably well). My test repo's cache is only 144K. The git cache is
> > about 2.7M. The linux-2.6 cache is 22M.
This is way suboptimal. First there is no reason for the cache to ever
grow to N^2. At worst it should be N*10 where 10 is the current window
size.
Next I think this can be made just N*2. Consider that the criteria for
skipping over delta matching for a given object is the fact
that we already know that such object doesn't delta against
none of the objects found in a given window. Therefore we only have to
compute a hash for the object names found in that window and store that
in the cache. So the cache entries would then be a pair of sha1: first
the sha1 of the victim object, and the sha1 of all sha1 names for the
objects against which the victim object was found not to delta well
against.
And this can be pushed even further by just including the sha1 of the
victim object inside the list of objects therefore computing a hash of
all objects (the victim and the window) for which no delta results. The
cache is therefore a list of hash values corresponding to bad
victim+window combinations.
So given my GIT repository such a cache would be 7610 * 40 = 304400
bytes if we stick to the full 40 bytes of sha1 to hash bad combinations.
Nicolas
^ permalink raw reply
* [PATCH] autoconf: Cleanup generation of config.mak.append by ./configure
From: Jakub Narebski @ 2006-06-29 15:04 UTC (permalink / raw)
To: git
In-Reply-To: <200606291536.18667.jnareb@gmail.com>
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
configure.ac | 7 ++++---
1 files changed, 4 insertions(+), 3 deletions(-)
diff --git a/configure.ac b/configure.ac
index fbd46e2..f48307c 100644
--- a/configure.ac
+++ b/configure.ac
@@ -6,12 +6,14 @@ AC_INIT([git], [1.4.0], [git@vger.kernel
AC_CONFIG_SRCDIR([git.c])
+echo "# config.mak.append. Generated by configure." >> config.mak.append
+
# Definitions of macros
# MY_APPEND_LINE(LINE)
# --------------------
# Append LINE to file config.mak.append
AC_DEFUN([MY_APPEND_LINE],
-[[echo "$1" >> config.mak.append]])# AC_APPEND_LINE
+[[echo "$1" >> config.mak.append]])# MY_APPEND_LINE
# Checks for libraries.
@@ -45,6 +47,5 @@ AC_CHECK_FUNC(setenv,,MY_APPEND_LINE(NO_
# Output files
AC_CONFIG_FILES([config.mak:config.mak.in:config.mak.append],
-[rm -f config.mak.append],
-[echo >> config.mak.append])
+[rm -f config.mak.append])
AC_OUTPUT
--
1.4.0
^ permalink raw reply related
* Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive
From: Alex Riesen @ 2006-06-29 14:14 UTC (permalink / raw)
To: Johannes Schindelin; +Cc: git, Junio C Hamano, Fredrik Kuivinen, Linus Torvalds
In-Reply-To: <Pine.LNX.4.63.0606291517010.29667@wbgn013.biozentrum.uni-wuerzburg.de>
On 6/29/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
>
> most of this patch is just a "sub-file rename", i.e. moving code
> literally (sue me, SCO!) from merge-base.c to commit.c.
>
BTW, you probably want to post merge-recursive.c changes separately.
^ permalink raw reply
* Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive
From: Alex Riesen @ 2006-06-29 14:13 UTC (permalink / raw)
To: Johannes Schindelin; +Cc: git, Junio C Hamano, Fredrik Kuivinen, Linus Torvalds
In-Reply-To: <Pine.LNX.4.63.0606291517010.29667@wbgn013.biozentrum.uni-wuerzburg.de>
On 6/29/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
>
> most of this patch is just a "sub-file rename", i.e. moving code
> literally (sue me, SCO!) from merge-base.c to commit.c.
>
Aah, thanks! Will try it later today.
^ permalink raw reply
* Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive
From: Alex Riesen @ 2006-06-29 14:12 UTC (permalink / raw)
To: Johannes Schindelin; +Cc: git, Junio C Hamano, Fredrik Kuivinen, Linus Torvalds
In-Reply-To: <Pine.LNX.4.63.0606291519440.29667@wbgn013.biozentrum.uni-wuerzburg.de>
On 6/29/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> Aargh! Of course this is [PATCH 2/2]. BTW, no signoff, since the whole
> merge-recursive is not mergeable yet (passes the tests, but we have a
> small way to go).
How did you get it to pass the tests? Maybe you still have git-merge-recursive
as default merge strategy?
^ permalink raw reply
* Re: [PATCH] autoconf: Use autoconf to write installation directories to config.mak
From: Jakub Narebski @ 2006-06-29 13:48 UTC (permalink / raw)
To: git
In-Reply-To: <E1FvvuX-0002Lr-Nt@moooo.ath.cx>
Matthias Lederhofer wrote:
>> This is beginning of patch series introducing installation configuration
>> using autoconf (and no other autotools) to git. The idea is to generate
>> config.mak using ./configure (generated from configure.ac) from
>> config.mak.in, so one can use autoconf as an _alternative_ to ordinary
>> Makefile, and creating one's own config.mak.
>
> Are you sure this should be named config.mak? From INSTALL:
>> You can place local settings in config.mak and the Makefile
>> will include them. Note that config.mak is not distributed;
>> the name is reserved for local settings.
>
> So with another filename either include it
> - before config.mak: the user may override ./configure options with
> config.mak
> - after config.mak: ./configure overrides config.mak
The idea was to use ./configure to _generate_ config.mak, which the user can
then edit.
But perhaps using another filename for results of ./configure script
(and including it in main Makefile) would be better idea.
> At least do not overwrite config.mak if it exists.
But one might want to run ./configure with different options, to finally
arrive at the set which is satisfactionary. So unless some magic to detect
if config.mak was generated from ./configure script, or generated by user
is used...
--
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
^ permalink raw reply
* [RFC/PATCH] autoconf: Use autoconf to check for some types and library functions
From: Jakub Narebski @ 2006-06-29 13:36 UTC (permalink / raw)
To: git
In-Reply-To: <200606291359.43640.jnareb@gmail.com>
./configure script checks now for existence of the following types
and structure members:
* dirent.d_ino in dirent.h (NO_D_INO_IN_DIRENT)
* dirent.d_type in dirent.h (NO_D_TYPE_IN_DIRENT)
* 'struct sockaddr_storage' in netinet/in.h (NO_SOCKADDR_STORAGE)
./configure script checks now for the following library functions:
* strcasestr (NO_STRCASESTR)
* strlcpy (NO_STRLCPY)
* setenv (NO_SETENV)
in default C library and in libraries which have AC_CHECK_LIB done for
them (crypto, curl, expat).
NOTE: not all checks are implemented!
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
This patch needs review by someone better versed in compiling git on
different platforms, namely AC_CHECK_MEMBER and AC_CHECK_TYPE needs
checking if all header files where git search for specified structure
member or specified type.
I don't know (yet) how to implement checking for NEEDS_SSL_WITH_CRYPTO
(probably also checlking for crypto library needs correction),
NEEDS_LIBICONV, NEEDS_SOCKET, NO_IPV6, NO_ICONV, Python < 2.3 and
Python == 2.3, if to check for NO_MMAP, and for NO_ACCURATE_DIFF.
This patch is to be considered preliminary!
configure.ac | 28 ++++++++++++++++++++++++++--
1 files changed, 26 insertions(+), 2 deletions(-)
diff --git a/configure.ac b/configure.ac
index 55d7a9b..fbd46e2 100644
--- a/configure.ac
+++ b/configure.ac
@@ -14,17 +14,41 @@ AC_CONFIG_SRCDIR([git.c])
AC_DEFUN([MY_APPEND_LINE],
[[echo "$1" >> config.mak.append]])# AC_APPEND_LINE
+
# Checks for libraries.
-AC_MSG_NOTICE(CHECKS for libraries)
+AC_MSG_NOTICE([CHECKS for libraries])
AC_CHECK_LIB([crypto], [SHA1_Init],,MY_APPEND_LINE(NO_OPENSSL=YesPlease))
AC_CHECK_LIB([curl], [curl_easy_setopt],,MY_APPEND_LINE(NO_CURL=YesPlease))
AC_CHECK_LIB([expat], [XML_ParserCreate],,MY_APPEND_LINE(NO_EXPAT=YesPlease))
+
+# Checks for typedefs, structures, and compiler characteristics.
+AC_MSG_NOTICE([CHECKS for typedefs, structures, and compiler characteristics])
+
+AC_CHECK_MEMBER(struct dirent.d_ino,,
+MY_APPEND_LINE(NO_D_INO_IN_DIRENT=YesPlease),
+[#include <dirent.h>])
+AC_CHECK_MEMBER(struct dirent.d_type,,
+MY_APPEND_LINE(NO_D_TYPE_IN_DIRENT=YesPlease),
+[#include <dirent.h>])
+
+AC_CHECK_TYPE(struct sockaddr_storage,,
+MY_APPEND_LINE(NO_SOCKADDR_STORAGE=YesPlease),
+[#include <netinet/in.h>])
+
+
+# Checks for library functions.
+AC_MSG_NOTICE([CHECKS for library functions])
+AC_CHECK_FUNC(strcasestr,,MY_APPEND_LINE(NO_STRCASESTR=YesPlease))
+AC_CHECK_FUNC(strlcpy,,MY_APPEND_LINE(NO_STRLCPY=YesPlease))
+AC_CHECK_FUNC(setenv,,MY_APPEND_LINE(NO_SETENV=YesPlease))
+
+
# Output files
AC_CONFIG_FILES([config.mak:config.mak.in:config.mak.append],
[rm -f config.mak.append],
--
1.4.0
^ permalink raw reply related
* Re: [PATCH] move get_merge_bases() to core lib; use it in merge-recursive
From: Johannes Schindelin @ 2006-06-29 13:21 UTC (permalink / raw)
To: Alex Riesen; +Cc: git, Junio C Hamano, Fredrik Kuivinen, Linus Torvalds
In-Reply-To: <Pine.LNX.4.63.0606291517010.29667@wbgn013.biozentrum.uni-wuerzburg.de>
Hi,
Aargh! Of course this is [PATCH 2/2]. BTW, no signoff, since the whole
merge-recursive is not mergeable yet (passes the tests, but we have a
small way to go).
Ciao,
Dscho
^ permalink raw reply
* [PATCH] move get_merge_bases() to core lib; use it in merge-recursive
From: Johannes Schindelin @ 2006-06-29 13:17 UTC (permalink / raw)
To: Alex Riesen; +Cc: git, Junio C Hamano, Fredrik Kuivinen, Linus Torvalds
In-Reply-To: <20060627223249.GA8177@steel.home>
most of this patch is just a "sub-file rename", i.e. moving code
literally (sue me, SCO!) from merge-base.c to commit.c.
---
commit.c | 240 +++++++++++++++++++++++++++++++++++++++++++++++++++++
commit.h | 2
merge-base.c | 238 -----------------------------------------------------
merge-recursive.c | 23 ++---
4 files changed, 250 insertions(+), 253 deletions(-)
diff --git a/commit.c b/commit.c
index 946615d..891c6d0 100644
--- a/commit.c
+++ b/commit.c
@@ -842,3 +842,243 @@ void sort_in_topological_order_fn(struct
}
free(nodes);
}
+
+/* merge-rebase stuff */
+
+#define PARENT1 1
+#define PARENT2 2
+#define UNINTERESTING 4
+
+static struct commit *interesting(struct commit_list *list)
+{
+ while (list) {
+ struct commit *commit = list->item;
+ list = list->next;
+ if (commit->object.flags & UNINTERESTING)
+ continue;
+ return commit;
+ }
+ return NULL;
+}
+
+/*
+ * A pathological example of how this thing works.
+ *
+ * Suppose we had this commit graph, where chronologically
+ * the timestamp on the commit are A <= B <= C <= D <= E <= F
+ * and we are trying to figure out the merge base for E and F
+ * commits.
+ *
+ * F
+ * / \
+ * E A D
+ * \ / /
+ * B /
+ * \ /
+ * C
+ *
+ * First we push E and F to list to be processed. E gets bit 1
+ * and F gets bit 2. The list becomes:
+ *
+ * list=F(2) E(1), result=empty
+ *
+ * Then we pop F, the newest commit, from the list. Its flag is 2.
+ * We scan its parents, mark them reachable from the side that F is
+ * reachable from, and push them to the list:
+ *
+ * list=E(1) D(2) A(2), result=empty
+ *
+ * Next pop E and do the same.
+ *
+ * list=D(2) B(1) A(2), result=empty
+ *
+ * Next pop D and do the same.
+ *
+ * list=C(2) B(1) A(2), result=empty
+ *
+ * Next pop C and do the same.
+ *
+ * list=B(1) A(2), result=empty
+ *
+ * Now it is B's turn. We mark its parent, C, reachable from B's side,
+ * and push it to the list:
+ *
+ * list=C(3) A(2), result=empty
+ *
+ * Now pop C and notice it has flags==3. It is placed on the result list,
+ * and the list now contains:
+ *
+ * list=A(2), result=C(3)
+ *
+ * We pop A and do the same.
+ *
+ * list=B(3), result=C(3)
+ *
+ * Next, we pop B and something very interesting happens. It has flags==3
+ * so it is also placed on the result list, and its parents are marked
+ * uninteresting, retroactively, and placed back on the list:
+ *
+ * list=C(7), result=C(7) B(3)
+ *
+ * Now, list does not have any interesting commit. So we find the newest
+ * commit from the result list that is not marked uninteresting. Which is
+ * commit B.
+ *
+ *
+ * Another pathological example how this thing used to fail to mark an
+ * ancestor of a merge base as UNINTERESTING before we introduced the
+ * postprocessing phase (mark_reachable_commits).
+ *
+ * 2
+ * H
+ * 1 / \
+ * G A \
+ * |\ / \
+ * | B \
+ * | \ \
+ * \ C F
+ * \ \ /
+ * \ D /
+ * \ | /
+ * \| /
+ * E
+ *
+ * list A B C D E F G H
+ * G1 H2 - - - - - - 1 2
+ * H2 E1 B1 - 1 - - 1 - 1 2
+ * F2 E1 B1 A2 2 1 - - 1 2 1 2
+ * E3 B1 A2 2 1 - - 3 2 1 2
+ * B1 A2 2 1 - - 3 2 1 2
+ * C1 A2 2 1 1 - 3 2 1 2
+ * D1 A2 2 1 1 1 3 2 1 2
+ * A2 2 1 1 1 3 2 1 2
+ * B3 2 3 1 1 3 2 1 2
+ * C7 2 3 7 1 3 2 1 2
+ *
+ * At this point, unfortunately, everybody in the list is
+ * uninteresting, so we fail to complete the following two
+ * steps to fully marking uninteresting commits.
+ *
+ * D7 2 3 7 7 3 2 1 2
+ * E7 2 3 7 7 7 2 1 2
+ *
+ * and we ended up showing E as an interesting merge base.
+ * The postprocessing phase re-injects C and continues traversal
+ * to contaminate D and E.
+ */
+
+static void mark_reachable_commits(struct commit_list *result,
+ struct commit_list *list)
+{
+ struct commit_list *tmp;
+
+ /*
+ * Postprocess to fully contaminate the well.
+ */
+ for (tmp = result; tmp; tmp = tmp->next) {
+ struct commit *c = tmp->item;
+ /* Reinject uninteresting ones to list,
+ * so we can scan their parents.
+ */
+ if (c->object.flags & UNINTERESTING)
+ commit_list_insert(c, &list);
+ }
+ while (list) {
+ struct commit *c = list->item;
+ struct commit_list *parents;
+
+ tmp = list;
+ list = list->next;
+ free(tmp);
+
+ /* Anything taken out of the list is uninteresting, so
+ * mark all its parents uninteresting. We do not
+ * parse new ones (we already parsed all the relevant
+ * ones).
+ */
+ parents = c->parents;
+ while (parents) {
+ struct commit *p = parents->item;
+ parents = parents->next;
+ if (!(p->object.flags & UNINTERESTING)) {
+ p->object.flags |= UNINTERESTING;
+ commit_list_insert(p, &list);
+ }
+ }
+ }
+}
+
+struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2)
+{
+ struct commit_list *list = NULL;
+ struct commit_list *result = NULL;
+ struct commit_list *tmp = NULL;
+
+ if (rev1 == rev2)
+ return commit_list_insert(rev1, &result);
+
+ parse_commit(rev1);
+ parse_commit(rev2);
+
+ rev1->object.flags |= PARENT1;
+ rev2->object.flags |= PARENT2;
+ insert_by_date(rev1, &list);
+ insert_by_date(rev2, &list);
+
+ while (interesting(list)) {
+ struct commit *commit = list->item;
+ struct commit_list *parents;
+ int flags = commit->object.flags
+ & (PARENT1 | PARENT2 | UNINTERESTING);
+
+ tmp = list;
+ list = list->next;
+ free(tmp);
+ if (flags == (PARENT1 | PARENT2)) {
+ insert_by_date(commit, &result);
+
+ /* Mark parents of a found merge uninteresting */
+ flags |= UNINTERESTING;
+ }
+ parents = commit->parents;
+ while (parents) {
+ struct commit *p = parents->item;
+ parents = parents->next;
+ if ((p->object.flags & flags) == flags)
+ continue;
+ parse_commit(p);
+ p->object.flags |= flags;
+ insert_by_date(p, &list);
+ }
+ }
+
+ if (!result)
+ return NULL;
+
+ if (result->next && list)
+ mark_reachable_commits(result, list);
+
+ /* cull duplicates */
+ for (tmp = result, list = NULL; tmp; ) {
+ struct commit *commit = tmp->item;
+ struct commit_list *next = tmp->next;
+ if (commit->object.flags & UNINTERESTING) {
+ if (list != NULL)
+ list->next = next;
+ free(tmp);
+ } else {
+ if (list == NULL)
+ result = tmp;
+ list = tmp;
+ commit->object.flags |= UNINTERESTING;
+ }
+
+ tmp = next;
+ }
+
+ /* reset flags */
+ clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING);
+ clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING);
+
+ return result;
+}
diff --git a/commit.h b/commit.h
index 7c9ca3f..89b9dad 100644
--- a/commit.h
+++ b/commit.h
@@ -105,4 +105,6 @@ struct commit_graft *read_graft_line(cha
int register_commit_graft(struct commit_graft *, int);
int read_graft_file(const char *graft_file);
+extern struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2);
+
#endif /* COMMIT_H */
diff --git a/merge-base.c b/merge-base.c
index 7d87c20..b41f76c 100644
--- a/merge-base.c
+++ b/merge-base.c
@@ -2,244 +2,6 @@ #include <stdlib.h>
#include "cache.h"
#include "commit.h"
-#define PARENT1 1
-#define PARENT2 2
-#define UNINTERESTING 4
-
-static struct commit *interesting(struct commit_list *list)
-{
- while (list) {
- struct commit *commit = list->item;
- list = list->next;
- if (commit->object.flags & UNINTERESTING)
- continue;
- return commit;
- }
- return NULL;
-}
-
-/*
- * A pathological example of how this thing works.
- *
- * Suppose we had this commit graph, where chronologically
- * the timestamp on the commit are A <= B <= C <= D <= E <= F
- * and we are trying to figure out the merge base for E and F
- * commits.
- *
- * F
- * / \
- * E A D
- * \ / /
- * B /
- * \ /
- * C
- *
- * First we push E and F to list to be processed. E gets bit 1
- * and F gets bit 2. The list becomes:
- *
- * list=F(2) E(1), result=empty
- *
- * Then we pop F, the newest commit, from the list. Its flag is 2.
- * We scan its parents, mark them reachable from the side that F is
- * reachable from, and push them to the list:
- *
- * list=E(1) D(2) A(2), result=empty
- *
- * Next pop E and do the same.
- *
- * list=D(2) B(1) A(2), result=empty
- *
- * Next pop D and do the same.
- *
- * list=C(2) B(1) A(2), result=empty
- *
- * Next pop C and do the same.
- *
- * list=B(1) A(2), result=empty
- *
- * Now it is B's turn. We mark its parent, C, reachable from B's side,
- * and push it to the list:
- *
- * list=C(3) A(2), result=empty
- *
- * Now pop C and notice it has flags==3. It is placed on the result list,
- * and the list now contains:
- *
- * list=A(2), result=C(3)
- *
- * We pop A and do the same.
- *
- * list=B(3), result=C(3)
- *
- * Next, we pop B and something very interesting happens. It has flags==3
- * so it is also placed on the result list, and its parents are marked
- * uninteresting, retroactively, and placed back on the list:
- *
- * list=C(7), result=C(7) B(3)
- *
- * Now, list does not have any interesting commit. So we find the newest
- * commit from the result list that is not marked uninteresting. Which is
- * commit B.
- *
- *
- * Another pathological example how this thing used to fail to mark an
- * ancestor of a merge base as UNINTERESTING before we introduced the
- * postprocessing phase (mark_reachable_commits).
- *
- * 2
- * H
- * 1 / \
- * G A \
- * |\ / \
- * | B \
- * | \ \
- * \ C F
- * \ \ /
- * \ D /
- * \ | /
- * \| /
- * E
- *
- * list A B C D E F G H
- * G1 H2 - - - - - - 1 2
- * H2 E1 B1 - 1 - - 1 - 1 2
- * F2 E1 B1 A2 2 1 - - 1 2 1 2
- * E3 B1 A2 2 1 - - 3 2 1 2
- * B1 A2 2 1 - - 3 2 1 2
- * C1 A2 2 1 1 - 3 2 1 2
- * D1 A2 2 1 1 1 3 2 1 2
- * A2 2 1 1 1 3 2 1 2
- * B3 2 3 1 1 3 2 1 2
- * C7 2 3 7 1 3 2 1 2
- *
- * At this point, unfortunately, everybody in the list is
- * uninteresting, so we fail to complete the following two
- * steps to fully marking uninteresting commits.
- *
- * D7 2 3 7 7 3 2 1 2
- * E7 2 3 7 7 7 2 1 2
- *
- * and we ended up showing E as an interesting merge base.
- * The postprocessing phase re-injects C and continues traversal
- * to contaminate D and E.
- */
-
-static void mark_reachable_commits(struct commit_list *result,
- struct commit_list *list)
-{
- struct commit_list *tmp;
-
- /*
- * Postprocess to fully contaminate the well.
- */
- for (tmp = result; tmp; tmp = tmp->next) {
- struct commit *c = tmp->item;
- /* Reinject uninteresting ones to list,
- * so we can scan their parents.
- */
- if (c->object.flags & UNINTERESTING)
- commit_list_insert(c, &list);
- }
- while (list) {
- struct commit *c = list->item;
- struct commit_list *parents;
-
- tmp = list;
- list = list->next;
- free(tmp);
-
- /* Anything taken out of the list is uninteresting, so
- * mark all its parents uninteresting. We do not
- * parse new ones (we already parsed all the relevant
- * ones).
- */
- parents = c->parents;
- while (parents) {
- struct commit *p = parents->item;
- parents = parents->next;
- if (!(p->object.flags & UNINTERESTING)) {
- p->object.flags |= UNINTERESTING;
- commit_list_insert(p, &list);
- }
- }
- }
-}
-
-struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2)
-{
- struct commit_list *list = NULL;
- struct commit_list *result = NULL;
- struct commit_list *tmp = NULL;
-
- if (rev1 == rev2)
- return commit_list_insert(rev1, &result);
-
- parse_commit(rev1);
- parse_commit(rev2);
-
- rev1->object.flags |= PARENT1;
- rev2->object.flags |= PARENT2;
- insert_by_date(rev1, &list);
- insert_by_date(rev2, &list);
-
- while (interesting(list)) {
- struct commit *commit = list->item;
- struct commit_list *parents;
- int flags = commit->object.flags
- & (PARENT1 | PARENT2 | UNINTERESTING);
-
- tmp = list;
- list = list->next;
- free(tmp);
- if (flags == (PARENT1 | PARENT2)) {
- insert_by_date(commit, &result);
-
- /* Mark parents of a found merge uninteresting */
- flags |= UNINTERESTING;
- }
- parents = commit->parents;
- while (parents) {
- struct commit *p = parents->item;
- parents = parents->next;
- if ((p->object.flags & flags) == flags)
- continue;
- parse_commit(p);
- p->object.flags |= flags;
- insert_by_date(p, &list);
- }
- }
-
- if (!result)
- return NULL;
-
- if (result->next && list)
- mark_reachable_commits(result, list);
-
- /* cull duplicates */
- for (tmp = result, list = NULL; tmp; ) {
- struct commit *commit = tmp->item;
- struct commit_list *next = tmp->next;
- if (commit->object.flags & UNINTERESTING) {
- if (list != NULL)
- list->next = next;
- free(tmp);
- } else {
- if (list == NULL)
- result = tmp;
- list = tmp;
- commit->object.flags |= UNINTERESTING;
- }
-
- tmp = next;
- }
-
- /* reset flags */
- clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING);
- clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING);
-
- return result;
-}
-
static int show_all = 0;
static int merge_base(struct commit *rev1, struct commit *rev2)
diff --git a/merge-recursive.c b/merge-recursive.c
index 9bbb426..c0de38a 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -186,22 +186,15 @@ struct merge_result merge(struct node *h
node_list_insert(ancestor, &ca);
else {
struct node_list **pca = &ca;
- char cmd[100];
- sprintf(cmd, "git-merge-base --all %s %s",
- node_hex_sha1(h1),
- node_hex_sha1(h2));
- FILE *fp = popen(cmd, "r");
- while (!feof(fp)) {
- unsigned char sha1[20];
- int ch;
- if (fget_sha1(sha1, fp, &ch) == 0) {
- struct node *n;
- n = node_alloc(lookup_commit(sha1));
- node_list_insert(n, pca);
- pca = &(*pca)->next;
- }
+ struct commit_list *iter, *merge_bases
+ = get_merge_bases(h1->commit, h2->commit);
+
+ for (iter = merge_bases; iter; iter = iter->next) {
+ struct node *n = node_alloc(iter->item);
+ node_list_insert(n, pca);
+ pca = &(*pca)->next;
}
- pclose(fp);
+ free_commit_list(merge_bases);
}
output("found %u common ancestor(s):", node_list_count(ca));
--
1.4.1.rc1.g87c00-dirty
^ permalink raw reply related
* [PATCH 1/2] refactor merge_bases() as preparation to libify merge-base
From: Johannes Schindelin @ 2006-06-29 13:16 UTC (permalink / raw)
To: Alex Riesen; +Cc: git, Junio C Hamano, Fredrik Kuivinen, Linus Torvalds
In-Reply-To: <20060627223249.GA8177@steel.home>
---
merge-base.c | 64 ++++++++++++++++++++++++++++++++++++++++++----------------
1 files changed, 46 insertions(+), 18 deletions(-)
diff --git a/merge-base.c b/merge-base.c
index 4856ca0..7d87c20 100644
--- a/merge-base.c
+++ b/merge-base.c
@@ -124,8 +124,6 @@ static struct commit *interesting(struct
* to contaminate D and E.
*/
-static int show_all = 0;
-
static void mark_reachable_commits(struct commit_list *result,
struct commit_list *list)
{
@@ -167,34 +165,33 @@ static void mark_reachable_commits(struc
}
}
-static int merge_base(struct commit *rev1, struct commit *rev2)
+struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2)
{
struct commit_list *list = NULL;
struct commit_list *result = NULL;
struct commit_list *tmp = NULL;
- if (rev1 == rev2) {
- printf("%s\n", sha1_to_hex(rev1->object.sha1));
- return 0;
- }
+ if (rev1 == rev2)
+ return commit_list_insert(rev1, &result);
parse_commit(rev1);
parse_commit(rev2);
- rev1->object.flags |= 1;
- rev2->object.flags |= 2;
+ rev1->object.flags |= PARENT1;
+ rev2->object.flags |= PARENT2;
insert_by_date(rev1, &list);
insert_by_date(rev2, &list);
while (interesting(list)) {
struct commit *commit = list->item;
struct commit_list *parents;
- int flags = commit->object.flags & 7;
+ int flags = commit->object.flags
+ & (PARENT1 | PARENT2 | UNINTERESTING);
tmp = list;
list = list->next;
free(tmp);
- if (flags == 3) {
+ if (flags == (PARENT1 | PARENT2)) {
insert_by_date(commit, &result);
/* Mark parents of a found merge uninteresting */
@@ -213,21 +210,52 @@ static int merge_base(struct commit *rev
}
if (!result)
- return 1;
+ return NULL;
if (result->next && list)
mark_reachable_commits(result, list);
+ /* cull duplicates */
+ for (tmp = result, list = NULL; tmp; ) {
+ struct commit *commit = tmp->item;
+ struct commit_list *next = tmp->next;
+ if (commit->object.flags & UNINTERESTING) {
+ if (list != NULL)
+ list->next = next;
+ free(tmp);
+ } else {
+ if (list == NULL)
+ result = tmp;
+ list = tmp;
+ commit->object.flags |= UNINTERESTING;
+ }
+
+ tmp = next;
+ }
+
+ /* reset flags */
+ clear_commit_marks(rev1, PARENT1 | PARENT2 | UNINTERESTING);
+ clear_commit_marks(rev2, PARENT1 | PARENT2 | UNINTERESTING);
+
+ return result;
+}
+
+static int show_all = 0;
+
+static int merge_base(struct commit *rev1, struct commit *rev2)
+{
+ struct commit_list *result = get_merge_bases(rev1, rev2);
+
+ if (!result)
+ return 1;
+
while (result) {
- struct commit *commit = result->item;
- result = result->next;
- if (commit->object.flags & UNINTERESTING)
- continue;
- printf("%s\n", sha1_to_hex(commit->object.sha1));
+ printf("%s\n", sha1_to_hex(result->item->object.sha1));
if (!show_all)
return 0;
- commit->object.flags |= UNINTERESTING;
+ result = result->next;
}
+
return 0;
}
--
1.4.1.rc1.g87c00-dirty
^ permalink raw reply related
* Re: CFT: merge-recursive in C (updated)
From: Johannes Schindelin @ 2006-06-29 13:16 UTC (permalink / raw)
To: Alex Riesen; +Cc: git, Junio C Hamano, Fredrik Kuivinen, Linus Torvalds
In-Reply-To: <20060627223249.GA8177@steel.home>
Hi,
On Wed, 28 Jun 2006, Alex Riesen wrote:
> > > Path list optimization should be next (and I'll be glad if someone does
> > > this before me).
> >
> > See below.
> >
>
> Aah, thanks. Merged, tried, tested, left in patch.
> The reallocs can cause some undesirable heap fragmentation, don't you
> think?
I do not care too deeply about the heap fragmentation there: it is just 4
bytes per file name. Besides, I chose an increment of 32 (probably I
should use alloc_nr() instead).
> I tried to replace that code completely with a call to git-merge-base
> (it does not happen too often). So far it passed all tests.
>
> > I have some commits in a private branch to split out get_merge_bases()
> > from merge-base.c, so I'll try that next.
>
> Thanks, that'd be nice.
Will reply with two patches.
> > BTW, before actually finishing this, we might want to do away with
> > capitalizedFunctionNames and 4-space indent.
>
> 4-space indent should be gone by now, the names pending (they were
> important in initial debugging after conversion).
Okay.
Ciao,
Dscho
^ permalink raw reply
* Re: [PATCH] autoconf: Use autoconf to write installation directories to config.mak
From: Matthias Lederhofer @ 2006-06-29 12:46 UTC (permalink / raw)
To: Jakub Narebski; +Cc: git
In-Reply-To: <200606290301.51657.jnareb@gmail.com>
> This is beginning of patch series introducing installation configuration
> using autoconf (and no other autotools) to git. The idea is to generate
> config.mak using ./configure (generated from configure.ac) from
> config.mak.in, so one can use autoconf as an _alternative_ to ordinary
> Makefile, and creating one's own config.mak.
Are you sure this should be named config.mak? From INSTALL:
> You can place local settings in config.mak and the Makefile
> will include them. Note that config.mak is not distributed;
> the name is reserved for local settings.
So with another filename either include it
- before config.mak: the user may override ./configure options with
config.mak
- after config.mak: ./configure overrides config.mak
At least do not overwrite config.mak if it exists.
^ permalink raw reply
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