Re: Symlink loop detection

Sean Hunter (huntersean@hotmail.com)
Wed, 15 Apr 1998 03:35:58 PDT

>
>> 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)
> --Scott
...except it does.

On the fourth time through the loop, the current element is 'd', so the
comparison pointer is set to 'd'.
The fifth time through the loop, the current element is 'c'.
'c'!='d', so go on
the sixth iteration gives 'd'
'd'=='d'---loop detected.

I may be wrong. Anyway, this is somewhat beside the point, as I'm sure
that Linus et al don't need anyone to tell them an algorithm to find a
loop in a linked list... ;^>

Sean Hunter

______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com

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