Reimplementing the Tree Command
2018 September 30

I decided I'm going to try to reimplement the tree utility from scratch in a very limited version. Mine will only work from the current directory and will support no arguments. This article will take you through my implementation of the problem.

The tree program produces a diagram of the directory structure from a given starting point, generally the current working directory. You can see an example in the screenshot below.

Tree output

My version is much simpler. It does not implement:

The first order of business is to open a directory and read it's content. For that we need opendir and readdir. These functions from the posix standard. opendir opens a directory stream, and readdir reads from that stream to produce a dirent structs. These structs contain information about the current entry, such as the name and type of file.

// from http://man7.org/linux/man-pages/man3/readdir.3.html
struct dirent {
    ino_t          d_ino;       /* Inode number */
    off_t          d_off;       /* Not an offset; see below */
    unsigned short d_reclen;    /* Length of this record */
    unsigned char  d_type;      /* Type of file; not supported
                                   by all filesystem types */
    char           d_name[256]; /* Null-terminated filename */
};

The next task is to separate out the results of readdir from what we want. We need to be careful of the current directory entry, and the previous directory entry, if we recurse on those directories we could get an infinite loop during our in order traversal. We also need to filter out hidden files, because the normal find does not include hidden files by default. To do this, we examine the contents of the dirent.d_name field.

The next step is to recurse on entries that contain more entries. According to the man page when d_type is equal to DT_DIR, that entry is a directory, and we should recurse on them. But we run into a problem, we don't have the full path. We could do string concatenation, and build on each step, but I didn't feel like it. Instead I used chdir to move our context to that directory, and drop down once we finished up. This may not be very efficient(system calls), but it avoids buffer overflows, and C-style strings are miserable.

The final piece we must consider is counting up the number of files and the number of directories. I used a struct containing the counts, and returned them from each layer of the walk in the classic recursive way of building up a solution.

The important takeaways are:

Below is the finished version of this code. It's quite simple as you can see.

/*
 * tree.c
 * Henry J Schmale
 * September 30, 2018
 *
 * A trivial reimplementation of the tree program with no support for
 * arguements. Works from the current directory, and produces a nice
 * ascii diagram of the directory structure. Once it has fully walked
 * the directory tree it prints out some stats.
 *
 */

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
#include <sys/types.h>
#include <dirent.h>
#include <unistd.h>

const int INDENT_SIZE = 4;

typedef struct {
    size_t num_dir;
    size_t num_files;
} dir_res_t;

/*
 * unix_error - unix-style error routine
 */
void 
unix_error (char *msg)
{
    fprintf (stderr, "%s: %s\n", msg, strerror(errno));
    exit (1);
}

static inline int
self_ref (const char* s) {
    return strcmp (s, ".") == 0 || strcmp(s, "..") == 0;
}

static inline int
hidden (const char* s) {
    return s[0] == '.' && s[1] != '\0';
}

dir_res_t
walk_dirtree (const char* start, int depth) {
    struct dirent* dir;
    dir_res_t stats = {0};

    DIR* dirstream = opendir (start);
    if (dirstream == NULL) {
        unix_error ("Failed to open dirstream"); 
    }
    while ((dir = readdir(dirstream)) != NULL) {
        if (self_ref (dir->d_name) || hidden(dir->d_name))
            continue;
        // print directory name indented
        printf ("%*c%s\n", depth, ' ', dir->d_name);
        if (dir->d_type == DT_DIR) { 
            if (chdir(dir->d_name) == -1)
                unix_error ("Failed to go deeper");

            dir_res_t d_res = walk_dirtree (".", depth + INDENT_SIZE);
            stats.num_files += d_res.num_files;
            stats.num_dir   += d_res.num_dir + 1;

            if (chdir ("..") == -1)
                unix_error ("Failed to go back up");
        } else {
            stats.num_files += 1;
        }
    }
    if (closedir (dirstream)) {
        unix_error ("Failed to close dirstream");
    }

    return stats;
}


int 
main (int argc, char** argv) {
    dir_res_t stats = walk_dirtree (".", 0);
    printf ("%d directories, %d directories\n", stats.num_dir, stats.num_files);
    return 0;
}
*****
Written by Henry J Schmale on 2018 September 30