Linux 内核中链表和散列表的实现原理揭秘
By 沈东良(良少) http://blog.csdn.net/shendl
Linux 内核的实现,大量使用了数据结构,包括了数组、链表和散列表。其中用的最多的是双向循
环链表。Linux 内核使用的是自己定义的链表和散列表,简单而高效,使用方法也非常的别具一格。
研究 Linux 内核的链表和散列表对于看懂 Linux 内核源代码有重要的意义。本文基于 kernel
2.6.39 版本进行分析。
Linux 的链表和散列表定义在 include/linux/types.h 文件中
struct list_head {
223 struct list_head *next, *prev;
224 };
225
226 struct hlist_head {
227 struct hlist_node *first;
228 };
229
230 struct hlist_node {
231 struct hlist_node *next, **pprev;
232 };
233
list_head 就是使用最为广泛的双向循环链表。这个数据结构可以说是 Linux Kernel 的基石,
大量内核源代码使用了这个数据结构。
hlist_head 和 hlist_node 常常用于散列表中。
Linux 的链表和散列表的操作函数的定义在 include/linux/list.h 文件
中
初始化双向循环链表,只有一个元素的双向循环链表,next 和 prev 指向自身。
static inline void INIT_LIST_HEAD(struct list_head *list)
25 {
26 list->next = list;
27 list->prev = list;
28 }
29
初始化散列表的链表。
空的里散列表链表的 first==NULL。每一个散列表链表的元素初始化时 next 和 pprev 指针都
是 NULL,而不是指向自身。
我们可以看到,散列表链表 hlist_node 虽然和双向循环链表 list_head 一样,都有两个指针,
但有本质的区别。
散列表链表 hlist_node 不是循环链表。它有头和尾,是单向的链表。
散列表链表 hlist_node 之所以有两个指针,是为了提高插入和删除链表的效率。hlist_node 的
插入,只需要一个相邻的 hlist_head 或者 hlist_node 节点即可。它的删除,只需要它本身即可定位
评论18