2020q1 Homework1 (lab0)

tags: `Linux`, `system programming`

contributed by < Randy870819 >

作業要求

Makefile 分析

快要完成作業實作與實驗後才發現有了 Makefile 才讓整個專案開發如此順暢，且為了做專案的修改實驗也需要修改 Makefile ，因此將 Makefile 的分析提前放到此處，也感謝同學 KYG-yaya573142 的共筆。

Makefile 語法在老師提供的 Makefile 語法和示範 已有詳盡的介紹， lab0/Makefile 。

一開始先對常用或是冗長的 變數(巨集) 做定義。

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 則會對編譯參數做修改。

# 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 來解決 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 ，而合以上流程，就是代替我們完成建立相依性的複雜工作！
```
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

$ 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)

/dev/null 是 NULL Device ，會回報丟入資料是否成功，使用以下輸入如果電腦中已有安裝 Valgrind 則會得到 yes 輸出喔。

$ if which valgrind 2>&1 > /dev/null 
> then echo yes
> else echo no
> fi
yes

|| 代表若左邊執行出錯，就執行右邊的內容。
因此最後整行的指令也顯而易見了吧！！

valgrind
- $(MAKE) 為 Recursive make commands ，所以要小心不要再次執行 make 建立同樣的目標，會造成無限迴圈。 Manual
- $(eval expression) 則是會將右邊 expression 展開並當作 Makefile 指令執行。 Manual
- sed -i "s/alarm/isnan/g" $(patched_file): 其中 "s/alarm/isnan/g" 並非路徑，而是 sed (stream editor) 替換字串的語法，在此是將 $(patched_file) 中的所有的 "alarm" 替換為 "iasnan" 。
發現同學 frankchang0125 解釋的更為清楚。

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 指標便於存取。

/* 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 。

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 結構。

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);
}

考慮以下變更:

@@ -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);

要點:

縮減 list_ele_t *pre 的 scope;
將 while 改寫為 for 迴圈，更好閱讀且程式碼縮減;
注意 free 的使用，當輸入參數為 NULL 時，該函式無作用，於是就可利用此特性減少一個 if 敘述;

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

最後插入到頭端後要特別注意 linked list 長度由 0 變 1 的情況，此時頭與尾端是指向同一個 list node 。

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 。

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 。

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 。

/*
 * 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;
}

可改寫為以下:

int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

簡潔又清晰！

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

`q_reverse`

一開使先對沒有 queue 或是 linked list 內只有一筆資料的特定情況做處理。
再利用以下3個指標持續走訪 linked list 並反轉其連結方向：

pointer pre: 指向前一個 list node ，對於 linked list 的頭 ( 第一個 element ) 來說，並沒有前一個 list node ，因此初始為 NULL 。
pointer cur: 指向現在正要反轉連結方向的 list node 。
pointer nex: 指向原本 linked list 的下一個 list node ，避免遺失下一個要處理 list node 的位址。

利用以上 3 個指標，在走訪 linked list 依序平移並將 linked list 反轉。

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;
}

TODO: 用 for 改寫並縮減 scope

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

`q_sort`

q_sort: Top level interface.
參考 Linked List Sort 其中的 Merge sort 。
令 q_sort() 為排序的 Top level interface ，除了檢查沒有 queue 或是長度為 1 不需要排序的情況，便進到 Merge sort 排序，但排序後會失去 linked list 尾端的資訊，因此需要重新走訪 linked list 找回尾端指標。

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 ，再進到合併並回傳頭端指標。

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 附加到尾端，結束合併，再回傳合併後的頭端指標。

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') 的情況。

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 的介紹其中的圖片便著手開始實現沒有遞迴呼叫的 merge sort ，使用 Bottom-up 的方式， for 迴圈第一次 iteration 為每個長度為 2 的 sub-list 完成排序，第二次 iteration 為每個長度為 4 的 sub-list 完成排序，依此類推 (即 for 迴圈中 k*=2 )。

From: Linked List Sort

但是觀察以下程式碼便會發現在排序對象是 linked list 而非一般陣列的時候，會在找尋左右要合併的 partition 中花很大的功夫，並且排序生成的樹狀圖形會如同上圖般為一棵不平衡的樹，在時間複雜度上會多一些 lower order 的項次，而且程式碼還比較複雜 (本身功力不足也有關係 QQ )。

因此最後還是好好的利用遞迴，將 merge sort 依各部功能實現。

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 來為字串進行排序 (連結內已有詳細敘述) 。

將 strnatcmp.c 與 strnatcmp.h 加入專案。

修改 Makefile ，加入 strnatcmp.o 進 $(OBJS) 以便專案建制。

OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        strnatcmp.o

接下來就可以在專案中的 queue.c 引用 strnatcmp.h 並使用其函數囉，有趣的是在 strnatcmp.c 中有兩種比較 Natural ordering 的函式分別為 strnatcmp() 與 strnatcasecmp() ，深入去看可以發現 strnatcasecmp() 其實是把字元轉換為大寫 (uppercase) 後再做比較，因此像是底線 _ 這個常用在檔名的字元與一般英文字母比較，優先度就會低，在這邊我們就採用 strnatcasecmp() 。

/*
 * 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;
}

接下來我們可以為 Natural Sort 裡提供的測資創建新的測資檔案並在 driver.py 中加入相對應的檔名與分數等。

    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"
    }











    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"
}

    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]

另外要注意有測資檔後，還必須要修改 qtest.c 中為 sorting 結果做檢查的部份，因為一開始是使用 strcasecmp() 而非 strnatcasecmp() 。














// ...
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;
        }
    }
}

最後便能順利使用 Natural sort 做測試。

$ 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 後會讓測試項目編號 15 trace-15-perf TLE ，去除掉一般字元比較的部份，可能的原因是做完一般字元 prefix 檢查後，便須要對剩餘的數字字串 (digits) 做大小的比較，因此此處也是之後可以加強的部份。

TODO:
研究是否能再提升 Natural Sort 的效率。

Valgrind & Massif

使用 Valgrind 排除實作的記憶體錯誤

使用以下指令運用 Valgrind 找尋出錯的地方，到第3筆測資 trace-03-ops 時遇到：

$ 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 。















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;
}

經過些微修改解決記憶體存取的問題。
















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;
}

TODO: 用 diff (HackMD 支援該語法標示) 來展現程式碼之間的差異

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

利用 Massif 視覺化記憶體的使用

開啟 stack flag 觀察 merge sort!?

Paper reading

System of Select

Reference

Appendix of interesting information

XOR Linked List: 利用 exclusive or 的特性，我們可以達到用 single pointer 除存 double pointer 的效果，缺點是必須要有得知兩個相鄰的 list node 才能繼續推理 (inferencing) 之後的 list node 位址。

2020q1 Homework1 (lab0)

tags: Linux, system programming

Makefile 分析

開發紀錄

queue.h：queue structure

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_size

q_reverse

q_sort

Old version of my q_sort() (2/23)

Natural sort

Valgrind & Massif

使用 Valgrind 排除實作的記憶體錯誤

利用 Massif 視覺化記憶體的使用

Paper reading

System of Select

Reference

Appendix of interesting information

tags: `Linux`, `system programming`

`queue.h`：queue structure

`q_new`

`q_free`

`q_insert_head`

`q_insert_tail`

`q_remove_head`

`q_size`

`q_reverse`

`q_sort`

Old version of my `q_sort()` (2/23)