# 2022q1 Homework1 (lab0)
contributed by < `extrovert7986` >
## 實驗環境
```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: 43 bits physical, 48 bits virtual
CPU(s): 16
On-line CPU(s) list: 0-15
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 23
Model: 113
Model name: AMD Ryzen 7 3800X 8-Core Processor
Stepping: 0
Frequency boost: enabled
CPU MHz: 2200.000
CPU max MHz: 4558.8862
CPU min MHz: 2200.0000
BogoMIPS: 7785.69
Virtualization: AMD-V
L1d cache: 256 KiB
L1i cache: 256 KiB
L2 cache: 4 MiB
L3 cache: 32 MiB
NUMA node0 CPU(s): 0-15
```
## q_new
依據 `list.h` 定義
```c=28
For an empty list,
both member variables point to the head.
```
可以得知 `empty list` 應該為一個 `prev` 與 `next` 都指向自己的<s>東西</s>
:::danger
請用正式的術語，避免說「東西」。考慮到日後參加科技公司面試，你現在所紀錄的內容，可能就會在日後出現，現在就養成說專業術語的習慣。
:notes: jserv
:::
:::info
Update:
可以得知 `empty list` 應該為一個`prev` 與 `next` 都指向自己的串列
:::
```c=
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (q) {
q->prev = q;
q->next = q;
}
return q;
}
```
## q_free
```c=
void q_free(struct list_head *l)
{
l->prev->next = NULL;
while (l) {
struct list_head *tmp = l;
l = l->next;
free(tmp);
}
}
```
上述的程式碼並為成功釋放 element_t 裡面字串的記憶體
更新為以下的形式
```c=
void q_free(struct list_head *l)
{
struct list_head *cur;
l->prev->next = NULL;
for (cur = l->next; cur;) {
element_t *tmp = list_entry(cur, element_t, list);
cur = cur->next;
if (tmp->value)
free(tmp->value);
free(tmp);
}
free(l);
}
```
:::info
2/26 Update: 需要判斷 l pointer 是否為 NULL
:::
```diff=
void q_free(struct list_head *l)
{
struct list_head *cur;
+
+ if (!l)
+ return;
l->prev->next = NULL;
```
## q_insert_head
```c=
bool q_insert_head(struct list_head *head, char *s)
{
element_t *ele = malloc(sizeof(element_t));
size_t bufSiz = sizeof(char) * (strlen(s) + 1);
if (!ele)
return false;
if (!(ele->value = malloc(bufSiz))) {
free(ele);
return false;
}
ele->value = strncpy(ele->value, s, bufSiz);
list_add(&ele->list, head);
return true;
}
```
開發過程中, 發現自己把 `ele` 加入 `head` 中（14 ~ 17）, 會導致 Memory leak 如下
```
Following files need to be cleaned up:
queue.c
queue.c:62:5: error: Memory leak: ele [memleak]
return true;
^
Fail to pass static analysis.
```
但如果使用 `list_add` function, 就不會出現問題, 推測應該是 static analysis 的問題, 檢查 cppcheck 版本為 1.90 沒有問題, 暫時將程式碼改為以下形式
Original：
```c
ele->list.prev = head;
ele->list.next = head->next;
head->next->prev = &(ele->list);
head->next = &(ele->list);
```
Updated：
```c
list_add(&ele->list, head);
```
:::warning
TODO: 查閱 [Cppcheck 手冊](https://cppcheck.sourceforge.io/manual.pdf)，使用其 suppression 標注。
:notes: jserv
:::
:::info
2/26 Update: 加入判斷確認 head 與 ele 是否為 NULL
:::
```diff=
bool q_insert_head(struct list_head *head, char *s)
{
+ if (!head)
+ return false;
+
element_t *ele = e_new(s);
+ if (!ele)
+ return false;
+
list_add(&ele->list, head);
```
## q_insert_tail
由於 q_insert_tail 中 new element 的動作可以與 q_insert_head 中共用, 所以將該部份的 code 抽出共用
```c
static inline element_t *e_new(char *s)
{
element_t *ele = malloc(sizeof(element_t));
size_t bufSiz = sizeof(char) * (strlen(s) + 1);
if (!ele)
return NULL;
if (!(ele->value = malloc(bufSiz))) {
free(ele);
return NULL;
}
ele->value = strncpy(ele->value, s, bufSiz);
return ele;
}
```
並且更改 q_insert_head 如下
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *ele = e_new(s);
list_add(&ele->list, head);
return true;
}
```
q_insert_tail 實做如下
```c
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *ele = e_new(s);
list_add_tail(&ele->list, head);
return true;
}
```
:::info
2/26 Update: 加入判斷確認 head 與 ele 是否為 NULL
:::
```diff=
bool q_insert_tail(struct list_head *head, char *s)
{
+ if (!head)
+ return false;
+
element_t *ele = e_new(s);
+ if (!ele)
+ return false;
+
list_add_tail(&ele->list, head);
```
## q_remove_head 與 q_remove_tail
這兩個 function 分別用來移除(remove)串列中的第一與最後一個節點,
移除時, 並不釋放目標節點的記憶體位置,
以下 2 段程式碼分別對串列開頭(head->next)與結尾(head->prev)節點進行移除相關的動作
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
element_t *tar = list_first_entry(head, element_t, list);
head->next = tar->list.next;
tar->list.next->prev = head;
if (sp && bufsize > 0) {
strncpy(sp, tar->value, bufsize - 1);
}
return tar;
}
```
```c=
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->prev == head)
return NULL;
element_t *tar = list_last_entry(head, element_t, list);
head->prev = tar->list.prev;
tar->list.prev->next = head;
if (sp && bufsize > 0) {
strncpy(sp, tar->value, bufsize - 1);
}
return tar;
}
```
:::info
2/26 Update: 根據 manual, strncpy 不會幫忙寫入最後一個 byte 的 '\0', 需要由使用者補上
:::
```diff=11
if (sp && bufsize > 0) {
strncpy(sp, tar->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
}
```
## q_delete_mid
q_delete_mid 暫時實做如下, 透過 `Floyd’s Cycle Detection Algorithm` 找出佇列的中心點並且 remove
> 「中心點」這詞不精準，需要定義
> :notes: jserv
:::info
2/27 Update: 此處中心點的定義如下
在不包含 head ,長度為 n 的佇列中, 佇列中的第一個 element_t index 為 0, 最後一個 element_t index 為 n-1 的情況下, 中心點為第 $\left\lfloor{n/2}\right\rfloor$ 個 node
:::
```c
bool q_delete_mid(struct list_head *head)
{
struct list_head **slow, **fast;
if (!head)
return false;
for (slow = fast = &head; (*fast) && (*fast)->next;
slow = &((*slow)->next), fast = &((*fast)->next->next))
;
*slow = (*slow)->next;
return true;
}
```
原本的作法為 remove 並非 delete
改為以下 delete 作法
```c
bool q_delete_mid(struct list_head *head)
{
element_t *tar;
struct list_head **slow, **fast;
if (!head)
return false;
for (slow = fast = &(head->next); (*fast) != head && (*fast)->next != head;
slow = &((*slow)->next), fast = &((*fast)->next->next))
;
tar = list_entry(&(**slow), element_t, list);
tar->list.prev->next = tar->list.next;
tar->list.next->prev = tar->list.prev;
if (tar->value)
free(tar->value);
free(tar);
return true;
}
```
## q_reverse
將每一個 node 的 next 與 prev 交換即可
```c=
void q_reverse(struct list_head *head)
{
if (!head || head->next == head) {
return;
}
struct list_head *current = head;
do {
struct list_head *tmp = current->next;
current->next = current->prev;
current->prev = tmp;
current = current->prev;
} while (current != head);
}
```
## q_swap
```c=
void q_swap(struct list_head *head)
{
struct list_head *fir, *sec;
for (fir = head->next, sec = fir->next; fir != head && sec != head;
fir->prev->next = sec, sec->next->prev = fir, fir->next = sec->next,
sec->prev = fir->prev, fir->prev = sec, sec->next = fir,
fir = fir->next, sec = fir->next)
;
}
```
:::warning
以 for_each 相關巨集改寫上述程式碼。
:notes: jserv
:::
:::info
2/28 Update:
```diff=1
void q_swap(struct list_head *head)
{
struct list_head *fir, *sec;
- for (fir = head->next, sec = fir->next; fir != head && sec != head;
- fir->prev->next = sec, sec->next->prev = fir, fir->next = sec->next,
- sec->prev = fir->prev, fir->prev = sec, sec->next = fir,
- fir = fir->next, sec = fir->next)
- ;
+
+ list_for_each (fir, head) {
+ sec = fir->next;
+ if (sec == head)
+ return;
+ fir->prev->next = sec;
+ sec->next->prev = fir;
+ fir->next = sec->next;
+ sec->prev = fir->prev;
+ fir->prev = sec;
+ sec->next = fir;
+ }
}
```
:::
## q_sort
透過 merge sort 將佇列進行排序
1. 此處實作的 merge sort 可以讓使用者丟入不包含 head 的剩餘佇列並且進行排序
```c=
/**
* sort list_head without include the first member
*/
struct list_head *q_merge_sort(struct list_head *head)
{
struct list_head *fir, *sec;
if (!head || !head->next)
return head;
fir = head;
sec = q_devide(fir);
fir = q_merge_sort(fir);
sec = q_merge_sort(sec);
return q_merge(fir, sec);
}
```
2. devide 函式將會從長度為 n 的 list 中找出 index 為 $\left\lceil{n/2}\right\rceil$(起始 element_t index = 0 的情況下) 的結點, 作為第二個節點的開頭, 並斷開前後 2 個佇列(將第一個佇列的最後一個 element_t 的 next 改為 NULL)
```c=
struct list_head *q_devide(struct list_head *head)
{
struct list_head **slow, **fast, *retVal;
for (slow = fast = &(head); *fast && (*fast)->next;
slow = &((*slow)->next), fast = &((*fast)->next->next))
;
retVal = *slow;
*slow = NULL;
return retVal;
}
```
透過以下的 merge 函式將切開來的 2 個 list 排序並且 merge 回來
```c=
struct list_head *q_merge(struct list_head *l1, struct list_head *l2)
{
struct list_head *indirect, head;
indirect = &head;
while (l1 && l2) {
if (strcmp(list_val(l1), list_val(l2)) < 0) {
indirect->next = l1;
l1 = l1->next;
} else {
indirect->next = l2;
l2 = l2->next;
}
indirect = indirect->next;
}
indirect->next =
(struct list_head *) ((unsigned long int) l1 | (unsigned long int) l2);
return head.next;
}
```
主要被 qtest 呼叫的 function
首先將最後一個 node 與 head 切開
然後在 sort 完之後, 將所有 node 的 prev link 回來外
處理最後一個 node 與 head 之間的 link
```c=
void q_sort(struct list_head *head)
{
struct list_head *last;
if (!head || head->next == head || head->next->next == head)
return;
head->prev->next = NULL;
head->next = q_merge_sort(head->next);
for (last = head; last->next; last = last->next) {
last->next->prev = last;
}
head->prev = last;
last->next = head;
}
```
## q_delete_dup
此 function 目前的演算法如下
```
FOR each node exclude head
WHILE node equals to its next one
delete next node
isRemove = true
IF isRemove
delete current node
```
```c=
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
for (struct list_head *cur = head->next; cur && cur != head;) {
bool isRemove = false;
while (cur->next != head &&
!strcmp(list_val(cur), list_val(cur->next))) {
isRemove = true;
cur->next = cur->next->next;
q_delete_node(cur->next->prev);
}
if (isRemove) {
struct list_head *tmp = cur;
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
cur = cur->next;
q_delete_node(tmp);
} else {
cur = cur->next;
}
}
return true;
}
```
Sign in with Wallet
Connect another wallet