玩轉C連結清單

連結清單是C語言程式設計中常用的資料結構，比如我們要建一個整數連結清單，一般可能這麼定義：

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

為了實作連結清單的插入、删除、周遊等功能，另外要再實作一系列函數，比如：

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 } }

如果我們的代碼裡隻有這麼一個資料結構的話，這樣做當然沒有問題，但是當代碼的規模足夠大，需要管理很多種連結清單，難道需要為每一種連結清單都要實作一套插入、删除、周遊等功能函數嗎？

熟悉C++的同學可能會說，我們可以用标準模闆庫啊，但是，我們這裡談的是C，在C語言裡有沒有比較好的方法呢？

Mr.Dave

在他的部落格裡介紹了自己的

實作

，這個實作是個很好的方案，各位不妨可以參考一下。在本文中，我們把目光投向當今開源界最大的C項目--

Linux Kernel

，看看Linux核心如何解決這個問題。

Linux核心中一般使用雙向連結清單，聲明為struct list_head，這個結構體是在include/linux/types.h中定義的，連結清單的通路是以宏或者内聯函數的形式在include/linux/list.h中定義。

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

Linux核心為連結清單提供了一緻的通路接口。

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核心裡摘選的幾個常用接口，更多的定義請參考

Linux核心源代碼

。

我們先通過一個簡單的實作來對Linux核心如何處理連結清單建立一個感性的認識。

#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; }

看完這個實作，是不是覺得在C代碼裡管理一個連結清單也很簡單呢？

代碼中包含的頭檔案list.h是我從Linux核心裡抽取出來并做了一點修改的連結清單處理代碼，現附在這裡給大家參考，使用的時候隻要把這個頭檔案包含到自己的工程裡即可。

代碼

list_head通常是嵌在資料結構内使用，在上文的實作中我們還是以整數連結清單為例，int_node的定義如下：

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

使用list_head組織的連結清單的結構如下圖所示：

周遊連結清單是用宏list_for_each來完成。

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

在這裡，pos和head均是struct list_head。在周遊的過程中如果需要通路節點，可以用list_entry來取得這個節點的基址。

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

我們來看看container_of是如何實作的。如下圖所示，我們已經知道TYPE結構中MEMBER的位址，如果要得到這個結構體的位址，隻需要知道MEMBER在結構體中的偏移量就可以了。如何得到這個偏移量位址呢？這裡用到C語言的一個小技巧，我們不妨把結構體投影到位址為0的地方，那麼成員的絕對位址就是偏移量。得到偏移量之後，再根據ptr指針指向的位址，就可以很容易的計算出結構體的位址。

list_entry就是通過上面的方法從ptr指針得到我們需要的type結構體。

Linux核心代碼博大精深，

陳莉君

老師曾把它形容為“覆壓三百餘裡，隔離天日”（摘自《

阿房宮賦

》），可見其内容之豐富、結構之龐雜。核心裡有着衆多重要的資料結構，具有相關性的資料結構之間很多都是用本文介紹的連結清單組織在一起，看來list_head結構雖小，作用可真不小。

Linux核心是個偉大的工程，其源代碼裡還有很多精妙之處，值得C/C++程式員認真去閱讀，即使我們不去做核心相關的工作，閱讀精彩的代碼對程式員自我修養的提高也是大有裨益的。