面試經歷
面試官：你說下什么是侵入式鏈表吧？
我：鏈表還分什么式？
面試官：是的
我：哦，從前面插入，從后面插入，對吧
面試官：eng?
我：哦，不對，侵入式，強行插入吧
面試官：停停停
旁邊的人事小姐姐聽了我的回答，面色紅潤，我心想我的回答應該不錯，美滋滋😄
面試官：那個，你怎么來的呀？
我：開車
面試官：好的，你先回去等通知吧
我心想，這么簡單，這么順利，可，回去等了半個月也沒見動靜，忽然意識當時回答侵入式鏈表的時候估計有失偏頗，趕緊上網查了下什么是侵入式鏈表，這才明白，原來是這樣，，，
鏈表
鏈表實際上是線性表的鏈式存盤結構，與陣列不同的是，它是用一組任意的存盤單元來存盤線性表中的資料，存盤單元不一定是連續的，
且鏈表的長度不是固定的，鏈表資料的這一特點使其可以非常的方便地實作節點的插入和洗掉操作，
鏈表的每個元素稱為一個節點，每個節點都可以存盤在記憶體中的不同的位置，為了表示每個元素與后繼元素的邏輯關系，以便構成“一個節點鏈著一個節點”的鏈式存盤結構，
除了存盤元素本身的資訊外，還要存盤其直接后繼資訊，因此，每個節點都包含兩個部分，第一部分稱為鏈表的資料域，用于存盤元素本身的資料資訊，這里用 data 表示，它不局限于一個成員資料，也可是多個成員資料，第二部分是一個結構體指標，稱為鏈表的指標域，用于存盤其直接后繼的節點資訊，這里用next表示，next的值實際上就是下一個節點的地址，
普通鏈表
struct foo_s {
int data;
struct foo_s *next;
};
鏈表 = 節點1 --> 節點2 -->… （前一個節點的指標域指向下一個節點的資料結構首地址）
節點 = data + next （每個節點都是使用的相同的資料結構）
侵入式鏈表
struct list_s {
struct list_s *next;
} list_t;
struct foo_s {
int data;
struct list_s link;
};
鏈表 = 節點1 --> 節點2 --> … （前一個節點的指標域指向下一個節點的指標域）
節點 = data + next （節點可以使用不同的資料結構，如 struct foo_s、struct foo_s2，只要在它們內部都包含 struct list_s就可以了）
內核鏈表
內核中使用的鏈表大多數都是侵入式鏈表，不過要比上面的例子稍微復雜點，是侵入式雙向回圈鏈表，如下圖
其資料結構如下，這里以 led_classdev 為例
struct list_head {
struct list_head *next, *prev;
};
struct led_classdev {
const char *name;
enum led_brightness brightness;
enum led_brightness max_brightness;
int flags;
...
struct list_head node; /* LED Device list */
...
}
從上面結構體可以看出，鏈表(list_head)是嵌(侵)入在其它宿主資料結構(led_classdev)中的，這些宿主資料結構可以不相同，并且，這些宿主資料結構中可以包含多個鏈表，
侵入式鏈表(內核鏈表)的好處
如果我們有一種資料結構 foo，并且需要維持一個這種資料結構的雙鏈佇列，最簡單的、也是最常用的辦法就是在這個資料結構的型別定義中加入兩個指標，例如：
typedef struct foo {
struct foo *prev;
struct foo *next;
....
} foo;
然后為這種資料結構寫一套用于各種佇列操作的子程式，由于用來維持佇列的這兩個指標的型別是固定的（都指向 foo 資料結構），這些子程式不能用于其它資料結構的佇列，換言之，需要維持多少種資料結構的佇列，就得有多少套的佇列操作子程式，對于使用佇列較少的應用程式或許不是個大問題，但對于使用大量佇列的內核就成問題了，所以，Linux 內核中采用了一套通用的、一般的、可以用到各種不同資料結構的佇列操作，為此，代碼的作者們把指標 prev 和 next 從具體的“宿主”資料結構中抽象出來成為一種資料結構 list_head，這種資料結構既可以“寄宿”在具體的宿主資料結構內部，成為該資料結構的一個“連接件”；也可以獨立存在而成為一個佇列的頭，這個資料結構的定義在 include/linux/list.h 中
實體決議
我們以用于記憶體頁面管理的 page 資料結構為例：
typedef struct page {
struct list_head list;
...
struct list_head lru;
...
} mem_map_t;
可見，在 page 資料結構中寄宿了兩個 list_head 結構，或者說有兩個佇列操作的連接件，所以 page 結構可以同時存在于兩個雙鏈佇列中，
一個疑問
有些小伙伴可能發問了：佇列操作都是通過 list_head 進行的，但是那不過是個連接件，如果我們手上有宿主結構，那當然知道它的某個 list_head 在哪里，從而以此為引數呼叫 list_add() 或 list_del()；可是，反過來，當我們順著一個佇列取得其中一項的 list_head 結構時，又怎樣找到其宿主結構呢？在 list_head 結構中并沒有指向宿主結構的指標啊，畢竟，我們真正關心的是宿主結構，而不是連接件，
這就要提到內核中 offsetof、container_of 這兩個神奇的宏了，使用這兩個宏，在給定鏈表結構地址時，我們能夠獲取其宿主結構的地址，這樣就能開心地操作宿主結構了，這里我們只給出它們的定義，后面再專門寫文章介紹他們，
include/linux/kernel.h
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member) * __mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298664.html
標籤：其他