# 2025q1 Homework1 (lab0)

contributed by < `qianzsh` >

{%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
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           
Model name:                      Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
Stepping:                        
CPU MHz:                         
CPU max MHz:                     4600.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6399.96
Virtualization:                  
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB 
L3 cache:                        12 MiB 
NUMA node0 CPU(s):               0-11

## 針對佇列操作的程式碼實作

### q_free
一開始程式碼為以下

void q_free(struct list_head *head)
{
    struct list_head *temp;

    while (head) {
        temp = head->next;
        free(head);
        head = temp;
    }
}

後來發現自己對佇列的理解有誤。起初，以為每個節點都是 list_head 結構體，但實際上只有佇列的頭部是 `list_head`，其餘節點均為 element_t 結構體，因此，在釋放記憶體時，不僅要釋放佇列頭部，還必須釋放各節點內部指標所指向的記憶體。

void q_free(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *current = head->next, *next;

    while (current != head) {
        next = current->next;
        element_t *entry = list_entry(current, element_t, list);
        free(entry->value);
        free(entry);
        current = next;
    }
    free(head);
}

### q_delete_mid
使用類似快慢指標定位中間節點，在自己手動跑第二個測資 `./qtest -f traces/trace-02-ops.cmd` 後發現有記憶體洩漏以及節點被錯誤刪除的問題，最後透過更改變數初始值以及釋放結構體中 value 所指向的記憶體來解決。

### q_reverse
我一開始不確定鏈結是否為循環結構，使用 `list_last_entry` 定位最後一個 element_t 再從尾端往前逐一遍歷，針對每個節點的 `next` 和 `prev` 指標進行交換。

element_t *last = list_last_entry(head, element_t, list);
    head->next = &last->list;  

後來回去看[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)找到以下這張圖
從圖片可以發現鏈結是頭尾相連的，所以除了對 `head->next` 做設定以外還需要對 `head->prev` 做設定。

### q_reverseK
首先閱讀[LeetCode 25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/description/)來理解題意，
## REFERENCE

- [共筆示範](https://hackmd.io/@sysprog/linux2025-sample-lab0)
- [2024 homework1 開發紀錄](https://hackmd.io/@sysprog/linux2024-homework1)