Messages in this thread | | | Date | Tue, 14 Apr 1998 21:31:43 -0400 (EDT) | From | "Adam D. Bradley" <> | Subject | Re: 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
| |