[lkml]   [1998]   [Apr]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectSymlink loop detection
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 */
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.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to

 \ /
  Last update: 2005-03-22 13:42    [from the cache]
©2003-2011 Jasper Spaans