C语言链表

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);
    }

参考

1. https://www.cs.uic.edu/~hnagaraj/articles/linked-list/
2. https://kernelnewbies.org/FAQ/LinkedLists