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