C語言的通用鏈表

C語言的通用鏈表

在操作系統編程中， 往往是使用C語言， 但C使用起來極為痛苦， 不像C++有方便的STL模板庫使用。

linux內核中，有一套非常神奇的通用鏈表結構，能夠方便的使用，管理各種類型的數據，我們今天就來研究一下，內核中的C數據結構。

本文參考：【深入分析 Linux 內核鏈表】

首先，我們的目標是構建一個循環雙鏈表結構，為何是雙鏈表，還要循環，當然是從易用性考慮了，雙鏈表能夠方便的得知自己的上一個元素，在內核中管理數據更為方便。

其一般結構大概是這樣：

實現機制

首先定義一個list_node結構，用來保存鏈表節點信息：

    /**
     * @brief 鏈表節點結構
     */
    typedef struct _list_node
    {
        struct _list_node   *next;
        struct _list_node   *prev;
    } list_node;

然後用一個存放數據的結構，比如我們要用int型的鏈表，如下定義：

    /**
     * @brief 數據存放結構
     */
    typedef struct _Int_List
    {
        list_node   node;
        int         data;
    } Int_List;

這和我們傳統的鏈表實現思路好像不大一樣，我們經典的C語言鏈表當然是在鏈表中保存數據：

    /**
     * @brief 鏈表節點結構
     */
    typedef ElementType     int;
    typedef struct _list_node
    {
        struct _list_node   *next;
        struct _list_node   *prev;
        ElementType         data;
    } list_node;

但這樣的實現必然會造成鏈表結構被反復定義，難以實現泛型。另外一種思路可能是將ElementType實現成void*指針，然後在使用時進行強制類型轉換，但這樣必然會帶來反復的類型轉換，而且其使用相對不便。

這時要出問題了，如果數據在外層，鏈表在裡層，那麼如何從鏈表找到數據呢？

offsetof宏和container_of宏

為了實現從內層元素找外層元素的功能，我們需要用到這兩個系統宏，一眼看上去很復雜，但實際上並不難理解。

/**
 * @brief 確定當前成員變量,在結構體中偏移量的宏
 */
#ifndef offsetof
#define offsetof(type, member) ((size_t) &((type*)0)->member)
#endif

/**
 * @brief 根據成員變量,找包含他的結構體指針
 */
#ifndef container_of
#define container_of(ptr, type, member) ({  
    const typeof( ((type *)0)->member ) *__mptr = (ptr); 
    (type *)( (char *)__mptr - offsetof(type,member) );})
#endif

這兩個宏較為復雜，首先是offsetof宏，這個宏用0號指針去尋找成員變量，我們試想，如何是普通的一個結構體，C編譯器如何查找其一個成員呢？
例如：

    /**
     * @brief 數據存放結構
     */
    typedef struct _Int_List
    {
        list_node   node;
        int         data;
    } Int_List;

假設我們用Int_List A語句，實例化一個結構體，然後取到了A的地址0x00001000
那麼node的起始地址是不是也是0x00001000
data的起始地址是不是0x00001000+data的偏移量？

那麼如何我想求data的偏移量，不就是如下的代碼麼：

    (&A)->data - (&A);

如果A的地址為0時，那麼也就不用減了，就是我們宏定義中的用法。

而container_of宏也是采用類似的思路，既然找到了當前list_node成員的偏移量，那麼減去偏移量，便是外層包圍著的結構體的起始地址。

那好，這樣我們就能實現這個鏈表了，但其實也不用這樣費事，還有簡單的辦法，那就是讓我們的被包含的list_node成員結構，處於我們數據存儲結構的第一個位置，那麼其地址就是包圍其結構的地址，直接類型轉換即可。

這種思路實際上也被用於C語言的繼承機制的實現。

Github項目

到此，我們已經講解了通用鏈表的實現思路，大家可以嘗試自己實現一個獨特的通用鏈表，具體內容就不一一贅述，我將完整的工程已經發布到了Github上面，歡迎大家前來fork測試。