On Tue, Aug 28, 2007 at 12:02:22PM +0100, Johannes Schindelin wrote:

quoted text
> 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.

quoted text
> 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.

quoted text
> 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.

quoted text
> 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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html