本文共 5869 字，大约阅读时间需要 19 分钟。
（转自：）
摘要：描述了普通链表、内核链表以及他们之间的区别，介绍了对链表进行创建，插入，遍历和删除的操作，使用内核链表对足球队球员信息进行操作，详细对内核链表中的各个函数进行了分析。
一、链表的概念与种类
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列节点组成，节点可以运行时动态生成。每个节点包括两个部分：一是存储数据元素的数据域，另一个是存储其它节点地址的指针域。建立链表无须预知数据总量，可以随机分配空间，可以高效的在任意位置实时的插入和删除节点，链表的开销主要是访问的顺序性和组织节点的空间损失。
链表分为单向链表、双向链表和循环双向链表。单向链表只有一个指向后继节点的指针，链表头代表了整个链表的基地址，最后一个节点的指针域为NULL。双向链表有两个指针，一个是后继节点的指针，一个是前一个节点的指针，这样就可以实现向前和向后两个方向的操作，但是头指针只有向后的指针，末尾指针只有向前的指针。双向循环链表的头指针指向末尾，末尾的指针指向头，这样就变成了一个循环。在我们Linux内核当中，使用的是双向循环链表。
二、内核链表和普通链表的区别
最大的区别就是内核链表中的链表元素不与特定的类型相关，具有通用性，为什么呢？看下面的图：
上面kernel list是内核链表，下面normal list是普通链表。可以看出其指针域都是指向前一个或者下一个节点的指针域，这样就避免了数据域的不同结构类型之间的冲突，任何结构体都可以通过内核的添加成为链表中的节点。而普通链表则指向其他节点的数据域，这样每次插入操作不同的数据类型都要修改前向和后继指针的类型，操作比较繁琐。
三、内核链表的结构与函数
structlist_head
{
structlist_head *prev,*next;
}
这是一个基本的内核链表结构体，next和prev分别是指向前驱和后继list_head的指针，是一个双向循环链表。
1.初始化链表头
staticinline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
将后继指针和前驱指针都指向自己list，这样后面进行插入就可以了。
2.插入
对链表的插入操作有两种：在表头插入和在表尾插入。Linux为此提供了两个接口：
list_add(struct list_head *list, struct list_head*head)
list_add_tail(struct list_head *list, struct list_head*head)
3.删除
list_del(struct list_head *entry);
4.遍历
list_for_each(pos, head)
5.链表节点到数据项
list_entry(ptr,type, member)
container_of(ptr,type, member)
list_entry宏是用来根据list_head指针查找链表所嵌入的结构体的地址，具体实现是依赖container_of。主要是求出内层结构体字段到外层的偏移量，计算的方式是，将外层结构体的地址设置为0，然后就有该字段的地址 =
该字段到外层结构体的偏移量。这些函数具体实现我们后面分析。
四、使用内核链表操作足球队球员信息
首先，要创建一个链表，就需要创建一个链表头，然后再将各个节点加进去，这里我打算链表结构中存放球员的号码，进球数和助攻数。单个节点如下图：
切到工作目录，创建两个文件，一个mylist.c一个Makefile。
1.Makefile内容如下：
obj-m:= mylist.o
KDIR:= /home/passionbird/project/test/linux-2.6.32.2
all:
make -C $(KDIR) M=$(PWD) modulesCROSS_COMPILE=arm-linux- ARCH=arm
clean:
rm -rf $(TARGET) *.o *.order *.symvers *.mod
红色字体部分添加你编译下载到开发板上的内核，不要添加错了。
2.mylist.c初步内容如下
初步先这样写，然后往里填
-
#include<linux/module.h> -
#include<linux/init.h> -
#include<linux/list.h> -
struct member -
{ -
num; -
score; -
assists; -
structlist_head list; -
}; -
int mylist_init() -
{ -
return 0; -
} -
void mylist_exit() -
{ -
} -
module_init(mylist_init); -
module_exit(mylist_exit);
首先添加头文件，然后末尾两个宏，现在mylist_init和mylist_exit什么都不做。然后在开头定义一个结构体
structmember
{
num;
score;
assists;
structlist_head list;
};
其中包含了号码，得分，助攻和一个list_head结构体，命名为list，这其实就对应我们刚才画的图。
创建链表：
#include<linux/list.h>
structlist_head member_head;
INIT_LIST_HEAD(&member_head);
staticinline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
这个函数需要头文件/list.h的支持，同时这里给进去的参数是一个list_head结构体的指针，我们这里给了member_head的地址，在内部这个指针前向和后继都指向自己，这样我们就完成了链表头的创建。
插入节点：
插入之前给成员变量赋值：
structmember memb1,memb2,memb3,memb4;
memb1.num= 9;
memb1.score= 1;
memb1.assists=2;
memb2.num= 66;
memb2.score= 0;
memb2.assists=0;
memb3.num= 21;
memb3.score= 1;
memb3.assists=1;
memb4.num= 10;
memb4.score= 2;
memb4.assists=0;
节点插入函数如下：
staticinline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
这里的第一个参数要填进去的是你的新节点的的list_head，后面这里是刚才创建的头节点的list_head，两个参数都需要是指针变量，调用方式如下：
list_add_tail(&(memb1.list),&member_head);
list_add_tail(&(memb2.list),&member_head);
list_add_tail(&(memb3.list),&member_head);
list_add_tail(&(memb4.list),&member_head);
这样我们就将其全部节点插入进去了。
遍历链表：
便利链表的函数如下;
#definelist_for_each(pos, head) \
for(pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
list_for_each其实是一个for循环，这里给进去的第二个参数head使我们需要遍历的链表头，也就是memnber_head，第一个参数pos是一个struct head_list类型的指针，会不断地去指向每一个节点的指针域，这里需要去定义：
structlist_head *pos;
因为pos指向的是指针域的，但是我们的数据域和指针域具有偏移（不同于普通链表，普通链表是指向数据域的）。所以这里需要使用list_entry将节点取出来，函数如下：
#definelist_entry(ptr, type, member) \
container_of(ptr,type, member)
也就是它依赖于container_of这个函数：
函数的思想如下：
第一步，首先定义一个临时的数据类型（通过typeof(((type *)0)->member )获得）与ptr相同的指针变量__mptr，然后用它来保存ptr的值。
第二步，用(char *)__mptr减去member在结构体中的偏移量，得到的值就是整个结构体变量的首地址（整个宏的返回值就是这个首地址）。
点看参数说明：
/**
*list_entry - get the struct for this entry
*@ptr: the &struct list_head pointer.
*@type: the type of the struct this isembedded in.
*@member: the name of the list_struct withinthe struct.
*/
ptr是在结构里面指向list_head的指针，这里指的是pos。
type指的是要获取的数据域的数据的类型。
member指的就是结构体list指针域中成员的名称。
调用如下：
temp=list_entry(pos,structmember,list);
这里temp还需要提前定义为struct member类型的，
structmember *temp;
printk("number%d,score %d, assists %d\n",temp->num,temp->score,temp->assists);
删除节点：
函数如下：
staticinline void list_del(struct list_head *entry)
{
__list_del(entry->prev,entry->next);
entry->next= LIST_POISON1;
entry->prev= LIST_POISON2;
}
可以看出这里传进去的参数只有一个，也就是要删除的节点的指针域的地址。
这里函数如下：
voidmylist_exit(void)
{
list_del(&(memb1.list));
list_del(&(memb3.list));
}
mylist.c完整代码如下：
-
<span style="font-size:14px;">#include<linux/module.h> -
#include<linux/init.h> -
#include<linux/list.h> -
MODULE_LICENSE("GPL"); -
MODULE_AUTHOR("Deep_l_zh"); -
struct member -
{ -
int num; -
int score; -
int assists; -
struct list_head list; -
}; -
struct list_head member_head; -
struct member memb1,memb2,memb3,memb4; -
struct list_head *pos; -
struct member *temp; -
int mylist_init(void) -
{ -
INIT_LIST_HEAD(&member_head); -
memb1.num = 9; -
memb1.score = 1; -
memb1.assists =2; -
list_add_tail(&(memb1.list),&member_head); -
memb2.num = 66; -
memb2.score = 0; -
memb2.assists =0; -
list_add_tail(&(memb2.list),&member_head); -
memb3.num = 21; -
memb3.score = 1; -
memb3.assists =1; -
list_add_tail(&(memb3.list),&member_head); -
memb4.num = 10; -
memb4.score = 2; -
memb4.assists =0; -
list_add_tail(&(memb4.list),&member_head); -
list_for_each(pos,&member_head) -
{ -
temp = list_entry(pos,struct member,list); -
printk("number %d,score %d, assists %d\n",temp->num,temp->score,temp->assists); -
} -
return 0; -
} -
void mylist_exit(void) -
{ -
list_del(&(memb1.list)); -
list_del(&(memb3.list)); -
} -
module_init(mylist_init); -
module_exit(mylist_exit);</span>
这时候编译下载到开发板，可以看到输出如下信息：
/# insmod mylist.ko
number9,score 1, assists 2
number66,score 0, assists 0
number21,score 1, assists 1
number10,score 2, assists 0
/ #
表明我们的链表建立，插入和遍历都成功了。
下一篇帖子打算在应用程序中使用内核链表进行一整套的操作，这篇帖子就到这里吧，如有不正确的地方，还请指出，大家共同进步。