algorithm - 遍历包含链接周期的目录树的有效方法

Question

有没有比跟踪已经访问过的文件更有效的方法来遍历包含链接周期的目录树？

例如，考虑遍历包含这些文件的目录：

symlink "parent" -> ".."
symlink "uh_oh" -> "/"
regular file "reg"
symlink "reg2" -> "reg"

Answer 1

根据您的第一个示例，您还应该跟踪哪些目录已被访问，但除此之外没有比为每个文件维护访问标志更好的解决方案。

如果有一种可移植的方式为已挂载的文件系统获取简短的唯一标识符，则维护标志会更容易。即使这样，您也需要考虑在扫描期间发生的挂载和卸载操作的后果，特别是因为如果文件系统树包含远程文件系统，这样的扫描可能需要相当长的时间。

理论上，您可以从界面中获取“文件系统 ID” stafvfs，但实际上这并不是完全可移植的。引用man statfsLinux 发行版：

没有人知道f_fsid应该包含什么……</p>

…一般的想法是f_fsid包含一些随机的东西，这样一对(f_fsid,ino)唯一地确定一个文件。一些操作系统使用（变体）设备号，或设备号与文件系统类型相结合。一些操作系统限制仅将 f_fsid 字段提供给超级用户（对非特权用户将其归零），因为当 NFS 导出时，该字段用于文件系统的文件句柄中，并且将其提供是安全问题。

后一种限制——对非特权用户显示f_fsid为 0——不违反上面引用的 Posix 标准，因为该标准包含一个非常普遍的免责声明：statvfs文件系统。”

Answer 2

树遍历算法保证您将访问目录下的每个文件，因此您可以维护搜索“根”列表，而不是跟踪单个文件：

• 将初始目录添加到根列表中
• 遍历每个搜索根的目录树
• 对于您找到的每个符号链接，检查它是否已包含在搜索根中。如果不是，请将其添加为新的搜索根。

这样，您将访问每个文件和目录，永远不会陷入循环，但可能会多次访问文件和目录。仅当您找到指向现有根的祖先的符号链接时，才会发生这种情况。为避免这样做，您可以在输入目录之前检查目录是否是搜索根目录。