深入浅出linux内核源代码之双向链表list_head pdf codes

深入浅出 linux 内核源代码之双向链表 list_head

原创文章，转载请注明出处，谢谢！

作者：清林，博客名：飞空静渡

范金宝

email:fjb2080@163.com

blog:http://blog.csdn.net/fjb2080

前言：在 linux 源代码中有个头文件为 list.h。很多 linux 下的源代码都会使用这个头文件，它里面定义

了一个结构,以及定义了和其相关的一组函数，这个结构是这样的：

学习计算机的人都会开一门课程《数据结构》，里面都会有讲解双向链表的内容。

什么是双向链表，它看起来是这样的：

struct dlist

{

int no;

void* data;

struct dlist *prev, *next;

};

它的图形结构图如下：

如果是双向循环链表，那么就加上虚线所示。

int age;

int weight;

};

表示动物的：

struct animal

{

int age;

{

int age;

int weight;

struct person *next, *prev;

};

表示动物的：

struct animal

{

int age;

int weight;

{

…....

struct person *p;

for(p = person_head->next; p != person_head; p=p->next)

{

}

…...

}

如果我们定义这样的两个函数，它们基本一样，会不会觉得有点冗余，如果是 c++就好了，但这里只说 c。

{\

type *p;\

for(p = ((type*)list)->next; p != (type*)list; p=p->next)\

if (p->age == age && p->weight == weight)\

{\

}\

}while(0)

那么我们获得一个年龄 50，体重 60 的人可以这样：

}

同样获得一个年龄 20，体重 130 的动物可以这样：

struct animal *one = NULL;

get_one(animal_head, 50, 60, struct animal, one);

if(one)

{

// get it

…...

}

我们再回过头来看这两个结构，它们的指向前和指向后的指针其实都差不多，那把它们综合起来吧，所以看起

{

int age;

int weight;

struct list_head list;

};

表示动物的：

struct animal

{

struct list_head list;

现在这个两个结构看起来就更差不多一样了。现在为了方便，我们去掉那些暂时不用的数据，如下：

struct person

{

struct list_head list;

};

表示动物的：

（即 4 个字节），只是不同类型的指针在解释的时候不一样而已，那么这个 struct list_head 又是怎么去

做这些结构的链表指针呢，那么就请看下一节吧：）。

二、struct list_head 结构的操作

首先，让我们来看下和 struct list_head 有关的两个宏，它们定义在 list.h 文件中。

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \

(ptr)->next = (ptr); (ptr)->prev = (ptr); \

} while (0)

这两个宏是用了定义双向链表的头节点的，定义一个双向链表的头节点，我们可以这样：

我们再看下和其相关的几个函数，这些函数都作为内联函数也都定义 list.h 中，这里要说明一下 linux 源码

的函数，这些函数一般都是调用以下划线开始的函数，或是说是对下划线开始的函数的封装。

2.1 增加节点的函数

static inline void __list_add();

static inline void list_add();

static inline void list_add_tail();

其实看源代码是最好的讲解了，这里我再简单的讲一下。

/**

* __list_add - Insert a new entry between two known consecutive entries.

* @new: