关键词：
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
