Linux内核中的链表通常都组织成双向循环链表,不同于一般意义上的链表,这里的链表节点只含有链表指针(next和prev),没有链表的数据。Linux内核中使用的链表源代码位于
include/linux/list.h
中,下面详细叙述。
1. 链表数据结构 list_head 的定义:
struct list_head {
struct list_head *next, *prev;
};
【注意】只有前后节点指针,没有数据 !
2. 链表的声明和初始化
2.1静态方法——编译时
#define LIST_HEAD_INIT(name) { &(name), &(name) } // 链表的pre和next指针都指向了节点自己的首地址
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
2.2动态方法——运行时
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
图示:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5SN3gzM4cTNlZWOmNWNwEzMzYzX1EjM1kDM2IzLclDMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
3. 插入/删除/合并
3.1插入
3.1.1 头插——list_add
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
3.1.2 尾插—— list_add_tail
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
- 可以看到他们调用了相同的
函数: __list_add
//将链表节点new插在prev和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;
}
3.2 删除
- 对链表的删除操作函数有两种:list_del函数和list_del_init函数:
3.2.1 list_del
static inline void list_del(struct list_head *entry) // entry:要删除的链表的首地址
{
__list_del(entry->prev, entry->next); // 等价于__list_del_entry(entry)
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
- 将链表节点entry从链表中删除后,list_del函数中又将entry的next和prev指针指向了LIST_POISON1和LIST_POISON2位置,使得以后若再对他们进行访问都将引起页故障,以确保不在链表中的节点项不可访问。
3.2.2 list_del_init
static inline void list_del_init(struct list_head *entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry); // 运行中初始化链表节点
}
static inline void __list_del_entry(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
- 将链表节点entry从链表中删除后,list_del_init函数中又将entry重新初始化了(next和prev指针指向了自己)。在此不再画图,唯一的不同是把删除下来的图的next和prev指针指向了自己的首地址
- 他们调用了相同的
函数__list_del
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
3.3 替换
对链表的替换操作有两个:list_replace函数和list_replace_init函数:
3.3.1 list_replace
static inline void list_replace(struct list_head *old, struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
3.3.2 list_replace_init
static inline void list_replace_init(struct list_head *old, struct list_head *new)
{
list_replace(old, new);
INIT_LIST_HEAD(old);
}
list_replace_init函数的图形在此处也不再画,区别就是多了初始化换下来的old节点
3.4 搬移
搬移的含义是将原本属于一个链表的节点移动到另一个链表的操作,有两个函数:list_move函数和list_move_tail函数:
3.4.1 list_move
/*
* list_move:把节点list从原先链表上搬移到另一个链表head的头部
* @list: 我们要移动的节点
* @head: 要移动到的另外的一个链表头
*/
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del_entry(list);
list_add(list, head);
}
3.4.2 list_move_tail
/*
* list_move_tail:把节点list从原先链表上搬移到另一个链表head的尾部
* @list: the entry to move
* @head: the head that will follow our entry
*/
static inline void list_move_tail(struct list_head *list, struct list_head *head)
{
__list_del_entry(list);
list_add_tail(list, head);
}
3.5 合并
合并在这里的意思就是合并了,是将两个独立的链表合并成为一个链表,合并的时候根据合并的位置的不同可以分为:
合并到头部的 list_splice函数和
合并到尾部的 list_splice_tail函数:(这两个函数有推荐使用的函数)
3.5.1 list_splice
/*
* list_splice: join two lists, this is designed for stacks
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(const struct list_head *list, struct list_head *head) {
if (!list_empty(list))
__list_splice(list, head, head->next);
}
- 假设当前有两个链表,表头分别是list1和list2(都是struct list_head变量),当调用list_splice(&list1,&list2)时,只要list1非空,list1链表的内容将被挂接在list2链表上,位于list2和list2.next(原list2表的第一个节点)之间。新list2链表将以原list1表的第一个节点为首节点,而尾节点不变。
3.5.2 list_splice_tail
/*
* list_splice_tail - join two lists, each list being a queue
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice_tail(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head->prev, head);
}
- 假设当前有两个链表,表头分别是list1和list2(都是struct list_head变量),当调用list_splice_tail(&list1,&list2)时,只要list1非空,list1链表的内容将被挂接在list2链表上,位于list2尾节点和list2(原list2头)之间。新list2链表将以原list1表的最后一个节点为尾节点,而头节点不变。
3.5.3 list_splice_init
static inline void list_splice_init(struct list_head *list, struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head, head->next);
INIT_LIST_HEAD(list); <--- 跟list_splice唯一的不同
}
}
3.5.4 list_splice_tail_init
static inline void list_splice_tail_init(struct list_head *list, struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head->prev, head);
INIT_LIST_HEAD(list); <--- 跟list_splice_tail唯一的不同
}
}
- 共同的函数
和__list_splice
list_empty
//将链表list插入到另一个链表的prev和next节点之间
static inline void __list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
first->prev = prev;
prev->next = first;
last->next = next;
next->prev = last;
}
//判断链表head是否为空
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
4. 找到链表中的数据
前边提到的函数都是操作的链表节点的入口,但是对于我们真正有意义的是节点上的数据,链表的头上没有数据,其他的节点上都是带有数据的。如何从一个链表节点的入口得到节点的数据呢?要用到以下的函数
list_entry函数:
/*
* list_entry - 通过链表地址获得包含该链表的结构体的地址
* @ptr: member的首地址
* @type: 容器的类型
* @member: 要得到他的容器的某个成员
*/
#define list_entry(ptr, type, member)\
container_of(ptr, type, member)
#define container_of(ptr, type, member) ({\
const typeof( ((type *)0)->member ) *__mptr = (ptr);
(type *)( (char *)__mptr - offsetof(type,member) );})
// 将数据结构体放到0地址处,天然的结构体中成员的首地址就是成员在结构体中的偏移量(字节)
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
举例:
main.c
#include <stdio.h>
#include <linux/list.h>
LIST_HEAD(device_list);
typedef struct device_struct
{
unsigned char *devname;
struct list_head entry;
} device_struct_s;
int main(int argc, const char *argv[])
{
device_struct_s led;
device_struct_s *ledp;
led.devname = "led";
/* 添加到链表的前边 */
list_add(&led.entry, &device_list);
/* 得到含有链表节点的数据结构体的首地址 */
ledp = list_entry(device_list.next, device_struct_s, entry);
printf("led.devname = %s\n", ledp->devname);
return 0;
}
5. 遍历链表
对linux内核的遍历可以分为遍历链表和遍历链表中的结构体:
从头开始遍历链表,
list_for_each
宏;
从头开始遍历链表中的结构体,
list_for_each_entry
宏;
5.1 遍历链表
/*
* list_for_each - 迭代/遍历 链表
* @pos: 链表指针.
* @head: 要遍历的链表头地址
*/
#define list_for_each(pos, head)
for (pos = (head)->next; pos != (head); pos = pos->next)
5.2 遍历链表中的结构体
/*
* list_for_each_entry - 遍历含链表节点入口的结构体
* @pos: the type * to use as a loop cursor.
* @head: 要遍历的链表头地址
* @member: 结构体中链表入口的名字
*/
#define list_for_each_entry(pos, head, member)\
for (pos = list_entry((head)->next, typeof(*pos), member);\
&pos->member != (head);\
pos = list_entry(pos->member.next, typeof(*pos), member))
- 举例
#include <stdio.h>
#include <linux/list.h>
LIST_HEAD(device_list);
typedef struct device_struct
{
unsigned char *devname;
struct list_head entry;
} device_struct_s;
int main(int argc, const char *argv[])
{
device_struct_s led, gpio, beep, *tmp;
led.devname = "led";
gpio.devname = "gpio";
beep.devname = "beep";
/* 一个一个往链表的头部添加 */
list_add(&led.entry, &device_list);
list_add(&gpio.entry, &device_list);
list_add(&beep.entry, &device_list);
/* 1. 遍历链表 */
struct list_head *i;
list_for_each(i, &device_list)
{
tmp = list_entry(i, device_struct_s, entry);
printf("tmp.devname = %s\n", tmp->devname);
}
/* 2. 遍历含链表的结构体 */
device_struct_s *j;
list_for_each_entry(j, &device_list, entry)
{
printf("j.devname = %s\n", j->devname);
}
return 0;
}
- 输出结果
tmp.devname = beep
tmp.devname = gpio
tmp.devname = led
j.devname = beep
j.devname = gpio
j.devname = led
另外:
- linux内核的链表中提供了反向遍历链表的宏
和list_for_each_prev
,他们分别是list_for_each_entry_reverse
和list_for_each
的反方向的实现,使用方法完全一样。list_for_each_entry
- 如果遍历不是从链表头开始,而是从已知的某个节点pos开始,则要使用
宏(使用方法同list_for_each_entry宏)。list_for_each_entry_continue
- 如果想实现如果pos有值则从pos开始遍历,如果没有则从链表的头开始遍历,为此,Linux专门提供了一个
宏,将它的返回值作为list_prepare_entry(pos,head,member)
的pos参数,就可以满足这一要求。list_for_each_entry_continue()
- 我们将list_for_each_prev和list_for_each_entry_reverse的代码和执行结果也写下来:
/* 3. 反向遍历链表的入口的首地值 */
printf("list_for_each_prev()\n");
struct list_head *k;
list_for_each_prev(k, &device_list)
{
tmp = list_entry(k, device_struct_s, entry);
printf("tmp.devname = %s\n", tmp->devname);
}
/* 4. 反向遍历含链表的入口的结构体的首地值 */
printf("list_for_each_reverse()\n");
device_struct_s *g;
list_for_each_entry_reverse(g, &device_list, entry)
{
printf("g.devname = %s\n", g->evname);
}
结合上边代码的执行结果如下:
list_for_each_prev() <— 可以看到遍历结果是从尾部遍历到头部
tmp.devname = led
tmp.devname = gpio
tmp.devname = beep
list_for_each_reverse() <— 可以看到遍历结果是从尾部遍历到头部
g.devname = led
g.devname = gpio
g.devname = beep