lkml.org 
[lkml]   [1998]   [Apr]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: PATCH: smart symlink loop detection.

> I'm wondering if there isn't another way to handle this problem. I
> didn't see the start of this conversation, so I don't have the patch
> in question.
>
> I have found loops in lists with this algorithm that has no recursion.
>
> Obj* pa = pStart;
> Obj* pb = pStart;
> do {
> pb = pb->next;
> if (pa == pb)
> goto loop_detected;
> pa = pa->next;
> pb = pb->next;
> if (pa == pb)
> goto loop_detected;
> } while (pb != pEnd);
>
> The algorithm is O(n), exactly N when there is no loop.
> I recognize that the pa->next operation may be expensive, but a
> general algorithm warrants the change.

The problem isn't finding the loops - it's in resolving each of the
symbolic names to a real pathname. The current system is inherently
recursive in the way it descends through each layer of the directory
tree.

If it can be flattened and made iterative, then loop detection is
simple. Doing it well and correctly with the current setup, however,
would be hairy.

Keep your eyes peeled for another patch from Scott (I e-mailed him
this AM with some comments about the current code, and within 20
minutes he had e-mailed me back saying he had a working patch running
on his system... I may code my own version for kicks, but you'll
probably see one from him on the list much sooner ;-> ...)

Adam
--
You crucify all honesty \\Adam D. Bradley artdodge@cs.bu.edu
No signs you see do you believe \\Boston University Computer Science
And all your words just twist and turn\\ Grad Student and Linux Hacker
Reviving just to crash and burn \\ <><
---------> Why can't you listen as love screams everywhere? <--------


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