# 2023q1 Homework1 (lab0)
contributed by < `csm1735` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 4999.90
```
## 改進 `queue.c`
### q_new
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(*head));
if (!head) {
free(head);
return NULL;
}
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
q_release_element(entry);
}
free(l);
}
```
釋放已配置的記憶體，考量到刪除節點後，還需要找到下一個節點的位置，因此這邊選擇使用 `list_for_each_entry_safe` 來實作。
### q_insert_head / tail
```c
element_t *new_element(char *s)
{
element_t *element = malloc(sizeof(*element));
if (!element) {
free(element);
return NULL;
}
element->value = strdup(s);
if (!element->value) {
free(element);
return NULL;
}
return element;
}
```
實作後發現 `q_insert_head` 跟 `q_insert_tail` 在程式碼上有大量重複的狀況，考量到精簡度及維護性，因此選擇將重複部分獨立成 `new_element` 來使用。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = new_element(s);
if (!element)
return false;
list_add(&element->list, head);
return true;
}
```
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = new_element(s);
if (!element)
return false;
list_add_tail(&element->list, head);
return true;
}
```
`q_insert_head` 跟 `q_insert_tail` 主要差異在於一個使用了 `list_add` 而另一個使用了 `list_add_tail` 。
### q_remove_head
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *tmp = list_first_entry(head, element_t, list);
if (sp) {
strncpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&tmp->list);
return tmp;
}
```
一開始沒有看懂說明，以為要對 `sp` 做 `malloc` ，所以產生了問題，後來發現應該直接去檢查 `sp` 是否為 `NULL` ， 再來做 `strncpy` 。
### q_remove_tail
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *tmp = list_last_entry(head, element_t, list);
if (sp) {
strncpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&tmp->list);
return tmp;
}
```
跟 `q_remove_head` 主要差異在於其使用了 `list_first_entry` 而這邊使用了 `list_last_entry` 。
### q_size
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
size_t len = 0;
struct list_head *cur;
list_for_each (cur, head) {
++len;
}
return len;
}
```
目前沒有想到其他更有效率的做法，只能透過走訪所有的節點來計算 `size` 。
### q_delete_mid
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
size_t len = q_size(head), count = -1;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
++count;
if (count == len / 2) {
list_del(&entry->list);
q_release_element(entry);
break;
}
}
return true;
}
```
找出中間的節點後，將其移除並釋放記憶體。
### q_delete_dup
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
bool flag = 0;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list == head) {
if (flag == 1) {
list_del(&entry->list);
q_release_element(entry);
}
break;
}
if (strcmp(entry->value, safe->value) == 0) {
list_del(&entry->list);
q_release_element(entry);
flag = 1;
} else if (flag == 1) {
list_del(&entry->list);
q_release_element(entry);
flag = 0;
}
}
return true;
}
```
這邊函式需要佇列在排序完的狀況下執行，去刪除具有相同字串的節點，假設這邊有 $N$ 個相同字串的節點，那麼前 $N-1$ 個可以透過 `strcmp` 的判斷來做刪除，第 $N$ 個則是透過 `flag` 的檢查來做刪除 。
:::warning
撰寫更精簡的程式碼。
:notes: jserv
:::
```c
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list != head && strcmp(entry->value, safe->value) == 0) {
list_del(&entry->list);
q_release_element(entry);
flag = 1;
} else if (flag == 1) {
list_del(&entry->list);
q_release_element(entry);
flag = 0;
}
}
```
將 `list_for_each_entry_safe` 內調整為更精簡的寫法
### q_swap
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return;
q_reverseK(head, 2);
return;
}
```
此函式 `swap` 的實質意義就等同於 `q_reverseK` 在參數 k 值為 2 的時候。
:::warning
是否可據此進一步精簡程式碼？
:notes: jserv
:::
### q_reverse
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
list_move(node, head);
}
return;
}
```
將所有的節點依序搬到頭後就等同於完成 `reverse` ， 要注意這邊得使用 `list_for_each_safe` 。
### q_reverseK
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head))
return;
struct list_head *node, *safe, *head_from = head, tmp;
INIT_LIST_HEAD(&tmp);
size_t count = 0;
list_for_each_safe (node, safe, head) {
++count;
if (count == k) {
list_cut_position(&tmp, head_from, node);
q_reverse(&tmp);
list_splice_init(&tmp, head_from);
head_from = safe->prev;
count = 0;
}
}
return;
}
```
這邊參考了 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_reverseK-%E5%AF%A6%E4%BD%9C) 的作法，每 k 個節點就切出來做 `reverse` 的動作，然後再將其連接回去。
### q_sort
:::danger
不用張貼完整程式碼，你應該闡述自己的想法、考量因素，還有分析已有方案的優缺點，並記錄過程中遇到的問題。
:notes: jserv
:::
```c
struct list_head *mergeTwoList(struct list_head *l1, struct list_head *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
element_t *n1 = list_entry(l1, element_t, list);
element_t *n2 = list_entry(l2, element_t, list);
if (strcmp(n1->value, n2->value) < 0) {
l1->next = mergeTwoList(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoList(l1, l2->next);
return l2;
}
}
```
`mergeTwoList` 原先的遞迴寫法，雖然程式碼較為精簡，但在 `make test` 時效能上無法通過，因此修正為以下的迴圈版本
```c
struct list_head *mergeTwoList(struct list_head *l1, struct list_head *l2)
{
struct list_head *head, *tmp;
element_t *n1 = list_entry(l1, element_t, list);
element_t *n2 = list_entry(l2, element_t, list);
if (strcmp(n1->value, n2->value) < 0) {
tmp = l1;
l1 = l1->next;
} else {
tmp = l2;
l2 = l2->next;
}
head = tmp;
while(l1 && l2) {
n1 = list_entry(l1, element_t, list);
n2 = list_entry(l2, element_t, list);
if(strcmp(n1->value, n2->value) < 0) {
tmp->next = l1;
tmp = tmp->next;
l1 = l1->next;
} else {
tmp->next = l2;
tmp = tmp->next;
l2 = l2->next;
}
}
if(l1) tmp->next = l1;
if(l2) tmp->next = l2;
return head;
}
```
```c
struct list_head *mergeSortList(struct list_head *head)
{
// merge sort
if (!head || !head->next)
return head;
struct list_head *fast = head->next;
struct list_head *slow = head;
// split list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
// sort each list
struct list_head *l1 = mergeSortList(head);
struct list_head *l2 = mergeSortList(fast);
// merge sorted l1 and sorted l2
return mergeTwoList(l1, l2);
}
```
以上 `merge sort` 實作參考自 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
head->prev->next = NULL;
head->next = mergeSortList(head->next);
struct list_head *cur;
for (cur = head; cur->next; cur = cur->next)
cur->next->prev = cur;
cur->next = head;
head->prev = cur;
return;
}
```
透過 `merge sort` 來完成排序，在實作時一開始忘記將最後一個節點的 next 指向 NULL ，導致程式有無窮迴圈的問題，需要注意，另外在排序完後，記得要將每個節點的 prev 重新連結上，還有將最後一個節點的 next 重新指向 head ，這樣才算完成。
### q_descend
```c
int q_descend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
element_t *maxNode = list_last_entry(head, element_t, list),
*curNode = NULL;
int count = 0;
for (struct list_head *cur = head->prev, *safe = cur->prev; cur != head;
cur = safe, safe = cur->prev) {
curNode = list_entry(cur, element_t, list);
if (strcmp(maxNode->value, curNode->value) > 0) {
list_del(&curNode->list);
q_release_element(curNode);
} else {
maxNode = curNode;
++count;
}
}
return count;
}
```
這邊的做法是從後往前掃來做檢查， `maxNode` 即為當前節點右側的節點中擁有最大值的那一個，當前節點的值如果小於 `maxNode` 的值則做刪除的動作，反之則更新成 `maxNode` 。
### q_merge
```c
int q_merge(struct list_head *head)
{
queue_contex_t *first = list_first_entry(head, queue_contex_t, chain),
*entry = NULL;
list_for_each_entry (entry, head, chain) {
if (entry->id == first->id) {
continue;
}
list_splice_init(entry->q, first->q);
}
q_sort(first->q);
return q_size(first->q);
}
```
這邊很直接的先將所有的佇列連接在一起，然後再<s>一口氣</s>一次將全部做排序，但這邊並沒有運用到各個佇列已經排序好的性質，可以再思考更好的做法。
:::warning
避免不精準的詞彙，「一口氣」對應的英語是什麼？這對於解析程式有何幫助？
:notes: jserv
> 已修正，謝謝老師
:::
:::info
目前測試分數 95 / 100
複雜度仍須提升
:::
---
## 以 Valgrind 分析記憶體問題
用 `make valgrind` 來測試，發現大部分都有如下的狀況:
```
==32347== 32 bytes in 1 blocks are still reachable in loss record 1 of 6
==32347== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==32347== by 0x10CBE0: do_new (qtest.c:146)
==32347== by 0x10DF3F: interpret_cmda (console.c:181)
==32347== by 0x10E4F4: interpret_cmd (console.c:201)
==32347== by 0x10E8F5: cmd_select (console.c:610)
==32347== by 0x10F1E1: run_console (console.c:705)
==32347== by 0x10D331: main (qtest.c:1274)
```
後來發現在 `qtest.c` 中的 `q_quit` 裡面，第一行就直接做了 `return true;` ，因此趕快將這行拿掉就恢復正常了，而後來發現這個問題在原本的 [lab0](https://github.com/sysprog21/lab0-c) 已經被修正掉了，這也提醒了我要記得同步專案。
:::info
測試結果 100 / 100
:::
---
## 在 qtest 提供新的命令 shuffle
### 實作 shuffle
一開始花了一些時間摸索如何在 `qtest` 中提供新的命令，後來發現要在 qtest.c 中的 `console_init` 加入以下程式碼。
```c
ADD_COMMAND(shuffle, "Shuffle queue", "");
```
並在 qtest.c 中新增 `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 (!current) {
report(3, "Warning: Try to operate null queue");
return false;
}
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
q_show(3);
return !error_check();
}
```
以下 `q_shuffle` 則是基於 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法的 Modern method 來實作。
```c
void q_shuffle(struct list_head *head)
{
int len = q_size(head), roll = 0;
struct list_head *rollNode = head->next, *lastNode = head->prev;
for (int i = len; i > 1; --i) {
roll = rand() % i;
if (roll == i - 1) {
lastNode = lastNode->prev;
continue;
}
rollNode = head->next;
for (int j = 0; j < roll; ++j)
rollNode = rollNode->next;
// swap value
element_t *A = list_entry(rollNode, element_t, list),
*B = list_entry(lastNode, element_t, list);
char *tmp = A->value;
A->value = B->value;
B->value = tmp;
lastNode = lastNode->prev;
}
return;
}
```
如果隨機抽選到的 `node` 是尚未被選擇的最後一個 `node` (也就是將被交換的那一個)，則省略交換的過程，直接做 continue ，反之則針對值來做交換的動作。
### 亂度分析
:::warning
有待分析
:::
## 執行 `option entropy 1`
```
cmd> option entropy 1
cmd> ih RAND 10
l = [jmhfj(21.88%) dlubbo(26.56%) abzjqxrsr(35.94%) uuiye(21.88%)
mxfangfme(32.81%) rdjtz(26.56%) dpjujvuf(29.69%) yvrkshlka(35.94%)
dkgjszx(32.81%) xgvygicw(32.81%)]
```
Sign in with Wallet
Connect another wallet