# 2024q1 Homework1 (lab0)
contributed by < `jjj0425` >

2024/3/11已退選
> 所以呢？就放棄成為更好的自己的機會嗎？
### Reviewed by `kkkkk1109`
* 建議在看到新的方法，可以於提供教材中查詢此用法，如 q_free 中使用到 `__glibc_unlikely` ，可以稍微解釋一下此巨集定義，和翻查[GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)中的相關敘述，並以自己的方式說明，以幫助理解
### Reviewed by `jychen0611`
* git commit message 約有一半無內文，以`what? why? how?` 描述每次更改的內容
* 佇列功能實作尚未完整

### Reviewed by `jujuegg`
- 貼過多程式碼在 hackmd

### Reviewed by `Kuanch`

### Reviewed by `kevinzxc1217`

## 開發環境

$ 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:         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
    Thread(s) per core:  2
    Core(s) per socket:  16
    Socket(s):           1
    Stepping:            1
    CPU max MHz:         5200.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4224.00
Caches (sum of all):     
  L1d:                   640 KiB (16 instances)
  L1i:                   768 KiB (16 instances)
  L2:                    24 MiB (10 instances)
  L3:                    30 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-23

:::danger
說好的進度呢？
>:moyai: : 收到！馬上來 :man-running:
:::

## 指定的佇列操作
在開始之前，釐清題目的時候有一些不太了解的地方，這裡感謝 [kart81604](https://hackmd.io/Cykxa6NdT0WDA3FE37rKhg?both) 的筆記裡提供的以下內容，讓我對整體架構更清楚。
>
看完這張圖意識到，佇列形式應為此圖表示的， Head 型別為 `list_head`，而 Node 0, Node 1, Node 2 的型別為 `element_t`。
:::info
`element_t` 的結構由 `char *value` 與 `struct list_head list` 組成，因此圖上 Node 中的
`int Data_A`、`int Data_B`、`int Data_C` 替換成 `char *value` 會更完整代表此題的形式。
:::
### `q_new`

>雖然是一個似簡單的功能，但實作時總是擔心忽略**細節**，這裡感謝 [alanjian85](https://hackmd.io/@alanjian85/lab0-2023) 以及 [25077667](https://hackmd.io/@25077667/lab0-2023) 兩位前人的智慧，秉持著**不疑有他處有疑**的精神，參考前人的作法，盡可能把功能做好。

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

根據 [malloc(3)](https://man7.org/linux/man-pages/man3/malloc.3.html#top_of_page):
> On error, these functions return NULL and set errno. Attempting to allocate more than PTRDIFF_MAX bytes is considered an error, as an object that large could cause later pointer subtraction to overflow.

如果 `malloc()` 失敗，得到的指標值會是 `NULL`，~~然而 `head` 變數仍會佔用記憶體空間，因此最好還是將其 `free()`~~
:::warning
後來在 ChatGPT 中得到以下回答：
在 C 或 C++ 中，指標變數本身不需要釋放。 只有透過動態記憶體分配（如 malloc、calloc、realloc 等）分配的記憶體需要手動釋放。
如果 head 是指向結構體 list_head 的指針，並且沒有透過 malloc 或類似函數分配內存，則不需要明確釋放 head。 例如，如果 head 被宣告為局部變數或指向一個靜態分配的結構體，它的記憶體會在離開其作用域或程式結束時自動釋放。
:::
修改後的內容：
>commit: [d011533](https://github.com/sysprog21/lab0-c/commit/d01153368c447b6b69b713b8b8a5f54221856388)

@@ -15,22 +15,15 @@
-  if (!head) {
-      free(head);
-      return NULL;
-  }
-  INIT_LIST_HEAD(head);
-  return head;

+  if (head)
+      INIT_LIST_HEAD(head);
+  return head

### `q_free`
一開始的想法很簡單，只要確認 `head` 非空指標並且指向內容也非空，就用 `list_for_each_safe` 走訪佇列並且依序釋放空間，值得一提的是，實作過程看到 [25077667](https://hackmd.io/@25077667/lab0-2023) 使用 `__glibc_unlikely` 提示編譯器該條件的可能性較低，這樣編譯器就會更傾向於將控制流設計為預測該條件為假。
雖然這操作讓我為之驚豔，然而我暫時未能提出證據證明該方法是否對於整體效能具有效的提升，因此暫且以常見易讀的寫法完成。

void q_free(struct list_head *head)
{
    if (!head || list_empty(head)) {
        free(head);
        return;
    }
    
    struct list_head *cur = NULL, *safe = NULL;
    list_for_each_safe (cur, safe, head)
        q_release_element(container_of(cur, element_t, list));
    free(head);
}

後來又看到 [alanjian85](https://hackmd.io/@alanjian85/lab0-2023) 所說：
>如果 `head` 在這個函式執行的一開始就是空的，釋放元素的迴圈就不會執行，而是直接開始釋放起始節點，因此這種狀況不需要額外處理也能得到正確的結果。

所以再次精簡程式碼：
> commit: [58f8c77](https://github.com/sysprog21/lab0-c/commit/58f8c77d5f6e4f8c83f222362b7175d9bb06b307)

-  if (!head || list_empty(head)) {
-      free(head);	
-      return;
-  }
+  if (!head)
+      return;

### `q_insert_head`
首先檢查若傳入的 `head` 為 `NULL` ，則不做任何動作，否則配置一個 `element_t` 的空間並且使用 [strdup(3)](https://man7.org/linux/man-pages/man3/strdup.3.html) 將字串複製到新的空間，並傳回位址給 `value` ，這裡要注意檢查若複製字串時因任何問題導致回傳空指標，要記得釋放當初為 `element` 配置的記憶體空間，否則會造成記憶體洩漏。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *element = malloc(sizeof(element_t));
    if (!element)
        return false;
    element->value = strdup(s);
    if (!element->value) {
        free(element);
        return false;
    }
    list_add(&element->list, head);
    return true;
}

### `q_insert_tail`
`q_insert_tail` 本質上與 `q_insert_head` 行為一樣，並且在雙向鍊結串列中，可以直接以 `head->prev` 取得最後一個節點的位置，值得一提的是，因為在 `q_insert_head` 程式碼中會檢查 `head` 指標是否為 `NULL`，因此**我認為**在呼叫 `q_insert_head` 之前無須再做一次檢查。

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

### `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`