# 2025q1 Homework1 (lab0)
contributed by < DivaGabriel >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

#### Reviewed by `kk908676`
在 `q_insert_head()` 與 `q_insert_tail()` 中，使用 `strdup()` 後應該檢查是否成功配置記憶體, 藉此避免記憶體的配置失敗

#### Reviewed by `Andrewtangtang`

##### commit 的使用
根據[作業一](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a)中對於 commit message 的使用方法，應該要對於每一次的改動詳細表達做了甚麼動作，因此在一開始一次撰寫了3、4個函式且並不是相關的函式一起去 commit 很難去詳細描述，應該針對類似功能的函式測試完後分別 commit。此外既然在 commit 發生了錯誤應該是針對錯誤的地方做查詢與修改(error message已經有寫 queue.c does not follow the consistent coding style.)，假設撰寫的程式本身沒有問題就不應該是將程式清空做 commit。

#### 開發日誌的撰寫
可以記錄如何實現的過程，例如:
> `q_delete_mid()` 這個函式目標是找到鏈結串列中中間的節點進行刪除，而我使用的是快慢指標的方法來尋找終點，這個方法是利用快指標與慢指標 traverse 速度的不同...

這樣可以讓閱讀程式碼的人可以理解快慢指標技巧實作原理進而有效閱讀程式碼。此外只附上關鍵部分程式碼即可，不用全部都貼上。

[207dee7](https://github.com/DivaGabriel/lab0-c/commit/207dee7e316cd2e4b3d0a361e45da1d01ebcba78) 只說針對了 `q_free` 做變更但事實上改了很多其他不相關函式。

#### Reviewed by `Denny0097`
> reverse 以後的 function 未完成

後面 function 應該更能理解這份作業的資料結構， ascend 跟 descend 相對容易，建議嘗試。

# 開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ 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):                   4
  On-line CPU(s) list:    0-3
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz
    CPU family:           6
    Model:                94
    Thread(s) per core:   1
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             3
    CPU(s) scaling MHz:   93%
    CPU max MHz:          3600.0000
    CPU min MHz:          800.0000
    BogoMIPS:             6399.96
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge m
                          ca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 s
                          s ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc 
                          art arch_perfmon pebs bts rep_good nopl xtopology nons
                          top_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor 
                          ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm p
                          cid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_tim
                          er aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch
                           cpuid_fault pti ssbd ibrs ibpb stibp tpr_shadow flexp
                          riority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 
                          smep bmi2 erms invpcid mpx rdseed adx smap clflushopt 
                          intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida ara
                          t pln pts hwp hwp_notify hwp_act_window hwp_epp vnmi m
                          d_clear flush_l1d arch_capabilities
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    128 KiB (4 instances)
  L1i:                    128 KiB (4 instances)
  L2:                     1 MiB (4 instances)
  L3:                     6 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-3
Vulnerabilities:          
  Gather data sampling:   Vulnerable: No microcode
  Itlb multihit:          KVM: Mitigation: VMX disabled
  L1tf:                   Mitigation; PTE Inversion; VMX conditional cache flush
                          es, SMT disabled
  Mds:                    Mitigation; Clear CPU buffers; SMT disabled
  Meltdown:               Mitigation; PTI
  Mmio stale data:        Mitigation; Clear CPU buffers; SMT disabled
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; IBRS
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prct
                          l
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointe
                          r sanitization
  Spectre v2:             Mitigation; IBRS; IBPB conditional; STIBP disabled; RS
                          B filling; PBRSB-eIBRS Not affected; BHI Not affected
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Mitigation; TSX disabled

# 開發過程

## Commit
原本寫了三、四個函式以後都沒有做`git commit`導致做的時候跳出一長串訊息不利於修復程式

$ git commit
--- modified queue.c
+++ expected coding style
@@ -65,12 +65,13 @@ bool q_insert_tail(struct list_head *hea
 /* Remove an element from head of queue */
 element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
 {
-    if (!head || !head->next) return NULL;
+    if (!head || !head->next)
+        return NULL;
     struct list_head *node = head->next;
     element_t *entry = list_first_entry(node, element_t, list);
-    if (sp && entry->value){
-        strncpy(sp,entry->value,bufsize);
-	sp[bufsize-1] = '\0';
+    if (sp && entry->value) {
+        strncpy(sp, entry->value, bufsize);
+        sp[bufsize - 1] = '\0';
     }
     list_del_init(node);
     return entry;
@@ -91,7 +92,7 @@ int q_size(struct list_head *head)
     int len = 0;
     struct list_head *li;
 
-    list_for_each (li, head)
+    list_for_each(li, head)
         len++;
     return len;
 }
@@ -101,15 +102,16 @@ int q_size(struct list_head *head)
 bool q_delete_mid(struct list_head *head)
 {
     // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
-    if (!head||!head->next) return false;
+    if (!head || !head->next)
+        return false;
     struct list_head *slow = head;
     struct list_head *fast = head;
     struct list_head *cur = NULL;
-    
-    while(fast && fast->next){
+
+    while (fast && fast->next) {
         cur = slow;
-	slow = slow->next;
-	fast = fast->next->next;
+        slow = slow->next;
+        fast = fast->next->next;
     }
     cur->next = slow->next;
     slow->next->prev = cur;
[!] queue.c does not follow the consistent coding style.

Make sure you indent as the following:
    clang-format -i queue.c

Following files need to be cleaned up:
queue.c
Running static analysis...

因此我先把先把裡面清空以後提交了一個初始的commit message上去
> Commit [70eb018](https://github.com/DivaGabriel/lab0-c/commit/70eb01826a96920a2677ad3147fb797f623191a6)

## queue.c
>目前分數: 58/100

### q_new()
> Commit [d8a6790](https://github.com/DivaGabriel/lab0-c/commit/d8a67901506ff639dc1e03a01947c1f95d18f8d5)

使用`malloc()`分配一個`list_head`節點的空間，若分配失敗則回傳`NULL`。並且
[根據你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)創建新的節點時，初始節點需要指向自己才能保證是一個完整的雙向鏈結串列。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
     if (!head)
         return NULL;
     head->prev = head;
     head->next = head;
    return head;
}

> Commit [fdbed4b](https://github.com/DivaGabriel/lab0-c/commit/fdbed4ba9c075471a53826e30672657d7346ad7f)

透過查閱`queue.h`調用`INIT_LIST_HEAD()`來取代原本的程式碼

    struct list_head *head = malloc(sizeof(struct list_head));
     if (!head)
         return NULL;
-    head->prev = head;
-    head->next = head;
+    INIT_LIST_HEAD(head);
     return head;

### q_free()
> Commit [d8a6790](https://github.com/DivaGabriel/lab0-c/commit/d8a67901506ff639dc1e03a01947c1f95d18f8d5)

先確認傳進來的節點存在，如果沒有則回傳`NULL`。再來從`head`開始遍歷每個節點並刪除。

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

    struct list_head *cur = head;
    struct list_head *nextNode;
    while (cur) {
        nextNode = cur->next;
        free(cur);
        cur = nextNode;
    }
}

> Commit [207dee7](https://github.com/DivaGabriel/lab0-c/commit/207dee7e316cd2e4b3d0a361e45da1d01ebcba78)

原本的寫法釋放的不是`element_t`節點，改用`list_for_each_entry_safe`來去遍歷整個佇列，使用`safe`來暫存下一個節點的指標，可以使得當`entry`被刪除時影響遍歷的過程。

    if (!head)
         return;
 
-    struct list_head *cur = head;
-    struct list_head *nextNode;
-    while (cur) {
-        nextNode = cur->next;
-        free(cur);
-        cur = nextNode;
-    }
+    element_t *entry, *safe;
+    list_for_each_entry_safe(entry, safe, head, list)
+        q_release_element(entry);
+    free(head);

### q_insert_head()
> Commit [5fefeb9](https://github.com/sysprog21/lab0-c/commit/5fefeb95d33d68542b74d9e212c440d58d3110fc) and [a4440b8](https://github.com/sysprog21/lab0-c/commit/a4440b8bcc080b1d8ad271b47fe3d3715ce4f2a1)

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;
    element_t *new_node = malloc(sizeof(element_t));
    if (!new_node)
        return false;
    INIT_LIST_HEAD(&new_node->list);
    new_node->value = strdup(s);
    list_add(&new_node->list, head);
    return true;
}

### q_insert_tail()
> Commit [5fefeb9](https://github.com/sysprog21/lab0-c/commit/5fefeb95d33d68542b74d9e212c440d58d3110fc) and [a4440b8](https://github.com/sysprog21/lab0-c/commit/a4440b8bcc080b1d8ad271b47fe3d3715ce4f2a1)

* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;
    element_t *new_node = malloc(sizeof(element_t));
    if (!new_node)
        return false;
    INIT_LIST_HEAD(&new_node->list);
    new_node->value = strdup(s);
    list_add_tail(&(new_node->list), head);
    return true;
}

### q_remove_head()
> Commit [fdbed4b](https://github.com/DivaGabriel/lab0-c/commit/fdbed4ba9c075471a53826e30672657d7346ad7f)

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || !head->next)
        return NULL;
    struct list_head *node = head->next;
    element_t *entry = list_entry(node, element_t, list);
    if (entry->value && sp) {
        strncpy(sp, entry->value, bufsize);
        sp[bufsize - 1] = '\n';
    }
    list_del_init(node);
    return entry;

}

### q_remove_tail()
> Commit [fdbed4b](https://github.com/DivaGabriel/lab0-c/commit/fdbed4ba9c075471a53826e30672657d7346ad7f)

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || !head->prev)
        return NULL;
    struct list_head *node = head->prev;
    element_t *entry = list_entry(node, element_t, list);
    if (entry->value && sp) {
        strncpy(sp, entry->value, bufsize);
        sp[bufsize - 1] = '\n';
    }
    list_del_init(node);
    return entry;
}

### q_delete_mid()
Commit [c1cb992](https://github.com/sysprog21/lab0-c/commit/c1cb99202d6d4db909e7beea6f5bab9bdbaf7321) and [2e9632f](https://github.com/DivaGabriel/lab0-c/commit/2e9632f25c6de28549df5d13429bf46a6a27ca1e)
使用快慢指標來讓我找到正中間的節點，再使用`list_del_init`斷開中間節點的連接,使用`list_entry`找到節點後釋放它的記憶體。

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head && list_empty(head))
        return false;
    struct list_head *fast = head->next;
    struct list_head *slow = head->next;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }
    list_del_init(slow);
    element_t *entry = list_entry(slow, element_t, list);
    free(entry);
    return true;
}

### q_delete_dup()
### q_swap()

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head && list_empty(head))
        return;
    struct list_head *first = head->next;
    struct list_head *second = head->next->next;
    while (first != head && second != head) {
        list_move(first, second);
        first = first->next->next;
        second = second->next->next;
    }
}

### q_reverse()
### q_reverseK()
### q_sort()

### q_acend()
### q_descend()
### q_merge()

---

+++ TESTING trace trace-02-ops:
# Test of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_remove_tail', and 'q_delete_mid'
ERROR: Freed queue, but 2 blocks are still allocated
---	trace-02-ops	0/6
+++ TESTING trace trace-03-ops:
# Test of 'q_new', 'q_insert_head', 'q_remove_head', 'q_reverse', 'q_sort', and 'q_merge'
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Removed value b != expected value z
ERROR: Removed value a != expected value r
Error limit exceeded.  Stopping command execution
---	trace-03-ops	0/6
+++ TESTING trace trace-04-ops:
# Test of 'q_new', 'q_insert_tail', 'q_insert_head', 'q_remove_head', 'q_size', 'q_swap', and 'q_sort'
ERROR: Removed value dolphin != expected value bear
ERROR: Not sorted in ascending order
---	trace-04-ops	0/6
+++ TESTING trace trace-05-ops:
# Test of 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', 'q_size', 'q_swap', and 'q_sort'
ERROR: Removed value gerbil != expected value dolphin
ERROR: Not sorted in ascending order
ERROR: Removed value bear != expected value meerkat
ERROR: Removed value dolphin != expected value fish
ERROR: Removed value meerkat != expected value gerbil
Error limit exceeded.  Stopping command execution
---	trace-05-ops	0/6
+++ TESTING trace trace-06-ops:
# Test of 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_delete_dup', 'q_sort', 'q_descend', and 'q_reverseK'
ERROR: Not sorted in ascending order
ERROR: Duplicate strings are in queue or distinct strings are not in queue
ERROR: Removed value c != expected value d
ERROR: Removed value a != expected value c
ERROR: Removed value d != expected value b
Error limit exceeded.  Stopping command execution
---	trace-06-ops	0/6
+++ TESTING trace trace-07-string:
# Test of truncated strings: 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', and 'q_sort'
ERROR: Removed value aardvark_bear_dolphin_gerbil_jaguar != expected value meerkat_panda_squirrel_vulture_wolf
ERROR: Removed value aardvark_bear_dolphin_gerbil_j != expected value meerkat_panda_squirrel_vulture
ERROR: Removed value meerkat_ != expected value aardvark
ERROR: Removed value meerkat_panda_squirrel_vulture_wolf != expected value aardvark_bear_dolphin_gerbil_jaguar
---	trace-07-string	0/6
+++ TESTING trace trace-15-perf:
# Test performance of 'q_sort' with random and descending orders: 'q_new', 'q_free', 'q_insert_head', 'q_sort', and 'q_reverse'
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
Error limit exceeded.  Stopping command execution
---	trace-15-perf	0/6