Hi,

On Tue, 28 Aug 2007, Jeff King wrote:

quoted text
> On Tue, Aug 28, 2007 at 11:03:22AM +0100, Johannes Schindelin wrote:
> 
> > But then, we could spare even more space when not using an array, but a 
> > linked list for the generation numbers...  It is a small performance 
> > impact, but in reality it will not matter, methinks.
> 
> Hrm. I was puzzled at first by what you meant, and then I thought about
> some more, and came up with this. Which is perhaps what you intended all
> along, or maybe not.

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.

Then, like you described, you can have instances of rev_name, pointing to 
other instances of rev_name instead of a root.

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:

struct rev_name {
	union {
	 	/* root is used when traversals == 0, otherwise previous */
		struct rev_name *previous;
		const char *root;
	} p;
	int generation;
	int traversals;
}

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;
	}

Name generation would be a bit more expensive, but then it is the 
operation which is called only rarely.

Ciao,
Dscho

	
-
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