linux链表实现原理

linux

数据结构定义

• linux的链表是嵌入到数据结构当中，而不是在数据结构的定义中定义链表

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

• 定义一个需要链表的数据结构

typedef struct Data{
    int n;
    // other data
    struct list_head list;  
}Data;
Data d;
struct list_head l = list_entry(&d,Data,list);

操作函数

• 根据链表地址获取结构体首地址

#define list_entry(ptr, type, member) \
   container_of(ptr, type, member)
#define container_of(ptr, type, member) ({      \
         const typeof( ((type *)0)->member ) *__mptr = (ptr);  \
         (type *)( (char *)__mptr - offsetof(type,member) );})

• 0.把地址0强制转换成（看成）type（结构体类型），提取结构体的member成员类型，typeof提取类型
• 1.定义一个成员类型的指针，结构ptr地址
• 2.成员地址减去成员在结构体中的偏移量，获取结构体的首地址
• 获取成员在结构体中的偏移量
• linux内核第一宏

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

• offsetof定义为获取结构体成员的地址，可以认为是结构体成员前面数据的大小

--------------------- // 地址空间 
| <-offset  ->  | 
地址0            member地址

• (TYPE*)0,把地址0看成是TYPE类型的首地址
• offset的值是member成员在结构体中的偏移量
• 参考地址