程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> C語言的通用鏈表

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測試。
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved