1、內(nèi)核中的鏈表節(jié)點表示

在內(nèi)核中，一個驅(qū)動管理程序負(fù)責(zé)管理多個設(shè)備，如果需要在驅(qū)動程序中跟蹤每個設(shè)備，這就需要鏈表。鏈表有兩種類型：

● 單鏈表

● 雙鏈表

然而,內(nèi)核中因為種種原因,只實現(xiàn)了雙鏈表,這種結(jié)構(gòu)可以實現(xiàn)FIFO(先進先出)和LIFO(后進先出).如需要使用內(nèi)核的鏈表支持,只需引用頭文件<linux/list.h>,核心部分的數(shù)據(jù)結(jié)構(gòu)如下:

在內(nèi)核中，這個結(jié)構(gòu)體用在鏈表頭結(jié)點和鏈表普通節(jié)點中。也就是說，在內(nèi)核中使用結(jié)構(gòu)體表示鏈表時，必須在該結(jié)構(gòu)中添加struct list_head 的實例。舉個例子，比如說學(xué)生成績的結(jié)構(gòu)體為：

要為其創(chuàng)建鏈表，就需要在該結(jié)構(gòu)體中添加一個struct list_head的實例。變成這個樣子：

如此這般，當(dāng)我們知道某個鏈表節(jié)點中struct list_head的指針時，便可以使用list.c中提供的宏list_entry方法來獲取該節(jié)點struct student的地址。如果有時間看代碼的話，其實list_entry是通過調(diào)用宏container_of來實現(xiàn)通過結(jié)構(gòu)體成員變量的指針獲取結(jié)構(gòu)體的地址。這里順手給出container_of的使用方法：

2、內(nèi)核中的鏈表操作

上面的論述中，我們已經(jīng)清楚了內(nèi)核中的鏈表節(jié)點的表現(xiàn)形式，接下來我們再學(xué)習(xí)內(nèi)核中如何對鏈表進行創(chuàng)建、銷毀以及增刪查改等操作。

2.1鏈表頭節(jié)點的創(chuàng)建（鏈表并不一定有頭結(jié)點）

????通過閱讀代碼，我發(fā)現(xiàn)內(nèi)核中所創(chuàng)建的鏈表中，其創(chuàng)建方式分為靜態(tài)創(chuàng)建和動態(tài)創(chuàng)建兩種。

有struct list_head可知，頭結(jié)點都是沒有數(shù)據(jù)域的，僅僅只有指針域，因此初始化時頭結(jié)點的指針域都指向其自身。那使用INIT_LIST_HEAD和LIST_HEAD的場景有什么區(qū)別呢？

我的理解是：當(dāng)需要初始化的struct list_head實例是獨立的且不是嵌入在其他結(jié)構(gòu)體中時，使用這兩種方法初始化都是可以的，這是因為此時的struct list_head并沒有進行實例化，也就沒有開辟對應(yīng)的內(nèi)存空間。但是若struct list_head已經(jīng)嵌入到其他結(jié)構(gòu)體中，它的內(nèi)存空間就會隨著父結(jié)構(gòu)體的開辟而開辟，這時再繼續(xù)使用LIST_HEAD就不合適了。

簡單來說，INIT_LIST_HEAD與LIST_HEAD的區(qū)別就是內(nèi)存空間的開辟，前者不具備開辟內(nèi)部才能空間的功能，但后者有。

2.2創(chuàng)建普通節(jié)點

創(chuàng)建普通節(jié)點，只需要創(chuàng)建結(jié)構(gòu)體實例，并初始化嵌入在其中的struct list_head字段即可。代碼如下：

這里創(chuàng)建的新節(jié)點，也是將struct list_head字段的指針初始化為指向自己本身，是為了避免出現(xiàn)內(nèi)存泄漏。

2.3添加鏈表節(jié)點

內(nèi)核提供了list_add用于向鏈表中添加新節(jié)點，它包裝了內(nèi)部函數(shù)__list_add。原型如下：

除了list_add外，內(nèi)核還提供了list_add_tail，實現(xiàn)在鏈表尾端加入新節(jié)點，原型如下：

2.4刪除鏈表節(jié)點

內(nèi)核中刪除鏈表節(jié)點的代碼：

該函數(shù)實現(xiàn)了斷開指定節(jié)點的prev和next指針，節(jié)點移除后，其占據(jù)的內(nèi)存需要手動kfree釋放。

2.5鏈表遍歷

使用的是list_for_each_entry宏進行鏈表遍歷。

示例代碼如下：

這段代碼可以實現(xiàn)統(tǒng)計鏈表中l(wèi)iming出現(xiàn)的次數(shù)。這個循環(huán)終止的條件是astu指向的節(jié)點的struct list_head字段的地址與傳入節(jié)點的struct list_head字段的地址相等，表示鏈表循環(huán)結(jié)束。

在這個循環(huán)中，鏈表節(jié)點的移動的都是struct list_head的指針來實現(xiàn)。