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)
commit7937f13b4ad21fc8b2c1eeb7c552cb87b090b59c
tree8f0376acccd8715366b6ab07e58382a2d721f8aa
parente736da277ad48e7bf47f993b0646ffba3f6202da
Hash table changes

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.
kern/include/hashtable.h
kern/include/hashtable_itr.h [deleted file]
kern/include/testing.h
kern/src/Makefrag
kern/src/hashtable.c
kern/src/hashtable_itr.c [deleted file]
kern/src/init.c
kern/src/testing.c