2023q1 Homework1 (lab0)

contributed by < yutingshih >

開發環境

目前尚未在實體機器執行 GNU/Linux，因此暫時在 Apple M1 Mac 上使用 Lima VM，參考 Lima VM with a foreign architecture (slow mode)

$ uname -a
Linux lima-linux2023 5.15.0-67-generic #74-Ubuntu SMP Wed Feb 22 14:14:39 UTC 2023 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 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:         40 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               AuthenticAMD
  Model name:            QEMU Virtual CPU version 2.5+
    CPU family:          15
    Model:               107
    Thread(s) per core:  1
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            1
    BogoMIPS:            1999.99
    Flags:               fpu de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx lm rep_
                         good nopl cpuid extd_apicid pni cx16 hypervisor lahf_lm cmp_legacy svm 3dnowprefetch vmmcall
Virtualization features: 
  Virtualization:        AMD-V
Caches (sum of all):     
  L1d:                   256 KiB (4 instances)
  L1i:                   256 KiB (4 instances)
  L2:                    2 MiB (4 instances)
  L3:                    64 MiB (4 instances)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-3

開發過程

q_new

使用 malloc 函式配置記憶體給新建立的 struct list_head，並用 Linux kernel API 提供的 INIT_LIST_HEAD 將 head 初始化 (把 prev 和 next 設為自身) 後回傳。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);
    return head;
}

q_free

在實作 q_free 函式時原本想用上課教過的 list_for_each 巨集來走訪 linked list 的每個節點並釋放，但仔細看 list_for_each 的實作和註解描述，卻發現沒辦法使用 Linux kernel 風格的間接指標的方式來處理節點的刪除

/**
 * list_for_each - Iterate over list nodes
 * @node: list_head pointer used as iterator
 * @head: pointer to the head of the list
 *
 * The nodes and the head of the list must be kept unmodified while
 * iterating through it. Any modifications to the the list will cause undefined
 * behavior.
 */
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

所幸在同一份標頭檔的下方不遠處有提供了另一個巨集 list_for_each_safe，可以用兩個 list_head 指標來進行走訪，一個用來指向目前要刪除的節點，另一個指向目前還「安全」的節點，正好符合我們的需求

/**
  * list_for_each_safe - Iterate over list nodes and allow deletions                                                                                                         
  * @node: list_head pointer used as iterator
  * @safe: list_head pointer used to store info for next entry in list
  * @head: pointer to the head of the list
  *
  * The current node (iterator) is allowed to be removed from the list. Any
  * other modifications to the the list will cause undefined behavior.
  */
 #define list_for_each_safe(node, safe, head)                     \
     for (node = (head)->next, safe = node->next; node != (head); \
          node = safe, safe = node->next)

因此我的 q_free 實作如下：利用 list_for_each_safe 巨集從 head 開始循序走訪每個 list 節點，再用 list_entry 巨集取得包含 list_head 的資料結構的起始位址，再依序釋放 element_t 結構體中手動配置的記憶體 (先釋放 value 字串再釋放 elem 物件本身)，為了避免釋放後的記憶體被存取所帶來的安全性議題，當記憶體空間被釋放後就馬上將指向該空間的指標歸零。

由於list_for_each_safe 是從標頭節點 head 的下個節點開始走訪，因此走訪結束後，還要記得釋放 head 指向的記憶體，並將 head 指標歸零。

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

    struct list_head *node, *safe;
    list_for_each_safe(node, safe, head) {
        element_t *elem = list_entry(node, element_t, list);

        free(elem->value), elem->value = NULL;
        free(elem), elem = NULL;
    }

    free(head), head = NULL;
}

__e_new

element_t 的建構函式，用來讓 q_insert_head 和 q_insert_tail 呼叫以產生新的節點

static element_t *__e_new(char *s)
{
    element_t *elem = malloc(sizeof(element_t));
    if (!elem)
        return NULL;

    size_t len = strlen(s);
    
    elem->value = malloc((len + 1) * sizeof(char));
    if (!elem->value) {
        free(elem), elem = NULL;
        return NULL;
    }

    strncpy(elem->value, s, len + 1);
    return elem;
}

q_insert_head

呼叫建構函式 __e_new 來創建新的 element_t 節點，並使用 Linux API 中的 list_add，來將新節點加入 linked list 的最前面 (head 節點的後面)，並且在過程中檢查 head 是否為空或是新增節點時是否配置記憶體失敗。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *elem = __e_new(s);
    if (!elem)
        return false;

    list_add(&elem->list, head);
    return true;
}

q_insert_tail

呼叫建構函式 __e_new 來創建新的 element_t 節點，並使用 Linux API 中的 list_add_tail，來將新節點加入 linked list 的最後面 (head 節點的前面)，並且在過程中檢查 head 是否為空或是新增節點時是否配置記憶體失敗。

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *elem = __e_new(s);
    if (!elem)
        return false;

    list_add_tail(&elem->list, head);
    return true;
}

q_remove_head

remove 操作必須要在串列至少有一個元素節點時才能進行，因此先確認標頭節點 head 存在且至少有一個元素節點，根據 queue.h 的描述，除了將節點自 linked list 移出之外，還需要將移除的節點回傳並將其儲存的字串複製到指定區域，需要注意的是，C 語言的字串是以零結尾的 (null-terminated)，因此要記得在字串 sp 的最後補零，另外，由於移除的節點需要被回傳，為了避免非預期的記憶體存取，這裡使用 list_del_init 而非 list_del 來移除節點。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *elem = list_entry(head->next, element_t, list);
    list_del_init(head->next);

    if (sp && bufsize) {
        strncpy(sp, elem->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return elem;
}

q_remove_tail

與 q_remove_head 類似，只是差別在於 q_remove_tail 移除的節點位於 linked list 的尾端，也就是 head 的前一個節點。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *elem = list_entry(head->prev, element_t, list);
    list_del_init(head->prev);

    if (sp && bufsize) {
        strncpy(sp, elem->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return elem;
}

q_size

q_size 計算 linked list 中有幾個元素 (struct list_head)，若 head 為 NULL 代表 linked list 為空，則回傳 0，否則走訪整個 linked list，走訪過程中利用計數器 len 計算經過幾個節點，最後回傳 len。

int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    
    int len = 0;
    struct list_head *li;
    
    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

利用快慢指標的技巧來找到位於 linked list 中間的元素，一開始兩個指標在同樣的起點，在每一輪的疊代中 fast 指標往前走兩步，slow 指標往前一步，代表 slow 一定在 fast 和 head 的中點，當 fast 走訪完整個 linked list，則 slow 剛好走到一半，剛好就是我們想要移除的節點，接著使用 list_del_init 移除 slow 節點，並將指向的記憶體空間釋放。

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, *slow;
    for (fast = slow = head->next; fast != head && fast->next != head;
         fast = fast->next->next, slow = slow->next)
        ;

    list_del_init(slow);
    element_t *elem = list_entry(slow, element_t, list);
    q_release_element(elem), elem = NULL;
    return true;
}

q_delete_dup

根據 queue.h 的描述：










/**
 *  q_delete_dup() - Delete all nodes that have duplicate string,
 *                  leaving only distinct strings from the original queue.
 * @head: header of queue
 *
 * Reference:
 * https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
 *
 * Return: true for success, false if list is NULL.
 */

一開始誤解了 q_delete_dup 函式的功能，以為它是要刪除所有具有重複字串的節點。也就是說，若有兩個節點存有相同字串，就刪除其中一個，留下另一個。因此，在解 LeetCode 81 時，我寫下了這樣的程式碼。

struct ListNode* deleteDuplicates(struct ListNode* head){
    if (!head) return NULL;

    for (struct ListNode** pp = &head; *pp && (*pp)->next; pp = &(*pp)->next) {
        if ((*pp)->val == (*pp)->next->val) {
            *pp = (*pp)->next;  // remove node
        }
    }
    return head;
}

後來才發現我誤解了題目，其實正確的作法應是若有兩個節點帶有相同資料，就都要刪除。為避免其他人誤解函式功能，或許未來可以改進一下程式碼的註解。

而正確的實作如下：

struct ListNode* deleteDuplicates(struct ListNode* head){
    if (!head || !head->next) return head;

    struct ListNode** pp = &head;
    while (*pp && (*pp)->next) {
        if ((*pp)->val != (*pp)->next->val) {
            pp = &(*pp)->next;  // move one step
            continue;
        }
        while ((*pp)->next && (*pp)->val == (*pp)->next->val) {
            *pp = (*pp)->next;  // remove mode
        }
        *pp = (*pp)->next;  // remove mode
    }
    return head;
}

這個實作可以順利通過 LeetCode 的所有測試，接著讓我們繼續將其修改為 Linux 雙向鏈結串列的版本，並好好處理記憶體的釋放

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head) || list_is_singular(head))
        return head;

    struct list_head **pp = &head->next;
    while ((*pp)->next != head) {
        element_t *curr = list_entry(*pp, element_t, list);
        element_t *next = list_entry((*pp)->next, element_t, list);

        if (STREQ(curr->value, next->value)) {
            pp = &(*pp)->next;
            continue;
        }
        while ((*pp)->next && STREQ(curr->value, next->value)) {
            element_t *tmp = list_entry(*pp, element_t, list);
            list_del(*pp);
            free(tmp->value), tmp->value = NULL;
            free(tmp), tmp = NULL;
        }
        element_t *tmp = list_entry(*pp, element_t, list);
        list_del(*pp);
        free(tmp->value), tmp->value = NULL;
        free(tmp), tmp = NULL;
    }

    return true;
}

其中為了方便，新宣告一個巨集做字串的比對

#define STREQ(left, right) (!strcmp((left), (right)))

q_swap

把串列中相鄰兩個節點交換順序可以拆成兩個步驟：

把前面的節點自串列移除
把移除的節點插入到後面節點的後面

因此 q_swap 把串列上相鄰節點兩兩一組做交換，可以透過走訪迴圈的同時重複上述兩個步驟來完成，實作如下：

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *node;
    list_for_each(node, head) {
        if (node->next == head)
            break;

        list_move(node, node->next);
    }
}

調整一下可以讓我們的程式碼更加精簡

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *node;
    list_for_each(node, head->next)
        list_move_tail(node, node->prev);
}

q_reverse

基於剛才對 list_move 和 list_move_tail 的理解，可以在走訪串列期間持續把節點加入 head 的後面，來達成 q_reverse 的效果

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *node;
    list_for_each(node, head)
        list_move(node, head);
}

q_reverseK

每經過 k 個節點，就重新設定一次 group_head，作為接下來要插入節點的基準

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *node, *group_head;
    int i = 0;
    list_for_each(node, head) {
        if (i == 0)
            group_head = node->prev;
        list_move(node, group_head);
        i = (i + 1) % k;
    }
}

不要急著張貼程式碼，你應該闡述你的想法、中間的嘗試，和研讀過的相關材料，「開發紀錄」著重過程。
:notes: jserv