saber - ¿Cómo hacer una recursiva lista de directorios en C en Linux?

saber cuantos archivos hay en un directorio c

Question

Necesito enumerar recursivamente todos los directorios y archivos en la programación C. He investigado FTW pero eso no está incluido con los 2 sistemas operativos que estoy usando (Fedora y Minix). Estoy empezando a tener un gran dolor de cabeza por todas las cosas diferentes que he leído en las últimas horas.

Si alguien sabe de un fragmento de código que podría mirar eso sería increíble, o si alguien puede darme una buena dirección sobre esto, estaría muy agradecido.

Answer 1

¿Por qué todos insisten en reinventar la rueda una y otra vez?

POSIX.1-2008 estandarizó la función nftw() , también definida en Single Unix Specification v4 (SuSv4), y disponible en Linux (glibc, man 3 nftw ), OS X y la mayoría de las variantes actuales de BSD. No es nuevo en absoluto.

Las opendir() / readdir() / closedir() ingenuamente casi nunca manejan los casos en que los directorios o archivos se mueven, renombran o borran durante el recorrido del árbol, mientras que nftw() debe manejarlos con gracia.

Como ejemplo, considere el siguiente programa en C que enumera el árbol de directorios que comienza en el directorio de trabajo actual, o en cada uno de los directorios nombrados en la línea de comandos, o solo los archivos nombrados en la línea de comando:

/* We want POSIX.1-2008 + XSI, i.e. SuSv4, features */
#define _XOPEN_SOURCE 700

/* Added on 2017-06-25:
   If the C library can support 64-bit file sizes
   and offsets, using the standard names,
   these defines tell the C library to do so. */
#define _LARGEFILE64_SOURCE
#define _FILE_OFFSET_BITS 64 

#include <stdlib.h>
#include <unistd.h>
#include <ftw.h>
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>

/* POSIX.1 says each process has at least 20 file descriptors.
 * Three of those belong to the standard streams.
 * Here, we use a conservative estimate of 15 available;
 * assuming we use at most two for other uses in this program,
 * we should never run into any problems.
 * Most trees are shallower than that, so it is efficient.
 * Deeper trees are traversed fine, just a bit slower.
 * (Linux allows typically hundreds to thousands of open files,
 *  so you''ll probably never see any issues even if you used
 *  a much higher value, say a couple of hundred, but
 *  15 is a safe, reasonable value.)
*/
#ifndef USE_FDS
#define USE_FDS 15
#endif

int print_entry(const char *filepath, const struct stat *info,
                const int typeflag, struct FTW *pathinfo)
{
    /* const char *const filename = filepath + pathinfo->base; */
    const double bytes = (double)info->st_size; /* Not exact if large! */
    struct tm mtime;

    localtime_r(&(info->st_mtime), &mtime);

    printf("%04d-%02d-%02d %02d:%02d:%02d",
           mtime.tm_year+1900, mtime.tm_mon+1, mtime.tm_mday,
           mtime.tm_hour, mtime.tm_min, mtime.tm_sec);

    if (bytes >= 1099511627776.0)
        printf(" %9.3f TiB", bytes / 1099511627776.0);
    else
    if (bytes >= 1073741824.0)
        printf(" %9.3f GiB", bytes / 1073741824.0);
    else
    if (bytes >= 1048576.0)
        printf(" %9.3f MiB", bytes / 1048576.0);
    else
    if (bytes >= 1024.0)
        printf(" %9.3f KiB", bytes / 1024.0);
    else
        printf(" %9.0f B  ", bytes);

    if (typeflag == FTW_SL) {
        char   *target;
        size_t  maxlen = 1023;
        ssize_t len;

        while (1) {

            target = malloc(maxlen + 1);
            if (target == NULL)
                return ENOMEM;

            len = readlink(filepath, target, maxlen);
            if (len == (ssize_t)-1) {
                const int saved_errno = errno;
                free(target);
                return saved_errno;
            }
            if (len >= (ssize_t)maxlen) {
                free(target);
                maxlen += 1024;
                continue;
            }

            target[len] = ''/0'';
            break;
        }

        printf(" %s -> %s/n", filepath, target);
        free(target);

    } else
    if (typeflag == FTW_SLN)
        printf(" %s (dangling symlink)/n", filepath);
    else
    if (typeflag == FTW_F)
        printf(" %s/n", filepath);
    else
    if (typeflag == FTW_D || typeflag == FTW_DP)
        printf(" %s//n", filepath);
    else
    if (typeflag == FTW_DNR)
        printf(" %s/ (unreadable)/n", filepath);
    else
        printf(" %s (unknown)/n", filepath);

    return 0;
}


int print_directory_tree(const char *const dirpath)
{
    int result;

    /* Invalid directory path? */
    if (dirpath == NULL || *dirpath == ''/0'')
        return errno = EINVAL;

    result = nftw(dirpath, print_entry, USE_FDS, FTW_PHYS);
    if (result >= 0)
        errno = result;

    return errno;
}

int main(int argc, char *argv[])
{
    int arg;

    if (argc < 2) {

        if (print_directory_tree(".")) {
            fprintf(stderr, "%s./n", strerror(errno));
            return EXIT_FAILURE;
        }

    } else {

        for (arg = 1; arg < argc; arg++) {
            if (print_directory_tree(argv[arg])) {
                fprintf(stderr, "%s./n", strerror(errno));
                return EXIT_FAILURE;
            }
        }

    }

    return EXIT_SUCCESS;
}

La mayoría del código anterior está en print_entry() . Su tarea es imprimir cada entrada de directorio. En print_directory_tree() , le nftw() a nftw() que lo llame por cada entrada de directorio que ve.

El único detalle ondulado a mano anterior es la decisión sobre cuántos descriptores de archivo uno debe permitir que nftw() . Si su programa utiliza como máximo dos descriptores de archivo adicionales (además de los flujos estándar) durante la caminata por el árbol de archivos, se sabe que 15 es seguro (en todos los sistemas que tienen nftw() y que son en su mayoría POSIX).

En Linux, puede usar sysconf(_SC_OPEN_MAX) para encontrar la cantidad máxima de archivos abiertos y restar el número que usa simultáneamente con la llamada nftw() , pero no me molestaría (a menos que supiera que la utilidad se usaría principalmente con estructuras de directorios patológicamente profundas). Quince descriptores no limitan la profundidad del árbol; nftw() simplemente se vuelve más lento (y puede no detectar cambios en un directorio si recorre un directorio más profundo que 13 directorios desde ese, aunque las compensaciones y la capacidad general para detectar cambios varían entre los sistemas y las implementaciones de la biblioteca C). El simple hecho de usar una constante de tiempo de compilación como esa mantiene el código portátil, debería funcionar no solo en Linux, sino también en Mac OS X y todas las variantes actuales de BSD, y en la mayoría de las demás variantes de Unix no demasiado antiguas.

En un comentario, Ruslan mencionó que tenían que cambiar a nftw64() porque tenían entradas de sistema de archivos que requerían tamaños / compensaciones de 64 bits, y la versión "normal" de nftw() fallaba con errno == EOVERFLOW . La solución correcta es no cambiar a funciones de 64 bits específicas de GLIBC, sino definir _LARGEFILE64_SOURCE y _FILE_OFFSET_BITS 64 . Estos le indican a la biblioteca C que cambie a tamaños de archivo de 64 bits y compensaciones si es posible, mientras usa las funciones estándar ( nftw() , fstat() , etcétera) y escribe nombres ( off_t etc.).

Answer 2

Aquí hay una versión recursiva:

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

void listdir(const char *name, int indent)
{
    DIR *dir;
    struct dirent *entry;

    if (!(dir = opendir(name)))
        return;

    while ((entry = readdir(dir)) != NULL) {
        if (entry->d_type == DT_DIR) {
            char path[1024];
            if (strcmp(entry->d_name, ".") == 0 || strcmp(entry->d_name, "..") == 0)
                continue;
            snprintf(path, sizeof(path), "%s/%s", name, entry->d_name);
            printf("%*s[%s]/n", indent, "", entry->d_name);
            listdir(path, indent + 2);
        } else {
            printf("%*s- %s/n", indent, "", entry->d_name);
        }
    }
    closedir(dir);
}

int main(void) {
    listdir(".", 0);
    return 0;
}

Answer 3

Aquí hay una versión simplificada que usa recursión pero usa mucho menos espacio de pila:

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

void listdir(char *path, size_t size) {
    DIR *dir;
    struct dirent *entry;
    size_t len = strlen(path);

    if (!(dir = opendir(path))) {
        fprintf(stderr, "path not found: %s: %s/n",
                path, strerror(errno));
        return;
    }

    puts(path);
    while ((entry = readdir(dir)) != NULL) {
        char *name = entry->d_name;
        if (entry->d_type == DT_DIR) {
            if (!strcmp(name, ".") || !strcmp(name, ".."))
                continue;
            if (len + strlen(name) + 2 > size) {
                fprintf(stderr, "path too long: %s/%s/n", path, name);
            } else {
                path[len] = ''/'';
                strcpy(path + len + 1, name);
                listdir(path, size);
                path[len] = ''/0'';
            }
        } else {
            printf("%s/%s/n", path, name);
        }
    }
    closedir(dir);
}

int main(void) {
    char path[1024] = ".";
    listdir(path, sizeof path);
    return 0;
}

En mi sistema, su salida es exactamente idéntica a la de find .

Answer 4

Como mencioné en mi comentario, creo que un enfoque recursivo tiene dos defectos inherentes a esta tarea.

El primer defecto es el límite en los archivos abiertos. Este límite impone un límite en el recorrido profundo. Si hay suficientes subcarpetas, el enfoque recursivo se romperá. ( Ver edición sobre desbordamiento de pila )

El segundo defecto es un poco más sutil. El enfoque recursivo hace que sea muy difícil probar los enlaces duros. Si un árbol de carpetas es cíclico (debido a los enlaces duros), el enfoque recursivo se romperá (con suerte sin un desbordamiento de la pila). ( Ver edición sobre enlaces duros )

Sin embargo, es bastante simple evitar estos problemas al reemplazar la recursión con un descriptor de archivo único y listas vinculadas.

Supongo que este no es un proyecto de la escuela y que la recursión es opcional.

Aquí hay una aplicación de ejemplo.

Use a.out ./ para ver el árbol de carpetas.

Me disculpo por las macros y esas cosas ... Usualmente uso funciones en línea, pero pensé que sería más fácil seguir el código si todo estuviera en una sola función.

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

int main(int argc, char const *argv[]) {
  /* print use instruction unless a folder name was given */
  if (argc < 2)
    fprintf(stderr,
            "/nuse:/n"
            "    %s <directory>/n"
            "for example:/n"
            "    %s .//n/n",
            argv[0], argv[0]),
        exit(0);

  /*************** a small linked list macro implementation ***************/

  typedef struct list_s {
    struct list_s *next;
    struct list_s *prev;
  } list_s;

#define LIST_INIT(name)                                                        /
  { .next = &name, .prev = &name }

#define LIST_PUSH(dest, node)                                                  /
  do {                                                                         /
    (node)->next = (dest)->next;                                               /
    (node)->prev = (dest);                                                     /
    (node)->next->prev = (node);                                               /
    (dest)->next = (node);                                                     /
  } while (0);

#define LIST_POP(list, var)                                                    /
  if ((list)->next == (list)) {                                                /
    var = NULL;                                                                /
  } else {                                                                     /
    var = (list)->next;                                                        /
    (list)->next = var->next;                                                  /
    var->next->prev = var->prev;                                               /
  }

  /*************** a record (file / folder) item type ***************/

  typedef struct record_s {
    /* this is a flat processing queue. */
    list_s queue;
    /* this will list all queued and processed folders (cyclic protection) */
    list_s folders;
    /* this will list all the completed items (siblings and such) */
    list_s list;
    /* unique ID */
    ino_t ino;
    /* name length */
    size_t len;
    /* name string */
    char name[];
  } record_s;

/* take a list_s pointer and convert it to the record_s pointer */
#define NODE2RECORD(node, list_name)                                           /
  ((record_s *)(((uintptr_t)(node)) -                                          /
                ((uintptr_t) & ((record_s *)0)->list_name)))

/* initializes a new record */
#define RECORD_INIT(name)                                                      /
  (record_s){.queue = LIST_INIT((name).queue),                                 /
             .folders = LIST_INIT((name).folders),                             /
             .list = LIST_INIT((name).list)}

  /*************** the actual code ***************/

  record_s records = RECORD_INIT(records);
  record_s *pos, *item;
  list_s *tmp;
  DIR *dir;
  struct dirent *entry;

  /* initialize the root folder record and add it to the queue */
  pos = malloc(sizeof(*pos) + strlen(argv[1]) + 2);
  *pos = RECORD_INIT(*pos);
  pos->len = strlen(argv[1]);
  memcpy(pos->name, argv[1], pos->len);
  if (pos->name[pos->len - 1] != ''/'')
    pos->name[pos->len++] = ''/'';
  pos->name[pos->len] = 0;
  /* push to queue, but also push to list (first item processed) */
  LIST_PUSH(&records.queue, &pos->queue);
  LIST_PUSH(&records.list, &pos->list);

  /* as long as the queue has items to be processed, do so */
  while (records.queue.next != &records.queue) {
    /* pop queued item */
    LIST_POP(&records.queue, tmp);
    /* collect record to process */
    pos = NODE2RECORD(tmp, queue);
    /* add record to the processed folder list */
    LIST_PUSH(&records.folders, &pos->folders);

    /* process the folder and add all folder data to current list */
    dir = opendir(pos->name);
    if (!dir)
      continue;

    while ((entry = readdir(dir)) != NULL) {

      /* create new item, copying it''s path data and unique ID */
      item = malloc(sizeof(*item) + pos->len + entry->d_namlen + 2);
      *item = RECORD_INIT(*item);
      item->len = pos->len + entry->d_namlen;
      memcpy(item->name, pos->name, pos->len);
      memcpy(item->name + pos->len, entry->d_name, entry->d_namlen);
      item->name[item->len] = 0;
      item->ino = entry->d_ino;
      /* add item to the list, right after the `pos` item */
      LIST_PUSH(&pos->list, &item->list);

      /* unless it''s a folder, we''re done. */
      if (entry->d_type != DT_DIR)
        continue;

      /* test for ''.'' and ''..'' */
      if (entry->d_name[0] == ''.'' &&
          (entry->d_name[1] == 0 ||
           (entry->d_name[1] == ''.'' && entry->d_name[2] == 0)))
        continue;

      /* add folder marker */
      item->name[item->len++] = ''/'';
      item->name[item->len] = 0;

      /* test for cyclic processing */
      list_s *t = records.folders.next;
      while (t != &records.folders) {
        if (NODE2RECORD(t, folders)->ino == item->ino) {
          /* we already processed this folder! */
          break; /* this breaks from the small loop... */
        }
        t = t->next;
      }
      if (t != &records.folders)
        continue; /* if we broke from the small loop, entry is done */

      /* item is a new folder, add to queue */
      LIST_PUSH(&records.queue, &item->queue);
    }
    closedir(dir);
  }

  /*************** Printing the results and cleaning up ***************/
  while (records.list.next != &records.list) {
    /* pop list item */
    LIST_POP(&records.list, tmp);
    /* collect record to process */
    pos = NODE2RECORD(tmp, list);
    /* prepare for next iteration */
    LIST_POP(&records.list, tmp);
    fwrite(pos->name, pos->len, 1, stderr);
    fwrite("/n", 1, 1, stderr);
    free(pos);
  }
  return 0;
}

EDITAR

@Stargateur mencionó en los comentarios que el código recursivo probablemente desbordará la pila antes de alcanzar el límite de archivo abierto.

Aunque no veo cómo un desbordamiento de pila es mejor, esta evaluación probablemente sea correcta siempre que el proceso no se acerque al límite del archivo cuando se invoca.

Otro punto mencionado por @Stargateur en los comentarios fue que la profundidad del código recursivo está limitada por la cantidad máxima de subdirectorios (64000 en el sistema de archivos ext4) y que los enlaces duros son extremadamente improbables (ya que los enlaces duros a las carpetas no son permitido en Linux / Unix).

Esta es una buena noticia si el código se ejecuta en Linux (que es, según la pregunta), por lo que este problema no es una preocupación real (a menos que se ejecute el código en macOS o, tal vez, en Windows) ... aunque 64K subcarpetas en recursión podría explotar la pila de par en par.

Habiendo dicho eso, la opción no recursiva todavía tiene ventajas, como ser capaz de agregar fácilmente un límite a la cantidad de elementos procesados, así como poder almacenar en caché el resultado.

PD

Según los comentarios, aquí hay una versión no recursiva del código que no verifica las jerarquías cíclicas. Es más rápido y debe ser lo suficientemente seguro como para usarlo en una máquina Linux donde no se permiten los enlaces duros a las carpetas.

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

int main(int argc, char const *argv[]) {
  /* print use instruction unless a folder name was given */
  if (argc < 2)
    fprintf(stderr,
            "/nuse:/n"
            "    %s <directory>/n"
            "for example:/n"
            "    %s .//n/n",
            argv[0], argv[0]),
        exit(0);

  /*************** a small linked list macro implementation ***************/

  typedef struct list_s {
    struct list_s *next;
    struct list_s *prev;
  } list_s;

#define LIST_INIT(name)                                                        /
  { .next = &name, .prev = &name }

#define LIST_PUSH(dest, node)                                                  /
  do {                                                                         /
    (node)->next = (dest)->next;                                               /
    (node)->prev = (dest);                                                     /
    (node)->next->prev = (node);                                               /
    (dest)->next = (node);                                                     /
  } while (0);

#define LIST_POP(list, var)                                                    /
  if ((list)->next == (list)) {                                                /
    var = NULL;                                                                /
  } else {                                                                     /
    var = (list)->next;                                                        /
    (list)->next = var->next;                                                  /
    var->next->prev = var->prev;                                               /
  }

  /*************** a record (file / folder) item type ***************/

  typedef struct record_s {
    /* this is a flat processing queue. */
    list_s queue;
    /* this will list all the completed items (siblings and such) */
    list_s list;
    /* unique ID */
    ino_t ino;
    /* name length */
    size_t len;
    /* name string */
    char name[];
  } record_s;

/* take a list_s pointer and convert it to the record_s pointer */
#define NODE2RECORD(node, list_name)                                           /
  ((record_s *)(((uintptr_t)(node)) -                                          /
                ((uintptr_t) & ((record_s *)0)->list_name)))

/* initializes a new record */
#define RECORD_INIT(name)                                                      /
  (record_s){.queue = LIST_INIT((name).queue), .list = LIST_INIT((name).list)}

  /*************** the actual code ***************/

  record_s records = RECORD_INIT(records);
  record_s *pos, *item;
  list_s *tmp;
  DIR *dir;
  struct dirent *entry;

  /* initialize the root folder record and add it to the queue */
  pos = malloc(sizeof(*pos) + strlen(argv[1]) + 2);
  *pos = RECORD_INIT(*pos);
  pos->len = strlen(argv[1]);
  memcpy(pos->name, argv[1], pos->len);
  if (pos->name[pos->len - 1] != ''/'')
    pos->name[pos->len++] = ''/'';
  pos->name[pos->len] = 0;
  /* push to queue, but also push to list (first item processed) */
  LIST_PUSH(&records.queue, &pos->queue);
  LIST_PUSH(&records.list, &pos->list);

  /* as long as the queue has items to be processed, do so */
  while (records.queue.next != &records.queue) {
    /* pop queued item */
    LIST_POP(&records.queue, tmp);
    /* collect record to process */
    pos = NODE2RECORD(tmp, queue);

    /* process the folder and add all folder data to current list */
    dir = opendir(pos->name);
    if (!dir)
      continue;

    while ((entry = readdir(dir)) != NULL) {

      /* create new item, copying it''s path data and unique ID */
      item = malloc(sizeof(*item) + pos->len + entry->d_namlen + 2);
      *item = RECORD_INIT(*item);
      item->len = pos->len + entry->d_namlen;
      memcpy(item->name, pos->name, pos->len);
      memcpy(item->name + pos->len, entry->d_name, entry->d_namlen);
      item->name[item->len] = 0;
      item->ino = entry->d_ino;
      /* add item to the list, right after the `pos` item */
      LIST_PUSH(&pos->list, &item->list);

      /* unless it''s a folder, we''re done. */
      if (entry->d_type != DT_DIR)
        continue;

      /* test for ''.'' and ''..'' */
      if (entry->d_name[0] == ''.'' &&
          (entry->d_name[1] == 0 ||
           (entry->d_name[1] == ''.'' && entry->d_name[2] == 0)))
        continue;

      /* add folder marker */
      item->name[item->len++] = ''/'';
      item->name[item->len] = 0;

      /* item is a new folder, add to queue */
      LIST_PUSH(&records.queue, &item->queue);
    }
    closedir(dir);
  }

  /*************** Printing the results and cleaning up ***************/
  while (records.list.next != &records.list) {
    /* pop list item */
    LIST_POP(&records.list, tmp);
    /* collect record to process */
    pos = NODE2RECORD(tmp, list);
    /* prepare for next iteration */
    LIST_POP(&records.list, tmp);
    fwrite(pos->name, pos->len, 1, stderr);
    fwrite("/n", 1, 1, stderr);
    free(pos);
  }
  return 0;
}

Answer 5

int is_directory_we_want_to_list(const char *parent, char *name) {
  struct stat st_buf;
  if (!strcmp(".", name) || !strcmp("..", name))
    return 0;
  char *path = alloca(strlen(name) + strlen(parent) + 2);
  sprintf(path, "%s/%s", parent, name);
  stat(path, &st_buf);
  return S_ISDIR(st_buf.st_mode);
}

int list(const char *name) {
  DIR *dir = opendir(name);
  struct dirent *ent;
  while (ent = readdir(dir)) {
    char *entry_name = ent->d_name;
    printf("%s/n", entry_name);
    if (is_directory_we_want_to_list(name, entry_name)) {
      // You can consider using alloca instead.
      char *next = malloc(strlen(name) + strlen(entry_name) + 2);
      sprintf(next, "%s/%s", name, entry_name);
      list(next);
      free(next);
    }
  }
  closedir(dir);
}

Los archivos de encabezado merecen ser descremados en este contexto: stat.h , dirent.h . Tenga en cuenta que el código anterior no busca errores que puedan ocurrir.

Un enfoque completamente diferente lo ofrece ftw definido en ftw.h.