Linked List 简介

链表是一种数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针
链表可以动态增长或者缩小，适合频繁的插入和删除操作，常见的链表类型有单向链表和双向链表

在 linux 内核开发中，开发者无需自己实现链表或者使用第三方库，内核内置了双向链表实现 struct list_head
定义在 linux/list.h 中

Linked List 操作方法

链表头结点初始化

Linux 内核链表用链表头 list_head 来表示，因为链表初始化其实就是初始化一个链表头节点

LIST_HEAD(demo_list)

LIST_HEAD 宏将创建一个名称为 demo_list 的链表，其实是一个链表头节点，在没有插入如何节点之前，它的首位指针指向自身，也可以认为首尾指针指向自身时链表就是空的

#define LIST_HEAD_INIT(name) {&(name), &(name)};#define LIST_HAED(name) \struct list_head name = LIST_HEAD_INIT(name);
struct list_head {struct list_head *next;struct list_head *prev;
}

注意 LIST_HAED 宏可以用于定义个链表头节点，LIST_HEAD_INIT 只能用于初始化链表头结点

创建链表节点

Linux 内核链表节点也使用 list_head 来表示，通常内嵌在自定义数据结构中:

struct my_node {struct list_head list;int data;
};struct my_node node

链表节点在插入链表之前也需要初始化，使用 INIT_LIST_HEAD 宏

添加节点到链表中

链表有节点初始化后，就可以往链表中添加节点:

static inline void list_add(struct list_head *new, struct list_head *head)
static inline void list_add_tail(struct list_head *new, struct list_head *head)

其中的 head 表示链表头，new 表示要添加的节点，

list_add 将 new 添加到链表头部
list_add_tail 将 new 添加到链表尾部

从链表中删除节点

从链表中删除节点实际上就是修改下一节点及其相邻节点的 prev 和 next 指针指向，并不会释放节点的内存
其中的 list_del_init 删除节点之后还会对该节点重新进行初始化操作

static inline void list_del(struct list_head *entry)
static inline void list_del_init(struct list_head *entry)

从链表中替换节点

和删除节点同理，替换节点也只是修改了 prev 和 next 的指针指向，并且 list_replace_init 还会对替换出来的节点
进行重新的初始化操作

static inline void list_replace(struct list_head *old, struct list_head *new)
static inline void list_replace_init(struct list_head *old, struct list_head *new)

移动链表中的节点

下面的函数中，list 表示要移动的链表，list_move 表示将其移动到链表首部，
list_move_tail 将其移动到链表尾部

static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list,struct list_head *head)

检查链表

Linux 内核还提供了检查链表的相关函数，例如:

• list_is_last: 检查节点是否是链表最后一个节点
• list_empty: 链表是否为空
• list_is_singular: 链表是否只有一个节点

static inline int list_is_last(const struct list_head *list,const struct list_head *head)
static inline int list_empty(const struct list_head *head)
static inline int list_is_singular(const struct list_head *head)

链表遍历

Linux 提供了一系列函数来遍历和操作链表中的元素:

• list_entry(ptr, type, member): 通过链表节点的地址获取包含该节点的结构体指针
• list_for_each(pos, head) : 遍历链表的每个节点
• list_for_each_entry(pos, head, member) : 遍历链表中的每个结构体实例
• list_for_each_entry_safe(pos, n, head, member) : 安全的遍历链表中每个结构体实例，可以在遍历过程中安全删除节点
• list_for_each_prev(pos, head): 逆向遍历链表中的每个节点
• list_for_each_entry_reverse(pos, head, member): 逆向遍历链表中每个结构体实例

#define list_entry(ptr, type, member) \
container_of(ptr, type, member)#define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)#define list_for_each_entry(pos, head, member)				\for (pos = list_first_entry(head, typeof(*pos), member);	\&pos->member != (head);					\pos = list_next_entry(pos, member))#define list_for_each_entry_safe(pos, n, head, member)			\for (pos = list_first_entry(head, typeof(*pos), member),	\n = list_next_entry(pos, member);			\&pos->member != (head); 					\pos = n, n = list_next_entry(n, member))#define list_for_each_prev(pos, head) \for (pos = (head)->prev; pos != (head); pos = pos->prev)#define list_for_each_entry_reverse(pos, head, member)			\for (pos = list_last_entry(head, typeof(*pos), member);		\&pos->member != (head); 					\pos = list_prev_entry(pos, member))

demo 实例

//static LIST_HEAD(demo_list);
static struct list_head demo_list;static struct demo_linklistnode {char buffer[LINKEDLIST_BUFFER_SIZE];struct list_head list;
};static ssize_t mdrv_read(struct file *file, char __user *buf, size_t size, loff_t *offset) {size_t to_read = min(size, BUFFER_SIZE - (size_t)*offset);if(to_read == 0) {return 0;}printk(KERN_DEBUG "%s: to_read size:%zu .\n", __func__, to_read);if(copy_to_user(buf, device_buffer + *offset, to_read)) {return -EFAULT;}struct demo_linklistnode* tempnode, *nextnode;int i = 0;list_for_each_entry_safe(tempnode, nextnode, &demo_list, list) {printk(KERN_DEBUG "Node[%d] buffer:%s", i, tempnode->buffer);if(list_is_first(&tempnode->list, &demo_list)) {printk(KERN_DEBUG "==> fist node");} else if(list_is_last(&tempnode->list, &demo_list)) {printk(KERN_DEBUG "==> last node");}printk(KERN_DEBUG "\n");i++;}*offset += to_read;return to_read;
}static ssize_t mdrv_write(struct file *file, const char __user *buf, size_t size, loff_t *offset) {size_t to_write = min(size, BUFFER_SIZE - (size_t)*offset);if(to_write == 0) {return -ENOMEM;}printk(KERN_DEBUG "%s: to_write size %zu .\n", __func__, to_write);if(copy_from_user(device_buffer + *offset, buf, to_write)) {return -EFAULT;}struct demo_linklistnode *node = NULL;node = kmalloc(sizeof(struct demo_linklistnode), GFP_KERNEL);if(!node) {printk(KERN_DEBUG "fail to allocate demo_linklistnode buffer\n");return -ENOMEM;}memset(node->buffer, 0, LINKEDLIST_BUFFER_SIZE);memcpy(node->buffer, device_buffer + *offset, to_write);INIT_LIST_HEAD(&node->list);//list_add(&node->list, &demo_list);list_add_tail(&node->list, &demo_list);*offset += to_write;return to_write;
}