SZ神庙

从此开始,遁入幻想

2017年1月12日

Linux 秘术记闻>

Linux内核数据结构之链表

链表是Linux内核中用的非常广泛的一种数据结构。在经典的链表定义中,链表的结点包含用户自定义类型的数据域,在C++中很容易实现出这种泛型的链表结构。然而,作为使用C语言的Linux内核又是怎样实现链表结构及其操作的呢?

一.链表结构定义

Linux中使用list_head这个结构体来组织链表,其定义如下:

这个结构体包含了prev和next指针,看上去是组织双向链表的,但是数据域去哪里了呢?事实上,数据域是用户自定义的结构,只要添加这个list_head结构的来组织链表就行,如下:

如此便可访问链表的各个节点的list_node字段,但如何由这个字段访问数据域呢?Linux采用如下的宏来访问数据域:

该宏的第一个参数是list_head的字段地址,第二个参数是数据域的结构类型,第三个参数是list_head字段在结构体中的名称。例如,如下代码即获取了test结构的地址:

list_entry内部使用的container_of又是另一个宏,定义如下:

可见,这个宏是通过计算字段间地址差值来得到数据域的入口地址的。

二.链表操作

2.1 初始化

链表初始化操作使用如下几个宏和函数:

可见,这几个宏和函数做的工作是将prev和next字段初始化为自身。

2.2 插入节点

list_add()函数调用__list_add()将新节点插入到head节点的后方,而list_add_tail()函数则插入到前方。

2.3 删除节点

list_del()函数主要的操作就是将这个节点从其前趋和后继所在的链表中删除,并将该节点的next和prev置为非法值。

2.4 遍历

list_for_each前向遍历链表,list_for_each_prev后向遍历。带safe的则是安全版本,考虑到了遍历过程中删除节点的情况。

三.总结

事实上,Linux中的链表操作远不止以上所列的这些。不过有了Linux自定义的这些结构,实现链表的操作变得很简单,剩下的操作和经典链表的操作也无太大区别,相信读者自己都能写出。本文就介绍到这里吧。