# Linux kernel linked list
**Reference: [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)**
### Linux中的linked list
circular doubly-linked list (雙向環狀鏈結串列，以下簡稱 list) 是Linux核心中相當實用的結構體，在行程 (process) 管理的相關實作中可見到應用。其概念是將結構體 list_head 嵌入到所需的結構體中，再藉由稍後會提及的 container_of 巨集得知 list 個別節點的地址，架構如下。
:::info
Head 是個特例，無法藉由 container_of 巨集來找到對應的節點，因為它並未嵌入到任何結構體之中，其存在是為了找到 list 整體 (list header)。
:::
* **list_head結構體**
```c
struct list_head
{
//the struct takes 8*2 bytes
struct list_head *prev;
struct list_head *next;
};
```
放進自定義的結構體中就會像 ...
```c
typedef struct node
{
int val;
struct list_head list;
}node;
```
### API的實作
當然，在Linux kernel的list.h檔中有許多操作應用，這邊簡單舉幾個例子 ...
* **LIST_HEAD**
```c
/* this define is used to create the header of list,
* and point the next and prev to itself. */
#define LIST_HEAD(head) struct list_head head = {&head, &head};
```
* **list_entry()**
```c
/* given the member of element of struct (which we want to get address),
* member's ptr and struct's type, than we can get the address of element*/
#define container_of(ptr, type, member) \
((type *)((char *)(ptr) - offsetof(type, member)))
```
:::info
```container_of()```是一個以```offsetof()```為基礎，擴充為「給定成員的位址、struct 的型態，及成員的名稱，傳回此 struct 的位址」的巨集。
:::
* **list_add()**
```c
/* add the node to the first element of list (head->next)*/
void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next_node = head->next;
next_node->prev = node;
node->next = next_node;
node->prev = head;
head->next = node;
}
```
1. 創建一個指標```next_node```指向```head```的下一個節點(也就是list的第一個節點)。並且對三個節點進行連接操作。
2. 這樣可以確保新節點```node```永遠都插入在list的首位(head後)。
### hash table應用
```
typedef struct { int bits; struct hlist_head *ht; } map_t;
struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
以上是 linux 中專門為了 hash table 而使用的結構，hash table 主要是由一個 hlist_head 的動態陣列所構成，每個 entry 指向一個由 struct hlist_node 構成的非環狀 doubly linked list，此外hlist_head 的設計也省去了 list 起始端 pprev 的存放空間、在初始狀態就省去了一半的記憶體容量。
* **hlist結構示意圖**
:::info
==`pprev`為何是指標的指標?==
**reference中有詳細提到**:100: ...
`hlist_node`有兩個指標，<span style="color:red">**但是需要注意的是`pprev`是指標的指標，它指向的是前一個節點的`next`指標**</span>。 這樣的好處是即使要刪除的節點是"最前頭的節點"時，也可以通過`*pprev = next`直接修改指標的指向。
:::
* 以下是一個刪除節點的範例
```c
// deletes entry from hlist
void __hlist_del(struct hlist_node* entry)
{
struct hlist_node *next = entry->next; // step1
struct hlist_node **pprev = entry->pprev; //step2
*pprev = next; //step3
if (next)
next->pprev = pprev; //step4
}
```
1.`struct hlist_node *next = entry->next; // step1`
記錄目標節點的下一個節點 `next`。
`entry->next` 是目標節點的下一個節點指針，這樣在刪除節點後還能保持對剩餘鏈表的連接。
2. `struct hlist_node **pprev = entry->pprev; // step2`
記錄目標節點的前一個節點的指針，即 `pprev`。這是一個指向指針的指針，因為哈希鏈表的節點可能是表頭（`hlist_head`）的一部分，所以用指針指向它的上一個節點。
3. `*pprev = next; // step3`
更新前一個節點的 `next` 指針，使其指向目標節點的下一個節點 `next`，從而完成對目標節點的跳過，實現刪除。這一步驟較難理解，`pprev`其實就是指向上一個節點的`next`的指標(pointer to pointer)，故對`pprev`取值符`*pprev`得到`pre_entry->next`的概念
4. `if (next) next->pprev = pprev; // step4`
如果目標節點的下一個節點 `next` 存在，則更新它的 `pprev`，使其指向目標節點的前一個節點的 `pprev`。
### 其他hash table API的實作
我們可以藉由更多的實作，來加深對這種特殊的雙向鏈結的概念 ...
* **map_init**
```c
// initialize the map of hash table
map_t *map_init(int bits) {
map_t *map = (map_t*)malloc(sizeof(map_t));
if (!map)
return NULL;
map->bits = bits;
map->ht = (struct hlist_head *)malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
if (map->ht) {
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
} else {
free(map);
map = NULL;
}
return map;
}
```
1. 創建一個空間給`map_t`結構體使用，結構體中包含hash table的bucket數`bits`以及一個`hlist_head`指標，指向一陣列分別對應到各個bucket的首位`first`。
2. `first`初始化為空`NULL`。
* **map_add**
```c
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return;
// step 1
kn = (struct hash_key *)malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
// step 2
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first; //step 3
if (first)
first->pprev = &n->next; //step 4
h->first = n; //step 5
n->pprev = &h->first; //step 6
}
```
1. 創建`hash_key`結構體並檢查鍵是否已存在list中。
2. 計算出哈希值，從hash table中獲取對應的`hlist_head`，並保存當前list第一個節點`first`。
3. 接下來就是操作`hlist_node`(雙向鏈結)，將新節點插入list頭部。
4. 值得注意的是連接方式都是把<mark><span style="color:red">後節點的pprev指向前節點的next的地址</span></mark>。
* **map_deinit**
```c
void map_deinit(map_t *map)
{
if (!map)
return;
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
// Unlink the node from the list
if (n->pprev) {
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL;
n->pprev = NULL;
}
// Free associated data and the node itself
free(kn->data);
free(kn);
}
}
// Free the map
free(map);
}
}
```
1. 遍歷哈希表所有的桶（bucket）。
2. map->ht 是哈希表（由多個 "桶" 組成的數組）。`MAP_HASH_SIZE(map->bits)`計算哈希表的大小（也就是桶的數量），程式逐一遍歷每一個桶。head 是指向每個桶的指標。
3. 遍歷每個桶中的節點，找到對應的`hash_key`結構。
4. `n`保存當前節點並移到下一個節點`p = p->next`。
5. 檢查當前節點是否鏈接到哈希表，檢查 n->pprev 是否為 NULL。如果是 NULL，代表該節點未鏈接到哈希表，則跳過它。如果有值，表示這個節點是鏈表的一部分，需要進行後續操作將它從鏈表中刪除。
6. 將節點從鏈表中移除並釋放記憶體空間，
`next = n->next`：保存當前節點 n 的下一個節點。
`pprev = n->pprev`：<mark>獲取上一個節點的 next 指標</mark>，這是用來移除當前節點的關鍵。
`*pprev = next`：將上一個節點的 next 指標指向當前節點的下一個節點，這樣當前節點就從鏈表中移除了。
如果`next`不為`NULL`，則把`next->pprev`設置為當前節點的前一個指標`pprev`，以保持鏈表完整。
最後將`n->next`和`n->pprev`設置為`NULL`，這樣該節點就完全從鏈表中脫離了。
7. 最後釋放哈希表本身。
Sign in with Wallet
Connect another wallet