---
tags: linux2022
---

# 2022q1 Homework1 (lab0)
contributed by < [jackyyeh5111](https://github.com/laneser) >

[共筆示範](https://hackmd.io/@cccccs100203/linux2020-lab0)

## 實驗環境

$ 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):                          6
On-line CPU(s) list:             0-5
Thread(s) per core:              1
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i5-9400F CPU @ 2.90GHz
Stepping:                        10
CPU MHz:                         800.125
CPU max MHz:                     4100.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5799.77
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        9 MiB
NUMA node0 CPU(s):               0-5

## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)

[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:

- `q_new`: 建立新的「空」佇列;
- `q_free`: 釋放佇列所佔用的記憶體;
- `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
- `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
- `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點;
- `q_release_element`: 釋放特定節點的記憶體空間;
- `q_size`: 計算目前佇列的節點總量;
- `q_delete_mid`: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
- `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
- `q_swap`: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
- `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
- `q_sort`: 以遞增順序來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;

## 完成佇列操作
重要術語解釋(提醒自己)
- `node`: 資料型態為 `list_head`，每個 `entry` 裡都有 `node`，用以鏈結佇列中各元素，包含每個佇列的 head 也屬於 `node`
- `entry`: 佇列中的元素，資料型態為 `element_t`，是一個結構包含 `node`, `value`
- `head`: 用以指向佇列中第一個和最後一個元素的 `node`，若佇列為空則指向自己

==TODO==
說明 `element_t` 包含`list_head` 的好處

### q_new
### q_free
### q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;

    ele->value = malloc((strlen(s) + 1) * sizeof(char));
    if (!ele->value) {
        q_release_element(ele);
        return false;
    }

    strncpy(ele->value, s, strlen(s) + 1);
    list_add(&(ele->list), head); // 導致 Memory leak?

    return true;
}

上方程式可以順利編譯，並於 make check 時也顯示正常輸出。但是在提交時，被靜態分析指出有 memory leak 風險
:::danger
文字訊息不要用圖片展現！
:notes: jserv
:::

若把上方程式第 17 行的取址後的括弧拿掉如下圖，即可解決此問題，為什麼呢？ (還在找資料中)

:::danger
「找出問題」和「找資料」是不同的，前者要思考和試驗，後者是靠 Google 賞賜，你到底投入哪一項？
:notes: jserv
:::

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;

    ele->value = malloc((strlen(s) + 1) * sizeof(char));
    if (!ele->value) {
        q_release_element(ele);
        return false;
    }

    strncpy(ele->value, s, strlen(s) + 1);
    list_add(&ele->list, head); // 替換掉 &(ele->list)

    return true;
}

### q_insert_tail
### q_remove_head
### q_release_element
### q_size
### q_delete_mid
### q_delete_dup
一開始誤解此題意思，以為將重複的元素刪除至剩下一個即可，後來仔細看才發現只要元素有重複，必須將其相關的節點全數刪除

:::spoiler 錯誤程式碼

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;

    element_t *ele, *safe;
    list_for_each_entry_safe (ele, safe, head, list) {
        if (&safe->list == head)
            break;
        if (!strcmp(ele->value, safe->value))
            list_del(&ele->list);
    }

    return true;
}

:::

註解中有說到：`this function always be called after sorting`

:::spoiler 實際程式碼

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    struct list_head *cur = head->next, *next = cur->next;
    while (cur != head && next != head) {
        element_t *cur_entry = list_entry(cur, element_t, list);
        element_t *next_entry = list_entry(next, element_t, list);

        bool is_dup = false;
        // Do this way because list is guaranteed to be sorted in ascending
        // order.
        while (next != head && !strcmp(cur_entry->value, next_entry->value)) {
            list_del(next);
            q_release_element(next_entry);
            next = cur->next;
            next_entry = list_entry(next, element_t, list);
            is_dup = true;
        }
        if (is_dup) {
            list_del(cur);
            q_release_element(cur_entry);
            is_dup = false;
        }

        cur = next;
        next = cur->next;
    }
    return true;
}

:::

### q_swap
### q_reverse

:::spoiler 程式碼

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *cur = head->next, *next = cur->next;
    while (cur != head) {
        cur->next = cur->prev;
        cur->prev = next;
        cur = next;
        next = cur->next;
    }

    cur->next = cur->prev;
    cur->prev = next;
}

:::
### q_sort