[Mesa-dev] [PATCH 3/5] mesa: Import a copy of the open-addressing hash table code I wrote.

[Eric Anholt]

Chad Versace <chad.versace at linux.intel.com> writes:

> I look forward to seeing this improved hash table land.
>
> Great that it includes tests. I failed to find a test that artificially
> constructed collisions and verified that they were handled correctly.
> Maybe I'll submit a test for that.
>
> Comments below. Everything looked correct, so my review mostly asks for
> an occasional clarifying comment.

> The while condition looks mystic. A comment here would be nice
> explaining that we break the loop because we've cycled around to the
> first probed address. Or simply a self-documenting variable name would
> suffice.

Check out the new version and see if it clarified.

>> +/**
>> + * Quick FNV-1 hash implementation based on:
>> + * http://www.isthe.com/chongo/tech/comp/fnv/
>> + *
>> + * FNV-1 is not be the best hash out there -- Jenkins's lookup3 is supposed to
>> + * be quite good, and it probably beats FNV.  But FNV has the advantage that
>> + * it involves almost no code.  For an improvement on both, see Paul
>> + * Hsieh's //www.azillionmonkeys.com/qed/hash.html
>> + */
>> +uint32_t
>> +_mesa_hash_data(const void *key, size_t size)
>
> This prototype differs from the one in hash_table.h:
>     _mesa_hash_data(const void *data, size_t size);
> Should it be 'data' or 'key'?

Meh, you're hashing the data in a key.  Arbitrarily picked one to be
consistent and renamed the local var to something else.

>> +/** FNV-1 string hash implementation */
>> +uint32_t
>> +_mesa_hash_string(const void *key)
>
> I expect the signature here to be _mesa_hash_string(const char *key). I believe
> using void* will result in a future misuse of the function that would have been
> caught by the type system.
>
> Why did you choose void*?

Probably I was originally typing a function that was the
_mesa_hash_data() variant.  Fixed.

>> +bool
>> +_mesa_key_string_equal(const void *a, const void *b)
>> +{
>> +   return strcmp(a, b) == 0;
>> +}
>
>
> As for _mesa_key_string_equal(), a comment here would be nice stating
> that _mesa_key_value_equal() function is intended to be passed to
> _mesa_hash_table_create().
>
> Also, I find the name of this function very confusing. "It's comparing
> the values of what? The pointers? The pointed-to's? How does it compare
> the pointed-to's of void pointers?" I think renaming this to
> _mesa_key_pointer_equal() makes it immediately clear what this function does:
> it compares pointers.

Yeah, for the current use case the things compared are actually uint32s
stuffed into a pointer, which resulted in the name I had before.  Still,
I think it's an improvement.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20121106/5511992e/attachment-0001.pgp>