[fuse-devel] How to index?

[Stef B. <st...@gm...>]

Hi,

I'm looking for a way to index entries to:

a. enable lookup based upon parent ino and name.

Much functions like lookup and mknod use the parent ino and the name,
so a lookup function based upon parent ino and name is required here.

b. get the directory entries given the parent ino.

A readdir with no backend (pure virtual) requires a function to get
the entries based upon ino (and entry->parent==parent).

Do any of you have some idea to do this?
I'm thinking about an hash table:

struct entry_struct **name_hash_table

and

name_hash_table=calloc(maxsize, sizeof(struct entry_struct *))

Now every entry should have a field like:

entry->nameindex_next
entry->nameindex_prev

of type entry_struct

So

ino % maxsize

points to a ordered double linked list of entries.

Now it's possible to search through this list using the search "in the
middle" and compare the entry found.
If bigger, take the upperhalf, and lower take the lower half and so on.
(there is a name for it I do not know anymore..)

Now this will work, but is silly. You have to compare names over and
over again. For example:

let's take an ordered list where the first name starts with a a, and
the latest name with a z.
Now I've got an name starting with a c. So when doing a lookup using
the above algoritm, it will look
in the middle between a and z, while of course it's much better to get
a value much closer
to a than to z:

a + 26 * (c-a) / (z -a )

when you expect the data is ordered random.

Now here only the first letter is used. Much better would be the first
3 or 4 letters, not all I think, I don't know.

Does anyone have some experience or advice?

Stef Bon