2019q1 Homework1 (lab0)

contributed by < ndsl7109256 >

環境

$ 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