# 2025q1 Homework1 (lab0)

## 開發環境

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-12500H
    CPU family:           6
    Model:                154
    Thread(s) per core:   2
    Core(s) per socket:   12
    Socket(s):            1
    Stepping:             3
    CPU(s) scaling MHz:   18%
    CPU max MHz:          4500.0000
    CPU min MHz:          400.0000
    BogoMIPS:             6220.80
Caches (sum of all):      
  L1d:                    448 KiB (12 instances)
  L1i:                    640 KiB (12 instances)
  L2:                     9 MiB (6 instances)
  L3:                     18 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-15

## 針對佇列操作的程式碼實作
### q_new
函式目的：建立一個空的佇列，並且回傳指標
實作方式：為了避免 `malloc` 配置失敗，需要在 `malloc` 後檢查配置是否成功，因此需要在 `malloc` 後做檢查，以免發生 Undefined Behavior
如果配置成功，則將 `prev` 及 `next` 指向自己並回傳

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

### q_free
目的：釋放整個佇列所佔據的記憶體
實作：先建立一個 `element` 接著夠過這個 `element` 尋訪整個 `queue` 在逐一進行釋放。此外，為了避免當前節點釋放後找不到下一個節點得問題，需要在額外新增一個 node 在釋放當前節點之前儲存下一個節點的位置，我們可以透過 list_for_each_safe() 這個 macro 達成

void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *cur = NULL, *node = NULL;
    list_for_each_entry_safe (cur, node, head, list) {
        free(cur->value);
        free(cur);
    }
    free(head);
} 

### q_insert_head & q_insert_tail

### q_remove_head & q_remove_tail
目的：將 queue 中第一個元素移除，並放置於暫存區
實作：使用 list_entry 這個 macro 來取得第一個元素，接著透過 `list_def` 將其從 queue 中移除，並置於暫存區 `sp`

首先是 `q_remove_head`，根據 queue.h 中的註解，`sp` 是一個暫存區，裡面放的是被 remove 的元素，`bufsize` 是這個暫存區的大小

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

以上程式碼在 queue 為 empty 的時候會進行 remove 會導致 Segmentation fault ，因此需要在額外檢查 list_head 是否為 empty

-    if (!head)
+    if (!head || list_empty(head))

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

### q_delete_mid

### q_delete_dup

### q_swap
目的：將兩元素的順序交換
實作：可以透過 `list.h` 中的 `list_del` 與 `list_add`，來實作

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

實際測試會有問題，只要佇列的數量大於 3 就會失敗，因此需修改

-    struct list_head *node = head->next;
-    while (node && node->next != head) {
+    struct list_head *cur = head->next, *node = cur->next;
+    while (cur != head && cur->next != head) {
         list_del(node);
-        list_add(node, node->next);
-        node = node->next;
+        list_add(node, cur->prev);
+        cur = cur->next;
+        node = cur->next;

### q_reverse
目的：反轉 queue 中元素的順序
實作：與 `q_swap` 類似，可以透過 `list_for_each_safe` 以及 `list_move` 等 function 來達成

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *node = NULL, *safe = NULL;
    list_for_each_safe (node, safe, head) {
        list_del(node);
        list_move(node, head);
    }
}

### q_reverseK
目的：對於整個 queue 以 k 個為一組進行反轉
實作：先將要反轉的部分從 queue 中切離，接著使用 q_reverse 進行反轉，再組合回去

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
	if(!head || list_empty(head))
		return;
	struct list_head *node = NULL,  *safe = NULL,  *start = head;
	int count = 0;
	list_for_each_safe(node, safe, head){
		if (count < k - 1 ){
            count++;
			continue;
		}
		LIST_HEAD(tmp);
		list_cut_position(&tmp, start, node);
		q_reverse(&tmp);
		list_splice(&tmp, start);
		start = safe->prev;
		count = 0;
	}
}

### q_ascend & q_descend
目的：對於每個節點，如果該節點右側有比當前節點還大 / 小的值，及刪除當前節點
實作：從 queue 的尾端往前找會比較簡單，如果條件成立就刪除，反之則繼續往前找

int q_ascend(struct list_head *head)
{
    ...
    while (tail != head && tail->prev != head) {
        struct list_head *node = tail->prev;
        element_t *node_elem = list_entry(node, element_t, list);
        if (strcmp(node_elem->value, tail_elem->value) > 0) {
    ...
}

int q_descend(struct list_head *head)
{
    ...
    while (tail != head && tail->prev != head) {
        struct list_head *node = tail->prev;
        element_t *node_elem = list_entry(node, element_t, list);
        if (strcmp(node_elem->value, tail_elem->value) < 0) {
    ...
}

### q_sort
目的：針對 queue 中的元素進行排序
實作：將排序拆成三個 fucntion ，分別是 `merge` 、 `merge_sort` 以及 `q_sort`

q_sort 中，將整個 list 的環狀部分拆掉，接著呼叫 `merge_sort` 將 list 拆分成單一元素，然後透過 `merge` 將 list 組合回來，最後在重建 list 的環狀結構

`merge_sort` 實作過程中發生 Segmentation fault ，原始版本如下

struct list_head *merge_sort(struct list_head *head, bool descend)
{
    if (!head || list_is_singular(head))
        return head;

    struct list_head *slow = head, *fast = head;
    ...
}

重新檢視實作的流程，當呼叫到 `merge_sort` 的時候，此時傳入的 `head` 並非 dummy node ，因此不該使用 `list_is_singular` 這個 function，應該判斷這個 `head` 後面是否還有節點存在，如果是單一節點則無須進行排序
另外，考量到傳入的 list 只有兩個節點的情況，如果 `fast` 的起始點設在 `head`，當進入 while 後，`fast` 會因為 `fast = fast->next->next` 存取到不存在的位址，造成 Segmentation fault
因此，程式碼應修成以下：

struct list_head *merge_sort(struct list_head *head, bool descend)
{
-   if (!head || list_is_singular(head))
+   if (!head || !head->next)
        return head;

-   struct list_head *slow = head, *fast = head;
+   struct list_head *slow = head, *fast = head->next;
    ...
}

### q_merge
目的：將所有 head 指向的 queue 合併成一個，接著進行排序
實作：建立一個新的 list_head ，接著將 head 指向的所有 queue 走過一遍，並切把節點搬到新的 list_head ，最後在進行排序

註解中有提到，這個函式有使用到 `queue_contex_t` 這個結構

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

可以先將 head->next 作為起始點，接著逐一將所有節點搬到這個 queue，如下

int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    queue_contex_t *new_head = list_entry(head->next, queue_contex_t, chain);
    struct list_head *node = head->next, *safe = NULL;
    while (node != head) {
        safe = node->next;
        queue_contex_t *tmp = list_entry(node, queue_contex_t, chain);
        list_splice(tmp->q, new_head->q);
        node = safe;
    }
    q_sort(new_head->q, descend);
    return q_size(new_head->q);
}

但這個版本由於 `new_head` 及 `tmp` 在最開始的時候同時指向同一個地址，接著在進行 `list_splice` 操作，導致 segmentation fault，因此修改後如下：

int q_merge(struct list_head *head, bool descend)
{
    ...
-   struct list_head *node = head->next, *safe = NULL;
+   struct list_head *node = head->next->next, *safe = node->next;
-    while (node != head) {
+    while (node && node != head) {
        queue_contex_t *tmp = list_entry(node, queue_contex_t, chain);
-       list_splice(tmp->q, new_head->q);
+       list_splice_tail_init(tmp->q, new_head->q);
    ...
}