lkml.org 
[lkml]   [1998]   [Apr]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: PATCH: smart symlink loop detection.
Date
> 
> >>>>> "Marc" == Marc Singer <elf@netcom.com> writes:
>
> Marc> I have found loops in lists with this algorithm that has no recursion.
>
> Marc> Obj* pa = pStart;
> Marc> Obj* pb = pStart;
> Marc> do {
> Marc> pb = pb->next;
> Marc> if (pa == pb)
> Marc> goto loop_detected;
> Marc> pa = pa->next;
> Marc> pb = pb->next;
> Marc> if (pa == pb)
> Marc> goto loop_detected;
> Marc> } while (pb != pEnd);
>
> um... if i read this right, you are only detecting loops of one node;
> that is, nodes that point at themselves. consider:

I think you aren't reading it correctly.

>
> Obj a, b, c, end;
> a.next = &b;
> b.next = &c;
> c.next = &a;
>
> Obj * pStart = &a;
> Obj * pEnd = &end;
>
> at no point in your algorithm is pa ever equal to pb. (not to mention
> that it will never terminate!) in fact, your algorithm probably boils
> down to something like this:
>
> Obj * p = pStart;
> while (p != pEnd) {
> Obj * t = p->next;
> if (p == t)
> goto loop_detected;
> p = t;
> }

Read it again. One pointer is incremented twice for every time the
other is incremented once.

>
> Marc> The algorithm is O(n), exactly N when there is no loop. I
> Marc> recognize that the pa->next operation may be expensive, but a
> Marc> general algorithm warrants the change.
>
> and i think you're thinking in C++, since in C, pa->next is always a
> pointer-to-member data lookup, not an "operation". (and if my C is
> rusty, it's because i've done C++ more recently than C, and perl more
> recently than that! :)

It's pseudo code. Besides, next could be a member of the Obj
structure in which case this is correct C.

>
> the most fruitful place to look for information on this topic is
> probably under discussions of classical algorithms, especially as
> applied to garbage collectors (since loop detection becomes an issue
> for pointer-following scavenging GC).
>
> general loop-detection is almost certainly O(n^2), since you have to
> compare n "next pointers" to (n-1) node addresses.

The constant is 2, O(2*n). An O(n^2) algorithm could be written if
you knew how many items were supposed to be in the list and you
compared each item against every other one. This algorithm doesn't do
this.

>
> alternatives include some sort of mark-and-sweep (mark nodes as you
> visit them, you've found a loop if you hit an already-marked node).
> but this entails a cost of O(n) in space (a factoid per nodes), as
> well as encapsulation concerns (if this is external to the objects
> being scanned, you probably don't want to add bookkeeping of this
> nature).


AFAIK, this algorithm is the best one known for finding loops in
lists. It works by moving two pointers through the list. One is
incremented twice as fast as the other, so it will either reach the
end of the list, or it will become equal to the slow moving pointer.
It is much simpler that mark and sweep and requires constant storage.


>
> t.
> --
> Tkil * <URL: http://www.scrye.com/~tkil> * hopelessly hopeless romantic.
> "So amplify this little one | She hears as much as she can see
> She's a volume freak | And what she sees, she can't believe."
> -- Catherine Wheel, _Happy Days_, "Judy Staring At The Sun"
>


-- Oscar


-
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    [W:0.496 / U:1.688 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site