# Linux 核心設計 Homework1 (lab0)
contributed by < r34796Kevin >
## 簡介
實作Jserv老師的[Linux 核心設計 (Linux Kernel Internals)](http://wiki.csie.ncku.edu.tw/linux/schedule)作業1,並且盡量完成作業的額外要求
，練習開發程式的好用工具，包含：
* 學習 GNU/Linux 開發工具
* [Cppcheck](https://cppcheck.sourceforge.io/): 靜態程式碼分析工具
* [Valgrind](https://valgrind.org/): 動態程式分析工具
* 學習使用 Git 與 GitHub
* 樹立一致且易於協作的程式開發規範
* 研究自動測試機制
## 作業要求
本次作業主要實作queue並實現以下功能：
* q_new: 建立新的「空」佇列;
* q_free: 釋放佇列所佔用的記憶體;
* q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的元素。
* q_size: 計算佇列中的元素數量。
* q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* q_sort: 以遞增順序來排序鏈結串列的元素;
## 實作
**下面的程式碼會依據時間呈現從最初版本到最終版本還有紀錄下開發中遇到的bug。**
我們使用的資料型態長這樣
``` c=
typedef struct ELE {
/* Pointer to array holding string.
* This array needs to be explicitly allocated and freed
*/
char *value;
struct ELE *next;
} list_ele_t;
```
為了使 insert_tai() 和 size() 兩函式都在 O(1) 的時間複雜度，我們在queue.h增加兩個 Object, tail 和 size。
```c=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
完成一些基本的實作
#### queue_t *q_new()
為pointer q配置一個記憶體位置，初始化參數後返回記憶體位置。
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
#### void q_free(queue_t *q)
原本的版本，忘記處理`queue_t *q = NULL`的情況，
```c=
void q_free(queue_t *q)
{
/* TODO: How about freeing the list elements and the strings? */
struct ELE *cur = q->head;
struct ELE *pre = NULL;
while (cur) {
if (pre != NULL) {
free(pre->value);
free(pre);
}
pre = cur;
cur = cur->next;
}
free(pre->value);
free(pre);
/* Free queue structure */
free(q);
}
```
所以在自動評分程式中會有dereferenced a NULL or invalid pointer的提示。
> --- Trace Points
+++ TESTING trace trace-01-ops:
Test of insert_head and remove_head
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-01-ops 0/6
使用[Valgrind](https://valgrind.org/): 動態程式分析工具，發現`new、insert_head、remove head`都沒有問題，在使用`free`的時候會dereference一個NULL pointer。
> $ valgrind -q --leak-check=full ./qtest
cmd> new
q = []
cmd> ih "a"
q = ["a"]
cmd> ih "b"
q = ["b" "a"]
cmd> ih "c"
q = ["c" "b" "a"]
cmd> rh
Removed "c" from queue
q = ["b" "a"]
cmd> rh
Removed "b" from queue
q = ["a"]
cmd> rh
Removed "a" from queue
q = []
cmd> free
8251 Invalid read of size 8
==8251 at 0x10E2E0: q_free (queue.c:37)==
8251 by 0x10ADA2: do_free (qtest.c:150)
8251 by 0x10CE65: interpret_cmda (console.c:221)
8251 by 0x10D2FC: interpret_cmd (console.c:244)
8251 by 0x10DDA9: run_console (console.c:660)
8251 by 0x10C2BF: main (qtest.c:788)
8251 Address 0x0 is not stack'd, malloc'd or (recently) free'd
修改後的function如下
釋放佇列所佔用的記憶體，注意需要分別釋放struct ELE中為Value分配的記憶體空間，為了避免dereference NULL pointer所以需要`if (pre != NULL)`的判斷。
``` c=
void q_free(queue_t *q)
{
/* TODO: How about freeing the list elements and the strings? */
if (!q) {
return;
}
struct ELE *cur = q->head;
struct ELE *pre = NULL;
while (cur) {
if (pre != NULL) {
free(pre->value);
free(pre);
}
pre = cur;
cur = cur->next;
}
if (pre != NULL) {
free(pre->value);
free(pre);
}
/* Free queue structure */
free(q);
}
```
#### bool q_insert_head(queue_t *q, char *s)
在佇列開頭加入給定的新元素，如果傳入的指標是NULL則回傳false，如果分配記憶體空間失敗也要回傳false，記得為Value分配大小為`length * sizeof(char)`的記憶體空間並用`snprintf(newh->value, length, "%s", s)`賦值。
```c=
bool q_insert_head(queue_t *q, char *s)
{
/* TODO: What should you do if the q is NULL? */
if (!q) {
return false;
}
struct ELE *newh = malloc(sizeof(list_ele_t));
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
if (!newh) {
return false;
}
size_t length = strlen(s) + 1;
newh->value = (char *) malloc(length * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
snprintf(newh->value, length, "%s", s);
newh->next = q->head;
q->head = newh;
if (q->size == 0) {
q->tail = newh;
}
q->size++;
return true;
}
```
#### bool q_insert_tail(queue_t *q, char *s)
操作與`bool q_insert_head(queue_t *q, char *s)`相似，注意指標操作。
```c=
bool q_insert_tail(queue_t *q, char *s)
{
/* TODO: You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
if (q == NULL) {
return false;
}
struct ELE *newt = malloc(sizeof(list_ele_t));
if (!newt) {
return false;
}
size_t length = strlen(s) + 1;
newt->value = malloc(sizeof(char) * length);
if (!newt->value) {
free(newt);
return false;
}
snprintf(newt->value, length, "%s", s);
newt->next = NULL;
if (!q->head) {
q->head = newt;
q->tail = newt;
q->size++;
} else {
q->tail->next = newt;
q->tail = newt;
q->size++;
}
return true;
}
```
#### bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
在佇列開頭移去給定的元素。根據Jserv老師的說明：
> “remove” 這動作對於 linked list 來說，是斷開節點和節點的關聯，也就是說原本若是 A → B → C，在 remove(B) 操作完成後，就會變成 A →
C 的節點關係。特別注意到 B 這個節點其實還存在於記憶體中，只是我們無法從節點間的關係看出來。於是 “remove” 可解讀為 “take away” (將某物帶走)
“delete” 則有 “erase” 的涵義，若用於 linked list，則指某個節點將被「抹除」，對應的記憶體就會有變化
應該不用從記憶體中刪除head的記憶體。多做了`free(remove->value);
free(remove);`的動作。
``` c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head) {
return false;
}
struct ELE *remove = q->head;
if (sp) {
snprintf(sp, bufsize, "%s", remove->value);
}
q->head = q->head->next;
free(remove->value);
free(remove);
q->size--;
return true;
}
```
#### int q_size(queue_t *q)
計算佇列中的元素數量，因為每次新增跟移除節點的時候都有更新`q->size`，故可以O(1)時間完成。
```c=
int q_size(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* Remember: It should operate in O(1) time */
if (!q || !q->head) {
return 0;
}
return q->size;
}
```
#### void q_reverse(queue_t *q)
原本的版本，忘記處理`struct ELE* q->head = NULL`的情況，而且`struct ELE *tmp = cur;`指標指錯應為`struct ELE *tmp = cur->next;`
```c=
*/
void q_reverse(queue_t *q)
{
if (q) {
struct ELE *pre = NULL;
struct ELE *cur = q->head;
while (cur) {
struct ELE *tmp = cur;
cur->next = pre;
pre = cur;
cur = tmp;
}
}
}
```
>+++ TESTING trace trace-03-ops:
Test of insert_head, insert_tail, reverse, and remove_head
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Removed value gerbil != expected value squirrel
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
Error limit exceeded. Stopping command execution
--- trace-03-ops 0/6
修改後
以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素。使用三個指標`pre、cur、tmp`紀錄下Node的位置，避免更動`next`後後面的Node記憶體位置遺失。
```c=
void q_reverse(queue_t *q)
{
if (q && q->head) {
struct ELE *pre = NULL;
struct ELE *cur = q->head;
q->tail = q->head;
while (cur) {
struct ELE *tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
q->head = pre;
}
}
```
#### void q_sort(queue_t *q)
以遞增順序來排序鏈結串列的元素，這邊使用以前寫過的Linked list Mergesort來改成可以對character做排序，做完mergesort後更改head與tail指標。
```c=
void q_sort(queue_t *q)
{
if (!q || q->head == q->tail) {
return;
}
// Merge sort
q->head=mergesort(q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
做mergesort時，先用fast與slow兩個指標找出中間的Node，用`struct ELE *head2 = (slow->next); slow->next = NULL;`分成兩條Linked list，再遞迴呼叫mergesort直到剩下一個Node，然後呼叫`struct ELE* merge(struct ELE *l, struct ELE *r)`做排序。
```c=
struct ELE* mergesort(struct ELE *head1)
{
if (!(head1)->next) {
return head1;
}
struct ELE *fast = (head1)->next;
struct ELE *slow = (head1);
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
struct ELE *head2 = (slow->next);
slow->next = NULL;
head1 = mergesort(head1);
head2 = mergesort(head2);
struct ELE *newHead = merge(head1,head2);
return newHead;
}
```
`struct ELE* merge(struct ELE *l, struct ELE *r)`可以將兩段排序好的Linked list合併成一條Linked list，並且返回新的head。其中用了一個dummy node作為Linked list的起點，因此返回新的head之前需要先刪除dummy node才不會造成memory leak。
while迴圈中分別判斷`struct ELE *l`還是`struct ELE *r`的`value`比較小，直到其中之一指向`NULL`。然後把剩下的Linked list接上去。
```c=
struct ELE* merge(struct ELE *l, struct ELE *r)
{ struct ELE *dummy = malloc(sizeof(list_ele_t));
dummy->next = NULL;
struct ELE *cur=dummy;
while(l && r){
if (strcmp(l->value, r->value) < 0) {
cur->next = l;
cur = cur->next;
l = l->next;
}
else{
cur->next = r;
cur = cur->next;
r = r->next;
}
}
if(l) {
cur->next = l;
}
if(r) {
cur->next = r;
}
cur = dummy->next;
free(dummy);
return cur;
}
```
修改完所有的bug後執行自動評分程式，獲得滿分。
>--- TOTAL 100/100
## 小結
本次作業算是滿基礎的作業，以前有做過類似的C++作業，但是額外加上了一些malloc失敗的判斷，還有memory leak的檢查，還要使用Cppcheck: 靜態程式碼分析工具、Valgrind: 動態程式分析工具與github，以及第一次使用Linux開發，所以還是花了很多時間學到了很多東西。
Sign in with Wallet
Connect another wallet