使用 opendir()、readdir() 和 closedir() 高效遍历目录树

Question

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

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

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

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

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

Answer 1

您尝试过

ftw()

又名文件树漫步吗？

来自

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()

Answer 2

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

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

Answer 3

使用

opendir

/

readdir

/

closedir

的方法就是让函数递归！在 Dreamincode.net 上查看代码片段。

希望这有帮助。

编辑感谢R.Sahu，链接已过期，但是，通过wayback archive找到了它，并冒昧地将其添加到gist。请记住，相应地检查许可证并注明来源的原始作者！ :)

Answer 4

您可以使用

opendir()

、

openat()

 和 

dirfd()

 的组合来代替 

fdopendir()，并构造一个递归函数来遍历目录树：

#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>

void dir_recurse (DIR *parent, int level) {
    struct dirent *ent;
    if (!parent) {
        return;
    }
    while ((ent = readdir(parent)) != NULL) {
        if ((strcmp(ent->d_name, ".") == 0) ||
            (strcmp(ent->d_name, "..") == 0)) {
            continue;
        }

        int parent_fd = dirfd(parent);
        if (parent_fd < 0) {
            perror("dirfd");
            continue;
        }
        int fd = openat(parent_fd, ent->d_name, O_RDONLY | O_DIRECTORY);
        if (fd != -1) { /* Directory */
            printf("%*s%s/\n", level, "", ent->d_name);
            DIR *child = fdopendir(fd);
            if (child) {
                dir_recurse(child, level + 1);
                closedir(child);
            } else {
                perror("fdopendir");
            }
        } else if (errno == ENOTDIR) { /* Regular file */
            printf("%*s%s\n", level, "", ent->d_name);
        } else {
            perror("openat");
        }
    }
}

int main (int argc, const char **argv) {
    DIR *root = opendir("..");
    if (root) {
        dir_recurse(root, 0);
        closedir(root);
    } else {
        perror("opendir");
    }

    return 0;
}

这里

readdir()

依然用来获取下一个目录项。如果下一个条目是一个目录，那么我们使用

dirfd()

找到父目录 fd 并将其与子目录名称一起传递给

openat()

。生成的 fd 引用子目录。它被传递到

fdopendir()

，它返回子目录的

DIR *

指针，然后可以将其传递到我们的

dir_recurse()

，在那里它将再次有效地用于

readdir()

调用。

此程序在以

..

为根的整个目录树上递归，打印条目，每个目录级别缩进 1 个空格。目录打印有尾随

/

。

在编译器资源管理器上。

Answer 5

对于您的应用程序来说可能有点大材小用，但这是一个旨在遍历包含数亿个文件的目录树的库。

https://github.com/hpc/libcircle