32_Linux内核链表剖析

关键词：

0. 课程目标

• 移植Linux内核链表，使其适用于非GNU编译器
• 分析Linux内核中链表的基本实现

1. 移植时的注意事项

• 清除文件间的依赖：剥离依赖文件中与链表实现相关的代码
• 清楚平台相关代码（GNU C）
  ({ })
typeof
__builtin_prefetch
static inline

2. Linux内核链表的实现

• 带头结点的双向循环链表，且头结点为表中成员
• 头结点的next指针指向首结点
• 头结点的prev指针指向尾结点
  Linux内核链表原理图

3. Linux内核链表的结点定义

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

在Linux内核链表结点定义中，结点的数据域放在哪儿？
使用Linux内核链表时，需要用户自定义Node结点，结点中包含了指针域和数据域。如下

struct Node
{
    struct list_head head;      // 指针域
    int value;                  // 数据域
    //...
};

4. Linux内核链表的创建及其初始化

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

struct Node
{
    struct list_head head;      // 指针域
    int value;                  // 数据域
};

int main(void)
{
    struct Node l = {0};    // 创建链表头结点
    struct list_head* list = (struct list_head*)&l;

    INIT_LIST_HEAD(list);   // 初始化头结点

    return 0;
}

5. INIT_LIST_HEAD()源码：

static void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

INIT_LIST_HEAD源码示意图

6. 插入操作

• 在链表头部插入：list_add(node, head)
• 在链表尾部插入：list_add_tail(node, head)

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

static void list_add(struct list_head *node, struct list_head *head)
{
    __list_add(node, head, head->next);
}

static void list_add_tail(struct list_head *node, struct list_head *head)
{
    __list_add(node, head->prev, head);
}

7. 删除操作

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

static void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}

8. 遍历操作

• 正向遍历：list_for_each(pos, head)
• 逆向遍历：list_for_each_pre(pos, head)

/**
 * list_for_each    -   iterate over a list
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:   the head for your list.
 */
#define list_for_each(pos, head) \
    for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            pos = pos->next)

/**
 * list_for_each_prev   -   iterate over a list backwards
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:   the head for your list.
 */
#define list_for_each_prev(pos, head) \
    for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
            pos = pos->prev)

Linux内核中遍历操作是通过宏定义来实现的，式中关键字prefetch是gnu中特有的关键字，为了在不同的操作系统中使用，需要重定义这个关键字为#define prefetch(x) ((void)x)

9. list_entry

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

10. 相关测试

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

void test_demo1()
{
    struct Node
    {
        struct list_head head;      // 指针域
        int value;                  // 数据域
    };

    struct Node l = {0};    // 创建链表头结点
    struct list_head* list = (struct list_head*)&l;
    struct list_head* slide = NULL;
    struct list_head* toDel = NULL;
    int value = 0;
    int i = 0;

    INIT_LIST_HEAD(list);   // 初始化头结点

    printf("Insert begin...\n");

    for(i=0; i<5; ++i)
    {
        struct Node* n = ( struct Node*)malloc(sizeof(struct Node));
        n->value = i;
        list_add_tail((struct list_head*)n, list);
    }

    list_for_each(slide, list)
    {
        printf("%d\n", ((struct Node*)slide)->value);
    }

    printf("Insert end...\n");

    printf("Delete begin...\n");

    list_for_each(slide, list)
    {
        value = ((struct Node*)slide)->value;
        if( value == 3 )
        {
            list_del(slide);
            free(slide);
            break;
        }
    }

    list_for_each(slide, list)
    {
        printf("%d\n", ((struct Node*)slide)->value);
    }

    printf("Delete end...\n");
}

void test_demo2()
{
    struct Node
    {
        int value;                  // 数据域
        struct list_head head;      // 指针域
    };

    struct Node l = {0};    // 创建链表头结点
    struct list_head* list = &l.head;
    struct list_head* slide = NULL;
    int i = 0;

    INIT_LIST_HEAD(list);   // 初始化头结点

    printf("Insert begin...\n");

    for(i=0; i<5; ++i)
    {
        struct Node* n = ( struct Node*)malloc(sizeof(struct Node));
        n->value = i;
        list_add(&n->head, list);
    }

    list_for_each(slide, list)
    {
        printf("%d\n", (list_entry(slide, struct Node, head)->value));
    }

    printf("Insert end...\n");

    printf("Delete begin...\n");

    list_for_each(slide, list)
    {
        struct Node* n = list_entry(slide, struct Node, head);
        if( n->value == 3 )
        {
            list_del(slide);
            free(n);
            break;
        }
    }

    list_for_each(slide, list)
    {
        printf("%d\n", list_entry(slide, struct Node, head)->value);
    }

    printf("Delete end...\n");
}

int main(void)
{
    test_demo1();
    test_demo2();

    return 0;
}

11. 小结

• Linux内核链表移植时需要剔除依赖以及平台相关代码
• Linux内核链表是带头结点的双向循环链表
• 使用Linux内核链表时需要自定义链表结点：
  (1) 将struct list_head作为结点结构体的第一个成员或最后一个成员
  (2) struct list_head作为最后一个成员时，需要使用list_entry宏
  (3) list_entry的定义中使用了container_of宏

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4