C语言链表
2019-03-25 本文已影响0人
louyang
1 准备
在Fedora 29中，使用下述命令安装内核源代码.
$ sudo dnf install kernel-devel
2 例子1
编写一个最简单的链表程序，3个节点依次加入链表后遍历：
#include <stdio.h>
#include "linux/list.h"
struct foo {
int data;
struct list_head list;
};
int main()
{
struct foo first = {
.data = 10,
.list = LIST_HEAD_INIT(first.list)
};
struct foo second = {
.data = 20,
.list = LIST_HEAD_INIT(second.list)
};
struct foo third = {
.data = 30,
.list = LIST_HEAD_INIT(third.list)
};
LIST_HEAD(head);
list_add(&first.list, &head);
list_add(&second.list, &head);
list_add(&third.list, &head);
struct foo *ptr = NULL;
list_for_each_entry(ptr, &head, list) {
printf("%d ", ptr->data);
}
printf("\n");
}
运行：
$ gcc a.c -I/usr/src/kernels/4.20.16-200.fc29.x86_64/tools/include/ && ./a.out
30 20 10
稍微改变一下：
...
list_add(&first.list, &head);
list_add(&second.list, &first.list);
list_add(&third.list, &second.list);
...
运行结果有所不同：
$ gcc a.c -I/usr/src/kernels/4.20.16-200.fc29.x86_64/tools/include/ && ./a.out
10 20 30
3 代码分析
3.1 首先，我们有个简单的数据结构
struct foo {
int data;
};
3.2 我们想把它变成一个链表
只需要在数据结构中加入struct list_head list
struct foo {
int data;
struct list_head list;
};
struct list_head定义在linux/types.h头文件中：
struct list_head {
struct list_head *next, *prev;
};
现在数据结构可以理解为如下图:
image.png
list_head也许在这里叫list_hook更合适。
3.3 实例化某个节点
定义一个 变量，变量名叫first.
struct foo first = {
.data = 10,
.list = LIST_HEAD_INIT(first.list)
};
LIST_HEAD_INIT定义在list.h中，
#define LIST_HEAD_INIT(name) { &(name), &(name) }
所以first这个变量看上去这个样子:
image.png
同样的道理，我们有second和third。
image.png
image.png
3.4 定义链表头
LIST_HEAD(head);
LIST_HEAD定义在list.h中：
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
image.png
3.5 把3个节点串成一串
list_add(&first.list, &head);
list_add(&second.list, &first.list);
list_add(&third.list, &second.list);
list_add定义在list.h文件中：
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
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;
}
图示下面这三行代码：
list_add(&first.list, &head);
list_add(&second.list, &first.list);
list_add(&third.list, &second.list);
image.png
4 例子2
另外一种写法：
#include <stdio.h>
#include "linux/list.h"
struct foo {
int data;
struct list_head list;
};
int main()
{
struct foo first, second, third;
first.data = 10,
second.data = 20,
third.data = 30,
INIT_LIST_HEAD(&first.list);
INIT_LIST_HEAD(&second.list);
INIT_LIST_HEAD(&third.list);
LIST_HEAD(head);
list_add(&first.list, &head);
list_add(&second.list, &head);
list_add(&third.list, &head);
struct foo *ptr = NULL;
list_for_each_entry(ptr, &head, list) {
printf("%d ", ptr->data);
}
printf("\n");
}
运行：
$ gcc b.c -I/usr/src/kernels/4.20.16-200.fc29.x86_64/tools/include/ && ./a.out
30 20 10
5 例子3
使用安全接口遍历，就算是同时有节点被删除，也OK。
struct foo *ptr, *tmp = NULL;
list_for_each_entry_safe(ptr, tmp, &head, list) {
printf("%d ", ptr->data);
}
