Re: Common hash table implementation

[Richard Guenther]

On Sat, 21 Jul 2001, Daniel Phillips wrote:

> On Saturday 21 July 2001 02:24, Brian J. Watson wrote:
> > Daniel Phillips wrote:
> > Richard Guenther sent the following link to his own common hashing
> > code, which makes nice use of pseudo-templates:
> >
> > http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/~checkout~/glame/glame
> >/src/include/hash.h?rev=1.5&content-type=text/plain
> >
> > A few things I would consider changing are:
> >
> >   - ditching the pprev pointer
> 
> Yes, you want to use the generic list macros there.

You get one-pointer size hash table entries and generic deletion from it.
 
> >   - encapsulating the next pointer inside a struct hash_head_##FOOBAR
> 
> I think the generic list macros give you that for free.

Umm, if you use such, you get lists.h style type-casting stuff which
doesnt have a nice interface as

my_type *hash_find_my()

instead you'd get

hash_dead_my *hash_find_my()

which you'll have to cast with something like the list_entry() macro.

> >   - stripping out the hard-coded hashing function, and allowing the
> >     user to provide their own

Ok, if the two expressions are not generic enough.

> Naturally.  And trying to reduce the size of the macros.  It's not that 
> easy to get stuff that has dozens of lines ending with "\" into the 
> kernel.  You might have better luck just generalizing a few short sets 
> of common operations used in hashes, and showing examples of how you'd 
> use them to rewrite some of the existing hash code.  Obviously, the 
> new, improved approach has to be no less efficient than the current way 
> of doing things.

All those \s are to encapsulate the whole thing into the template-style
macro - not that I like this, but I cannot see an alternative.

> > All the backslashes offend my aesthetic sensibility, but the
> > preprocessor provides no alternative. ;)
> 
> It's hard to argue against using inlines there.  It's true that there 
> are a lot of generalizations you just can't do with inlines, but so 
> what?  What matters is how efficient the generated code is and to a 
> lesser extent, how readable the source is.  You could make that source 
> quite a bit more readable with a few *small* macros and some inline 
> functions.  Suggestion: express the bucket probe as an inline, compute 
> the hash outside and pass it in.  Then you can wrap the whole thing up 
> in a really short macro.

Ok, with an approach like the list.h one (struct hash_head) you'd get
there, but of course without automatic type conversion (and safety).
Of course, if you can tidy up the macro without changing to use a
hash_head structure, I'd be glad to see how :)

Richard.

--
Richard Guenther <[e-mail]>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/
The GLAME Project: http://www.glame.de/