2
\$\begingroup\$

A recent post on StackOverflow about a recursive directory listing which produced an unsorted mixed file/directory list, sparked the stray thought of "What would it take to write a wrapper for the recursive call to produce a sorted listing with directories sorted first?" (this rabbit trail followed...)

In addition to the general code review for any glaring efficiency bottlenecks or obvious mistakes, a specific question would be does it need a check for the number of open file-descriptors, similar to the ftw/nftw parameter nopenfd.

The following example takes the directory path to list as the first argument (defaulting to "." if none given) to provide directory listing sorted ascending with the directories listed first, and optionally a second argument (it doesn't matter what it is) that triggers a descending sort with the directories listed first.

The wrapper function listdir takes the path as its first parameter and a function pointer to the qsort compare function to be used and returns an allocated array of pointers to char with a sentinel NULL marking the end of pointers pointing to an allocated and filled filename. Since the pointer to pointer was declared and initially allocated in the wrapper, calling the actual listdir_read function required just sucking it up and becoming a 3-star programmer (if there is a better way to handle this, that would be another point, but it seemed justified here)

The rest is commented and fairly self-explanatory. The qsort compare functions, just iterate past any leading "." or ".." and checks whether either of the paths being compared contains a second directory separator while the other does not and sorts the directory before the filename. Otherwise it is just a simple strcmp of the adjacent filenames.

The code:

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

#define INITDSZ 64      /* initial number of pointers to allocate */

#ifndef PATH_MAX        /* fallback definition for PATH_MAX */
#define PATH_MAX 4096
#endif

/* file/dir name comparison - ascending (sort dirs first) */
int sort_ascending (const void *a, const void *b) {
    const char  *pa = *(char * const *)a,
                *pb = *(char * const *)b,
                *hasdira = NULL,
                *hasdirb = NULL;

    while (*pa == '.')                  /* scan past "." and ".." */
        pa++;
    while (*pb == '.')
        pb++;

    hasdira = strchr (pa + 1, '/');     /* check for 2nd '/' */
    hasdirb = strchr (pb + 1, '/');

    if (hasdira && !hasdirb)            /* sort dirs before files */
        return -1;
    else if (!hasdira && hasdirb)
        return 1;

    return strcmp (*(char * const *)a, *(char * const *)b);
}

/* file/dir name comparison - descending (sort dirs first) */
int sort_descending (const void *a, const void *b) {
    const char  *pa = *(char * const *)a,
                *pb = *(char * const *)b,
                *hasdira = NULL,
                *hasdirb = NULL;

    while (*pa == '.')                  /* scan past "." and ".." */
        pa++;
    while (*pb == '.')
        pb++;

    hasdira = strchr (pa + 1, '/');     /* check for 2nd '/' */
    hasdirb = strchr (pb + 1, '/');

    if (hasdira && !hasdirb)            /* sort dirs before files */
        return -1;
    else if (!hasdira && hasdirb)
        return 1;

    return strcmp (*(char * const *)b, *(char * const *)a);
}

/* listdir_read - recursive read of directory storing entires in contents.
 * listdir_read recursively loops over directory entries beginning with
 * the last directory entry in contents. nptrs is a pointer to the currently
 * allocated number of pointers in contents and n is the current used number
 * of pointers. storage is allocated for each file/directory and each entry
 * added to contents to preserve entries for sorting, and each diretory is
 * recursed into to gather subdirectory entries. reallocation occurs as
 * needed.
 */
void listdir_read (char ***contents, size_t *nptrs, size_t *n)
{
    char *path = (*contents)[*n - 1];   /* pointer to current path */
    DIR *dir;
    struct dirent *entry;

    if (!(dir = opendir(path))) {       /* open/validate directory */
        perror ("opendir-path not found");
        return;
    }

    while ((entry = readdir(dir))) {    /* loop over each entry */

        char *name = entry->d_name;
        size_t  len = strlen (name),
                pathlen = strlen (path),
                entrylen = pathlen + len + 1;   /* +1 for '/' */

        if (*n + 1 == *nptrs) { /* realloc, preserving sentinel NULL */
            void *tmp = realloc (*contents, 2 * *nptrs * sizeof **contents);
            if (!tmp) {         /* validate */
                perror ("listdir_read() realloc-*contents");
                return;
            }
            *contents = tmp;    /* assign new block, zero pointers */
            memset (*contents + *nptrs, 0, *nptrs * sizeof **contents);
            *nptrs *= 2;        /* update number of allocated pointers */
        }

        if (entry->d_type == DT_DIR)    /* if "." or ".." skip */
            if (!strcmp(name, ".") || !strcmp(name, ".."))
                continue;

        (*contents)[*n] = malloc (entrylen + 1);    /* allocate storage */
        if (!(*contents)[*n]) { /* validate */
            perror ("listdir_read() malloc-(*contents)[*n]");
            return;
        }

        sprintf ((*contents)[(*n)++], "%s/%s", path, name); /* fill entry */

        if (entry->d_type == DT_DIR)    /* if is directory, recurse */
            listdir_read (contents, nptrs, n);
    }
    closedir (dir);     /* close directory */
}

/* wrapper for listdir_read, takes path and qsort compare function.
 * returns allocated/sorted pointers to entries on success, NULL otherwise.
 */
char **listdir (char *path, int (*cmp)(const void*, const void*))
{
    size_t len, n = 0, nptrs = INITDSZ;
    char **contents = calloc (nptrs, sizeof *contents); /* allocate nptrs */

    if (!contents) {    /* validate */
        perror ("listdir() calloc-contents");
        return NULL;
    }

    len = strlen (path);
    contents[n] = malloc (len + 1); /* allocate storage for 1st entry */
    if (!contents[n]) { /* validate */
        perror ("listdir() malloc-contents[n]");
        return NULL;
    }
    strcpy (contents[n++], path);   /* copy path as first entry */

    listdir_read (&contents, &nptrs, &n);   /* call listdir_read */

    qsort (contents, n, sizeof *contents, cmp);  /* sort contents */

    return contents;
}

/* read path provided as argv[1] or present working directory by default.
 * sort ascending with directories sorted first by default, or descending 
 * if any agrv[2] provided.
 */
int main (int argc, char **argv) {

    char path[PATH_MAX],
        **contents = NULL;

    if (argc > 1)
        strcpy (path, argv[1]);
    else
        *path = '.', path[1] = 0;

    if (argc > 2)
        contents = listdir (path, sort_descending);
    else
        contents = listdir (path, sort_ascending);

    if (contents) {
        char **p = contents;
        while (*p) {
            puts (*p);
            free (*p++);    /* free entries */
        }
        free (contents);    /* free pointers */
    }

    return 0;
}

valgrind gives the code a clean bill of health on memory handling (though I've only run it against 15 or so subdirectories with ~5500 files). The memory required was approximately 1.8M for that number of files and directories. Execution time seems quite good.

Look things over and let me have the good, the bad and the ugly.

\$\endgroup\$
  • \$\begingroup\$ I needed to define _DEFAULT_SOURCE when compiling, otherwise DT_DIR is undefined (on GNU/Linux). \$\endgroup\$ – Toby Speight Feb 14 at 9:32
  • \$\begingroup\$ Wow, thanks. I compiled both on OpenSuSE w/gcc 4.8.5 and on Archlinux with gcc 8.2.1 and never got a peep out of the compiler. Ahah! I used -std=gnu11, but with -std=c11 it behaves as you report. \$\endgroup\$ – David C. Rankin Feb 14 at 10:02
1
\$\begingroup\$

Possible bug

while (*pa == '.')                  /* scan past "." and ".." */
    pa++;

This also scans past ... and ...., which are perfectly valid filenames.

Locale

This program always sorts using the C locale. We should instead order as the user prefers, by setting locale from environment in main():

setlocale(LC_ALL, "");

and then using strcoll rather than strcmp to order strings.

Directory-first isn't recursive

I was surprised to get this output:

./a/A
./b/B
./b/x
./b/x/X
./b/y
./b/y/Y
./c/C
.
./a
./b
./c

Why is the file b/B shown before directory b/x? I'd expected the directory-first rule to be applied recursively, too.

Duplication

The sort_ascending and sort_descending functions are almost identical. I'd be inclined to refactor out the common part:

static int sort_bydir (const char  *pa, const char *pb)
{
    /* scan past "." and ".." */
    if (*pa == '.') ++pa;
    if (*pa == '.') ++pa;

    if (*pb == '.') ++pb;
    if (*pb == '.') ++pb;

    const char *hasdira = strchr (pa + 1, '/');     /* check for 2nd '/' */
    const char *hasdirb = strchr (pb + 1, '/');

    return (!hasdira && hasdirb) - (hasdira && !hasdirb);
}

Then the two functions are greatly simplified:

/* file/dir name comparison - ascending (sort dirs first) */
int sort_ascending (const void *a, const void *b) {
    const char *pa = *(char *const *)a;
    const char *pb = *(char *const *)b;

    int bydir = sort_bydir(pa, pb);
    return bydir ? bydir : strcoll(pa, pb);
}

/* file/dir name comparison - descending (sort dirs first) */
int sort_descending (const void *a, const void *b) {
    const char *pa = *(char *const *)a;
    const char *pb = *(char *const *)b;

    int bydir = sort_bydir(pa, pb);
    return bydir ? bydir : strcoll(pb, pa);
}

Improve the error checking

If we fail, we perror() but still continue to write incomplete (misleading) results. I think it would be better to emit only the error message in these cases.

Using perror() following memory allocation failure is misleading, as these functions don't set errno.

We forgot to check readdir() for error:

If an error occurs, NULL is returned and errno is set appropriately. To distinguish end of stream and from an error, set errno to zero before calling readdir() and then check the value of errno if NULL is returned.

Cope with absence of d_type field

Not all readdir() implementations provide file type information, and even on systems which do, you can't assume it's populated. The GNU man page says:

Only the fields d_name and (as an XSI extension) d_ino are specified in POSIX.1. Other than Linux, the d_type field is available mainly only on BSD systems. The remaining fields are available on many, but not all systems. Under glibc, programs can check for the availability of the fields not defined in POSIX.1 by testing whether the macros _DIRENT_HAVE_D_NAMLEN, _DIRENT_HAVE_D_RECLEN, _DIRENT_HAVE_D_OFF, or _DIRENT_HAVE_D_TYPE are defined.

It also says:

Currently, only some filesystems (among them: Btrfs, ext2, ext3, and ext4) have full support for returning the file type in d_type. All applications must properly handle a return of DT_UNKNOWN.

This means that we must be prepared to fall back to lstat() if _DIRENT_HAVE_D_TYPE is undefined or if entry->d_type == DT_UNKNOWN.

\$\endgroup\$
  • \$\begingroup\$ I think we can probably sort each subdir separately, rather than a single big qsort() at the end - I'll come back to this later if I can. \$\endgroup\$ – Toby Speight Feb 14 at 10:44
  • \$\begingroup\$ Toby, great feedback. I like the sort refactor to simplify. The error checking can always be improved, what is there is what I put in it when I was toying with the idea before I even considered posting it here. The absence of the d_type field is something I considered, using an atomic call to open with O_DIRECTORY | O_RDONLY flags, but hadn't implemented it yet. The sort issues is a good point. Currently it sorts the total results at once, bu a sort on a per-directory basis would work for the subs, but presents a pickle when then sorting the parent (files before/after the sorted subs) \$\endgroup\$ – David C. Rankin Feb 14 at 14:17
  • \$\begingroup\$ Oh yes, no need to lstat(). Perhaps a simpler approach is to opendir() everything and handle "not a directory" to mean a leaf node? And then add back using d_type if available, as an optimisation. \$\endgroup\$ – Toby Speight Feb 14 at 14:24
  • \$\begingroup\$ Yes, I've been playing with the sort and there isn't a clean way to do a sort at the end. So it looks like I'll need to append a '/' to the directory before recursing. That will fix the toplevel sort, but it looks like a btree variant will be needed to handle forcing a dirs first sort throughout. For error handling I just changed listdir_read from void to int returning 0 on failure wrapping the recursive call in if (!listdir_read (contents, nptrs, n)) { closedir (dir); return 0; } that allows the recursion to unwind after failure. Thanks for your help. \$\endgroup\$ – David C. Rankin Feb 14 at 18:20
  • \$\begingroup\$ A further point on error checking - we can't assume that directory entries won't change between us reading the entry and following the filename. Murphy's Law says that somebody will be renaming files as we're running! \$\endgroup\$ – Toby Speight Feb 19 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.