关于哈希表,在内核里设计两个很重要的数据结构:
哈希链表节点:
点击(此处)折叠或打开
-
/*Kernel Version : 3.4.x [include/linux/types.h]*/
-
struct hlist_node {
-
struct hlist_node *next, **pprev;
- };
哈希链表表头:
点击(此处)折叠或打开
-
/*Kernel Version : 3.4.x [include/linux/types.h]*/
-
struct hlist_head {
-
struct hlist_node *first;
- };
接下来,我们来重点回答一下哈希节点里那个两级指针的问题。先讲个小插曲,记得本人当年刚参加工作时,导师给安排了一个活儿,那时候年轻气盛、血气方刚,没一会儿功夫,三下五除二就搞定了。然后拿着自己的“杰作”去师傅看,师傅瞄了一眼说,你这函数简直是一坨shi(和乔老爷当年骂另外一个程序员的用词、语气差不多),谁让你函数入参传个三级指针进去的?这段代码TM能维护么?谁看得懂?完了之后感觉自己还受了莫大的委屈一样,不过谁的人生没有那么点波澜壮阔的过往呢,就像有句名言说的:程序写出来是给人看的,顺带能在机器上运行。OK,那这个故事跟我们要介绍的哈希节点的关系在哪儿呢?没错,就是struct hlist_node{}里那个前向的两级指针的存在意义。
关于两级指针的目的与意义,让我们采用反证法来看看,如果struct
hlist_node{}被设计成如下一级指针的样子,会发生什么:
点击(此处)折叠或打开
-
struct hlist_node {
-
struct hlist_node *next, *pprev;
- };
然后就有以下两个问题跟着冒出来:
1)、在往哈希链myhlist里插入node1时必须这么写:
点击(此处)折叠或打开
-
mylist.first = node1;
- node1->pprev=( struct hlist_node*)&mylist;
点击(此处)折叠或打开
-
node[X]->next = node[X+1];
- node[X]->pprev = node[X-1];
简而言之啥意思呢?往哈希链表里插入元素时,如果在表头的第一个位置上插入元素,和插入在哈希链表的其他位置上的代码处理逻辑是不一样的。因为哈希表头是list_head类型,而其他节点都是list_node类型。
2)、同样,如果删除节点时,对于非首节点,以node2为例:
点击(此处)折叠或打开
-
node2->pprev->next = node2->next;
- node2->next->pprev = node2->pprev;
点击(此处)折叠或打开
-
((struct hlist_head*)(node1->pprev))->first = node1->next;
- node1->next->pprev = ( struct hlist_node*)&mylist; 或者 node1->next->pprev = node1->pprev;
所以,记住,当我们在代码中看到类似与*(hlist_node->pprev)这样的代码时,我们心里应该清楚,此时正在哈希表里操作当前节点前一个节点里的第一个指针元素所指向的内存地址,只是以间接的方式实现罢了。那么回到删除哈希链表节点的场景,当删除首节点时,此时情况就变成了:
点击(此处)折叠或打开
-
*(node1->pprev) = node1->next;
- node1->next->pprev = node1->pprev;
点击(此处)折叠或打开
-
*(node2->pprev) = node2->next;
- node2->next->pprev = node2->pprev;
大家自行将上述函数里的入参n换成node2,最终和我们上面推断的结果是一致的:
点击(此处)折叠或打开
- hlist_add_head(struct hlist_node *n, struct hlist_head *h)
理论上说,内核应该再提供一个对称的方法hlist_add_tail()才算完美,用于将哈希链表操作成如下的样子:
还有hlist_add_behind()和hlist_add_before(),在3.17版本之前hlist_add_behind()的名字还是hlist_add_after(),不过作用都一样。两个函数原型分别如下:
点击(此处)折叠或打开
-
hlist_add_before(struct hlist_node *n,struct hlist_node *next);
- hlist_add_behind(struct hlist_node *n,struct hlist_node *prev);
hlist_add_before():在next节点的前面插入n节点;
hlist_add_behind():在prev节点的后面插入n节点;
接下来,让我们…..
1)、在node4节点的前面插入node3:
2)、在node1的节点后面插入node5:
未完,待续...