歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux綜合 >> Linux內核

Linux內核鏈表的研究與應用

前言:
在Linux內核中使用了大量的鏈表來組織其數據,其采用了雙向鏈表作為其基本的數據結構。但是與我們傳統的數據結構中所學的雙向鏈表又有著本質的一些不同(其不包含數據域)。其主要是Linux內核鏈表在設計時給出了一種抽象的定義。

采用這種定義有以下兩種好處:1是可擴展性,2是封裝。可擴展性肯定是必須的,內核一直都是在發展中的,所以代碼都不能寫成死代碼,要方便修改和追加。將鏈表常見的操作都進行封裝,使用者只關注接口,不需關注實現。

分析內核中的鏈表我們可以做些什麼呢?

個人認為我們可以將其復用到用戶態編程中,以後在用戶態下編程就不需要寫一些關於鏈表的代碼了,直接將內核中list.h中的代碼拷貝過來用。也可以整理出my_list.h,在以後的用戶態編程中直接將其包含到C文件中。

一.Linux 內核鏈表數據結構
1.其代碼位於include/linux/list.h中,3.0內核中將其數據結構定義放在了include/linux/types.h中
鏈表的數據定義:

struct  list_head{

    struct list_head  * next,*prev;

}

這個不含數據域的鏈表,可以嵌入到任何結構中,例如可以按如下方式定義含有數據域的鏈表:

struct  test_list{

    void  *testdata;

        structlist_head list;

};

說明:

1>list 域隱蔽了鏈表的指針特性

2>struct list_head 可以位於結構的任何位置,可以給其起任何名字。

3>在一個結構體中可以有多個list域。

以struct list_head 為基本對象,對鏈表進行插入、刪除、合並以及遍歷等各種操作。

2.內核鏈表數據結構的設計思想是:
盡可能的代碼重用,化大堆的鏈表設計為單個鏈表。

3.使用循環鏈表的好處:
雙向循環鏈表的效率是最高的,找頭節點,尾節點,直接前驅,直接後繼時間復雜度都是O (1) ,而使用單鏈表,單向循環鏈表或其他形式的鏈表是不能完成的。

4.鏈表的構造:

如果需要構造某類對象的特定列表,則在其結構中定義一個類型為list_head
指針的成員(例如上面所說的struct test_list),通過這個成員將這類對象連接起來,形成所需列表,並通過通用鏈表函數對其進行操作。其優點是只需編寫通用鏈表函數,即可構造和操作不同對象的列表,而無需為每類對象的每種列表編寫專用函數,實現了代碼的重用。

5.如何內核鏈表使用:
如果想對某種類型創建鏈表,就把一個list_head類型的變量嵌入到該類型中,用list_head中的成員和相對應的處理函數來對鏈表進行遍歷。如果想得到相應的結構的指針,使用list_entry可以算出來。

二.鏈表的聲明和初始化宏
實際上,struct list_head 只定義了鏈表結點,並沒有專門定義鏈表頭,可以 使用以下兩個宏
 #define LIST_HEAD_INIT(name) { &(name), &(name) }
 #define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)
1>name 為結構體struct list_head{}的一個結構體變量,&(name)為該結構體變量的地址。用name結構體變量的始地址將改結構體變量進行初始化。
2>LIST_HEAD_INIT(name)函數宏只進行初始化
3>LIST_HEAD(name)函數宏聲明並進行初始化
4>如果要聲明並初始化自己的鏈表頭mylist_head,則直接調用LIST_HEAD:
LIST_HEAD(mylist_head)
調用之後,mylist_head的next,prev指針都初始化為指向自己,這樣就有了一個空鏈表。因此可以得知在Linux中用頭指針的next是否指向自己來判斷鏈表是否為空。
5>除了LIST_HEAD宏在編譯時靜態初始化,還可以使用內嵌函數INIT_LIST_HEAD(struct list_head *list)在運行時進行初始化。
例如:調用INIT_LIST_HEAD(&mylist_head)對mylist_head鏈表進行初始化。
static inline void INIT_LIST_HEAD(struct list_head *list)
  {
          list->next = list;
          list->prev = list;
}
注無論是采用哪種方式,新生成的鏈表頭的指針next,prev都初始化為指向自己

Copyright © Linux教程網 All Rights Reserved