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

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