On Wed, 06 Jul 2005 23:42:50 -0700, Hans Reiser <[EMAIL PROTECTED]> said:
> Oh no, don't store the whole path, store just the parent list. This > will make fsck more robust in the event that the directory gets > clobbered by hardware error. > I don't think it affects the cost of detecting cycles though, I think > it only makes fsck more robust. It doesn't affect the worst-case cost of detecting cycles; by necessity, any (static [1]) directed cycle detection algorithm must take O(n) time, n being the size of the tree (nodes + links). However, under "reasonable assumptions" (where the reasonableness of those assumptions may be questioned, but I think they're reasonable), I think that doing a depth-first-search through the parent links makes the algorithm not-too-terrible. Namely, the "reasonable assumptions" are that a node doesn't have "too many" parents, and the filesystem hierarchy is not "too deep". [1] BTW, I had also previously looked at online/dynamic algorithms, for those who are familiar with that area. The best known so far is still O(n) worst case, but much, much smaller in "most cases". -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
