Hash table changes
authorBarret Rhoden <brho@cs.berkeley.edu>
Sat, 7 Nov 2009 01:33:47 +0000 (17:33 -0800)
committerBarret Rhoden <brho@cs.berkeley.edu>
Mon, 9 Nov 2009 22:20:49 +0000 (14:20 -0800)
Changed how the hash table works, most notably that you must free your
keys on your own.  This way, you can either kfree, kmem_cache_free, or
just nothing, based on whatever is appropriate for what your key is.
(Just an int requires no freeing, but still requires a typecast).

This is a good example of packaged solutions being non-ideal, since they
make assumptions about its usage (kfree, let alone that the key is an
obkect).  I nearly ripped out the function pointers for hashing and
equality, in favor of the hashed value being passed to functions (where
needed), and the key just being a long.  It simplifies a lot and would
perform better, and I don't have an example of when I want an object for
a key where equivalence isn't the address of the object.  There may be a
case where the function pointers are nice, so I held off.

There are also generic functions for the hashfn and eqfn.  Don't call
these directly, etc.  Also, the hash entries (hentry) are now slab
allocated, instead of kmalloc'd.

NB: be warned that there is no checking for duplicate keys.

Also, another way to do these things is to embed the hash_entry in any
struct that will be hashed (like the struct proc).  You won't need
dynamic allocation of the hentry, you can check if you are hashed or
not, and the hentry doesn't need a pointer to you (can do something like
container_of()).  A downside is that concurrency can be weird - others
could temp touch your entry while walking a hash chain.  Not sure what's
best, overall.


No differences found