Symlink loop detection

Colin Plumb (colin@nyx.net)
Tue, 14 Apr 1998 16:47:59 -0600 (MDT)

Linus noted that it's possible to fuck up the algorithm for
for detecting loops by changing the world under it.
(It's referred to as Tarjan's algorithm, but I knew it as Floyd's
cycle-finding algorithm).

A more efficient, and somewhat simpler to implement, IMHO,
technique was developed by Richard Brent. It consists of:

int i = 1;
list_t *remember;
list_t *cur;

remember = cur = start;

for (;;) {
cur = cur->next;
if (cur == remember)
break; /* Cycle found */
i++;
if ((i&(i-1)) == 0) /* Is i a power of 2? */
remember = cur;
}

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.

-- 
	-Colin


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