Linux內(nei)核中的數(shu)據結構的一點認(ren)識(shi)
時間：2018-09-25 ; 來源：未(wei)知
大家都知道linux內核(he)(he)是世(shi)界上優(you)秀的(de)(de)軟(ruan)件之一，作(zuo)為一款優(you)秀的(de)(de)軟(ruan)件，其(qi)中(zhong)的(de)(de)許多(duo)的(de)(de)設計(ji)都精妙之處，十(shi)分值得學習和借鑒。今(jin)天(tian)我們就帶大家看(kan)一下內核(he)(he)中(zhong)的(de)(de)數據結構中(zhong)一點(dian)設計(ji)。
打(da)開(kai)內核(he)源碼中(zhong)的(de) include/linux/list.h頭文件，就可以看到內核(he)中(zhong)聲(sheng)明的(de)一些與(yu)鏈(lian)表操(cao)作(zuo)相關的(de)結(jie)構體定義和函數(shu)接口。內核(he)中(zhong)使(shi)用更多(duo)的(de)是雙向(xiang)循(xun)環鏈(lian)表。我們就看一看內核(he)中(zhong)雙向(xiang)循(xun)環鏈(lian)表的(de)精妙(miao)之(zhi)處(chu)吧。
首先看鏈(lian)表節點(dian)的(de)(de)結構(gou)體(ti)的(de)(de)定義：
struct list_head{
struct list_head *next, *prev;
};
大(da)家都(dou)可以看到，該結(jie)(jie)構(gou)(gou)體(ti)(ti)的(de)(de)(de)(de)(de)成(cheng)員(yuan)僅(jin)包(bao)含了兩(liang)個(ge)指(zhi)向(xiang)前(qian)和后的(de)(de)(de)(de)(de)兩(liang)個(ge)結(jie)(jie)構(gou)(gou)體(ti)(ti)指(zhi)針(zhen)，但是(shi)在該結(jie)(jie)構(gou)(gou)體(ti)(ti)中(zhong)卻沒(mei)(mei)有數(shu)據成(cheng)員(yuan)，那么(me)到時候鏈(lian)表中(zhong)沒(mei)(mei)有任何數(shu)據，這樣(yang)(yang)的(de)(de)(de)(de)(de)鏈(lian)表有什(shen)么(me)用呢?其實這就是(shi)內(nei)核鏈(lian)表設計的(de)(de)(de)(de)(de)巧妙之處(chu)，因為在整個(ge)內(nei)核中(zhong)需要(yao)使用鏈(lian)表來(lai)存(cun)放的(de)(de)(de)(de)(de)數(shu)據類型太多了，因此如果將內(nei)核的(de)(de)(de)(de)(de)數(shu)據結(jie)(jie)構(gou)(gou)定義成(cheng)固(gu)定的(de)(de)(de)(de)(de)話(hua)，就會增加大(da)量的(de)(de)(de)(de)(de)結(jie)(jie)構(gou)(gou)體(ti)(ti)類型的(de)(de)(de)(de)(de)定義，而內(nei)核將數(shu)據成(cheng)員(yuan)的(de)(de)(de)(de)(de)定義變的(de)(de)(de)(de)(de)靈活了，就是(shi)當用到什(shen)么(me)樣(yang)(yang)的(de)(de)(de)(de)(de)數(shu)據時就臨時添加什(shen)么(me)數(shu)據，那到底是(shi)怎么(me)做的(de)(de)(de)(de)(de)呢?再看下邊(bian)的(de)(de)(de)(de)(de)一個(ge)結(jie)(jie)構(gou)(gou)體(ti)(ti)的(de)(de)(de)(de)(de)定義:
struct Data{
int a;
struct list_head p;
};
其中成(cheng)員(yuan)(yuan)(yuan)a是(shi)(shi)我(wo)(wo)們的(de)數據(ju)，而鏈表(biao)節點(dian)的(de)變(bian)量變(bian)成(cheng)了(le)我(wo)(wo)們新(xin)結(jie)構體類型(xing)的(de)成(cheng)員(yuan)(yuan)(yuan)。這樣(yang)定義的(de)話，只需要(yao)將其中的(de)成(cheng)員(yuan)(yuan)(yuan)p添(tian)加到(dao)一(yi)個(ge)(ge)雙向循環鏈表(biao)中，通過成(cheng)員(yuan)(yuan)(yuan)p我(wo)(wo)們就(jiu)可(ke)以得(de)到(dao)我(wo)(wo)們的(de)數據(ju)成(cheng)員(yuan)(yuan)(yuan)a。可(ke)以這樣(yang)比喻，就(jiu)是(shi)(shi)成(cheng)員(yuan)(yuan)(yuan)p就(jiu)是(shi)(shi)一(yi)個(ge)(ge)晾(liang)(liang)衣架，有很多晾(liang)(liang)衣架都掛(gua)(gua)在(zai)一(yi)個(ge)(ge)晾(liang)(liang)衣桿上，但是(shi)(shi)每(mei)個(ge)(ge)晾(liang)(liang)衣架上掛(gua)(gua)什么衣服(fu)(fu)就(jiu)比較隨(sui)便了(le)。只要(yao)我(wo)(wo)們找到(dao)一(yi)個(ge)(ge)晾(liang)(liang)衣架就(jiu)可(ke)以立刻得(de)到(dao)掛(gua)(gua)在(zai)上邊的(de)衣服(fu)(fu)了(le)。
下(xia)邊提供一個示(shi)例(li)代碼，闡釋一下(xia)這中用法：
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)
{
//初始(shi)化雙向鏈表頭
struct list_head *head = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(head);
struct list_head *q;
//初始化數(shu)據結構體的值
struct Data data[4] = {0};
int i;
for ( i = 0; i < 4; i++)
{
data[i].a = i + 1;
}
//將(jiang)數據結構體中的list_head類型(xing)成員頭插入到(dao)雙向鏈(lian)表中
for(i = 0; i < 4; i++)
{
list_add(&(data[i].p), head);
}
//根據結(jie)構體的一個成員地址(zhi)進而找到整個結(jie)構體的地址(zhi)
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;
}
