2024q1 Homework1 (lab0)

contributed by < yulin0625 >

Review by 164253

q_remove_head 和 q_remove_tail 有許多重複部分
q_delete_mid 中的快慢指針可以改為兩個指針從頭尾向中間靠近
q_ascend 和 q_descend 中也有許多重複

開發與實驗環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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:         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-12400
    CPU family:          6
    Model:               151
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         4400.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4992.00

使用的結構體

雙向鏈節串列實作

是「雙向鏈結串列」。
留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心

使用 list_head 以及 element_t 這兩種結構體來實作雙向鏈節

list_head

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

element_t

typedef struct {
    char *value;
    struct list_head list;
} element_t;

從這兩種結構體的定義中，我們可以了解到本次作業中佇列的實作方式是將結構體 list_head 嵌入到新的結構體 element_t 中。這種方法類似於 Linux 核心的 Linked list 實作方式。
這樣設計的好處是只要將 list_head 納入到新的結構體的一個成員中，就可以操作這個佇列，而不需要自行維護一套雙向鏈結串列。

佇列管理

使用結構體 queue_contex_t 及 queue_chain_t 管理多個佇列

queue_contex_t

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

避免非必要的項目縮排 (即 * )，以清晰、明確，且通順的漢語書寫。

已修正

q：指向佇列 head 節點的指標

chain：用於將不同佇列的頭節點連接在一起

size：表示這個佇列的長度

id：唯一的識別號，用於區分不同的佇列

queue_chain_t

typedef struct {
    struct list_head head;
    int size;
} queue_chain_t;

static queue_chain_t chain = {.size = 0};

queue_chain_t 利用 chain 將各個 queue_contex_t 串連成一個雙向鍊結串列，如此一來便能管理多個佇列，示意圖如下：

指定的佇列操作

q_new

commit 2201f29

使用你 fork 後得到的 GitHub repository 的 commit 超連結

建立新的「空」佇列

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

1. 使用 malloc 配置 list_head 大小的記憶體空間，並由指標 head 指向
2. 若空間分配失敗(malloc 回傳 NULL)，則回傳 NULL
3. 使用 INIT_LIST_HEAD 初始化 head

q_free

commit 0fa78c5

釋放佇列所佔用的記憶體

使用 list_for_each_entry_safe 走訪每個節點，再利用 q_release_element 釋放節點所佔用的記憶體

q_insert_head

commit b4290b3
在佇列前端插入值為 s 的新節點

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

使用 melloc 配置 element_t 大小的記憶體空間，若配置失敗則回傳 false
使用函式 strdup 複製字串資料，若複製失敗則回傳 false
使用 list_add 將節點加入佇列的前端

q_insert_tail

commit b4290b3

在佇列尾端插入值為 s 的新節點

我發現 q_insert_tail 實際上與 q_insert_head 幾乎相同，唯一的區別在於新元素應該從佇列的哪個位置添加。因此，可以重用 q_insert_head 的程式碼。

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }

    q_insert_head(&head->prev, s);
}

改進你的漢語表達。

q_remove_head

commit b4290b3

將佇列的第一個 entry 移除，並將 entry 的 value 複製到 buffer 中

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

使用 list_first_entry 取得佇列的第一個 entry
使用 list_del 將該 entry 由佇列中刪除
使用 strncpy 複製該 entry 的 value 至 buffer中

注意行文的空白字元！

發現原本的方法在buffer大小不夠時會產生字串結尾無'\0'的狀況，修改方式如下:
7ceb10a

@@ -79,7 +79,8 @@ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
     list_del(&element->list);
 
     if (sp && bufsize) {
-        strncpy(sp, element->value, bufsize);
+        strncpy(sp, element->value, bufsize - 1);
+        sp[bufsize - 1] = '\0';
     }
 
     return element;

q_remove_tail

commit b4290b3

將佇列的最後一個 entry 移除，並將 entry 的 value 複製到 buffer 中

與 q_remove_head類似，差別為將 list_first_entry 改為 list_last_entry

q_size

commit fc78b84

取得佇列的長度

使用 list_for_each 走訪佇列的每個節點，並利用變數 len 紀錄節點數量

q_delete_mid

commit 8dc1568

刪除佇列中間的節點

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

參考 你所不知道的 C 語言: linked list 和非連續記憶體 所提到的快慢指標技巧找出佇列中間的節點
使用 list_del 將該節點由佇列刪除
使用 q_release_element 釋放該節點所佔用的記憶體

q_delete_dup

commit b5f0c26

刪除佇列中具有重複值的節點

實作方式：

1. 使用 list_for_each_entry_safe 走訪佇列中的每個節點
2. 使用 strcmp 比較該節點與右側節點是否有相同的值
3. 若兩節點有相同的值，則將 equal 設為 true，並將該節點刪除
4. 若兩節點沒有相同的值，則判斷 equal 是否為 true，

q_reverse

commit dd6f602

反轉佇列中的元素

逐一將每個節點移動至佇列的最前方，等同於將佇列反轉

使用 list_for_each_entry_safe 走訪每個佇列的節點，並利用 list_move 將節點移動至佇列的最前方

q_reverseK

commit ab10d48

將佇列每 k 個節點反轉一次

將佇列以 k 為單位，切割成數個子佇列，再將每個子佇列反轉，即可獲得 reverseK 的效果

1. 走訪佇列的每個節點，並以指標 cut 紀錄子佇列的開頭處
2. 若經過 k 個點，則利用 list_cut_position 將子佇列切出，並複製至新的佇列 tmp
3. 使用 q_reverse 將 tmp 佇列反轉
4. 使用 list_splice 將 tmp 佇列插入回原本的佇列

q_swap

commit c9e9b0b

將佇列每2個節點反轉一次

q_swap 為 q_reverseK k=2 時的特例

q_ascend

commit 6a45a0c

移除每個節點，只要該節點右側的任何地方存在一個嚴格小於它的節點。

題目要求「若某節點的右側存在值小於該節點的其他節點，則必須移除該節點」。
如果按照原始規則，需要使用兩層迴圈來實作。然而，我們可以將這個條件簡化為「由右至左檢查每個節點，若該節點的左側節點大於該節點，則將左側節點移除」。這樣的話，只需要一層迴圈即可實作。

q_descend

commit 6a45a0c

移除每個節點，只要該節點右側的任何地方存在一個嚴格大於它的節點。

與 q_ascend 實作方式類似，差別為將條件改為「由右至左檢查每個節點，若該節點的左側節點小於該節點，則將左側節點移除」。

q_sort

commit 601f6b5

將佇列中的元素按照升序/降序排序

採用 merge sort 遞迴演算法來實作。

如何確保目前的測試已涵蓋排序演算法的最差狀況？

q_merge

commit 2552906

將所有的佇列合併成一個排序的佇列

將所有的佇列合併為一個佇列，再將該佇列用 q_sort 進行排序

以 Valgrind 分析記憶體問題

執行 make valgrind

執行 massif: 分析

• Heap blocks
• Heap administration blocks
• Stack sizes

valgrind --tool=massif ./qtest -f <trace file>

使用 Valgrind 驗證程式後，沒有出現記憶體錯誤的狀況，但仍然會有錯誤訊息 ERROR: Probably not constant time or wrong implementation

使用 massif-visualizer 將數據圖形化

$ massif-visualizer massif.out.<pid>

分析 trace-17-complexity.cmd

使用 address sanitizer

make clean
make SANITIZER=1

之後執行 make test ，沒有出現任何記憶體相關錯誤訊息，檢查通過。

尚未依據作業三指示，進行對應的 git rebase 操作！