Linux 内核 链表 的简单模拟（1）

　　第零章：扯扯淡

　　出一个有意思的题目：用一个宏定义FIND求一个结构体struct里某个变量相对struc的编移量，如

struct student
{
    int a;    //FIND(struct student,a) 等于0
    char b;    //FIND(struct student,b）等于4
    double c;
};

参考答案：#define FIND(type,member) ((size_t)&((type*)0)->member)

我这样理解（可能不太正确）：

(type*)0，0在编译过程中会用一个int临时变量装一下，现在把这个临时变量转化成了指针，指向假想的在地址0处存在的结构体，其实是没有的。

((type*)0)->member就访问这个结构体的变量了，

&((type*)0)->member就取得了这个变量的地址了，因为假想这个结构体放在0地址处嘛，所以这个变量的地址就是相对于结构体的偏移，

(size_t)&((type*)0)->member再把这个地址转化成size_t类型（typedef unsigned int size_t），因为地址是0x00000004这样形式的，转化成无符号整形，即得偏移。

测试如下：

#include <iostream>

#define FIND(type,member) ((size_t)&((type*)0)->member)

struct student
{
    int a;    //FIND(struct student,a) 等于0
    char b;    //FIND(struct student,b）等于4
    double c;
};

using namespace std;

int main(void)
{
    cout << sizeof(size_t) << endl;
    cout << FIND(struct student, a) << endl << FIND(struct student, b)<<endl<< FIND(struct student, c) << endl;
    cin.get();
}

输出为 4 0 4 8

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第一章：普通链表

　　正常的的链表不是这样嘛：

/*表示书的结构体*/
struct Book
{
    int bkId;
    string bkName;

    struct Book *prev;    //指向链表中前一个节点
    struct Book *next;    //指向链表中后一个节点
};

然后再具体写对struct Book结构体的具体操作，如添加一个节点啊，删除一个啊等等。设想：如果有几十个甚至上百个链表，那不是搞死了嘛！要为每一个特定类型的链表写一个具体的操作，程序员怎么会做这么愚蠢的事情呢？于是就有了帅帅的Linux内核链表管理法。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第二章：Linux内核链表

　　Linux内核链表数据结构如下：（在我的M:\linux-3.14.5\include\linux下types.h文件中）

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

正常的链表是把指向前后节点的指针放到链表节点中，但Linux内核不是这么干的，它把上面的struct list_head塞到数据结构中，这样每一个struct list_head就成为了链表节点，其中next指向下一个struct list_hand，prev指向前一个struct list_hand，这样是不是很帅？但关键是要看它怎么使用。现在来看我的struct Book，如果要弄一个它的链表，只要这样：

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

/*表示书的结构体*/
struct Book
{
    int bkId;
    string bkName;

    struct list_head list;        //所有的Book结构体形成链表
};

我这是在抄袭哈！最关键的是要看到底怎么才能组成链表以及到底怎么样才能操作链表。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第三章：Linux内核链表创建与初始化

　　

　　创建一个链表也就是创建一个链表头，这个头也是一个struct list_head，源代码有些宏就省去了。（在我的M:\linux-3.14.5\include\linux下list.h文件中）

/*初始化链表*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

其实就是让头的前后指针都指向自己啦。目前我的代码如下：

#include <string>

using std::string;

/*链表节点*/
struct list_head {
    struct list_head *next, *prev;
};

/*表示书的结构体*/
struct Book
{
    int bkId;
    string bkName;
    struct list_head list;        //所有的Book结构体形成链表
};

/*初始化链表*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

myHead.h

#include <iostream>
#include "myList.h"

using namespace std;

int main(void)
{
    struct list_head MyBkList;    //创建我的链表头
    INIT_LIST_HEAD(&MyBkList);   //初始化这个链表

    cin.get();
}

main.cpp

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第四章：Linux内核链表插入

　　（1）插入节点

　　上面只是建立了一个空链表，现在要插入数据了。

　　内核提供了把一个新struct list_head节点插入到两个节点之间的方法：

/*
* 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 *new1,struct list_head * prev,struct list_head * next)
{
    next->prev = new1;
    new1->next = next;
    new1->prev = prev;
    prev->next = new1;
}

这里很抱歉啊，我的是C++项目，new是语言的关键词，所以把new换成了new1，内核源代码中上面的都是new。这个函数是其他插入函数都要调用的，其实就是提取了前插、后插的共同点啦，这个真美！

　　（2）尾插节点

/**
 * 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);
}

尾插这个方法其实就是在head节点之前插入一个节点啦，最终调用__list_add(new, head->prev, head);表明是在head前一个节点和head节点之间插入一个节点。

　　设想：刚开始只有一个链表头结点struct list_head head，head的前后都是指向自己的，现在调用 list_add_tail(struct list_head *new, struct list_head *head)，即__list_add(new, head->prev, head);链表成了两个节点，并且都是各自的相互指向对方：

因为这是个双向链表，可以看做new1加到了head后面。再调用一个这个函数 list_add_tail(struct list_head *new, struct list_head *head)：

所以可以看做：把head当队头，每次修改的都是head的prev指针，每次都在队尾添加，相当于队列啦！现在代码是：

#include <iostream>
#include "myList.h"

using namespace std;

int main(void)
{
    struct list_head MyBkList;    //创建我的链表头
    INIT_LIST_HEAD(&MyBkList);   //初始化这个链表

    /*创建新书结构体*/
    struct Book bk1;
    bk1.bkId = ;
    bk1.bkName = "book1";

    list_add_tail(&bk1.list, &MyBkList);        //把新书1加到头结点MyBkList后面

    struct Book bk2;
    bk2.bkId = ;
    bk2.bkName = "book2";

    list_add_tail(&bk2.list,&MyBkList);    //把书2加到bk1与MyBkList之间，把MyBkList看做头，则为MyBkList->bk1->bk2(按照节点next指针，MyBkList的next指针是没有变的，MyBkList的prev指针变了)

    cin.get();
}

链表添加了2节点

　　（3）头插

　　内核还有个头插，相当于每次都插在了head的后面了，即每次都修改了head的next指针，每次都在前面插，相当于栈啦！和上面的基本差不多，不多写了。

/**
 * 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);
}

其实这个更好理解，每次都在head节点和head节点后面一个节点之前插入一个节点。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

　　第四章：从list_head结构体到包含它的给定数据结构

　　上面的都是针对struct list_head操作的，插入也只是把给定结构体的的struct list_head成员传递给函数，但如何才能获得包含struct list_head的结构体呢？毕竟真正要访问的时候我们想访问到我们真正关心的数据。好了，下面一步一步来

　　container_of（）（在我的M:\linux-3.14.5\include\linux下kernel.h文件中）

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:    the pointer to the member.
 * @type:    the type of the container struct this is embedded in.
 * @member:    the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({            \
    const typeof( ((type *))->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

它已经描述很清楚，由结构体包含的成员获得包含这个成员的结构体，ptr是指向结构体成员的指针，type是包含给定成员的结构体名称，member是结构体所含指定成员的的在结构体中的名字。

typeof：是g++对c / c++语法的一个扩展，用来静态获取参数类型，在windows下面一直报错，我就迁徙到linux，用g++就ok比如：

int a = 3;

typeof(a) b = 4; // 相当于 int b = 4;

offsetof：如下，是内核源代码定义的宏(在我的M:\linux-3.14.5\include\linux下stddef.h文件中)

#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

offsetoff(struct_t, member)宏的作用就是获得成员member在类型struct_t中的偏移量。是不是第零章扯扯淡差不多？？？

好了，其实理解了第零章的扯扯淡就大概知道怎么做了：获得member相对于type的偏移，再拿给定的member地址减去这个便宜不就是这个结构体的地址吗？这里主要注意一些参数类型，因为这个宏针对各种结构体类型都可以的：

typeof(((type *)0)->member)：获得type结构体中member成员名所对应的具体类型，是int呢还是struct list_head呢等等，如果对应我的程序，type是struct Book，member是struct list_head类型的list，则这里获得的是struct list_head；

const typeof(((type *)0)->member) *__mptr = (ptr);看看对应我的程序就懂了，即 const struct list_head  *__mptr = ptr ,就是定义了一个结构体中member所对应的类型的指针，并把ptr赋给它，因为在使用这个宏的时候传递的ptr只是一个大概0xffffffff形式的member的地址，不知道具体类型，member也只是自己起的名字。现在 __mptr是有身份的地址啦！

(type *)((char *)__mptr - offsetof(type, member))：对应我的程序就是那struct Book里面的list变量地址减去struct Book里面list的偏移，得到的就是这个结构体的地址，再强制转换成struct Book类型。搞定！但还是不明白为什么要进行ptr到__mptr的转换......

这里利用编译器技术的小技巧，即先求得结构成员在与结构中的偏移量，然后根据成员变量的地址反过来得出属主结构变量的地址。

下接：Linux 内核 链表 的简单模拟（2）