# 2022q1 Homework1 (lab0)
###### tags: `Linux 核心設計` `成大課程`
contributed by < `hbr890627` >
## 實驗環境
暫時使用 WSL (Windows Subsystem for Linux)
```
$ 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
Vendor ID: GenuineIntel
CPU family: 6
Model: 151
Model name: 12th Gen Intel(R) Core(TM) i5-12400
Stepping: 5
CPU MHz: 2495.999
BogoMIPS: 4991.99
Virtualization: VT-x
Hypervisor vendor: Microsoft
Virtualization type: full
L1d cache: 288 KiB
L1i cache: 192 KiB
L2 cache: 7.5 MiB
L3 cache: 18 MiB
```
## 進度
* 環境架設
* 暫時使用 WSL (Windows Subsystem for Linux)
<s>
* 2/20: 觀看[lab0 解說影片](https://www.youtube.com/watch?v=CMcbfQiQIHg)
</s>
:::warning
不需要在此標注日期，修改紀錄都在 HackMD 中。只是「觀看」不能算是成果，你至少該提出問題和摘要你所學到的事物。
:notes: jserv
:::
* 嘗試修改 queue.c
## queue.c
### q_new
```c
struct list_head *q_new()
{
element_t *e = malloc(sizeof(element_t));
if (!e)
return NULL;
e->value = NULL;
INIT_LIST_HEAD(&e->list);
return &e->list;
}
```
### q_free
```c
void q_free(struct list_head *l) {}
```
### q_insert_head
```C
bool q_insert_head(struct list_head *head, char *s)
{
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = s;
list_add(&e->list, head);
return true;
}
```
:::danger
注意書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
:::
在 `make check` 後發現錯誤。
```bash
cmd> ih dolphin
ERROR: Need to allocate and copy string for new queue element
```
發現並未分配記憶體給 `e->value` ，修改程式碼。
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = malloc(sizeof(s));
strcpy(e->value, s);
list_add(&e->list, head);
return true;
}
```
在 `make check` 時不再發生 ERROR ，但無法 git commit 。
```
[2022-02-22T03:32:42.314Z] Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/hbr/linux2022/lab0-c/queue.c
45: strcpy(e->value, s);
Read 'Common vulnerabilities guide for C programmers' carefully.
https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml
```
根據 https://security.web.cern.ch/recommendations/en/codetools/c.shtml ，將不安全的 `strcpy` ，改為 `strncpy` ，並補上字串的結尾`\0`。
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = malloc(sizeof(char) * (strlen(s) + 1));
strncpy(e->value, s, strlen(s));
*(e->value + strlen(s)) = '\0';
list_add(&e->list, head);
return true;
}
```
發現有些人使用 `strdup` 取代 `strcpy` ，雖然實作起來較方便，但這不包含在C的標準函式庫，不利於程式的移植性。
[參考資料](https://www.itread01.com/article/1440470244.html)
### q_insert_tail
大致上與 `q_insert_head` 差不多，將 `list_add` 改為 `list_add_tail` 。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = malloc(sizeof(char) * (strlen(s) + 1));
strncpy(e->value, s, strlen(s));
*(e->value + strlen(s)) = '\0';
list_add(&e->list, head);
return true;
}
```
### q_remove_head
要移除第一個節點，實際上就是要移除 `head->next` ，而在 `list.h` 中，有 `list_first_entry` 這個巨集可以使用，用來精簡程式碼。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_first_entry(head, element_t, list);
list_del(&node->list);
if (sp) {
strncpy(sp, node->value, bufsize);
sp[bufsize - 1] = '\0';
}
return node;
}
```
### q_remove_tail
與 `q_remove_head` 幾乎相同，將 `list_first_entry` 改為 `list_last_entry` 即可。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_last_entry(head, element_t, list);
list_del(&node->list);
if (sp) {
strncpy(sp, node->value, bufsize);
sp[bufsize - 1] = '\0';
}
return node;
}
```
### q_release_element
此函式會被外部程式使用到，不用修改即可。
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
### q_size
直接使用作業說明中的範例程式。
[作業說明-lab0-牛刀小試](https://hackmd.io/@sysprog/linux2022-lab0#%E7%89%9B%E5%88%80%E5%B0%8F%E8%A9%A6)
```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
參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94)，使用龜兔賽跑的方式找到中間節點。
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *slow = head->next, *fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
### q_delete_dup
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
if (!head)
return false;
element_t *entry, *safe;
char *value = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
if (strcmp(value, entry->value) == 0) {
list_del(&entry->list);
q_release_element(entry);
} else {
value = entry->value;
}
}
return true;
}
```
此段程式碼會出現 `You dereferenced a NULL or invalid pointer` ，但一直找不到問題出現在哪，在參考 [mm0809](https://hackmd.io/@2QYhHFatQmWFUgzITEcRjA/B1lsUihy9#q_delete_dup) 後，發現只要使用`""`初始化 `value` 即可。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
if (!head)
return false;
element_t *entry, *safe;
char *value = "";
list_for_each_entry_safe (entry, safe, head, list) {
if (strcmp(value, entry->value) == 0) {
list_del(&entry->list);
q_release_element(entry);
} else {
value = entry->value;
}
}
return true;
}
```
### q_swap
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
struct list_head *node = head->next;
while (node != head && node->next != head) {
struct list_head *next = node->next;
list_del(node);
list_add(node, next);
node = node->next;
}
}
```
### q_reverse
想要實作 reverse 的其中一個方式，就是從頭將結點移出，再照順序將結點 enqueue 即可，但根據作業要求，在此函式中，不能再額外分配記憶體用來暫時儲存暫時移出的節點，在思考解決方式時，參考 [mm0809](https://hackmd.io/@2QYhHFatQmWFUgzITEcRjA/B1lsUihy9#q_reverse) 的方式，只要先固定第一個指標後，不斷將後面的節點移到前面即可。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *tmp = head->next;
for (struct list_head *node = tmp->next; tmp->next != head;
node = tmp->next) {
list_del(node);
list_add(node, head);
}
}
```
### q_sort
使用到[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94)中的 mergesort ，但是其實作的是單向的鏈結串列，必須在 merge 結束後，將 `prev` 的節點補上。
```c
/*
* The sub-function of q_sort
*/
struct list_head *mergeTwoLists(struct list_head *h1, struct list_head *h2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; h1 && h2; *node = (*node)->next) {
node = strcmp(list_entry(h1, element_t, list)->value,
list_entry(h2, element_t, list)->value) < 0
? &h1
: &h2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) h1 | (uintptr_t) h2);
return head;
}
/*
* The sub-function of q_sort
*/
struct list_head *mergesort(struct list_head *head)
{
if (!head || !head->next)
return head;
// find middle node
struct list_head *slow = head;
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow->next;
slow->next = NULL;
struct list_head *left = mergesort(head), *right = mergesort(mid);
return mergeTwoLists(left, 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))
return;
head->prev->next = NULL;
head->next->prev = NULL;
struct list_head *sorted = mergesort(head->next);
// link head & fix prev
head->next = sorted;
sorted->prev = head;
struct list_head *temp = sorted;
while (temp->next) {
temp->next->prev = temp;
temp = temp->next;
}
head->prev = temp;
temp->next = head;
}
```
Sign in with Wallet
Connect another wallet