linux內(nèi)核中l(wèi)list.h文件中的鏈表宏講解

鏈表宏在linux內(nèi)核、鴻蒙內(nèi)核、rtos和一些開源代碼中用的非常多。鏈表宏是雙向鏈表的經(jīng)典實現(xiàn)方式，總代碼不超過50行，相當精煉。在一些開源框架中，它的數(shù)據(jù)結(jié)構(gòu)，就是以鏈表宏為基礎(chǔ)進行搭建(如shttpd，一個開源的輕量級、嵌入式服務(wù)器框架)。本篇文章將對llist.h文件中的鏈表宏進行逐個講解。

1 源碼（llist.h）

llist.h文件的全部源碼如下：

#ifndefLLIST_HEADER_INCLUDED
#defineLLIST_HEADER_INCLUDED

/*
*Linkedlistmacros.
*/
structllhead{
structllhead*prev;
structllhead*next;
};

#defineLL_INIT(N)((N)->next=(N)->prev=(N))

#defineLL_HEAD(H)structllheadH={&H,&H}

#defineLL_ENTRY(P,T,N)((T*)((char*)(P)-offsetof(T,N)))

#defineLL_ADD(H,N)
do{
((H)->next)->prev=(N);
(N)->next=((H)->next);
(N)->prev=(H);
(H)->next=(N);
}while(0)

#defineLL_TAIL(H,N)
do{
((H)->prev)->next=(N);
(N)->prev=((H)->prev);
(N)->next=(H);
(H)->prev=(N);
}while(0)

#defineLL_DEL(N)
do{
((N)->next)->prev=((N)->prev);
((N)->prev)->next=((N)->next);
LL_INIT(N);
}while(0)

#defineLL_EMPTY(N)((N)->next==(N))

#defineLL_FOREACH(H,N)for(N=(H)->next;N!=(H);N=(N)->next)

#defineLL_FOREACH_SAFE(H,N,T)
for(N=(H)->next,T=(N)->next;N!=(H);
N=(T),T=(N)->next)

#endif/*LLIST_HEADER_INCLUDED*/

2 注解

在llist.h中，所用到的鏈表是雙向鏈表，其節(jié)點結(jié)構(gòu)定義如下。在此節(jié)點結(jié)構(gòu)中，其只包含了兩個指針域，一個指向直接前驅(qū)，一個指向直接后繼，沒有定義數(shù)據(jù)域。

structllhead{
structllhead*prev;
structllhead*next;
};

2.1 LL_INIT(N)

宏LL_INIT的定義如下，其作用是將所傳入指針N的兩個指針域(N)->next和(N)->prev都指向N。目的是完成單個節(jié)點的初始化工作，如下圖示意了該過程。

#defineLL_INIT(N)((N)->next=(N)->prev=(N))

2.2 LL_HEAD(H)

宏LL_HEAD的定義如下，直接將宏LL_HEAD展開，其意圖很明顯是定義一個新鏈表H（H表示為傳入宏的參數(shù)名），并且將H的兩個指針域，都初始化為H地址本身，如下圖示意了該過程。

#defineLL_HEAD(H)structllheadH={&H,&H}

2.3 LL_ENTRY(P,T,N)

宏LL_ENTRY的定義如下，其依賴于宏offsetof。下面先對宏offsetof進行詳細描述，其功能描述為：

C語言的offsetof()宏，是定義在stddef.h。用于求出一個struct或union數(shù)據(jù)類型的給定成員的size_t類型的字節(jié)偏移值（相對于struct或union數(shù)據(jù)類型的開頭）。offsetof()宏有兩個參數(shù)，分別是結(jié)構(gòu)名與結(jié)構(gòu)內(nèi)的成員名?！S基百科

#defineLL_ENTRY(P,T,N)((T*)((char*)(P)-offsetof(T,N)))

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

為了更好的理解宏offsetof，下面按照宏的定義來進行拆解說明。

• ((TYPE *)0)：取整數(shù)零并將其強轉(zhuǎn)換為指向TYPE的指針。
• ((TYPE *)0)->MEMBER)：引用指向結(jié)構(gòu)成員MEMBER。
• &((TYPE *)0)->MEMBER)：取出MEMBER的地址。
• ((size_t) &((TYPE *)0)->MEMBER)：將結(jié)果轉(zhuǎn)換為適當?shù)臄?shù)據(jù)類型。

由于該結(jié)構(gòu)體是以0地址開頭，所以最后該宏返回的結(jié)果就是該成員相對于結(jié)構(gòu)體開頭的偏移量。有了對宏offsetof的理解，再來看宏LL_ENTRY就比較好理解了。宏LL_ENTRY的功能是，根據(jù)結(jié)構(gòu)體變量(T)中的域成員變量(N)的指針(P)來獲取指向整個結(jié)構(gòu)體變量的指針，下面來做拆解說明：

• offsetof(T, N)：計算成員N相對于其結(jié)構(gòu)體T開頭的偏移量。
• ((char *)(P)：將指針P強轉(zhuǎn)為字符指針類型，保證其做+/-運算時是以字節(jié)為單位。
• (char *)(P) - offsetof(T, N))：P為成員N的指針，減去偏移量，指針到了結(jié)構(gòu)體開頭位置。
• ((T *)((char *)(P)- offsetof(T, N)))：將指針強轉(zhuǎn)，得到了整個結(jié)構(gòu)體指針。

宏LL_ENTRY的作用和linux中的宏container_of作用基本一樣，該宏定義如下：

#definecontainer_of(ptr,type,member)({
consttypeof(((type*)0)->member)*__mptr=(ptr);
(type*)((char*)__mptr-offsetof(type,member));})

2.4 LL_ADD(H, N)

宏LL_ADD的定義如下，其作用是向雙向鏈表H的頭部添加節(jié)點N。根據(jù)LL_ADD定義的語句順序，對照著圖片分析，會更加清晰。如下圖，上面這張圖片展示了添加節(jié)點N之前的結(jié)構(gòu)，下圖展示了添加節(jié)點N之后的結(jié)構(gòu)。

#defineLL_ADD(H,N)
do{
((H)->next)->prev=(N);
(N)->next=((H)->next);
(N)->prev=(H);
(H)->next=(N);
}while(0)

2.5 LL_TAIL(H, N)

宏LL_TAIL的定義如下，其作用是將節(jié)點N添加到雙向鏈表H的尾部。宏LL_TAIL的定義如下，其作用是向雙向鏈表H的頭部添加節(jié)點N。根據(jù)LL_TAIL定義的語句順序，對照著圖片分析，會更加清晰。如下圖，上面這張圖片展示了添加節(jié)點N之前的結(jié)構(gòu)，下圖展示了添加節(jié)點N之后的結(jié)構(gòu)，可以和LL_ADD的結(jié)果進行對照。

#defineLL_TAIL(H,N)
do{
((H)->prev)->next=(N);
(N)->prev=((H)->prev);
(N)->next=(H);
(H)->prev=(N);
}while(0)

2.6 LL_DEL(N)

宏LL_DEL的定義如下，其作用是將節(jié)點N從雙向鏈表中刪除，并且節(jié)點N回到初始狀態(tài)(其指針僅指向自身，不再指向其它地方)。

#defineLL_DEL(N)
do{
((N)->next)->prev=((N)->prev);
((N)->prev)->next=((N)->next);
LL_INIT(N);
}while(0)

2.7 LL_EMPTY(N)

宏LL_EMPTY的定義如下，其作用是判斷鏈表N是否為空鏈表，返回布爾值false/true。如果節(jié)點的直接后繼next指向其自身，就認為其為空節(jié)點。

#defineLL_EMPTY(N)((N)->next==(N))

2.8 LL_FOREACH(H,N)

宏LL_FOREACH的定義如下，其作用是在雙向鏈表H中，循環(huán)遍歷出節(jié)點。

#defineLL_FOREACH(H,N)for(N=(H)->next;N!=(H);N=(N)->next)

2.9 LL_FOREACH_SAFE(H,N,T)

宏LL_FOREACH_SAFE的定義如下，其作用是在雙向鏈表H中，循環(huán)遍歷出節(jié)點N，因為其有提前存儲N的下一個節(jié)點T。即使N節(jié)點被清理掉，也不影響其下一個節(jié)點的遍歷，所以該宏一般用來做循環(huán)清除雙向鏈表中節(jié)點的操作，而宏LL_FOREACH僅用來遍歷雙向鏈表。

#defineLL_FOREACH_SAFE(H,N,T)
for(N=(H)->next,T=(N)->next;N!=(H);
N=(T),T=(N)->next)

3 使用案例

有人可能會有疑惑，這個雙向鏈表定義如此簡單，只有前驅(qū)和后繼兩個指針，甚至連數(shù)據(jù)域都沒有，那實際該如何使用呢？這個可能就是這組雙向鏈表宏的精妙之處。其在使用過程中并不需要數(shù)據(jù)域，而是通過指針將結(jié)構(gòu)體串聯(lián)成雙向鏈表，并且通過該指針借助 LL_ENTRY宏 能還原出該結(jié)構(gòu)體指針，從而達到操作具體結(jié)構(gòu)體的目的。

如下例子雖然不是完整能跑的程序，但是足夠說明雙向鏈表宏的關(guān)鍵用法。程序源碼如下，現(xiàn)對照代碼，描述雙向鏈表宏的大致使用步驟：

1. 定義一個結(jié)構(gòu)體，結(jié)構(gòu)體中必須包含struct llheadlink;雙向鏈表節(jié)點，這是后續(xù)能通過遍歷雙向鏈表節(jié)點，還原出該結(jié)構(gòu)體指針的關(guān)鍵；
2. 通過LL_HEAD(listeners);，創(chuàng)建一個雙向鏈表的頭為listeners；
3. 在具體邏輯中，肯定有地方通過LL_TAIL(&listeners, &l->link);或者LL_ADD(H, N)，向雙向鏈表的頭listeners添加節(jié)點；
4. 在需要操作1.所定義的結(jié)構(gòu)體時，通過LL_FOREACH(&listeners, lp)遍歷出節(jié)點指針；
5. 這是最精華的一步，通過4.遍歷出來的節(jié)點，傳入宏LL_ENTRY(lp, struct listener, link);中，還原出節(jié)點所在的結(jié)構(gòu)體指針，根據(jù)邏輯的需要對結(jié)構(gòu)體進行具體相應(yīng)的操作；
6. 通過宏LL_FOREACH_SAFE來遍歷雙向鏈表，LL_DEL來刪除遍歷出來的節(jié)點，達到清空鏈表的作用。

structllhead{
structllhead*prev;
structllhead*next;
};

structlistener{
structllheadlink;
structshttpd_ctx*ctx;/*Contextthatsocketbelongs*/
intsock;/*Listeningsocket*/
intis_ssl;/*ShouldbeSSL-ed*/
};

staticLL_HEAD(listeners);/*Listoflisteningsockets*/

structlistener*l;
LL_TAIL(&listeners,&l->link);

structllhead*lp;
LL_FOREACH(&listeners,lp){
l=LL_ENTRY(lp,structlistener,link);
FD_SET(l->sock,&read_set);
if(l->sock>max_fd)
max_fd=l->sock;
DBG(("FD_SET(%d)(listening)",l->sock));
}

structllhead*lp,*tmp;
LL_FOREACH_SAFE(&listeners,lp,tmp){
l=LL_ENTRY(lp,structlistener,link);
(void)closesocket(l->sock);
LL_DEL(&l->link);
free(l);
}

4 總結(jié)

• LL_ENTRY(P,T,N)宏是這一組宏的核心，其在具體使用中的功能可以概括為，通過傳入鏈表節(jié)點P，還原出節(jié)點所在結(jié)構(gòu)體的指針，進而能對結(jié)構(gòu)體進行相應(yīng)操作；
• 這一組雙向鏈表宏其實形成的是一個循環(huán)雙向鏈表；
• 這些宏最初是極客寫出的，后來在Linux內(nèi)核中被推廣使用。