lkml.org 
[lkml]   [1998]   [Apr]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Symlink loop detection
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 does a signle traversal of the list, but "halts" a comparison
> > point at each power-of-two step. If you ever come back to the
> > comparison pointer, you have a loop.
>
> 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...

A more difficult case would be:

a->b->c->d->e->c->d->e->c->d->e->c...

But this case would be found too, since a, b, d, e and c are
all on powers of two somewhere.
In fact, when you have a loop of an uneven lenght, all values
will be on a power-of two boundary somewhere...

Rik.
+-------------------------------------------+--------------------------+
| Linux: - LinuxHQ MM-patches page | Scouting webmaster |
| - kswapd ask-him & complain-to guy | Vries cubscout leader |
| http://www.fys.ruu.nl/~riel/ | <H.H.vanRiel@fys.ruu.nl> |
+-------------------------------------------+--------------------------+


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

\
 
 \ /
  Last update: 2005-03-22 13:42    [W:0.062 / U:0.120 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site