Re: Symlink loop detection

C. Scott Ananian (cananian@lcs.mit.edu)
Wed, 15 Apr 1998 12:55:48 -0400 (EDT)

On Wed, 15 Apr 1998, Rik van Riel wrote:
> On Tue, 14 Apr 1998, C. Scott Ananian wrote:
> > On Tue, 14 Apr 1998 Colin Plumb <colin@nyx.net> wrote:
>
> > > A more efficient, and somewhat simpler to implement, IMHO,
> > > technique was developed by Richard Brent. It consists of:
[...]
> > This obviously doesn't work.
> > (a->b->c->d->c... for example)
>
> a->b->c->d->c->d ... !loop detected!
>
> Yes it does work, at least in this case...

I stand corrected. I obviously was not thinking hard enough.
In any case, both these algorithms are O(N).
--Scott
@ @
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-oOO-(_)-OOo-=-=-=-=-=
C. Scott Ananian: cananian@lcs.mit.edu / Declare the Truth boldly and
Laboratory for Computer Science/Crypto / without hindrance.
Massachusetts Institute of Technology /META-PARRESIAS AKOLUTOS:Acts 28:31
-.-. .-.. .. ..-. ..-. --- .-. -.. ... -.-. --- - - .- -. .- -. .. .- -.
PGP key available via finger and from http://www.pdos.lcs.mit.edu/~cananian

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu