Linux 内核学习笔记： hlist 的理解

前言

• 最近阅读 Linux 内核时，遇到了 hlist，这个 hlist 用起来像是普通的链表，但是为何使用 hlist，hlist 是怎么工作的？

• 相关代码 hlist_add_head(&clk->clks_node, &core->clks);

/**
 * clk_core_link_consumer - Add a clk consumer to the list of consumers in a clk_core
 * @core: clk to add consumer to
 * @clk: consumer to link to a clk
 */
static void clk_core_link_consumer(struct clk_core *core, struct clk *clk)
{
	clk_prepare_lock();
	hlist_add_head(&clk->clks_node, &core->clks);
	clk_prepare_unlock();
}

• 越来越感到 Linux 内核真的是一个宝藏库，学习软件开发，阅读 Linux 内核代码，会受益匪浅。

hlist 定义

• hlist 结构体定义所在的文件 `include\linux\types.h

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

• 有的人理解 hlist 是 hash list 的简写，也就是 哈希链表，我不敢苟同，但 hlist 用在哈希桶上时，会由于 struct hlist_head 只有一个指针，比普通的 struct list_head 节省空间

• 哈希表，由于哈希碰撞，即使哈希桶再大，都有可能多个数据拥有同一个哈希值，此时引入了链表，哈希值相同的元素，挂在链表上，此时由于 哈希桶的数量极大，比如 100万个，使用 struct hlist_head 会比 struct list_head 节省很大的【内存空间】

• 由于 struct hlist_head 特殊的结构，造成 struct hlist_head 不能成为 【双向循环】链表，但是由于 struct hlist_node 有两个指针，因此可以享受 链表节点快速【插入】与【删除】的有点，这部分有点像 普通链表 struct list_head

• struct hlist_head 只用于定义 链表的头部，链表的节点使用 struct hlist_node 定义。

• 【重点理解】 struct hlist_node 中的 pprev 是二级指针，用于指向前一个 节点的 next，也就是前一个节点成员 next 指针的指针。这里不是 pprev = prev->next，而是 pprev= &prev->next ，一定要理解清楚，否则 pprev = prev->next 就是自身指针了，因为上一个节点的 next 就是指向下一个节点，这样获取不到上一个节点的指针。

hlist 的定义与初始化

• 可以通过阅读 Linux 经典链表操作头文件 include\linux\list.h ，详细了解 链表的操作，比如 定义、 初始化、插入、删除、遍历等操作。

• 如果链表嵌入在一个较大的数据结构中，双向链表的各个节点一般都是采用经典的前驱与后继相连，而通过链表成员，获取结构体的指针（地址），可以使用 container_of，比如 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)

• 初始化与定义，可以直接查看 include\linux\list.h ，一般定义方法为

• 定义 hlist 头部 struct hlist_head children;

• 定义 hlist 节点 struct hlist_node clks_node;

• hlist head 定义后需要初始化，可以定义时初始化，也可以手动初始化

• 定义并初始化 static HLIST_HEAD(clk_root_list);

• 手动在初始化函数中初始化 INIT_HLIST_HEAD(&core->clks);

hlist 插入操作

• 由于 hlist 特殊的结构，造成 hlist 插入操作分为两种： 头部的插入 hlist_add_head ，节点的插入 hlist_add_before hlist_add_behind 两种

• hlist_add_head 操作： 知道 hlist 头部，插入到头部后面，新插入的节点，成为第一个hlist 节点

• hlist_add_before ，两个 hlist_node 节点，前面插入节点

• hlist_add_behind 两个 hlist_node 节点，插入到后面，类似于 after

删除节点 __hlist_del

• 由于 hlist node 节点是双向的，双重指针 pprev 可以获取到前一个节点，而 next 可以获取到后一个节点，因此像常规双向链表一样，删除操作不依赖 链表头部

小结

• 深入熟悉 hlist 的操作，感觉 Linux 代码阅读起来，更熟悉了，后面抽时间自己写驱动时用起来。

• hlist 设计很巧妙，但使用起来由于区分 链表头与链表节点，没有 list_head 操作那么简单，但是用于哈希桶结构，可以用于节省空间（链表头部节点多、链表节点少的场合）