Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!clyde!ima!haddock!karl
From: karl@haddock.UUCP (Karl Heuer)
Newsgroups: comp.unix.wizards
Subject: Re: symbolic links are a botch
Message-ID: <637@haddock.UUCP>
Date: Sat, 27-Jun-87 15:51:44 EDT
Article-I.D.: haddock.637
Posted: Sat Jun 27 15:51:44 1987
Date-Received: Sun, 28-Jun-87 02:38:15 EDT
References: <7955@brl-adm.ARPA> <2249@bunker.UUCP> <634@haddock.UUCP>
Reply-To: karl@haddock.ISC.COM (Karl Heuer)
Organization: Interactive Systems, Boston
Lines: 18

In article <634@haddock.UUCP> karl@haddock.ISC.COM.UUCP (Karl Heuer) writes:
>There exists a loop detection algorithm which uses O(log(N)) space and O(N)
>time (it doesn't detect the loop immediately, but it does stop before the
>third visit of any node).  Why isn't this used [for ELOOP]?

Alright folks, stop sending me mail on this -- yes, I know it can be done in
O(1) space using the two-and-one algorithm, but that does not have the
property I mentioned.  For example, a -> b -> ... -> z -> z will require 75
link-traversals before the slower one catches up to the loop.  I was thinking
of the algorithm from HAKMEM, item 132.  The extra O(log(N)) space is
unimportant (32 words, since N < 2^32); the time savings is potentially more
valuable.  (Traversing a symlink is, I expect, an expensive operation.*)

Of course, either algorithm is better than the current hopcount=8 kludge.

Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
*Hmm... Y'know, symlink target names are usually so short -- maybe they could
be stored in the inode itself?  When they're less than 40 chars, say?