---
# System prepended metadata

title: 2021q1 Homework1 (lab0)
tags: [linux2021]

---

# 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
心得：我光是寫第一個作業的第一個目標就花了不下幾十個小時，我深知自己基本功不足，光是處理最基本的課題就花了一堆時間，但是我還是想要學好這門課，所以只能慢慢來。
:::