---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < [Duodenum87](https://github.com/Duodenum87/lab0-c) >
> [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
## 實驗環境
```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): 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: GenuineIntel
CPU family: 6
Model: 167
Model name: 11th Gen Intel(R) Core(TM) i7-11700 @ 2.50GHz
Stepping: 1
CPU MHz: 2500.000
CPU max MHz: 4900.0000
CPU min MHz: 800.0000
BogoMIPS: 4992.00
Virtualization: VT-x
L1d cache: 384 KiB
L1i cache: 256 KiB
L2 cache: 4 MiB
L3 cache: 16 MiB
NUMA node0 CPU(s): 0-15
```
## 開發紀錄
### q_new
> Create empty queue.
> Return NULL if could not allocate space.
參照 list API 初始化 list node
```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
> Free all storage used by queue.
在撰寫此函式時，碰到了迭代 list 的問題，最後參照 list API 中的 list_for_each_entry 才得以順利完成。其中又 list_for_each_entry_safe 迭代時會預先儲存下一個節點，故刪除不會影響迴圈。
```c
void q_free(struct list_head *l)
{
if (l == NULL)
return;
element_t *ele, *tmp;
list_for_each_entry_safe (ele, tmp, l, list) {
free(ele->value);
free(ele);
}
free(l);
}
```
### q_insert_head
> Attempt to insert element at head of queue.
> Return true if successful.
> Return false if q is NULL or could not allocate space.
`malloc` 時需注意，配置的空間大小需要包含 string terminator ``'\0'``，即 strlen(s) + 1
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *newh = malloc(sizeof(element_t));
if (newh == NULL)
return false;
int l = strlen(s);
newh->value = malloc(sizeof(char) * (l + 1));
// one more byte for '\0'
if (newh->value == NULL) {
free(newh);
return false;
}
strncpy(newh->value, s, l);
newh->value[l] = '\0';
// set the string terminator
list_add(&newh->list, head);
return true;
}
```
### q_insert_tail
> Attempt to insert element at tail of queue.
> Return true if successful.
> Return false if q is NULL or could not allocate space.
與前述 `q_insert_head` 只相差產生節點所用的 API 不同
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *newt = malloc(sizeof(element_t));
if (newt == NULL)
return false;
int l = strlen(s);
newt->value = malloc(sizeof(char) * (l + 1));
/* one more byte for '\0' */
if (newt->value == NULL) {
free(newt);
return false;
}
strncpy(newt->value, s, l);
// set the string terminator
newt->value[l] = '\0';
list_add_tail(&newt->list, head);
return true;
}
```
### q_remove
Issue: not in constant time
Fix: 未注意到題目中 `*sp` 可能為 `NULL`，提早結束函式
Fix: 題幹之 remove 並不需要 `free` 任何空間
`list_entry` 指向欲移除之節點元素後，即可斷開鏈結，隨後複製其內容。
#### head
> Attempt to remove element from head of queue.
> Return target element.
> Return NULL if queue is NULL or empty.
```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 *fptr = list_first_entry(head, element_t, list);
// ptr redirect
list_del(head->next);
// to copy string
if (sp != NULL) {
strncpy(sp, fptr->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return fptr;
}
```
#### tail
> Attempt to remove element from tail of queue.
> Return target element.
> Return NULL if queue is NULL or empty.
```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 *fptr = list_last_entry(head, element_t, list);
// ptr redirect
list_del(head->prev);
// to copy string
if (sp != NULL) {
strncpy(sp, fptr->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return fptr;
}
```
### q_size
> Return number of elements in queue.
> Return 0 if q is NULL or empty
即[作業要求](https://hackmd.io/@sysprog/linux2022-lab0#牛刀小試)所提供之方法
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_delete_mid
> Delete the middle node in list
> from [leetcode](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
兩個指標分別走一步及兩步，則當 `fast` 走 n 步時，`slow` 即走 n / 2 步，也就是欲刪除之 middle node
```c
bool q_delete_mid(struct list_head *head)
{
if (head == NULL || list_empty(head))
return false;
struct list_head *fast = head->next->next, *slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
element_t *ele = list_entry(slow, element_t, list);
list_del(slow);
q_release_element(ele);
return true;
}
```
### q_delete_dup
> Delete all nodes that have duplicate string,
leaving only distinct strings from the original list.
Return true if successful.
Return false if list is NULL.
>
> Note: this function always be called after sorting
> from [leetcode](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
因為 list 已經排序過，所以重複值之節點必然相鄰，也就是說每次迴圈只需檢查是否與上個迭代元素值相同即可。`cmp` 用以儲存前個迭代之節點元素值，與當下值比較則可以判斷是否有重複值。
```c
bool q_delete_dup(struct list_head *head)
{
if (head == NULL || list_empty(head))
return false;
char *cmp = NULL;
element_t *ele = NULL, *tmp = NULL;
list_for_each_entry_safe (ele, tmp, head, list) {
if (strcmp(cmp, ele->value) == 0 && cmp) {
list_del(&ele->list);
free(ele->value);
free(ele);
} else {
cmp = ele->value;
}
}
return true;
}
```
Fix: 初始版本中沒有初始化 `cmp` 導致無法進入迴圈
```diff
bool q_delete_dup(struct list_head *head)
{
...
list_for_each_entry_safe(ele, tmp, head, list) {
- if (strcmp(cmp, ele->value) == 0 && cmp) {
+ if (!cmp)
+ cmp = ele->value;
+ if (strcmp(cmp, ele->value) == 0) {
...
}
```
### q_swap
>Attempt to swap every two adjacent nodes.
`list_move` 原用以將某 list 移至另一 list 之首，或可用以將單兩節點做交換
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (head == NULL || list_empty(head))
return;
struct list_head *i;
list_for_each (i, head) {
// to identify odd list count
if (i->next == head)
break;
list_move(i, i->next);
}
}
```
### q_reverse
>Reverse elements in queue
```c
void q_reverse(struct list_head *head)
{
if (head == NULL || list_empty(head))
return;
struct list_head *i;
for (i = head; i->next != head->prev; i = i->next) {
list_move(head->prev, i);
}
}
```
### q_sort
#### list_merge
用以排序已分離之 list
```c
struct list_head *list_merge(struct list_head *l1, struct list_head *l2)
{
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
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 = list_merge(l1->next, l2);
return l1;
} else {
l2->next = list_merge(l1, l2->next);
return l2;
}
}
```
該遞迴方法遲遲無法通過 perf 評分，參照[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)中的解法，對其以指標的指標方式改寫迭代 list 。
```c
struct list_head *list_merge(struct list_head *l1, struct list_head *l2)
{
struct list_head *head = NULL;
struct list_head **ptr = &head, **node = NULL;
for (; l1 && l2; *node = (*node)->next) {
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) {
node = &l1;
*ptr = *node;
ptr = &(*ptr)->next;
} else {
node = &l2;
*ptr = *node;
ptr = &(*ptr)->next;
}
}
*ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
return head;
}
```
#### list_split
與前述 `q_delete_mid` 所使用的兩個指摽方式相同，用以對半拆分 list。不斷遞迴直到 list 僅剩一個以下元素後開始合併。
```c
struct list_head *list_spilt(struct list_head *head)
{
if (head == NULL || head->next == NULL)
return head;
// find the middle node to spilt
struct list_head *fast = head->next, *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
// merge sperately
struct list_head *l1 = list_spilt(head);
struct list_head *l2 = list_spilt(fast);
return list_merge(l1, l2);
}
```
#### q_sort
```c
void q_sort(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
// unlink the end node
head->prev->next = NULL;
head->next = list_spilt(head->next);
// relink the ptr of list
struct list_head *node = head;
while (node->next != NULL) {
node->next->prev = i;
node = node->next;
}
// relink the end node
head->prev = node;
node->next = head;
}
```
### 為 qtest 提供 shuffle 命令
首先參照 [Fisher–Yates shuffle algorithm](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) ，演算法之核心概念乃為從 list 的最尾端元素，逐個與隨機產生出的位置元素，進行交換。其 psuedo code 為以下：
```
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
又根據觀察 `qtest.c` 中的 `do_swap()` `do_reverse()` 等函式，判斷需要預先呼叫 `exception_setup()` 以保證執行正確，臨摹出以下函式
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes 0 arguments", argv[0]);
return false;
}
if (l_meta.l == NULL) {
report(3, "Warning: Calling shuffle on null queue");
return false;
}
int cnt = q_size(l_meta.l);
if (cnt < 2) {
report(3, "Warning: Calling shuffle on single node queue");
return false;
}
set_noallocate_mode(true);
if (exception_setup(true)) {
// to iterate from tail to head
struct list_head *swaper = l_meta.l->prev;
for (; --cnt; swaper = swaper->prev) {
int r = rand() % cnt + 1;
struct list_head *curr = l_meta.l->next;
for (int i = 0; i < r; i++) {
curr = curr->next;
}
element_t *c = list_entry(curr, element_t, list);
element_t *s = list_entry(swaper, element_t, list);
char *tmp = c->value;
c->value = s->value;
s->value = tmp;
}
}
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
結果如下
```
cmd> new
l = []
cmd> it 22
l = [22]
cmd> it 12
l = [22 12]
cmd> it 9128
l = [22 12 9128]
cmd> it 18
l = [22 12 9128 18]
cmd> it 192
l = [22 12 9128 18 192]
cmd> sort
l = [12 18 192 22 9128]
cmd> shuffle
l = [12 192 18 22 9128]
cmd> shuffle
l = [12 9128 192 22 18]
cmd> sort
l = [12 18 192 22 9128]
cmd> shuffle
l = [12 22 192 18 9128]
```
Sign in with Wallet
Connect another wallet