Linux核心連結串列實現過程

NO IMAGE

關於雙連結串列實現,一般教科書上定義一個雙向連結串列節點的方法如下:
複製程式碼 程式碼如下:
struct list_node{
stuct list_node *pre;
stuct list_node *next;
ElemType data;
}

即一個連結串列節點包含:一個指向前向節點的指標、一個指向後續節點的指標,以及資料域共三部分。
但檢視linux核心程式碼中的list實現時,會發現其與教科書上的方法有很大的差別。
來看看linux是如何實現雙連結串列。
雙連結串列節點定義
複製程式碼 程式碼如下:
struct list_head {
 struct list_head *next, *prev;
};

發現連結串列節點中根本就沒有資料域,這樣的連結串列有什麼用?linux核心中定義這樣的連結串列原因何在?
這是因為linux中是通過獨立定義一個連結串列結構,並在結構體中內嵌一個連結串列節點來實現連結串列結構的。這樣有一個好處就是能達到連結串列與結構體分離的目的。如此一來,我們構建好一個連結串列後,其結構示意圖如下:

連結串列的定義及初始化巨集定義:
複製程式碼 程式碼如下:
#define LIST_HEAD_INIT(name){&(name),&(name)} 
#define LIST_HEAD(name) \
      struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
      (ptr)->next = (ptr); (ptr)->prev = (ptr);\
      } while (0)

LIST_HEAD(name)巨集用來定義一個連結串列頭,並使他的兩個指標都指向自己。我們可以在程式的變數宣告處,直接呼叫LIST_HEAD(name)巨集,來定義並初始化一個名為name的連結串列。也可以先宣告一個連結串列,然後再使用INIT_LIST_HEAD來初始化這個連結串列。
也即:
複製程式碼 程式碼如下:
 LIST_HEAD(mylist);
 與
 struct list_head mylist;
 INIT_LIST_HEAD(&mylist);

 是等價的。

插入操作
複製程式碼 程式碼如下:
/*僅供內部呼叫
  * Insert a new entry between two known consecutive entries.
  * This is only for internal list manipulation where we know
  * the prev/next entries already!
  */
static inline void __list_add(struct list_head *new,
         struct list_head *prev,
         struct list_head *next)
{
 next->prev = new;
 new->next = next;
 new->prev = prev;
 prev->next = new;
}
 
複製程式碼 程式碼如下:
//在頭節點後面插入一個節點
static inline void list_add(struct list_head *new, struct list_head *head)
{
 __list_add(new, head, head->next);
}
//在尾節點後插入一個節點
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
 __list_add(new, head->prev, head);
}

刪除操作
複製程式碼 程式碼如下:
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
 next->prev = prev;
 prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
 __list_del(entry->prev, entry->next);
}

刪除連結串列節點的操作很簡單,是通過將要刪除的節點的前一個節點與後一個節點連結到一起。
連結串列節點替換操作
 複製程式碼 程式碼如下:
static inline void list_replace(struct list_head *old,
    struct list_head *new)
{
 new->next = old->next;
 new->next->prev = new;
 new->prev = old->prev;
 new->prev->next = new;
}
 

連結串列遍歷操作(重點在這裡)
首先來看一個如何根據連結串列節點地址得到其所在結構體的地址。
複製程式碼 程式碼如下:
#define list_entry(ptr, type, member) container_of(ptr, type, member)
//container_of巨集的定義如下:
#define container_of(ptr, type, member)({\
        const typeof(((type *)0)->member ) *__mptr = (ptr);\
        (type *)( (char *)__mptr – offsetof(type,member) );})
//offsetof的巨集定義如下:
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
將上述簡化一下成為下面這樣:
#define list_entry(ptr, type, member) \
  ((type *)((char *)(ptr)-(size_t)(&((type *)0)->member)))

是一個帶3個引數的巨集,該巨集的作用是獲取連結串列節點(ptr)所在結構體的起始地址。有了這個巨集,我們只要知道某一個連結串列節點指標,就可以通過該連結串列節點得到其所在結構體的指標,從而,我們遍歷連結串列,也便可以達到遍歷我們自己定義的結構體。第一個引數為一個地址,他是結構體連結串列節點元素的地址,第二個引數是結構體型別,第三個引數是連結串列節點元素在結構體中的名字。
來仔細分析一下這個巨集:
最外面的一層括號可以去掉,這是為了防止巨集擴充套件的,去掉如下:
(type *) ((char *)(ptr)-(size_t)(&((type *)0)->member))
現在就比較清楚了,首先(type *)是C強制轉換操作,就是將後面的的資料轉化成type結構的指標。而後面的操作可以再分解
(char *)(ptr) – (size_t)(&((type *)0)->member)
 這樣就是一個減法的操作,前面是一個指標,我們傳過去的結構體連結串列節點元素的指標,這裡被轉化成指向字元的。而後面是一個整形,可以再分解
(size_t) (&((type *)0)->member)
顯然這個整形是一個指標轉化的,而這個指標又可以再分解,
&((type *)0)->member
     可以看出這個指標是一個變數取地址得到的,這個變數又是什麼呢
((type *)0)->member
     看起來有點奇怪,不過這個操作是整個巨集中最精妙的,他將地址0轉化成type型別,接下來又取得這個結構的member元素,member就是我們傳進來的引數:元素在結構體中的命名。其實((type *)0)->member取的變數是內容是什麼一點都不重要,重要的我們要取這個變數的地址。取完這個地址將它轉換成size_t型別,這樣這個資料就是((type *)0)->member相對與地址0的偏移。回到上面的那個減法,將結構體中連結串列節點元素的地址與他與結構體首地址的偏移相減,不就得到了結構體的地址了嗎。)(&((type *)0)->member)))
    最外面的一層括號可以去掉,這是為了防止巨集擴充套件的,去掉如下:
(type *) ((char *)(ptr)-(size_t)(&((type *)0)->member))
     現在就比較清楚了,首先(type *)是C強制轉換操作,就是將後面的資料轉化成type結構的指標。而後面的操作可以再分解
(char *)(ptr) – (size_t)(&((type *)0)->member)
     這樣就是一個減法的操作,前面是一個指標,我們傳過去的結構體元素的指標,這裡被轉化成指向字元的。而後面是一個長整形,可以再分解
(size_t) (&((type *)0)->member)
     顯然這個長整形是一個指標轉化的,而這個指標又可以再分解,
&((type *)0)->member
     可以看出這個指標是一個變數取地址得到的,這個變數又是什麼呢?
((type *)0)->member
     起來有點奇怪,不過這個操作是整個巨集中最精妙的,他將地址0轉化成type型別,接下來又取得這個結構的member元素,member就是我們傳進來的引數:元素在結構體中的命名。其實((type *)0)->member取的變數是內容是什麼一點都不重要,重要的我們要取這個變數的地址。取完這個地址將它轉換成size_t型別,這樣這個資料就是((type *)0)->member相對與地址0的偏移。回到上面的那個減法,將結構體中元素的地址與他與結構體首地址的偏移相減,便得到了結構體的地址了。
連結串列的遍歷操作時通過一個巨集來實現的:
複製程式碼 程式碼如下:
#define list_for_each(pos, head) \
   for(pos = (head)->next, prefetch(pos->next);pos!=(head);\
        pos = pos->next,prefetch(pos->next))

其中prefetch是用於效能優化,暫時不用去管它。
從上述連結串列遍歷巨集可以看出,其只是一次獲得了連結串列節點指標,在實際應用中,我們都需要獲取連結串列節點所在結構體的資料項,因此,通常將list_for_each和list_entry一起使用。為此,linux的list實現提供了另外一個介面如下:
複製程式碼 程式碼如下:
#define list_for_each_entry(pos, head, member)\
 for(pos = list_entry((head)->next, typeof(*pos), member);\
    prefetch(pos->member.next), &pos->member != (head);\
    pos = list_entry(pos->member.next, typeof(*pos), member))
 
有了這個介面,我們就可以通過連結串列結構來遍歷我們實際的結構體資料域了。
例如,我們定義了一個結構體如下:
複製程式碼 程式碼如下:
struct mystruct{
ElemType1 data1;
ElemType2 data2;
strcut list_head anchor;//通常我們稱結構體內的連結串列節點為連結串列錨,因為它有定位的作用。
}

那麼我們遍歷連結串列的程式碼如下:
複製程式碼 程式碼如下:
struct mystruct  *pos;
list_for_each_entry(pos,head,anchor){
mystruct *pStruct=pos;
//do something with pStruct…..
}

此外Linux連結串列還提供了兩個對應於基本遍歷操作的”_safe”介面:list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member),它們要求呼叫者另外提供一個與pos同型別的指標n,在for迴圈中暫存pos下一個節點的地址,避免因pos節點被釋放而造成的斷鏈。
當然,linux連結串列不止提供上述介面,還有
複製程式碼 程式碼如下:
list_for_each_prev(pos, head)
list_for_each_prev_safe(pos, n, head)
list_for_each_entry_reverse(pos, head, member)
list_prepare_entry(pos, head, member)
static inline int list_empty_careful(const struct list_head *head)
static inline void list_del_init(struct list_head *entry)
static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
static inline int list_empty(const struct list_head *head)

您可能感興趣的文章:

Linux中的核心連結串列例項詳解Linux 核心通用連結串列學習小結