---
# System prepended metadata

title: 2022q1 Homework1 (lab0)

---

---
tag: linux2022
---

# 2022q1 Homework1 (lab0)
contributed by < happyjack91630 >

### Reviewed by `kevinshieh0225`
- `q_free` 逐一拜訪可用 `list_for_each_safe`
- 根據 `list.h` : `#define list_entry(node, type, member) container_of(node, type, member)`
- 函式標題打錯很多字喔
- `q_delete_mid` 將 `do-while` 改為 `while` 可使的若佇列長度為 1 時，少做一次指派。
- `q_shuffle` 可用 `list_move_tail` 取代字串操作。

## 實驗環境
```shell
$ 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):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
Stepping:                        12
CPU MHz:                         1800.000
CPU max MHz:                     3900.0000
CPU min MHz:                     400.0000
BogoMIPS:                        3600.00
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

```

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

* 詳細閱讀 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 說明，依據指示著手修改 queue.[c] 和連帶的檔案，測試後用 Git 管理各項修改。

- [x]  `q_new`: 建立新的「空」佇列
- [x]  `q_free`: 釋放佇列所佔用的記憶體
- [x]  `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
- [x]  `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
- [x]  `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點
- [x]  `q_release_element`: 釋放特定節點的記憶體空間
- [x]  `q_size`: 計算目前佇列的節點總量
- [x]  `q_delete_mid`: 移走佇列中間的節點
- [x]  `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點
- [x]  `q_swap`: 交換佇列中鄰近的節點
- [x]  `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
- [x]  `q_sort`: 以==遞增順序==來排序鏈結串列的節點

* 在 qtest 提供新的命令 shuffle
- [x] Fisher–Yates shuffle 演算法

## 針對佇列的操作

### 結構體說明
```c=
struct list_head {
    struct list_head *prev;
    struct list_head *next;
};
```
`struct list_head`為 `list.h` 中定義的結構，經由`prev`與`next`分別指向前一個和下一個節點，便能實作circular double-linked-list。
```c=
typedef struct {
    char *value;
    struct list_head list;
} element_t;
```
`struct element_`為 `queue.h` 中定義的結構，這結構裡面存了一組 char array 和 `list_head`用來記錄前後節點。


![](https://i.imgur.com/1z2jjlm.png)
> 圖修改自[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)

## 針對佇列的操作

### q_new
建立新的「空」佇列，若沒有配置指定大小的記憶體，則回傳 NULL。

```c=
struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    if (!new) {
        return NULL;  // malloc fail
    }
    INIT_LIST_HEAD(new);
    return new;
}
```
建立新的「空」佇列，就是要將`prev`與`next`指標指向自己，可以利用`list.h`裡的`INIT_LIST_HEAD`此巨集函式來處理。
![](https://i.imgur.com/L7vOD6Z.png)

### q_free
釋放佇列所佔用的記憶體
```c=
void q_free(struct list_head *l)
{
    if (l == NULL) {
        return;
    }
    struct list_head *tmp = l->next;
    while (tmp != l) {
        element_t *del = container_of(tmp, element_t, list);
        tmp = tmp->next;
        free(del->value);
        free(del);
    }
    free(tmp);
}
```

為了要先避免`l`為空，要先判斷是否為`NULL`，如果不是才執行迴圈。
這裡要使用到`container_of`此巨集函式，用來獲得包含此`list_head`的`elemet_t`的地址，進一步將此`element_t`裡的`value`以及此`element_t`釋放掉。

```c=
//#define container_of(node, type, member)
element_t *del = container_of(tmp, element_t, list);
//container of便是通過list_head的地址(tmp)計算得到element_t(Node 0)的起始位置
```
![](https://i.imgur.com/qNre0jS.png)

#### :memo: 小問題
`container of`和`list_entry`這兩個巨集函式都是利用member的地址(node)計算得到type的起始位置。不太明白這兩個函式的差異性?

### q_inset_head
在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
```c=
bool q_insert_head(struct list_head *head, char *s)
{
    if (head == NULL) {
        return false;
    }
    element_t *new = malloc(sizeof(element_t));
    if (new == NULL) {
        return false;
    }
    int char_size = strlen(s);
    new->value = malloc(char_size + 1);
    if (new->value == NULL) {
        free(new);
        return false;
    }
    memcpy(new->value, s, char_size); //memcpy(dst,src,size);
    new->value[char_size] = '\0';
    list_add(&new->list, head);
    return true;
}
```
要先`malloc`出`element_t`可用的地址空間`(new)`，如果`malloc`失敗則直接return false，反之則利用`strlen`算出`s`的字元數`char_size`，用來`malloc`出`new->value`此字元串列所需的空間，這邊要小心，由於必須多儲存一個空字元`\0`，所以要創`char_size + 1`的空間。只要有使用`malloc`，要檢查是否有創立成功，如果沒有則必須連同前面創的`new`釋放掉，才不會造成memory leak。利用`memcpy`來將`s`複製進`new->value`空間裡。最後在使用`list_add`此函式將`new`插入到head。

### q_inset_tail
在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
```c=
bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL) {
        return false;
    }
    element_t *new = malloc(sizeof(element_t));
    if (new == NULL) {
        return false;
    }
    int char_size = strlen(s);
    new->value = malloc(char_size + 1);
    if (new->value == NULL) {
        free(new);
        return false;
    }
    memcpy(new->value, s, char_size);
    new->value[char_size] = '\0';
    list_add_tail(&new->list, head);
    return true;
}
```
與前一個function`q_insert_head`操作邏輯一樣，只是將`list_add`換成`list_add_tail`，就能將new插入到queue的尾巴了。


### q_remove_head
在佇列開頭 (head) 移去 (remove) 給定的節點
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head)) {
        return NULL;
    }
    element_t *remove_head =
        list_first_entry(head, element_t, list);  // for head entry
    if (remove_head == NULL) {
        return NULL;
    }
    list_del(&remove_head->list);
    if (sp) {
        memcpy(sp, remove_head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return remove_head;
}
```
要移去開頭的節點，必須得知開頭節點以及對應的`element_t`的地址，這時可以使用跟`container of`一樣功能的巨集函式，就是`list_first_entry`，差別在於`list_first_entry`是專門用在找到開頭節點資訊的函式。remove的要求是斷開與其他節點的連結，所以只需要用`list_del`就能斷開了，不需要`free`掉其對應的`element_t`的資訊。最後再將`head`的`value`放進`sp`裡面(要注意的是如果`value`的大小超過了`bufsize`，那只需要放入`bufsize`容量的`value`即可)。

### q_remove_tail
在佇列開頭 (head) 移去 (remove) 給定的節點
```c=
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head)) {
        return NULL;
    }
    element_t *remove_tail =
        list_last_entry(head, element_t, list);  // for tail entry
    if (remove_tail == NULL) {
        return NULL;
    }
    list_del(&remove_tail->list);
    if (sp) {
        memcpy(sp, remove_tail->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return remove_tail;
}
```
與前一個function`q_remove_head`操作邏輯一樣，只需要使用`list_last_entry`，就能取得`tail`對應的`element_t`的地址資訊了。

### q_release_element
釋放特定節點的記憶體空間
```c=
void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}
```
### q_szie
計算目前佇列的節點總量
```c=
int q_size(struct list_head *head)
{
    if (head == NULL) {
        return 0;
    }
    int length = 0;
    struct list_head *node;
    list_for_each (node, head) {
        length++;
    }
    return length;
}
```
在不更改原有存在的結構體，必須遍歷所有的queue節點，才能算出queue的長度為何。這裡可以使用`list_for_each`此巨集函式，來幫助我們遍歷所有的節點，進而計算出長度。

### q_delete_mid 
移走佇列中間的節點
```c=
bool q_delete_mid(struct list_head *head)
{
    if (head == NULL || list_empty(head)) {
        return false;
    }
    struct list_head *slow_ptr = head;
    struct list_head *fast_ptr = head;
    do {
        slow_ptr = slow_ptr->next;
        fast_ptr = fast_ptr->next->next;
    } while (fast_ptr->next != head && fast_ptr != head);
    element_t *mid_node =
        list_entry(slow_ptr, element_t, list);  // slow_ptr will be the middle
    list_del(slow_ptr);
    free(mid_node->value);
    free(mid_node);
    return true;
}
```
![](https://i.imgur.com/OqJe3gf.png)
> 圖取自[GeeksforGeeks - Find the middle of a given linked list](https://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/)

利用類似single link-list找middle node的原理運用在double circular link-list，一個`slow_ptr`每次只往前進一步，一個`fast_ptr`每次往前進兩步
只要`fast_ptr`或者`fast_ptr->next`到了`head`，則此時的`slow_ptr`就會是整條link-list的中間點了。這題要注意題目為q_**delete**_mid，所以不只要斷開連結，也要將該節點的`element_t`的所有資訊都刪掉。

### q_delete_dup(還要再優化)
在已經排序的狀況，移走佇列中具備重複內容的節點
```c=
bool q_delete_dup(struct list_head *head)
{
    if (head == NULL || list_empty(head)) {
        return false;
    }
    struct list_head *cur = head->next;
    element_t *cur_e;
    bool flag = false;  // record is cur duplicate ?
    while (cur->next != head) {
        cur_e = list_entry(cur, element_t, list);
        element_t *cur_next_e = list_entry(cur->next, element_t, list);

        if (strcmp(cur_e->value, cur_next_e->value) == 0) {
            struct list_head *cur_next_next = cur->next->next;
            cur->next = cur_next_next;
            cur_next_next->prev = cur;
            free(cur_next_e->value);
            free(cur_next_e);
            flag = true;  // cur_e->value == cur_next_e->value, so cur is duplicate
        } else {
            if (flag) {  // cur is duplicate so need to be delete
                cur->next->prev = cur->prev;
                cur->prev->next = cur->next;
                cur = cur->next;
                free(cur_e->value);
                free(cur_e);
            } else {
                cur = cur->next;
                flag = false;
            }
        }
    }
    if (flag) {  // queue only left one item(cur) and this item also duplicate
        cur->next->prev = cur->prev;
        cur->prev->next = cur->next;
        // cur = cur->next;
        free(cur_e->value);
        free(cur_e);
    }
    return true;
}
```
一開始先設一個`flag`，用來判斷每次的`cur`是否為重複`value`的一員。
:::info
```c=
if (strcmp(cur_e->value, cur_next_e->value) == 0) {
            struct list_head *cur_next_next = cur->next->next;
            cur->next = cur_next_next;
            cur_next_next->prev = cur;
            free(cur_next_e->value);
            free(cur_next_e);
            flag = true;  // cur_e->value == cur_next_e->value, so cur is duplicate
```
檢查`cur_e->value`和`cur_next_e->value`是否一樣，一樣的話就把`cur_next`刪掉，且`cur`為重複`value`的一員，所以`flag`變成`true`。
![](https://i.imgur.com/VNpttOz.png)
:::

:::info
```c=
if (flag) {  // cur is duplicate so need to be delete
    cur->next->prev = cur->prev;
    cur->prev->next = cur->next;
    cur = cur->next;
    free(cur_e->value);
    free(cur_e);
} else {
    cur = cur->next;
    flag = false;
}
```
如果`flag`為`true`，則要將目前的`cur`刪掉，反之`cur`就保留，往下個節點前進。
![](https://i.imgur.com/zytf6eK.png)
:::

:::info
```c=
if (flag) {  // queue only left one item(cur) and this item also duplicate
    cur->next->prev = cur->prev;
    cur->prev->next = cur->next;
    // cur = cur->next;
    free(cur_e->value);
    free(cur_e);
}
```
這個條件式會成立的場景為，全部節點只剩下`cur`一點，而且此節點為重複的一員`(flag =true)`，所以也要將`cur`刪掉。
![](https://i.imgur.com/3pCoSoZ.png)
:::

### q_swap(還要再優化)
交換佇列中鄰近的節點
```c=
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (head == NULL) {
        return;
    }
    struct list_head *cur = head->next;
    struct list_head *prev = head;
    struct list_head *next = cur->next;
    while (cur->next != head && cur != head) {
        cur->next = next->next;
        next->next->prev = cur;
        cur->prev = next;
        next->next = cur;
        next->prev = prev;
        prev->next = next;
        // prev->prev =cur;
        prev = cur;
        cur = cur->next;
        next = cur->next;
    }
}
```
此題參考[leetcode 24.Swap Node in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/discuss/222534/C-0ms)的做法，只是要再考慮`prev`如何連接就好了。

### q_reverse
以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
```c=
void q_reverse(struct list_head *head)
{
    if (head == NULL || list_empty(head)) {
        return;
    }
    struct list_head *cur = head;
    struct list_head *tmp;
    do {
        tmp = cur->prev;
        cur->prev = cur->next;
        cur->next = tmp;
        cur = cur->prev;
    } while (cur != head);
}
```
此題參考[GeeksforGeeks - Reverse a link list](https://www.geeksforgeeks.org/reverse-a-linked-list/)的做法，只是我是從tail端reverse回來，且必須多考慮`prev`的方向變化。

### q_sort
> 參考 kevinshieh0225

以遞增順序來排序鏈結串列的節點
```c=
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **cur;
    for (cur = NULL; L1 && L2; *cur = (*cur)->next) {
        // compare accending pair by pair
        element_t *node1 = container_of(L1, element_t, list);
        element_t *node2 = container_of(L2, element_t, list);
        cur = (strcmp(node1->value, node2->value) <= 0) ? &L1 : &L2;
        *ptr = *cur;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}


static struct list_head *mergesort_list(struct list_head *head)
{
    if (!head || !head->next) {
        return head;
    }
    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_list(head);
    struct list_head *right = mergesort_list(mid);

    return mergeTwoLists(left, right);
}

void q_sort(struct list_head *head)
{
    if (head == NULL || list_empty(head)) {
        return;
    }
    head->prev->next = NULL;  // circular to non-circular
    head->next = mergesort_list(head->next);


    struct list_head *ptr = head;
    while (ptr->next) {  // reconstruct circular link list (prev)
        ptr->next->prev = ptr;
        ptr = ptr->next;
    }
    ptr->next = head;
    head->prev = ptr;
}
```
此題雖然要使用circular double link-list做merge sort，但是其實我們可以先把circular變成non-circular`(head->prev->next = NULL)`就會容易許多。在副程式`mergesort_list`，也是使用`slow_ptr`和`fast_ptr`來切出link-list的middle node，就能拿middle node的左邊(含middle node)和右邊去做排序`mergeTwoLists`。`mergeTwoLists`就是參考了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)裡的**Merge Sort的實作**。要注意得是要使用`uintptr_t(typedef unsigned long int uintptr_t)`這項型態是必須多`#include <stdint.h>`才能使用。

## qtest 新功能實作：Fisher-Yates shuffle 

> 參考 kevinshieh0225

先在`qtest.c`裡找到一個`console_init`的function是專門用來放`./qtest`所打的command，所以在這裏面加上一行等等所需要用的shufle。
```c=
static void console_init()
{
    .....
    ADD_COMMAND(shuffle, "                | shuffle by Fisher-Yates shuffle");
    .....
}
```
Fisher-Yates shuffle則是參考了[【筆記】洗牌演算法：Fisher-Yates Shuffle](https://medium.com/@globelex65/%E7%AD%86%E8%A8%98-%E6%B4%97%E7%89%8C%E6%BC%94%E7%AE%97%E6%B3%95-fisher-yates-shuffle-c9feeb463154)實做出來。
```c=
void q_shuffle(struct list_head *head)
{
    if (head == NULL || list_empty(head)) {
        return;
    }

    int q_length = q_size(head);

    if (q_length == 1) {
        return;
    }

    struct list_head *cur;
    for (cur = head->next; cur->next != head; cur = cur->next) {
        int target;
        do {
            target = rand() % q_length;
        } while (target == 0);  // prevent target = cur
        struct list_head *target_list = cur;
        for (int i = 0; i < target; i++) {
            target_list = target_list->next;
        }
        element_t *cur_e = list_entry(cur, element_t, list);
        element_t *target_list_e = list_entry(target_list, element_t, list);

        char *tmp = cur_e->value;
        cur_e->value = target_list_e->value;
        target_list_e->value = tmp;
        q_length--;
    }
}
```
一開始本來想將`q_shuffle`定義在`queue.c`裡，同時也要將`q_shuffle`定義在`queue.h`，但是如果這樣做，在`git commiat -a`因為無法修改`queue.h`而報錯，所以只能將`q_shuffle`放在`qtest.c`裡面。
```c=
static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!l_meta.l)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();

    set_noallocate_mode(false);
    show_queue(3);
    return !error_check();
}
```
最後在實作能被`ADD_COMMAND`呼叫到的function，此function參考了`do_reverse`所寫的。