HASHTAB FOR LINUX 64 BIT
Now we can see, on a 64 bit machine, that first and third have been hashed to bucket number 1 and second has been hashed to bucket number 2. Now we have an element that can be added to a hashtable, so lets define a hashtable.ġ5 #define DEFINE_HASHTABLE(name, bits) \ my_hash_list = 0 /* Will be initilaized when added to the hashtable */ So every element is essentially part of a hlist and the hashtable only holds the head of these lists.īack to our example, let's create our first variable representing an element that will be hashed: The hashtable is an array of struct hlist_head pointers, where each one points to a different list, and each one of those lists holds all elements that are hashed to the same bucket. The main difference between the list_node and hlist_node structs is the fact that list_node is a cyclic linked list, while hlist_node is terminated by a null pointer. So Why do we have a pointer to hlist_node? Why do do we need a list in the first place? First you may wish to read FAQ/LinkedLists to grasp the idea of linked lists in the kernel. When first encountering this, most people are confused because they have been taught to implement hashtables differently. To be able to link each element of type struct mystruct to others, we need to add a struct list_head field: Let's start by defining a data structure that we will then embed in a kernel hashtable: Let's take a look at the kernel's hashtable API from the perspective of "how would I use it in my own code?" (e.g. A good hash function should make sure you get O(1) elements into every bucket. As every data structure course teaches, the idea is that the hashtable is big enough to contain all elements in different buckets, and the hash function should be good enough to distribute them uniformly, but just in case a collision does happen, the elements are chained. So every bucket in the hashtable is a linked list which will hold all objects that are hashed to the same bucket.
HASHTAB FOR LINUX CODE
Understanding this API can help you make sense of tidbits of kernel code here and there but is also a great opportunity to improve your C programming knowledge by reading some very interestingly put together code.įirst things first, the following implementation of the hashtable relies on chaining elements upon a collision. Recent versions of the kernel now features a "unified" and very smart generic API to manipulate such data structures.
It wasn't uncommon, when working with older versions of the kernel, to encounter redundant code managing classical data structures such as linked lists, hashtables, etc. How does the kernel implements Hashtables?
0 kommentar(er)
