# 2021q1 Homework1 (lab0)
[作業內容](https://hackmd.io/@sysprog/linux2021-lab0)
[github](https://github.com/ShaneDocument/Linux-Kernel-Internals-lab0-c)
## 7/31
[7/31 commit](https://github.com/ShaneDocument/Linux-Kernel-Internals-lab0-c/commit/ae506bc8900257ce2bcbe5950aa2e2b1b2c51a3b)
### queue.c
#### **queue_t \*q_new()**
如果 malloc return NULL，則代表 q 被配置NULL，依照原文註解要求，直接回傳NULL即可
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
if (q == NULL) {
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
#### **void q_free(queue_t \*q)**
* 利用 while loop 釋放所走 element 與其 string 的記憶體
* 利用tmp來存放 queue head 的 next，釋放 queue head 後，再把queue head 指向 tmp
:::info
第 3 行的判斷一開始沒有加上去，後來跑 make check 有出現 segmentation fault，才知道這一塊有錯誤
:::
```c=
void q_free(queue_t *q)
{
if (!q)
return;
/* TODO: How about freeing the list elements and the strings? */
while (q->head != NULL) {
list_ele_t *tmp = q->head->next;
free(q->head->value);
free(q->head);
q->head = tmp;
}
/* Free queue structure */
free(q);
}
```
#### **bool q_insert_head(queue_t \*q, char \*s)**
* 首先，若 q 為 NULL，則 return false
* 若 malloc 的值為 NULL，則也要 return false
* 真正開始 insert 了！
* 先計算出傳入的 string 的大小，加上 1 是為了 '\0'
* 配置 strSize 給newh->value
* 判定 tail 是否為 NULL
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
list_ele_t *newh;
/* TODO: What should you do if the q is NULL? */
newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
size_t strSize = strlen(s) + 1;
newh->value = malloc(sizeof(char) * strSize);
snprintf(newh->value, strSize, "%s", s);
q->size++;
if (!q->tail) {
q->tail = newh;
}
newh->next = q->head;
q->head = newh;
return true;
}
```
### 心得
老實說，雖然我是資工系的碩士生，但對底層還是一竅不通。必須承認以上的程式碼有部分參考之前修課的大神們。希望以後可以自己寫出漂亮的c code
### 問題
1. 為何在 q_insert_head 中，要先 allocate memory 給 newh->value 呢？為何不能直接把 s 值傳遞給newh->value?
```c=
newh->value = s;
```
2. snprintf 與 sprintf 有何差異？
## 8/1
[8/1 commit](https://github.com/ShaneDocument/Linux-Kernel-Internals-lab0-c/commit/14ec8b94221f99b824cb6865f714c78c98ae9b71)
### queue.c
#### **bool q_insert_tail(queue_t \*q, char \*s)**
一開始作法跟 q_insert_head 很像。程式碼內有我自己打的註解，如果 q->tail = NULL，表示與 insert_head 是一樣的步驟，所以直接把結果寫在 if 判斷式內。
後來的作法與 insert_head 有一點不太一樣，這部分可以對照著程式碼去思考。
```c=
bool q_insert_tail(queue_t *q, char *s)
{
return false;
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
size_t strSize = strlen(s) + 1;
newt->value = malloc(sizeof(char) * strSize);
snprintf(newt->value, strSize, "%s", s);
q->size++;
if (!q->tail) {
q->tail = newt;
newt->next = q->head;
q->head = newt;
/* If the tail is NULL, the whole queue is empty. So, inserting tail is
* same as inserting head. */
return true;
}
q->tail->next = newt;
q->tail = newt;
q->tail->next = NULL;
return true;
}
```
#### **bool q_remove_head(queue_t \*q, char \*sp, size_t bufsize)**
特別把這個 function 的註解貼上來，主要是因為自己不太懂他的要求是什麼。
一開始看大概知道是要把 remove 的內容貼到 sp 上，可能是要實作出類似 stack 的 pop 之類的功能（ remove 之後可以取到值），但那個 buffer 有點不是太明白，因此這個部分參考了之前修課的同學的 code ，大概懂意思之後，就自己寫出來了。
```c=
/*
* Attempt to remove element from head of queue.
* Return true if successful.
* Return false if queue is NULL or empty.
* 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.)
* The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || q->size == 0)
return false;
list_ele_t *rmvtarget = q->head;
q->head = q->head->next;
if (sp) {
size_t slen = strlen(rmvtarget->value);
size_t spSize = (bufsize > slen) ? bufsize - 1 : slen;
memset(sp, '\0', spSize + 1);
snprintf(sp, spSize, "%s", rmvtarget->value);
}
free(rmvtarget->value);
free(rmvtarget);
q->size--;
return true;
}
```
#### **int q_size(queue_t \*q)**
要注意，如果 q 為 NULL，還是回傳個 0
```c=
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
#### **void q_reverse(queue_t \*q)**
前陣子刷 leetcode、codility 有解過一樣的題目，不過當時是用 recursion 去解的，所以當下思考了很久。後來參考了大神的解法，果然用 iteration 就可以輕鬆解出來。
用三個 pointer 分別指向：前一個( prev )、現在( current )、下一個( next )，有點像過去、現在、緯來的概念。然後 current 往回指向 prev，接著他們三個都往前移動並重複上述的作法，即可完成 reverse。
要注意的是，第一次忘記加上第 21 行，會造成錯誤。也許其他強者有更好的作法。
```c=
void q_reverse(queue_t *q)
{
if (!q)
return;
if (q->size <= 1)
return;
list_ele_t *prev = q->head;
list_ele_t *current = q->head->next;
list_ele_t *next = q->head->next->next;
do {
current->next = prev;
if (!next)
break;
prev = current;
current = next;
next = next->next;
} while (current);
list_ele_t *tmp = q->head;
q->head = q->tail;
q->tail = tmp;
q->tail->next = NULL;
}
```
### 心得
今天實作出四個 function，難度不高，我並沒有參考太多，大概只有 remove 那裡有偷看一下強者們是怎麼理解這塊的。
每一次實作完一個 function 後，都會用 qtest 去測試，大多沒什麼大問題，功能性都有出來。不過，我用 make test 去測試，只拿到 59 分。其實不太知道剩下 sort 沒做完的話，實際會拿到幾分，但感覺有點太低了，因此我認為我的功能上應該有瑕疵，最大的可能就是 remove_head 那裡。
然後，我有使用到 **Address Sanitizer** 來幫我分析，卻出現了 global-buffer-overflow。看起來是 console.c 那裡有狀況，但我沒動到他，不太清楚原因。這幾天先搞懂 **Address Sanitizer** 好讓我知道它的報告怎麼看。
## 8/2
[8/2 commit](https://github.com/ShaneDocument/Linux-Kernel-Internals-lab0-c/commit/60dda4f636b2dcdde566624e1cde326577fb1e56)
### queue.c
#### insert 系列
使用 make test 後發現 insert head、inset tail 有錯誤，一開始抓不太到原因，後來才知道是幫新的 head 或 tail 的 **value** malloc 的時候，沒有去針對 NULL 的部分做處理。
於是，在 q_insert_head ( Line 12-15 ) 與 q_insert_tail ( Line 11-14 ) 新增了判斷。
要注意的是，如果 value 確實被指派為 NULL，則整個 list_ele_t 要被釋放（ free ）。
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
size_t strSize = strlen(s) + 1;
newh->value = malloc(sizeof(char) * strSize);
if (!newh->value) {
free(newh);
return false;
}
snprintf(newh->value, strSize, "%s", s);
q->size++;
if (!q->tail) {
q->tail = newh;
}
newh->next = q->head;
q->head = newh;
return true;
}
```
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
size_t strSize = strlen(s) + 1;
newt->value = malloc(sizeof(char) * strSize);
if (!newt->value) {
free(newt);
return false;
}
snprintf(newt->value, strSize, "%s", s);
q->size++;
if (!q->tail) {
q->tail = newt;
newt->next = q->head;
q->head = newt;
/* If the tail is NULL, the whole queue is empty. So, inserting tail is
* same as inserting head. */
return true;
}
q->tail->next = newt;
q->tail = newt;
q->tail->next = NULL;
return true;
}
```
#### **bool q_remove_head(queue_t \*q, char \*sp, size_t bufsize)**
因為在 make test 的時候，也發現 remove_head 有問題，所以看一下。發現第 17 行的邏輯有問題，後來發現是英文理解力不夠。
根據 comment ，大概是說：sp 的大小最大就是 bufsize-1 個char，再加上一個空字串。
於是稍微改變一下第17行的邏輯：如果 bufsize 比較大，則使用 target 的 size 即可（夠用），如果 target 的 size 比較大，則因為最大就是使用 bufsize，所以指派給 sp 的量為 bufsize。
```c=
/*
* Attempt to remove element from head of queue.
* Return true if successful.
* Return false if queue is NULL or empty.
* 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.)
* The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || q->size == 0)
return false;
list_ele_t *rmvtarget = q->head;
q->head = q->head->next;
if (sp) {
size_t slen = strlen(rmvtarget->value) + 1;
size_t spSize = (bufsize > slen) ? slen : bufsize - 1;
memset(sp, '\0', spSize + 1);
snprintf(sp, spSize + 1, "%s", rmvtarget->value);
}
free(rmvtarget->value);
free(rmvtarget);
q->size--;
return true;
}
```
#### **void q_sort(queue_t \*q)**
這部分我分成三個 function 來實作，分別是：merge、mergeSort 和原本的 q_sort。
**q_sort**
這部分很簡單，就只是先初步的判定 q 是否為 NULL 以及是否只有 0 或 1 個 element （不必sort了）
之後直接 call mergeSort！
```c=
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(queue_t *q)
{
if (!q)
return;
if (q->size <= 1)
return;
q->head = mergeSort(q, q->head);
}
```
每個人的實作方法好像都不一樣，先說說我的想法：因為這個 queue 還需要去維護 head 和 tail，所以傳參數的時候我很直觀的覺得，應該把 q 給傳進去，這樣在排序過程中才可以更新 tail 和 head 的部分。
**mergeSort**
這個 function 我寫的算是蠻 general 的 mergeSort。先判斷進來的 head 有幾個 element，如果只有 1 個或 0 個，那就直接 return 這個 head 即可。
之後利用 fast、slow 的方法，切割出兩個 list。
要注意的是，slow->next 才是指向中間 node 的，而第 11 行的作法就是在記錄這個node，並在第 12 行把上半部的 list 的尾端指向 NULL，以完成切割的動作。（我覺得這塊需要一點點想像力）
切割後，就是一般的 mergeSort 作法了。傳進去兩個 list，並期待回傳的 headA、headB 是兩個已經 sort 好的 list 的 head。
最後再將這兩個 head 帶進去 merge。
```c=
list_ele_t *mergeSort(queue_t *q, list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *headA = mergeSort(q, head);
list_ele_t *headB = mergeSort(q, fast);
return merge(q, headA, headB);
}
```
**merge**
因為要維護 head、tail，所以一樣要傳入 q。
先說說 tmp 的作用。它比較像是一個 pseudo node 的概念，總是指向較小值並 tmp = tmp -> next
但為什麼不是使用 malloc 來 new 一個新的 list_ele_t 呢？這題如果這樣做，邏輯上是對的，但會被 **harness.h** 這個外部參考給擋下來。這部分老師上課有提到。擋下來的大意是：**不允許使用 malloc**。所以這題老師的意思應該是不能使用額外的空間來達到 sort 的目的。因此才出現了 3-12 行。目的在於，我要先知道誰是 merge 完的 list 的 head，也因此我要先知道誰是比較小的值。
相信到第 23 行應該都沒什麼問題，就只是一般的 linked list 的 merge sort 會出現的伎倆。而第 24-36 行則是在把剩下來的 node 接上去，並且找到誰才是 tail。
```c=
list_ele_t *merge(queue_t *q, list_ele_t *headA, list_ele_t *headB)
{
list_ele_t *tmp;
list_ele_t *head;
if (strcmp(headB->value, headA->value) > 0) {
tmp = headA;
headA = headA->next;
} else {
tmp = headB;
headB = headB->next;
}
head = tmp;
while (headA && headB) {
if (strcmp(headB->value, headA->value) > 0) {
tmp->next = headA;
tmp = tmp->next;
headA = headA->next;
} else {
tmp->next = headB;
tmp = tmp->next;
headB = headB->next;
}
}
if (headA) {
tmp->next = headA;
while (headA->next) {
headA = headA->next;
}
q->tail = headA;
} else if (headB) {
tmp->next = headB;
while (headB->next) {
headB = headB->next;
}
q->tail = headB;
}
return head;
}
```
心得：
老實說，這份作業的演算法難度不高，但是非常吃細心程度。不幸的是，我是一個蠻粗心的傢伙。這份作業很強調 malloc 的保護（如果 NULL 了怎麼辦）等等，至少我在記憶體配置吃蠻多苦的，常常 bug 抓好幾個小時甚至一整天就是卡在這裡想不透。
我一直認為底層相當困難而沒有去碰過，資工系的學生似乎很少這麼不愛底層的。但修了這堂課，讓我對底層的印象稍微改觀。沒錯，他還是相當困難，但他其實相當有趣，相當 freedom。
Sign in with Wallet
Connect another wallet