# 2024q1 Homework1 (lab0)
contributed by < [`duckcone`](https://github.com/duckcone) >

## 開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.

$ 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) i7-6700 CPU @ 3.40GHz
    CPU family:          6
    Model:               94
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4000.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6799.81

## 指定的佇列操作
### q_new()
建立一個空佇列。利用 `malloc()` 配置一塊記憶體，並且將指標 `prev` 以及 `next` 都指向此位址。
在後續的測試中，發現原先程式碼並未考慮 `malloc` 失敗的問題，因此加入了判斷 `malloc` 是否成功的程式碼。
> commit: [5088d8b](https://github.com/duckcone/lab0-c/commit/5088d8bc30171726d16b3e46f9ca858b30e25283)

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

    head->prev = head;
    head->next = head;
    return head;

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

### q_free()
釋放佇列的空間。利用 `list_for_each_entry_safe` 拜訪鏈結串列的每個節點，並且使用 `q_release_element()` 釋放節點。其中 `q_release_element()` 的 parameter 為 `element_t` 型態。

### q_insert_head()
新增一個節點在佇列的起始位置。會呼叫 `element_new()` 函式來新增新的 `element_t`。最初的構想是 直接將 `element_t` 中的 `value` 直接指向所傳入的 parameter `s`

element_t *element_new(char *s)
{
    elemnt_t *new_element = malloc(sizeof(element_t));
    new_element->value = s;
    return new_element;
}

但經由 `make check` 執行之後，會產生以下訊息：

# Fill it with some values. First at the head
ERROR: Need to allocate and copy string for new queue element
l = [dolphin]
ERROR: Need to allocate and copy string for new queue element
l = [bear ih]
ERROR: Need to allocate and copy string for new queue element

因此將程式修正為動態分配所傳入字串長度 +1 大小的空間，並且利用 `strncpy()` 將 `s` 複製到新的空間。便可解決此問題。

element_t *element_new(char *s)
{
    elemnt_t *new_element = malloc(sizeof(element_t));
+    if (!new_element)
+        return NULL;
+    int length = strlen(s) + 1;
+    char *str = malloc(sizeof(char) * length);
+    strncpy(str, s, length);
+    new_element->value = str;
-    new_element->value = s;
    return new_element;
}

最後透過 `list_add()` 函式將節點新增在佇列的開頭位置。

#### 如果 `*s` 是 NULL pointer 呢？
看到 [2024 年系統軟體系列課程討論區](https://www.facebook.com/groups/system.software2024/permalink/1556863905091502/?mibextid=oMANbw) 社團中的這篇貼文所提到的問題，發現自己的程式碼無法確認使用者在新增節點時所輸入的字串為何，因此在 `q_insert_head()` 以及 `q_insert_tail()` 中新增了判斷字串的程式碼，透過 `if(!s || !*s)` 來確保指標 `s` 所指向的位址非 `NULL`或字串非 `NULL` 。

> commit: [15275b1](https://github.com/duckcone/lab0-c/commit/15275b1eb2e592217a1ee6b65f9c6de33441f308)

在執行 `make test` 時，出現以下錯誤訊息：

+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---     trace-11-malloc 0/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---     trace-12-malloc 0/6

:::danger
明確標示你參考的 GitHub 帳號名稱。
:::

判斷是 `element_new()` 函式出問題，在不知如何解決的情況下決定參考<s>其他人</s> 的方法，發現 2 個問題：
1. 其他人透過 `strdup()` 的方式將參數 `s` duplicate 一份，並且將節點的 `value` 指向其位址，因此我將原先的 `strncpy()` 更改為 `strdup()` 。
2. 在進行 `element_t *new_element = malloc(sizeof(element_t));` 之後並未判斷 `malloc()` 是否成功，因此加入判斷式，若 `malloc()` 失敗則釋放其記憶體並回傳 `NULL` 。

修改過後便可順利通過測試。
> commit:[15275b1](https://github.com/duckcone/lab0-c/commit/15275b1eb2e592217a1ee6b65f9c6de33441f308)

:::danger
allocate 的翻譯是「配置」，以區格 dispatch (分配/分發) 的翻譯。
:::

針對上述第 1 點，很明顯是我原先的<s>實做</s> 方式有問題。因此在重新檢視程式碼之後，發現我在 `char *str = malloc(sizeof(char) * length + 1);` 之後並未判斷是否<s>分配</s> 成功便進行 `strncpy()` ，因而導致 **dereferenced a NULL or invalid pointer** 的問題發生。在加入判斷式之後便解決了 Segmentation fault 的問題。

element_t *element_new(char *s)
{

    int length = strlen(s) + 1;
    char *str = malloc(sizeof(char) * length + 1);
+    if(!str) {
+        free(new_element);
+        free(str);
+        return NULL;
+    }
    memset(str, '\0', length + 1);
    strncpy(str, s, length);

### q_insert_tail()

:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/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$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

與 `q_insert_head()` 的<s>實做</s> 實作方式相同，透過呼叫 `element_new()` 函式來新增新的節點，並透過 `list_add_tail()` 將節點新增在佇列的尾端。

### q_remove_head()
原先的想法是先取得佇列開頭的節點位址，並且調整 `prev` 以及 `next` 所指向的位址。但是在進行 `$ make test` 後，發現在進行 `Test of insert_head and remove_head` 測試時會有以下錯誤訊息：

ERROR: Attempted to free unallocated block.  Address = 0x558a5a52e278
ERROR: Attempted to free unallocated or corrupted block.  Address = 0x558a5a52e278
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

在閱讀 `queue.h` 檔案時不夠仔細，忽略了以下針對 `q_remove_head()` 的說明：
> If sp is non-NULL and an element is removed, copy the removed string to `*sp` (up to a maximum of bufsize-1 characters, plus a null terminator.)

因此針對此函式進行修正。
> commit: [5f2037b](https://github.com/duckcone/lab0-c/commit/5f2037beadb855754af4418b6b3c4abb6708b5cf)

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
-    if (!head)
+    if (!head || list_empty(head))
+        return NULL;
+
+    element_t *head_element = list_first_entry(head, element_t, list);
+    if (!head_element)
         return NULL;
-    element_t *head_element = container_of(head, element_t, list);
-    head->next->prev = head->prev;
-    head->prev->next = head->next;
+    list_del(&head_element->list);
+
+    if (!sp)
+        return head_element;
+
+    memset(sp, '\0', bufsize);
+    strncpy(sp, head_element->value, bufsize);
+    INIT_LIST_HEAD(&(head_element->list));
     return head_element;
}

### q_delete_mid()
`q_delete_mid()` 在實作上與 `q_remove_head()` 及 `q_remove_tail()` 有所不同，主要差異在於 `q_delete_mid()` 需找出佇列中間節點，並釋放其記憶體，而 `q_remove_head()` 及 `q_remove_tail()` 僅將佇列開頭或是結尾的節點移除，但並未釋放其記憶體。

利用兩個指標 `head_ptr` 以及 `tail_ptr` 對 `head` 的 `prev` 以及 `next` 方向逐一探訪，當兩個指標相等時即為佇列中間的節點。透過 `list_entry()` 取得節點並將其釋放。
> commit: [ba59182](https://github.com/duckcone/lab0-c/commit/ba591829e44a320b647f564046df8bb892143247)

### q_reverse()
由於原先的佇列是以雙向鏈結串列實作，因此在對佇列反轉時需考慮 `prev` 以及 `next` 兩個指標的操作。下列程式碼與附圖為詳細的實作方式。

 list_for_each_safe (current, safe, head) {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
}

<s>
</s>

:::danger
使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記中。
:::