# 2020q1 Homework1 (lab0)
contributed by < ``yceugene`` >

### Outline
* 環境設定
* 作業要求
* 實作流程
* 新增指令
* TODO

### 環境設定

$ uname -a
Linux LAPTOP-K7JUAVPA 4.19.128-microsoft-standard #1 SMP Tue Jun 23 12:58:10 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$  gcc --version                                     
gcc-10 (Homebrew GCC 10.2.0) 10.2.0                   
Copyright (C) 2020 Free Software Foundation, Inc.     
This is free software; see the source for copying conditions. There is NO 
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

### 作業要求
* 在 ``queue.[c/h]`` 中完成以下實作:
* ``q_new``: 建立新的「空」佇列;
* ``q_free``: 釋放佇列所佔用的記憶體;
* ``q_insert_head``: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* ``q_insert_tail``: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* ``q_remove_head``: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* ``q_size``: 計算佇列中的元素數量。
* ``q_reverse``: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* ``q_sort``: 以遞增順序來排序鏈結串列的元素

### 實作流程
#### queue.h
根據題目要求為了讓 q_size 和 q_insert_tail 都可在 Q(1) 內完成，我們需要在 queue_t 結構中新增一些成員。
* 新的 Queue 結構定義如下:

    typedef struct {
        list_ele_t *head; 
        list_ele_t *tail;
        int size;
    } queue_t;

#### queue.h
##### q_new
* 新增一個空 queue 時，需要先以 malloc() 配置的一塊夠大的記憶體空間存放此 queue ，需要預防 malloc 配置失敗的情況，因次我們的程式在對 queue 初始化結構成員時，要先判斷 malloc() 回傳的是否為有效記憶體位址(即回傳位址非 NULL)。
* 修改 q_new() 如下:

    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
* 在釋出 queue 占用的記憶體空間前須先判斷 q 是否為 NULL，若否才會進一步釋放記憶體。
* 由於各個 queue 節點中都包含一個指向 string value 的指標，因此在我們依序釋放各節點前要先釋放該節點指向的 string，接著才是移除該節點。
* 在釋放 queue 之前我們先宣告一個 temp_ptr 指標，其功能是逐一指向 head 的下一個節點，這樣的好處是當我們用 head 釋放前一個節點後，仍然能保留下一個開始節點的資訊。
* 修改 q_free 如下:

    void q_free(queue_t *q)
    {
        /* TODO: How about freeing the list elements and the strings? */
        /* Free queue structure */
        if (!q)
            return NULL;

        list_ele_t *temp_ptr;
        while (q->head) {
            temp_ptr = q->head->next;
            free(q->head->value);
            free(q->head);
            q->head=temp_ptr;
        }
        free(q);
    }

##### q_insert_head
* 根據提示，當函式被呼叫時先檢查 q 是否為 NULL，是則 return false。
* 針對要 insert 的字串配置一塊有效的記憶體，加上字串結束字元一共需準備 (strlen(s) + 1) 個 char 大小的空間。
* insert_head 過程中會做兩次的 malloc ，分別配置記憶體空間給新節點和新節點所指向的字串(存放要插入的字串)，若 malloc 失敗則 return false。
* 如果成功配置記憶體給新節點，但字串空間配置失敗則必須一併釋放新節點的記憶體，再 return false。
* 配置好新節點後，須將新節點的記憶體位置 assign 給 q->head，並將 q->size 加一。
* 最後考慮新節點是否為第一個建立的節點，是的話則必須再以 q->tail 指向新節點(這時只有一個節點，此節點同時為 head 也是 tail)。

    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;

        /* To allocate space for the string and copy it */
        newh->value = malloc(sizeof(char) * (strlen(s) + 1));
        if (!newh->value)
        {
            free(newh);
            return false;
        }
        memset (newh->value,'\0', strlen(s) + 1);
        strncpy(newh->value, s, strlen(s));

        /* Adjust head and size */
        newh->next = q->head;
        q->head = newh;
        q->size += 1;

        /* Adjust tail */
        if (q->tail == NULL)
        {
            q->tail = newh;
        }
        return true;
    }

##### q_insert_tail
* 做法和 q_insert_head 類似，只是方向不同

    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(sizeof(char) * srlen(s + 1));

        if(!newt)
        {
            free(newt);
            return false;
        }

        memset(newt->value, 0, sizeof(char) * srlen(s + 1));
        newt->value = strncpy(newt->value, s, strlen(s));
        newt->next = q->head;

        q->tail->next = newt;
        q->tail = newt;

        q->size += 1;

        if(!q->head)
            q->head = newt;

        return false;
    }

##### q_remove_head
* 發生下列兩種情況時 return false
* 修改 q_remove_head 如下:

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

    if (strlen(q->head->value) * sizeof(char) > bufsize - 1)
        return NULL;

    memset(sp, '\0', sizeof(char) * bufsize);
    strncpy(sp, q->head->value, bufsize);

    list_ele_t *temp_ptr = q->head->next;
    free(q->head->value);
    free(q->head);

    q->head = temp_ptr;
    q->size -= 1;


    return true;
}

##### q_reverse
* 這裡我參考 http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html 中對 single linkded list 做 reverse 的方式:
1. 先判斷 queue 中有幾個有效節點:
* 若 ``q->size < 2`` 直接 return
* 若 ``q->size == 2`` 也很好處理
2. 當 ``q->size >= 3`` 時，我們先新增三個 pointer: prev_ptr、curr_ptr、post_ptr，依序從原本 head 位址依序向 tail 方向移動，每次移動時改變 curr_ptr 指向節點的 next 的方向反轉。
* 改寫 q_reverse 如下:

    void q_reverse(queue_t *q)
    {
        if (!q)
            return;
        if (q->size<2)
            return;
        if (q->size == 2)
        {
            q->head->next = NULL;
            q->tail->next = q->head;
            q->head = q->tail;
            q->tail = q->tail->next;
            return;
        }
        list_ele_t *prev_ptr = NULL;
        list_ele_t *curr_ptr = NULL;
        list_ele_t *post_ptr = NULL;

        prev_ptr = q->head;
        curr_ptr = prev_ptr->next;
        post_ptr = curr_ptr->next;

        q->head = q->tail;
        q->tail = prev_ptr;
        prev_ptr->next = NULL;

        while (post_ptr->next)
        {
            curr_ptr->next = prev_ptr;
        }
        post_ptr->next = curr_ptr;

        return;
    }

##### q_size
* 若 q 不為 NULL，直接回傳 q->size 即可。
* 修改 q_size 如下:

    int q_size(queue_t *q)
    {
        if(!q)
            return false;
        return q->size;
    }

### 嘗試新增 hello 指令
1. 做法:
* 修改 qtest.c
* 在 console_init() 中新增如下:

        add_cmd("hello", do_hello, "                | Print hello message");

* 在 Forward declarations 中新增如下:

        static bool do_hello(int argc, char *argv[]);

* 新增 do_hello()

        static bool do_hello(int argc, char *argv[])
        {
            return (bool) printf("Hello, World\n");
        }

2. 編譯後執行結果:
* 輸入 help 可看到新增的 hello 指令

   Commands:
        #        ...            | Display comment
        free                    | Delete queue
        hello                   | Print hello message
        help                    | Show documentation

* 輸入 hello 可看到執行效果

    cmd> hello
    Hello, World

## 其他:
* lab0 作業說明中:
* "qtest 命令直譯器的實作" 內容中 cmd_init 應改為 init_cmd 。
* "以下示範在console.c 檔案新增名為 hello 的命令。先準備 do_hello 函式" 內文中 console.c 應改為 qtest.c。

### TODO
* Cppcheck: 靜態程式碼分析工具
* 新增指令 hello
* Git Hooks 進行自動程式碼排版檢查
* Valgrind 動態程式分析工具
* 研究自動測試機制
* Linux Programming Interface