---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `stupidrara` >
## 實驗環境
```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: 94
Model name: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
Stepping: 3
CPU MHz: 2600.000
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
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
````
## 開發過程
### q_new
建立新的「空」佇列。
```c
struct list_head *q_new()
{
struct list_head *newHead = malloc(sizeof(struct list_head));
if (newHead) {
INIT_LIST_HEAD(newHead);
}
return newHead;
}
```
因為 `malloc` 失敗會回傳 `NULL` ，所以 `return newHead` 已經包含了判斷 `NULL` 的結果。
### q_free
釋放佇列所佔用的記憶體。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *now = l->next;
element_t *toDel;
while (now != l) {
toDel = list_entry(now, element_t, list);
now = now->next;
q_release_element(toDel);
}
free(l);
}
```
若 `l` 為 `NULL` 則跳出函式，否則 `l->next` 一定存在。此時從 `now = l->next` 開始釋放，直到 `now == l` 時 break while（如果 `l->next` 一開始指向自己的話 `while` 會直接 break）。
* 更新使用 macro `list_for_each_entry_safe` 取代 `while`
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *toDel, *safe;
list_for_each_entry_safe (toDel, safe, l, list) {
q_release_element(toDel);
}
free(l);
}
```
### q_insert_head
在佇列開頭 ( head ) 插入 ( insert ) 給定的新節點 (以 LIFO 準則)。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!(head && s))
return false;
element_t *newElement = malloc(sizeof(element_t));
if (!newElement)
return false;
size_t strSize = strlen(s);
newElement->value = malloc(strSize + 1);
if (!newElement->value) {
free(newElement);
return false;
}
newElement->value[strSize] = '\0';
strncpy(newElement->value, s, strSize);
list_add(&newElement->list, head);
return true;
}
```
先判斷 `head` 和 `s` 是否為 `NULL` ，皆存在時則嘗試配置 element 空間，若配置失敗則釋放並回傳 false 。更新：移除 `sizeof(char)`。
### q_insert_tail
在佇列尾端 ( tail ) 插入 ( insert ) 給定的新節點 (以 FIFO 準則)。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!(head && s))
return false;
element_t *newElement = malloc(sizeof(element_t));
if (!newElement)
return false;
size_t strSize = strlen(s);
newElement->value = malloc(strSize + 1);
if (!newElement->value) {
free(newElement);
return false;
}
newElement->value[strSize] = '\0';
strncpy(newElement->value, s, strSize);
list_add_tail(&newElement->list, head);
return true;
}
```
與 `q_insert_head` 相似。
### q_remove_head
在佇列開頭 ( head ) 移去 ( remove ) 給定的節點。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *toRemove = list_entry(head->next, element_t, list);
list_del(head->next);
if (sp) {
strncpy(sp, toRemove->value, bufsize - 2);
sp[bufsize - 1] = '\0';
}
return toRemove;
}
```
先判斷 `head` 是否為 `empty` 或 `NULL` ，再判斷 `sp` 是否需要複製。
### q_relese_element
釋放特定節點的記憶體空間。
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
### q_size
計算目前佇列的節點總量。
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int counter = 1;
struct list_head *now = head->next->next;
while (now != head) {
++counter;
now = now->next;
}
return counter;
}
```
先使 `counter = 1` 和 `now = head->next->next`，這樣可以在佇列長度至少為 1 時，最小化計算量。
### q_delete_mid
移走佇列中間的節點。
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *slow = head->next, *fast = head->next->next;
while (fast != head && fast != head->prev) {
slow = slow->next;
fast = fast->next->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
使用龜兔賽跑演算法找出中間點。為了使計算量最小，可初始化 `slow = head->next, fast = head->next->next` ，讓 `while` 運作最少次。
### q_delete_dup
在已經排序的狀況，移走佇列中具備重複內容的節點。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
bool flag = false;
element_t *now, *safe;
list_for_each_entry_safe (now, safe, head, list) {
if (&safe->list != head && !strcmp(now->value, safe->value)) {
list_del(&now->list);
q_release_element(now);
flag = true;
} else if (flag) {
list_del(&now->list);
q_release_element(now);
flag = false;
}
}
return true;
}
```
以自動狀態機來思考這題，如果遇到 `now->value` 和 `safe->value` 相同時，則把 `flag` 設定為 `true` ，此時開始刪除 `now` 節點，直到遇到 `now->value` 和 `safe->value` 不同後，判斷 `flag` 是否為 `true` 來判斷是否要離開狀態，離開時要刪除 `now` 節點。
### q_swap
交換佇列中鄰近的節點。
```c
void q_swap(struct list_head *head)
{
struct list_head *prev, *now;
list_for_each_safe (prev, now, head) {
list_move_tail(now, prev);
now = prev->next;
}
}
```
先利用 `list_move_tail(now, prev)` 可以使兩節點交換位置，且 `now = prev->next` 使 traverse 速度變一般的兩倍，兩個效果合併後就是 swap 了。
### q_reverse
以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *now, *safe, *temp;
list_for_each_safe (now, safe, head) {
temp = now->next;
now->next = now->prev;
now->prev = temp;
}
temp = now->next;
now->next = now->prev;
now->prev = temp;
}
```
先交換所有節點的 `prev` 和 `next` pointer ，最後再交換 `head` 的 `prev` 和 `next` pointer。
### q_sort
以遞增順序來排序鏈結串列的節點。
```c
void q_sort(struct list_head *head)
{
int listSize = q_size(head);
if (listSize < 2)
return;
// spilt every element by using local variable 'heads[]'
struct list_head heads[listSize];
struct list_head *now = head->next, *temp;
for (int i = 0; i < listSize; i++) {
INIT_LIST_HEAD(&heads[i]);
temp = now->next;
list_add(now, &heads[i]);
now = temp;
}
// merge
for (int interval = 1; interval < listSize; interval *= 2) {
for (int i = 0; i + interval < listSize; i += interval * 2) {
struct list_head *L1 = heads[i].next;
struct list_head *L2 = heads[i + interval].next;
// merged 為目前完成排列的最尾端的 pointer
struct list_head **node, *merged = &heads[i];
// 正式開始 merge
for (node = NULL; L1 != &heads[i] && L2 != &heads[i + interval]; \
*node = (*node)->next) {
node = strcmp(list_entry(L1, element_t, list)->value, \
list_entry(L2, element_t, list)->value) < 0 ? &L1 : &L2;
merged->next = *node;
(*node)->prev = merged;
merged = merged->next;
}
// 處理未接完的 linked list
merged->next = (L1 != &heads[i]) ? L1 : L2;
merged->next->prev = merged;
heads[i].prev = (L1 != &heads[i]) ? heads[i].prev : heads[i + interval].prev;
heads[i].prev->next = &heads[i];
}
}
// merge 完的結果會存在 heads[0], 所以要把 pointer 還給 head
heads[0].next->prev = head;
heads[0].prev->next = head;
head->next = heads[0].next;
head->prev = heads[0].prev;
}
```
使用非遞迴實作 mergesort ，過程中遇到的 bug 都是忘記接回 doubly circular link 。實作過程參考了 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 的非遞迴作法，並使用了 indirect pointer `node` 來省下 `L1` `L2` 的分支。
但很可惜現在還不能看到皮卡丘，因為我使用 local variables 陣列 `heads` 來 spilt 所有 elements，而這樣會導致在 elements 數量過多時無法正常運作。
目前想到的解決辦法是利用 hierarchy 階級制度，把初始資料切成好幾份資料，並且建立額外的 `secondary_heads` 來指向切開來的資料，讓 local variable 陣列的大小可以壓在允許範圍內。優點是可以重複利用創造出來的 `heads` 來節省 stack 的空間，甚至還可以建立數層的 hierarchy 來極限壓低 stack 的空間，而且我認為可以降低 cache miss 或 page fault 的機率。
Sign in with Wallet
Connect another wallet