[经验]

Linux内核中的数据结构的一点认识

2022-4-20 16:42:25

3820

大家都知道linux内核是世界上优秀的软件之一，作为一款优秀的软件，其中的许多的设计都精妙之处，十分值得学习和借鉴。今天我们就带大家看一下内核中的数据结构中一点设计。
打开内核源码中的 include/linux/list.h头文件，就可以看到内核中声明的一些与链表操作相关的结构体定义和函数接口。内核中使用更多的是双向循环链表。我们就看一看内核中双向循环链表的精妙之处吧。
首先看链表节点的结构体的定义：
struct list_head{
struct list_head *next, *prev;
};
大家都可以看到，该结构体的成员仅包含了两个指向前和后的两个结构体指针，但是在该结构体中却没有数据成员，那么到时候链表中没有任何数据，这样的链表有什么用呢?其实这就是内核链表设计的巧妙之处，因为在整个内核中需要使用链表来存放的数据类型太多了，因此如果将内核的数据结构定义成固定的话，就会增加大量的结构体类型的定义，而内核将数据成员的定义变的灵活了，就是当用到什么样的数据时就临时添加什么数据，那到底是怎么做的呢?再看下边的一个结构体的定义:
struct Data{
int a;
struct list_head p;
};
其中成员a是我们的数据，而链表节点的变量变成了我们新结构体类型的成员。这样定义的话，只需要将其中的成员p添加到一个双向循环链表中，通过成员p我们就可以得到我们的数据成员a。可以这样比喻，就是成员p就是一个晾衣架，有很多晾衣架都挂在一个晾衣杆上，但是每个晾衣架上挂什么衣服就比较随便了。只要我们找到一个晾衣架就可以立刻得到挂在上边的衣服了。
下边提供一个示例代码，阐释一下这中用法：
struct list_head{
struct list_head *next, *prev;
};
/* data struct */
struct Data{
int a;
struct list_head p;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name)
struct list_head name = LIST_HEAD_INIT(name)
#define mycontainer_of(memadd, type, memname)
((struct type*)(((char*)memadd - ((unsigned long)&(((struct type*)0)->memname)))))
void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
int main(void)
{
//初始化双向链表头
struct list_head *head = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(head);
struct list_head *q;
//初始化数据结构体的值
struct Data data[4] = {0};
int i;
for ( i = 0; i < 4; i++)
{
data[i].a = i + 1;
}
//将数据结构体中的list_head类型成员头插入到双向链表中
for(i = 0; i < 4; i++)
{
list_add(&(data[i].p), head);
}
//根据结构体的一个成员地址进而找到整个结构体的地址
for (q = head->next; q != head; q = q->next )
{
struct Data *temp;
temp = mycontainer_of(q, Data, p);
printf("%dn", temp->a);
}
return 0;
}