鏈表宏在linux內核、鴻蒙內核、rtos和一些開源代碼中用的非常多。鏈表宏是雙向鏈表的經典實現方式，總代碼不超過50行，相當精煉。在一些開源框架中，它的數據結構，就是以鏈表宏為基礎進行搭建(如shttpd，一個開源的輕量級、嵌入式服務器框架)。本篇文章將對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中，所用到的鏈表是雙向鏈表，其節點結構定義如下。在此節點結構中，其只包含了兩個指針域，一個指向直接前驅，一個指向直接后繼，沒有定義數據域。

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

2.1 LL_INIT(N)

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

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

2.2 LL_HEAD(H)

宏LL_HEAD的定義如下，直接將宏LL_HEAD展開，其意圖很明顯是定義一個新鏈表H（H表示為傳入宏的參數名），并且將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數據類型的給定成員的size_t類型的字節偏移值（相對于struct或union數據類型的開頭）。offsetof()宏有兩個參數，分別是結構名與結構內的成員名。——維基百科

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

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

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

• ((TYPE *)0)：取整數零并將其強轉換為指向TYPE的指針。
• ((TYPE *)0)->MEMBER)：引用指向結構成員MEMBER。
• &((TYPE *)0)->MEMBER)：取出MEMBER的地址。
• ((size_t) &((TYPE *)0)->MEMBER)：將結果轉換為適當的數據類型。

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

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

宏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的頭部添加節點N。根據LL_ADD定義的語句順序，對照著圖片分析，會更加清晰。如下圖，上面這張圖片展示了添加節點N之前的結構，下圖展示了添加節點N之后的結構。

#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的定義如下，其作用是將節點N添加到雙向鏈表H的尾部。宏LL_TAIL的定義如下，其作用是向雙向鏈表H的頭部添加節點N。根據LL_TAIL定義的語句順序，對照著圖片分析，會更加清晰。如下圖，上面這張圖片展示了添加節點N之前的結構，下圖展示了添加節點N之后的結構，可以和LL_ADD的結果進行對照。

#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的定義如下，其作用是將節點N從雙向鏈表中刪除，并且節點N回到初始狀態(其指針僅指向自身，不再指向其它地方)。

#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。如果節點的直接后繼next指向其自身，就認為其為空節點。

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

2.8 LL_FOREACH(H,N)

宏LL_FOREACH的定義如下，其作用是在雙向鏈表H中，循環遍歷出節點。

#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中，循環遍歷出節點N，因為其有提前存儲N的下一個節點T。即使N節點被清理掉，也不影響其下一個節點的遍歷，所以該宏一般用來做循環清除雙向鏈表中節點的操作，而宏LL_FOREACH僅用來遍歷雙向鏈表。

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

3 使用案例

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

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

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

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 總結

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