# 2019q1 Homework1 (lab0)
contributed by < [ `ndsl7109256` ](https://github.com/ndsl7109256) >

[作業說明](https://hackmd.io/s/BJp_jq-tm)
[C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)

## 環境

$ uname -a
Linux bk 4.15.0-39-generic #42-Ubuntu SMP Tue Oct 23 15:48:01 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version 
gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0

## 作業目標
- 英文閱讀
- C 語言程式設計基礎
- 準備 GNU/Linux 開發工具
- 學習使用 Git 與 GitHub
- 學習效能分析
- 研究自動測試機制

## 作業要求
- 實驗目標為實作 queue
* first in, first out (FIFO)
* last in, first out (LIFO)

## 實際過程
此次作業主要編輯的部分其實只有 `queue.c` 和 `queue.h` 其他有趣的部分留在後面探討。

- queue.h

在 queue.h 裡只更動了 queue_t 的 structure部分，在裡面加入一個指向指標 tail 的指標和一個 integer 的 size 。其目的主要為了達成 $O(1)$ 的 q_insert_tail 和 q_size 否則每次都必須遍尋整串 linked list 使時間複雜度變成 $O(n)$。

    typedef struct {
    list_ele_t *head;   /* Linked list of elements */
                        
    list_ele_t **tail;  // To implement q_insert_tail quickly
    int size;           // To know the q_size quickly
    } queue_t;
    

- queue.c
* q_new
初始化 queue ，記得檢查有沒有 malloc 成功和將 size 設為 0。
(這裡的 q->tail 不能初始化為 NULL 否則如果一開始就 insert tail 的話會失敗 )

    queue_t *q_new()
    {
        queue_t *q = (queue_t *) malloc(sizeof(queue_t));
        /* What if malloc returned NULL? */
        if (q != NULL) {
            q->head = NULL;
            q->tail = &q->head;
            q->size = 0;
            return q;
        } else
            return NULL;
    }

* q_free
如果 queue 存在的話，不斷檢查其 head 是否 NULL ，如果是就不斷切掉頭，再將 head 指向原本 head 的下一個 element。最後再 free 掉 queue 本身。

記得如果只 free head 本身，其裡面的 value **並不會** 被一起 free 掉。要連同 value 一起做 free 的動作。

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

            while (q->head != NULL) {
                next = q->head->next;
                free(q->head->value);
                free(q->head);
                q->head = next;
            }
            free(q);
        }
    }    

* q_insert_head
一開始要逐步確認 queue 是否存在、 malloc node 是否成功、 malloc value 是否成功 (如果 malloc 失敗記得 free 掉 node再結束否則會有 memory leak)。
而這裡 malloc 和 copy 字串的長度記得要再加 1 給終結字元否則會有亂碼錯誤出現。

        ERROR:  Removed value dolphin��� != expected value dolphin

    bool q_insert_head(queue_t *q, char *s)
    {
        /* What should you do if the q is NULL? */
        if (q == NULL)
            return false;
        list_ele_t *new_node = (list_ele_t *) malloc(sizeof(list_ele_t));
        /* What if either call to malloc returns NULL? */
        if (new_node == NULL)
            return false;

        /* Don't forget to allocate space for the string and copy it */
        new_node->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
        if (new_node->value == NULL) {
            free(new_node);
            return false;
        }
        memcpy(new_node->value, s, (strlen(s) + 1));

        new_node->next = q->head;
        q->head = new_node;
        if (q->size == 0) {
            q->tail = &new_node->next;
        }
        ++q->size;
        return true;
    }

* q_insert_tail
跟 q_insert_head 類似，感謝 tail。 可以直接串在 tail 指向的位置就好。

    bool q_insert_tail(queue_t *q, char *s)
    {
        /* You need to write the complete code for this function */
        /* Remember: It should operate in O(1) time */
        if (q == NULL)
            return false;
        list_ele_t *new_node = (list_ele_t *) malloc(sizeof(list_ele_t));

        if (new_node == NULL)
            return false;


        new_node->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
        if (new_node->value == NULL) {
            free(new_node);
            return false;
        }
        memcpy(new_node->value, s, (strlen(s) + 1));

        new_node->next = NULL;
        *(q->tail) = new_node;
        q->tail = &new_node->next;
        ++q->size;
        return true;
    }    

* q_remove_head

    bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
    {
        if (q == NULL || q->size == 0) {
            return false;
        }
        list_ele_t *ptr;

        ptr = q->head;
        q->head = q->head->next;

        if (sp != NULL) {
            strncpy(sp, ptr->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        }
        free(ptr->value);
        free(ptr);
        q->size--;
        if (q->size == 0) {
            q->tail = &q->head;
        }
        return true;
    }

* q_size

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

* q_reverse

    void q_reverse(queue_t *q)
    {
        if (q != NULL && q->size > 1) {
            list_ele_t *prev = q->head, *next;

            q->tail = &(prev->next);
            q->head = q->head->next;
            *q->tail = NULL;
            while (q->head != NULL) {
                next = q->head->next;
                q->head->next = prev;
                prev = q->head;
                q->head = next;
            }
            q->head = prev;
        }
    }

## 時間複雜度分析
隔每個 1000000 個 element 測量 insert tail 和 計算 size 的時間
- insert_tail

cmd>new
q = []
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time it a
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.026
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time it a
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.044
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time it a
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.078
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time it a
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.094

| Element 數 | 1000000 | 2000000 | 3000000 | 4000000 |
| -------- | -------- | -------- |-------- | -------- |
| **Delta time** | 0.026 | 0.044 |0.078 | 0.094 |

- size

cmd>new
q = []
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time size
Queue size = 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.023
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time size 
Queue size = 2000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.050
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time size
Queue size = 3000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.067
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time size
Queue size = 4000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.088
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time size 
Queue size = 5000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.128
cmd>ih a 1000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
cmd>time size
Queue size = 6000000
q = [a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ... ]
Delta time = 0.149

| Element 數 | 1000000 | 2000000 | 3000000 | 4000000 |5000000 | 6000000 |
| -------- | -------- | -------- |-------- | -------- | -------- |-------- | -------- |
| **Delta time** | 0.023 | 0.050 |0.067 | 0.088 | 0.0128 | 0.149 |

這裡發現每次所花的時間跟我們預期的還是有所差距，明顯會隨著 element 數而增加。
尚須思考為何有這樣的情形發生。
## 自動評分系統運作的原理

CPP check 靜態分析
Vargilind 動態分析

git stash?

oom killer

sat formal verification

###### tags: `sysprog`,`2019spring`