# 【Linux】Linked List 筆記
> 資料整理 Corn

## 議題
* 偵測環狀結構
* 排序問題確保空間複雜度為 $O(1)$
* Traverse

## Linked List 在 Linux 核心程式碼
在 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 為 Linked List 中 以 **circular doubly-linked list ( 雙向環狀鏈結串列 )** 進行實作，只要在自定義的資料結構中加入 `struct list_head` 便可以透過Linux List 的 API 進行操作。如下圖所示，也就是將其**嵌入**自定義的資料結構。

## Linux核心原始程式碼巨集 `container_of` & `offsetof`
[【Linux】Linux核心原始程式碼巨集 container_of & offsetof](/CYV1UFMNRJ6v3FeKZrxF_g)

## Circular Doubly-Linked List
環狀鏈結串列 (circular Doubly-linked list) 為 linux kernel 中實現 `list` 方式，包含了以下特性
* `head` 到 `tail` 的時間複雜度從 $O(n)$ 到 $O(1)$
* `node` 具有上個節點與下個節點的特性
* 任何節點都可以為開始位置

圖解如下:

- [ ] `list_head` 結構體

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

digraph list_head {
    rankdir=LR;
    node[shape=record, style=bold];
    head [label="{<prev>prev|<next>next}"];
}

- [ ] 自定義結構體嵌入 `list_head`
自定義的結構體 ( container struct ) 被稱作 entry，
我們可以使用 `list_entry` 來求得自定義結構體的起始位址。

digraph list{
    rankdir=LR;
    node[shape=record, style=bold];
    subgraph cluster_0{
        node [shape=record];
        value [label="{value}"];
        head [label="{<prev>prev|<next>next}"];
        style=bold;
        label=my_data
    }
    
}

- [ ] `LIST_HEAD` - Declare list head and initialize it

#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

digraph list_init {
    rankdir=LR;
    node[shape=record];
    style=bold
    node [shape=record];
    head [label="{<left>prev|<right>next}", style="bold"];
    head:right:e -> head:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}

- [ ] `list_entry` - Calculate address of entry that contains list node
`list_entry` 就是 `container_of` 的封裝而已喔!
`list_first_entry`為取得在`head->next`的自定義結構體的起始位置，也就是第一個`node`
`list_first_last`為取得在`head->prev`的自定義結構體的起始位置，也就是最後一個`node`

#define list_entry(node, type, member) container_of(node, type, member)

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

#define list_last_entry(head, type, member) \
    list_entry((head)->prev, type, member)

- [ ] `list_for_each` iterate over list nodes
尋訪整個list，但不能對`node` 與 `head` 進行修改，否則會造成未定義！

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

digraph ele_list {
    rankdir=LR;
    node[shape=record];
    
    head [label="head"]
    nnode [label="node"]
    head:bottom:e -> e1:top:w
    nnode:bottom:e -> e1:top:w[arrowhead=normal, arrowtail=normal, style=dashed]
    
    e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
    e2 [label="cat|{<left>prev|<right>next}", style="bold"];
    e3 [label="...", style="bold"];
    e4 [label="eat|{<left>prev|<right>next}", style="bold"];
    e5 [label="fat|{<left>prev|<right>next}", style="bold"];
    
    e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
    e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
    e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
    e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
    e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}

- [ ] `list_for_each` iterate over list nodes and allow deletions
尋訪整個 list，但可以針對 `node` 進行操作，因為有了 `safe` 確保下一個節點的位置

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
    node = safe, safe = node->next)