如何在文件系统中找到循环？

Question

如何在Linux中找到文件系统中的循环？我正在索引所有文件以便快速搜索(O(1))...我正在使用c编程语言来实现dir.h中的库函数....我可以扫描整个文件系统但它进入一个循环,如果文件系统中有循环(示例循环安装)...如何在文件系统中找到循环..我已经看到当文件系统中有循环时updatedb命令报告...我不明白逻辑...任何人都可以帮忙找到解决方案吗？

Answer 1

阻止在图中重新扫描节点的一般方法是在传递节点时标记节点,然后忽略标记的节点.如果您不想修改要扫描的图形,这不是非常实用,因此您需要一种在外部标记节点的方法.我能想到在linux下执行此操作的最简单方法是为您访问的每个目录存储device/inode.然后,当您查看目录时,首先检查您是否还没有看到具有相同设备/ inode的任何目录.这不仅可以处理循环,还可以处理彼此合并的树.

要获取device/inode编号,请查看stat/fstat函数以及stat结构的st_dev和st_ino成员.

对于存储数据,您可能希望查看哈希表或二叉树.

Answer 2

我在这里发现了关于在 DAG 中查找循环的有趣评论：

斯坦纳尔·冈德森 (Steinar H. Gunderson) 写道：

2004 年 2 月 26 日星期四 00:28:32 +0100，Orlondow 写道：

...也转载于 Cormen-Leiserson-Rivest, IIC。哪个最容易找到。

是的，我实际上有 Cormen 等人，但当我想要循环检测时，我从来没有想到要查找“强连接组件”。谢谢，我会看一下。:-)

要在有向图中找到一个环（你不关心是哪个环），只要存在一个环，你就不需要过度使用 SCC。普通的老式深度优先搜索 DFS（在 CLRS 的同一章中）就足够了。

因此，粗略地说，当您遍历目录树时，创建一个表示树结构的 DAG，其中节点处的数据引用文件的 inode。然后，您只需检查以确保不会多次访问某个节点。