[cs631apue] questions for our last class

[Jan Schaumann]

> With regards to fts, I still can?t figure the best
> way to use it in order to recurse through the levels
> of a directory efficiently. (This is more towards
> efficiency of ls from the midterm) So my question is
> how would you use fts to get each item stored at
> each level and displaying it when doing -R in the
> most efficient manner?

The need to traverse directories multiple times stems
from the requirement to format all fields based on the
largest value.  That value, however, need only be
determined for the entries in the specific directory,
not within the entire hierarchy underneath the
directory.

That is, given a same hierarchy such as

              dir/
file1  file2  file3  subdir1/   subdir2/  
                      f1  f2     f3   f4

and listing 'dir', there is no need to traverse all of
'subdri1' and 'subdir2'.  So even when using '-R',
you'd first iterate over the contents of 'dir',
determine the largest fields, then print those
entries, and subsequently recurse into the
subdirectories.

The NetBSD implementation of ls(1) illustrates this
approach.  See the function 'traverse' in
http://cvsweb.netbsd.org/bsdweb.cgi/~checkout~/src/bin/ls/ls.c?HEAD&only_with_tag=MAIN

	if ((ftsp =
	    fts_open(argv, options, f_nosort ? NULL : mastercmp)) == NULL)
		err(EXIT_FAILURE, NULL);

	display(NULL, fts_children(ftsp, 0));

That is, after calling fts_open(3), it passes the list
of entries (i.e., the return of fts_children(3)) to
the 'display' function.  Then:

	while ((p = fts_read(ftsp)) != NULL)
		switch (p->fts_info) {
		case FTS_D:
			chp = fts_children(ftsp, ch_options);
			display(p, chp);

			if (!f_recursive && chp != NULL)
				(void)fts_set(ftsp, p, FTS_SKIP);

iterate over the entries; if you encounter a
directory, display the children of that directory.  If
not recursive, mark the entry to not be descended
into.

The 'display' function then builds a list of items to
display while determining the max values.  After it
has processed all entries, it then passes that list to
the appropriate function to print out the list of
entries.

This way, you don't have to iterate over the directory
again after having determined the max value within
that directory.

Other implementations of ls(1) may use a different
strategy; compare to e.g., the GNU implementation (in
'coreutils'; ftp.gnu.org/gnu/coreutils/) or Illumos
(https://github.com/illumos/illumos-gate/blob/master/usr/src/cmd/ls/).

-Jan