主要內容
- 鏈表
- 佇列
- 映射
- 二叉樹
1. 鏈表
- 單向鏈表、雙向鏈表
- 環形鏈表
linux內核中的鏈表使用方法和一般資料結構中定義的鏈表是有所不同的，
傳統鏈表：
傳統雙向鏈表.png
傳統的鏈表有個最大的缺點就是不好共通化，因為每個node中的data1，data2等等都是不確定的(無論是個數還是型別)，
linux中的鏈表巧妙的解決了這個問題，linux的鏈表不是將用戶資料保存在鏈表節點中，而是將鏈表節點保存在用戶資料中，
linux的鏈表節點只有2個指標(pre和next)，這樣的話，鏈表的節點將獨立于用戶資料之外，便于實作鏈表的共同操作，
Linux內核鏈表：
linux內核雙向鏈表.png
最大的問題在于，怎樣通過鏈表的節點來取得用戶資料？
答案是通過container_of()宏
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member)*__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })- type一般是個結構體，也就是包含用戶資料和鏈表節點的結構體，
- ptr是指向type中鏈表節點的指標
- member則是type中定義鏈表節點是用的名字
比如：
struct student
{
int id;
char* name;
struct list_head list;
};- type是struct student
- ptr是指向stuct list的指標，也就是指向member型別的指標
- member就是 list
下面分析一下container_of宏:
// 步驟1：將數字0強制轉型為type*，然后取得其中的member元素
((type *)0)->member // 相當于((struct student *)0)->list
// 步驟2：定義一個臨時變數__mptr，并將其也指向ptr所指向的鏈表節點
const typeof(((type *)0)->member)*__mptr = (ptr);
// 步驟3：計算member欄位距離type中第一個欄位的距離，也就是type地址和member地址之間的差
// offset(type, member)也是一個宏，定義如下：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
// 步驟4：將__mptr的地址 - type地址和member地址之間的差
// 其實也就是獲取type的地址
步驟1，2，4比較容易理解，下面的圖以sturct student為例進行說明步驟3：
- 首先需要知道 ((TYPE *)0) 表示將地址0轉換為 TYPE 型別的地址
- 由于TYPE的地址是0，所以((TYPE *)0)->MEMBER 也就是 MEMBER的地址和TYPE地址的差，如下圖所示：
理解步驟3.png
2. 佇列
FIFO，沒啥好說的
- 佇列的size在初始化時，始終設定為2的n次方
- 使用佇列之前將佇列結構體中的鎖(spinlock)釋放
3. 映射
類似于python里的字典
散串列是一種映射，但自平衡二叉樹搜索樹也能實作存盤資料，比如C++中map就是紅黑樹嘛，在最壞情況下能有更好的表現
Linux內核中的映射叫idr，目標是映射一個位于id標識數UID到一個指標
4. 紅黑樹
5. 演算法復雜度
大o符號代表上限（更差情況）
大θ符號代表最小上限
文末給大家分享幾個Linux內核的視頻講解：
1、linux內核，行程調度器的實作，完全公平調度器 CFS：https://www.bilibili.com/video/BV1hf4y1B7Yg/
2、 Linux內核丨紅黑樹 | 設計模式與演算法：https://www.bilibili.com/video/BV1ig4y1v7So/
3、Linux內核學習視頻來啦，這么學，才簡單：https://www.bilibili.com/video/BV1m54y127Mb/
附上一份Linux內核學習大綱：
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/242418.html
標籤：其他