青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

那誰的技術(shù)博客

感興趣領(lǐng)域:高性能服務(wù)器編程,存儲,算法,Linux內(nèi)核
隨筆 - 210, 文章 - 0, 評論 - 1183, 引用 - 0
數(shù)據(jù)加載中……

linux內(nèi)核V2.6.11學(xué)習(xí)筆記(2)--list和hlist

這兩個數(shù)據(jù)結(jié)構(gòu)在內(nèi)核中隨處可見,不得不拿出來單獨講講.

這兩個數(shù)據(jù)結(jié)構(gòu)都是為了方便內(nèi)核開發(fā)者在使用到類似數(shù)據(jù)結(jié)構(gòu)的時候不必自行開發(fā)(雖然不難),因此它們需要做到足夠的"通用性",也就是說,今天可以用它們做一個存放進程的鏈表,明天同樣可以做一個封裝定時器的鏈表.兩個數(shù)據(jù)結(jié)構(gòu)的對外API封裝了針對它們的基本操作,也是最常見的操作,比如遍歷,查找等等.

一般的,如果我們需要寫一個鏈表,會這么寫:
struct node
{
    
struct node *next;
    data_t data;
}
其中的data假設(shè)是鏈表中元素存放的數(shù)據(jù).然后針對這個鏈表寫一些相關(guān)操作的API.

假設(shè)下一個需求,鏈表存放的元素變了,那么我們還需要定義一個新的數(shù)據(jù)結(jié)構(gòu),寫一些相關(guān)操作的API.

但是,其實我們需要做的事情都是類似:遍歷一個鏈表,按照某個條件定位到其中的一個元素,等等.有沒有辦法將操作比較特定數(shù)據(jù)的操作交給使用者,而封裝出一套滿足基本鏈表操作的API呢?

C++里面的做法是STL,使用的是范型技術(shù),在運行時才直到容器所要存放的數(shù)據(jù)元素的類型.而通過C++中的重載,函數(shù)對象等技術(shù)可以平滑的實現(xiàn)操作不同數(shù)據(jù)元素.

C中沒有這些技術(shù),用STL的方式恐怕是走不通了.

于是,內(nèi)核采用了另一種方法解決這個問題.

內(nèi)核中實現(xiàn)的鏈表數(shù)據(jù)結(jié)構(gòu)是這樣的:
struct list_head {
    
struct list_head *next, *prev;
};
可見,這個鏈表中只有分別指向前一個和后一個元素的指針,而沒有特定的類型.也就是說,這個數(shù)據(jù)類型關(guān)注的僅僅是鏈表本身的東西,與具體的數(shù)據(jù)無關(guān).

當(dāng)需要使用鏈表的時候,可以這樣來:
struct node
{
    
struct list_head link;
    data_t data;
}
那么,如何根據(jù)這個link定位到所需要管理的數(shù)據(jù)呢?

內(nèi)核中定義了這么一個宏:
#define container_of(ptr, type, member) \
    ((type 
*)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
這個宏的作用是容器類型type中有一個名為member的list_head元素,要根據(jù)這個元素的指針(ptr)得到存放它的type類型的對象的地址.

一步一步看這個宏:
1) &((type *)0)->member)
從C的角度出發(fā), 假設(shè)結(jié)構(gòu)體node中有一個成員data, 那么對于一個指向結(jié)構(gòu)體node的指針p來說,
p->data與p的地址相差為data這個域在結(jié)構(gòu)體node中的偏移量.
于是,&(p->member)就是type類型的指針p中的成員member的地址,而這個地址是p的地址+member成員在這個結(jié)構(gòu)體中的偏移,
當(dāng)這個p變成了0之后,自然就得出了member成員在結(jié)構(gòu)體type中的偏移量.

所以,&((type *)0)->member)獲得了結(jié)構(gòu)體type中成員member的偏移量.

2) (char *)(ptr)-(unsigned long)(&((type *)0)->member))
這里ptr是list_head的指針,也就是member成員的指針,因此兩者相減得到了存放member的type結(jié)構(gòu)體的指針.

3)
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
最后在前面加上一個類型轉(zhuǎn)換,將前面得到的指針轉(zhuǎn)換成type類型.

這就是內(nèi)核中根據(jù)list_head指針得到容納它的容器地址的魔法.

理解了這個,理解內(nèi)核中的鏈表操作也就不再難.


接著看hlist,首先看看內(nèi)核中的定義:
struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};
這個數(shù)據(jù)結(jié)構(gòu)與一般的hash-list數(shù)據(jù)結(jié)構(gòu)定義有以下的區(qū)別:
1) 首先,hash的頭節(jié)點僅存放一個指針,也就是first指針,指向的是list的頭結(jié)點,沒有tail指針也就是指向list尾節(jié)點的指針,這樣的考慮是為了節(jié)省空間--尤其在hash bucket很大的情況下可以節(jié)省一半的指針空間.

2) list的節(jié)點有兩個指針,但是需要注意的是pprev是指針的指針,它指向的是前一個節(jié)點的next指針(見下圖).

現(xiàn)在疑問來了:為什么pprev不是prev也就是一個指針,用于簡單的指向list的前一個指針呢?這樣即使對于first而言,它可以將prev指針指向list的尾結(jié)點.

主要是基于以下幾個考慮:
1) hash-list中的list一般元素不多(如果太多了一般是設(shè)計出現(xiàn)了問題),即使遍歷也不需要太大的代價,同時需要得到尾結(jié)點的需求也不多.
2) 如果對于一般節(jié)點而言,prev指向的是前一個指針,而對于first也就是hash的第一個元素而言prev指向的是list的尾結(jié)點,那么在刪除一個元素的時候還需要判斷該節(jié)點是不是first節(jié)點進行處理.而在hlist提供的刪除節(jié)點的API中,并沒有帶上hlist_head這個參數(shù),因此做這個判斷存在難度.
3) 以上兩點說明了為什么不使用prev,現(xiàn)在來說明為什么需要的是pprev,也就是一個指向指針的指針來保存前一個節(jié)點的next指針--因為這樣做即使在刪除的節(jié)點是first節(jié)點時也可以通過*pprev = next;直接修改指針的指向.來看刪除一個節(jié)點和修改list頭結(jié)點的兩個API:
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    
struct hlist_node *first = h->first;
    n
->next = first;
    
if (first)
        first
->pprev = &n->next;
    h
->first = n;
    n
->pprev = &h->first; //此時n是hash的first指針,因此它的pprev指向的是hash的first指針的地址
}

static inline void __hlist_del(struct hlist_node *n)
{
    
struct hlist_node *next = n->next;
    
struct hlist_node **pprev = n->pprev;
    
*pprev = next; // pprev指向的是前一個節(jié)點的next指針,而當(dāng)該節(jié)點是first節(jié)點時指向自己,因此兩種情況下不論該節(jié)點是一般的節(jié)點還是頭結(jié)點都可以通過這個操作刪除掉所需刪除的節(jié)點
    if (next)
        next
->pprev = pprev;
}




參考資料:
1)http://blog.chinaunix.net/u/12592/showart.php?id=451619
我對里面的示意圖做了一下修改,主要是將list頭結(jié)點的pprev指針指向hash的first指針地址.這樣看上去更明白一些.
2)http://linux.chinaunix.net/bbs/viewthread.php?tid=1032772


posted on 2009-04-11 10:47 那誰 閱讀(4232) 評論(8)  編輯 收藏 引用 所屬分類: Linux/Unixlinux kernel

評論

# re: linux內(nèi)核V2.6.11學(xué)習(xí)筆記(二)--list和hlist  回復(fù)  更多評論   

學(xué)習(xí)了。我也在學(xué)習(xí)內(nèi)核,不過還是學(xué)習(xí)低級版本的內(nèi)核。
2009-04-14 09:00 | xuminggang

# re: linux內(nèi)核V2.6.11學(xué)習(xí)筆記(二)--list和hlist  回復(fù)  更多評論   

支持,期待你的更新
2009-04-16 08:58 | 石子

# re: linux內(nèi)核V2.6.11學(xué)習(xí)筆記(二)--list和hlist  回復(fù)  更多評論   

"((type *)0)->member)獲得了結(jié)構(gòu)體type中成員member的偏移量"這個是獲取結(jié)構(gòu)體的member成員吧,前面要加&才是偏移量。

2009-04-16 17:09 | capable

# re: linux內(nèi)核V2.6.11學(xué)習(xí)筆記(2)--list和hlist  回復(fù)  更多評論   

@capable
感謝提醒,已經(jīng)重新做了修改.
2009-04-19 10:22 | 那誰

# re: linux內(nèi)核V2.6.11學(xué)習(xí)筆記(2)--list和hlist  回復(fù)  更多評論   

我想問下博主,為什么最后做減法的時候要把ptr的類型強制轉(zhuǎn)化為char型的指針再減去后面那部分呢,謝謝。
2009-04-20 13:36 | bruin

# re: linux內(nèi)核V2.6.11學(xué)習(xí)筆記(2)--list和hlist[未登錄]  回復(fù)  更多評論   

@bruin
如果不轉(zhuǎn)換為char,而是別的類型,那么就會根據(jù)該類型的長度進行加減.
這個也是C語言的基礎(chǔ)知識了.

2009-04-20 13:59 | 那誰

# re: linux內(nèi)核V2.6.11學(xué)習(xí)筆記(2)--list和hlist  回復(fù)  更多評論   

~~~~(>_<)~~~~ 我還是米有明白瓦。
為什么不可以轉(zhuǎn)化為ul呢。
我不知道(char*)減去ul是怎么回事兒了。。。
博主給個鏈接讓我看看這部分C基礎(chǔ)也行哇。
我現(xiàn)在好像被魘到這兒了,死活想不明白。。。
漿糊中o(╯□╰)o
2009-04-20 20:22 | bruin

# re: linux內(nèi)核V2.6.11學(xué)習(xí)筆記(2)--list和hlist  回復(fù)  更多評論   

可以用ul。
去找本c語言的書看看指針的內(nèi)容。
2009-04-20 21:09 | capable
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            裸体女人亚洲精品一区| 亚洲国产欧美一区二区三区同亚洲| 欧美丰满少妇xxxbbb| 久久久久成人精品免费播放动漫| 国产日韩欧美一区在线| 性欧美超级视频| 午夜精品一区二区在线观看| 国产麻豆精品theporn| 久久成人这里只有精品| 久久久人成影片一区二区三区| 欧美久久九九| 99精品欧美一区二区蜜桃免费| 欧美国产一区在线| 亚洲一区二区三区激情| 午夜精品国产更新| 亚洲国产精品久久久久秋霞蜜臀 | 亚洲黄色三级| 亚洲精品国产日韩| 国产模特精品视频久久久久| 久久久久免费| 欧美日韩在线免费视频| 久久久精品一区二区三区| 欧美成人性生活| 亚洲在线观看免费| 久久久久久久久久久久久女国产乱 | 欧美激情第1页| 久久黄色级2电影| 欧美激情国产日韩| 久久久精品国产免费观看同学| 欧美电影资源| 久久精品二区| 欧美日韩一区二区三区在线视频| 久久蜜桃精品| 国产精品v欧美精品∨日韩| 久久香蕉精品| 国产精品美女久久久久久2018| 欧美国产精品va在线观看| 国产精品久久久久久久久免费| 欧美黄色小视频| 国产亚洲人成网站在线观看| 亚洲免费观看高清完整版在线观看熊| 精品91在线| 亚洲欧美日韩精品久久久久| 亚洲作爱视频| 男女视频一区二区| 久久综合色影院| 国产精品实拍| 亚洲桃色在线一区| 夜色激情一区二区| 欧美久久婷婷综合色| 欧美大尺度在线| 国语自产精品视频在线看| 亚洲天堂免费观看| 在线一区二区三区四区| 欧美国产视频一区二区| 欧美高清视频一区| 亚洲黄色av一区| 欧美国产欧美亚洲国产日韩mv天天看完整| 久久久久91| 狠狠色综合日日| 久久精品亚洲一区二区三区浴池| 欧美一区二区三区在线看 | 久久噜噜亚洲综合| 久久久人成影片一区二区三区| 国产日产欧美一区| 欧美一区1区三区3区公司| 欧美一区二区三区久久精品| 国产精品a级| 亚洲在线成人精品| 裸体歌舞表演一区二区| 欧美精品不卡| 欧美高清hd18日本| 亚洲美女电影在线| 欧美精品综合| 中文精品一区二区三区 | 亚洲高清不卡在线观看| 久久视频一区二区| 亚洲高清视频的网址| 亚洲乱码国产乱码精品精天堂| 欧美精品电影在线| 中日韩视频在线观看| 久久av老司机精品网站导航| 国产一区91| 免费在线一区二区| 中国亚洲黄色| 麻豆久久精品| 中文精品视频| 国产偷国产偷精品高清尤物| 久久久久九九九| 亚洲精品日日夜夜| 欧美一级黄色录像| 亚洲高清一区二| 欧美日韩一区二区欧美激情| 亚洲欧美在线x视频| 理论片一区二区在线| 一区二区欧美日韩视频| 国产精品影音先锋| 牛牛影视久久网| 亚洲综合激情| 欧美福利小视频| 亚洲欧美日本精品| 亚洲第一色在线| 国产精品高潮粉嫩av| 久久久久久9999| 亚洲一区二区黄| 欧美华人在线视频| 欧美在线三区| 亚洲手机成人高清视频| 激情欧美亚洲| 国产精品女人久久久久久| 老司机久久99久久精品播放免费| 一区二区三区不卡视频在线观看| 老司机一区二区三区| 亚洲欧美日韩国产成人| 亚洲国产黄色片| 国产日本欧美视频| 欧美三级中文字幕在线观看| 久久嫩草精品久久久精品一| 亚洲一区激情| 日韩一级裸体免费视频| 亚洲二区在线观看| 久久婷婷国产综合精品青草| 亚洲欧美日韩中文视频| 一区二区国产日产| 亚洲乱码国产乱码精品精天堂| 狠狠爱www人成狠狠爱综合网| 欧美日韩综合网| 欧美日韩亚洲一区二区| 欧美α欧美αv大片| 久久激情中文| 欧美在线不卡视频| 午夜久久资源| 亚洲欧美乱综合| 亚洲综合三区| 亚洲天天影视| 这里只有精品丝袜| 一本色道久久综合亚洲二区三区| 亚洲美女网站| 一区二区国产精品| 亚洲一区精品在线| 亚洲欧美区自拍先锋| 亚洲一区日韩在线| 久久亚洲欧洲| 激情av一区二区| 欧美视频1区| 国产精品成人免费| 国产精品久久久免费| 国产精品jvid在线观看蜜臀 | 女生裸体视频一区二区三区| 久久嫩草精品久久久精品| 老司机凹凸av亚洲导航| 美女国产一区| 欧美激情一区二区三区在线| 欧美精品三级| 国产精品成人一区二区三区夜夜夜 | 99国产精品久久久久久久久久| 亚洲精品精选| 亚洲一区二区三区高清| 香蕉久久a毛片| 久久亚洲视频| 欧美日韩国产大片| 国产精品久久毛片a| 国产日韩欧美在线播放不卡| 狠狠色综合色综合网络| 91久久久国产精品| 亚洲午夜久久久久久久久电影网| 午夜精品理论片| 久久一区二区三区国产精品| 亚洲风情在线资源站| 中文一区二区在线观看| 欧美在线|欧美| 欧美精品在线观看| 国产区亚洲区欧美区| 亚洲日本欧美| 亚欧美中日韩视频| 欧美激情一区| 亚洲欧美综合国产精品一区| 麻豆国产va免费精品高清在线| 欧美日韩一区二区精品| 狠狠色噜噜狠狠色综合久| 一区二区三区视频免费在线观看| 新狼窝色av性久久久久久| 欧美成在线视频| 午夜视频在线观看一区| 欧美成人69| 国产婷婷色一区二区三区| 亚洲精品日产精品乱码不卡| 久久aⅴ国产紧身牛仔裤| 亚洲精品久久视频| 久久精品国产综合精品| 欧美三日本三级少妇三2023| 在线成人亚洲| 欧美怡红院视频| 一本色道久久综合精品竹菊 | 免费在线成人| 国内精品久久久久久久影视麻豆| 亚洲私人影院在线观看| 欧美国产日韩xxxxx| 欧美中文在线观看| 国产精品久久看|