5.8 Exercise: Traversing Directories

The exercises in this section develop programs to traverse directory trees in depth-first and breadth-first orders. Depth-first searches explore each branch of a tree to its leaves before looking at other branches. Breadth-first searches explore all the nodes at a given level before descending lower in the tree.

Example 5.37

For the file system tree in Figure 5.1 on page 146, depth-first ordering visits the nodes in the following order.

 /   dirC      my3.dat   dirA      dirB         my1.dat      my1.dat      my2.dat 

The indentation of the filenames in Example 5.37 shows the level in the file system tree. Depth-first search is naturally recursive, as indicated by the following pseudocode.

 depthfirst(root) {    for each node at or below root       visit node;         if node is a directory            depthfirst(node); } 

Example 5.38

For the file system tree in Figure 5.1, breadth-first order visits the nodes in the following order.

 / /dirC /dirA /dirC/my3.dat /dirA/dirB /dirA/my1.dat /dirA/my2.dat /dirA/dirB/my1.dat 

Breadth-first search can be implemented with a queue similar to the history queue of Program 2.8 on page 47. As the program encounters each directory node at a particular level, it enqueues the complete pathname for later examination. The following pseudocode assumes the existence of a queue. The enqueue operation puts a node at the end of the queue, and the dequeue operation removes a node from the front of the queue.

 breadthfirst(root){     enqueue(root);     while (queue is not empty) {        dequeue(&next);        for each node directly below next:            visit the node            if node is a directory               enqueue(node)     }  } 

Exercise 5.39

The UNIX du shell command is part of the POSIX:UP Extension. The command displays the sizes of the subdirectories of the tree rooted at the directory specified by its command-line argument. If called with no directory, the du utility uses the current working directory. If du is defined on your system, experiment with it. Try to determine which search strategy it uses to traverse the tree.

Develop a program called mydu that uses a depth-first search strategy to display the sizes of the subdirectories in a tree rooted at the specified file.

1. Write a function called depthfirstapply that has the following prototype.

    int depthfirstapply(char *path, int pathfun(char *path1)); 

   The depthfirstapply function traverses the tree, starting at path . It applies the pathfun function to each file that it encounters in the traversal. The depthfirstapply function returns the sum of the positive return values of pathfun , or “1 if it failed to traverse any subdirectory of the directory. An example of a possible pathfun is the sizepathfun function specified in the next part.

2. Write a function called sizepathfun that has the following prototype.

    int sizepathfun(char *path); 

   The sizepathfun function outputs path along with other information obtained by calling stat for path . The sizepathfun returns the size in blocks of the file given by path or -1 if path does not correspond to an ordinary file.

3. Use depthfirstapply with the pathfun given by sizepathfun to implement the following command.

    showtreesize pathname 

   The showtreesize command writes pathname followed by its total size to standard output. If pathname is a directory, the total size corresponds to the size of the entire subtree rooted at pathname . If pathname is a special file, print an informative message but no size.

4. Write a command called mydu that is called with a command-line argument rootpath as follows .

    mydu rootpath 

   The mydu program calls a modified depthfirstapply with the function sizepathfun . It outputs the size of each directory followed by its pathname. The size of the directory does not count the size of subtrees of that directory. The program outputs the total size of the tree at the end and exits.

5. Write breadthfirstapply that is similar to depthfirstapply but uses a breadth-first search strategy.