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

要點:

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

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

簡潔又清晰！

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 反轉。

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

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

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

2. 修改 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
   

3. 接下來就可以在專案中的 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;
   ​​​​}
   

4. 接下來我們可以為 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]
   

5. 另外要注意有測資檔後，還必須要修改 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;
   ​​​​        }
   ​​​​    }
   ​​​​}
   

6. 最後便能順利使用 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 支援該語法標示) 來展現程式碼之間的差異

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 位址。