Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 数据结构 » ,

Linux内核中的链表

链表是最基本的数据结构之一,Linux的内核中也广泛使用了链表,特别是双向链表,比如进程的描述符、设备列表以及各种功能模块中的数据组织。
但是Linux内核中链表的实现方式比较特殊,本文将介绍其实现细节及如何在自己的程序中使用这个链表。

链表节点

Linux的链表实现在linux-2.6.39.4\include\linux\lish.h中,不同版本之间差别不大。
链表是通过指针将一系列数据节点连接成一条链,其不需要事先知道链表的长度,可以高效地动态增加或移除节点。通常链表的节点包括数据和指针两部分内容,数据域存储数据,指针域存储下一个节点的指针。但Linux内核中提供的链表节点只包含指针域,由于是双向链表,所以对应包含两个指针值,其定义在linux-2.6.39.4\include\linux\type.h中:

struct list_head {
	struct list_head *next, *prev;
};

通过next和prev指针即可向后或向前遍历整个链表。但是只有指针而没有数据内容的链表又有什么意义呢?这就是内核在实现链表过程中的一个技巧,在定义具体的链表的时候,无论链表节点的数据成员是什么,都只需要把list_head作为其中一个成员包含在内即可。这样实现的目的是为了达到更好的可扩展性,因为内核是用C编写的,不支持C++的模板及泛型编程的特性。

例如,如果要定义一个只包含一个整数的链表,那么只需做如下定义:

struct node {
	struct list_head list;
	int num;
};

已知一个node类型的节点指针p,通过p.list->next和p.list->prev可以分别获取其下一个和前一个节点的list成员的地址。

而已知一个节点的list成员的地址,可以通过以下宏获取该节点本身的地址:

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

其中的container_of本身也是个宏,其定义在kernel.h中:

#define container_of(ptr, type, member) ({                \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);  \
    (type *)( (char *)__mptr - offsetof(type,member) );})

而其中的offsetof则定义在stddef.h中:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

这里的几个宏是内核中非常常见的,其中offsetof宏取得member成员在type对象中相对于对象首地址的偏移量,具体是通过把0强制转化成为type类型指针,然后引用成员member,此时得到的指针大小即为偏移量(因为对象首地址为0)。而container_of宏取得包含ptr的数据结构的指针,具体是把ptr转化为type对象中member类型的指针,然后减去member类型在type对象的偏移量得到type对象的首地址。

于是,内核中的链表正是通过list_head成员链起来的,通过节点指针可以知道list_head成员的地址,通过list_head成员也可以得到节点的地址。

链表操作

链表节点的初始化可以通过以下宏完成,其中前两个是静态定义初始节点,最后一个是动态初始化节点:

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

在链表中插入元素时使用到以下的辅助函数,其可以在两个连续节点中间插入节点,不过一般是供内部使用。

static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) 
{ 
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

应用程序使用时一般选择以下两个函数之一,其中第一个在head后插入节点,可用于实现栈;第二个在head前插入节点,可用于实现队列。

static inline void list_add(struct list_head *new, struct list_head *head)
static inline void list_add_tail(struct list_head *new, struct list_head *head)

在链表中删除节点时使用到以下的辅助函数,其可以把prev和next连接起来,如果prev和next之间有节点,则节点被从列表中移除了。如果要删除一个节点p,则可以把p->prev和p->next传进这个函数,即可实现把p移除出链表。

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}

应用程序使用时则可以选择以下的函数之一,第一个是简单地移除节点;第二个是删除节点并把该节点前后指针置空;第三个是删除节点并把该节点重新初始化。

static inline void __list_del_entry(struct list_head *entry)
static inline void list_del(struct list_head *entry)
static inline void list_del_init(struct list_head *entry)

可以用一个new节点替换掉一个old节点,通过以下函数实现:

static inline void list_replace(struct list_head *old, struct list_head *new)
{
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}

如果替换后要重新初始化,可以选择:

static inline void list_replace_init(struct list_head *old, struct list_head *new)

还可以把一个节点移到另一个地方,第一个函数把节点list移到head前面,第二个则把节点list移到head后面。这里本质上是__list_del_entry和list_add的具体应用。

static inline void list_move(struct list_head *list, struct list_head *head)
{
	__list_del_entry(list);
	list_add(list, head);
}
static inline void list_move_tail(struct list_head *list, struct list_head *head)
{
	__list_del_entry(list);
	list_add_tail(list, head);
}

另外还有如链表旋转、拼接等操作,这里不再详细介绍。最后再讲一个非常常用的遍历操作,其可以通过以下宏实现。第二个以双下划线开头,区别是不含prefetch功能。prefetch是GCC支持数据的手工预抓取的内置函数,其可以减少访问延时并提高性能,在需要数据之前把数据放到缓存中。如果元素不多,则不使用prefetch影响不大。

#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
		pos = pos->next)

#define __list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

如果在遍历的过程中涉及到删除节点的操作,则遍历可能会出现问题,此时可以使用以下的宏替代:

#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

实际使用

下面通过一个简单的例子说明其使用方法。
由于list.h中包含有许多内核的东西,具体使用时需要进行一定的修改。首先把linux-2.6.39.4\include\linux\lish.h拷贝到当前目录,然后去掉所有include语句,最后添加上由于删除include而丢失的代码,具体如下,其中作了一定的简化:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ( { \
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \
        (type *)( (char *)__mptr - offsetof(type,member) ); } )

static inline void prefetch(const void *x) {;}

#define LIST_POISON1 ((void *) 0x00100100)
#define LIST_POISON2 ((void *) 0x00200200)

#undef NULL
#if defined(__cplusplus)
#define NULL 0
#else
#define NULL ((void *)0)
#endif

struct list_head {
	struct list_head *next, *prev;
};

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

然后是具体使用该链表的一个例子,其中创建了一个包含一个整数成员的简单链表,并向其进行初始化、添加、删除、遍历、释放等操作。

#include <stdio.h>
#include "list.h"

struct node 
{
	struct list_head list;
	int num;
};

int main() 
{
	int i;                     //临时变量
	struct node *tem;
	struct list_head *pos, *n;

	struct node mylist;       //链表
	INIT_LIST_HEAD(&mylist);  //动态链表初始化

	//插入0~9共10个元素
	for (i = 0; i < 10; i++)
	{
		tem = (struct node*) malloc(sizeof(struct node));
		tem->num = i;
		list_add(&(tem->list), &(mylist.list));
	}

	//打印链表
	list_for_each(pos, &mylist.list)
	{
		tem = list_entry(pos, struct node, list);
		printf("%d ", tem->num);
	}
	printf("\n");
	
	//删除所有值为5的节点,使用safe版本遍历
	list_for_each_safe(pos, n, &mylist.list)
	{
		tem = list_entry(pos, struct node, list);
		if (tem->num == 5)
		{
			list_del_init(pos);
			free(tem);
		}
	}

	//打印链表
	list_for_each(pos, &mylist.list)
	{
		tem = list_entry(pos, struct node, list);
		printf("%d ", tem->num);
	}
	printf("\n");

	//释放链表元素
	list_for_each_safe(pos, n, &mylist.list)
	{
		tem = list_entry(pos, struct node, list);
		list_del_init(pos);
		free(tem);
	}

	return 0;
}

最后编译运行结果如下:

xxx@AdMin:~$ gcc test.c list.h -o test
xxx@AdMin:~$ ./test
9 8 7 6 5 4 3 2 1 0 
9 8 7 6 4 3 2 1 0 
上一篇: 下一篇:
  1. 之前来过,其实你的博客版式不错。文章也很有启示。今天 再来,望回访。

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论