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