Re: Common hash table implementation

["Brian J. Watson" <Brian.J.Watson@compaq.com>]

Daniel Phillips wrote:
> 
> On Wednesday 18 July 2001 03:34, Larry McVoy wrote:
> > We've got a fairly nice hash table interface in BitKeeper that we'd
> > be happy to provide under the GPL.  I've always thought it would be
> > cool to have it in the kernel, we use it everywhere.
> >
> > http://bitmover.com:8888//home/bk/bugfixes/src/src/mdbm

Thanks, Larry. Your hashing functions are much more sophisticated than
the simple modulo operator I've been using for hashing by inode
number.


> I think the original poster was thinking more along the lines of a
> generic insertion, deletion and lookup interface, which we are now
> doing in an almost-generic way in a few places.  Once place that is
> distinctly un-generic is the buffer hash, for no good reason that I
> can see.  This would be a good starting point for a demonstration.
> 

Daniel's correct. I'm hashing function agnostic, but would like some
common code to simplify the management of a hash table.

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
  - encapsulating the next pointer inside a struct hash_head_##FOOBAR
  - stripping out the hard-coded hashing function, and allowing the
    user to provide their own

All the backslashes offend my aesthetic sensibility, but the
preprocessor provides no alternative. ;)


-- 
Brian Watson                 | "The common people of England... so 
Linux Kernel Developer       |  jealous of their liberty, but like the 
Open SSI Clustering Project  |  common people of most other countries 
Compaq Computer Corp         |  never rightly considering wherein it 
Los Angeles, CA              |  consists..."
                             |      -Adam Smith, Wealth of Nations,
1776

mailto:Brian.J.Watson@compaq.com
http://opensource.compaq.com/