Tukukkk

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.