Tom Lord <lord@emf.net> writes:
> > From: Greg Stein <gstein@lyra.org>
>
> > That huge email is based on a premise that you don't
> > explain. You throw out "this won't work", but without anything
> > to back it up, and then go into a long list of "which means this
> > and that, and can't do this, and so the code should do that."
>
> Mostly I left out explaining why "this won't work" to keep the message
> from being huger than huge.
>
> But here you go.
>
> We can already assume that for every path@rev we can quickly and
> easily compute a node_id.copy_id.rev.
Today, the ease of this calculation is quite high. You simply
traverse the DAG for PATH's parent directory, and return (roughly) the
NODE-REV-ID for basename(path)'s entry in its parent. As such, the
speed of this calculation is directly proportional to the number of
path components in PATH. Also, I say "roughly" because NODE-REV-ID is
node_id.copy_id.txn_id -- to get specifically what you asked for is an
extra table lookup mapping txn_id -> rev.
> We can assume that for two such noderev ids, the predicate:
>
> X is_ancestor_of Y
>
> is easy to compute. It's cheap to know where a given node_id.copy_id
> branched from. The immediate ancestor of a noderev is easy to find.
> I'll assume that immediate successor is easy to compute, though I
> don't know that for a fact.
Immediate successors are stored in the NODE-REVISION structure, so
that's easy. Branch point calculation is a bit tricky. Don't ask for
details on that just yet, please. My brain has dismissed the details
(I'll be working to remedy that in upcoming days).
X is_ancestor_of Y is nearly impossible to calculate as stated. But X
is_ancestor_of Y ::= Y is_successor_of X, which is doable, but which
has costs on the order of the number of successors between X and Y
(it's a linked-list backwards in time, essentially). Of course, you
get a quick rule-out if X is_related_to Y fails (which is
a constant-time calculation).
---
And ... judging by the size of the rest of your mail, and that a quick
skim doesn't seem to reveal more questions about today's FS, I regret
to inform you that I've timed out. :-\
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Fri Apr 18 05:43:00 2003