[aclug-L] Re: This one goes out to the C programmers...

[Tom Hull <thull@xxxxxxxxxxx>]

Burt Humburg wrote:
> 
> I'm coding a search engine and I need to make like a tree.c and recursively
> scan through a folder looking for all subdirectories and files. Thing is,
> I'd prefer not to reinvent the wheel. Is there a repository for
> commonly-used C routines? Specifically, can someone show me code or
> pseudocode for a tree algorithm?

The primitive functions for reading filenames in a directory are:

  opendir, readdir, closedir

You then need to call lstat() on each pathname to determine which
are directories. You also need code to ignore "." and "..". The usual
approach is to recurse on directories. You also have to decide whether
to follow symbolic links, what to do with "hidden" filenames, what to
do on errors, whether to do a "depth first" search (critical for
implementing something like rm -r), etc.

There have been several attempts to generalize file tree search code:
ftw (older Unix), nftw (newer Unix), fts (BSD). You can find ftw/nftw
in glibc; e.g.:

  http://puffin.external.hp.com/lxr/source/glibc/io/ftw.c

The above functions give you files in whatever order the directory
lists them (usually insertion). If you want sorted order, you need
to collect the set of nodes, then sort them. In some cases, it might
be easier to just suck the output from a shell command; e.g.:

  FILE *f;
  char buf[PATHLEN], *s;
  if ((f = popen("find . -print | sort", "r")) != 0) {
    while (fgets(buf, sizeof buf, f)) {
      if (s = strchr(buf, '\n')) *s = 0;
      /* do your thing */
    }
    pclose(f);
  }

I've always thought that rocketaware was a good general repository for
re-usable source code information, although it hasn't yielded much in
this case:

  http://www.rocketaware.com/

The tree(1) source code is available from:

  ftp://mama.indstate.edu/linux/tree/tree-1.3.tgz

I wrote a non-recursive file tree search function in ftwalk. The
basic idea is to keep a queue of directory pathnames. Put the start
directory into the queue, add new directory pathnames to the queue
as found, and loop until the queue is empty. The source code is in
"ft_find.C", but it's in C++ and pretty dense, but the good news
is that the memory management code is all buried in classes (mostly
in libn).

-- 
/*
 *  Tom Hull * thull at kscable.com * http://www.ocston.org/~thull/
 */
-- This is the discussion@xxxxxxxxx list.  To unsubscribe,
visit http://tmp2.complete.org/cgi-bin/listargate-aclug.cgi