---
# System prepended metadata

title: 2022q1 Homework1 (lab0)
tags: [成大課程, Linux 核心設計]

---

# 2022q1 Homework1 (lab0)
###### tags: `Linux 核心設計` `成大課程`
contributed by < `hbr890627` >

## 實驗環境
暫時使用 WSL (Windows Subsystem for Linux)
```
$ 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):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           151
Model name:                      12th Gen Intel(R) Core(TM) i5-12400
Stepping:                        5
CPU MHz:                         2495.999
BogoMIPS:                        4991.99
Virtualization:                  VT-x
Hypervisor vendor:               Microsoft
Virtualization type:             full
L1d cache:                       288 KiB
L1i cache:                       192 KiB
L2 cache:                        7.5 MiB
L3 cache:                        18 MiB
```


## 進度
* 環境架設
    * 暫時使用 WSL (Windows Subsystem for Linux)
<s>
* 2/20: 觀看[lab0 解說影片](https://www.youtube.com/watch?v=CMcbfQiQIHg)
</s>
:::warning
不需要在此標注日期，修改紀錄都在 HackMD 中。只是「觀看」不能算是成果，你至少該提出問題和摘要你所學到的事物。
:notes: jserv
:::
* 嘗試修改 queue.c

## queue.c
### q_new
```c
struct list_head *q_new()
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return NULL;

    e->value = NULL;
    INIT_LIST_HEAD(&e->list);
    return &e->list;
}
```
### q_free
```c
void q_free(struct list_head *l) {}
```
### q_insert_head
```C
bool q_insert_head(struct list_head *head, char *s)
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = s;
    list_add(&e->list, head);
    return true;
}
```

:::danger
注意書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
:::

在 `make check` 後發現錯誤。
```bash
cmd> ih dolphin
ERROR: Need to allocate and copy string for new queue element
```

發現並未分配記憶體給 `e->value` ，修改程式碼。
```c
bool q_insert_head(struct list_head *head, char *s)
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = malloc(sizeof(s));
    strcpy(e->value, s);
    list_add(&e->list, head);
    return true;
}
```
在 `make check` 時不再發生 ERROR ，但無法 git commit 。
```
[2022-02-22T03:32:42.314Z] Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/hbr/linux2022/lab0-c/queue.c
45:    strcpy(e->value, s);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml
```
根據 https://security.web.cern.ch/recommendations/en/codetools/c.shtml ，將不安全的 `strcpy` ，改為 `strncpy` ，並補上字串的結尾`\0`。
```c
bool q_insert_head(struct list_head *head, char *s)
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = malloc(sizeof(char) * (strlen(s) + 1));
    strncpy(e->value, s, strlen(s));
    *(e->value + strlen(s)) = '\0';
    list_add(&e->list, head);
    return true;
}
```


發現有些人使用 `strdup` 取代 `strcpy` ，雖然實作起來較方便，但這不包含在C的標準函式庫，不利於程式的移植性。
[參考資料](https://www.itread01.com/article/1440470244.html)

### q_insert_tail
大致上與 `q_insert_head` 差不多，將 `list_add` 改為 `list_add_tail` 。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = malloc(sizeof(char) * (strlen(s) + 1));
    strncpy(e->value, s, strlen(s));
    *(e->value + strlen(s)) = '\0';
    list_add(&e->list, head);
    return true;
}
```
### q_remove_head
要移除第一個節點，實際上就是要移除 `head->next` ，而在 `list.h` 中，有 `list_first_entry` 這個巨集可以使用，用來精簡程式碼。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *node = list_first_entry(head, element_t, list);
    list_del(&node->list);

    if (sp) {
        strncpy(sp, node->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    return node;
}
```
### q_remove_tail
與 `q_remove_head` 幾乎相同，將 `list_first_entry` 改為 `list_last_entry` 即可。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *node = list_last_entry(head, element_t, list);
    list_del(&node->list);

    if (sp) {
        strncpy(sp, node->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    return node;
}
```
### q_release_element
此函式會被外部程式使用到，不用修改即可。
```c
void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}
```
### q_size
直接使用作業說明中的範例程式。
[作業說明-lab0-牛刀小試](https://hackmd.io/@sysprog/linux2022-lab0#%E7%89%9B%E5%88%80%E5%B0%8F%E8%A9%A6)
```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;
}
```
### q_delete_mid
參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94)，使用龜兔賽跑的方式找到中間節點。
```c
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *slow = head->next, *fast = head->next;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}
```
### q_delete_dup
```c
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
    if (!head)
        return false;

    element_t *entry, *safe;
    char *value = NULL;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (strcmp(value, entry->value) == 0) {
            list_del(&entry->list);
            q_release_element(entry);
        } else {
            value = entry->value;
        }
    }

    return true;
}
```
此段程式碼會出現 `You dereferenced a NULL or invalid pointer` ，但一直找不到問題出現在哪，在參考 [mm0809](https://hackmd.io/@2QYhHFatQmWFUgzITEcRjA/B1lsUihy9#q_delete_dup) 後，發現只要使用`""`初始化 `value` 即可。
```c
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
    if (!head)
        return false;

    element_t *entry, *safe;
    char *value = "";
    list_for_each_entry_safe (entry, safe, head, list) {
        if (strcmp(value, entry->value) == 0) {
            list_del(&entry->list);
            q_release_element(entry);
        } else {
            value = entry->value;
        }
    }

    return true;
}
```
### q_swap
```c
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;

    struct list_head *node = head->next;
    while (node != head && node->next != head) {
        struct list_head *next = node->next;
        list_del(node);
        list_add(node, next);
        node = node->next;
    }
}
```
### q_reverse

想要實作 reverse 的其中一個方式，就是從頭將結點移出，再照順序將結點 enqueue 即可，但根據作業要求，在此函式中，不能再額外分配記憶體用來暫時儲存暫時移出的節點，在思考解決方式時，參考 [mm0809](https://hackmd.io/@2QYhHFatQmWFUgzITEcRjA/B1lsUihy9#q_reverse) 的方式，只要先固定第一個指標後，不斷將後面的節點移到前面即可。
```c
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *tmp = head->next;
    for (struct list_head *node = tmp->next; tmp->next != head;
         node = tmp->next) {
        list_del(node);
        list_add(node, head);
    }
}
```
### q_sort
使用到[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94)中的 mergesort ，但是其實作的是單向的鏈結串列，必須在 merge 結束後，將 `prev` 的節點補上。
```c
/*
 * The sub-function of q_sort
 */
struct list_head *mergeTwoLists(struct list_head *h1, struct list_head *h2)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; h1 && h2; *node = (*node)->next) {
        node = strcmp(list_entry(h1, element_t, list)->value,
                      list_entry(h2, element_t, list)->value) < 0
                   ? &h1
                   : &h2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) h1 | (uintptr_t) h2);
    return head;
}

/*
 * The sub-function of q_sort
 */
struct list_head *mergesort(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    // find middle node
    struct list_head *slow = head;
    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow->next;
    slow->next = NULL;

    struct list_head *left = mergesort(head), *right = mergesort(mid);
    return mergeTwoLists(left, right);
}

/*
 * 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(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    head->prev->next = NULL;
    head->next->prev = NULL;

    struct list_head *sorted = mergesort(head->next);

    // link head & fix prev
    head->next = sorted;
    sorted->prev = head;
    struct list_head *temp = sorted;
    while (temp->next) {
        temp->next->prev = temp;
        temp = temp->next;
    }
    head->prev = temp;
    temp->next = head;
}
```





