Here is what he came up with:
word32 one_at_a_time(unsigned char const *key, size_t len)
{
word32 hash = 0x9e3779b9; /* Or any arbitrary value */
size_t i;
for (i=0; i < len; ++i) {
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Pretty simple, but much more effective and thorough that
what's there now.
The last three steps are to make sure the low 10 bits or so,
as currently used, are an effective hash of the whole thing.
Obviously, if you're comparing all 32 bits, you don't need them.
A trickier question is where to include the parent dentry
pointer. The current code does this after the hash is computed
on the name. It could be added in using this algorithm, just
like it was a character, but that breaks some of the assumptions
the hash is based on.
An alternative which might do better is to include it at
the *beginning*, in the initial hash value.
Question: other than messing up the qstr abstraction, is there
any reason why the dcache can't just have one kind of hash,
a hash of the name plus the parent dentry?
-- -Colin- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/faq.html