2024q1 Homework1 (lab0)

contributed by < jerry7961 >

Reviewed by `jychen0611`

git commit message 的標題重複且無特別意義，以祈使句為標題
git commit message 無內文，以what? why? how? 描述每次更改的內容
單次 commit 修改過多函式，如 commit 1aa9030
可斟酌參考我寫的 commit :monkey: commit a064820 和〈如何寫一個 Git Commit Message〉
開發紀錄不用存放完整程式碼，善用 diff 功能標出重點
佇列功能實作尚未完整

直接列出 git commits 的超連結並討論，不要只談「心法」，跟同學說你認為要改成什麼，細節！

不用說「建議」，什麼沒做好，就去改什麼。假裝有禮貌無助於工程品質的提升。
:notes: jserv

Reviewed by `jimmy01240397`

善用巨集展開以減少重複的程式碼，例如：

#define q_remove_base(head, sp, bufsize, from)                             \
    if (head && !list_empty(head)) {                                       \
        element_t *to_remove = list_##from##_entry(head, element_t, list); \
        list_del(&to_remove->list);                                        \
        if (sp) {                                                          \
            strncpy(sp, to_remove->value, bufsize - 1);                    \
        }                                                                  \
        return to_remove;                                                  \
    }                                                                      \
    return NULL;                                                           \
    
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    q_remove_base(head, sp, bufsize, first);
}

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    q_remove_base(head, sp, bufsize, last);
}

q_insert_head
q_insert_tail
q_remove_head
q_remove_tail

提供說明用的程式碼，不要只談「心法」。
:notes: jserv

Reviewed by `jujuegg`

可以只列出重點程式碼討論
建議將內文中提及程式碼的部份加上``，如 strcpy。

開發環境

$ 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:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-1235U
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            4
    BogoMIPS:            4992.00

指定的佇列操作

`q_new`

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

`q_free`

先檢查佇列是否為空，若為空則 return 。
用 list_for_each_entry_safe 巨集走訪所有節點，並釋放節點。
最後釋放開頭節點。

void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *cur, *next;
    list_for_each_entry_safe (cur, next, head, list) {
        q_release_element(cur);
    }
    free(head);
}

`q_insert_head`

一開始誤用 strcpy (如下) 。

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

    element_t *new_element=malloc(sizeof(element_t));
    if(!new_element)
        return false;

    strcpy(new_element->value,s);
    if(!new_element->value){
        free(new_element);
        return false;
    }

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

}

strcpy(s1,s2) 的功能是複製字串 s2 到字串 s1 ，不會為 s1 分配内存， s1 的長度必須大於 s2 的長度。
因此在沒有為 new_element->value 分配內存的情況下直接用 strcpy(new_element->value,s) 會造成錯誤。
事先為 new_element->value 分配內存再用 strcpy 複製字串即可修正錯誤。

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

    element_t *new_element=malloc(sizeof(element_t));
    if(!new_element)
        return false;

    new_element->value=malloc(strlen(s) + 1);
    if(!new_element->value){
        free(new_element);
        return false;
    }

    strcpy(new_element->value,s);
    list_add(&new_element->list,head);
    return true;

}

另一種做法是使用 strdup 來代替 strcpy ，strdup 會為字串分配內存空間，並返回新分配空間的指標。

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

    element_t *new_element=malloc(sizeof(element_t));
    if(!new_element)
        return false;

    new_element->value=strdup(s);
    if(!new_element->value){
        free(new_element);
        return false;
    }

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

}

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

`q_insert_tail`

與 q_insert_head 的做法類似，差別是改用 list_add_tail。

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

    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;

    new_element->value = strdup(s);
    if (!new_element->value) {
        free(new_element);
        return false;
    }

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

`q_remove_head`

對照 Dictionary.com 對 implement 一詞的解釋:

to fulfill; perform; carry out:
to put into effect according to or by means of a definite plan or procedure.
Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

\to

資訊科技詞彙翻譯

q_remove_head 的作用是從鏈結串列的開頭移除一個元素。

首先檢查 head 是否為空指標，以及鏈結串列中是否至少有一個節點，確保鏈結串列存在且不為空。接著用 list_first_entry 取得鏈結串列第一個元素的指標，並透過 list_del 將這個元素從鏈結串列中移除。

如果 sp 不為 NULL ，使用 strncpy 函式將被移除元素的字串 (to_delete->value) 複製到 sp 指向的位址中。複製的字元數量最多為 bufsize - 1 ，這是為了在字串結尾預留一個位置，用來存放 \0 。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head && !list_empty(head)) {
        element_t *to_remove = list_first_entry(head, element_t, list);
        list_del(&to_remove->list);

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

        }
        return to_remove;
    }

    return NULL;
}

`q_remove_tail`

與 q_remove_head 類似，差別在使用 list_last_entry 來取得要移除的元素。

`q_size`

使用 list_for_each 來走訪所有節點，每走訪一個節點 count 值就加一。

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int count = 0;
    struct list_head *temp;
    list_for_each (temp, head)
        count++;

    return count;
}

說好的進度呢？

`q_delete_mid`

使用快慢指標，快指標每次前進兩步，慢指標每次前進一步。

當鏈結串列包含奇數個節點時，快指標會停在最後一個節點上，此時慢指標正好指向鏈結串列的中間節點。
當鏈結串列包含偶數個節點時，快指標會回到鏈結串列的 head ，此時慢指標將指向中間兩個節點中的第二個。為了使 q_delete_mid 能夠刪除中間兩個節點中的第一個，需要增加一個 if 語句來調整慢指標的位置。

改進你的漢語表達。

if (fast == head) {
    slow = slow->prev;
}

使用作業規範的程式碼縮排風格

`q_delete_dup`

q_delete_dup 是要在鏈結串列已經排序好的狀況下，移走其中具有重複內容的節點。

使用 list_for_each_safe 來走訪鏈結串列中的每個節點。
mark_del 用來標記是否遇到重複節點。
在走訪過程中，根據當前節點與前後節點的關係，需要處理以下幾種情況：

當前節點已經是最後一個節點，此時用 mark_del 來判斷當前節點是否與前一個節點重複，如果重複則刪除它。
當前節點與下一個節點內容相同，此時刪除當前節點，並將 mark_del 設為 true ，表示已遇到重複節點。
當前節點與下一個節點內容不同，但 mark_del 為 true，這表示當前節點與上一個節點內容相同，因此刪除當前節點，並將 mark_del 設為 false。
非前三種情況，代表當前節點與下一個節點內容不同，與上一個節點也不同，無需執行任何操作。

`q_swap`

q_swap 的作用是交換鏈結串列中鄰近的節點。

如果鏈結串列中的節點數量小於等於 1 ，無需執行任何操作。
如果鏈結串列中的節點數量大於 1 ，則 q_swap 從頭部節點的下一個節點開始走訪鏈結串列。對於每對相鄰節點，q_swap 會先將它們從鏈結串列中移除，然後以交換後的順序將它們重新插入到鏈結串列中。這個過程會一直重複，直到走訪完鏈結串列的所有節點。

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

    struct list_head *node = head->next;
    while (node != head && node->next != head) {
        struct list_head *nextNode = node->next;

        list_del(node);
        list_del(nextNode);

        list_add(nextNode, node->prev);
        list_add(node, nextNode);

        node = node->next;
    }
}

`q_reverse`

從頭部節點開始走訪鏈結串列，交換每個節點的 next 和 prev 指標以反轉鏈結串列方向，直到走訪完整個鏈結串列。

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

    struct list_head *current = head;
    struct list_head *temp = NULL;

    do {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;

        current = current->prev;
    } while (current != head);
}

`q_sort`

一開始使用 Insertion Sort ，無法通過測資，後來參考同學寫法，改用 Merge Sort 。

void merge(struct list_head *l_head,
           struct list_head *r_head,
           struct list_head *head)
{
    struct list_head temp_list;
    INIT_LIST_HEAD(&temp_list);

    while (!list_empty(l_head) || !list_empty(r_head)) {
        struct list_head *chosen;

        if (list_empty(l_head)) {
            chosen = r_head;
        } else if (list_empty(r_head)) {
            chosen = l_head;
        } else {
            element_t *l_entry = list_entry(l_head->next, element_t, list);
            element_t *r_entry = list_entry(r_head->next, element_t, list);
            chosen =
                (strcmp(l_entry->value, r_entry->value) <= 0) ? l_head : r_head;
        }

        list_move_tail(chosen->next, &temp_list);
    }

    list_splice_tail_init(&temp_list, head);
}
void merge_sort_recursive(struct list_head *head, int length)
{
    if (length <= 1)
        return;

    int mid = length / 2;
    struct list_head left, right;
    INIT_LIST_HEAD(&left);
    INIT_LIST_HEAD(&right);

    struct list_head *current = head->next;
    for (int i = 0; i < mid; i++) {
        struct list_head *next = current->next;
        list_move_tail(current, &left);
        current = next;
    }
    list_splice_tail_init(head, &right);

    merge_sort_recursive(&left, mid);
    merge_sort_recursive(&right, length - mid);

    INIT_LIST_HEAD(head);
    merge(&left, &right, head);
}

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

    int length = 0;
    struct list_head *pos;
    list_for_each (pos, head) {
        length++;
    }

    merge_sort_recursive(head, length);
}

void q_sort(struct list_head *head, bool descend)
{
    merge_sort(head);
    if (descend) {
        q_reverse(head);
    }
}

`q_merge`

使用 list_for_each_entry_safe 走訪整個鏈結串列。從第二個鏈結串列開始，透過 list_splice_init 將每個鏈結串列中的節點合併到第一個鏈結串列中。完成合併後，利用 q_sort 對合併後的鏈結串列進行排序。

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head)) {
        return 0;
    }
    if (list_is_singular(head)) {
        return 1;
    }

    int total_elements = 0;
    queue_contex_t *context, *tmp;
    struct list_head *first_queue = NULL;

    list_for_each_entry_safe (context, tmp, head, chain) {
        if (!first_queue) {
            first_queue = context->q;
            total_elements += context->size;
        } else {
            list_splice_init(context->q, first_queue);
            context->q = NULL;
            total_elements += context->size;
        }
    }
    q_sort(first_queue, false);

    return total_elements;
}

記憶體洩漏

在 trace-03-ops 出現以上錯誤，經過排查，問題出在 q_merge 函式。原始版本的 q_merge 創建了一個新的 first_queue 指標，它用來指向第一個遇到的非空鏈結串列，這個鏈結串列將作為所有鏈結串列合併的目標，所有其他鏈結串列的元素都會被合併到這個 first_queue 中，其他鏈結串列在合併到 first_queue 後 q 指標會被設為 NULL，但相關內存沒有被釋放，導致錯誤。修改 q_merge 函式後， trace-03-ops 可順利通過。

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head)) {
        return 0;
    }

    queue_contex_t *base_queue = list_first_entry(head, queue_contex_t, chain);
    if (list_is_singular(head)) {
        return base_queue->size;
    }

    queue_contex_t *queue_to_merge;
    struct list_head *current, *next;

    list_for_each_safe (current, next, head) {
        if (current == &base_queue->chain) {
            continue;
        }
        queue_to_merge = list_entry(current, queue_contex_t, chain);
        list_splice_tail_init(queue_to_merge->q, base_queue->q);
        base_queue->size += queue_to_merge->size;
    }

    q_sort(base_queue->q, descend);
    return base_queue->size;
}

透過 Massif 分析記憶體使用量

參考 alanjiang85 的說明，用 trace-eg.cmd 進行分析

透過 Valgrind 產生 massif 檔案

$ valgrind --tool=massif ./qtest -f traces/trace-eg.cmd

產生記憶體使用情形的時間分佈圖

$ massif-visualizer ./massif.out.59554

2024q1 Homework1 (lab0)

Reviewed by jychen0611

Reviewed by jimmy01240397

Reviewed by jujuegg

開發環境

指定的佇列操作

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

q_merge