Re: hashtables

[Thor Lancelot Simon <tls%panix.com@localhost>]

On Tue, Jul 24, 2018 at 10:14:57PM +0000, coypu%sdf.org@localhost wrote:
> 
> I don't have any opinions about hashtables - I just know that
> implementing one would take me really long and would probably still be
> buggy in the end, and I didn't find a similar API that claims to be a
> hashtable.
> 
> Is there some code I could use? I'm totally OK with not a hashtable too.

The basic approach used in our kernel is to declare an array of HEADs
for one of our queue.h datastructures (you usually only have to walk
in one direction, and hardly ever even that, so it's usually a LIST).

Each LIST is a "bucket".  The hash picks out the "bucket" (the LIST_HEAD)
and then you just insert at the head (if adding) or walk down the LIST
until you find the entry you're looking for (if searching).

As a hash function, if you've got things of a convenient size, you can
just use the % operator as your hash function (use an array of buckets
that's of a convenient prime size).  If what you have to hash is larger
there's a hash(9) API.

There are examples all over the kernel; the multicast and ifaddr hashes
in netinet/in.c are fairly simple, though they've had some locking added.
Maybe someone can suggest one even simpler.

This extends fairly naturally to other use cases -- you can put a
mutex at the head of each chain and make a datastructure that allows
parallel access to different buckets; you can sacrifice evenness of
the hash and use a power-of-2 hash size and shift/mask for the lookup,
which is faster most of the time but has a much worse worst case.

This kind of implementation doesn't lend itself to being expanded
so it's collision-free, but most else you might like to do is not too
hard.

Thor