1.定义头节点
/*结点结构*/
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)
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
2.插入新节点/*新节点添加在head和head->next之间，逆序添加*/
static __inline__ void list_add(struct list_head *new, struct list_head *head)
{
① ② ③
__list_add(new, head, head->next);
/*
* ①新节点
* ②头结点
* ③头结点的下一个节点
* 说明：新节点的插入操作总是在头结点和其下一个节点之间进行插入，即每次插入到第二的位置，逆序插入。
*/
}
/*新节点添加在head-prev和head之间,顺序添加*/
static __inline__ void list_add_tail(struct list_head *new, struct list_head *head)
{
① ② ③
__list_add(new, head->prev, head);
/*
* ①新节点
* ②头结的上一个节点，即尾节点
* ③头结点
* 说明：新节点的插入操作总是在头结点的上一个节点和头节点间插入，即每次插入到尾部，顺序插入。
*/
}
/*添加节点时链接关系的建立*/
static __inline__ void __list_add(struct list_head * new, struct list_head * prev, struct list_head * next)
/* ① ② ③
* nod1 head head //当新添nod1时，head = head->next = head->prev
* nod2 head nod1 //当新添nod2时，nod2插入head和nod1之间
* nod3 head nod2 //当新添nod3时，nod3插入head和nod2之间
*/
{ //当新添nod1时 //当新添nod2时 //当新添nod3时
next->prev = new; //head->prev = nod1; //nod1->prev = nod2; //nod2->prev = nod3;
new->next = next; //nod1->next = head; //nod2->next = nod1; //nod3->next = nod2;
new->prev = prev; //nod1->prev = head; //nod2->prev = head; //nod3->prev = head;
prev->next = new; //head->next = nod1; //head->next = nod2; //head->next = nod3;
}
3.删除节点
/*指定删除节点的地址*/
static __inline__ void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
/*建立前一个节点和后一个节点的链接*/
static __inline__ void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
/* 删除entry指向的节点，并让被删除节点的prev,next字段指向自己 */
static __inline__ void list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}
4.判断一个链表是否为空
static __inline__ int list_empty(struct list_head *head)
{
return head->next == head;
}
5.连接两个链表
static __inline__ void list_splice(struct list_head *list, struct list_head *head)
{
/*
* head，被加入/插入的链表头指针
* list，插入链表的头指针
*/
struct list_head *first = list->next; //插入链表的第一个节点
if (first != list) { //插入链表不为空
struct list_head *last = list->prev; //插入链表的尾节点
struct list_head *at = head->next; //被插入链表的第一个节点
//将list插入head链表的head和head->next之间，即插入头节点和第一节点之间
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
}
6.list_entry
作用：从ptr指向的结构中，计算member成员所在的绝对地址，即计算member的指针。
原理是：member的地址 = ptr指向的地址 - 零地址处的member偏移量
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
7.遍历链表
#define list_for_each(pos, head) \
for (pos = (head)->next, prefetch(pos->next); pos != (head); \
pos = pos->next, prefetch(pos->next))
以上等价于
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
其中prefetch(x)是一个宏，它的主要作用是将变量x预取到CPU L1 缓存，起加速作用，对程序逻辑没有影响。