Hi,
On Tue, 28 Aug 2007, Jeff King wrote:
> 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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
