# 2021q1 Homework1 (lab0)
contributed by < `Chungchiyu` >
###### tags: `linux2021`
## 作業簡介
本次作業是 Linux kernal 的第一次作業，目標是更深入的認識 C 語言，並且熟悉記憶體的操作。通過 lab0 的 queue 例題練習 Linked list 的撰寫並學習一些基本的指標操作。
作業過程中會運用到其他的工具，如：git 版本控制系統、GNU/Linux 開發工具等。利用這些工具可以熟練的寫程式，並檢查程式內容。
## 預期目標
- [x] queue.c 的完整實作
- [ ] make test 達到滿分
- [ ] 學習 Address Sanitizer
- [ ] 以 Valgrind 分析記憶體問題
- [ ] 持續更新程式
## 實作進度(更新中)
## 作業內容
### queue.c 實作
#### 內容
1. [q_new](#q_new)
2. [q_free](#q_free)
3. [q_insert_head](#q_insert_head)
4. [q_insert_tail](#q_insert_tail)
5. [q_remove_head](#q_remove_head)
6. [q_size](#q_size)
7. [q_reverse](#q_reverse)
8. [q_sort](#q_sort)
---
:::danger
如果只是列出程式碼，而沒有你的洞見和觀察，那就不算「開發紀錄」，請更正！
:notes: jserv
:::
#### `q_new`
:::spoiler 打開
```c=
queue_t *q_new()
{
/* allocate memory to q */
queue_t *q = malloc(sizeof(queue_t));
/* check if something goes wrong when allocating memory */
if (!q) {
return NULL;
}
/* initialize member in q */
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
:::
#### `q_free`
:::spoiler 打開
```c=
void q_free(queue_t *q)
{
/* Check if q is NULL */
if (!q)
return;
/* Steping by steps to free list_ele_t in q */
while (q->head) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
:::
#### `q_insert_head`
:::spoiler 打開
```c=
bool q_insert_head(queue_t *q, char *s)
{
/* check if q is NULL */
if (!q)
return false;
/* allocate memory to new list_ele_t for new head */
list_ele_t *newh = malloc(sizeof(list_ele_t));
//if alloctaion failed
if (!newh)
return false;
/* get the size of input char data, +1 for '\0' */
size_t value_size = strlen(s) + 1;
/* allocate memory for the input data */
newh->value = (char *) malloc(value_size * sizeof(char));
//if allocation failed
if (!newh->value) {
free(newh); //don't forget to free the memory that allocate for newh
return false;
}
/* copy input data into newh->value */
strncpy(newh->value, s, value_size);
/* insert newh into q*/
newh->next = q->head;
q->head = newh;
/* make head and tail the same if only one element in queue */
if (q->size == 0)
q->tail = newh;
q->size++;
return true;
}
```
:::
#### `q_insert_tail`
:::spoiler 打開
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
size_t value_size = strlen(s) + 1;
newt->value = (char *) malloc(value_size * sizeof(char));
if (!newt->value) {
free(newt);
return false;
}
//tail->next should be NULL
newt->next = NULL;
strncpy(newt->value, s, value_size);
/* if queue is empty just use ih to fill an element */
if (!q->head)
q_insert_head(q, s);
/* if not empty insert from tail */
else {
newt->next = q->tail->next;
q->tail->next = newt;
q->tail = newt;
q->size++;
}
return true;
}
```
:::
#### `q_remove_head`
:::spoiler 打開
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* if queue doesn't exist or empty*/
if (!q || !q->head)
return false;
/* if sp isn't NULL */
if (sp) {
/* if buffer size is lager than value's then let copySize to be value size, on the other way let copySize to be buffer size */
size_t copySize = (bufsize - 1 > strlen(q->head->value)
? strlen(q->head->value)
: bufsize - 1;)
sp[copySize] = '\0';
strncpy(sp, q->head->value, copySize);
}
/* free the origin head of queue and its value*/
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
:::
#### `q_size`
:::spoiler 打開
```c=
int q_size(queue_t *q)
{
if (!q)
return 0;
/* return the size of queue */
return q->size;
}
```
:::
#### `q_reverse`
:::spoiler 打開
```c=
void q_reverse(queue_t *q)
{
/* if queue is empty or it has only one element */
if (!q || q->size < 2)
return;
/* three list elements are represent previous, now, and next node */
list_ele_t *prev = NULL, *now = q->head, *next = NULL;
/* reversing the nodes */
while (now != NULL) {
next = now->next;
now->next = prev;
prev = now;
now = next;
}
q->tail = q->head;
q->head = prev;
return;
}
```
:::
#### `q_sort`
:::spoiler {state=open} 打開
```c=
void q_sort(queue_t *q)
{
/* if queue is empty or has only onr element */
if (!q || q->size < 2)
return;
/* use mergesort to sort the queue */
mergeSort(&(q->head));
/* relocating tail position */
while (q->tail->next) {
q->tail = q->tail->next;
}
}
void mergeSort(list_ele_t **head)
{
if (!(*head) || !(*head)->next)
return;
list_ele_t *fast = (*head)->next;
list_ele_t *slow = *head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
slow = (*head);
mergeSort(&slow);
mergeSort(&fast);
while (slow && fast) {
int compare = strcasecmp(slow->value, fast->value);
if (compare == 0 ? strcmp(slow->value, fast->value) < 0 : compare < 0) {
(*head) = slow;
slow = slow->next;
} else {
(*head) = fast;
fast = fast->next;
}
head = &((*head)->next);
}
(*head) = slow ? slow : fast;
}
```
:::
### 遇到的問題(2021/03/17)
1. 在 mergeSort 中，我在最後排大小時一直遇到指向問題。原先我是參考 lab0 中的 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) ，我選擇不用 recursive 的方式來做 merge 而是用 pseudo node 來做，因為我覺得 recursive 會用到太多的 stack 記憶體，但分解還是用遞迴否則程式會太複雜。
```c=
merge_sort(&slow);
merge_sort(&fast);
//lines are the same with current's above
list_ele_t **ptr = NULL;
(*head) = NULL;
while (slow && fast) {
int compare = strcasecmp(slow->value, fast->value);
if (compare == 0 ? strcmp(slow->value, fast->value) < 0 : compare < 0) {
(*ptr)->next = slow;
slow = slow->next;
} else {
(*ptr)->next = fast;
fast = fast->next;
}
if (!(*head))
(*head) = (*ptr)->next;
(*ptr) = (*ptr)->next;
}
(*ptr)->next = slow ? slow : fast;
```
假設以下：
```graphviz
digraph mergeSort{
node[shape=record]
A [label="<f0> 1 |<f1> 13 |<f2> 17 |<f3> 9"]
B [label="<f0> 1 |<f1> 13"] C [label="<f0> 17 |<f1> 9"]
D [label="<f0> 1"] E[label="<f0> 13"] F[label="<f0> 17"] G[label="<f0> 9"]
A->B A->C
B:f0->D B:f1->E C:f0->F C:f1->G
}
```
此時當 recursive 的 mergeSort 已經分到這四個數並要排大小時。
(也就是程式碼到↓這幾段時)
```c=
fast = slow->next;
slow->next = NULL;
slow = (*head);
mergeSort(&slow);
mergeSort(&fast);
```
第一行 mergeSort 會取出 `slow->value = 1` 的 slow 位置
第二行 mergeSort 會取出 `fast->value = 13` 的 fast 位置
然後宣告一個指標的指標來存取指標位置，並先指向 NULL。再讓 head 也指向 NULL 作為辨識 head 是否有指向最小述職的位置。
然後進入以下迴圈：
```c=
while (slow && fast) {
int compare = strcasecmp(slow->value, fast->value);
if (compare == 0 ? strcmp(slow->value, fast->value) < 0 : compare < 0) {
(*ptr)->next = slow;
slow = slow->next;
} else {
(*ptr)->next = fast;
fast = fast->next;
}
if (!(*head))
(*head) = (*ptr)->next;
(*ptr) = (*ptr)->next;
}
```
首先，當 slow->value < fast->value 進入 `if` 、反之進入 `else`， 因為 1 > 13 進入 `if` ，此時： `(*ptr)->next = slow;`
```graphviz
digraph mergeSort_a{
node[shape=box]
ptr_next[label="ptr_next=slow"]
NULL_1[label="NULL"]
NULL_2[label="NULL"]
ptr->ptr_next->1->NULL_1
fast->13->NULL_2
{rank=same;ptr ptr_next}
{rank=same;1 NULL_1 13 NULL_2}
}
```
然後：`slow = slow->next`
```graphviz
digraph mergeSort_b{
node[shape=box]
NULL_1[label="NULL"]
NULL_2[label="NULL"]
ptr->ptr_next->1->NULL_1
fast->13->NULL_2
slow->NULL_1
{rank=same;ptr ptr_next}
{rank=same;1 NULL_1 13 NULL_2}
}
```
再來因為 `*head = NULL` 所以 `(*head) = (*ptr)->next`
```graphviz
digraph mergeSort_c{
node[shape=box]
ptr_next[label="head=ptr_next"]
NULL_1[label="NULL"]
NULL_2[label="NULL"]
ptr->ptr_next->1->NULL_1
fast->13->NULL_2
slow->NULL_1
{rank=same;ptr ptr_next}
{rank=same;1 NULL_1 13 NULL_2}
}
```
接著 `(*ptr) = (*ptr)->next`
```graphviz
digraph mergeSort_d{
node[shape=box]
ptr[label="head=ptr=ptr->next"]
NULL_1[label="NULL"]
NULL_2[label="NULL"]
ptr->1->NULL_1
fast->13->NULL_2
slow->NULL_1
{rank=same;ptr slow}
{rank=same;1 NULL_1 13 NULL_2}
}
```
最後：
```
(*ptr)->next = slow ? slow : fast;
```
```graphviz
digraph mergeSort_d{
node[shape=box]
ptr[label="head=ptr"]
ptr_next[label="ptr_next=fast"]
NULL_1[label="NULL"]
NULL_2[label="NULL"]
ptr->1->13
ptr_next->13->NULL_2
slow->NULL_1
{rank=same;ptr ptr_next}
{rank=same;1 NULL_1 13 NULL_2}
}
```
:::warning
跳出這個 recursive 後會取得 head 的位置，程式錯誤。但我抓不出錯誤。
:::
2. 在 mergeSort 中，我在最後排大小時一直遇到指向問題，所以我借用了 [`Masa1u`](https://github.com/Masa1u/lab0-c/blob/master/queue.c) 的這段程式碼來改。假設以下：
```graphviz
digraph mergeSort{
node[shape=record]
A [label="<f0> 1 |<f1> 13 |<f2> 17 |<f3> 9"]
B [label="<f0> 1 |<f1> 13"] C [label="<f0> 17 |<f1> 9"]
D [label="<f0> 1"] E[label="<f0> 13"] F[label="<f0> 17"] G[label="<f0> 9"]
A->B A->C
B:f0->D B:f1->E C:f0->F C:f1->G
}
```
此時當 recursive 的 mergeSort 已經分到這四個數並要排大小時。
(也就是程式碼到↓這幾段時)
```c=
fast = slow->next;
slow->next = NULL;
slow = (*head);
mergeSort(&slow);
mergeSort(&fast);
```
第一行 mergeSort 會取出 `slow->value = 1` 的 slow 位置
第二行 mergeSort 會取出 `fast->value = 13` 的 fast 位置
然後進入以下迴圈：
```c=
while (slow && fast) {
int compare = strcasecmp(slow->value, fast->value);
if (compare == 0 ? strcmp(slow->value, fast->value) < 0 : compare < 0) {
(*head) = slow;
slow = slow->next;
} else {
(*head) = fast;
fast = fast->next;
}
head = &((*head)->next);
}
(*head) = slow ? slow : fast;
```
當 slow->value < fast->value 進入 `if` 、反之進入 `else`， 因為 1 > 13 進入 `if` ，此時： `(*head) = slow;`
```graphviz
digraph mergeSort_1{
node[shape=box]
head[label="head=slow"]
NULL_1[label="NULL"]
NULL_2[label="NULL"]
head->1->NULL_1 fast->13->NULL_2
{rank=same;1 NULL_1 13 NULL_2}
}
```
然後： `slow = slow->next`
```graphviz
digraph mergeSort_2{
node[shape=box]
NULL_1[label="NULL"]
NULL_2[label="NULL"]
slow->NULL_1
head->1->NULL_1 fast->13->NULL_2
{rank=same;1 NULL_1 13 NULL_2}
}
```
然後： `head = &((*head)->next);`
```graphviz
digraph mergeSort_3{
node[shape=box]
NULL_1[label="NULL"]
NULL_2[label="NULL"]
head->NULL_1 1->NULL_1
slow->NULL_1 fast->13->NULL_2
{rank=same;1 NULL_1 13 NULL_2}
}
```
最後： `(*head) = slow ? slow : fast;`
```graphviz
digraph mergeSort_4{
node[shape=box]
NULL_1[label="NULL"]
NULL_2[label="NULL"]
head[label="head=fast"]
1->NULL_1 slow->NULL_1
head->13->NULL_2
{rank=same;1 NULL_1 13 NULL_2}
}
```
:::warning
跳出 `mergeSort(&slow);` 後使外一層的 `slow->value = 13`
但是原本的 1 就這樣消失了???
我就這樣一直卡在這裡，卡了幾十個小時，明明可以編譯通過並且跑測試出來也都是對的，但我邏輯上一直都想不通。
:::
:::info
心得：我光是寫第一個作業的第一個目標就花了不下幾十個小時，我深知自己基本功不足，光是處理最基本的課題就花了一堆時間，但是我還是想要學好這門課，所以只能慢慢來。
:::
Sign in with Wallet
Connect another wallet