---
# System prepended metadata

title: 2024q1 Homework2 (quiz1+2)
tags: [linux 2024]

---

# 2024q1 Homework2 (quiz1+2)
contributed by < [yy214123](https://github.com/yy214123) >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Address sizes:         39 bits physical, 48 bits virtual
Byte Order:            Little Endian
CPU(s):                20
On-line CPU(s) list:   0-19
Vendor ID:             GenuineIntel
Model name:            13th Gen Intel(R) Core(TM) i5-13600KF
CPU family:            6
Model:                 183
Thread(s) per core:    2
Core(s) per socket:    14
Socket(s):             1
Stepping:              1
CPU max MHz:           5100.0000
CPU min MHz:           800.0000
BogoMIPS:              6988.80 
Virtualization:        VT-x 
L1d:                   544 KiB (14 instances)
L1i:                   704 KiB (14 instances)
L2:                    20 MiB (8 instances)
L3:                    24 MiB (1 instance) 
NUMA node(s):          1
NUMA node0 CPU(s):     0-19
```
## 填寫 Google 表單時獲得的啟發
### Dangling Pointer
在 [基於 C 語言標準研究與系統程式安全議題](https://hackmd.io/@sysprog/c-std-security) 的主題(二)中討論了有關 Dangling Pointer 的議題，其中提到：**在使用指標時，安全起見應該要記得將不用的指標在 free() 後設為 NULL。** 重新審視了我在 [lab0-c](https://github.com/yy214123/lab0-c) 的程式後，發現部份函式都有釋放指標的行為，而釋放後我卻沒有將其指向 NULL，如此會有造成 Dangling Pointer 的風險。
對此我進行了以下修改:
```diff
    free(head);
+   head = NULL;
    free(new);
+   new = NULL
```
## 第一周測驗
### 測驗一
```clike
node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &((*left)->next);
    return *left;
}
int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &((*left)->next);
    }
    return n;
}
```
在這兩個函式中，我們處理的是一個鏈結串列結構，其中 node_t 是串列節點的結構定義。這些函式通過間接指標（即指向指針的指針）作為參數來操作鏈表。允許函式直接修改指向鏈表頭部的指針。

```list_tail``` 的目的是找到並回傳串列的最末節點。它透過迴圈遍歷串列，每次迭代都檢查當前節點的下一個節點是否存在。當下一個節點不存在時，當前節點即為串列的最末節點。

```list_length``` 的目的是計算串列中的節點數量。透過遍歷串列的每個節點，每遍歷一個節點就將計數器 n 增加 1。當遍歷完所有節點後，函式回傳計數器 n 的值即為串列的長度。
```clike
while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = p->next;
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = list_tail(&left);
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = list_tail(&right);

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
```
這邊花了很多時間來紙筆追蹤，一開始搞不懂他的邏輯，一直卡在 else 判別式的地方。後續仔細觀察 begin 各個索引指向的串列後，才逐漸理解整個架構的運作模式。

可將每三個 begin 索引看作一組處理單元，其中每組的中心點是一個基準值 （pivot），這個節點左側的串列包含所有小於基準值的節點，而右側則包含所有大於基準值的節點。演算法的執行流程傾向於先處理基準值右側的部分，也就是那些大於基準值的節點。對於大於基準值的每個部分，演算法繼續將其細分為更小的三元組（左、中、右），依此類推，直到只剩下單一節點。一旦某個大於基準值的部分被細分到只包含一個節點，該節點就會被加入到最終的 result 中 。
:::success
延伸問題:
1.解釋上述程式碼的運作原理，提出改進方案並予以實作。
:::
:::success
延伸問題:
2.使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
:::
#### 考慮時間複雜度
在 **worst case** 情況下，會因為 pivot 的緣故，導致快速排序的時間複雜度為 $\mathcal{O}(n^2)$，可以透過選擇更好的 pivot 來避免此問題。
**解決方法一**：以 Middle of three 挑選 pivot
```graphviz
digraph G {
    node [shape=record, height=.1];
    array [label="<f0> 4|<f1> 7|<f2> 2|<f3> 5|<f4> 9|<f5> 1|<f6> 6", style=filled, color=lightgrey];
    pivot [label="Pivot: 5", shape=box, style=filled, color=lightblue];

    start [shape=none, label=""];
    end [shape=none, label=""];

    start -> array:f0 [label="First"];
    array:f3 -> pivot [label="Middle of three\n(4, 5, 6)"];
    end -> array:f6 [label="Last"];
}
```

**解決方法二**：以 Median of Medians 挑選 pivot
```graphviz
digraph G {
    node [shape=record, height=.1];
    subgraph cluster_0 {
        label="Array";
        color=lightgrey;
        array [label="1|2|3|4|5|6|7|8|9|10|11|12|13|14|15", style=filled];
    }

    subgraph cluster_1 {
        label="Groups of 5";
        color=lightgrey;
        group1 [label="1|2|3|4|5", style=filled];
        group2 [label="6|7|8|9|10", style=filled];
        group3 [label="11|12|13|14|15", style=filled];
    }

    subgraph cluster_2 {
        label="Medians of Groups";
        color=lightgrey;
        median1 [label="3", shape=box, style=filled, color=lightblue];
        median2 [label="8", shape=box, style=filled, color=lightblue];
        median3 [label="13", shape=box, style=filled, color=lightblue];
    }

    subgraph cluster_3 {
        label="Median of Medians";
        color=lightgrey;
        pivot [label="Pivot: 8", shape=box, style=filled, color=red];
    }

    array -> group1 [label="Divide"];
    array -> group2;
    array -> group3;

    group1 -> median1 [label="Find median"];
    group2 -> median2;
    group3 -> median3;

    median1 -> pivot [label="Choose median"];
    median2 -> pivot;
    median3 -> pivot;
}

```

#### 考慮空間複雜度
原先程式碼使用了額外的 ```begin```、```end```來追蹤子串列，又使用 ```left```、```right```來存分割後的結果，能以 in-place partitioning 的角度出發去改善。
### 測驗二
:::success
延伸問題：
1.解釋上述程式碼的運作原理，提出改進方案並予以實作。
:::
在 `timsort` 函式中，第一行宣告了：
```c  
stk_size = 0;
```
接著去搜尋其定義方式：
```c    
static size_t stk_size;
```
原先不懂 size_t 為何，在 `stddef.h` 中找到了其定義：
```c
typedef __SIZE_TYPE__ size_t;
```
這點在 [C99](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 之 [6.5.3.4] 第4點也有提及。 
:::info
The value of the result is implementation-defined, and its type (an unsigned integer type)
is size_t, defined in <stddef.h> (and other headers).
:::
延伸問題中提到使用 Linux 核心風格的 List API 改寫，一開始判斷是否為 empty 的判斷式就能改進：
```diff
-   if (head == head->prev)
+   if (!head || list_empty(head) || list_is_singular(head))
        return;
```
首先是 `find_run` 這個函式，其功能為在串列中尋找連續遞增或遞減的序列（run），並根據這個序列是遞增還是遞減來相應地處理鏈表。如果序列是遞減的，函式會將其內的節點反轉，使之成為遞增序列，此處有可以改善的空間，上述反轉的操作可以搭配 `q_reverse` 來使程式碼更精簡。

以一個簡單的範例來追蹤程式碼：
```graphviz
digraph G {
    rankdir =LR
    node [shape=record];

    Node0 [label="<f0> head"];
    Node1 [label="<f0> 5"];
    Node2 [label="<f0> 2"];
    Node3 [label="<f0> 3"];
    Node4 [label="<f0> 7"];
    Node5 [label="<f0> 6"];
    Node6 [label="<f0> 1"];
    Node7 [label="<f0> head"];
    // Node0 <-> Node1
    Node0:f0 -> Node1:f0 [color="red"];
    Node1:f0 -> Node0:f0 ;

    // Node1 <-> Node2
    Node1:f0 -> Node2:f0 [color="red"];
    Node2:f0 -> Node1:f0 ;

    // Node2 <-> Node3
    Node2:f0 -> Node3:f0 [color="red"];
    Node3:f0 -> Node2:f0 ;

    // Node3 <-> Node4
    Node3:f0 -> Node4:f0 [color="red"];
    Node4:f0 -> Node3:f0 ;

    // Node4 <-> Node5
    Node4:f0 -> Node5:f0 [color="red"];
    Node5:f0 -> Node4:f0 ;

    // Node5 <-> Node6
    Node5:f0 -> Node6:f0 [color="red"];
    Node6:f0 -> Node5:f0 ;
    
    // Node6 <-> Node7
    Node6:f0 -> Node7:f0 [color="red"];
    Node7:f0 -> Node6:f0 ;
}
```
待補

:::success
延伸問題：
2.將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。
:::
> [commit ce2f8f4](https://github.com/sysprog21/lab0-c/commit/ce2f8f4888535b7e7010d4c52417b94cd4a9bc7c)

先前已完成透過 option 命令修改 sort_type 之值，根據其值選擇要使用 merge_sort 或 list_sort 進行佇列排序操作。此次更新加入 timsort 並對程式碼做了下方更動。
```diff
-   add_param("sort_type", &sort_type, "0 for merge_sort, 1 for list_sort",NULL);
+   add_param("sort_type", &sort_type, "0 for merge_sort, 1 for list_sort, 2 for timsort",NULL);
```
```diff
/* Sort elements of queue in ascending order */
extern int sort_type;
void q_sort(struct list_head *head, bool descend)
{
    switch (sort_type) {
    case 0:
        merge_sort(head);
        break;
    case 1:
        list_sort(head, cmp);
        break;
+   case 2:
+       timsort(head, cmp);
+       break;
    default:
        printf("Unknown sort type.\n");
        break;
    }

    if (descend)
        q_reverse(head);
}
```
詳細的效能評比，我將其更新於 [2024q1 Homework1 (lab0) - 嘗試將 Timsort 引入到 lab0-c](https://hackmd.io/yI-Rh8l7Q9uzWhQgBQbsnQ?view#%E5%98%97%E8%A9%A6%E5%B0%87-Timsort-%E5%BC%95%E5%85%A5%E5%88%B0-lab0-c) 中。
## 第二周測驗
[2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 `1`
:::success
解釋程式碼的運作原理。
:::
```clike
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = AAAA;
    n->pprev = &h->first;
    h->first = n;
}
```
**`AAAA` 應填入 `h->first`。**

假設目前串列中還沒有節點（不會執行 if 判別式），根據： 
```clike
static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
    h->first = NULL;
}
```
所以初始 first 會指向 NULL：
```graphviz
digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    list_head[label = "<m>hlist_head | <n>first"] 
    NULL[shape = plaintext, label = "NULL", group = list]
    list_head:n -> NULL;
}
```
現在執行第一次的 `hlist_add_head`，因 `AAAA` 填入 `h->first` 所以：
```graphviz
digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    list_head[label = "<m>hlist_head | <n>first"] 
    NULL[shape = plaintext, label = "NULL", group = list]
    list_head:n -> NULL;
}
```
```graphviz
digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
    NULL[shape = plaintext, label = "NULL", group = list]
    node_1:n -> NULL;

}
```
接著執行`n->pprev = &h->first;`
```graphviz
digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    list_head[label = "<m>hlist_head | <n>first"]
    node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];

    
    NULL[shape = plaintext, label = "NULL", group = list]

    {rank = "min" list_head}
    
    list_head -> node_1 [
        weight = 10, style = invis
    ]

    node_1:p -> list_head:n;
    node_1:n -> NULL;

}
```
最後執行 `h->first = n;`
```graphviz
digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    list_head[label = "<m>hlist_head | <n>first"]
    node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];

    
    NULL[shape = plaintext, label = "NULL", group = list]

    {rank = "min" list_head}
    
    list_head -> node_1 [
        weight = 10, style = invis
    ]
    
    list_head:n -> node_1:m;
    node_1:p -> list_head:n;
    node_1:n -> NULL;

}
```
若再次執行 `hlist_add_head` 插入 `hist_node_2` 節點，這次會執行 if 判別式部份。
`h->first->pprev` 即 `hist_node_1` 的 pprev，將其指向 `hist_node_2` 的 next。
```graphviz
digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    list_head[label = "<m>hlist_head | <n>first"]
    node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
    node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", ];

    
    NULL[shape = plaintext, label = "NULL", group = list]

    {rank = "min" list_head}
    
    list_head -> node_1 [
        weight = 10, style = invis
    ]
    
    list_head:n -> node_1:m;
    node_1:p -> node_2:n;
    node_1:n -> NULL;

}
```
接著依序執行：
```clike
n->next = h->first;
n->pprev = &h->first;
h->first = n;
```
```graphviz
digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    list_head[label = "<m>hlist_head | <n>first"]
    node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
    node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", ];

    
    NULL[shape = plaintext, label = "NULL", group = list]

    {rank = "min" list_head}
    
    list_head -> node_2 -> node_1 [
        weight = 10, style = invis
    ]
    
    list_head:n -> node_2:m;
    node_2:p -> list_head:n
    node_2:n -> node_1:m
    node_1:p -> node_2:n;
    node_1:n -> NULL;

}
```
以相同範例，Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]。
首先呼叫 `buildTree`，參數代入上方範例的 preorder 及 inorder，兩者 size 均為 5，前 3 行程式碼如下：
```clike
struct hlist_head *in_heads = malloc(5 * sizeof(*in_heads));
    for (int i = 0; i < 5; i++)
        INIT_HLIST_HEAD(&in_heads[i]);
```
```graphviz
digraph G {

    rankdir=LR;

    node[shape=record];
    nullNode [label="NULL", shape=plaintext];
    map [label="in_heads |<ht0>first |<ht1>first |<ht2>first |<ht3>first |<ht4>first"];
    map:ht0 -> nullNode;
    map:ht1 -> nullNode;
    map:ht2 -> nullNode;
    map:ht3 -> nullNode;
    map:ht4 -> nullNode;
}
```
接著是
```clike
for (int i = 0; i < inorderSize; i++)
        node_add(inorder[i], i, inorderSize, in_heads);
```

在 `node_add` 中會去計算 inorder 的各元素應放入哪格 in_heads 中：
```graphviz
digraph G {

    rankdir=LR;

    node[shape=record];
    map [label="in_heads |<ht0>first |<ht1>first |<ht2>first |<ht3>first |<ht4>first"];
    
    node[shape=none]
    null1 [label=NULL]
    null2 [label=NULL]
    null3 [label=NULL]
    null4 [label=NULL]
    null5 [label=NULL]
    
    subgraph cluster_1 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:0;val:3"
    }
    subgraph cluster_2 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:1;val:9"
    }
    subgraph cluster_3 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:2;val:20"
    }
    subgraph cluster_4 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn4 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:3;val:15"
    }
    subgraph cluster_5 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn5 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:4;val:=7"
    }
    map:ht0 -> hn3;
    hn3:prev:s -> map:ht0;
    hn3:next -> hn4;
    hn4:prev:s -> hn3:next
    hn4:next -> null1;
    
    map:ht1 -> hn5;
    hn5:prev:s ->map:ht1;
    hn5:next -> null2;
    
    map:ht2 -> hn1;
    hn1:prev:s ->map:ht2;
    hn1:next -> null3;
    
    map:ht3 -> hn2;
    hn2:prev:s ->map:ht3;
    hn2:next -> null4;
    
    map:ht4 -> null5;
    
    
}
```
起初用上方的圖去進行後續的 dfs 遞迴，發現結果與預期的有落差，重新看過程式碼後發現我 idx 的編號是依照 prorder 的元素順序，正確來說在 `INIT_HLIST_HEAD` 及 `node_add` 是以 inorder 的元素順序才對，故上方的圖片應如下修正：
```graphviz
digraph G {

    rankdir=LR;

    node[shape=record];
    map [label="in_heads |<ht0>first |<ht1>first |<ht2>first |<ht3>first |<ht4>first"];
    
    node[shape=none]
    null1 [label=NULL]
    null2 [label=NULL]
    null3 [label=NULL]
    null4 [label=NULL]
    null5 [label=NULL]
    
    subgraph cluster_1 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:1;val:3"
    }
    subgraph cluster_2 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:0;val:9"
    }
    subgraph cluster_3 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:2;val:15"
    }
    subgraph cluster_4 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn4 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:3;val:20"
    }
    subgraph cluster_5 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn5 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="idx:4;val:=7"
    }
    map:ht0 -> hn3;
    hn3:prev:s -> map:ht0;
    hn3:next -> hn4;
    hn4:prev:s -> hn3:next
    hn4:next -> null1;
    
    map:ht1 -> hn5;
    hn5:prev:s ->map:ht1;
    hn5:next -> null2;
    
    map:ht2 -> hn1;
    hn1:prev:s ->map:ht2;
    hn1:next -> null3;
    
    map:ht3 -> hn2;
    hn2:prev:s ->map:ht3;
    hn2:next -> null4;
    
    map:ht4 -> null5;
}
```
接著是 `dfs` 的部份，這邊我覺得蠻困難的，一開始對遞迴呼叫中傳入的參數運算很混亂，這邊以另一個例子來追蹤：
> preorder = [A, B, D, E, C, F, G] 
> inorder = [D, B, E, A, F, C, G]

根據建構二元數的規則，我們可以得知根節點為 `A` ，先看第一個遞迴呼叫：
```clike
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
```
* `pre_low + 1`：根節點 `A` 之左子樹其起始索引於 preorder 中的 `pre_low + 1`，即根節點 `A` 的下個位置。
* `idx - in_low`： `idx` 為 `A` 在 inorder 中的索引，經由 `idx - in_low` 可以計算出根節點 `A` 之左子樹節點總數（即 3 個）。

由上方兩點可知左子樹在 preorder 中從索引 `pre_low + 1`（即 1） 開始且長度為`idx - in_low` （即 3）。所以可以知道結束的索引位於 `pre_low + 1 + (idx - in_low) - 1`，將其化簡後可得 `pre_low + (idx - in_low)`。
```clike
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
```
先將 `pre_high - (in_high - idx - 1)` 改為 `pre_high - (in_high - idx ) + 1`，我覺得這樣解釋比較清晰。
* `in_high - idx`： `idx` 為 `A` 在 inorder 中的索引，經由 `in_high - idx` 可以計算出根節點 `A` 之右子樹節點總數（即 3 個）。

所以由 `pre_high - (in_high - idx ) + 1` 可以得知右子樹在 preorder 的起始索引（即 4）。

綜合上述可以理解為每次呼叫遞迴時會傳入左右子樹的**起始索引**及**結束索引**。
:::success
#### 撰寫完整的測試程式。
:::
目前的設想是撰寫 preorder traversal 及 inorder traversal 的遞迴程式碼，倘若由 preorder 序列及 inorder 序列所構建的 BT 是正確的，對該 BT 進行 preorder traversal 及 inorder traversal 後會與原先的序列相同。
:::success
#### 指出其中可改進之處並實作。
:::
> [commit 5b568bb](https://github.com/yy214123/M02-quiz1-2/commit/5b568bbe9b5e4b89d0b68efff54511135f19f683)
此次提交先上傳原始的程式碼。

參考教材 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)，原始程式的雜湊函數採 Division method，應可用教材所提及的 Multiplication Method 來改進。
:::warning
我對於 Multiplication Method 的 bits 部份有疑惑，不知道該如何代入什麼值。
:::

> [commit 5333c09](https://github.com/yy214123/M02-quiz1-2/commit/5333c09b2b596a4cac5c5fb2689543a657358702)
> 此次更新加入了教材中的 Multiplication Method 雜湊函數。這個版本的程式碼目前有 bug 須修正

> [commit b2d2080](https://github.com/yy214123/M02-quiz1-2/commit/b2d2080061be7c49bb8a0eaadc445cd9631aaf2f)
> 此次更新修復了原先的 bug，逐步偵錯後發現是 `INIT_HLIST_HEAD(&in_heads[i])` 這部份的迭代次數設置有誤，原先的次數是 `inorderSize `應該配合 `bits` 的設計調整，否則會出現計算後的 `hash` 值找不到對應的 bucket。

原先提及對 Multiplication Method 的 bits 部份有疑惑，目前是以下方方式撰寫，但我不清楚是否正確：
```clike
int bits =ceil(log2(size));
int hash = (num < 0 ? hash_32(-num, bits) : hash_32(num, bits));
```
如果上方是正確的，那麼這部份也還有改進空間，可參考 [第 3 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3) 測驗 `1` 提及的方法改進。
### 測驗 `2`
:::success
解釋程式碼的運作原理。
:::
```clike
void hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;
    if (next)
        EEEE = pprev;
}
```
`EEEE` 應填入 `next->pprev`。間接指標 `pprev` 會指向一個**指著自身節點的指標**，根據 if 判別條件，如果刪除的節點並非最末節點，將欲刪除節點之下一節點的 `pprev` 指向其自身。

```clike
void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, FFFF);
        list_del(GGGG);
        free(cache);
    }
    free(obj);
}
```
這邊一開始填的答案都錯，因為我只看了 `lRUCacheCreate` 的程式架構，但實際上這邊的 `INIT_LIST_HEAD` 及 `INIT_HLIST_HEAD` 還未將節點彼此串接起來，應先理解 `lRUCachePut` 的運作邏輯後才回過頭來完成此部份。

仔細研究整個程式架構後，發現這個測驗蠻有趣的，本質上是兩個獨立的結構體，一個（hlist）利用雜湊函數的方式來降低搜尋節點的成本，一個（list）用雙向環狀鍊結串列來維護 LRU 的特性，將最近使用過的節點透過 `list_move` 來調整該節點之優先權。

理解整體架構後，回過頭看 `lRUCacheFree` 就清晰許多，可以看到： 

`list_for_each_safe (pos, n, &obj->dhead)`

而 dhead 是維護 LRU 的雙向環狀鍊結串列的頭部，故 `FFFF` 應填入 `link`，而 `GGGG` 應該填入 `&cache->link`。
:::success
撰寫完整的測試程式。
:::
:::success
指出其中可改進之處並實作。
:::
雜湊函數也有改進空間，原始程式碼採 Division method，同測驗 `1` 可將其改為 Multiplication Method。
### 測驗 `3`
:::success
解釋程式碼的運作原理。
:::
一開始對 `small_const_nbits`中的`__builtin_constant_p` 感到疑惑，翻閱 [GCC 官方文件](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)及重新觀看[第 2 週課程 [34:07]](https://www.youtube.com/watch?v=WYcexo6T3UI&t=609s)後，才了解其功能。此函式會在編譯時期檢查某個表示式是否為常數。