Linux 内核学习(11) --- Linux 链表结构

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