---
tags: linux2020
---
# 2020q1 Homework1 (lab0)
contributed by < `bananemo` >

## 作業說明

* [作業要求](https://hackmd.io/@sysprog/linux2020-lab0)
* [作業區](https://hackmd.io/@sysprog/linux2020-homework1)

## 實做

### q_new()
* 特別注意如果 malloc 失敗要回傳 NULL, 後面的 function 每個有使用 malloc 的都要記得處理
* 以前寫程式都沒有這樣做，不太安全

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));

    if (!q) {
        return NULL;
    }

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

### q_free()
* 記得要 free 掉分配的記憶體空間

void q_free(queue_t *q)
{
    if (!q)
        return;
    if (q->size > 0) {
        list_ele_t *curr = q->head;
        list_ele_t *prev = NULL;
        while (curr) {
            prev = curr;
            curr = curr->next;
            free(prev->value);
            free(prev);
        }
    }
    free(q);
}

### q_insert_head()
* 要特別處理 queue 是 empty ，第一次新增 node 的情況

bool q_insert_head(queue_t *q, char *s)
{
    if (!q) {
        return false;
    }

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }

    newh->value = malloc((strlen(s) + 1) * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }
    memset(newh->value, '\0', strlen(s) + 1);
    strncpy(newh->value, s, strlen(s));

    if (!q->head) {
        q->tail = newh;
    }
    newh->next = q->head;
    q->head = newh;

    q->size++;

    return true;
}

### q_insert_tail
* 和 q_insert_head 類似
* 因為要達到 $O(1)$ 的時間複雜度，不能使用從 head iterate 到最後一個 node 的方式新增，因此在 queue_t 內新增了 tail 的變數來紀錄最末端的 node
* 遇到的問題
* 宣告出 newt 之後沒有把 newt->next 初始化為 NULL(下面21行)，所以一直 segmetation fault
* 對 valgrind 還不太熟悉，同一種錯誤信息 `8 bytes in 1 blocks are still reachable in loss record` 出現很給多個，不確定要以哪個為基準，有的說是在 qtest 等其他檔案，沒有寫道是 queue.c 裡面的，有的說是測試過沒有問題的 function 內，花了好久才找出來。

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q) {
        return false;
    }

    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (!newt) {
        return false;
    }

    newt->value = malloc((strlen(s) + 1) * sizeof(char));
    if (!newt->value) {
        free(newt);
        return false;
    }
    memset(newt->value, '\0', strlen(s) + 1);
    strncpy(newt->value, s, strlen(s));

    newt->next = NULL;
    if (!q->head) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
    q->tail = newt;

    q->size++;

    return true;
}

* valgrind 部分錯誤訊息

    ==2335== 8 bytes in 1 blocks are still reachable in loss record 1 of 34
    ==2335==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==2335==    by 0x10CC19: q_insert_head (queue.c:63)
    ==2335==    by 0x10A829: do_insert_head (qtest.c:212)
    ==2335==    by 0x10B992: interpret_cmda (console.c:220)
    ==2335==    by 0x10BF06: interpret_cmd (console.c:243)
    ==2335==    by 0x10C4D4: cmd_select (console.c:569)
    ==2335==    by 0x10C71C: run_console (console.c:628)
    ==2335==    by 0x10AE41: main (qtest.c:772)

### q_remove_head()
* 需特別處理只有一個 node 的情況，把 queue 的 head, tail 等設為 NULL。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head) {
        return false;
    }

    if (sp != NULL) {
        memset(sp, '\0', bufsize);
        strncpy(sp, q->head->value, bufsize - 1);
    }

    if (!q->head->next) {
        free(q->head->value);
        free(q->head);

        q->head = NULL;
        q->tail = NULL;
        q->size--;
        return true;
    }

    list_ele_t *tmp;
    tmp = q->head;
    q->head = q->head->next;
    q->size--;

    free(tmp->value);
    free(tmp);

    return true;
}

#### Warning

* Warining in q_remove_head()
* 嘗試了一陣子之後，發現把 `!sp` 改成 `sp != NULL` 就好了

    queue.c:127:17: warning: Either the condition '!sp' is redundant or there is possible null pointer dereference: sp. [nullPointerRedundantCheck]
            strncpy(sp, q->head->value, bufsize - 1);
                    ^
    queue.c:125:9: note: Assuming that condition '!sp' is not redundant
        if (!sp) {
            ^
    queue.c:127:17: note: Null pointer dereference
            strncpy(sp, q->head->value, bufsize - 1);
                    ^
    queue.c:127:17: error: Null pointer dereference [nullPointer]
            strncpy(sp, q->head->value, bufsize - 1);
                    ^

    Fail to pass static analysis.

* Before: ==!sp==

        if (!sp) {
            memset(sp, '\0', bufsize);
            strncpy(sp, q->head->value, bufsize - 1);
        }

* Fixed: ==sp != NULL==
* 嘗試了一陣子之後，發現把判斷是否為 NULL 的條件式從 `!sp` 改成 `sp != NULL` 就沒有 warning 了
* 但還沒有很確定為什麼其他地方都可以這樣用

        if (sp != NULL) {
            memset(sp, '\0', bufsize);
            strncpy(sp, q->head->value, bufsize - 1);
        }

### q_size()
* 為了達到 $O(1)$ 的時間複雜度，因此在`queue_t` 加一個變數 `size` 來記錄 linked list 的長度，並在每次 insert, remove node 時更新。

int q_size(queue_t *q)
{
    if (!q) {
        return 0;
    }

    return q->size;
}

### q_reverse()
* 慢慢從原本的 head 到 tail iterate, 並紀錄前一個 node(prev)，做為現在 iterate 到的 node(curr) 的 next(curr->next)，來完成 reverse

void q_reverse(queue_t *q)
{
    if (!q || !q->head) {
        return;
    }

    list_ele_t *curr = q->head;
    list_ele_t *prev = NULL;
    list_ele_t *next;

    while (curr != NULL) {
        // Reverse curr->next
        next = curr->next;
        curr->next = prev;

        // Shift one node
        prev = curr;
        curr = next;
    }

    list_ele_t *tmp = q->tail;
    q->tail = q->head;
    q->head = tmp;
}

### q_sort()
* 使用 merge sort 演算法，並分成 q_sort(),merge_sort(), merge() 等三個 function

#### q_sort

void q_sort(queue_t *q)
{
    if (!q || q->size == 0 || q->size == 1) {
        return;
    }

    q->head = merge_sort(q->head);

    // Update list tail
    list_ele_t *tmp = q->head;
    while (tmp->next != NULL) {
        tmp = tmp->next;
    }
    q->tail = tmp;
}

#### merge_sort
* 將 linked list 分成兩段的方法
* 利用 `fast` 和 `slow` 這兩個 pointer，來 iterate linked list。而 `fast` 每次前進兩個 node, `slow` 只前進一次，如此一來當 `fast` iterate 完的時候，slow 落在 linked list 的中間。
* 要記得把 slow->next 設為 NULL，左半邊那段 list 知道他切到哪裡(21行)

list_ele_t *merge_sort(list_ele_t *head)
{
    if (!head || !head->next) {
        return head;
    }

    /*
     * Divide nodes of linked list into two halves by slow-fast pointer.
     * Forward 'fast' by two nodes, and forward 'slow' by one node.
     */
    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }

    list_ele_t *left = head;
    list_ele_t *right = slow->next;
    slow->next = NULL;  // To let 'right' know where to end

    left = merge_sort(left);
    right = merge_sort(right);

    return merge(left, right);
}

#### merge
* 如果左右有任一是空的話，直接回傳另一邊的 list
* 否則就 iterate 一一去比較兩邊的 node 的 value 大小，一個個把比較小的放到 result list 內。
* 因為一開始 result_head 是空的，所以記得要先初始化(13行)
* 最後如果有任一一邊還有剩下的，整段接到 result list 上面。

list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
    if (!left) {
        return right;
    }
    if (!right) {
        return left;
    }

    list_ele_t *result_head;
    list_ele_t *curr;

    // Initialize result_head and curr
    if (strnatcmp(left->value, right->value) < 0) {
        result_head = curr = left;
        left = left->next;
    } else {
        result_head = curr = right;
        right = right->next;
    }

    while (left != NULL && right != NULL) {
        if (strnatcmp(left->value, right->value) < 0) {
            curr->next = left;
            curr = curr->next;
            left = left->next;
        } else {
            curr->next = right;
            curr = curr->next;
            right = right->next;
        }
    }

    // If there is still node left in 'left list'
    if (left) {
        curr->next = left;
    }

    // If there is still node left in 'right list'
    if (right) {
        curr->next = right;
    }

    return result_head;
}

### natural sort

* 把 `strnatcmp.h`, `strnatcmp.c` 下載下來並放到專案內
* 更改 queue.c
* 加上 `#include strnatcmp.h, strnatcmp.c `
* 把 strcmp() 改成 strnatcmp()
* 更改 make file
* 在 `OBJS` 加上 `strnatcmp.o`

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

#### 在 commit 自動檢查時，有一些 warning，大概分為兩個
* The scope of the variable can be reduced
* 本來 ca, cb 在 while 外面宣告，但只有在 while loop 內才會用到，故可以在 while 的 scope 宣告就好
* The function is never used.
* 把沒用到的 strnatcasecmp() 整段刪除

    strnatcmp.c:109:14: style: The scope of the variable 'ca' can be reduced. [variableScope]
        nat_char ca, cb;
                 ^
    strnatcmp.c:109:18: style: The scope of the variable 'cb' can be reduced. [variableScope]
        nat_char ca, cb;
                     ^
    strnatcmp.c:167:0: style: The function 'strnatcasecmp' is never used. [unusedFunction]

    ^

    Fail to pass static analysis.