---
# System prepended metadata

title: 2021q1 Homework1 (lab0)

---

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