非侵入式链表

数据和指针保存在同一个数据结构中，数据类型和链表是耦合在一起的，缺点对每一种类型都得实现 一个，或者一整条链必须是同一种类型。但是有时候就是想把很多东西串起来。

侵入式链表

数据节点包含指针节点，指针结构和数据类型是分开，只要一个数据结构类型包含了该指针结构类型，就能成为链表中的一个节点。

linux内核的链表都是侵入式链表实现，因为需要用链表来管理很多类型。设备，task_struct，mem_page等等。

list_head

list_head即是内核链表中的通用指针结构类型，内核中链表都为双向循环链表。

c
struct list_head {
  struct list_head *next, *prev;
};

初始化

调用LIST_HEAD宏直接初始化一个头结点，前后指针都指向自身。记住，第一个节点，也就是头结点，不存数据。

c
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
   struct list_head name = LIST_HEAD_INIT(name)
   
   
// 示例  
// 1. 链表节点初始化，前驱和后继都指向自己（初始化）
//  struct list = LIST_HEAD(list);

还有接口初始化

c
static inline void INIT_LIST_HEAD(struct list_head *list)
{
   list->next = list;
   list->prev = list;
}

上面就是内核链表的指针数据结构，怎么使用呢?

c

struct data{
    int val;
    struct list_head list;
}

struct data first_data =
{ 
    .val = 1,
    
    .list = LIST_HEAD_INIT(data.list),
};

add接口

c
static inline void list_add(struct list_head *new, struct list_head *head)
{
   __list_add(new, head, head->next);
}


static inline void __list_add(struct list_head *new,
         struct list_head *prev,
         struct list_head *next)
{
   next->prev = new;
   new->next = next;
   new->prev = prev;
   prev->next = new;
}

尾插

c
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
   __list_add(new, head->prev, head);
}

del

c
static inline void list_del(struct list_head *entry)
{
    /* __list_del_entry(entry) 也行*/
   __list_del(entry->prev, entry->next);
    
    /* 指向特定的位置，反初始化 */
   entry->next = LIST_POISON1; //代表节点无效，指向某个特殊地址。
   entry->prev = LIST_POISON2;
}

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
 next->prev = prev;
 prev->next = next;
}

删除一个节点

c
static inline void __list_del_entry(struct list_head *entry)
{
   __list_del(entry->prev, entry->next);
}

https://mp.weixin.qq.com/s/vt78z95V1BJER3Hb0a6vSw

https://mp.weixin.qq.com/s/yol66GJettPUk-AZt6XFmQ

https://mp.weixin.qq.com/s/Ddonv6FdY4oroIT32IGxOw