Linux 内核通用链表学习

描述

在linux内核中封装了一个通用的双向链表库，这个通用的链表库有很好的扩展性和封装性，它给我们提供了一个固定的指针域结构体，我们在使用的时候，只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了，具体的实现、链接并不需要我们关心，只要调用提供给我们的相关接口就可以完成了。

传统的链表结构

struct node{
    int key;
    int val;
    node* prev;
    node* next;
 }

linux 内核通用链表库结构

提供给我们的指针域结构体：
struct list_head {
    struct list_head *next, *prev;
};

我们只需要包含它就可以：
struct node{
    int val;
    int key;
    struct list_head* head;
}

可以看到通过这个 list_head 结构就把我们的数据层跟驱动层分开了，而内核提供的各种操作方法接口也只关心 list_head 这个结构，也就是具体链接的时候也只链接这个list_head 结构，并不关心你数据层定义了什么类型.

一些接口宏定义

//初始化头指针
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

//遍历链表
#define __list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

//获取节点首地址(不是list_head地址，是数据层节点首地址)
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

//container_of在Linux内核中是一个常用的宏，用于从包含在某个
//结构中的指针获得结构本身的指针，通俗地讲就是通过结构体变
//量中某个成员的首地址进而获得整个结构体变量的首地址
#define container_of(ptr, type, member) ({          \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})

#define offsetof(s,m) (size_t)&(((s *)0)->m)

使用方式

typedef struct node{
    int val;
    int key;
    struct list_head* list;
}node;

//初始化头指针
LIST_HEAD(head);

//创建节点
node* a = malloc(sizeof(node));
node* b = malloc(sizeof(node));

//插入链表 方式一
list_add(&a->list,&head);
list_add(&b->list,&head);

//插入链表 方式二
list_add_tail(&a->list,&head);
list_add_tail(&b->list,&head);

//遍历链表   
struct list_head* p;
struct node* n;
__list_for_each(p,head){
   //返回list_head地址，然后再通过list_head地址反推
   //节点结构体首地址.
   n = list_entry(pos,struct node,list);
}

list_add 接口，先入后出原则，有点类似于栈

list_add-先入后出模式

list_add_tail 接口，先入先出原则，有点类似于fifo

list_add-先入先出模式

接口实现方式

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

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

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

我们的链表节点，实际在内存中的展示形态

节点描述

可以看到最终的形态是，通过指向每个结构体里面的 list_head 类型指针，然后把它们串联起来的

list_entry 接口，通过结构体变量某个成员的地址，反推结构体首地址，就像 __list_for_each 接口只返回 list_head 地址，所以我们要通过这个成员地址在去获取它本身的结构体首地址，底层实现方法 container_of 宏

反推结构体首地址

结束

linux 内核提供的这个通用链表库里面还有很多其他的接口，这里没有详细的一一举例，有兴趣的可以自己去看看，在源码包 include/linux/list.h 文件里面，不过通过阅读一些源代码确实对我们也有很大的提高，可以看看高手是如何去设计并实现，还可以学到一些技巧以及对代码细节的掌握~~.