# 2022q1 Homework1 (lab0)
contributed by < `chrisliu430` >
> [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)

## 實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          16
On-line CPU(s) list:             0-15
Thread(s) per core:              2
Core(s) per socket:              8
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           165
Model name:                      Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
Stepping:                        5
CPU MHz:                         2900.000
CPU max MHz:                     4800.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5799.77
Virtualization:                  VT-x
L1d cache:                       256 KiB
L1i cache:                       256 KiB
L2 cache:                        2 MiB
L3 cache:                        16 MiB
NUMA node0 CPU(s):               0-15

## 針對佇列的操作

### q_new
> 4846696

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q) {
        return NULL;
    }
    q->prev = q->next = q;
    return q;
}

先使用 `malloc` 對 `list_head` 做記憶體分配的動作，接下來檢測是否有分配，若沒有分配就回傳 `NULL` ；若有分配則對 `struct list_head` 做初始化，將 `prev` 及 `next` 指回自身位址。
> 參考 [laneser](https://hackmd.io/@laneser/linux2022_lab0) 得知 `list.h` 中有提供 `INIT_LIST_HEAD` 可以使用

- 改進程式碼
> b3d85fe

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

### q_free
### q_size
> 4846696

int q_size(struct list_head *head)
{
    if (!head) {
        return 0;
    }
    int cnt = 0;
    struct list_head *n;
    for (n = head->next; n != head; n = n->next) {
        cnt++;
    }
    return cnt;
}

先判斷 `head` 是否為不存在，若不存在則 `Queue Size` 為0；存在時在利用 `list_head`
環形結構計算 `Queue` 中內存有多少元素，結束條件為節點被指派的位址與 `list_head` 的開頭相同。
> 宣告 `struct list_head` 的指標時，並沒有給予初始值，於是往內移至 `for loop` 內

- 改進程式碼
> b3d85fe

int q_size(struct list_head *head)
{
    if (!head) {
        return 0;
    }
    int cnt = 0;
    for (struct list_head *n = head->next; n != head; n = n->next) {
        cnt++;
    }
    return cnt;
}

### q_insert_head
> 4846696

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

先分配記憶體空間給 `element_t` 作為要被儲存的元素的節點，接下來才判斷串接資料的節點 `head` 是否不存在或分配 `element_t` 空間時是否有分配，若沒有就將剛剛分配給予 `element_t` 的空間給釋；若 `head` 存在及 `element_t` 有分配到記憶體的情況下，則將使用 `strdup` 對要儲存的字串分配記憶體空間，並採用在 `list.h` 中現有的 `list_add` 對新增節點加入在開頭的部份。
> 參考 [laneser](https://hackmd.io/@laneser/linux2022_lab0) 的開發筆記，對於 `insert` 的處理是先判斷 `head` 是否存在。
> 我的寫法是先創建 `element_t` 再判斷可否正常插入 `node` ，這個寫法雖然可以正常用作，但根據所查詢的資料 [Is it good practice to free a NULL pointer in C?](https://stackoverflow.com/questions/6084218/is-it-good-practice-to-free-a-null-pointer-in-c) 中提到不要對 `NULL` 指標坐存取，原因是因為會多存取不必要的程式碼，即使 `free` 函式傳入 `NULL` 不會發生任何問題。

- 改進程式碼
> b3d85fe

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

### q_insert_tail
> 4846696

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

先分配記憶體空間給 `element_t` 作為要被儲存的元素的節點，接下來才判斷串接資料的節點 `head` 是否不存在或分配 `element_t` 空間時是否有分配，若沒有就將剛剛分配給予 `element_t` 的空間給釋；若 `head` 存在及 `element_t` 有分配到記憶體的情況下，則將使用 `strdup` 對要儲存的字串分配記憶體空間，並採用在 `list.h` 中現有的 `list_add_tail` 對新增節點加入在結尾的部份。

- 改進程式碼
> b3d85fe

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

### q_remove_head
### q_remove_tail
### q_delete_mid
### q_delete_dup
### q_swap
### q_reverse
### q_sort