On Tue, Aug 28, 2007 at 12:02:22PM +0100, Johannes Schindelin wrote:
> Okay, I could have been clearer: make rev_name a linked list, where only
> the first contains the actual root of the name (i.e. "v2.6.22-rc1"). This
> can be made const char *, so that it is not allocated.
OK, I think we're on the same page.
> And to speed up comparison (and to know whether to point to a rev_name or
> a const char *) you can store the number of merge traversals:
Can't that number get stale if the pointed-to rev_name improves? That
is, if I have named a rev "foo~20^2~5", and another rev points at it
with "^2~30", then in the second rev we know that the number of merge
traversals is 2. But what if foo~20^2~5 is actually "bar", and when we
process the "bar" ref, our merge traversal number _should_ shrink to 1.
But it won't, since when we're processing the pointed-to rev, we don't
know which commits point to it.
I have a feeling we would eventually hit the pointing-from rev and fix
it (since the new value will always be better than the old), but I'm not
sure I'm comfortable relying on that without more proof.
> struct rev_name {
> union {
> /* root is used when traversals == 0, otherwise previous */
> struct rev_name *previous;
> const char *root;
> } p;
> int generation;
> int traversals;
> }
You would also, of course, need the parent number.
> Then comparison would be something like
>
> int cmp_name(struct rev_name *n1, struct rev_name *n2)
> {
> int result = 0;
> if (n1->traversals != n2->traversals)
> return n1->traversals - n2->traversals;
> do {
> if (n1->generation != n2->generation)
> result = n1->generation - n2->generation;
> n1 = n1->p.previous;
> n2 = n2->p.previous;
> } while (n1->traversals);
> return result;
> }
I do wonder if this would actually have worse performance due to jumping
all over the cache. I think there's no way to do without writing it.
-Peff
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
