鏈表是C語(yǔ)言編程中常用的數(shù)據(jù)結(jié)構(gòu)，比如我們要建一個(gè)整數(shù)鏈表，一般可能這么定義：

struct?int_node {int?val;struct?int_node *next;};

?

為了實(shí)現(xiàn)鏈表的插入、刪除、遍歷等功能，另外要再實(shí)現(xiàn)一系列函數(shù)，比如：

void?insert_node(struct?int_node **head, int?val);void?delete_node(struct?int_node *head, struct?int_node *current);void?access_node(struct?int_node *head){struct?int_node *node;for?(node = head; node != NULL; node = node->next) {// do something here}}

?

如果我們的代碼里只有這么一個(gè)數(shù)據(jù)結(jié)構(gòu)的話，這樣做當(dāng)然沒(méi)有問(wèn)題，但是當(dāng)代碼的規(guī)模足夠大，需要管理很多種鏈表，難道需要為每一種鏈表都要實(shí)現(xiàn)一套插入、刪除、遍歷等功能函數(shù)嗎？

熟悉C++的同學(xué)可能會(huì)說(shuō)，我們可以用標(biāo)準(zhǔn)模板庫(kù)啊，但是，我們這里談的是C，在C語(yǔ)言里有沒(méi)有比較好的方法呢？

在本文中，我們把目光投向當(dāng)今開(kāi)源界最大的C項(xiàng)目--Linux Kernel，看看Linux內(nèi)核如何解決這個(gè)問(wèn)題。

Linux內(nèi)核中一般使用雙向鏈表，聲明為struct list_head，這個(gè)結(jié)構(gòu)體是在include/linux/types.h中定義的，鏈表的訪問(wèn)是以宏或者內(nèi)聯(lián)函數(shù)的形式在include/linux/list.h中定義。

struct?list_head {struct?list_head *next, *prev;};

?

Linux內(nèi)核為鏈表提供了一致的訪問(wèn)接口。

void?INIT_LIST_HEAD(struct?list_head *list)；void?list_add(struct?list_head *new, struct?list_head *head)；void?list_add_tail(struct?list_head *new, struct?list_head *head)；void?list_del(struct?list_head *entry);int?list_empty(const?struct?list_head *head)；

?

以上只是從Linux內(nèi)核里摘選的幾個(gè)常用接口，更多的定義請(qǐng)參考Linux內(nèi)核源代碼。

我們先通過(guò)一個(gè)簡(jiǎn)單的實(shí)作來(lái)對(duì)Linux內(nèi)核如何處理鏈表建立一個(gè)感性的認(rèn)識(shí)。

#include <stdio.h>#include "list.h"struct?int_node {int?val;struct?list_head list;};int?main(){struct?list_head head, *plist;struct?int_node a, b;a.val = 2;b.val = 3;INIT_LIST_HEAD(&head);list_add(&a.list, &head);list_add(&b.list, &head);list_for_each(plist, &head) {struct?int_node *node = list_entry(plist, struct?int_node, list);printf("val = %d\n", node->val);}return?0;}

?

看完這個(gè)實(shí)作，是不是覺(jué)得在C代碼里管理一個(gè)鏈表也很簡(jiǎn)單呢？

代碼中包含的頭文件list.h是我從Linux內(nèi)核里抽取出來(lái)并做了一點(diǎn)修改的鏈表處理代碼，現(xiàn)附在這里給大家參考，使用的時(shí)候只要把這個(gè)頭文件包含到自己的工程里即可。

代碼

list_head通常是嵌在數(shù)據(jù)結(jié)構(gòu)內(nèi)使用，在上文的實(shí)作中我們還是以整數(shù)鏈表為例，int_node的定義如下：

struct?int_node {int?val;struct?list_head list;};

1 2 3 4

使用list_head組織的鏈表的結(jié)構(gòu)如下圖所示：

遍歷鏈表是用宏list_for_each來(lái)完成。

#define list_for_each(pos, head) \for?(pos = (head)->next; prefetch(pos->next), pos != (head); \pos = pos->next)

?

在這里，pos和head均是struct list_head。在遍歷的過(guò)程中如果需要訪問(wèn)節(jié)點(diǎn)，可以用list_entry來(lái)取得這個(gè)節(jié)點(diǎn)的基址。

#define list_entry(ptr, type, member) \container_of(ptr, type, member)

?

我們來(lái)看看container_of是如何實(shí)現(xiàn)的。如下圖所示，我們已經(jīng)知道TYPE結(jié)構(gòu)中MEMBER的地址，如果要得到這個(gè)結(jié)構(gòu)體的地址，只需要知道MEMBER在結(jié)構(gòu)體中的偏移量就可以了。如何得到這個(gè)偏移量地址呢？這里用到C語(yǔ)言的一個(gè)小技巧，我們不妨把結(jié)構(gòu)體投影到地址為0的地方，那么成員的絕對(duì)地址就是偏移量。得到偏移量之后，再根據(jù)ptr指針指向的地址，就可以很容易的計(jì)算出結(jié)構(gòu)體的地址。

list_entry就是通過(guò)上面的方法從ptr指針得到我們需要的type結(jié)構(gòu)體。

Linux內(nèi)核代碼博大精深，陳莉君老師曾把它形容為“覆壓三百余里，隔離天日”（摘自《阿房宮賦》），可見(jiàn)其內(nèi)容之豐富、結(jié)構(gòu)之龐雜。內(nèi)核里有著眾多重要的數(shù)據(jù)結(jié)構(gòu)，具有相關(guān)性的數(shù)據(jù)結(jié)構(gòu)之間很多都是用本文介紹的鏈表組織在一起，看來(lái)list_head結(jié)構(gòu)雖小，作用可真不小。

Linux內(nèi)核是個(gè)偉大的工程，其源代碼里還有很多精妙之處，值得C/C++程序員認(rèn)真去閱讀，即使我們不去做內(nèi)核相關(guān)的工作，閱讀精彩的代碼對(duì)程序員自我修養(yǎng)的提高也是大有裨益的。