Linux内核中双向链表的经典实现

1. Linux中的两个经典宏定义

offsetof

定义：offsetof在linux内核的include/linux/stddef.h中定义

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

说明：获得结构体（TYPE）的变量成员（MEMBER）在次结构体的偏移量。

• ((TYPE *)0) 将零转型为TYPE类型指针，即TYPE类型的指针地址是0
• ((TYPE *)0)->MEMBER 访问结构中的数据成员
• &(((TYPE *)0)->MEMBER)) 取出数据成员的地址。由于TYPE的地址是0，这里获取到的地址就是相对MEMBER在TYPE中的偏移量。
• (size_t) &((TYPE *)0)->MEMBER) 结果转换类型。对于32位系统，size_t是unsigned int类型，对于64位系统，size_t是unsigned long类型。

示例：

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

struct Person {
    char gender;
    int id;
    int age;
    char name[20];
};

int main(int argc, char const *argv[])
    int genderOffset, idOffset, ageOffset, nameOffset;
    genderOffset = offsetof(struct Person, gender);
    idOffset = offsetof(struct Person, id);
    ageOffset = offsetof(struct Person, age);
    nameOffset = offsetof(struct Person, name);
    
    printf("gender offset = %d\n", genderOffset);
    printf("id offset = %d\n", idOffset);
    printf("age offset = %d\n", ageOffset);
    printf("name offset = %d\n", nameOffset);

	return 0;
}

2. Linux中双向链表的经典实现

Linux中双向链表介绍

Linux双向链表的定义主要涉及到两个文件： include/linux/types.h include/linux/list.h

Linux中双向链表的使用思想

它是将双向链表节点嵌套在其它的结构体中；在遍历链表的时候，根据双链表节点的指针获取"它所在结构体的指针"，从而再获取数据。

例子来说明，可能比较容易理解。假设存在一个社区中有很多人，每个人都有姓名和年龄。通过双向链表将人进行关联的模型图如下：

graph LR
subgraph person
list1[list_head]
end

subgraph person
list2[list_head]
end

subgraph person
list3[list_head]
end

subgraph person
list...[...]
end

subgraph person
listN[list_head]
end

list1 --- list2
list2 --- list3
list3 --- list...
list... --- listN

Loading

person代表人，它有name和age属性。为了通过双向链表对person进行链接，我们在person中添加了list_head属性。通过list_head，我们就将person关联起来了

struct person {
  int age;
  char name[20];
  struct list_head list;
}