# 2024q1 Homework2 (quiz1+2)
contributed by < `PochariChun `>

## Quiz 1

### Quiz 1 -1 程式碼解釋

Quiz 1 的函式是一個使用非遞迴方法實做的快速排序, 其中以自定義的結構體 node_t, 作為鏈結串列的節點, 並透過間接指標 `**list` 來操作 `node_t` 節點的內部元素:

digraph node_t {
    rankdir=LR;
    "**list" [fontcolor=red, color=red, shape=plaintext];
    "*head" [shape=plaintext];
    {
        "**list" -> "*head" [color=red];
        "*head" -> node1 [color=blue];
    }    
    subgraph cluster_0 {
        label="node_t";
        node1 [shape=record, label="long value | *next | {*left | *right}"];
    }
}

#### What is 'AAAA'?

**AAAA** 出現在 list_length 函式中, 這個函式先 **判斷** 間接指標**現在指向的點** `*left` 和**指向的點的下一個點** `(*left)->next` **是否存在**, 存在則重複執行 AAAA 這個動作. **不存在就回傳現在指向的節點位址** `*left`.

已知 `*left` 指向尾端時為 NULL, 迴圈中止. 可判斷 AAAA 這個動作是 **"透過間接指標走訪"**, 可以推斷是 [linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 中提過的間接指標指向 `next` 的走訪技術, 也就是 `AAAA = (*left)->next`.

#### What is 'BBBB'?

**BBBB** 出現在 list_length 函式中, 最後回傳的是**數字 n**, 因為 n 的初始值為 0, 加上函式名稱為計算長度, 故推斷 n 是用於計算走訪節點數量的計數器.
函式接著 **判斷** 間接指標 **現在指向的點** `*left` **是否存在**, 存在則重複執行計數器加一, 和 BBBB 這個動作.
已知 `*left` 指向尾端時為 NULL, 迴圈中止. 故 BBBB 這個動作同樣是 **"透過間接指標走訪"**, 也就是 `BBBB = (*left)->next`.

#### What is 'CCCC', 'DDDD', 'EEEE'?

這三個敘述都在非遞迴快速排序的主函式中, 這個函式用兩個儲存指標的陣列 begin[ ] 和 end[ ] 作為堆疊，去儲存尚未排列好的串列, 以 stack 達到取代遞迴的方式。
begin[ ] 代表尚未排列好的串列開頭, end[ ]則代表尚未排列好的串列結尾,
一開始先假定輸入的整串連結串列是未排序的, 就將整串串列開頭放入 begin[0], 尾端節點放入 end[0]。

digraph nodet {

    begin [shape = none, label=< 
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
            <TD PORT="a0">  begin[0]</TD>
            <TD PORT="a1">  begin[1]</TD>
            <TD PORT="a2">  begin[2]</TD>
        </TR> </TABLE>>];
    end[shape = none, label=< 
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
            <TD PORT="a0">  end[0]</TD>
            <TD PORT="a1">  end[1]</TD>
            <TD PORT="a2">  end[2]</TD>
        </TR> </TABLE>>];
    n1[label = "4", fontcolor=red];
    n2[label = "1"];
    n3[label = "3"];
    n4[label = "5"];
    n5[label = "2"];
    n6[label = "7", fontcolor=green];
    "*list" [fontcolor=red,color=red];
    "**list" [fontcolor=red,color=red]; 
    {
        begin:a0->"*list"
        end:a0->n6
        n1->n2;
        n2->n3;
        n3->n4;
        n4->n5;
        n5->n6;
    }
    {
        rank="same";
        "*list" -> n1
        "**list" -> "*list"
    }
    
}

接著從 begin 和 end 兩個 **代表未排序的 stack** 之中 "**取出**" 最上方串列, 使用 **L** 和 **R** 兩個指標分別指向現在處理的串列的開頭和結尾. 也就是取出的 begin 和 end.

如果 L 不等於 R, 就根據現在未排序串列中的 pivot **分類**串列, 分別成為**數值小於 pivot 的串列, pivot ,和數值大於 pivot 的串列**.

如果 L, R 指向同個位置，就表示現在 stack 最上層的串列是已經排序完畢，可以把這個節點加入結果串列最後 (最大)的位置. 於是透過 `i--` 可以做到從 stack 中 pop 的效果,

> 取出: 並非真正意義上從 stack 陣列取出, 而是使用 L 和 R 指標分別指向這些開頭節點, 最後要將分類結果存入 stack 時, 無視 stack 最上方那筆資料, 從那個位置開始存入三個分類結果

digraph list{
    node [shape=box];
    rankdir = "LR"
    
    n1[label = "4"];
    n2[label = "1"];
    n3[label = "3"];
    n4[label = "5"];
    n5[label = "2"];
    n6[label = "7"];
    "*list" [fontcolor=red,color=red];
    "**list" [fontcolor=red,color=red];
    begin[label = "begin[0]"]
    end[label = "end[0]"]   
    value[fontcolor=orange,color=orange];
    value[label = "piviot value = 4", group = g3]
    L[fontcolor=orange,color=orange];
    R[fontcolor=orange,color=orange];
    {
        n1->n2;
        n2->n3;
        n3->n4;
        n4->n5;
        n5->n6;
    }
    {
        rank="same";
        "*list" -> n1
        "**list" -> "*list"
    }
    {
        begin->"*list"
        L->begin
        R->end
    }
    {
        rank="same";
        end->n6      
    }
    
}

確定 L 和 R 之後, 使用底下迴圈走訪 pivot 後續的節點的值, 如果比較大, 就把這個節點加入 right 連結串列之中, 沒有比較大就加入 left 連結串列,
由於是走訪, 故 `CCCC = p->next`

while (p) {
                node_t *n = p;
                p = CCCC;
                list_add(n->value > value ? &right : &left, n);
            }

digraph list{
    node [shape=box];
    rankdir = "RL"
    
    n1[label = "4"];
    n2[label = "1"];
    n3[label = "3"];
    n4[label = "5"];
    n5[label = "2"];
    n6[label = "7"];
    pivot [fontcolor=red,color=red];

    value[fontcolor=orange,color=orange];
    value[label = "piviot value = 4", group = g3]
    left[fontcolor=red,color=red];
    right[fontcolor=red,color=red];
    {
        pivot->n1;
        left->n5->n3->n2;
        right->n6->n4;
    }

}

將這個串列 **分類** 成 **"小於 pivot 的 left"**, **"pivot"**, **"大於 pivot 的 right"** 的三個串列, 將這些串列的開頭和結尾指標 **依序存入** begin 和 end 兩個 stack 的 i ~i +2 層.
故 `DDDD = list_tail(&left)`,
故 `EEEE = list_tail(&right)`,
這樣可以用 stack 模擬原本使用遞迴呼叫來實做快速排序的方式,

digraph nodet {
    rankdir = "RL";
    n1[shape = box, label = "4", fontcolor=red];
    n2[shape = box, label = "1", fontcolor=green];
    n3[shape = box, label = "3"];
    n4[shape = box, label = "5", fontcolor=green];
    n5[shape = box, label = "2", fontcolor=red];
    n6[shape = box, label = "7", fontcolor=red];
    n7[shape = box, label = "4", fontcolor=green];
    n8[shape = box, label = "1", fontcolor=green];
    n9[shape = box, label = "5", fontcolor=green]; 
    pivot [shape = box,fontcolor=red,color=red]; 
    left[shape = box,fontcolor=red,color=red];
    right[shape = box,fontcolor=red,color=red];
 
    {

        begin:a0 -> left -> n5->n3->n2;
        begin:a1 -> pivot -> n1;
        begin:a2 -> right -> n6->n4;
        end:a0 -> n8;
        end:a2 -> n9;
        end:a1 -> n7;
    }
    begin [shape = none, label=< 
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
            <TD PORT="a0">  begin[0]</TD>
            <TD PORT="a1">  begin[1]</TD>
            <TD PORT="a2">  begin[2]</TD>
        </TR> </TABLE>>];
    end[shape = none, label=< 
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
            <TD PORT="a0">  end[0]</TD>
            <TD PORT="a1">  end[1]</TD>
            <TD PORT="a2">  end[2]</TD>
        </TR> </TABLE>>];
    
}

最後可歸納出這個函式的運行原理:

- 從 begin 和 end 兩個 **代表未排序的 stack** 之中 "**取出**" 最上方串列, 將此串列開頭和結尾分別作為 L 和 R.
1. **如果 L 不等於 R**, 將這個串列 **分類** 成 **"小於 pivot"**, **"pivot"**, **"大於 pivot"** 的三個串列, 將這些串列的開頭和結尾指標 **依序存入** begin 和 end 兩個 stack .
2. **如果 L, R 指向同個位置**，就把這個 stack 的節點加入結果串列之前.

重複這兩個過程, 直到清空整個 stack, 最後回傳 result 就是由小到大排序好的結果.

### Linux 核心風格的List API 改寫

### 改進實作

### 延伸問題
> 使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，
> 提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
> 最差狀況:

### Quiz 1 -2
> a >>= 1; 意思 跟a >>1
>
a >>= 1;
a >>= 1; 是就地修改變數 a 的值，而 a >> 1 僅僅是一個右移運算的結果，不會修改 a 的值。

## Quiz 2

### Quiz 2 -1

### 延伸問題
> 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討
### Quiz 2 -2

### 延伸問題
> 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
在 Linux 核心找出 LRU 相關程式碼並探討
### Quiz 2 -3

### 延伸問題

>解釋上述程式碼的運作原理
在 Linux 核心原始程式碼找出 find_nth_bit 的應用案例，並予以解說和分析，需要涵蓋 CPU affinity 相關的原始程式碼。