Path: utzoo!utgpu!watserv1!watmath!att!rutgers!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!haven!mimsy!chris
From: chris@mimsy.umd.edu (Chris Torek)
Newsgroups: comp.unix.shell
Subject: Re: Leaf directories (Re: Why is find so slow)
Message-ID: <27040@mimsy.umd.edu>
Date: 18 Oct 90 05:29:51 GMT
References: <F&gya5o2@cs.psu.edu> <15052@hydra.gatech.EDU> <F&0u96p2@cs.psu.edu> <9959@jpl-devvax.JPL.NASA.GOV>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 43

>In article <26981@mimsy.umd.edu> I demonstrate how to avoid extra
`stat' calls on Unix systems that happen also to be POSIX conformant.
(I am told that POSIX requires links, but not `..' links, so the code
that says `nsubdirs = st.st_nlink - 2' is Unix-specific.)  An important
feature of the algorithm is that stat()s stop as soon as all
subdirectories have been found.

In article <9959@jpl-devvax.JPL.NASA.GOV> lwall@jpl-devvax.JPL.NASA.GOV
(Larry Wall) writes:
>If find is done this way, it would behoove us to sort subdirectories
>before filenames in each directory so that nsubdirs goes to 0 as soon
>as possible.

Yes.  Note that `restore'ing a file system Just Happens to do this.
(Actually, it does it for an obvious reason---the data `dump' writes
is in this order---but it turns out to be convenient.)  You can also
write a program that marches through a directory tree, moving all
subdirectories to the front---it looks something like this:

	# untested shell script to move files after directories
	# does not work in / or at mount points
	# does not handle file names with embedded shell metacharacters
	dirs=
	files=
	for i in `ls -a | tail +2`; do
		if [ -d $i ]; then
			dirs="$dirs $i"
			(cd $i; sh move_them_around)
		else
			files="$files $i"
		fi
	done
	mkdir ../move_tmp.$$
	case "$dirs" in "");; *) mv $dirs ../move_tmp.$$;; esac
	case "$files" in "");; *) mv $files ../move_tmp.$$;; esac
	here=`pwd | sed -e 's,.*/,,`
	cd ..
	rmdir $here; mv move_tmp.$$ $here

This can all be done better in perl. :-)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
Domain:	chris@cs.umd.edu	Path:	uunet!mimsy!chris