#2025q1 Homework2 (quiz1+2)
contributed by < Yuyuan1110 >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.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):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                GenuineIntel
  Model name:             12th Gen Intel(R) Core(TM) i5-1240P
    CPU family:           6
    Model:                154
    Thread(s) per core:   2
    Core(s) per socket:   12
    Socket(s):            1
    Stepping:             3
    CPU(s) scaling MHz:   30%
    CPU max MHz:          4400.0000
    CPU min MHz:          400.0000
    BogoMIPS:             4224.00
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    448 KiB (12 instances)
  L1i:                    640 KiB (12 instances)
  L2:                     9 MiB (6 instances)
  L3:                     12 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-15

## 第一週測驗題
### [測驗題1](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-1)

#### 補完 `list_insert_before` 函式

list_insert_before(list_t *l, list_item_t *before, list_item_t *item){
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    item->next = before;
}

#### 程式碼運作原理
函式定義是將一個新元素插入到陣列中的指定元素之前。
可以看到函式內宣告了一個指向 `list_item_t` 類型的指標的間接指標 `p`，所以 for 迴圈當中的第一個條件應該要放入一個 `list_item_t` 類型的指標的地址值作為 for 迴圈的起始值。
當 `p` 中的值不等於 `before` 的時候條件成立，繼續走訪。
更新 `p` 中的 `list_item_t` 的指標為下個節點的指標位置。

#### 在現有的程式碼基礎上，撰寫合併排序操作
[完整程式碼](https://github.com/Yuyuan1110/linux-kernel-course-assignment/blob/master/week2/merge.h)
使用間接指標可以簡化當 `curr1 = NULL` 時的判斷，未使用間接指標時，會需要一個變數 `prev` 儲存 `curr1` 的最後一個元素，將 `prev->next` 指向 list2 剩餘的元素。

void merge(struct list_t *list1, struct list_t *list2){
    struct list_item_t **curr1 = &list1->head;
    struct list_item_t *curr2 = list2->head;
    while(*curr1 && curr2){    
        if((*curr1)->value > curr2->value){
            temp = curr2->next;
            list_insert_before(list1, *curr1, curr2);
            if(*curr1 == list1->head){
                list1->head = curr2;
            }
            curr2 = temp;
        }else{
            curr1 = &((*curr1)->next);
        }
    }
    *curr1 = curr2;
    list2->head = NULL;
}

#### 思考
Linux Kernel 風格的 linked list 的 header 是否可以當作一個指向第一個元素的指標的指標?

### [測驗題2](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-2)
#### 補完程式碼

while ((*pred_ptr)->r)
    pred_ptr = &(*pred_ptr)->r;

### [測驗題3](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3)
#### 補完程式碼

static void rebuild_list_link(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *prev;
    prev = head;
    node = head->next;
    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    head->prev=prev;/* GGGG */
}

quick_sort(list_head *list){
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    struct list_head *begin[max_level];
    struct list_head *result = NULL, *left = NULL, *right = NULL;
    begin[0] = list->next;
    list->prev->next = NULL;
    while (i >= 0) {
        struct list_head *L = begin[i], *R = list_tail(begin[i]);
        if (L != R) {
            struct list_head *pivot = L;
            value = list_entry(pivot,node_t,list)->value;/* HHHH */
            struct list_head *p = pivot->next;
            pivot->next = NULL; /* break the list */

            while (p) {
                struct list_head *n = p;
                p = p->next;
                int n_value = list_entry(n,node_t,list)->value;/* IIII */
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

            begin[i] = left;
            begin[i + 1] = pivot;/* JJJJ */
            begin[i + 2] = right;/* KKKK */
            left = right = NULL;
            i += 2;
        } else {
            if (L) {
                L->next = result;
                result = L;
            }
            i--;
        }
    }
    list->next = result;
    rebuild_list_link(list);
}