2020q1 Homework1 (lab0)
====
###### tags: `Linux`, `system programming`
contributed by < `Randy870819` >
> [作業要求](https://hackmd.io/@sysprog/linux2020-lab0#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
## Makefile 分析
快要完成作業實作與實驗後才發現有了 `Makefile` 才讓整個專案開發如此順暢，且為了做專案的修改實驗也需要修改 `Makefile` ，因此將 `Makefile` 的分析提前放到此處，也感謝同學 [KYG-yaya573142](https://hackmd.io/@KYWeng/S1DPSVSQ8#%E5%88%86%E6%9E%90-Makefile) 的共筆。
Makefile 語法在老師提供的 [**Makefile 語法和示範**](https://hackmd.io/@sysprog/SySTMXPvl) 已有詳盡的介紹， [lab0/Makefile](https://github.com/KYG-yaya573142/lab0-c/blob/master/Makefile) 。
- 一開始先對常用或是冗長的 **變數(巨集)** 做定義。
```shell
CC = gcc
CFLAGS = -O1 -g -Wall -Werror -Idudect -I.
GIT_HOOKS := .git/hooks/applied
DUT_DIR := dudect
```
- 第一次執行 `make` 會先行安裝 Git Hooks:
執行 `make` 後，`make` 會在 makefile 中找尋第一個目標 (target) ，亦即將 `all` 預設為最終建制目標，因此除了編譯 `qtest` 外，還會安裝 Git Hooks 。
```
all: $(GIT_HOOKS) qtest
$(GIT_HOOKS):
@scripts/install-git-hooks
@echo
```
- 參數設定： VERBOSE and SANITIZER
- 當執行 `make` 並附加 `VERBOSE=1` 會讓顯示詳細編譯的過程:
- Q: `@` 加在指令前，會讓指令不顯示，因此利用 `Macro` 附加在之後會執行的指令前，便能輕易控制是否顯示。
- VECHO: `@true` 能追加該行指令直接被視為成功的作用， `@printf` 則可以印出相對應字串。
- 當執行 `make` 並附加 `SANITIZER=1` 則會對編譯參數做修改。
```shell
# Control the build verbosity
ifeq ("$(VERBOSE)","1")
Q :=
VECHO = @true
else
Q := @
VECHO = @printf
endif
# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
# https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
LDFLAGS += -fsanitize=address
endif
```
- Objects and Dependencies: 這邊使用了 [Auto-Dependency Generation](http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/) 來解決 dependency 的問題。
- Line 3: `deps := $(OBJS:%.o=.%.o.d)` 使用萬用字元 `%` 配上之前建立的變數，為所有 objective file 設立好它 dependency file 的檔名，以備之後 include 。
- Line 8: 接下來就是在為每個 .c 檔編譯建立 object file 的同時也建立 dependency file ，當然這些 dependency file 要與先前變數 `deps` 設定一樣，接下來才能順利使用。 ( 註：建立 dependency file 是編譯器中 pre-processor 的工作 )
- Line 10: 最後也最重要的一步，就是 include 所有 dependency file 。
當一個目標 (target) 比其自己的相依項目 (dependency) 更新時間還要早時，代表其相依項目已被修改，要重新建立目標，但一個專案往往會有眾多 dependency file ，而合以上流程，就是代替我們完成建立相依性的複雜工作！
```shell
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o
deps := $(OBJS:%.o=.%.o.d)
%.o: %.c
@mkdir -p .$(DUT_DIR)
$(VECHO) " CC\t$@\n"
$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
-include $(deps)
```
- Valgrind 支援
- `valgrind_existence`: 檢查作業系統有無安裝 Valgrind 。
- 一開始不懂 which 是什麼沒關係，打開 Terminal 輸入 `man which`
```shell
$ man which
NAME: which - locate a command
DESCRIPTION: which returns the pathnames of the files (or links) which would be executed in the current environment
```
`which` 指令讓使用者得知某一 command 執行的路徑。
- `2>&1` 則是代表將 `stderr` 導入 `stdout` 。 (From: [Stack Overflow](https://stackoverflow.com/questions/818255/in-the-shell-what-does-21-mean))
- `/dev/null` 是 **NULL Device** ，會回報丟入資料是否成功，使用以下輸入如果電腦中已有安裝 Valgrind 則會得到 `yes` 輸出喔。
```shell
$ if which valgrind 2>&1 > /dev/null
> then echo yes
> else echo no
> fi
yes
```
- `||` 代表若左邊執行出錯，就執行右邊的內容。
- 因此最後整行的指令也顯而易見了吧！！
- valgrind
- `$(MAKE)` 為 Recursive make commands ，所以要小心不要再次執行 `make` 建立同樣的目標，會造成無限迴圈。 [Manual](https://www.gnu.org/software/make/manual/html_node/MAKE-Variable.html)
- `$(eval expression)` 則是會將右邊 expression 展開並當作 Makefile 指令執行。 [Manual](https://www.gnu.org/software/make/manual/html_node/Eval-Function.html)
- `sed -i "s/alarm/isnan/g" $(patched_file)`: 其中 `"s/alarm/isnan/g"` 並非路徑，而是 `sed` ([stream editor](http://manpages.ubuntu.com/manpages/precise/en/man1/plan9-sed.1.html)) 替換字串的[語法](https://www.gnu.org/software/sed/manual/html_node/The-_0022s_0022-Command.html)，在此是將 $(patched_file) 中的所有的 "alarm" 替換為 "iasnan" 。
發現同學 [frankchang0125](https://hackmd.io/@frankchang0125/lab0#%E4%BD%BF%E7%94%A8-Valgrind-%E6%8E%92%E9%99%A4-qtest-%E5%AF%A6%E4%BD%9C%E7%9A%84%E8%A8%98%E6%86%B6%E9%AB%94%E9%8C%AF%E8%AA%A4) 解釋的更為清楚。
```shell
valgrind_existence:
@which valgrind 2>&1 > /dev/null || (echo "FATAL: valgrind not found"; exit 1)
valgrind: valgrind_existence
# Explicitly disable sanitizer(s)
$(MAKE) clean SANITIZER=0 qtest
$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
cp qtest $(patched_file)
chmod u+x $(patched_file)
sed -i "s/alarm/isnan/g" $(patched_file)
scripts/driver.py -p $(patched_file) --valgrind
@echo
@echo "Test with specific case by running command:"
@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"
```
## 開發紀錄
### `queue.h`：queue structure
為了讓 `q_insert_tail()` 跟 `q_size()` 執行時達到 $O(1)$ 的時間複雜度，增加了變數 `size` 與 `tail` 指標便於存取。
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head, *tail; /* Linked list of elements */
int size; /* Memorizing the size of queue */
} queue_t;
```
### `q_new`
建立一個新的 `queue_t` 結構，並對其初始化，若 `malloc()` 回傳 NULL ，代表配置記憶體失敗，回傳 NULL 。
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = q->tail = NULL;
q->size = 0;
return q;
}
```
### `q_free`
一開使先對沒有 queue 的特定情況做處理；在 queue 被建立的情況下，走訪整個 linked list 利用 `pre` 指標指向前一個 list element 在對其指到的記憶體做 deallocation ，最後再清除 queue 結構。
```cpp
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *tmp = q->head, *pre = NULL;
while (tmp) {
pre = tmp;
tmp = tmp->next;
if (pre->value)
free(pre->value);
free(pre);
}
free(q);
}
```
:::warning
考慮以下變更:
```diff
@@ -2,12 +2,11 @@
{
if (!q)
return;
- list_ele_t *tmp = q->head, *pre = NULL;
- while (tmp) {
- pre = tmp;
- tmp = tmp->next;
- if (pre->value)
- free(pre->value);
+
+ list_ele_t *front = NULL;
+ for (list_ele_t *tmp = q->head; tmp; tmp = front) {
+ front = tmp->next;
+ free(pre->value);
free(pre);
}
free(q);
```
要點:
1. 縮減 `list_ele_t *pre` 的 scope;
2. 將 `while` 改寫為 `for` 迴圈，更好閱讀且程式碼縮減;
3. 注意 [free](https://linux.die.net/man/3/free) 的使用，當輸入參數為 `NULL` 時，該函式無作用，於是就可利用此特性減少一個 `if` 敘述;
:notes: jserv
:::
### `q_insert_head`
一開使先對沒有 queue 的特定情況做處理，再依序新增 `list_ele_t` 與字串，要注意的是如果其中某一環節出錯，必須將在這函式中新增的記憶體位置都釋放掉。
接下來使用 `strncpy()` 將輸入字串複製到新增的字串中，要注意的是 `strncpy()` 只會複製指定長度 $n$ 個字元，必須自行注意字串結尾有沒有 `null character ('\0')` ：
> The `strncpy()` function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated. [Linux man page](https://linux.die.net/man/3/strncpy)
最後插入到頭端後要特別注意 linked list 長度由 0 變 1 的情況，此時頭與尾端是指向同一個 list node 。
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *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;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s));
*(newh->value + strlen(s)) = '\0';
newh->next = q->head;
q->head = newh;
// Insert to empty queue, we have to update both head and tail pointer.
if (++(q->size) == 1) {
q->tail = newh;
}
return true;
}
```
### `q_insert_tail`
此實做跟 `q_insert_head()` 幾乎一致，最後插入到尾端後也要特別注意 linked list 長度由 0 變 1 的情況，此時頭與尾端是指向同一個 list node 。
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *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;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s));
*(newh->value + strlen(s)) = '\0';
newh->next = NULL;
if (q->tail)
q->tail->next = newh;
q->tail = newh;
// Insert to empty queue, we have to update both head and tail pointer.
if (++(q->size) == 1) {
q->head = newh;
}
return true;
}
```
### `q_remove_head`
再處理完沒有 queue 或是 queue 為空的情況後，便能使用 `strncpy()` 複製，並在字串尾端加上 `null character ('\0')` 。
接下來移除頭端 list node 要注意必須確實將配置在該 list node 上的記憶體清除，亦即清除完字串後，再將 list node 清除；最後在更新 list size 時也要注意當 linked list 長度由 1 變 0 ，我們要將 queue 中頭端與尾端的指標更新為 `NULL` ，避免之後又存取已清除的記憶體造成 Segmentation fault 。
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
if (sp && bufsize > 0 && q->head->value) {
strncpy(sp, q->head->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_ele_t *tmp = q->head;
q->head = q->head->next;
if (tmp->value) {
free(tmp->value);
}
free(tmp);
// Remove element from queue with size 1,
// we have to update both head and tail pointer.
if (--(q->size) == 0) {
q->head = q->tail = NULL;
}
return true;
}
```
### `q_size`
檢查完 queue 尚未被建立的情況後，便直接回傳 size 。
```cpp
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
:::warning
可改寫為以下:
```cpp
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
簡潔又清晰！
:notes: jserv
:::
### `q_reverse`
一開使先對沒有 queue 或是 linked list 內只有一筆資料的特定情況做處理。
再利用以下3個指標持續走訪 linked list 並反轉其連結方向：
1. pointer pre: 指向前一個 list node ，對於 linked list 的頭 ( 第一個 element ) 來說，並沒有前一個 list node ，因此初始為 NULL 。
2. pointer cur: 指向現在正要反轉連結方向的 list node 。
3. pointer nex: 指向原本 linked list 的下一個 list node ，避免遺失下一個要處理 list node 的位址。
利用以上 3 個指標，在走訪 linked list 依序平移並將 linked list 反轉。
```cpp
void q_reverse(queue_t *q)
{
if (!q || q->size <= 1)
return;
list_ele_t *pre = NULL, *cur = q->head, *nex = q->head->next;
while (nex) {
cur->next = pre;
pre = cur;
cur = nex;
nex = cur->next;
}
cur->next = pre;
cur = q->head;
q->head = q->tail;
q->tail = cur;
}
```
:::warning
TODO: 用 `for` 改寫並縮減 scope
:notes: jserv
:::
### `q_sort`
- `q_sort`: Top level interface.
參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 其中的 Merge sort 。
令 `q_sort()` 為排序的 Top level interface ，除了檢查沒有 queue 或是長度為 1 不需要排序的情況，便進到 Merge sort 排序，但排序後會失去 linked list 尾端的資訊，因此需要重新走訪 linked list 找回尾端指標。
```cpp
void q_sort(queue_t *q)
{
if (!q || q->size <= 1)
return;
q->tail = q->head = merge_sort(q->head);
// After merge sort, the pointer q->tail would no longer point
// to the tail of queue anymore.
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
- `merge_sort`: Recursive merge sort (Divide and Conquer).
利用龜兔賽跑的概念，一個指標一次前進一格，另一個指標則是一次前進兩格，便能順利的找到 linked list 的中點，但找到中點後要注意的是必須將 linked list 一分為二，才能接下去遞迴呼叫，分別排序好左右 partition 的 linked list ，再進到合併並回傳頭端指標。
```cpp
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// Find the cutting point.
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// Redirect the pointer to the right partition and split the linked list.
fast = slow->next;
slow->next = NULL;
// Recursive call to sort the sub-lists.
head = merge_sort(head);
fast = merge_sort(fast);
return merge(head, fast);
}
```
- `merge`: Merge 2 linked list according to natural ordering.
一開始先定義一個指向 `list_ele_t` 的指標 `head` 指向 NULL ， 再另外使用一個 double pointer (pointer to pointer) `cursor` 來記下目前合併 linked list 進行到的位置，接下來便能走訪兩個 linked list ，依據定義好的 ordering 做合併，利用 `cursor` 更新目前尾端的 list element 的指標；最後當某一個 list 已經走完，因為兩個 linked list 早已做完排序，便能直接另一個 list 附加到尾端，結束合併，再回傳合併後的頭端指標。
```cpp
list_ele_t *merge(list_ele_t *p1, list_ele_t *p2)
{
list_ele_t *head = NULL;
list_ele_t **cursor = &head;
// Merge 2 list according to their Lexicographical order.
while (p1 && p2) {
if (str_cmp(p1->value, p2->value) >= 0) {
*cursor = p2;
p2 = p2->next;
cursor = &((*cursor)->next);
} else {
*cursor = p1;
p1 = p1->next;
cursor = &((*cursor)->next);
}
}
// Append the last remaining list to the end of merged list.
if (p1) {
*cursor = p1;
} else {
*cursor = p2;
}
return head;
}
```
- `str_cmp`:
利用兩個 pointer 去存取字元做比較，跳出迴圈則是遇到尾端，或是遇到第一個字元不同的情況，最後回傳字典序的大小，在簡化流程之後也要注意當兩個字串一樣，要考慮兩個 pointer 最後都指向 `null character ('\0')` 的情況。
```cpp
int str_cmp(const char *s1, const char *s2)
{
// Skip the same prefix of 2 given string
// After leaving while loop, either pointer s1 and s2 would point
// to the first distinct character or both of them point to '\0'.
while (*s1 != '\0' && *s2 != '\0' && *s1 == *s2) {
++s1, ++s2;
}
// Consider their Lexicographical order (also cover the case of eqivalence).
return (*s1 > *s2) * (1) + (*s1 < *s2) * (-1);
}
```
#### Old version of my `q_sort()` (2/23)
一開始看完 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的介紹其中的圖片便著手開始實現沒有遞迴呼叫的 merge sort ，使用 Bottom-up 的方式， for 迴圈第一次 iteration 為每個長度為 2 的 sub-list 完成排序，第二次 iteration 為每個長度為 4 的 sub-list 完成排序，依此類推 (即 for 迴圈中 `k*=2` )。
From: [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
但是觀察以下程式碼便會發現在排序對象是 linked list 而非一般陣列的時候，會在找尋左右要合併的 partition 中花很大的功夫，並且排序生成的樹狀圖形會如同上圖般為一棵不平衡的樹，在時間複雜度上會多一些 lower order 的項次，而且程式碼還比較複雜 (本身功力不足也有關係 QQ )。
因此最後還是好好的利用遞迴，將 merge sort 依各部功能實現。
```cpp
void q_sort(queue_t *q)
{
if (!q || q->size <= 1)
return;
for (int k = 1; k < q->size; k *= 2) {
list_ele_t **cursor = &(q->head); // storing point
list_ele_t *point = q->head; // processing point
list_ele_t *left = point, *right = point;
int t = k;
while (t && right) {
--t;
right = right->next;
}
point = right;
t = k;
while (t && point) {
--t;
point = point->next;
}
while (right) {
int left_size = k;
while (left_size && right != point) {
if (str_cmp(left->value, right->value) >= 0) {
*cursor = right;
right = right->next;
cursor = &((*cursor)->next);
} else {
*cursor = left;
left = left->next;
cursor = &((*cursor)->next);
--left_size;
}
}
while (left_size) {
*cursor = left;
q->tail = left;
left = left->next;
cursor = &((*cursor)->next);
--left_size;
}
while (right != point) {
*cursor = right;
q->tail = right;
right = right->next;
cursor = &((*cursor)->next);
}
*cursor = point;
left = right = point;
t = k;
while (t && right) {
--t;
right = right->next;
}
point = right;
t = k;
while (t && point) {
--t;
point = point->next;
}
}
}
}
```
## Natural sort
採用 [Natural Sort](https://github.com/sourcefrog/natsort) 來為字串進行排序 (連結內已有詳細敘述) 。
1. 將 strnatcmp.c 與 strnatcmp.h 加入專案。
2. 修改 Makefile ，加入 `strnatcmp.o` 進 `$(OBJS)` 以便專案建制。
```shell
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
strnatcmp.o
```
3. 接下來就可以在專案中的 `queue.c` 引用 `strnatcmp.h` 並使用其函數囉，有趣的是在 `strnatcmp.c` 中有兩種比較 Natural ordering 的函式分別為 `strnatcmp()` 與 `strnatcasecmp()` ，深入去看可以發現 `strnatcasecmp()` 其實是把字元轉換為大寫 (uppercase) 後再做比較，因此像是底線 `_` 這個常用在檔名的字元與一般英文字母比較，優先度就會低，在這邊我們就採用 `strnatcasecmp()` 。
```cpp
/*
* Merge 2 linked list into 1 linked list in ascending order.
*/
list_ele_t *merge(list_ele_t *p1, list_ele_t *p2)
{
list_ele_t *head = NULL;
list_ele_t **cursor = &head;
// Merge 2 list according to their Lexicographical order.
while (p1 && p2) {
// if (str_cmp(p1->value, p2->value) >= 0) {
if (strnatcasecmp(p1->value, p2->value) >= 0) {
*cursor = p2;
p2 = p2->next;
cursor = &((*cursor)->next);
} else {
*cursor = p1;
p1 = p1->next;
cursor = &((*cursor)->next);
}
}
// Append the last remaining list to the end of merged list.
if (p1) {
*cursor = p1;
} else {
*cursor = p2;
}
return head;
}
```
4. 接下來我們可以為 [Natural Sort](https://github.com/sourcefrog/natsort) 裡提供的測資創建新的測資檔案並在 `driver.py` 中加入相對應的檔名與分數等。
```python
traceDict = {
# ...
16: "trace-16-perf",
17: "trace-17-complexity",
# Natural sort testing data
18: "trace-18-test-dates",
19: "trace-19-test-debs",
20: "trace-20-test-debvers",
21: "trace-21-test-fractions",
22: "trace-22-test-versions",
23: "trace-23-test-words"
}
```
```python=
traceProbs = {
# ...
17: "Trace-17",
# Natural sort testing data
18: "Trace-18",
19: "Trace-19",
20: "Trace-20",
21: "Trace-21",
22: "Trace-22",
23: "Trace-23"
}
```
```python
maxScores = [0, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
5, 6, 6, 6, 6, 6, 6]
```
5. 另外要注意有測資檔後，還必須要修改 `qtest.c` 中為 sorting 結果做檢查的部份，因為一開始是使用 `strcasecmp()` 而非 `strnatcasecmp()` 。
```cpp=559
// ...
bool ok = true;
if (q) {
for (list_ele_t *e = q->head; e && --cnt; e = e->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
// if (strcasecmp(e->value, e->next->value) > 0) {
if (strnatcasecmp(e->value, e->next->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
```
6. 最後便能順利使用 Natural sort 做測試。
```shell
$ make test
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
--- trace-15-perf 0/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
+++ TESTING trace trace-18-test-dates:
--- trace-18-test-dates 6/6
+++ TESTING trace trace-19-test-debs:
--- trace-19-test-debs 6/6
+++ TESTING trace trace-20-test-debvers:
--- trace-20-test-debvers 6/6
+++ TESTING trace trace-21-test-fractions:
# Fractional release numbers
--- trace-21-test-fractions 6/6
+++ TESTING trace trace-22-test-versions:
--- trace-22-test-versions 6/6
+++ TESTING trace trace-23-test-words:
--- trace-23-test-words 6/6
--- TOTAL 130/136
```
但是目前還是有一個問題未解決，就是採用 [Natural Sort](https://github.com/sourcefrog/natsort) 後會讓測試項目編號 15 `trace-15-perf` TLE ，去除掉一般字元比較的部份，可能的原因是做完一般字元 prefix 檢查後，便須要對剩餘的數字字串 (digits) 做大小的比較，因此此處也是之後可以加強的部份。
:::warning
TODO:
研究是否能再提升 [Natural Sort](https://github.com/sourcefrog/natsort) 的效率。
:::
## Valgrind & Massif
### 使用 Valgrind 排除實作的記憶體錯誤
使用以下指令運用 Valgrind 找尋出錯的地方，到第3筆測資 trace-03-ops 時遇到：
```shell
$ make valgrind
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
==12439== Invalid read of size 8
==12439== at 0x10CDA9: q_reverse (queue.c:161)
==12439== by 0x109D92: do_reverse (qtest.c:463)
==12439== by 0x10B90B: interpret_cmda (console.c:220)
==12439== by 0x10BE83: interpret_cmd (console.c:243)
==12439== by 0x10C440: cmd_select (console.c:571)
==12439== by 0x10C66F: run_console (console.c:630)
==12439== by 0x10ADA7: main (qtest.c:770)
==12439== Address 0x8 is not stack'd, malloc'd or (recently) free'd
==12439==
ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
回追至 `q_reverse()` 發現是在反轉 linked list 最後還會去對尾端節點的指標 next 會指向 `NULL` 我卻還去存取造成 Segmentation fault 。
```cpp=152
void q_reverse(queue_t *q)
{
if (!q || q->size <= 1)
return;
list_ele_t *pre = NULL, *cur = q->head, *nex = q->head->next;
while (cur) {
cur->next = pre;
pre = cur;
cur = nex;
nex = cur->next;
}
cur = q->head;
q->head = q->tail;
q->tail = cur;
}
```
經過些微修改解決記憶體存取的問題。
```cpp=152
void q_reverse(queue_t *q)
{
if (!q || q->size <= 1)
return;
list_ele_t *pre = NULL, *cur = q->head, *nex = q->head->next;
while (nex) {
cur->next = pre;
pre = cur;
cur = nex;
nex = cur->next;
}
cur->next = pre;
cur = q->head;
q->head = q->tail;
q->tail = cur;
}
```
:::warning
TODO: 用 diff (HackMD 支援該語法標示) 來展現程式碼之間的差異
:notes: jserv
:::
### 利用 Massif 視覺化記憶體的使用
開啟 stack flag 觀察 merge sort!?
## Paper reading
## System of Select
## Reference
## Appendix of interesting information
[XOR Linked List](https://en.wikipedia.org/wiki/XOR_linked_list): 利用 exclusive or 的特性，我們可以達到用 single pointer 除存 double pointer 的效果，缺點是必須要有得知兩個相鄰的 list node 才能繼續推理 (inferencing) 之後的 list node 位址。
Sign in with Wallet
Connect another wallet