内核链表

1. 基本概念

• 常规链表的缺陷

  • 每一种应用中，结点都是特殊的，导致每一条链表都是特殊的，因此每一种链表的增删查改这些算法也都是特殊的。
  • 当一个节点处于变化的数据结构网络中的时候，节点指针无法指向稳定不变的结点。

• Linux内核链表的原理

  • Linux 内核链表的结点只有两个指针（pre、next），链表的结点将独立于数据之外。

• 将链表“寄宿”于具体的数据节点之中，使他贯穿这些节点，可以借助一定的方式通过“纯粹链表“的指针域得到数据节点。

• 抽象后的内核链表

可以看出内核链表就是一个只有前驱指针域、后继指针域的双向循环链表，很多操作都跟普通的双向循环链表差不多。

2. 内核源码解读

2.1 小结构体声明

struct list_head                // 声明一个只有指针域的结构体
{
    struct list_head *pre;    	// 前驱指针域
    struct list_head *next; 	// 后继指针域
};

2.2 链表初始化以及定义头结点

• 链表初始化

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)

// 初始化小结构体，让其自己形成一个双向循环
#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0);

• 定义头结点

// 可以如下：
LIST_HEAD(head);
// 或者:
struct list_head head;
LIST_HEAD_INIT(head);

2.3 添加结点

• 将新结点new添加到以head为首的链表的开头

static inline void list_add(struct list_head *new, struct list_head *head)
{
    struct list_head *prev = head;			// 让前驱结点指向头结点
    struct list_head *next = head->next;	// 让后继结点指向头结点指向的下一个结点
    
    prev->next = new;		// 让前驱结点的后继指针指向新结点new
    new->next = next;		// 让新结点new的后继指针指向next结点
    next->prev = new;		// 让next结点的前驱指针指向新结点
    new->prev = prev;		// 让new结点的前驱指针指向前驱结点
}

• 将新结点new添加到以head为首的链表的末尾

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    struct list_head *prev = head->prev;	// 让前驱结点指向头结点指向的前驱结点（也就是没插入新结点时最末尾的结点）
    struct list_head *next = head;			// 让后继结点指向头结点（最末尾结点的后继指针是指向头结点的）
    
    prev->next = new;		// 让前驱结点的后继指针指向新结点new
    new->next = next;		// 让新结点new的后继指针指向next结点
    next->prev = new;		// 让next结点的前驱指针指向新结点
    new->prev = prev;		// 让new结点的前驱指针指向前驱结点
}

• 在两个结点之间插入新的结点

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

信息

从上面三种方式的插入结点代码跟图可以看出，它们的代码构成几乎是一样的。

它们的插入方式都是找到插入地方的前一个结点和后一个结点，然后断开它们之间的链接，将新结点与前一个结点、后一个结点联系起来。

• 内核链表中插入结点的实现代码

// 在两个结点中间插入新结点
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;
}
// 将新节点new插入到以head为首的链表的开头
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}
// 将新节点new插入到以head为首的链表的末尾
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

2.4 删除结点

• 通过查找前一个和后一个结点来删除结点

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

• 将entry指向的节点，从链表中剔除出去

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

• 删除完结点后并重新初始化

static inline void list_del_init(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	INIT_LIST_HEAD(entry);
}

2.5 移动结点

移动结点其实就是删除这个结点后不销毁，再采用插入结点的方法到指定位置。

• 将节点list移动到以head为首的链表的开头

static inline void list_move(struct list_head *list,struct list_head *head)
{
	__list_del(list->prev, list->next);
	list_add(list, head);
}

• 将节点list移动到以head为首的链表的末尾

static inline void list_move_tail(struct list_head *list,
					struct list_head *head)
{
	__list_del(list->prev, list->next);
	list_add_tail(list, head);
}

2.6 判断链表是否为空

static inline int list_empty(struct list_head *head)
{
	return head->next == head;
}

2.7 合并链表

• 将list和head两个链表合并

//合并后的头节点是head，将原来list的所有节点放在head的后面。
//比如： list 1 2 3 4   head 5 6 7 8 合并后：head 1 2 3 4 5 6 7 8
static inline void __list_splice(struct list_head *list,struct list_head *head)
{
	struct list_head *first = list->next;
	struct list_head *last = list->prev;
	struct list_head *at = head->next;

	first->prev = head;
	head->next = first;

	last->next = at;
	at->prev = last;
}
//如果list为空链表，就不用合并了，不为空才合并
static inline void list_splice(struct list_head *list, struct list_head *head)
{
	if (!list_empty(list))
		__list_splice(list, head);
}

• 连接两个列表并重新初始化空列表

static inline void list_splice_init(struct list_head *list,struct list_head *head)
{
	if (!list_empty(list)) 
    {
		__list_splice(list, head);
		INIT_LIST_HEAD(list);
	}
}

3. 内核链表中的宏

内核链表中的宏定义可以很方便用户进行使用传参。

3.1 遍历链表

遍历链表的宏定义其实就是 for 循环 只有到 pos 指针等于头结点的时候，才说明遍历完了。

• 从头开始往后遍历链表（遍历过程中，不可以将节点删除）

#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); \
pos = pos->next)

• 从头开始往后遍历链表（遍历过程中，可以将节点删除）

这个宏多定义了一个中间变量 n 来保存 pos 指针指向的下一个地址，这样就可以防止删除后找不到下一个结点。

#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)

• 从尾开始往前遍历链表（遍历过程中，不可以将节点删除）

#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); \
pos = pos->prev)

• 从头开始往后遍历链表（遍历过程中，可以将节点删除）

这个宏多定义了一个中间变量 n 来保存 pos 指针指向的下一个地址，这样就可以防止删除后找不到下一个结点。

#define list_for_each_prev_safe(pos, n, head) \
for (pos = (head)->prev, n = pos->prev; pos != (head); \
pos = n, n = pos->prev)

3.2 访问数据域宏

由于链表本质上是用来存储数据的，所以我们需要访问链表的数据域成员。而通用链表保存的是指针域的首地址，所以我们需要由指针域的首地址计算出数据域的首地址。

公式如下

数据域地址 = 指针域地址 - 数据域到指针域的偏移量

offset 宏

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

• **( TYPE * ) **将地址0强制转化成 TYPE 的指针。
• *( (TYPE )0 )->MEMBER 访问 TYPE 指针的 MEMBER 成员。
• *&( (TYPE )0 )->MEMBER 获取 MEMBER 成员的地址，也就是 MEMBER 成员在 TYPE 中的偏移量。
• *((size_t) &((TYPE )0)->MEMBER) 再将这个偏移量强制转换成size_t型数据（无符号整型）。

container_of 宏

#define container_of(ptr, type, member) ({			\
        const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
        (type *)( (char *)__mptr - offsetof(type,member) );})

• *typeof( ((type )0)->member ) 获取 member 成员的数据类型。
• **const typeof( ((type )0)->member ) __mptr = (ptr) 将 member 成员的指针赋值给 __mptr 。
• offsetof(type, member) 获取 type 中 member 成员的偏移量。
• *( (char )__mptr - offsetof(type,member) ) 获取 type 的起始地址。
• **(type )( (char )__mptr - offsetof(type,member) ) 将 type 的起始地址再转化回 type 类型。

3.3 获取宿主结点指针

list_entry 宏

#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

// 小结构体指针ptr转换成大结构体指针p: p = list_entry(ptr, type, member)
// ptr:小结构体指针
// type:大结构体类型
// member:小结构体在大结构体的名字

• 使用方法

struct list_head                // 声明一个只有指针域的结构体
{
    struct list_head *pre;    	// 前驱指针域
    struct list_head *next; 	// 后继指针域
}

struct user_info
{
	int id;
	char name[10];
	struct list_head node;
};

struct user_info user_tmp;
struct numlist *p = list_entry(user_tmp.id, struct numblist, node)
// p的地址就相当于user_tmp的地址，p.id == user_tmp.id

list_for_each_entry 宏

#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))

• list_for_each_entry 宏是一个 for 循环语句，for 循环的第一个参数就是让 (head)->next 指向 member 成员所在数据结构的指针，也就是将 pos 初始化为链表头指向的第一个实体链表成员。
• for 的第三个参数通过 pos->member.next 指针遍历整个实体链表。
• 当 pos->member.next 再次指向我们的链表头的时候跳出 for 循环。

整个过程没有对链表头进行遍历（不需要被遍历），所以使用list_for_each_entry遍历链表必须从链表头开始。

list_for_each_entry 的功能就是遍历以head为链表头的实体链表，对实体链表中的数据结构进行处理。

list_for_each_entry_safe 宏

#define list_for_each_entry_safe(pos, n, head, member)            \
for (pos = list_entry((head)->next, typeof(*pos), member),    \
n = list_entry(pos->member.next, typeof(*pos), member);    \
&pos->member != (head);                     \
pos = n, n = list_entry(n->member.next, typeof(*n), member))

• list_for_each_entry_safe 用指针n对链表的下一个数据结构进行了临时存储，所以在遍历链表的时候可以删除结点。
• 用 n 指针可以继续完成接下来的遍历， 而 list_for_each_entry 则无法继续遍历，删除后会导致无法继续遍历。

4. 部分内核链表的应用代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "kernel_list.h"

struct list_head head_node;

struct user_info
{
	int id;
	char name[20];
	struct list_head node;
};

void add_user_info(int id, char *name)
{
	struct user_info *user_tmp = (struct user_info *)malloc(sizeof(struct user_info));

	user_tmp->id = id;
	memcpy(user_tmp->name, name, strlen(name));

	list_add(&(user_tmp->node), &head_node);
}


int main(int argc, char *argv[])
{
	INIT_LIST_HEAD(&head_node);

	struct list_head *pos = NULL;
	struct user_info *user_tmp = NULL;

	add_user_info(1001, "zha_san");
	add_user_info(1002, "li_si");
	add_user_info(1003, "wang_wu");  // 添加数据
	
	list_for_each(pos, &head_node)   // 遍历
	{
		user_tmp = container_of(pos, struct user_info, node);

		printf("id = %d name = %s \n", user_tmp->id, user_tmp->name);
	}
	
	return 0;
}