Re: Expected getdents behaviour

[Nikita Danilov <nikita@clusterfs.com>]

Theodore Ts'o writes:
 > On Thu, Sep 15, 2005 at 07:46:58PM +0200, J?rn Engel wrote:
 > > Correct.  But you're missing half of the problem.
 > > 
 > > The other half is getting O(1)  or O(ln(n)) performance for lookup on
 > > a large directory.  Solution to this half alone would be to use a
 > > balanced tree for directory entries.  Now, using a self-balancing tree
 > > would not solve your half of the problem, so it is not a full
 > > solution.
 > > 
 > > Ext2, as far as I understand it, solved both halves by having both a
 > > hashtree and the sequential list.  Getdents is walking the list and
 > > ignoring entries with the "deleted" flag.  Lookup is using the
 > > hashtree, which points to the list for actual data.
 > 
 > Actually, no.  What we do is return the directory entries in hash sort
 > order, by walking the btree.  And we use the hash as the offset
 > returned in d_off and via telldir().  The reason for this?  So that if
 > we add files which causes a node to split, that we still only return
 > files in the directory once and only once.  If we traversed the tree

Except for hash collided directory entries, that are returned multiple
times, because after seekdir() ext2_readdir() restarts from the start of
hash-bucket, right?

Nikita.