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

Question

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

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

第一种方法的问题是,如果目录路径的长度足够大,那么将包含它的字符串传递给opendir()的成本将超过打开目录的成本.如果你有点理论上的话,可以说你的复杂性可能超过线性时间(在目录树中(相对)文件名的总字符数).

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

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

Answer 1

您是否尝试过ftw()又名文件树径？

Snippit来自man 3 ftw:

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

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

Answer 2

您似乎缺少一个基本点:目录遍历涉及从磁盘读取数据.即使/如果该数据在缓存中,您最终也会通过相当数量的代码将缓存中的数据导入您的流程.路径通常也很短 - 任何超过几百个字节都是非常不寻常的.这些意味着您可以非常合理地为所需的所有路径构建字符串,而不会出现任何实际问题.与从磁盘读取数据的时间相比,构建字符串所花费的时间仍然很少.这意味着您通常可以忽略在字符串操作上花费的时间,并专门用于优化磁盘使用.

我自己的经验是,对于大多数目录遍历,广度优先搜索通常是可取的 - 当您遍历当前目录时,将所有子目录的完整路径放在类似优先级队列的内容中.遍历当前目录后,从队列中拉出第一个项目并遍历它,继续直到队列为空.这通常可以改善缓存局部性,因此可以减少读取磁盘所花费的时间.它取决于系统(磁盘速度与CPU速度,可用总内存等),它几乎总是至少与深度优先遍历一样快,并且可以轻松地达到两倍(或左右).

Answer 3

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

希望这可以帮助。

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