linux 内核 hash table 的使用

很早以前就想学习一下如何使用linux内核中的散列函数。google了几次，发现
网上有大量介绍有关hlist的东西。可找来找去也找不到究竟该如何使用散列。
原来，我先入为主的认为内核中的散列函数会像那些高级语言中实现的散列功能
类似：我提供一对对的(key value)给内核，然后再调用某一个api，传给它一个
key，就可以得到对应的value。

后来参考了一些内核中应用散列的实例才发现，原来根本不是这么回事。实际
上，对于如何将输入数据散列到一个指定范围的算法，需要使用散列的人自己决
定。内核只提供了一个发射碰撞时把碰撞的项链接到一起的hlist结构。

例如，你创建了一个长度为m的散列表，并且已经选择了一个将输入数据映射到
范围0 ~ m-1的散列函数。接下来，你就要在这个长度为m的散列表的每个表项内
放上一个hlist_head结构体。然后在每个输入数据的结构体中定义一个
hlist_node的结构体。每当把一个输入通过散列函数映射到0 ~ m-1的范围内时，就
把这个输入的hlist_node挂到散列表对应的槽的hlist_head上面。当给定一个
key，想获取它的value的时候，就先用散列函数算出这个key对应的槽的位置，
然后遍历这个槽的hlist_node链表，找到与key相等的项。把它的value返回。

例如，有这样一个数组：
0x01, 0x02, 0x04, 0x08,0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8,
0xcd, 0x87, 0x13,
其中每个元素对应的索引号为：
1, 2, 3, 4, 5, ... 15
也就是说，当输入0x01时，我希望得到索引号1，当输入0x08时，得到4，当输入
0x3a时，得到10...
这种从数值到索引号的转换，可通过散列来实现。

下面是实现该功能的一个内核代码，散列函数我选择的是：
value = ((104 * key + 52) % 233) % 15
(实际上，对于输入固定的情况，使用完全散列可以获得完全固定的访问时间，
上面这个散列函数就是我想使用完全散列时搜索一个全域散列族得到的第一级散
列函数，但我发先这个散列函数已经足够好，总共才只有一次碰撞。所以就没有
必要像完全散列那样使用二级散列了。)

#include <linux/init.h>
#include <linux/module.h>
#include <linux/list.h>

struct q_coef
{
    u8 coef;
    u8 index;
    struct hlist_node hash;
};

#define HASH_NUMBER 15
u8 coef[HASH_NUMBER] = {
    0x01, 0x02, 0x04, 0x08,0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13,
};
struct q_coef q_coef_list[HASH_NUMBER];

struct hlist_head hashtbl[HASH_NUMBER];

static inline int hash_func(u8 k)
{
    int a, b, p, m;
    a = 104;
    b = 52;
    p = 233;
    m = HASH_NUMBER;
    return ((a * k + b) % p) % m;
}

static void hash_init(void)
{
    int i, j;
    for (i = 0 ; i < HASH_NUMBER ; i++) {
        INIT_HLIST_HEAD(&hashtbl[i]);
        INIT_HLIST_NODE(&q_coef_list[i].hash);
        q_coef_list[i].coef = coef[i];
        q_coef_list[i].index = i + 1;
    }
    for (i = 0 ; i < HASH_NUMBER ; i++) {
        j = hash_func(q_coef_list[i].coef);
        hlist_add_head(&q_coef_list[i].hash, &hashtbl[j]);
    }
}

static void hash_test(void)
{
    int i, j;
    struct q_coef *q;
    struct hlist_node *hn;
    for (i = 0 ; i < HASH_NUMBER ; i++) {
        j = hash_func(coef[i]);
        hlist_for_each_entry(q, hn, &hashtbl[j], hash)
            if (q->coef == coef[i])
                printk("found: coef=0x%02x index=%d\n", q->coef, q->index);
    }
}
static int htest_init (void)
{
    hash_init();
    hash_test();
    return -1;
}

static void htest_exit (void)
{
}

module_init(htest_init);
module_exit(htest_exit);

MODULE_LICENSE("Dual BSD/GPL");