###### tags: `Linux核心`
# 2020q3 Homework1 (lab0)
contributed by < `heysun0728` >
## 實驗環境
```
$ uname -a
Linux yr 5.4.0-45-generic #49-Ubuntu SMP Wed Aug 26 13:38:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
```
## 作業要求
1. - [x] 修改 queue.c 及 queue.h 完成以下內容：
* `q_new` : 建立新的「空」佇列。
* `q_free`: 釋放佇列所佔用的記憶體。
* `q_insert_head`: 在佇列開頭加入給定的新元素 (以 LIFO 準則)。
* `q_insert_tail`: 在佇列尾端加入給定的新元素 (以 FIFO 準則)。
* `q_remove_head`: 在佇列開頭移除給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式只能重排已經存在的元素。
* `q_sort`: 以遞增順序來排序鏈結串列的元素。
2. - [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 simulation 過程中的記憶體使用量
3. - [ ] 研讀論文 `Dude, is my code constant time?`，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度
[詳細作業要求](https://hackmd.io/@sysprog/2020-lab0)
## Queue實作細節
#### q_new
* 注意是否已為 `queue_t` 內所有變數進行初始化。
* 檢查 `malloc()` 回傳是否為空指標。
```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;
}
```
#### q_free
* 實作方法為從頭至尾一邊走訪一邊 free ，注意節點空間也須釋放。
* `list_ele_free()` : 預計 free element 動作會出現多次而撰寫。
```c
void list_ele_free(list_ele_t *e)
{
free(e->value);
free(e);
}
```
```c
void q_free(queue_t *q)
{
if (q) {
list_ele_t *e = q->head;
list_ele_t *next;
while (e) {
next = e->next;
list_ele_free(e);
e = next;
}
free(q);
}
}
```
#### q_insert_head
* `list_ele_new()` 除了配置 element 空間外, 還會設定element內每個變數的值, 建立原因為避免 repeated code。
* 注意若 `e->value` 使用 `malloc` 配置記憶體失敗, 要同時將 `e` 已配置好的空間釋放掉, 避免memory leak。
* 注意若此 element 為該 list 中的第一個, 須修改 `q->tail`。
* 注意 `strncpy()` 不能保證字串一定是 null 結尾, 因此此處手動增加。
```c
list_ele_t *list_ele_new(char *v, list_ele_t *n)
{
/* Allocate space for new element*/
list_ele_t *e = malloc(sizeof(list_ele_t));
if (!e)
return NULL;
/* Allocate space for the value string and copy it */
size_t vlen = strlen(v);
e->value = malloc(vlen * sizeof(char) + 1);
if (!e->value) {
free(e);
return NULL;
}
strncpy(e->value, v, vlen);
e->value[vlen] = '\0';
e->next = n;
return e;
}
```
```c
bool q_insert_head(queue_t *q, char *s)
{
if (!q || !s)
return false;
/* Allocate space and copy string for new element*/
list_ele_t *new = list_ele_new(s, q->head);
if (!new)
return false;
/* Update list information */
if (q->size == 0)
q->tail = new;
q->head = new;
q->size++;
return true;
}
```
#### q_insert_tail
* 注意若此 element 為該 list 中的第一個, 須修改 `q->head`。
```c
bool q_insert_tail(queue_t *q, char *s)
{
if (!q || !s)
return false;
/* Allocate space and copy string for new element*/
list_ele_t *new = list_ele_new(s, NULL);
if (!new)
return false;
/* Update list information */
if (q->size == 0)
q->head = new;
else
q->tail->next = new;
q->tail = new;
q->size++;
return true;
}
```
#### q_remove_head
```c
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
/* Copy the removed string to *sp */
list_ele_t *rmv = q->head;
if (sp) {
size_t vlen = strlen(rmv->value);
if (vlen > bufsize - 1)
vlen = bufsize - 1;
strncpy(sp, rmv->value, vlen);
sp[vlen] = '\0';
}
/* Update list information */
if (q->tail == rmv)
q->tail = NULL;
q->head = rmv->next;
q->size--;
list_ele_free(rmv);
return true;
}
```
#### q_size
```c
int q_size(queue_t *q)
{
if (!q || !q->head)
return 0;
return q->size;
}
```
#### q_reverse
* 循序走遍每一個 element ，每經過一個就將其的 `*next` 所指向的目標換成其前方 element。
```c
void q_reverse(queue_t *q)
{
if (!q || q->size < 2)
return;
list_ele_t *e = q->head;
list_ele_t *nxt, *pre = NULL;
q->tail = e;
while (e) {
nxt = e->next;
e->next = pre;
pre = e;
e = nxt;
}
q->head = pre;
}
```
#### q_sort
* 使用 merge sort 實做。
* `split()` : 參考 [AndybnA](https://hackmd.io/@AndybnA/lab0-c) 寫法透過 `slow` 與 `fast` 兩變數來快速找到切割點，`slow` 一次移動一格，而 `fast` 一次移動兩格，當 `fast` 移動到尾端時 `slow` 就是我們找尋的切割點。
```c
void split(list_ele_t *head, list_ele_t **l, list_ele_t **r)
{
list_ele_t *slow, *fast;
slow = head;
fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
*r = slow->next;
*l = head;
slow->next = NULL;
}
```
```c
list_ele_t *merge(list_ele_t *l, list_ele_t *r)
{
list_ele_t *head = NULL;
list_ele_t **tmp = &head;
while (l && r) {
if (strnatcmp(l->value, r->value) < 0) {
*tmp = l;
l = l->next;
} else {
*tmp = r;
r = r->next;
}
tmp = &((*tmp)->next);
}
if (l)
*tmp = l; // l and r are already null-terminated
if (r)
*tmp = r;
return head;
}
```
```c
list_ele_t *m_sort(list_ele_t *head)
{
if (!head || !head->next) // if only 1 or 0 elements left in this list
return head;
list_ele_t *l = NULL, *r = NULL;
split(head, &l, &r);
return merge(m_sort(l), m_sort(r));
}
```
```c
void q_sort(queue_t *q)
{
if (!q || q->size < 2)
return;
q->head = m_sort(q->head);
}
```
#### 簡化程式碼或提昇執行效率
:::info
To do
:::
## Valgrind檢查
### 執行`make valgrind`
得分100/100，無記憶體錯誤
### massif 實驗
```
$ valgrind --tool=massif --stacks=yes --time-unit=i ./qtest
```
##### 實驗一
```
new
ih RAND 10
sort
reverse
sort
free
```
上圖使用 massif visualizer 工具生成。透過此圖可看出程式在開始執行後使用 malloc 的記憶體數量持續上升，應是 `ih` 指令為新增 list node 而致。而後整體記憶體使用量在一段時間維持不變，應是因為 `sort` 與 `reverse` 不額外要求記憶體。而後由於程式結束前呼叫了 `free`，因此記憶體使用量逐漸減少至0。
##### 實驗二
```
new
ih RAND 10
rh
rh
rh
rh
rh
```
由於想繼續觀察使用 `rh` 移除節點的記憶體表現，於是進行了實驗二。與實驗一相比，圖片左半多了 `do_remove_head` 所使用的記憶體，應是由於 `rh` 動作使用額外空間來存取被刪除節點的 `value` 值而增加。
##### 實驗三
```
new
ih RAND 10
rhq
rhq
rhq
rhq
rhq
```
為了驗證實驗二得出的結論，將實驗二使用的 `rh` 改成 `rhq` 觀察記憶體使用狀況。可看出實驗二進行移除節點時，發生的記憶體使用增加情況，在此處並沒有發生。
## 論文閱讀
:::info
To do
:::
Sign in with Wallet
Connect another wallet