2024q1 Homework1 (lab0)

contributed by < YiChiChao >

Reviewed by yu-hsiennn

多利用 graphviz 來製圖

開發環境

$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            12
    CPU max MHz:         3900.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00

名詞中英定義

過去整理筆記很習慣中英夾雜，透過這學期的學習希望能改變這樣的行為。

• linked list ： 鏈結串列
• traverse ： 走訪
• memory hierarchy ： 記憶體階層架構
• generic programming ： 泛用性 （？）

資料閱讀筆記

你所不知道的 C 語言: linked list 和非連續記憶體

• （待解答）如何偵測鏈結串列是否存在環狀結構？
• （待解答）如何對鏈結串列排序並確保空間複雜度為
  $O(1)$呢？
• （待解答）什麼是 Locality of reference
• 有品味的寫法（以remove_list_node為例）：
  • 直覺：用指標指向第一個元素資料，此種方法需要考慮到此筆資料是否為第一筆資料，如果是，則list->head 和 prev->next都需要更新。
  • 有品味：用「指標的指標」指向 ＆list->head，以「要更新的位址」為思考點來操作，而後指標的指標皆為指向 &node->next。刪除的操作，實質上是去更新特定指標的位址中的內容，而不是單就個別的node 去判別。
• 針對移走節點的間接指標版本

typedef struct list_entry {
  int value;
  struct list_entry *next;
} list_entry_t;

// Given that there is a remove function in stdio.h, I have renamed it to
// remove_element to avoid potential conflicts. The for loop needs to account
// for scenarios both with and without the target value. The indirect variable
// cannot be included in the for loop because its new value needs to be assigned
// at the end.
void remove_element(list_entry_t **head, int value) {
  list_entry_t **indirect = head;
  for (; (*indirect)->value != value || (*indirect)->next == NULL;
       indirect = &((*indirect)->next)) {
  }
  *indirect = (*indirect)->next;
}

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

指定的佇列操作

q_new

透過 malloc 配置記憶體，並且透過 list.h 中的 INIT_LIST_HEAD 初始結構體。

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

list.h 中有 LIST_HEAD(head) 和 INIT_LIST_HEAD(struct list_head *head) 兩個功能很類似的函式/巨集。LIST_HEAD 是直接宣告一個區域變數並且完成初始化的巨集，INIT_LIST_HEAD 只負責初始化傳入的 list_head 指標。

allocate 翻譯為「配置」，以區隔 dispatch (分發/分配) 的翻譯，二者在作業系統領域都是常見詞彙。

了解，已修正。YiChi Chao

之所以不能直接用 LIST_HEAD(head) 而要動態配置記憶體，再用 INIT_LIST_HEAD 初始化指標，是因為在函式中宣告的區域變數會被配置到 stack 中，當函式返回時會自動將此區域回收，此時即使回傳此結構體的指標，指標的內容也可能為未定義之內容。透過 malloc 配置的記憶體在 heap 中，此區的記憶體需要透過 free 來釋放。所以 malloc 配置的記憶體的結構體指標回傳後，其內容並不會因為函式結束而被回收。

struct list_head *q_new()
{  // instead of using LIST_HEAD creating local variable
    // use INIT_LIST_HEAD and malloc for both declaration and initialization
    struct list_head *new_queue = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(new_queue);
    return new_queue;
}

q_free

void q_free(struct list_head *l)
{
    free(l);
}

q_insert_head

string 是「字串」。

strdup 是用來動態複製一個以 '\0' 結尾的字串，並回傳字串指標。

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

Delete 的時候在處理記憶體問題時，除了結構體本身，要記得處理字串本身記憶體的回收。

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

    element_t *nownode = malloc(sizeof(element_t));
    assert(nownode);
    if (!nownode) {
        return false;
    }
    nownode->value = strdup(s);

    if (!nownode->value) {
        free(nownode);
        return false;
    }
    list_add(&(nownode->list), head);
    return true;
}

在 commit 時遇到 error

git commit
Following files need to be cleaned up:
queue.c
queue.c:69:5: error: Memory leak: nownode [memleak]
    return true;
    ^

Fail to pass static analysis.

最後的解決方式是將 &(nownode->next) 改成 &nownode->next 。

q_insert_tail

從 terry23304 看到可重用 q_insert_head 的建議，將插入 Head 的尾看作插入 Head->prev 的頭。

bool q_insert_tail(struct list_head *head, char *s)
{
    return q_insert_head(head->prev, s);
}

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

了解，先刪除此部份

container_of

#define container_of(ptr, type, member)                            \
    ({                                                             \
        void *__mptr = (void *) (ptr);                             \
        static_assert(__same_type(*(ptr), ((type *) 0)->member) || \
                          __same_type(*(ptr), void),               \
                      "pointer type mismatch in container_of()");  \
        ((type *) (__mptr - offsetof(type, member)));              \
    })

由已知結構體中的 某個成員起始位址 去獲得此成員所在之 結構體的起始位址。

利用成員起始位址ptr扣掉成員在結構體中相對位址。

避免非必要的項目列表 (即 * )，以清晰且明確的漢語書寫。

q_delete_dup

此函式的目的是要消除佇列中重複的字串節點。在條件判斷會有三種情況：

1. 目前的節點字串和前一個節點字串相同
2. 目前的節點字串和前一個節點字串不同，但和下一個節點字串相同
3. 目前的節點字串和前一個節點字串不同，且和下一個節點字串不同

前兩者皆為字串重複，第二種除了消除目前節點外，還需要更新紀錄重複字串之變數（ prob )

原本更新 prob 的寫法為直接透過 strdup 重新動態配置字串空間，紀錄最新重複字串。

if (prob == NULL || strcmp(prob, cur->value)) {
    // Check if the current node has the same string
    // as the next node
    if (next == NULL || strcmp(cur->value, next->value)) {
        continue;
    } else {
        // Update the prob if cur and next have the same string
        prob = strdup(cur->value);
    }
}
//printf("Free: %s\n", cur->value);
list_del(&cur->list);
free(cur->value);
free(cur);

當透過 make check 搭配 trace-06-ops.cmd 測試時，會發現有兩個配置的位置沒有被釋放

make check
  CC	queue.o
  LD	qtest
./qtest -v 3 -f traces/trace-06-ops.cmd
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
l = []
l = [tvzaist vfktis prljcykrc jxiswnclm]
l = [tvzaist vfktis prljcykrc jxiswnclm gerbil gerbil gerbil]
l = [tvzaist vfktis prljcykrc jxiswnclm gerbil gerbil gerbil lion lion]
l = [tvzaist vfktis prljcykrc jxiswnclm gerbil gerbil gerbil lion lion zebra zebra]
l = [gerbil gerbil gerbil jxiswnclm lion lion prljcykrc tvzaist vfktis zebra zebra]
l = [jxiswnclm prljcykrc tvzaist vfktis]
l = NULL
ERROR: There is no queue, but 2 blocks are still allocated

更仔細地印出目前釋放位置的字串內容才發覺，當透過 strdup 來更新 prob 的字串時，未釋放前一個 prob 字串的位置。

l = [gerbil gerbil gerbil jxiswnclm lion lion prljcykrc tvzaist vfktis zebra zebra]
Free: gerbil
Free: gerbil
Free: gerbil
Free: lion
Free: lion
Free: zebra
Free: zebra
Free Prob: zebra
...
ERROR: There is no queue, but 2 blocks are still allocated

在更新 prob 前，先釋放目前字串之位置，將 prob 設為 NULL ，再進行更新。

if (prob) {
    free(prob);
    prob = NULL;
}
prob = strdup(cur->value);

改為以下:

free(prob);
prob = strdup(cur->val);

注意看 free(3)。