链表结构解析-Linux源码

链表结构解析-Linux源码

在Linux内核代码中，经常会使用到链表结构，其中分为普通链表和哈希表。普通链表在文件list.h中，定义的格式如下：

struct list_head {

 struct list_head *next, *prev;

};

其中比较难理解的地方有两点：

1、如何通过在数据结构中添加list_head成员变量实现链表；

2、如何通过list_head成员变量访问宿主数据；

关于第二点，本文稍作解释。

list_head成员可以放置在宿主的任意位置，不需要放置在第一个变量的位置。当需要访问宿主的结构时，首先通过使用list_head成员变量的地址减去相对于结构的偏移量，从而获取结构的地址，进而可以访问结构的其他成员。使用公式表示如下：

Address(struct data)=Address(list_head)-offset(list_head)

如下图所示：

struct data

------------------_______

| length          |     |

| ...                 |    偏移量

| list_head      |__|____

|  ...                |

|                     |

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