Re: [PATCH v5] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 09/16/2012 09:33 PM, Mathieu Desnoyers wrote:
>> How would you create a dynamic hashtable with this code to begin with?
> With a var. sized array in a structure, e.g.:
> 
> struct hashtable {
>         size_t len;
>         struct hlist_head t[];
> };
> 
> Then create a hash table allocation function, and turn both hash_empty
> and hash_init into functions that take a struct simplehash pointer as
> parameter. The downside is to consume extra space (especially because
> the array always has a power of 2 len), but the nice thing is that we
> could use this code with a kmalloc'd/vmalloc'd hash table.
> 
> I'm not saying we need to do it (due to the space consumption downside),
> but that we should at least document this limitation.

We've gone through the process of attempting to support dynamic hashtables in
the previous versions of this patch, this turned to complicate the code a lot
beyond simply changing the array of hlist_heads into the struct you proposed, so
it was decided to not support dynamic hashtables at this point at all.

I thought we've agreed that non-dynamically allocated hashtables are widespread
enough to have a dedicated abstraction of their own, and further hashtable
implementations may introduce their own API for that.

We can ofcourse open that for discussion again, but I'd rather not go back and
forth adding support for dynamic hashtables and removing it again.


Thanks,
Sasha
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/