# linux2024-homework2

## Week1
### 測驗 `1`

- 排序原理

使用非遞迴的方式來實現快速排序法，運作的原理是先選定 `pivot` 節點，再將串列以此為基準，分為 `left` 和 `right` 兩個串列，使用 `begin` 和 `end` 兩個堆疊來儲存兩個串列的開頭與結尾以及分類的中心 `pivot`。

下面以圖形話來重現程式的流程:

開始有串列 [2, 0, 4, 1, 5, 3]，`left` 以及 `right` 皆為 NULL，儲存比較數值的 `L` 和 `R` 先指在頭跟尾，`piovt` 為串列第一節點的數值。

digraph structs {
    node[shape=plaintext];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    
    node[shape=box];
    struct0 [label= "2"];
    struct1 [label= "0"];
    struct2 [label= "4"];
    struct3 [label= "1"];
    struct4 [label= "5"];
    struct5 [label= "3"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> struct5
    }
    pivot -> struct0;
    L -> struct0;
    R -> struct5;
}

隨著指標 `p` 從頭遍歷到尾部，將串列分成三個部分，比 `pivot` 數值小的會被依序放入 `left` 串列，反之放入 `right` 串列，過程中呼叫 `list_add` 函式執行加入的動作，該函式將以建立好的節點放入串列的最前端，下面是三個部份的示意圖。

digraph structs{
    node[shape=plaintext];
    left [fontcolor="blue"];
    pivot [fontcolor="red"];
    right [fontcolor="blue"];
    node[shape=box]
    struct0 [label= "2"];
    struct1 [label= "0"];
    struct2 [label= "4"];
    struct3 [label= "1"];
    struct4 [label= "5"];
    struct5 [label= "3"];
    pivot -> struct0;
    left -> struct3;
    struct3 -> struct1;
    right -> struct5;
    struct5 -> struct4;
    struct4 -> struct2;
}

完成分開左右串列後，開始建立 `begin` 和 `end` 堆疊，首先加入 `left` 串列的首跟尾，再來是 `pivot`，最後是 `right`，完成堆疊建立後索引 `i` 會被加二，指在兩個堆疊最末端。

digraph structs{
    node[shape=plaintext];
    begin [fontcolor="blue"];
    end [fontcolor="blue"];
    i [fontcolor="red"];
    node[shape=box]
    struct0 [label= "2"];
    struct1 [label= "0"];
    struct2 [label= "4"];
    struct3 [label= "1"];
    struct4 [label= "2"];
    struct5 [label= "3"];
    begin -> struct3;
    struct3 -> struct0;
    struct0 -> struct5;
    end -> struct1;
    struct1 -> struct4;
    struct4 -> struct2;
    {
        rank="same";
        i -> struct2;
    }
}

當索引 `i` 大於零時，`while` 迴圈條件成立，將 `begin[i]` 和 `end[i]` 分別指派給 `L` 和 `R`， `pivot` 初始化為 `L` (數值為 3 的節點)，再次進行分開左右串列以及進行堆疊的動作。

digraph structs{
    node[shape=plaintext];
    left [fontcolor="blue"];
    pivot [fontcolor="red"];
    right [fontcolor="blue"];
    node[shape=box]
    struct2 [label= "4"];
    struct3 [label= "NULL"]
    struct4 [label= "5"];
    struct5 [label= "3"];
    pivot -> struct5;
    left -> struct3;
    right -> struct2;
    struct2 -> struct4;
}

`begin` 和 `end` 堆疊在索引 `i` 的位置會被新進數值覆蓋(以紅字表示)，索引 `i` 再次加二:

digraph structs{
    node[shape=plaintext];
    begin [fontcolor="blue"];
    end [fontcolor="blue"];
    i [fontcolor="red"];
    node[shape=box]
    struct0 [label= "2"];
    struct1 [label= "0"];
    struct2 [label= "NULL"][fontcolor="red"];
    struct3 [label= "1"];
    struct4 [label= "2"];
    struct5 [label= "NULL"][fontcolor="red"];
    struct6 [label= "3"];
    struct7 [label= "3"];
    struct8 [label= "4"];
    struct9 [label= "5"];
    begin -> struct3;
    struct3 -> struct0;
    struct0 -> struct5;
    struct5 -> struct6;
    struct6 -> struct8;
    end -> struct1;
    struct1 -> struct4;
    struct4 -> struct2;
    struct2 -> struct7;
    struct7 -> struct9;
    {
        rank="same";
        i -> struct9;
    }
}

因為現在索引 i 所指的兩個數值(`begin[i]`=4) 和 (`end[i]`=5)，仍然不相等，所以還要進行下一輪比較，重複上面分割後為堆疊插入新值兩步驟，當下一輪比較結束時`begin` 和 `end` 的模樣為下面的樣式:

digraph structs{
    node[shape=plaintext];
    begin [fontcolor="blue"];
    end [fontcolor="blue"];
    i [fontcolor="red"];
    node[shape=box]
    struct0 [label= "2"];
    struct1 [label= "0"];
    struct2 [label= "NULL"];
    struct3 [label= "1"];
    struct4 [label= "2"];
    struct5 [label= "NULL"];
    struct6 [label= "3"];
    struct7 [label= "3"];
    struct8 [label= "NULL"][fontcolor="red"];
    struct9 [label= "NULL"][fontcolor="red"];
    struct10 [label= "4"];
    struct11 [label= "4"];
    struct12 [label= "5"];
    struct13 [label= "5"];
    begin -> struct3;
    struct3 -> struct0;
    struct0 -> struct5;
    struct5 -> struct6;
    struct6 -> struct8;
    struct8 -> struct10;
    struct10 -> struct12;
    end -> struct1;
    struct1 -> struct4;
    struct4 -> struct2;
    struct2 -> struct7;
    struct7 -> struct9;
    struct9 -> struct11;
    struct11 -> struct13;
    {
        rank="same";
        i -> struct13;
    }
}

此時索引 `i` 所指的兩個數值(`begin[i]`=5) 和 (`end[i]`=5)相等，不滿足 `if` 條件，所以進行 `else` 的動作，如果 `L` 不為空的時候，將 `L` 的值，也就`begin[i]` 加入串列 `reslut`，並將索引 `i` 減一，重複動作值到碰到不相等的時候(`begin[i] != end[i]`)。

當索引 `i` 扣到小於 0 時，`while` 條件不成立跳離，將 `result` 指派給 `list`，因為是使用間接指標，所以可以直接影響原本的值。

digraph structs {
    node[shape=plaintext];
    List [fontcolor="blue"];
    node[shape=box];
    struct0 [label= "0"];
    struct1 [label= "1"];
    struct2 [label= "2"];
    struct3 [label= "3"];
    struct4 [label= "4"];
    struct5 [label= "5"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> struct5
    }

}

- 效能評估及改進

使用 `clock()` 方法來計算中央處理器時脈時間，除以 `CLOCKS_PER_SEC` 得到程式執行花費時間，原本的程式執行效能結果為:

Size: 10, Execution time: 0.000005 seconds, Cpu clock time: 5
Size: 100, Execution time: 0.000038 seconds, Cpu clock time: 38
Size: 1000, Execution time: 0.000561 seconds, Cpu clock time: 561
Size: 10000, Execution time: 0.044383 seconds, Cpu clock time: 44383
Size: 100000, Execution time: 5.653967 seconds, Cpu clock time: 5653967

改進的部分認為可以避免每次都給 `pivot` 從最左邊開始選擇，可以避免整個串列都要走一遍的最糟狀況。

### 測驗 `2`

總共有四個檔案:
- `sort_impl.h` 包裝 Timsort 在內的排序操作介面
- `main.c` 用來測試 Timsort 的鏈結串列程式碼
- `timsort.c` 實作 Timsort，刻意不額外配置記憶體空間
- `list.h` 引入 Linux 核心原始程式碼的鏈結串列實作

在檔案 `sort_impl.h` 中定義一個名為 `list_cmp_func_t` 的函式指標類型，該函式指標類型可以指向一個具有特定格式的函式，這個函式接受三個參數，參數代表了比較列表元素所需的資料以及兩個要比較的列表元素。函式該返回一個整數值，表示比較結果，程式段落如下:

typedef int (*list_cmp_func_t)(void *,
                               const struct list_head *,
                               const struct list_head *);

在 `main.c` 程式中使用 `create_sample` 函式為以配置空間的 `samples` 創造 `nums` 個節點的資料，並將其複製兩份 `testdata_head` 和 `warmdata_head` 分別對其使用 `timsort` 函式排序，使用 `check_list` 函式確認是否有按升序且是預期的順序排序。

檔案 `timsort.c` 定義 Timsort 的實作，首先使用 find_run 函式將鏈結串列切開，接著呼叫 merge_collapse 函式，將 run 合併直到輸入資料完畢，最後使用 `merge_force_collapse` 合併到 `skt_size` 小於 3，如果只剩下一個 run 就呼叫 `build_prev_link` 函式建立往前的連結，剩下兩個 run 就使用 `merge_final` 函式將其合併。

---

下面以圖形話來重現程式的流程，同時再次作答測驗:

開始有串列 [0, 2, 5, 4, 1, 3]，這個串列同時進行 run 的切割與合併的動作:

digraph structs {
    node[shape=plaintext];
    head [fontcolor="blue"];
    tail [fontcolor="blue"];
    
    node[shape=box];
    struct0 [label= "0"];
    struct1 [label= "2"];
    struct2 [label= "5"];
    struct3 [label= "4"];
    struct4 [label= "1"];
    struct5 [label= "3"];
    {
        rank="same";
        head -> struct0;
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> struct5         
        struct5 -> tail;
    }
   
}

首先進入 `find_run` 切割的動作，參數 list_cmp_func_t 是 compare 函式，此函式會回傳兩者數值相減後的值，判斷式會呼叫 compare 判斷兩節點的大小，若是下個節點 next 小於或等於當前節點 list，則紀錄升序的片段並切割，若 next 大於當前節點 list，則要將其反轉後切割，所以再來得到的樣子是:

digraph structs {
    node[shape=plaintext];
    "result.head" [fontcolor="blue"];
    "result.next" [fontcolor="blue"];
    "" [fontcolor="blue"];
    NULL [fontcolor="red"]
    
    
    node[shape=box];
    struct0 [label= "0"];
    struct1 [label= "2"];
    struct2 [label= "4"];
    struct3 [label= "5"];
    struct4 [label= "1"];
    struct5 [label= "3"];
    {
        rank="same";
        "result.head" -> struct0;
        struct0 -> struct1;
        struct1 -> struct3;
        struct3 -> "NULL";
        "result.next" -> struct2;
        struct2 -> struct4;  
        struct4 -> struct5; 
    }
   
}

執行完 `find_run` 回到 `timesort` 函式，將回傳的 `result.head`(0, 2, 5) 值指派給 `tp` 和 `result.next`(4, 1, 3) 值指派給 `list` 後的模樣是:

digraph structs {
    node[shape=plaintext];
    
    list [fontcolor="blue"];
    "" [fontcolor="blue"];
    NULL [fontcolor="red"];
    
    node[shape=box];
    struct0 [label= "0"];
    struct1 [label= "2"];
    struct2 [label= "4"];
    struct3 [label= "5"];
    struct4 [label= "1"];
    struct5 [label= "3"];
    {
        rank="same";
        NULL -> struct0;
        struct0 -> struct1;
        struct1 -> struct3;
        struct3 -> "";
    }
    {
        rank="same";
        list -> struct2;
        struct2 -> struct4;  
        struct4 -> struct5; 
    }
   
}

接下來，因為 stk_size = 1，所以將 `tp` 傳入函式 `merge_collapse` 後沒有做任何動作就回傳，`while` 的條件式因為 `list(4, 1, 3)` 不為空，所以會繼續執行，再次執行 `find_run` ，因為當前節點數值 4 大於下一個節點數值 1，所以要反轉，結果如下:

digraph structs {
    node[shape=plaintext];
    "result.head" [fontcolor="blue"];
    "result.next" [fontcolor="blue"];
    "" [fontcolor="blue"];
    NULL [fontcolor="red"]
    
    
    node[shape=box];
    struct2 [label= "4"];
    struct4 [label= "1"];
    struct5 [label= "3"];
    {
        rank="same";
        "result.head" -> struct4;
        struct4 -> struct2;
        struct2 -> "NULL";
        "result.next" -> struct5;
    }
   
}

執行完 `find_run` 回到 `timesort` 函式，之前的 `tp`(0, 2, 5) 會放到 result.head 前面，而現在`result.head`(1, 4) 值指派給 `tp` 和 `result.next`(3) 值指派給 `list`，`tp` 的樣子如下:

digraph structs {
    node[shape=plaintext];
    NULL [fontcolor="red"];
    
    node[shape=box];
    struct0 [label= "0, 2, 5"];
    struct1 [label= "1,4"];
    {
        rank="same";
        NULL -> struct0;
        struct0 -> struct1;
    }
   
}

stk_size 加一現在值是 2，再將 `tp` 傳入函式 `merge_collapse`，但是因為 run_size(tp->prev)=3 小於 run_size(tp)=2，所以直接跳離函式，回到 timsort 函式，list(3) 再進入 find_run，結果如下:

digraph structs {
    node[shape=plaintext];
    "result.head" [fontcolor="blue"];
    "result.next" [fontcolor="blue"];
    "" [fontcolor="blue"];
    NULL [fontcolor="red"]
    
    
    node[shape=box];
    struct5 [label= "3"];
    {
        rank="same";
        "result.head" -> struct5;
        "result.next" -> "NULL";
    }
   
}

回到 timsort 函式，list 指派為空，stk_size 加一值為 3，將之前的 tp 接到 result.head 前面， tp 現在節點指派為現在的 result.head(3)，現在 tp 總共有三個節點((0, 2, 5), (1, 4), (3))。

將 `tp` 傳入函式 `merge_collapse`，滿足 `(n >= 3 && run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp))`，呼叫 `merge_at`，其中他會呼叫 `merge` 兩兩比較，將小的點先放入鏈表當中，跳離後對於 stk_size 減一值為2。

函式 `merge` 中 AAAA 填入 &head， BBBB 填入 &a->next，而 CCCC 填入 &b->next，函式，最後回傳結果會是 (1, 3, 4)。

static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)
{
    struct list_head *head;
    struct list_head **tail = &head; //AAAA

    for (;;) {
        /* if equal, take 'a' -- important for sort stability */
        if (cmp(priv, a, b) <= 0) { 
            // 回傳 a->val - b->val，如果小於等於零，表示節點 b 數值較大 
            *tail = a;
            tail = &a->next; // BBBB
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = &b->next; // CCCC
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

完成這次的合併後， tp 剩下兩個節點 ((0, 2, 5),(1, 3, 4))，因為如果剩下的節點大於 1 就需要做最後的合併 `merge_final`，所以這裡的 `FFFF` 答案填入 1。

if (stk_size <= 1) {
    build_prev_link(head, head, stk0);
    return;
}
merge_final(priv, cmp, head, stk1, stk0);

現在的stk_size = 2，所以是要進入 `merge_final`，一樣兩兩相比後加入鏈表，最後呼叫 `build_prev_link` 將單向鏈表完善成雙向的，其中 DDDD 填入 `tail->next`，而 EEEE 填入 `head->prev`。

static void build_prev_link(struct list_head *head,
                            struct list_head *tail,
                            struct list_head *list)
{
    tail->next = list; //tail-list
    do {
        list->prev = tail;
        tail = list;
        list = list->next;
    } while (list);

    /* The final links to make a circular doubly-linked list */
    tail->next = head; // DDDD = head;
    head->prev = tail; // EEEE = tail;
}

---

- 改進方案

1. 加入 minrun 的使用
- 合併序列時，若 run 的數量等於或者略小於 2 的冪(ex:2, 4, 8, 16, 32...)，效率會最高；若略大於 2 的冪，效率就會特別低。minrun 的設計目的是讓剩餘資料在分割為 minrun 時，能夠盡可能接近 2 的冪，所以選擇 minrun 的策略是 Timsort 的關鍵。
2. 使用 Galloping mode 來合併不合規則的串列，但要判斷使用時機。

- 整合進 lab0-c
>將改進過的 Timsort 實作整合進 lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。

建立 timsort.c 和 timsort.h 兩個檔案進入 lab0-c 的目錄底下，但這是初步的完成 timsort指令，在比較後發現跟 list_sort.c 檔案的函式有所重疊，未來應該要把先前拿掉 list_cmp_fun_t 參數加回來，拿掉重疊的部分:

commit message:
>Implementation of a novel version merge sort

因為 lab0-c 中結構體 `element_t` 的 `attribute` 是 `char` 資料型態的，所以在比較的 `compare` 函式需要做更動， `strcmp` 大於 0，表示參數一較大，可以直接回傳結果作為 `compare` 函式的回傳值。

// 比較兩個串列節點的值
int tim_compare(const struct list_head *a, const struct list_head *b)
{
    if (!a || !b || a == b)
        return 0;
-    int res = list_entry(a, element_t, list)->val -
-              list_entry(b, element_t, list)->val;
+    element_t *a_ele = container_of(a, element_t, list);
+    element_t *b_ele = container_of(b, element_t, list);
+    int result = 0;
+    if (a_ele && b_ele)
+        result = strcmp(a_ele->value, b_ele->value);
-   if (priv)
-        *((int *) priv) += 1; 
    return result;
}

在 `qtest.c` 檔案中增加排序指令，並且增加 `do_timsort` 函式。

+ bool do_timsort(int argc, char *argv[]){...}
                            + ADD_COMMAND(timsort, "New version of merge sort", "")

- 測試

要在 traces 目錄下增加新的 .cmd 檔案，並且更改 scripts 目錄下的 drive.py 檔案，來執行新的命令檔案。

# Test of new version of sorting "tim sort"
option fail 0
option malloc 0
new
ih RAND 50000
time
timsort
time
free

make test 執行結果如下:

scripts/driver.py -c
---     Trace           Points
+++ TESTING trace timsort:
# Test of new version of sorting list_sort
Elapsed time = 0.115, Delta time = 0.115
Elapsed time = 0.154, Delta time = 0.038
---     timsort 5/5
---     TOTAL           5/5

完成 timsort 指令想要 commit 的時候出現以下錯誤:

timsort.c:16:24: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
    element_t *a_ele = container_of(a, element_t, list);

嘗試在前面先判斷 a 是否為空指令，排除指到空指令的情況，但還是無法，最後是在程式碼後面加上 `cppcheck-suppress nullPointer` 才能 push 成功，程式碼紀錄在 [commit cb5eddd](https://github.com/Lisa304/lab0-c/commit/cb5edddcdad1c4183d2a28d2a1f018c77c33c103)。

因為最近 github 要求要使用手機兩段式認證，導致原先的 https 連結無法使用，最後依照[Generating a new SSH key and adding it to the ssh-agent](https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent)將連結改成 SSH Key 才恢復 push 的功能。
## week2
### 測驗 `1`

preorder 是"中->左->右"， inorder 是 "左->中->右"，指要在三種排序中知道兩種，就能夠建構出獨一無二的二元樹。
- preorder 的開頭就是 root value
- 接著去 inorder 找對應的左右元素，不斷將左右當成 root，反覆做到直到再也找不到對應元素。

本程式使用 Linux 核心的 hash table 實作，當所有的 key 經過雜湊函數轉換後，會得到 index，如果都不一樣，稱此雜湊函數為 perfect function。

敘述程式運作原理，以及重新作答:

在 hlist_add_head 函式，AAAA 的答案是 h->first:

/*
hlist_add_head: 往前加節點
@n: 要加入的節點
@h: 現在的 head node
*/
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = h->first; //AAAA
    n->pprev = &h->first;
    h->first = n;
}

在 `find` 函式當中，BBBB 的答案是 &heads[hash] 和 CCCC 的答案是 list_entry:

/*
find: 使用 node 的 num 屬性找 node 的 idx 屬性
@num: 用來尋找的數值
@size: 用來跟 num 計算 hash
@heads: 現在的 head node

找不到有這個數值的 num 屬性的節點時，就會回傳 -1。
*/
static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    // int hash = (num < 0 ? -num : num) % size; // 轉成正整數的 num 對於 size 取餘數
    hlist_for_each (p, &heads[hash]) { // BBBB
        struct order_node *on = list_entry(p, struct order_node, node); // CCCC
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

在 `node_add` 函式當中，DDDD 的答案是 &heads[hash]:

/*
node_add: 新增節點到鏈表最前端
@val: 新節點的數值
@idx: 新節點的在排序中的位置，感覺未來會想要用 hash 來替代
@size: 用來跟 val 計算 hash
@heads: 現在的 head node

建立一個新的節點，並且呼叫 hlist_add_head 把新節點放到鏈表最前端
*/
static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx; 
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, &heads[hash]); //DDDD
}

---
改進程式:

1. 使用 hash 值，現在的函式當中 idx 值表示的是該數值在陣列中的位置，或許應該要換成 hash 值來運作。
2. 增加顯示 postortder 排序的函式 `tra_postorder` ，印出 postorder 排序的樣式，方便查看程式的運作。

    void tra_postorder(struct TreeNode* node){
        while(node->right){
            tra_postorder(node->right);
            break;
        }
        printf("%d ", node->val);
        while(node->left){
            tra_postorder(node->left);
            break;
        }
    }

---
### 測驗 `2`

實作遵循最近最少使用 (LRU) 快取約束的資料結構。實作四個功能: `lRUCacheCreate`、`lRUCacheFree` 、`lRUCacheGet` 和 `lRUCachePut`。

- `lRUCacheCreate` 以參數 @capacity 大小，來初始化 LRU 快取的容量。
- `lRUCacheFree` 為 LRU 快取刪除全部節點，並釋放快取的記憶體空間。
- `lRUCacheGet` 取出參數 @key 所對應的數值，如果找不到就會回傳 -1。
- `lRUCachePut` 更新或新增key，沒位置就將LRU的key刪除。

敘述程式運作原理，以及重新作答 EEEE ~ KKKK:

首先程式中會使用到兩種結構體 LRUCache 和 LRUNode，他們會使用 list_head 來串連彼此，而儲存數值的是雜湊表格，LRUCache 儲存多個 hlist_head，LRUNode 會使用 key 屬性找到自己位於哪個 hlist_head 鏈表當中。

首先呼叫 lRUCacheCreate 函式宣告一個容量為 3 的快取:

digraph {
    rankdir=LR;
    node[shape=record];    
    subgraph cluster_4 {
        dhlist_head [label="dhead | {<prev>prev | <next>next}"]; 
        subgraph cluster_5{
            hash0 [label=" hhead[0]", color=lightgrey];
            hash1 [label=" hhead[1]", color=lightgrey];
            hash2 [label=" hhead[2]", color=lightgrey];
        }
        label="LRUCache"
    }   
}

使用 `lRUCachePut(obj, 1, 1)` 將節點 (key=1, value=1) 放入快取當中，JJJJ 答案是 node，KKKK 答案是 &c->link:

/*
lRUCachePut: 更新或新增key，沒位置就LRU的key刪除。
@obj: 指向快取的指標
@key: 要放入的 key
@value: 要放入的 key 的對應值

如果該 @key 存在，則更新該 @key 的值。使用 list_move
將節點移到最前面，表示最近才使用過。
否則，將鍵值對新增至快取。如果 @key 的數量超過此快取的
容量(@obj->capacity)，則逐出最近最少使用的鍵。
*/
void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *cache = NULL;
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *c = list_entry(pos, LRUNode, node); // JJJJ
        if (c->key == key) {
            list_move(&c->link, &obj->dhead); // KKKK 把節點移到最前面，表示最新被使用的
            cache = c;
        }
    }

    if (!cache) {
        if (obj->count == obj->capacity) { // 快取已經滿了，把放在最後的節點刪除並釋放
            cache = list_last_entry(&obj->dhead, LRUNode, link);
            list_move(&cache->link, &obj->dhead); // 把最後一個節點移到最前面
            hlist_del(&cache->node); // 刪除存著 hlist 節點的值
            hlist_add_head(&cache->node, &obj->hhead[hash]); // hlist 加到頭
        } else { 
            // 沒有滿，所以就直接加入節點，加在 hash 表上的第 key % obj->capacity 的 hlist
            cache = malloc(sizeof(LRUNode));
            hlist_add_head(&cache->node, &obj->hhead[hash]);
            list_add(&cache->link, &obj->dhead);
            obj->count++; // 代表在快取裡的資料個數增加一個
        }
        cache->key = key;
    }
    cache->value = value; // 更新值
}

下面是圖示，因為 key = 1，所以 hash 為 1%3 = 1，這個新的 LRUNode 將會放到 hhead[1] 鏈表當中:

digraph G {
    rankdir=LR;
    node[shape=record];    
    subgraph cluster_0 {
        dhlist_head [label="dhead | {<prev>prev | <next>next}"]; 
        subgraph cluster_3{
            hash0 [label=" hhead[0]", color=lightgrey];
            hash1 [label=" hhead[1]", color=lightgrey];
            hash2 [label=" hhead[2]", color=lightgrey];
        }
        label="LRUCache"
    }   
    subgraph cluster_1 {
        node [shape=record];
        link1 [label="link | {<prev>prev | <next>next} "];
        node1 [label="node | {<prev>pprev | <next>next} "];
        label="LRUNode 1"
    }
    null [label=NULL, shape="plaintext", color = red]
    
    hash1 -> node1
    link1:next -> null [color = red]    
    node1: prev -> hash1
    dhlist_head:next -> link1:prev [color = red]
}

我們在執行一次 `lRUCachePut(obj, 2, 2)` 方便下面的功能實作展示，因為 key = 2，所以 hash 為 2%3 = 2，這個新的 LRUNode 將會放到 hhead[2] 鏈表當中:

digraph G {
    rankdir=LR;
    node[shape=record];    
    subgraph cluster_0 {
        dhlist_head [label="dhead | {<prev>prev | <next>next}"]; 
        subgraph cluster_3{
            hash0 [label=" hhead[0]", color=lightgrey];
            hash1 [label=" hhead[1]", color=lightgrey];
            hash2 [label=" hhead[2]", color=lightgrey];
        }
        label="LRUCache"
    }   
    subgraph cluster_1 {
        node [shape=record];
        hlink1 [label="link | {<prev>prev | <next>next} "];
        node1 [label="node | {<prev>pprev | <next>next} "];
        label="LRUNode 1"
    }
    subgraph cluster_2 {
        node [shape=record];
        hlink2 [label="link | {<prev>prev | <next>next} "];
        node2 [label="node | {<prev>pprev | <next>next} "];
        label="LRUNode 2"
    }
    null [label=NULL, shape="plaintext"]
    
    hash1 -> node1
    hlink1: next -> hlink2:prev[color = red]
    node1: prev -> hash1
    dhlist_head:next -> hlink1:prev [color = red]
    hash2 -> node2
    hlink2:next -> null [color = red]
    node2: prev -> hash2
}

此時如果想要取用 key 值為 2 的資料的時候，首先會去快取查詢是否有這 key 值，我們會呼叫函式 `lRUCacheGet`，HHHH 答案是 node，IIII 答案是 &cache->link:

/*
lRUCacheGet: 查詢 key 的數值
@obj: 指向快取的指標
@key: 想要查詢數值的 key

如果鍵存在則傳回鍵的值，否則回傳-1。
*/
int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, node); // HHHH
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead); // IIII
            return cache->value;
        }
    }
    return -1;
}

想要查詢值要去雜湊表查詢，所以在 `list_entry` 要傳入參數是資料型別為 hlist_node 的 `node`，而因為被使用者查詢過，代表最近有使用過，所以要將此節點往前移動，呼叫 `list_move` 函式執行，而儲存節點關連的是 list_head 資料型別，所以傳入參數應該要是 `link`，而此函式要求的參數型別為指標，所以要使用地址運算子 &cache->link，下方是執行 `lRUCacheGet(obj, 1)`後的樣子，可以看到點的鏈結順序已經產生變化 (dhead->LRUNode2->LRUCode1):

digraph G {
    rankdir=LR;
    node[shape=record];    
    subgraph cluster_0 {
        dhlist_head [label="dhead | {<prev>prev | <next>next}"]; 
        subgraph cluster_3{
            hash0 [label=" hhead[0]", color=lightgrey];
            hash1 [label=" hhead[1]", color=lightgrey];
            hash2 [label=" hhead[2]", color=lightgrey];
        }
        label="LRUCache"
    }   
    subgraph cluster_1 {
        hlink1 [label="link | {<prev>prev | <next>next} "];
        node1 [label="node | {<prev>pprev | <next>next} "];
        label="LRUNode 1"
    }
    subgraph cluster_2 {
        hlink2 [label="link | {<prev>prev | <next>next} "];
        node2 [label="node | {<prev>pprev | <next>next} "];
        label="LRUNode 2"
    }
    null [label=NULL,shape="plaintext"]
    
    
    dhlist_head:next -> hlink2:prev [color = red]
    hlink2: next -> hlink1:prev[color = red]
    hlink1: next -> null [color = red]
    
    hash1 -> node1    
    node1: prev -> hash1   
    hash2 -> node2
    node2: prev -> hash2 
}

如果呼叫 `lRUCachePut` 函式時，發現快取已經被放滿，那會將鏈表最末端的節點刪除，進行刪除時會呼叫 `hlist_del` 函式，這裡 EEEE 作答為 `next->pprev`，而`pprev` 間接指標，所存放的是前一個節點的 `next` 指標，間接指標的使用解決了刪除 head 節點時的特例。

/*
hlist_del: 刪除節點
@n: 用於指向目標刪除節點的指標

刪除指標 @n 所指向的節點
*/
void hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;
    if (next)
        next->pprev = pprev; //EEEE
}

當實驗完成後，要釋放記憶體空間，呼叫函式 `lRUCacheFree`，這裡 GGGG 的答案是 &cache->link，因為要刪除節點，所以是要取出 list_head 屬性的變數 link，而 `list_del` 函式要求的參數型態為指標，所以要加上地址運算子(&):

/*
lRUCacheFree: 為 LRU 快取刪除全部節點，並釋放快取的記憶體空間
@obj: 指向快取的指標

使用 list_for_each_safe 允許刪除，在遍歷時的當下節點指標名稱為 pos，
使用 pos 傳入 list_entry 找到 LRUNode 節點，刪除其屬性 link 後，釋放其記憶體。
*/
void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *nex;
    list_for_each_safe (pos, nex, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, link); // FFFF
        list_del(&cache->link); // GGGG
        free(cache);
    }
    free(obj);
}

### 測驗 `3`
>此程式實作 64 bit 架構的記憶體是如何找尋位址中存放的數值，第 n 個標記為 1 的位元位置。

重新作答以及敘述程式運作原理，從最外層的程式往內部運作說明:

**find_nth_bit**

首先，這是模擬 64 位元的 Linux kernel，將 BITS_PER_LONG 定義為 64，想要尋找第 n 個標記為 1 的位元位置，會呼叫函式 `find_nth_bit`，傳入的三個參數分別是開始進行搜尋的地址 @addr、要搜尋的範圍 @size 以及想要找到為 1 位元的第 @n 個。

當 @size 小於 @n 時，就像如果設定 @n = 5 和 @size = 1，那麼搜尋範圍只有一個位元，不管該位元是否為 1，在 @size 的範圍內也一定找不到第 5 個為 1 的位元，函式會值接回傳 @size。

如果 @size 大於 @n 時，函式呼叫 `small_const_nbits(@size)` 巨集，巨集會檢查三個條件，第一個檢查參數是否為編譯時常數，寫法很特殊，使用到 `__builtin_constant_p` 一個內建的 GCC 函數，如果不能確定是編譯時常數回傳 0，否則回傳 1。第二個檢查是確認 @size 是在 64 以下，最後確認 @size 是否為正數。如果以上三個條件都通過，表示想要檢查的範圍是在一個 word 以內，函式會使用巨集 `GENMASK` 清空 @addr 從 @size-1 到 0 的以外的部分，如果清空後不為 0，則呼叫 `fns`，清空後為零則回傳 @size 表示找不到。

/*
GENMASK(h, l): 產生一個位元掩碼，其中位元 @h 到位 @l 之間的位元被設定為 1，其他位元被清除。
@h: 開始保留為 1 的位置
@l: 結束保留為 1 的位置

@l = 2，((~0) - (1 << (2)) + 1) = -4 = ...1111 1111 1111 1100
@h = 4，(~0UL >> (BITS_PER_LONG - 1 - (4))) = -1 >> 59 = 0000... 0001 1111 
*/
#define GENMASK(h, l) \
    (((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

如果函式呼叫 `small_const_nbits(@size)` 巨集結果為 false 的時候，`find_nth_bit` 函式回傳 `FIND_NTH_BIT(addr[idx], size, n)`。

**fns**

先討論第二種情況，也就是 `small_const_nbits(@size)` 巨集結果為 ture，並且清空後的地址不為零，進入 `fns` 的狀況。

`fns` 函式會傳入兩個參數，第一個參數 @word 代表要進行尋找的 word，也是剛才被清空後的地址，而第二個參數跟前面，是想要找到為 1 位元的第 @n 個。

當 @word 地址不為零的時候，呼叫 `__ffs(@word)` 巨集，這裡的 AAAA 作答為 0xffffffff，如果 @word 是 0000 1000，函式回傳 3 代表最低的有 1 位元是第四位。

/* 
__ffs: find first bit in word. 用於查找給定的 64 位無符號整數中的最低位元。
@word: The word to search 

Undefined if no bit exists, so code should check against 0 first.
一個 f 代表 4 個 1，所以 16 三個 f，32 該要有 8 個 f。
*/
static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;

#if BITS_PER_LONG == 64
    if ((word & 0xffffffff) == 0) { // AAAA
    // 檢查低 32 位是否全為 0，是的話就要將 word 右移 32 位
        num += 32;
        word >>= 32;
    }
#endif
    if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
    if ((word & 0x1) == 0)
        num += 1;
    return num;
}

當 `__ffs` 完成後，`fns` 函式會檢查 n 是否為零，如果為零代表已經找到第 @n 個 1 值接回傳，不是的話就就 @n 減一並且呼叫 `__clear_bit` 巨集，將剛才找到的 1 給清除，這裡 BBBB 的答案是 ~mask，要使用 ~ 運算子將呼叫 `BIT_MASK` 巨集產生的遮罩做反轉，達到清空特定位元的效果。

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    /*
    BIT_MASK: 用於生成位元 nr 所對應的遮罩
    @nr: 生成只有在第 @nr 個位置會為 1 的數值

    會變成 2 的 @nr % 64 次方，如果 @nr = 2 => 0000 0100
    生成位元遮罩的意義在於方便地進行位元操作
    */
    unsigned long mask = BIT_MASK(nr);
    
    // BIT_WORD 用於計算 @nr 在位圖中對應的字（word）索引
    // p 是把地址在加上偏差值
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

    *p &= ~mask; // BBBB
}

在最後如果 `fns` 找不到 1 位元的話就會回傳 `BITS_PER_LONG` 表示找不到。

**FIND_NTH_BIT**

第三種情況，也就是 `small_const_nbits(@size)` 巨集結果為 false，`find_nth_bit` 函式回傳 `FIND_NTH_BIT(addr[idx], size, n)`的狀況，這裡作答 CCCC = %。

/*
FIND_NTH_BIT: 找到從左到右數第 n 個為 1 的位置
@FETCH: 一個將被替換的表達式
@size: 要被搜尋的最大數量位元數
@num: 從0開始計數，指定要找第 n 個為 1 

*/
#define FIND_NTH_BIT(FETCH, size, num)                          \
    ({                                                          \
        unsigned long sz = (size), nr = (num), idx, w, tmp;     \
                                                                \
        for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
            if (idx * BITS_PER_LONG + nr >= sz)                 \
                goto out;                                       \
                                                                \
            tmp = (FETCH);                                      \
            w = hweight_long(tmp);                              \
            if (w > nr)                                         \
                goto found;                                     \
                                                                \
            nr -= w;                                            \
        }                                                       \
                                                                \
        if (sz % BITS_PER_LONG)                                                                  
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
    found:                                                      \
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \
    out:                                                        \
        sz;                                                     \
    })

函式中呼叫 `hweight_long(tmp)` 來位 64 位元的參數計算當中含有的 1 位元個數，最底層的原理是使用下面的 `__const_hweight8` 巨集來達成的:

/*
__const_hweight8: 用來計算一個 8 位數字中包含的位元 1 的個數
@w: pointer to the previous node in the list

(w) & (1ULL << n): 這個表達式將 w 中的第 n 位與 1 做按位與運算，以檢查該位是否為 1
(1ULL << 0): << 是左移位運算符，這部分代表將 1 左移 0 位，也就是 1
如果表達式的值為 0，則 !! 將其轉換為 0；如果表達式的值為非零，則 !! 將其轉換為 1

假設現在 w = 5，其二進為表示是 0000 0101，經過此巨集結果為 2
*/
#define __const_hweight8(w)                                              \
    ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
                     (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
                     (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
                     (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))