Linux内核中链表和散列表的实现原理揭秘

Linux内核的实现，大量使用了数据结构，包括了数组、链表和散列表。其中用的最多的是双向循环链表。Linux内核使用的是自己定义的链表和散列表，简单而高效，使用方法也非常的别具一格。研究Linux内核的链表和散列表对于看懂Linux内核源代码有重要的意义。本文基于kernel2.6.39版本进行分析。

Linux的链表和散列表定义在include/linux/types.h文件中

structlist_head { 223 struct list_head *next, *prev; 224}; 225 226structhlist_head { 227 struct hlist_node *first; 228}; 229 230structhlist_node { 231 struct hlist_node *next, **pprev; 232}; 233 list_head就是使用最为广泛的双向循环链表。这个数据结构可以说是LinuxKernel的基石，大量内核源代码使用了这个数据结构。 hlist_head和hlist_node常常用于散列表中。

Linux的链表和散列表的操作函数的定义在include/linux/list.h文件中

初始化双向循环链表，只有一个元素的双向循环链表，next和prev指向自身。staticinline voidINIT_LIST_HEAD（structlist_head *list）
25{
26list->next = list;
27list->prev = list;
28}
29

初始化散列表的链表。空的散列表链表的first==NULL。每一个散列表链表的元素初始化时next和pprev指针都是NULL，而不是指向自身。我们可以看到，散列表链表hlist_node虽然和双向循环链表list_head一样，都有两个指针，但有本质的区别。散列表链表hlist_node不是循环链表。它有头和尾，是单向的链表。散列表链表hlist_node之所以有两个指针，是为了提高插入和删除链表的效率。hlist_node的插入，只需要一个相邻的hlist_head或者hlist_node节点即可。它的删除，只需要它本身即可定位其相邻的前后两个元素。570
571#defineHLIST_HEAD_INIT { .first =NULL }
572#defineHLIST_HEAD（name） struct hlist_headname = { .first =NULL }
573#defineINIT_HLIST_HEAD（ptr）（（ptr）->first = NULL）
574staticinline voidINIT_HLIST_NODE（structhlist_node *h）
575{
576h->next = NULL;
577h->pprev = NULL;
578}
579

脱离链表的元素的状态

staticinline void__list_add（structlist_head *new,
38 struct list_head *prev,
39 struct list_head *next）
40{
41next->prev = new;
42new->next = next;
43new->prev = prev;
44prev->next = new;
45}
46

/*
80* Delete a list entry by making the prev/next entries
81* point to each other.
82*
83* This is only for internal list manipulation where we know
84* the prev/next entries already！
85*/
86staticinline void__list_del（structlist_head *prev, structlist_head *next）
87{
88next->prev = prev;
89prev->next = next;
90}
91

92/**
93* list_del - deletes entry from list.
94* @entry: the element to delete from the list.
95* Note: list_empty（） on entry does not return true after this, the entry is
96* in an undefined state.
97*/
98#ifndefCONFIG_DEBUG_LIST
99staticinline void__list_del_entry（structlist_head *entry）
100{
101__list_del（entry->prev,entry->next）;
102}
103
104staticinline voidlist_del（structlist_head *entry）
105{
106__list_del（entry->prev,entry->next）;
107entry->next = LIST_POISON1;
108entry->prev = LIST_POISON2;
109}
110#else

散列表链表的脱离链表代码：

90staticinline void__hlist_del（structhlist_node *n）
591{
592 struct hlist_node *next = n->next;
593 struct hlist_node **pprev = n->pprev;
594 *pprev =next;
595 if （next）
596next->pprev = pprev;
597}
598
599staticinline voidhlist_del（structhlist_node *n）
600{
601__hlist_del（n）;
602n->next = LIST_POISON1;
603n->pprev = LIST_POISON2;
604}
605 看看LIST_POISON1和LIST_POISON2是何方神圣。16
17/*
18* These are non-NULL pointers that will result in page faults
19* under normal circumstances, used to verify that nobody uses
20* non-initialized list entries.
21*/
22#defineLIST_POISON1 （（void *） 0x00100100 + POISON_POINTER_DELTA）
23#defineLIST_POISON2 （（void *） 0x00200200 + POISON_POINTER_DELTA）
24

表示链表元素是未初始化的，既不在链表中，也没有经过初始化，不应该使用。