# 2024q1 Homework1 (lab0)
contributed by < [aftuta85](https://github.com/aftuta85) >

## 開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  20
  On-line CPU(s) list:   0-19
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-14500
    CPU family:          6
    Model:               191
    Thread(s) per core:  2
    Core(s) per socket:  14
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         5000.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5222.40
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   544 KiB (14 instances)
  L1i:                   704 KiB (14 instances)
  L2:                    11.5 MiB (8 instances)
  L3:                    24 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-19

## 佇列實作
### `q_insert_head, q_insert_tail`
> commit [f61bded](https://github.com/aftuta85/lab0-c/commit/f61bded32f76c3af79194e7de5ade7db08d490a3)

### `q_remove_head, q_remove_tail`
> commit [311e71a](https://github.com/aftuta85/lab0-c/commit/311e71aeecb1b958b16efdf3d155dcc4b037699a)

在執行 `q_remove_head` 和 `q_remove_tail` 操作時，會需要複製待刪除節點的值，目前的實作方式是計算長度後使用 `strncpy` 來做字串複製，由於會手動在字串尾部加上`\0`，是否用 `memcpy` 取代`strncpy` 即可?

以前在使用 `strncpy` 的時候沒注意到一些細節，例如 `source` 長度小於指定複製的長度時， `strncpy` 會將不足長度的部分都補上 `null-terminated`。

**Linux Programmer's Manual - STRCPY(3)**
> If the length of src is less than n, strncpy() writes additional null bytes to dest to ensure that a total of n bytes are written.

**[Linux Kernel Deprecated Page](https://www.kernel.org/doc/html/latest/process/deprecated.html#strncpy-on-nul-terminated-strings)**
> Use of strncpy() does not guarantee that the destination buffer will be NUL terminated. This can lead to various linear read overflows and other misbehavior due to the missing termination. It also NUL-pads the destination buffer if the source contents are shorter than the destination buffer size, which may be a needless performance penalty for callers using only NUL-terminated strings.

:::danger
你的洞見呢？
:::

### `q_delete_mid`
> commit [e99aaad](https://github.com/aftuta85/lab0-c/commit/e99aaad2aa3d990864999ab8767ac675b8fea092)

在實作 [LeetCode: Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/) 的時候是採用快慢指標的方式，如下：

struct ListNode* deleteMiddle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    struct ListNode* prev = NULL;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    if (prev)
        prev->next = slow->next;
    return prev ? head : prev;
}

:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

由於在 lab0-c 中的佇列是環狀雙向鏈結串列，因此嘗試用兩個指標 `currNext` 和 `currPrev` 同時從 `head` 的前後兩端<s>遍歷</s> 逐一走訪每個節點，直到兩個指標指向相同節點，或是直到 `currNext->next` 指向 `currPrev` 為止。迴圈結束後 `currNext` 即為待刪除之中間節點。實作方式如下：

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *currNext = head->next, *currPrev = head->prev;
    while (currNext != currPrev && currNext->next != currPrev) {
        currNext = currNext->next;
        currPrev = currPrev->prev;
    }
    element_t *del = list_entry(currNext, element_t, list);
    list_del(&del->list);
    free(del->value);
    free(del);
    return true;
}

### `q_ascend` / `q_descend `
> commit [a544d2d](https://github.com/aftuta85/lab0-c/commit/a544d2df814fd2b5aba5c7a43f0edda1290c1dbe)

額外使用一個 `descend_list` 用來暫時放置逐一訪問節點時的當前節點並將其從原本的 `head` 移除。每次新加入節點至 `descend_list` 時，通過 `while` 迴圈檢查 `descend_list` 的最後一個節點的字串是否比當前節點大。若當前節點較大則將 `descend_list` 的最後一個節點刪除並繼續往前面節點比較，直到 `descend_list` 為空或是有節點的字串大於當前節點才停止並放置在 `descend_list` 的尾端。最後再將整個 `descend_list` 移動回 `head`。

int q_descend(struct list_head *head)
{
    // ...
    LIST_HEAD(descend_list);
    element_t *curr_e = NULL, *last_e = NULL;
    struct list_head *curr = NULL, *tmp = NULL;
    list_for_each_safe (curr, tmp, head) {
        curr_e = list_entry(curr, element_t, list);
        while (q_size(&descend_list) > 0) {
            last_e = list_last_entry(&descend_list, element_t, list);
            if (strcmp(curr_e->value, last_e->value) > 0) {
                // delete and free
            } else
                break;
        }
        list_move_tail(curr, &descend_list);
    }
    list_splice_init(&descend_list, head);
    return q_size(head);
}

### `q_reverseK`
> commit [aff642c](https://github.com/aftuta85/lab0-c/commit/aff642ca1ed360b27d009cdf89966cbe8d59c65a)

`q_reverseK()` 用於將給定的鏈結串列按照 K 個節點一組進行反轉。在這段程式碼中，我們使用了一個 `while` 迴圈來逐一訪問鏈結串列。每當訪問了 K 個節點後，我們就利用 `list_cut_position` 將這 K 個節點移至 `tmp_list` 中進行暫存，然後進行反轉操作。接著再將它們移回原本的位置。然後我們繼續尋找下一組 K 個節點，並重複上述的移動、反轉、移動操作。

void q_reverseK(struct list_head *head, int k)
{
    // ...
    int count = 1;
    struct list_head *curr = head->next, *prev = head, *nxt = curr->next;
    LIST_HEAD(tmp_list);
    while (curr != head) {
        if (count % k == 0) {
            list_cut_position(&tmp_list, prev, curr);
            q_reverse(&tmp_list);
            list_splice_init(&tmp_list, prev);
            prev = nxt->prev;
        }
        count++;
        curr = nxt;
        nxt = nxt->next;
    }
}