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@cygwin.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/