一. hash链表的介绍
hash链表也是内核的基本的数据结构，在内核的代码中搜索"struct hlist_head"和"struct hlist_node"，会发现非常多的地方使用到了。所以，搞懂hash链表的原理和操作方式非常的重要，包括链表的初始化，增加，删除，遍历等等。如果对C语言指针不太熟练的读者，建议在看本篇文章前，先看一下我前面写的C语言中指针的理解，帮助对本文理解。
二. hash链表操作原理及使用
1. hash链表的结构介绍
先给出hash链表的示意结构，对hash链表有一个整体的认识，如下图所示：
如图可知：
1. 每个hash链表以first作为链表的头，hash链表是由多个以first作为头的链表组成，如上图的数组arr[n]中n，n表示链表数量。
2. 每个hlist_node的next成员保存的是下一个hlist_node的地址，hlist_node的pprev成员保存的是前一个hlist_node的next成员的地址，如果是链表第一个元素，保存的是first的地址。
3. 最后一个hlist_node的next成员的内容是NULL，也就是指向NULL。
为什么不把hash链表的每条链设计成内核普通链表的形态呢？
1. 节省空间。因为struct list_head *next，struct list_head *prev，加起来是8个字节，struct hlist_node *first只需要4个字节，每个头部可以省略4字节，整个hash链表就可以省略4*n个字节，所以链表头设计为只有4字节。
2. 不需要前向遍历。hash链表只需要后向遍历就可以，所以不需要升级成普通链表形式。
3. 对于节点的操作可以使用统一的接口。例如在删除节点时，删除头节点和普通节点都可以使用__hlist_del函数来删除，下面会分析到。
2. 基本数据结构
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};hash链表由链表头和链表节点组成，分别对应不同的结构体。链表头是由一个struct hlist类型的first指针组成，链表节点则是由struct hlist类型的next指针和二级指针pprev组成。
3. hash链表的初始化
// 初始化struct hlist_head变量, 例如struct hlist_head head = HLIST_HEAD_INIT;
#define HLIST_HEAD_INIT { .first = NULL }
// 定义struct hlist_head变量并初始化, 例如HLIST_HEAD(objects)
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
// 初始化ptr指向的struct hlist_head变量, 例如INIT_HLIST_HEAD(&object->area_list)
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)hash链表的初始化是把链表头的first成员置位NULL，各个宏的区别见上面代码上方的注释。
4. hash链表元素的删除
static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}__hlist_del函数的作用是从hash链表中删除节点n，有两种情况，一种是删除头结点，一种是删除普通节点。示意图如下所示：
删除头结点：
分析：
1. struct hlist_node *next = n->next
n->next保存的是node a的地址，next = n->next，所以next保存的是node a的地址，next指向node a。
2. struct hlist_node **pprev = n->pprev
n->pprev保存的是first的地址，pprev = n->pprev，所以pprev保存的是first的地址
3. *pprev = next
pprev表示first的地址值，*pprev表示取first地址的值，*pprev = next表示将next的地址赋值给first。
4. if (next) next->pprev = pprev
如果next为空，也就是node a不存在，则不继续操作，如果next不为NULL，则node a的pprev成员指向first。
删除普通节点：
分析：
1. struct hlist_node *next = n->next
n->next保存的是node b的地址，next = n->next，所以next保存的是node b的地址，next指向node b。
2. struct hlist_node **pprev = n->pprev
n->pprev保存的是node a的next成员的地址，pprev = n->pprev，所以pprev保存的是node a的next成员的地址
3. *pprev = next
pprev表示first的地址值，*pprev表示取first地址的值，*pprev = next表示将next的地址赋值给first。
4. if (next) next->pprev = pprev
如果next为空，也就是node b不存在，则不继续操作，如果next不为NULL，则node b的pprev成员指向first。
小结：
从删除头结点和普通节点的示意图来看，__list_del函数是同时适用于两种情况的删除的。
5. hash链表元素添加
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
struct hlist_node *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next)
{
n->pprev = next->pprev;
n->next = next;
next->pprev = &n->next;
*(n->pprev) = n;
}
static inline void hlist_add_behind(struct hlist_node *n,
struct hlist_node *prev)
{
n->next = prev->next;
prev->next = n;
n->pprev = &prev->next;
if (n->next)
n->next->pprev = &n->next;
}hlist_add_head函数用于添加链表头结点，示意图如下：
分析：
1. struct hlist_node *first = h->first
保存第一个节点（node h）的地址为first指针的值。
2. n->next = first
node n的next指针的值被赋值为node h的地址。
3. if (first)
first->pprev = &n->next
如果node h存在，则node h的pprev指针的值被赋值为node n的next指针的地址
4. h->first = n
h->first指针的值被赋值为node n指针的值。
5. n->pprev = &h->first
node n的pprev指针的值h->first指针的地址。
hlist_add_before函数有hlist_node n和hlist_node next两个参数，表示在node next前添加node n，示意图如下：
分析：
1. n->pprev = next->pprev
next->pprev表示是node b的next指针的地址，n->pprev = next->pprev表示n->pprev指针的值保存的是node b的next指针的地址。
2. n->next = next
node n的next指针的值被赋值为node next的地址。
3. next->pprev = &n->next
node next的pprev指针的值被赋值为node n的next指针的地址。
4. *(n->pprev) = n
node next的pprev指针的值是node b的next指针的地址，所以*(n->pprev)是node b的next指针的内容被赋值为node n的地址
hlist_add_behind函数有hlist_node n和hlist_node prev两个参数，表示在node prev后添加node n，示意图如下：
分析：
1. n->next = prev->next
prev->next表示是node b的地址，n->next = prev->next表示node n的next指针的值被赋值为node b的地址。
2. prev->next = n
node prev的next指针的值是node n的地址。
3. n->pprev = &prev->next
node prev的next指针的地址赋值为node n的pprev指针的值。
4. if (n->next)
n->next->pprev = &n->next
if (n->next)表示如果node b存在，n->next是node b的地址，n->next->pprev是node b的pprev指针的值被赋值为node n的next指针的地址。
6. hash链表元素遍历
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos ; pos = pos->next)
#define hlist_for_each_safe(pos, n, head) \
for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
pos = n)
#define hlist_entry_safe(ptr, type, member) \
({ typeof(ptr) ____ptr = (ptr); \
____ptr ? hlist_entry(____ptr, type, member) : NULL; \
})
hlist_entry宏与Linux内核链表理解与使用解析的list_entry一样，都是封装了container_of函数，此处不再分析。
hlist_for_each宏用于遍历hash链表，分别有pos和head参数，pos指向head的first成员，通过next指针遍历整个链表。
hlist_for_each_safe宏分别有pos和head参数，和list_for_each_safe宏的作用类似，当在遍历链表的时候，删除pos指向的节点，不会影响遍历后面的链表节点。
hlist_entry_safe则会对ptr的类型做一个检查。
三. 总结
最后以一个hash链表的示例结尾吧，这段代码是引用一个别的博客的，我觉得例子很好，链接list and hlist in kernel，代码粘贴如下
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/version.h>
#include <linux/list.h>
#include <linux/slab.h>
MODULE_LICENSE("GPL");
#define init_name_hash() 0
#define IFNAMSIZ 16
#define NETDEV_HASHBITS 8
#define NETDEV_HASHENTRIES (1 << NETDEV_HASHBITS)
/* partial hash update function. Assume roughly 4 bits per character */
static inline unsigned long
partial_name_hash(unsigned long c, unsigned long prevhash)
{
return (prevhash + (c << 4) + (c >> 4)) * 11;
}
/*
* Finally: cut down the number of bits to a int value (and try to avoid
* losing bits)
*/
static inline unsigned long end_name_hash(unsigned long hash)
{
return (unsigned int) hash;
}
/* Compute the hash for a name string. */
static inline unsigned int
full_name_hash(const unsigned char *name, unsigned int len)
{
unsigned long hash = init_name_hash();
while (len--)
hash = partial_name_hash(*name++, hash);
return end_name_hash(hash);
}
struct net {
struct hlist_head *dev_name_head;
};
static inline struct hlist_head *dev_name_hash(struct net *net,
const char *name)
{
unsigned hash = full_name_hash(name, strnlen(name, IFNAMSIZ));
return &net->dev_name_head[hash & ((1 << NETDEV_HASHBITS) - 1)];
}
static struct hlist_head *netdev_create_hash(void)
{
int i;
struct hlist_head *hash;
hash = kmalloc(sizeof(*hash) * NETDEV_HASHENTRIES, GFP_KERNEL);
if (hash != NULL)
for (i = 0; i < NETDEV_HASHENTRIES; i++)
INIT_HLIST_HEAD(&hash[i]);
return hash;
}
struct net_device {
char name[IFNAMSIZ];
struct hlist_node name_hlist;
int net_num;
};
struct net_device *dev_get_by_name(struct net *net, const char *name) {
struct hlist_node *p;
hlist_for_each(p, dev_name_hash(net, name)) {
struct net_device *dev
= hlist_entry(p, struct net_device, name_hlist);
if (!strncmp(dev->name, name, IFNAMSIZ))
return dev;
}
return NULL;
}
static struct net net_space;
static struct net_device *devices;
static int hlist_module_init(void) {
const int dev_num = 10;
int i;
net_space.dev_name_head = netdev_create_hash();
if (net_space.dev_name_head == NULL) {
goto err_name;
}
devices = kmalloc(sizeof(struct net_device) * dev_num, GFP_KERNEL);
if (devices == NULL) {
goto err_dev;
}
for (i = 0; i < dev_num; ++i) {
snprintf(devices[i].name, IFNAMSIZ, "eth%d", i);
devices[i].net_num = i;
hlist_add_head(&devices[i].name_hlist,
dev_name_hash(&net_space, devices[i].name));
}
struct net_device *dev;
dev = dev_get_by_name(&net_space, "eth1");
if (dev) {
printk("%s, %d\n", dev->name, dev->net_num);
}
return 0;
err_dev:
kfree(net_space.dev_name_head);
err_name:
return -ENOMEM;
}
static void hlist_module_exit(void) {
kfree(devices);
kfree(net_space.dev_name_head);
}
module_init(hlist_module_init);
module_exit(hlist_module_exit);