Mail Archives: cygwin/2005/05/03/09:50:22
> O(n^2)? I see only O(n), regardless where the algorithm begins the search.
> In any path of length n, you have a constant sum of n stat and mkdir calls,
> AFAICS.
I was using n to mean the number of components separated by /, not the string length of the path (see the source code coreutils/lib/makepath.c where the optimization discusses this same issue). Yes, there are only O(n) syscalls, but each syscall has to check the existance of O(n) components, and the leftmost component's existance is checked n times, for a total of O(n^2) component checks. By starting at the left, and changing directories as you go, the leftmost component's existance is checked only once (at least, on systems where relative paths do not have to be converted to an absolute path first). I concede that you are probably right that the optimization attempted by coreutils performs no faster on cygwin, since cygwin has to convert relative to absolute and check the existance of the leftmost component every time (whether it is cygwin1.dll or Windows doing the check each time).
> If coreutils is trying to be POSIX compliant, it has to allow and evalute
> correctly two leading slashes:
The coreutils maintainers are well aware of that fact. I think this case is just an oversight; I'm not sure if coreutils ever worked, since looking at http://savannah.gnu.org/cgi-bin/viewcvs/coreutils/coreutils/lib/makepath.c shows that it has blindly chdir()'d to / ever since version 1.27 in July 1997, before coreutils even existed.
--
Eric Blake
--
Unsubscribe info: http://cygwin.com/ml/#unsubscribe-simple
Problem reports: http://cygwin.com/problems.html
Documentation: http://cygwin.com/docs.html
FAQ: http://cygwin.com/faq/
- Raw text -