On 4/13/07, Tzahi Fadida <Tzahi.ML@xxxxxxxxx> wrote:
On Thursday 12 April 2007 22:18:42 Eddie Pettis wrote: > On 4/12/07, Tzahi Fadida <Tzahi.ML2@xxxxxxxxx> wrote: > > Is there a hashtable implementation in the kernel i can use instead of > > reinventing the wheel. > > There are several individual hash table implementations within the > kernel. However, I have never seen a library-like version. (Anybody > please correct me if I'm wrong!) > > I wrote my own little library for hashing: > http://cobweb.ecn.purdue.edu/~npettis/kernel/index.htm > > Use hashtable.c for numeric hashes. Use hashstring.c for hashing > strings (e.g. filenames). Hope the function comments are sufficient > to get you started. I think you did not send your email to the list.
My apologies for clumsy use of the Reply to All button. :) Posted to the list.
I found this: drivers/char/drm/drm_hashtab.c which looks similar to your implementation.
Looks good. The primary difference between their application and mine is that their implementation produces sorted chains, whereas my implementation just throws elements into the chain in insertion order. Actually, I should probably update mine so that recently referenced objects get spliced into the head of the chain. My thesis code base is 2.6.17, which doesn't include this file. For all current and future versions, the code you mention is excellent.
I thought about maybe to create an expandable hashtable, for fun :). i.e. you define the number of items per hashkey and if there is no room you rebuild the hashtable with a higher order. You can also add that you rebuild if the table is xx% filled (probably 67% is a golden ratio) to avoid too many rebuilds.
I don't know if percentage filled is the proper metric for chained hash tables such as these. Average search depth is probably a better metric, possibly maintained through an exponential average with a low decay factor. However, percentage filled is an excellent metric if you implement an open addressing table. If you build it, post back to the list. I'd love to use it! :) -- Eddie Pettis Electrical and Computer Engineering Purdue University -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
