Linux內核中的數據結構的一點認識
時間：2018-10-28 來源：華清遠見
大家都知道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("%d\n", temp->a);
}
return 0;
}
