Submission

Please, submit your solution by e-mail to: weinhold (at) os.inf.tu-dresden.de .

Exercise

The goal of this exercise is to familiarize yourself with the basic operations and data structures of the UNIX file system.

The UNIX utility find searches the file system for files that meet certain requirements. Your task is to implement a small find utility that accepts the following command-line syntax:

find <directory name> [-name <pattern>] [-type <f | d>] [-follow] [-xdev]

Your program should print a filename if the corresponding file or directory matches all the constraints specified on the command line (if any). Using the -type switch, the user can specify that either regular files or directories will match, but not both. The option -follow shall tell your program to follow symbolic links. The option -xdev specifies that 'find' shall not search directories whose contents are located in another file system (e.g., another disk partition). The option -name shall accept wildcards as explained in the following manpage excerpt:

          A string is a wildcard pattern if it contains one of the characters `?', `*' or
          `['. Globbing is the operation that expands a wildcard pattern into the list of
          pathnames matching the pattern. Matching is defined by:
          A `?' (not between brackets) matches any single character.
          A `*' (not between brackets) matches any string, including the empty string.
          ...
          (see also glob(7))
        

If you are in doubt about what the exact behavior of your tool shall be for the various options, see what GNU find outputs in your test environment (comes with your Linux distribution). Reading the GNU find manpage is also a good idea. You might find the functions readdir(), stat(), and fnmatch() or glob() to be useful when you develop the functionality to traverse directory trees. Note that it is not allowed use existing directory tree walkers such nftw() or ftw(), instead you are expected to build this functionality yourself.

A complete solution of this exercise consists of a tarball containing C or C++ source code and a Makefile that builds your program from these sources. Please make sure that you test your program thoroughly and any debugging output is disabled before you submit it. We look at the source code, but we primarily use automated tests to verify the correctness of your find tool. Therefore, your program should print all matching pathnames like, GNU find does. Don't use output formats such as "found file: /path/to/file" or "found match: type=d, /path/to/dir"!

Important: To get good test coverage, you should download this tarball, which contains a shell script for creating a directory hierarchy for testing your find program. It is particularly useful for making sure that your implementation of the '-follow' option behaves in sensible way, like for example GNU find does! Also, see the included README for details on how to test the '-xdev' option.

Resources

• W.R. Stevens: "Advanced Programming in the UNIX Environment"
• find manpage
• readdir(), stat(), and fnmatch() or glob() manpages
• Tarball with shell script to create testbed