Get in touch:
01524 851 877
07718 896 553

Hash Table Implementation

Posted on Jun 12 2009 by Matthew Jakeman

I have been doing some more kernel module coding and have been using the linked list implementation provided by list.h quite a bit recently as I have known in advance that the lists would only ever have a small amount of entries so looping through the list would not prove to be too much of a performance penalty.

For my latest problem however I have a list that could grow a bit larger in size so I made the decision to use a hash table instead of a linked list. I searched through the kernel source naively hoping there would be a neat generic hash table implementation included.. Alas there is not.

After a bit of searching I stumbled across uthash. This is a nice hash table implementation allowing you to basically put any struct into a hash table based on using one of the fields in the struct as the id. The included macro’s allow a string or an int to be used for the id as well which is quite useful.

So far it seems quite simple to use. All the functions are included in one header file wrapped us as macro’s so it is nice and easy to integrate with any project and it doesn’t rely on much to be included externally. In my case all the functions it does need are provided by the kernel so it was very simple to integrate. I will definitely be using this again in other projects in the future.

Leave a comment