Subject: Re: an in-kernel getcwd() implementation
To: Bill Sommerfeld <>
From: Ignatios Souvatzis <>
List: tech-kern
Date: 03/08/1999 10:42:47
On Sun, Mar 07, 1999 at 08:56:38PM -0500, Bill Sommerfeld wrote:
> > > It has to do with the use of per-process pointers into directories to
> > > prevent a loop stat'ing every file in a directory from taking O(n**2)
> > > time.  This can't help reverse lookups in any meaningful way.
> > 
> > O(n!), but still not nice.
> O(n!) is a lot bigger than O(n**2).

Whatever... if I'm not confusing caches, the caching code there was inserted
to make sequential loops through all directory entries take O(n) instead of
O(n**2). Sequential loops through all the directory are frequent enough and 
were formerly slow enough (O(n**2)) to ask for special case coding.