Linux内核中的双向链表
Linux内核中实现了一个通用的双向链表,其实现极其简洁而优雅。
先来看看数据结构的定义:
struct list_head{
struct list_head *next, *prev;
};
和正常的双向链表一样,包含了一个prev和next指针。但是,正常的双向链表还会有数据域,这里却没有。这正是linux中list实现的优雅之处:不是在list中包含数据,而是在其他数据结构中包含list,从而实现list的通用性,而不用针对每一种数据结构实现不同的链表。
需要使用到list功能时,只需要在当前数据结构中加入struct list_head作为一个成员,就可以使用list的所有特性。list的许多功能都是通过宏定义的,比如最重要的list_entry,list_entry的功能是,通过list的地址和包含list的结构体类型,获取包含list的结构体的首地址。从而实现从list到外部数据结构的逆向访问。实现如下。
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
只是简单地将list_entry替换为container_of而已,再来看看container_of的实现:
#ifndef container_of
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member) * __mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
#endif
这里有两个重要的组成:typeof和offsetof,其中typeof是gcc的一个扩展特性,可以在编译时获取变量的类型。而offsetof的实现十分巧妙:
#ifndef offsetof
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
将一个NULL作为结构体的指针,从而计算出成员在结构体内部的偏移。NULL虽然是空指针,但是没有对其进行解引用的话,是不会引发错误的。通过在0x00000000处构造一个虚拟的结构体变量,从而计算成员在结构体中的偏移量,的确是非常tricky的方法,不过很实用。
不过这里还有一点疑问:为何container_of宏中需要用一个临时的__mptr常量来保存ptr的值,而不是直接用ptr进行计算?若直接使用ptr,也仅仅引用了一次,所以不会出现自增自减操作的错误。如果是想要起到检查输入的作用,即防止传入的member不是结构体的成员,那也说不通,因为offsetof宏也能起到相同的作用。待考证。
2014年01月18日更新:__mptr可以起到类型检查的作用,若传入的ptr不是member类型的指针,则会给出警告。
References
Post Info
- Copyright Notice: Creative Commons BY-NC-ND 3.0