在操作系統編程中, 往往是使用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*指針,然後在使用時進行強制類型轉換,但這樣必然會帶來反復的類型轉換,而且其使用相對不便。
這時要出問題了,如果數據在外層,鏈表在裡層,那麼如何從鏈表找到數據呢?
為了實現從內層元素找外層元素的功能,我們需要用到這兩個系統宏,一眼看上去很復雜,但實際上並不難理解。
/**
* @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上面,歡迎大家前來fork測試。