# 2022q1 Homework1 (lab0)
contributed by < `zhy62396` >
## 實驗環境
```shell
$ 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): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 94
Model name: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
Stepping: 3
CPU MHz: 3400.000
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 6799.81
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 8 MiB
NUMA node0 CPU(s): 0-7
```
## 作業要求
詳細閱讀 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 說明，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改
* q_new: 建立新的「空」佇列
* q_free: 釋放佇列所佔用的記憶體
* q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
* q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
* q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點
* q_release_element: 釋放特定節點的記憶體空間
* q_size: 計算目前佇列的節點總量
* q_delete_mid: 移走佇列中間的節點
* q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
* q_swap: 交換佇列中鄰近的節點
* q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
* q_sort: 以遞增順序來排序鏈結串列的節點
## 開發過程
首先查看標頭檔
- [ ] queue.h
```c
typedef struct {
/* Pointer to array holding string.
* This array needs to be explicitly allocated and freed
*/
char *value;
struct list_head list;
} element_t;
```
- [ ] list.h
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
### q_size
使用老師 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 所提供的程式碼
```c
int q_size(struct list_head *head)
{
if (!head) return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
:::warning
除了張貼程式碼，你應該說明並指出日後可改進之處。
:notes: jserv
:::
### q_new
#### 思考過程
* 1.首先要求一塊 element_t 大小的記憶體，若沒成功回傳 NULL
* 2.element_t 之 value 給值 (NULL)
* 3.element_t 內 list_head 之 prev 和 next 給值(指向自己)
:::danger
注意書寫規範：中英文間用一個半形空白字元區隔
:notes: jserv
:::
:::info
已修正
:::
```c
struct list_head *q_new()
{
element_t *q = malloc(sizeof(element_t));
if (q == NULL) {
return NULL;
}
q->value = NULL;
q->list.prev = &q->list;
q->list.next = &q->list;
return &q->list;
}
```
重新查看`list.h`，有 `INIT_LIST_HEAD` 函式可使用，取代指標宣告的部份
:::danger
請加上標點符號，這是正式的開發紀錄，不是抒發心情的 Dcard 文。
:notes: jserv
:::
:::info
已修正
:::
```c
struct list_head *q_new()
{
element_t *q = malloc(sizeof(element_t));
if (q == NULL) {
return NULL;
}
q->value = NULL;
INIT_LIST_HEAD(&q->list);
return &q->list;
}
```
重新查看文件，發現 queue 之開頭應為 list_head，後續接上的 node 才為 element_t
#### 思考過程（修改後）
* 1.首先要求一塊 list_head 大小的記憶體，若沒成功回傳 NULL
* 2.list_head 之 prev 和 next 給值(指向自己)
```c
struct list_head *q_new()
{
struct list_head *h = malloc(sizeof(struct list_head));
if (h == NULL) {
return NULL;
}
INIT_LIST_HEAD(h);
return h;
}
```
### q_free
`container_of`用來取得 struct 之起始點，知道某結構任一成員位址，即可知道該結構起始位址
1.若 list 為空則直接回傳
2.新增一個 `list_head` 指標 (tmp) 指向 head 之 next
3.若 tmp 不指向 head (只剩 head 的情況)
4.則先用 `container_of` 從 `list_head` 找出 `element_t` 起始位址
5.先將 tmp 指向下一個 `list_head` 再將 `element_t` 刪除
重複 3 ～ 5 直到只剩下 head
6.用 `container_of` 從 `list_head` 找出 `element_t` 起始位址
7.將 `element_t` 刪除
```c
void q_free(struct list_head *l)
{
if (l == NULL) {
return;
}
struct list_head *tmp = l->next;
element_t *e = NULL;
while (tmp != l) {
e = container_of(tmp, element_t, list);
tmp = tmp->next;
q_release_element(e);
}
e = container_of(tmp, element_t, list);
q_release_element(e);
}
```
重新查看作業描述，發現 head 為list_head， 釋放只要用 free 即可
重新查看 `list.h` 發現 `list_entry` 即為 `container_of`
```c
#define list_entry(node, type, member) container_of(node, type, member)
```
重新簡化程式碼
```c
void q_free(struct list_head *l)
{
if (l == NULL)
return;
struct list_head *tmp = l->next;
struct list_head *del = NULL;
while (tmp != l) {
del = tmp;
tmp = tmp->next;
q_release_element(list_entry(del, element_t, list));
}
free(l);
}
```
:::warning
TODO：list_entry 和 container_of 的使用時機
:::
### q_insert_head
查看 `list.h` 中相關的 kernel API，發現 `list_add` 對於此函式實做有幫助
此函式為在 head 後面插入一個 node
```c
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
步驟
1.判斷 queue 是否為空，若是則回傳 false
2.分配一個 `element_t` 大小的記憶體區塊 e，若不成功則回傳 false
3.分配一塊長度 s 個 char 型態的記憶體大小，並將 e 之 value 指向該塊記憶體
4.將記憶體內容由 s 複製到 e->value
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *e = malloc(sizeof(element_t));
if (e == NULL)
return false;
e->value = malloc(sizeof(char) * (strlen(s) + 1));
if (e->value == NULL) {
free(e);
return NULL;
}
memcpy(&e->value, s, strlen(s) + 1);
list_add(&e->list, head);
return true;
}
```
發現先分配 `element_t` ，再將分配失敗和 queue 為 NULL 的情況一起判斷，可以減少程式碼
然後 `element_t` 發現要找 value 不用 `＆`
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *e = malloc(sizeof(element_t));
if (e == NULL || head == NULL)
return false;
e->value = malloc(strlen(s) + 1);
if (e->value == NULL) {
free(e);
return false;
}
memcpy(e->value, s, strlen(s) + 1);
list_add(&e->list, head);
return true;
}
```
### q_insert_tail
同樣使用 `list.h` 中相關的 kernel API `list_add_tail`
此函式為在 `head` 和 `head->prev` 之間插入一個 node（相當於插入 list 尾端）
```c
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
```c
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *e = malloc(sizeof(element_t));
if (e == NULL || head == NULL)
return false;
e->value = malloc(strlen(s) + 1);
if (e->value == NULL) {
free(e);
return false;
}
memcpy(e->value, s, strlen(s) + 1);
list_add_tail(&e->list, head);
return true;
}
```
### q_remove_head
### q_remove_tail
### q_release_element
### q_delete_min
### q_delete_dup
### q_swap
### q_reverse
### q_sort
Sign in with Wallet
Connect another wallet