2025q1 Homework1 (lab0)

contributed by < vestata >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.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):                   24
  On-line CPU(s) list:    0-23
Vendor ID:                GenuineIntel
  Model name:             13th Gen Intel(R) Core(TM) i7-13700
    CPU family:           6
    Model:                183

針對佇列操作的程式碼實作

• 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_reverseK
• q_sort
• q_ascend
• q_descend
• q_merge

---

/* Free all storage used by queue */
void q_free(struct list_head *head) {
    if(!head)   return;

    element_t *tmp, *safe;
    list_for_each_entry_safe(tmp, safe, head, list) {
        q_release_element(tmp);
    }
    free(head);
    return;
}

要記得釋放 head，根據 queue.h 的敘述：

/**
 * q_free() - Free all storage used by queue, no effect if header is NULL
 * @head: header of queue
 */

若是 head 記憶體沒有被釋放會出現以下錯誤：

ERROR: There is no queue, but 1 blocks are still allocated

commit

q_insert_head() and q_insert_tail()

原本的實做方法無法通過 trace-11-malloc、trace-12-malloc。 查看 traces/trace-11-malloc.cmd malloc 的失敗率設為 25%。

In strdup:

The strdup() function returns a pointer to a new string which is a duplicate of the strings. Memory for the new string is obtained with malloc(3), and can be freed with free(3).
Linux man page

在 harness.h 中，malloc、calloc、free 和 strdup 都透過對應的巨集 test_ 來執行自定義操作。而在 qtest 中，可以使用 malloc [probability] 命令來設定 fail_probability，導致 test_strdup 中的 test_malloc 可能因為 fail_probability 的影響而失敗。因此，需要加入相應的檢查機制。

         return false;
 
     new->value = strdup(s);
+    if (!new->value) {
+        free(new);
+        return false;
+    }
 
     list_add(&new->list, head);
     return true;

commit 58c0e8b

研讀 lib/list_sort.c