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

Question

是否有比跟踪哪些文件已被访问过更有效的方式来遍历包含链接循环的目录树？

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

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

Answer 1

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

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

理论上，您可以从 stafvfs 中获取“文件系统 ID”接口(interface)，但实际上并不完全可移植。从 Linux 发行版中引用 man statfs:

Nobody knows what f_fsid is supposed to contain…

…The general idea is that f_fsid contains some random stuff such that the pair (f_fsid,ino) uniquely determines a file. Some operating systems use (a variation on) the device number, or the device number combined with the filesystem type. Several OSes restrict giving out the f_fsid field to the superuser only (and zero it for unprivileged users), because this field is used in the filehandle of the filesystem when NFS-exported, and giving it out is a security concern.

后一种限制——f_fsid 对非特权用户显示为 0——并不违反上面引用的 Posix 标准，因为该标准包含一个非常通用的 disclaimer。 : "未指定 statvfs 结构的所有成员是否在所有文件系统上都具有有意义的值。"