Linux内核当中的数据结构之链表

和很多其他大型项目一样，linux内核实现了一些通用的数据结构，供开发者在开发的过程中重用。今天先来给大家介绍以下linux当中的链表

1. 链表

链表是linux内核当中最简单、最普遍的数据结构。它是一种存放和操作可变数量元素的数据结构，其和静态数组不同的地方在于，它所包含的元素都是动态创建并插入的，在编译时不需要指导具体创建多少个元素，也正是由于这样，链表在内存中不需要占用连续的内存。

通常情况下，我们的链表大概长这样：

struct list_entry{
    void *data;
    struct list_entry *next;
};

双链表的话就是在结构体当中多了一个prev指针，之后的什么循环链表等都是围绕着指针进行操作

但是，linux内核当中的链表却根上面的结构不一样，它采用的是内嵌式的结构，其定义如下：

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

要使用这个链表只需要把它嵌入到要使用链表的结构体当中即可，如下：

struct list_entry{
    /*
     * some other datas
    */
    struct list_head list;
};

遍历链表可以从每一个链表当中的节点开始，也可以从名以上的头节点，这个头节点的相关定义方式如下， 其实就是建立了一个空结构：

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)
#define (name) { &(name), &(name) }

整个链表对应的相关api如下：

void list_add(struct list_head *new, struct list_head *head)
void list_del(struct list_head *entry)
void list_move(struct list_head *list, struct list_head *head)

其中list_move 是将list移动到head后面

关于遍历链表
当时觉得最困扰自己的就是遍历这块，看了好久才回味过来，自己总结如下：按照嵌入式的方式，我们先不管外层，理论上一路next可以遍历完整个链表，可以拿到每个元素中list_head的首地址、next、prev指针，那剩下的问题就转化为：
已知一个结构体的结构，和一个指向其中固定成员的指针，求这个结构体的首地址，其所有遍历汉书都依赖的函数调用链为：list_entry---->container_of---->offsetof

// include/linux/list.h
/**
 * list_entry - get the struct for this entry
 * @ptr:    the &struct list_head pointer.
 * @type:    the type of the struct this is embedded in.
 * @member:    the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)



// include/linux/kernel.h
#define container_of(ptr, type, member) ({                \
    void *__mptr = (void *)(ptr);                    \
    BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&    \
             !__same_type(*(ptr), void),            \
             "pointer type mismatch in container_of()");    \
    ((type *)(__mptr - offsetof(type, member))); })

// include/linux/stddef.h
#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER)    __compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER)    ((size_t)&((TYPE *)0)->MEMBER)
#endif

以上，就是linux内核当中的链表结构的简介了