---
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`用來記錄前後節點。
> 圖修改自[你所不知道的 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`此巨集函式來處理。
### 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)的起始位置
```
#### :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;
}
```
> 圖取自[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`。
:::
:::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`就保留，往下個節點前進。
:::
:::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`刪掉。
:::
### 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`所寫的。
Sign in with Wallet
Connect another wallet