On 4/10/07, Neil Brown <[EMAIL PROTECTED]> wrote:
2/ Some data structure using an ordered search key that is based on
the filename (e.g. a B-tree with a search key that is a hash of the
filename).
In the first case, you just use a fixed opaque cookie for location in
a directory.
In the second you use the filename. If the file has been deleted,
that shouldn't stop you finding the place where it would have been in
the overall sort order.
I can think of one (admittedly insane) FS that is between those two:
3/ an unsorted hash table, where each directory entry has an indirect
pointer to its neighbor in case of hash collisions.
a
b -> d -> c -> e
g
f -> x
Given 'c' as the "last" thing returned, you can hash c to find out
that you are in the bucket with 'b', but if 'c' was deleted, the best
you can do is return b twice or skip the chain entirely. I maintain
an out-of-tree driver for such an fs (I promise I did not invent it);
the best I could come up with is to encode the hash chain index in the
top byte of f_pos. Needless to say, readdir is very not performant
with all the seeking this hash scheme entails.
-Bob
-
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/
