---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `StevenChou499` >
## 實驗環境
```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): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Core(TM) i5-4690 CPU @ 3.50GHz
Stepping: 3
CPU MHz: 2962.442
CPU max MHz: 3900.0000
CPU min MHz: 800.0000
BogoMIPS: 6983.77
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-3
```
## queue.c 開發過程
### q_new
創造一個空的佇列，先宣告一個指向 `list_head` 的指標變數 `head` ，再用 `malloc` 配置記憶體給 `head` ，透過 `INIT_LIST_HEAD(head) `將 `next` 以及 `prev` 均指向自己。若 `malloc` 失敗則會回傳 `NULL` 至 `head` ，所以 `malloc` 成功會回傳真正的指標，失敗會回傳 `NULL` 。
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(head);
return head;
}
```
**修改程式碼：**
之後再加上若 `head` 成功 `malloc` 再進入初始化，但之後在 `make check` 時，會一直跳出 `there are n blocks still allocated` ，目前懷疑是 `head` 記憶體配置失敗後不會進入初始化，但其實是有成功配置的，因此在配置失敗後再執行 `free(head)` 釋放記憶體，最後回傳 `NULL` 。
* ***以下為完整的程式碼：***
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head) {
INIT_LIST_HEAD(head);
return head;
}
free(head);
return NULL;
}
```
其中有使用到 `list.h` 的 `INIT_LIST_HEAD()` ，其實做方式為下：
>**INIT_LIST_HEAD()**
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
### q_free
先定義一指標變數 `tmp = l->next` ，若 `tmp` 不等於 `l` ，則代表還沒回到 `head` ，因此定義一個指向 `element_t` 的指標變數 `del_el` ，由 `container_of` 找出相對應的 `element_t *`，再將 `tmp` 只向下一個節點，同時釋放 `value` 以及自己本身的記憶體空間，直到回到 `head` 為止。最後再 `free(tmp)`。
```c
void q_free(struct list_head *l)
{
if(!l)
return;
struct list_head *tmp = l->next;
while (tmp != l) {
element_t *del_el;
del_el = container_of(tmp, element_t, list);
tmp = tmp->next;
free(del_el->value);
free(del_el);
}
free(tmp);
}
```
**修改程式碼：**
之後修改了判斷式，先判斷 `l` 是否存在，存在後先依序訪問各個節點並將其刪除並釋放記憶體，直到 `tmp` 剛好與 `head` 相同時再跳出 `while` 判斷式，最後將自己也刪除並釋放記憶體。
* ***以下為完整的程式碼：***
```c
void q_free(struct list_head *l)
{
if (l) {
struct list_head *tmp = l->next;
while (tmp != l) {
element_t *del_el;
del_el = container_of(tmp, element_t, list);
tmp = tmp->next;
q_release_element(del_el);
}
free(l);
}
}
```
其中有使用到 `list.h` 的 `container_of()` ，其實做方式為下：
>**container_of()**
```c
#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#else
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif
```
### q_insert_head
先透過 `malloc` 配置空間給指向 `element_t` 的指標變數 `new_el` ，若 `malloc` 成功，則配置記憶體給 `new_el` 的 `value` ，利用 `strncpy` 複製 `s` 的內容。最後藉由 `list_add `加入 `head` 的下一個節點，回傳` true` ，若 `malloc` 失敗則回傳 `false` 。
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new_el = malloc(sizeof(element_t));
if(new_el){
new_el->value = (char *)malloc(strlen(s) + 1);
strncpy(new_el->value, s, strlen(s) + 1);
list_add(&new_el->list, head);
return true;
}
return false;
}
```
**修改程式碼：**
先判斷 `head` 是否存在，若存在則配置一 `element_t` 的記憶體。若配置成功且 `s` 並不是 `NULL` 則配置記憶體空間給新節點的字串，複製字串內容並加入佇列的第一位，再回傳 `true` 。因為也會遇到配置失敗但 `make check` 時卻回傳 `there are n blocks still allocated` ，因次只要配置失敗都會再 `free()` 相關的指標變數，並回傳 `false` 。
* ***以下為完整的程式碼：***
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_el = malloc(sizeof(element_t));
if (new_el && s) {
new_el->value = malloc(strlen(s) + 1);
if (new_el->value) {
strncpy(new_el->value, s, strlen(s));
*(new_el->value + strlen(s)) = '\0';
list_add(&new_el->list, head);
return true;
}
free(new_el->value);
}
free(new_el);
return false;
}
```
其中有使用到 `list.h` 的 `list_add()` ，其實做方式為下：
>**list_add()**
```c
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
### q_insert_tail
先透過 `malloc` 配置空間給指向 `element_t` 的指標變數 `new_el` ，若 `malloc` 成功，則配置記憶體給 `new_el` 的 `value` ，利用 `strncpy` 複製 `s` 的內容。最後藉由 `list_add` 加入 `head` 的上一個節點，回傳 `true` ，若 `malloc` 失敗則回傳 `false` 。完整程式碼如下：
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new_el = malloc(sizeof(element_t));
if(new_el){
new_el->value = (char *)malloc(strlen(s) + 1);
strncpy(new_el->value, s, strlen(s) + 1);
list_add(&new_el->list, head);
return true;
}
return false;
}
```
**修改程式碼：**
先判斷 `head` 是否存在，若存在則配置一 `element_t` 的記憶體。若配置成功且 `s` 並不是 `NULL` 則配置記憶體空間給新節點的字串，複製字串內容並加入佇列的最後一位，再回傳 `true` 。因為也會遇到配置失敗但 `make check` 時卻回傳 `there are n blocks still allocated` ，因次只要配置失敗都會再 `free()` 相關的指標變數，並回傳 `false` 。
* ***以下為完整的程式碼：***
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_el = malloc(sizeof(element_t));
if (new_el && s) {
new_el->value = malloc(strlen(s) + 1);
if (new_el->value) {
strncpy(new_el->value, s, strlen(s));
*(new_el->value + strlen(s)) = '\0';
list_add_tail(&new_el->list, head);
return true;
}
free(new_el->value);
}
free(new_el);
return false;
}
```
其中有使用到 `list.h` 的 `list_add_tail()` ，其實做方式為下：
>**list_add_tail()**
```c
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
### q_remove_head
先測試 `head` 是否為 `NULL` 或是空的，若符合以上規則則直接回傳 `NULL` 。再利用 `container_of` 找出 `head` 的下一個指標。計算出 `bufsize` 與 `strlen(rem_el) + 1` 誰比較小，代入 `char_len` 。若 `sp` 存在則重新配置記憶體並複製 `rem_el->value` 的內容，移除該節點並回傳。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head && !list_empty(head)) {
element_t *rem_el = container_of(head->next, element_t, list);
int char_len = strlen(rem_el->value) + 1 < bufsize
? strlen(rem_el->value) + 1
: bufsize;
if (sp) {
sp = realloc(sp, char_len);
strncpy(sp, rem_el->value, char_len - 1);
*(sp + char_len - 1) = '\0';
list_del(&rem_el->list);
return rem_el;
}
return rem_el;
}
return NULL;
}
```
**修改程式碼：**
在進行 `make test` 時會 `trace-07` 會有 `malloc(): mismatching next->prev_size (unsorted)` 的錯誤產生，在將 `realloc` 去除掉後便沒有錯誤了。
* ***以下為完整的程式碼：***
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head && !list_empty(head)) {
element_t *rem_el = list_entry(head->next, element_t, list);
int char_len = strlen(rem_el->value) < bufsize - 1
? strlen(rem_el->value)
: bufsize - 1;
if (sp && (char_len > 0)) {
strncpy(sp, rem_el->value, char_len + 1);
*(sp + char_len) = '\0';
}
list_del(&rem_el->list);
return rem_el;
}
return NULL;
}
```
其中有使用到 `list.h` 的 `list_del()` 與 `list_empty()`，其實做方式為下：
>**list_del()**
```c
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
>**list_empty()**
```c
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
### q_remove_tail
先測試 `head` 是否為 `NULL` 或是空的，若符合以上規則則直接回傳 `NULL` 。再利用 `container_of` 找出 `head` 的上一個指標。計算出 `bufsize` 與 `strlen(rem_el) + 1` 誰比較小，代入 `char_len` 。若 `sp` 存在則重新配置記憶體並複製 `rem_el->value` 的內容，移除該節點並回傳。完整程式碼如下：
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (head && !list_empty(head)) {
element_t *rem_el = container_of(head->next, element_t, list);
int char_len = strlen(rem_el->value) + 1 < bufsize
? strlen(rem_el->value) + 1
: bufsize;
if (sp) {
sp = realloc(sp, char_len);
strncpy(sp, rem_el->value, char_len - 1);
*(sp + char_len - 1) = '\0';
list_del(&rem_el->list);
return rem_el;
}
return rem_el;
}
return NULL;
}
```
**修改程式碼：**
在進行 `make test` 時會 `trace-07` 會有 `malloc(): mismatching next->prev_size (unsorted)` 的錯誤產生，在將 `realloc` 去除掉後便沒有錯誤了。
* ***以下為完整的程式碼：***
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (head && !list_empty(head)) {
element_t *rem_el = list_entry(head->prev, element_t, list);
int char_len = strlen(rem_el->value) < bufsize - 1
? strlen(rem_el->value)
: bufsize - 1;
if (sp) {
strncpy(sp, rem_el->value, char_len + 1);
*(sp + char_len) = '\0';
}
list_del(&rem_el->list);
return rem_el;
}
return NULL;
}
```
### q_release_element
此函式不可更動
* ***以下為完整的程式碼：***
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
### q_size
先定義一區域變數 `i=0` ，利用 `!list_empty(head)` 確認佇列是否為空的，若為空的則定義一個指標變數 `tmp` 指向 `head->next` 。若 `tmp` 不等於 `head` 則 `i++` 且 `tmp` 指向 `tmp->next` ，最後回傳 `i` 。
* ***以下為完整的程式碼：***
```c
int q_size(struct list_head *head)
{
int i = 0;
if(!list_empty(head)){
struct list_head *tmp = head->next;
while(tmp != head){
i++;
tmp = tmp->next;
}
}
return i;
}
```
### q_delete_mid
先找出佇列的總節點個數，除以2後建立一指向 `struct list head` 的指標變數 `tmp` ，一直跳入下一個節點直到走到中間，利用 `list_del` 移除該節點後回傳 `true` ，若 `head` 不存在或是為空佇列則回傳 `false` 。
```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)) {
int n = q_size(head) / 2;
struct list_head *tmp = head;
for (int i = 0; i != n; i++) {
tmp = tmp->next;
}
list_del(tmp);
return true;
}
return false;
}
```
:::warning
思考避免呼叫 `q_size` 的方法，降低記憶體存取的數量。
:notes: jserv
:::
>好的，學生再想想看，謝謝老師。[name=StevenChou43]
**修改程式碼：**
為了不使用 `q_size` 計算總節點的數量，我使用一個一次移動一格的指標 `slow` 與一次移動兩格的指標 `fast` 。若 `fast` 已經與 `head` 重疊或是下一個是 `head` ，則停止移動並刪除 `slow` 的節點。最後回傳 `true` 。
* ***以下為完整的程式碼：***
```c
bool q_delete_mid(struct list_head *head)
{
if (head && !list_empty(head)) {
struct list_head *slow = head->next, *fast = slow->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;
}
return false;
}
```
### q_delete_dup
先確認 `head` 是否存在並且至少存在兩個以上的元素。接著創造三個指向 `struct list_head` 的指標變數， `*tmp1 = head->next` 、`tmp2 = tmp1->next` 和 `tmp = NULL` 。接著找出 `tmp1` 與 `tmp2` 分別代表的字串，若不同則分別至向下一個元素。若遇到字串內容相同，則鄉用 `tmp = tmp1` 將重複元素中的第一個位置記下來，再將 `tmp2` 元素刪掉並跳至下一個元素，繼續進行比較，直到不同或是 `tmp2` 已經與 `head` 重疊（代表已經完全比完了）則跳出 `while` 迴圈，並將 `tmp1` 與 `tmp2` 的位置各前進一格。此時 `tmp` 的位置仍是需要被刪除的，藉由 `if(tmp != NULL)` 可以知道是否有元素重複，若重負責刪除 `tmp` 的元素。此時仍必須再比較一次看使否 `tmp2` 與 `head` 的位置重疊。若重疊則直接跳出迴圈，回傳 `true` 。
* ***以下為完整的程式碼：***
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (head && !list_empty(head) && !list_is_singular(head)) {
struct list_head *tmp1 = head->next;
struct list_head *tmp2 = tmp1->next;
struct list_head *tmp = NULL;
while (tmp1 != head) {
element_t *del_el_1 = list_entry(tmp1, element_t, list);
element_t *del_el_2 = list_entry(tmp2, element_t, list);
while (!strcmp(del_el_1->value, del_el_2->value)) {
tmp = tmp1;
list_del(tmp2);
q_release_element(list_entry(tmp2, element_t, list));
tmp2 = tmp1->next;
del_el_2 = list_entry(tmp2, element_t, list);
if (tmp2 == head)
break;
}
tmp1 = tmp2;
tmp2 = tmp1->next;
if (tmp != NULL) {
list_del(tmp);
q_release_element(list_entry(tmp, element_t, list));
tmp = NULL;
}
if (tmp2 == head)
break;
}
return true;
}
return false;
}
```
其中有使用到 `list.h` 的 `list_is_singular()` ，其實做方法如下：
>**list_is_singular()**
```c
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
### q_swap
首先檢查 `head` 是否存在或是只有一個以下的元素，若為上述情況則直接跳出該程式。接著指標 `curr` 指向 `head` 的下一個 `list_head` ，進入迴圈，指標 `tmp` 指向 `curr` 的下一個 `list_head` 。先使用 `list_del` 除去 `curr` ，再將 `curr` 利用 `list_add` 加入 `tmp` 的下一個元素位置，接著將 `curr` 移至下下個位置。繼續上述的動作直到 `curr` 或是 `curr` 的下一個元素是 `head` 。
* ***以下為完整的程式碼：***
```c
void q_swap(struct list_head *head)
{
if (head && !list_empty(head) && !list_is_singular(head)) {
struct list_head *curr = head->next;
for (; !(curr == head || curr->next == head); curr = curr->next) {
struct list_head *tmp = curr->next;
list_del(curr);
list_add(curr, tmp);
}
}
// https://leetcode.com/problems/swap-nodes-in-pairs/
}
```
### q_reverse
首先先確認 `head` 是否存在或是只有一個以下的元素，若為上述情況則直接跳出該程式。接著先定義三個指向 `list_head` 的指標變數，分別是 `prev` 指向 `head->prev` ， `curr` 指向 `head` ， `next` 指向 `head->next` 。接著是將 `curr->next` 指向 `prev` ，`curr->prev` 指向 `next` 。並一起跳至下一個元素，直到 `curr` 再次與 `head` 重疊，代表已經反轉完畢，結束並返回。
* ***以下為完整的程式碼：***
```c
void q_reverse(struct list_head *head)
{
if(!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *prev = head->prev;
struct list_head *curr = head;
struct list_head *next = head->next;
do{
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
next = next->next;
} while(curr != head);
}
```
### q_sort
以下將分成 `q_sort` 原函式， `merge_sort` 真正的實做部份以及 `find_mid` 回傳該佇列的中間點。
* ***以下為完整的程式碼：***
#### q_sort
先判斷傳入的 `head` 是否存在，若不存在則跳出函式。反之則將 `head` 拿出該佇列。並將剩下的佇列傳入 `merge_sort` 。
```c
void q_sort(struct list_head *head)
{
if (head == NULL)
return;
struct list_head *new_head = head->next;
list_del(head);
new_head = merge_sort(new_head);
list_add_tail(head, new_head);
}
```
#### merge_sort
先確認是否只剩下一個節點，若為真則直接回傳自己。接著利用 `find_mid` 找出中間的節點，並將兩個佇列分離並各自形成一個環狀雙向佇列，並遞迴呼叫 `merge_sort` ，直到 `left` 與 `right` 都各自只剩下一個節點而已。接著開始進行接合，先將本身的 `prev` 的 `next` 指向 `NULL` ，並定義一個 `tmp` 指向 `NULL` ，接著若 `left` 以及 `right` 至少存在一個(代表可以進入迴圈)，則開始進行比較。若只有 `left` 存在或是 `left` 的字串比 `right` 的字串小，則將 `left` 的元素置入新的佇列中。若 `tmp == NULL` ，則代表佇列尚未建立，須將 `new_head` 指向這新的原點。反之則直接加入即可。最後若 `right` 以及 `left` 皆指向 `NULL` ，則代表已經接合完畢，回傳 `new_head` 即可。
```c
struct list_head *merge_sort(struct list_head *new_head)
{
if (new_head == new_head->next)
return new_head;
struct list_head *left = new_head;
struct list_head *right = find_mid(new_head);
if (list_is_singular(left)) {
list_del_init(left);
list_del_init(right);
} else {
right->prev->next = left;
left->prev->next = right;
struct list_head *tp = left->prev;
left->prev = right->prev;
right->prev = tp;
}
left = merge_sort(left);
right = merge_sort(right);
left->prev->next = NULL;
right->prev->next = NULL;
for (struct list_head *tmp = NULL; left || right;) {
if (!right ||
(left &&
((strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value)) < 0))) {
if (!tmp) {
tmp = new_head = left;
left = left->next;
if (left != NULL) {
left->prev = tmp->prev;
}
INIT_LIST_HEAD(tmp);
} else {
tmp = left;
left = left->next;
if (left != NULL) {
left->prev = tmp->prev;
}
list_add_tail(tmp, new_head);
}
} else {
if (!tmp) {
tmp = new_head = right;
right = right->next;
if (right != NULL) {
right->prev = tmp->prev;
}
INIT_LIST_HEAD(tmp);
} else {
tmp = right;
right = right->next;
if (right != NULL) {
right->prev = tmp->prev;
}
list_add_tail(tmp, new_head);
}
}
}
return new_head;
}
```
#### find_mid
先利用指標指向 `head` 與 `head->next`，接著各自向前與向後一步，直到兩者重疊或是相鄰，再回傳該指標即可。
```c
struct list_head *find_mid(struct list_head *head)
{
struct list_head *forw = head, *back = head->prev;
while (forw != back && forw->next != back) {
forw = forw->next;
back = back->prev;
}
return back;
}
```
### 終於完成了～
## qtest實做新命令：shuffle
先打開 `qtest.c` 並依照 [lab-0](https://hackmd.io/@sysprog/linux2022-lab0) 實做 `do_hello` 後，可以成功出現 Hello World 的訊息。
### trace code
先打開 `qtest.c` 檔後，進入 `main()` 主程式找到 `run_console(infile_name)` 後，會發現 `run_console()` 這函式是位於 `console.c` 的檔案中。打開 `console.c` 後，找到 `run_console` 的函式，發現它傳入的引數為 `infile_name` ，我認為應該是傳入的檔案名稱。進入 `run_console` 後，會檢查是否有 `has_infile` ，若有則會進入 `else` 的區域，且會持續執行 `cmd_select()` 直到 `cmd_done()` 為止。
**以下為 `run_console` 的程式碼：**
```c
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
接著也可以在 `console.c` 找到 `cmd_select()` ，在該函式中找到 `/* Commandline input available */` 的註解。下面還有 `if(has_infile)` ，進入之後還有 `cmdline = reeadline()` 和 `interpret_cmd(cmdline)` ，我認為這應該是確認是否有輸入指令，若指令存在則開始進行翻譯的動作。
**以下為 `cmd_select()` 部份的程式碼：**
```c
if (readfds && FD_ISSET(infd, readfds)) {
/* Commandline input available */
FD_CLR(infd, readfds);
result--;
if (has_infile) {
char *cmdline;
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
}
}
```
找到 `interpret_cmd()` 後，可以看到其中有 `parse_args(cmdline, &argc);` 與 `bool ok = interpret_cmda(argc, argv);`，我認為這兩個函式應該是先解析出共有幾個指令並且傳送出指向指令的位址。
**以下為 `interpret_cmd()` 的程式瑪：**
```c
static bool interpret_cmd(char *cmdline)
{
if (quit_flag)
return false;
#if RPT >= 6
report(6, "Interpreting command '%s'\n", cmdline);
#endif
int argc;
char **argv = parse_args(cmdline, &argc);
bool ok = interpret_cmda(argc, argv);
for (int i = 0; i < argc; i++)
free_string(argv[i]);
free_array(argv, argc, sizeof(char *));
return ok;
}
```
接著找到 `interpret_cmda()` 的函式，其中會有 `cmd_ptr` 指向所有的指令，經過 `while` 迴圈一直尋找相同指令後，最後再進入該 `next_cmd` 的 `operation` 。執行相對應的指令動作，若沒有找到該指令則會印出 `report(1, "Unknown command '%s'", argv[0]);` ，印出剛剛輸入的指令名稱。
**以下為 `interpret_cmda()` 的程式碼：**
```c
static bool interpret_cmda(int argc, char *argv[])
{
if (argc == 0)
return true;
/* Try to find matching command */
cmd_ptr next_cmd = cmd_list;
bool ok = true;
while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
next_cmd = next_cmd->next;
if (next_cmd) {
ok = next_cmd->operation(argc, argv);
if (!ok)
record_error();
} else {
report(1, "Unknown command '%s'", argv[0]);
record_error();
ok = false;
}
return ok;
}
```
當輸入不存在的指令時（輸入 wrong 為指令）：
在大致了解程式運作流程後，為了增加 `shuffle` 的指令，我們必須先在 `console_init()` 中加入該程式碼:
```c
add_cmd("shuffle", do_shuffle, " | Shuffle every node on the list");
```
這樣在輸入 `shuffle` 該指令時便系統會自動去尋找 `do_shuffle()` 的函式，因此我們還需要在 `qtest.c` 中加入 `do_shuffle()` 的函式。
**以下為 `do_shuffle()` 的完整程式碼：**
```c
static 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: Try to access null queue");
return false;
}
error_check();
bool ok = false;
set_noallocate_mode(true);
if (exception_setup(true)) {
ok = q_shuffle(l_meta.l);
}
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return ok && !error_check();
}
```
程式碼中的前兩個判斷式是我複製檔案中其他函式的。第一個是確定傳入的引述個數只有一個，第二個是確認該佇列不是指向 `NULL` 。接著開始進行 `q_shuffle()` 的函式， `shuffle()` 完成後再使用 `show_queue()` 依序展現每個節點。
**以下為 `q_shuffle()` 的完整程式碼：**
```c
bool q_shuffle(struct list_head *head)
{
if (head == NULL)
return false;
if (list_empty(head))
return true;
if (list_is_singular(head))
return true;
int n = q_size(head);
struct list_head *sorted = head->prev;
struct list_head *to_swap = sorted;
struct list_head *tmp = NULL;
srand(time(NULL));
for (; n > 1; n--) {
int to_sort = rand() % (n - 1) + 1;
for (int i = 0; i < to_sort; i++) {
to_swap = to_swap->prev;
}
tmp = sorted->next;
list_del(sorted);
list_add_tail(sorted, to_swap);
list_del(to_swap);
list_add_tail(to_swap, tmp);
to_swap = to_swap->prev;
sorted = to_swap;
to_swap = to_swap->prev;
to_swap = sorted;
}
return true;
}
```
先確認傳入的佇列不是空節點或是只有一個以下的節點，接著找出佇列的節點數量。並依照 [Fisher-Yates Shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 的方法先使用一個指標分開已經洗完牌與尚未洗牌的節點。接著隨機尋找要交換的節點，再使用 Linux 的內建的 API 實現交換的過程，最後回傳 `true` 。
### 測試結果
成功！！
## 利用 Valgrind 檢查記憶體
在終端機輸入 `make valgrind` 後，系統跳出了非常多的錯誤，且幾乎都是 `still reachable` 的情況。
先試著 `valgrind ./qtest` ，並沒有發現任何錯誤。
接著試著測試每個測試檔是否有記憶體的問題：
### trace1
輸入 `valgrind ./qtest -f ./traces/trace-01-ops.cmd` 後，會出現三個問題，皆為 `still reachable` 的情況，且皆來自 `linenoiseHistoryAdd` 的函式。
:::spoiler 以下為 `linenoiseHistoryAdd` 的原始程式碼：
```c=1215
int linenoiseHistoryAdd(const char *line)
{
char *linecopy;
if (history_max_len == 0)
return 0;
/* Initialization on first call. */
if (history == NULL) {
history = malloc(sizeof(char *) * history_max_len);
if (history == NULL)
return 0;
memset(history, 0, (sizeof(char *) * history_max_len));
}
/* Don't add duplicated lines. */
if (history_len && !strcmp(history[history_len - 1], line))
return 0;
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older line. */
linecopy = strdup(line);
if (!linecopy)
return 0;
if (history_len == history_max_len) {
free(history[0]);
memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
history_len--;
}
history[history_len] = linecopy;
history_len++;
return 1;
}
```
可以看到在 1224 行的 `strdup` 與 1236 行的 `malloc` 皆有 `still reachable` 的情況。我想應該是因為在配置繼體後使用完畢沒有釋放造成的，因此我在程式 `history_len++` 後方加上釋放記憶體的動作。
:::
更改後的程式碼：
```c=1245
history_len++;
free(linecopy);
for(int i = 0; i < history_len; i++){
free(*history + i);
}
free(history);
return 1;
```
執行結果：
## 引用Linux核心原始程式碼之 `lib/list_sort.c`
原始程式碼之效能：
新建一個 `trace-time.cmd` 檔，隨機插入 300000 個元素，以測試 `sort` 的效能。
```python
option fail 0
option malloc 0
new
ih RAND 300000
time
sort
time
```
以自己撰寫的 `q_sort.c` 實測排序的效能，在終端機輸入 `make check` 可以得出排序的時間約為 0.263 秒。
Sign in with Wallet
Connect another wallet