Mail Archives: cygwin/2005/05/03/09:24:48
On May 3 07:05, Eric Blake wrote:
> rather than starting at the left and
> making sure each path component exists, the algorithm could start at the
> right and successively prune each rightmost component until it no longer
> gets ENOENT (or gets to the empty string), then build back up from that
> point. Then, even though //MACHINE does not resolve to a directory,
> `mkdir -p //MACHINE/Share/existing/nonexisting' only has to check whether
> //MACHINE/Share/existing exists, and create nonexisting from there, rather
> than starting all the way from the problematic /, //, or //MACHINE. The
> only drawback to this approach is that it would then require up to n
> stat() calls to decide where to start making directories, each processing
> O(n) names, which is the exact O(n^2) syscall overhead that the code was
> optimized to try to avoid by starting blindly at the leftmost component.
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.
> The only other approach I can think of is to special case leading // (at
> least on cygwin, leading // should start after //MACHINE/Share/), but not
> all POSIX-compliant hosts have the same semantics for leading //, so I
> don't know how well such a special case would fold into upstream coreutils.
If coreutils is trying to be POSIX compliant, it has to allow and evalute
correctly two leading slashes:
http://www.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap04.html#tag_04_11
Quote:
"A pathname that begins with two successive slashes may be interpreted in an
implementation-defined manner, although more than two leading slashes shall
be treated as a single slash."
Corinna
--
Corinna Vinschen Please, send mails regarding Cygwin to
Cygwin Project Co-Leader mailto:cygwin AT cygwin DOT com
Red Hat, Inc.
--
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 -