关于链表宏的个人理解

发表于 更新于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 3 分钟

笔者在学习这一部分的过程中，一开始完全看不懂这链表的宏是在干啥，经过自己坐大牢+问朋友，才搞清楚，记录一下。

如有理解错误，感谢指正。

链表的节点是啥

一开始看这个看不懂，就想着看看这个链表宏在代码里面是怎么使用的，我觉得以这个为例比较好理解。

这是Page结构体（在pmap.h）中，也就是链表的节点。

1
2
3
4
struct Page {
	Page_LIST_entry_t pp_link;	
	u_short pp_ref;
};

这里面的Page_LIST_entry_t其实就是LIST_ENTRY(Page)

因为在pmap.h中把LIST_ENTRY(Page) typedef为了Page_LIST_entry_t

而LIST_ENTRY(Page)：

1
2
3
4
5
#define LIST_ENTRY(type)                                                	\
        struct {                                                                \
                struct type *le_next;   /* next element */                      \
                struct type **le_prev;  /* address of previous next element */  \
        }

就是一个结构体的定义，这个结构体中包含两个类型为type的指针，le_next是指向type的指针，指向链表的下一个节点；le_prev是指向指向type的指针的指针，指向上一个节点的le_next指针。

这里我一开始非常不理解为什么le_prev要是双重指针，其实重点在于，le_prev指向的不是链表的前一个节点，而是前一个节点的le_next

（在我的印象中链表的实现都是直接保存指向上一个节点的指针，但是我们这个实现中，链表的节点只是保存了指向上一个节点的le_next的指针，这样就可以通过当前节点修改上一个节点的le_next，也可以实现链表的功能（插入、删除等）

但是我不理解这么做有什么好处，求大佬解答（？？？）

我觉得这个可能是为了保护。使用这种实现方法的话，后一个节点就只能修改前一个节点的le_next，不能修改前一个节点的le_prev或者别的什么东西，而如果直接把后一个节点的le_prev指向前一个节点的话，程序员就可以通过后一个节点获取前一个节点的一切信息，有可能篡改前一个节点和前前一个节点之间的关系，这是不安全的。

因此Page实际上展开后长这样：

e7884c8b5185658c312bb672a6e5294

对应我们的宏是这样

6c4ec5d51e205963934ace59a1281e4

链表是啥

以实验代码中的Page_list为例

Page_list是包含了头结点的一个结构体：

1
2
3
4
#define LIST_HEAD(name, type)  //LIST_HEAD(Page_list, Page);                                         	\
        struct name {                                                           \
                struct type *lh_first;  /* first element */                     \
        }

这是一个结构体的定义，结构体名为name，里面有一个类型为type的指针

在我们的项目中这个宏被用在

1
LIST_HEAD(Page_list, Page);

相当于

1
2
3
 struct Page_list {                                                           \
         struct Page *lh_first;  /* first element */                     \
}

链表的INSERT_BEFORE

其实要是搞清楚链表结构体中的每个东西都是干嘛用的，理解这个就不难了。

1
2
3
4
5
6
#define LIST_INSERT_BEFORE(listelm, elm, field) do {		                \
                (elm)->field.le_prev = (listelm)->field.le_prev;                \
                LIST_NEXT((elm), field) = (listelm);                            \
                *(listelm)->field.le_prev = (elm);                              \
                (listelm)->field.le_prev = &LIST_NEXT((elm), field);            \
        } while (0)

这里面的listelm，elm都是指向链表节点的指针

四条语句分别对应下面图中的1,2,3,4

image-20220406100023694

比较难理解的是(listelm)->field.le_prev = &LIST_NEXT((elm), field);

其实这就是把指向指向listelm的指针的指针赋值给了listelm的le_prev