Messages in this thread | | | Date | Wed, 15 Apr 1998 12:26:56 +0200 (MET DST) | From | Rik van Riel <> | Subject | Re: 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
| |