[dm-devel] [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

[Mathieu Desnoyers]

* Tejun Heo (tj at kernel.org) wrote:
> Hello,
> 
> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> > Thats the thing, the amount of things of things you can do with a given bucket
> > is very limited. You can't add entries to any point besides the head (without
> > walking the entire list).
> 
> Kinda my point.  We already have all the hlist*() interface to deal
> with such cases.  Having something which is evidently the trivial
> hlist hashtable and advertises as such in the interface can be
> helpful.  I think we need that more than we need anything fancy.
> 
> Heh, this is a debate about which one is less insignificant.  I can
> see your point.  I'd really like to hear what others think on this.
> 
> Guys, do we want something which is evidently trivial hlist hashtable
> which can use hlist_*() API directly or do we want something better
> encapsulated?

My 2 cents, FWIW: I think this specific effort should target a trivially
understandable API and implementation, for use-cases where one would be
tempted to reimplement his own trivial hash table anyway. So here
exposing hlist internals, with which kernel developers are already
familiar, seems like a good approach in my opinion, because hiding stuff
behind new abstraction might make the target users go away.

Then, as we see the need, we can eventually merge a more elaborate hash
table with poneys and whatnot, but I would expect that the trivial hash
table implementation would still be useful. There are of course very
compelling reasons to use a more featureful hash table: automatic
resize, RT-aware updates, scalable updates, etc... but I see a purpose
for a trivial implementation. Its primary strong points being:

- it's trivially understandable, so anyone how want to be really sure
  they won't end up debugging the hash table instead of their
  work-in-progress code can have a full understanding of it,
- it has few dependencies, which makes it easier to understand and
  easier to use in some contexts (e.g. early boot).

So I'm in favor of not overdoing the abstraction for this trivial hash
table, and honestly I would rather prefer that this trivial hash table
stays trivial. A more elaborate hash table should probably come as a
separate API.

Thanks,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com