linux内核的链表实现
定义链表节点和初始化
LIST_HEAD_INIT宏通过将next和prev都指向自身，来对节点进行初始化
LIST_HEAD宏定义一个struct list_head类型的节点，并使用LIST_HEAD_INIT宏进行初始化
点击查看代码
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) \
{ &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
插入节点
linux内核实现了头插法和尾插法。
__list_add函数将待插入节点，插入到prev和next之间，而不管prev和next是什么
list_add和list_add_tail，参数列表一直，但使用__list_add的方式不一致。
list_add将头结点，作为prev。
list_add_tail将头结点的prev，作为prev。
因此list_add是头插法
list_add_tail是尾插法
点击查看代码
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_add(struct list_head *new, struct list_head *prev,
struct list_head *next) {
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new);
}
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head) {
__list_add(new, head, head->next);
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new,
struct list_head *head) {
__list_add(new, head->prev, head);
}
}
删除节点
点击查看代码
删除链表某个节点，使用list_del
__list_del负责将entry->next->prev 设置为 entrey -> prev。entry->prev->next 设置为 entry->next。entry自身的next指向LIST_POISON1，prev指向LIST_POISON2上。
/*
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_del(struct list_head *prev, struct list_head *next) {
next->prev = prev;
WRITE_ONCE(prev->next, next);
}
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty() on entry does not return true after this, the entry is
* in an undefined state.
*/
static inline void __list_del_entry(struct list_head *entry) {
if (!__list_del_entry_valid(entry))
return;
__list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head *entry) {
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}