19

C 例程 opendir()、readdir() 和 closedir() 为我提供了一种遍历目录结构的方法。但是，readdir() 返回的每个 dirent 结构似乎都没有为我提供一种有用的方法来获取指向 DIR 的指针集，我需要递归到目录子目录中。

当然，他们给了我文件的名称，所以我可以将该名称附加到目录路径和 stat() 和 opendir() 它们，或者我可以通过 chdir() 更改进程的当前工作目录并滚动它通过 chdir("..") 返回。

第一种方法的问题是，如果目录路径的长度足够大，那么将包含它的字符串传递给 opendir() 的成本将超过打开目录的成本。如果您更具理论性，则可以说您的复杂性可能会增加超过线性时间（在目录树中（相对）文件名的总字符数中）。

此外，第二种方法存在问题。由于每个进程都有一个当前工作目录，因此除了一个线程之外的所有线程都必须在多线程应用程序中阻塞。另外，我不知道当前工作目录是否只是为了方便（即，在文件系统查询之前，相对路径将附加到它上面）。如果是这样，这种方法也将是低效的。

我接受这些功能的替代品。那么如何有效地遍历 UNIX 目录树（其下文件的总字符数的线性时间）？

4

5 回答 5

16

您是否尝试过ftw()又名File Tree Walk？

片段来自man 3 ftw：

int ftw(const char *dir, int (*fn)(const char *file, const struct stat *sb, int flag), int nopenfd);

ftw() 从指定的目录 dir 开始遍历目录树。对于树中找到的每个条目，它使用条目的完整路径名、指向条目的 stat(2) 结构的指针和 int 标志调用 fn()

于 2010-02-22T20:08:15.770 回答
5

您似乎遗漏了一个基本点：目录遍历涉及从磁盘读取数据。即使/如果该数据在缓存中，您最终也会通过大量代码将其从缓存中获取到您的进程中。路径通常也很短——超过几百个字节是很不寻常的。这些一起意味着您可以非常合理地为您需要的所有路径构建字符串，而不会出现任何实际问题。与从磁盘读取数据的时间相比，构建字符串所花费的时间仍然非常少。这意味着您通常可以忽略花在字符串操作上的时间，而专门致力于优化磁盘使用。

我自己的经验是，对于大多数目录遍历来说，广度优先搜索通常更可取——当您遍历当前目录时，将所有子目录的完整路径放在优先级队列中。当您完成遍历当前目录时，从队列中拉出第一个项目并遍历它，继续直到队列为空。这通常会提高缓存局部性，从而减少读取磁盘所花费的时间。根据系统（磁盘速度与 CPU 速度、可用总内存等）的不同，它几乎总是至少与深度优先遍历一样快，并且可以轻松达到两倍（左右）。

于 2010-02-22T16:28:07.963 回答
4

opendir//的使用方式readdir就是closedir让函数递归！看看Dreamincode.net上的代码片段。

希望这可以帮助。

编辑感谢 R.Sahu，linky 已过期，但是，通过wayback 存档找到它并冒昧地将其添加到gist。请记住，相应地检查许可证并注明出处为原作者！:)

于 2010-02-22T16:14:41.160 回答
2

可能对您的应用程序来说太过分了，但这是一个旨在遍历包含数亿个文件的目录树的库。

https://github.com/hpc/libcircle

于 2012-02-09T16:42:00.023 回答
0

代替opendir()，您可以使用 、 和 的组合openat()，dirfd()并fdopendir()构造一个递归函数来遍历目录树：

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

void
dir_recurse (DIR *parent, int level)
{
    struct dirent *ent;
    DIR *child;
    int fd;

    while ((ent = readdir(parent)) != NULL) {
        if ((strcmp(ent->d_name, ".") == 0) ||
            (strcmp(ent->d_name, "..") == 0)) {
            continue;
        }
        if (ent->d_type == DT_DIR) {
            printf("%*s%s/\n", level, "", ent->d_name);
            fd = openat(dirfd(parent), ent->d_name, O_RDONLY | O_DIRECTORY);
            if (fd != -1) {
                child = fdopendir(fd);
                dir_recurse(child, level + 1);
                closedir(child);
            } else {
                perror("open");
            }
        } else {
            printf("%*s%s\n", level, "", ent->d_name);
        }
    }
}

int
main (int argc, char *argv)
{
    DIR *root;

    root = opendir(".");
    dir_recurse(root, 0);
    closedir(root);

    return 0;
}

这里readdir()仍然用于获取下一个目录条目。如果下一个条目是一个目录，那么我们找到父目录 fddirfd()并将其与子目录名称一起传递给openat(). 结果 fd 引用子目录。这被传递给fdopendir()返回DIR *子目录的指针，然后可以将其传递给我们的dir_recurse()位置，它再次对readdir()调用有效。

该程序在以.. 打印条目，每个目录级别缩进 1 个空格。目录以结尾打印/。

在 ideone 上。

于 2019-07-10T18:13:30.293 回答