---
tag: 2022linuxclass
---
# 2022q1 Homework1 (lab0)
contributed by < `Wallmountain` >
## 實驗環境
```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): 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: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
Stepping: 10
CPU MHz: 1637.560
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 9 MiB
NUMA node0 CPU(s): 0-11
```
## 作業要求
閱讀 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 說明，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，並利用 [Cppcheck](http://cppcheck.sourceforge.net/) 和 [Valgrind](https://valgrind.org/) 作程式評估。
* `q_new`: 建立新的「空」佇列
* `q_free`: 釋放佇列所佔用的記憶體
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點
* `q_release_element`: 釋放特定節點的記憶體空間
* `q_size`: 計算目前佇列的節點總量
* `q_delete_mid`: 移走佇列中間的節點
* `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點
* `q_swap`: 交換佇列中鄰近的節點
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
* `q_sort`: 以==遞增順序==來排序鏈結串列的節點
## 開發過程
### q_new
建立空佇列，檢查 malloc 是否正常運作
```cpp
struct list_head *q_new()
{
struct list_head *tmp =
(struct list_head *) malloc(sizeof(struct list_head));
if (!tmp) {
return NULL;
}
INIT_LIST_HEAD(tmp);
return tmp;
}
```
### q_free
釋放所有佇列所佔記憶體
```cpp
void q_free(struct list_head *l)
{
if (!l) {
return;
}
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
list_del_init(&entry->list);
q_release_element(entry);
}
free(l);
}
```
### q_insert_head
檢查 malloc 有沒有給指定大小的記憶體，字串結尾要加 ``'\0'``
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *node = (element_t *) malloc(sizeof(element_t));
if (!node) {
return false;
}
int length = strlen(s);
node->value = (char *) malloc(length + 1);
if (!node->value) {
q_release_element(node);
return false;
}
for (int i = 0; i < length; i++) {
node->value[i] = s[i];
}
node->value[length] = '\0';
list_add(&node->list, head);
return true;
}
```
### q_insert_tail
跟 insert head 基本相同
```cpp
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *node = (element_t *) malloc(sizeof(element_t));
if (!node) {
return false;
}
int length = strlen(s);
node->value = (char *) malloc(length + 1);
if (!node->value) {
q_release_element(node);
return false;
}
for (int i = 0; i < length; i++) {
node->value[i] = s[i];
}
node->value[length] = '\0';
list_add_tail(&node->list, head);
return true;
}
```
### q_size
計算目前佇列的節點總量
```cpp
int q_size(struct list_head *head)
{
if (!head || list_empty(head)) {
return 0;
}
struct list_head *node;
int size = 0;
list_for_each (node, head) {
size++;
}
return size;
}
```
### q_delete_mid
移走佇列中間的節點, 使用前面的 q_size 得到佇列長度
```cpp
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head)) {
return false;
}
struct list_head *node = head->next;
int size = q_size(head) / 2;
while (size--) {
node = node->next;
}
list_del_init(node);
q_release_element(list_entry(node, element_t, list));
return true;
}
```
### q_delete_dup
刪除值重複的 node
```cpp
bool q_delete_dup(struct list_head *head)
{
if (!head) {
return false;
}
struct list_head *node = head->next;
while (node->next != head) {
element_t *tmp = list_entry(node->next, element_t, list);
if (strcmp(list_entry(node, element_t, list)->value, tmp->value) == 0) {
list_del_init(node->next);
q_release_element(tmp);
} else {
node = node->next;
}
}
return true;
}
```
### q_swap
交換佇列中鄰近的節點，不用額外指標便可 swap
```cpp
void q_swap(struct list_head *head)
{
if (!head) {
return;
}
struct list_head *node = head->next;
while (node->next != head) {
// swap
node->next->prev = node->prev;
node->prev->next = node->next;
node->next->next->prev = node;
node->prev = node->next;
node->next = node->next->next;
node->prev->next = node;
node = node->next;
}
}
```
### q_reverse
以反向順序重新排列鏈結串列, trace 過整個佇列一個一個把他們的 prev 和 next 交換
```cpp
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head)) {
return;
}
struct list_head *tmp = head->next;
head->next = head->prev;
head->prev = tmp;
struct list_head *node;
list_for_each (node, head) {
tmp = node->next;
node->next = node->prev;
node->prev = tmp;
}
}
```
### q_sort
一開始，下意識以為就是要作 quicksort, 然後打完才發現， 而且 quicksort 的 worst case 為 $O(n^2)$,故下面就繼續實作老師上課提到的 mergesort
#### quicksort
```cpp
void q_sort(struct list_head *head)
{
if (!head || head->next == head->prev) {
return;
}
struct list_head *left, *right, *pivot;
left = q_new();
right = q_new();
pivot = head->next;
list_del(pivot);
// partition
while (!list_empty(head)) {
struct list_head *tmp, *t_head;
tmp = head->next;
list_del(tmp);
t_head = (strcmp(list_entry(pivot, element_t, list)->value,
list_entry(tmp, element_t, list)->value) < 0)
? right
: left;
list_add_tail(tmp, t_head);
}
q_sort(left);
q_sort(right);
list_add_tail(pivot, left);
list_splice_tail(right, left);
q_release_element(list_entry(right, element_t, list));
}
```
#### mergesort
參照 jserv 的實作，在 mergesort 當中當作queue為單向的
```cpp
struct list_head *mergetwoqueues(struct list_head *left,
struct list_head *right)
{
struct list_head *head = NULL;
struct list_head **ptr = &head, **node = NULL;
for (; left && right; *node = (*node)->next) {
node = (strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) < 0)
? &left
: &right;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);
return head;
}
struct list_head *mergesort_list(struct list_head *head)
{
if (!head || !head->next) {
return head;
}
struct list_head *slow = head, *right;
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
right = slow->next;
slow->next = NULL;
head = mergesort_list(head);
right = mergesort_list(right);
return mergetwoqueues(head, right);
}
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *node = head->next;
head->prev->next = NULL;
node = mergesort_list(node);
head->next = node;
for (node = head; node->next; node = node->next) {
node->next->prev = node;
}
node->next = head;
head->prev = node;
}
```
## 提供新的命令 shuffle
觀察如何加入新命令， 找到 ```ADD_COMMAND``` 巨集的定義
``` cpp
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
將 ```shuffle``` 加入命令
``` cpp
ADD_COMMAND(shuffle, "| Fisher-Yates shuffle algorithm");
```
模仿 ```do_sort``` 實作 ```do_shuffle```
```cpp
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 sort on null queue");
error_check();
int cnt = q_size(l_meta.l);
if (cnt < 2)
report(3, "Warning: Calling sort 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();
}
```
### q_shuffle
依據 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 作出的函式，隨機選出node搬到最後，每次都減少能選取範圍，直到node都已經被選取過
```cpp
void q_shuffle(struct list_head *head)
{
int len = q_size(head);
if (len < 2)
return;
for (; len > 1; len--) {
int n = rand() % len;
struct list_head *cur = head->next;
for (; n; n--) {
cur = cur->next;
}
list_del(cur);
list_add_tail(cur, head);
}
}
```
## 參考資料
* [laneser](https://hackmd.io/@laneser/linux2022_lab0)
Sign in with Wallet
Connect another wallet