# 2022q1 Homework1 (lab0)
contributed by < [Tcc0403](https://github.com/Tcc0403) >
## 實驗環境
```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: 48 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
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 25
Model: 33
Model name: AMD Ryzen 5 5600X 6-Core Processor
Stepping: 0
Frequency boost: enabled
CPU MHz: 2200.000
CPU max MHz: 4650.2920
CPU min MHz: 2200.0000
BogoMIPS: 7385.57
Virtualization: AMD-V
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 3 MiB
L3 cache: 32 MiB
NUMA node0 CPU(s): 0-11
```
## 針對佇列的操作
### q_new
為佇列建立 `list_head` 結構體後，透過 `INIT_LIST_HEAD` 為其初始化
```c
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (q == NULL)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
### q_free
利用 `list_for_each_entry_safe` 走訪每個 `element_t` ，呼叫 `q_relase_element` 函式釋放空間
```c
void q_free(struct list_head *l)
{
if (l == NULL)
return;
element_t *e, *s;
list_for_each_entry_safe (e, s, l, list) {
q_release_element(e);
}
free(l);
}
```
### q_insert_head
:::warning
[課程文章中題的到 Head](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) 跟 `q_insert_head` 的 head 是不一樣的東西，這裡所指的是圖片所標記的 Node 0 ，也就是 `head->next`
:::
建立 `element_t` 結構體 `new` ，利用 `strdup` 儲存字串內容，接著將 `element_t` 結構體中包含的 `list_head` 結構體作為參數傳入`list_add` 函式，使其加入佇列
```c=47
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;
new->value = strdup(s);
if(new->value == NULL){
q_release_element(new);
return false;
}
list_add(&(new->list), head);
return true;
}
```
:::warning
目前無法通過 pre-commit 的靜態分析，顯示第 60 行出錯
```shell
$ git commit
queue.c:60:5: error: Memory leak: new [memleak]
return true;
^
```
:::
把 `&(new->list)` 改成 `&new->list` 就通過了
```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;
new->value = strdup(s);
if (new->value == NULL) {
free(new);
return false;
}
list_add(&new->list, head);
return true;
}
```
### q_insert_tail
與上面操作類似，差別在 `list_add` 改成 `list_add_tail`
```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;
new->value = strdup(s);
if (new->value == NULL) {
free(new);
return false;
}
list_add_tail(&new->list, head);
return true;
}
```
### q_remove_head
利用 `list_del_init` 將第一項 `element_t` 結構體移出佇列
```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 *ele = list_entry(head->next, element_t, list);
list_del_init(&ele->list);
if (sp != NULL) {
strncpy(sp, ele->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
return ele;
}
```
使用 `list_del_init` 而非 `list_del` 的原因，是擔心未來對回傳的 `element_t` 結構體做額外操作，導致錯誤發生
:::warning
~~時間複雜度測試沒過，待研究~~
發現 [eric88525 筆記](https://hackmd.io/@eric88525/linux2022-lab0#%E6%9C%80%E5%BE%8C%E4%B8%80%E5%80%8B%E6%B8%AC%E8%A9%A6%E7%9A%84bug) 有類似情況，自己上傳後在 GitHub Actions 中也有通過
:::
### q_remove_tail
跟上方作法類似
```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 *ele = list_entry(head->prev, element_t, list);
list_del_init(&ele->list);
if (sp != NULL) {
strncpy(sp, ele->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
return ele;
}
```
:::warning
同上
:::
### q_size
利用 `list_for_each` 走訪每個節點
```c
int q_size(struct list_head *head)
{
if (head == NULL || list_empty(head))
return 0;
int count = 0;
struct list_head *n;
list_for_each (n, head) {
count++;
}
return count;
}
```
原本以為 `list_for_each` 會走到 `head` 本身，但仔細看才發現是從 `head->next` 開始
```c
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
### q_delete_mid
利用環狀雙向鏈結串列的特性，透過兩個指標反向走訪串列，一個向前、一個向後，當兩個指標相遇或相鄰時， 向前走的指標所指向的節點即是中間節點
```c
bool q_delete_mid(struct list_head *head)
{
if(head == NULL || list_empty(head))
return false;
struct list_head *forward, *backward;
forward = head->next;
backward = head->prev;
while(forward != backward && forward->next != backward)
{
forward = forward->next;
backward = backward->prev;
}
list_del(forward);
q_release_element(list_entry(forward, element_t, list));
return true;
}
```
之後排序會使用到中間節點，因此將取得中間節點寫成函式 `q_get_mid`
```c
struct list_head *q_get_mid(struct list_head *head)
{
if (list_is_singular(head))
return head->next;
struct list_head *forward, *backward;
forward = head->next;
backward = head->prev;
while (forward != backward && forward->next != backward) {
forward = forward->next;
backward = backward->prev;
}
return forward;
}
```
改寫 `q_delete_mid`
```c
bool q_delete_mid(struct list_head *head)
{
if (head == NULL || list_empty(head))
return false;
struct list_head *mid = q_get_mid(head);
list_del(mid);
q_release_element(list_entry(mid, element_t, list));
return true;
}
```
### q_delete_dup
透過 `list_for_each_entry_safe` 來走訪佇列並刪除與相鄰節點有相同值的節點
```c
bool q_delete_dup(struct list_head *head)
{
if (head == NULL)
return false;
element_t *e, *s;
list_for_each_entry_safe (e, s, head, list)
if (strcmp(e->value, s->value) == 0) {
list_del(&e->list);
q_release_element(e);
}
return true;
}
```
:::warning
會發生 Segmentation fault
問題發生在 `list_for_each_entry_safe` 巨集的 `safe` 會走回串列的 `head` 節點，由於該節點並非 `element_t` 結構體，試圖讀取不存在的成員便會出錯
```c
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
```
:::
修正如下，在比對字串前先確認是 `safe` 是否為串列的 `head`
```c
bool q_delete_dup(struct list_head *head)
{
if (head == NULL)
return false;
element_t *e, *s;
list_for_each_entry_safe (e, s, head, list)
if (&s->list != head && strcmp(e->value, s->value) == 0) {
list_del(&e->list);
q_release_element(e);
}
return true;
}
```
:::warning
近期的 commit [de856da](https://github.com/sysprog21/lab0-c/commit/de856da257eeb42ca1d3dd86424588606692d9f5) 修正 `q_delete_dup` 函式的定義，上述程式碼需要進行修改
:::
修正如下
多宣告一個 `bool` 變數來幫忙紀錄是否重複
```c
bool q_delete_dup(struct list_head *head)
{
if (head == NULL)
return false;
element_t *e, *s;
bool is_dup = false;
list_for_each_entry_safe (e, s, head, list)
if (&s->list != head && strcmp(e->value, s->value) == 0) {
is_dup = true;
list_del(&e->list);
q_release_element(e);
} else if (is_dup) {
is_dup = false;
list_del(&e->list);
q_release_element(e);
}
return true;
}
```
### `q_swap`
直接重新指派兩兩一組節點相連的六個指標
```c
void q_swap(struct list_head *head)
{
struct list_head *node1, *node2;
node1 = head->next;
node2 = node1->next;
while (node1 != head && node2 != head) {
node1->prev->next = node2;
node2->prev = node1->prev;
node2->next->prev = node1;
node1->next = node2->next;
node2->next = node1;
node1->prev = node2;
node1 = node1->next;
node2 = node1->next;
}
}
```
閱讀 [lanser 同學的作法](https://hackmd.io/@laneser/linux2022_lab0#q_swap)後，發現可以將 `q_swap` 視作將奇數節點移除後插入偶數節點之後
List API 中的`list_move` 函式正好是 `list_delete` 和 `list_add` 的連續操作
將以上程式改寫為更精簡易讀的版本
```c
void q_swap(struct list_head *head)
{
struct list_head *node1, *node2;
node1 = head->next;
node2 = node1->next;
while (node1 != head && node2 != head) {
list_move(node1, node2);
node1 = node1->next;
node2 = node1->next;
}
}
```
### q_reverse
利用 `list_for_each_safe` 走訪串列交換 `next` 和 `prev` ，因為不會走到佇列的 `head` ，所以要額外處理
```c
void q_reverse(struct list_head *head)
{
if (head == NULL || list_empty(head))
return;
struct list_head *n, *s;
list_for_each_safe (n, s, head) {
n->next = n->prev;
n->prev = s;
}
struct list_head *tmp;
tmp = head->next;
head->next = head->prev;
head->prev = tmp;
}
```
### q_sort
原本打算參考 [Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/modified-merge-sort#Merge-Sort-%E8%88%87%E5%AE%83%E7%9A%84%E8%AE%8A%E5%8C%96) ，但跟本次實驗的資料結構略為不同，這次實驗是採用[Intrusive linked lists](https://www.data-structures-in-practice.com/intrusive-linked-lists/)
一開始想另外宣告 `list_head` 結構體並存放在 `list_head *` 陣列當中，以便進行上述筆記的[分割方法](https://hackmd.io/@lambert-wu/modified-merge-sort#%E5%88%86%E5%89%B2)，但寫完發現本次實驗不允許在 `q_sort` 當中進行 `malloc` 和 `free` 等操作
參考幾位同學的筆記後，決定利用 `LIST_HEAD` 巨集宣告區域變數接收分割出來的串列，維持雙向環狀的結構，以便透過 List API 操作串列
```c
void q_sort(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
LIST_HEAD(tmp);
list_cut_position(&tmp, head, q_get_mid(head));
q_sort(head);
q_sort(&tmp);
mergeTwoLists(head, &tmp);
}
```
在 `mergeTwoLists` 函式中，因為兩個引數 `L1`, `L2` 都是用來管理串列的 Head ，可以利用此特性，將兩條串列合併至其中一個 Head 之下
`list_move_tail(node, head)` 函式等價於把 `node` 節點移出原本其所在的串列，再將其插入 `head` 節點之前
```c
void mergeTwoLists(struct list_head *L1, struct list_head *L2) {
struct list_head *node = L1->next;
element_t *E1, *E2;
while(!list_empty(L2) && node != L1){
E1 = list_entry(node, element_t, list);
E2 = list_entry(L2->next, element_t, list);
if(strcmp(E1->value, E2->value) > 0){
list_move_tail(&E2->list, &E1->list);
} else {
node = node->next;
}
}
list_splice_tail(L2, L1);
}
```
### q_shuffle
嘗試撰寫一個 Linux 風格的 List API
```c
struct list_head *list_node_at(struct list_head *head, int index)
{
struct list_head *node = head->next;
while(--index)
node = node->next;
return node;
}
```
依照 [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法實作
因為每次迭代都會縮小選取範圍，直接將選到的節點移至串列最尾端即可
```c
void q_shuffle(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
srand(time(NULL));
for(int i = q_size(head); i > 1 ; i--){
list_move_tail(list_node_at(head, rand()%i), head);
}
}
```
在 `qtest.c` 中參考 `do_sort` 函式，實作 `do_shuffle` 函式
```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();
int cnt = q_size(l_meta.l);
if (cnt < 2)
report(3, "Warning: Calling shuffle on single node");
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();
}
```
`console_init` 函式中新增 Shuffle 的相關命令
```c
ADD_COMMAND(shuffle,
" | Perform Fisher-Yates shuffle in queue");
```
透過 `qtest` 進行測試
```shell
$ ./qtest
cmd> new
l = []
cmd> it 1
l = [1]
cmd> it 2
l = [1 2]
cmd> it 3
l = [1 2 3]
cmd> shuffle
l = [3 2 1]
cmd> shuffle
l = [2 1 3]
cmd> it 4
l = [2 1 3 4]
cmd> shuffle
l = [3 2 1 4]
```
git commit 的時候發現不能更動 `queue.h` 和 `list.h`，將所有程式移至 `qtest.c`
Sign in with Wallet
Connect another wallet