2022q1 Homework1 (lab0)

contributed by < sternacht >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu

Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
Stepping:                        10
CPU MHz:                         1800.000
CPU max MHz:                     3400.0000
CPU min MHz:                     400.0000
BogoMIPS:                        3600.00
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

作業要求

依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。

q_new: 創一個空的 queue
q_free: 釋放掉一個 queue
q_insert_head: 在 head 插入一個 element (LIFO)
q_insert_tail: 在 tail 插入一個 element (FIFO), O(1)
q_remove_head: 把 head 的 element 移除
q_remove_tail: 把 tail 的 elemeny 移除
q_size: return queue 的大小
q_delete_mid: 把位在中間的 element 刪除
q_reverse: 將 queue 反轉，不配置或釋放任何的 element
q_delete_dup: 將 queue 中有重複字串出現的所有節點刪除
q_swap: 將 queue 的節點兩兩一組交換順序
q_sort: 將 queue 由小排到大, sort by nature sort
在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。

列出其他在作業要求中出現的操作，例如 LeetCode 題目。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

開發過程

q_new

向記憶體索取大小為 element_t 的空間，並檢查是否成功，若非則回傳 NULL ，是則進行初始化並回傳

struct list_head *q_new()
{    
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return NULL;
    new->value = NULL;
    INIT_LIST_HEAD(&(new->list));
    return &(new->list);
}

git commit 時出現以下警告

queue.c:25:5: error: Memory leak: new [memleak]
return &(new->list);
^

修改為

struct list_head *q_new()
{    
    struct list_head *new = malloc(sizeof(struct list_head));
    if (!new)
        return NULL;
    INIT_LIST_HEAD(new);
    return new;
}

q_free

逐個走訪包括 head 在內的 entry 並將其釋放

void q_free(struct list_head *l)
{
    element_t *del = NULL, *safe = NULL;
    list_for_each_entry_safe(del, safe, l, list){
        free(del);
    }
    free(l);
}

原先未考慮到 element 內還有 value 要釋放而出錯，並且在輸入值為 NULL 也沒有進行例外處理，因此修改為

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *del, *safe;
    list_for_each_entry_safe(del, safe, l, list){
        list_del(&(del->list));
        q_release_element(del);
    }
    free(l);
}

q_insert_head

判斷佇列是否存在，否則回傳 false ，是則向記憶體索取大小為 element_t 的空間，失敗則回傳 false ，成功則將 s 的內容複製到節點內，並將該節點放入 queue 的開頭並回傳 true 。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    strcpy(new->value, s);
    list_add(&(new->list), head);
    return true;
}

new 配置時的 new->value 尚未配置記憶體空間，因此 strcpy 會報錯，因此需要先行計算欲放入的字串大小並向記憶體索取適當的空間，然後再用 strncpy 將字串放入。

註 : strcpy 與 strncpy 的差別在於 strcpy 會有 buffer overflow 的問題，因為其不考慮 *dest 是否有足夠空間放下 *src 的字串，而 strncpy 則會透過最後一個參數 count 來限制，但在必要時需自行補上 \0 來做結尾。參考來源

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    size_t len = strlen(s) + 1;
    new->value = malloc(len);
    if (!new->value) {
        free(new);
        return false;
    }
    strncpy(new->value, s, len);
    list_add(&new->list, head);
    return true;
}

q_insert_tail

大致與 q_insert_head 相同，僅節點放置之位置不同。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    strcpy(new->value, s);
    list_add_tail(&new->list, head);
    return true;
}

同 q_insert_head 做修改

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    size_t len = strlen(s) + 1;
    new->value = malloc(len);
    if (!(new->value)) {
        free(new);
        return false;
    }
    strncpy(new->value, s, len);
    list_add_tail(&new->list, head);
    return true;
}

q_remove_head

將 queue 中的第一個節點移出 queue 並回傳該節點，同時將節點中的內容複製到 sp 中，若queue 不存在或為空時回傳 NULL 。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head || list_empty(head))
        return NULL;
    element_t *remove = NULL;
    remove = list_entry (head->next, element_t, list);
    strncpy(sp, remove->value, bufsize);
    head->next = head->next->next;
    return remove;
}

題目上表示 if sp is non-NULL… ，因此加上對 sp 的判斷式。此外，之前對strncpy有誤會，字串末的 \0是要自己加的，連同最後第二行錯誤也一齊修正，修改後如下:

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *remove = list_entry(head->next, element_t, list);
    if (sp != NULL){
        strncpy(sp, remove->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    list_del_init(&(remove->list));
    return remove;
}

q_remove_tail

大致同 q_remove_head 。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head || list_empty(head))
        return NULL;
    element_t *remove = list_entry(head->prev, element_t, list);
    strncpy(sp, remove->value, bufsize);
    head->prev = head->prev->prev;
    return remove;
}

同 q_remove_head 做修改

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *remove = list_entry(head->prev, element_t, list);
    if (sp != NULL){
        strncpy(sp, remove->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    list_del_init(&(remove->list));
    return remove;
}

q_size

利用一個 counter 逐個計算 queue 中的節點個數(不包含 head )，當 queue 不存在時回傳0

{
    if (!head)
        return 0;
    int len = 0;
    struct list_head *node;
    list_for_each (node, head)
        len++;
    return len;
}

q_delete_mid

利用快慢指標來找出位在中間的節點，因作業要求是在 queue size 為偶數時刪除第

⌊ \frac{n}{2} ⌋

個，因此要從 head 開始，而非從 head->next 開始，刪除時先利用 list_del_init 將位處中間的節點 slow 從 queue 中移除，再用 q_free 將該節點的記憶體釋放。

註 : list_del 不會將該節點的 prev, next 指回自身，因此直接用使用 q_free 會有問題，需要先取得整個節點( element_t )後，再進行 free 。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *slow = head;
    for (struct list_head *fast = head; fast && fast->next; fast->next->next){
        slow = slow->next;
    }
    list_del_init(slow);
    q_free(slow);
    return true;
}

先前撰寫時錯以 singly linked list 的方式來寫，但這樣在 doubly linked list 中會有 infinite loop 的問題發生，因此改成以個數計算的方式來做為迴圈的條件，找出第

⌊ \frac{n}{2} ⌋

個節點

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *node = head;
    for (int len = q_size(head); len > 0; len -= 2) {
        node = node->next;
    }
    element_t *del = list_entry(node, element_t, list);
    list_del(node);
    q_release_element(del);
    return true;
}

q_delete_dup

將佇列裡有重複出現的所有字串刪除，當佇列不存在或為空時回傳 false ，若只有一個節點則因不會有重複出現直接回傳 true 。

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    if (list_empty(head) || list_is_singular(head))
        return true;
    struct list_head *node = head->next;
    struct list_head *del_q = q_new();
    element_t *entry1 = NULL, *entry2 = NULL;
    int len = q_size(head) - 1;
    while (len > 0) {
        entry1 = container_of(node, element_t, list);
        entry2 = list_entry(node->next, element_t, list);
        if (strcmp(entry1->value, entry2->value) == 0) {
            while (len && strcmp(entry1->value, entry2->value) == 0) {
                list_move(node->next, del_q);
                entry2 = list_entry(node->next, element_t, list);
                len--;
            }
            node = node->next;
            list_move(node->prev, del_q);
        } else {
            node = node->next;
        }
        len--;
    }
    q_free(del_q);
    return true;
}

q_swap

將佇列中的節點兩兩交換位置

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *lnode = head->next;
    struct list_head *rnode = lnode->next;
    int len = q_size(head);
    while (len > 1) {
        lnode->prev->next = rnode;
        rnode->next->prev = lnode;
        lnode->next = rnode->next;
        rnode->prev = lnode->prev;
        lnode->prev = rnode;
        rnode->next = lnode;
        lnode = lnode->next;
        rnode = lnode->next;
        len -= 2;
    }
    return;
}

使用 List API 改寫為更精簡好讀的程式碼。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

先前對 list_add 有些誤會，仔細想一想才發覺改成這樣做是沒問題的，雖然以指標操作的數量來說並沒有減少，但相比於上方的程式碼來說，更為直觀且好讀。

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    bool lock = false;
    struct list_head *node = NULL, *safe = NULL;
    list_for_each_safe(node, safe, head) {
        if (lock){
            list_del(node);
            list_add(node, safe->prev->prev);
        }
        lock = !lock;
    }
    return;
}

q_reverse

將佇列中的節點順序反過來

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        list_del(node);
        list_add(node, head);
    }
    return;
}

q_sort

將佇列中節點依照字串值由小至大排序

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    // list_head is doubly linked list, so make it singly first
    head->prev->next = NULL;
    
    // go mergesort
    head->next = q_mergesort(head->next);
    
    // make queue doubly again
    head->next->prev = head;
    struct list_head *node = head->next;
    while (node->next){
        node = node->next;
    }
    node->next = head;
    head->prev = node;
}

struct list_head *q_mergesort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *tail = q_split(head);
    head = q_mergesort(head);
    tail = q_mergesort(tail);
    return q_merge(head, tail);
}

struct list_head *q_merge(struct list_head *head, struct list_head *tail)
{
    if (!head)
        return (tail);
    if (!tail)
        return (head);
    if (cmp(head, tail) > 0){
        tail->next = q_merge(head, tail->next);
        tail->next->prev = tail;
        tail->prev = NULL;
        return tail;
    } else {
        head->next = q_merge(head->next, tail);
        head->next->prev = head;
        head->prev = NULL;
        return head;
    }
}

struct list_head *q_split(struct list_head *head)
{
    struct list_head *slow = head;
    for (struct list_head *fast = head->next; fast && fast->next;
                    fast = fast->next->next){
        slow = slow->next;
    }
    struct list_head *tmp = slow->next;
    slow->next = NULL;
    return tmp;
}

int cmp(struct list_head *a, struct list_head *b)
{
    element_t *entry1 = list_entry(a, element_t, list);
    element_t *entry2 = list_entry(b, element_t, list);
    return strcmp(entry1->value, entry2->value);
}

以上是用 merge sort 實作，理論上時間複雜度為

O (n \log n)

，而以測試的結果來說，該 sort 實作可以通過第 15 項測試，表示其時間複雜度確實在

O (n \log n)

，然而此 sort 實作在第 14 項測試中會失敗。

接著引入 lib/list_sort.c

void q_sort(struct list_head *head)
{
    // this function is rewrite from list_sort.c
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *list = head->next, *pending = NULL;
    size_t count = 0;
    head->prev->next = NULL;
    do {
        size_t bits;
        struct list_head **tail = &pending;
        for (bits = count; bits & 1; bits >>= 1)
            tail = &(*tail)->prev;
        if (likely(bits)) {
            struct list_head *a = *tail, *b = a->prev;
            a = merge(b, a);
            a->prev = b->prev;
            *tail = a;
        }
        list->prev = pending;
        pending = list;
        list = list->next;
        pending->next = NULL;
        count++;
    } while (list);
    list = pending;
    pending = pending->prev;
    for (;;) {
        struct list_head *next = pending->prev;
        if (!next)
            break;
        list = merge(pending, list);
        pending = next;
    }
    merge_final(head, pending, list);
}

int cmp(struct list_head *a, struct list_head *b)
{
    element_t *entry1 = list_entry(a, element_t, list);
    element_t *entry2 = list_entry(b, element_t, list);
    return strcmp(entry1->value, entry2->value);
}

static struct list_head *merge(struct list_head *a, struct list_head *b)
{
    struct list_head *head, **tail = &head;
    for (;;) {
        if (cmp(a, b) <= 0) {
            *tail = a;
            tail = &a->next;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

static void merge_final(struct list_head *head,
                        struct list_head *a,
                        struct list_head *b)
{
    struct list_head *tail = head;
    int count = 0;
    for (;;) {
        if (cmp(a, b) <= 0) {
            tail->next = a;
            a->prev = tail;
            tail = a;
            a = a->next;
            if (!a)
                break;
        } else {
            tail->next = b;
            b->prev = tail;
            tail = b;
            b = b->next;
            if (!b) {
                b = a;
                break;
            }
        }
    }
    tail->next = b;
    do {
        if (unlikely(!++count))
            cmp(b, b);
        b->prev = tail;
        tail = b;
        b = b->next;
    } while (b);
    tail->next = head;
    head->prev = tail;
}

從 list_sort.c 改寫的 sort 實作可通過第 14 項測試，觀察兩種 sort function 在 perf top 中的使用情況，主要由兩項函式消耗大部分的資源，第一個是 sort 本身，第二個是 strcmp ，前後兩個相比 strcmp 消耗程度大致相同，因此合理推斷導致第 14 項測試結果出現分歧的原因，就是第一個 sort 實作使用的是 recuresive 的結構，而使得資料量大的時候會出現崩潰。

需要更多分析和實驗，來支持你的論點。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110== Can't extend stack to 0x1ffe8010a8 during signal delivery for thread 1:
==59110==   no stack segment
==59110== 
==59110== Process terminating with default action of signal 11 (SIGSEGV)
==59110==  Access not within mapped region at address 0x1FFE8010A8
==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110==    at 0x10EED6: q_merge (queue.c:313)
==59110==  If you believe this happened as a result of a stack
==59110==  overflow in your program's main thread (unlikely but
==59110==  possible), you can try to increase the size of the
==59110==  main thread stack using the --main-stacksize= flag.
==59110==  The main thread stack size used in this run was 8388608.
==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110== 
==59110== Process terminating with default action of signal 11 (SIGSEGV)
==59110==  Access not within mapped region at address 0x1FFE801F70
==59110== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==59110==    at 0x4831130: _vgnU_freeres (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_core-amd64-linux.so)
==59110==  If you believe this happened as a result of a stack
==59110==  overflow in your program's main thread (unlikely but
==59110==  possible), you can try to increase the size of the
==59110==  main thread stack using the --main-stacksize= flag.
==59110==  The main thread stack size used in this run was 8388608.
Segmentation fault (core dumped)

利用 valgraind ./qtest ，並執行如 14 項測試中的命令順序 :
new -> ih dolphin 1000000 -> it gerbil 1000000 -> reverse -> sort
其中用 recursive 形式的 sort 實作會跑出以上的訊息，並以 Segmentation fault (core sumped) 的錯誤結束程式。
仔細看看錯誤訊息，可以發現出錯的原因是主程式 main 的 stack 沒有空間了，也就是大名鼎鼎的 stack overflow，這是因為函式在執行的時候，若是遇到要執行其他函式，則會把目前的參數值、變數以及其他函數結束後的返回位址 push 到該函式的 stack 中，直到要繼續執行才會 pop 出來，而也就是因為這個特性，使得 recursive 形式的函式雖然直觀但執行速度慢 (push, pop 都要花時間)，而且還有發生 stack overflow 的風險。

shuffle

將佇列中的節點打亂，演算法參考
以下是直接利用演算法的原理實作的，能夠運作但依然需要改進，尤其是面對巨量資料的時候。

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    srand(time(0));
    int len = q_size(head);
    struct list_head *tail = head->prev, *node = NULL;
    for (;len > 1; len--) {
        node = head->next;
        for (int i = rand() % len; i > 0; i--){
            node = node->next;
        }
        swap_two_node(node, tail);
        tail = node->prev;
    }
}

void swap_two_node(struct list_head *a, struct list_head *b)
{
    if (a->next == b){
        a->prev->next = b;
        b->next->prev = a;
        a->next = b->next;
        b->prev = a->prev;
        a->prev = b;
        b->next = a;
    } else {
        struct list_head *tmp;
        a->prev->next = b;
        b->prev->next = a;
        tmp = a->prev;
        a->prev = b->prev;
        b->prev = tmp;
        a->next->prev = b;
        b->next->prev = a;
        tmp = a->next;
        a->next = b->next;
        b->next = tmp;
    }
}

因為 queue.h 不能更動的關係，需要額外寫一個 .h 檔來放置函式的宣告，如下，並在 qtest.c 中將其 include 進去

#include "list.h"
#include "queue.h"

void q_shuffle(struct list_head *head);

void swap_two_node(struct list_head *a, struct list_head *b);

原本的演算法中，面對結構簡單的陣列可以達到

O (n)

的時間複雜度，但在結構較複雜且記憶體不連續的 linked list 中，要還原演算法的話就必須花費

O (n^{2})

的時間複雜度在逐個尋找節點的過程上。

總是書寫為 linked list，中間不要有連字號。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

而若不考慮完全按照演算法，不用交換 node 的方式來做，則可以不使用 swap 函式，改成如下，在指標的操作上次數會固定，而不需要進行條件判斷

// swap_two_node(node, tail);
// tail = node->prev;
//     |
//     v
list_del(node);
list_add(node, tail->prev);
tail = node;

完全移除 swap_two_node，改為用 list api 來實作

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    srand(time(0));
    int len = q_size(head);
    struct list_head *tail = head->prev, *node = NULL;
    for (;len > 1; len--) {
        node = head->next;
        for (int i = rand() % len; i > 0; i--){
            node = node->next;
        }
        if (node->next != tail){
            list_del(node);
            list_add(node, tail->prev);
        }
        tail = node;
    }
}

web

使用 tiny-web-server 提供伺服器功能，目前如下的程式能符合伺服器運作的同時， qtest 仍可輸入指令命令的要求，但是當 tiny 有輸出訊息時，畫面會被覆蓋掉，不影響運作。

instruction 是「指令」，command 是「命令」，二者語意不同。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

錯誤嘗試

// this code is writen in qtest.c, not queue.c
static bool do_web(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    // tiny is installed in different path, so path was given here
    int id = system("../tiny-web-server/tiny 9999 &");
    if (id == -1)
        return false;
    return true;
}

更新錯誤 : 當 qtest 結束執行時， tiny 程式不會結束執行，也無法用 jobs 命令查到。

不要呼叫 system 函式，你應該引入 tiny-web-server 的原始程式碼並整合。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

select 系統呼叫在本程式的使用方式

首先先看看 select 的用途，參考了這篇以及這篇，了解 select 中各項傳入參數所代表的意義。

select(nfds, readfds, writefds, exceptfds, timeout) 中， ndfs 用以表示可以檢查的 file descriptors 的範圍，中間三個參數個別表示指向存放 read, write, except 的三個 file descriptors set (fd_set) ，最後 timeout 參數則限制了 select 要等待多久，特別的是當 timeout 值為 NULL 時， select 會無限制的等下去。

當 select 回傳 -1 表示有錯誤發生，回傳 0 表示等待超時，而成功時則會回傳一個值，根據描述，這個值是大於0的，端看傳入的 fd_set 大小。

the total number of bits that are set in readfds, writefds, exceptfds

回頭看 select 在程式中在何處使用，是在 console.c 的 cmd_select 中，並且依據 cmd_select 的使用， nfds, writefds, exceptfds, timeout 四個參數的傳入值都是固定的，分別是 0 以及三個 NULL ，這意味著 select 永遠只會看 read 的 fd_set 中的第一個，而且會無限制地等到該 fd 準備好，而該 fd 就是指向我們所輸入的命令ㄉ，或是 source 從檔案中讀到的第一個命令。

運用 Valgrind 排除 qtest 實作的記憶體錯誤

如果輸入 make valgrind 來檢查程式運作，在將 queue.c 撰寫完成之後，仍可看到來自 linenoise.c 的錯誤發生，而主要是從 linenoiseHistoryAdd 的函式中所取的記憶體沒有完全釋放掉，而使部分資料仍 'reachable'

先看這部分的程式碼是如何運作

int linenoiseHistoryAdd(const char *line)
{
    char *linecopy;
    if (history_max_len == 0)
        return 0;

    /* Initialization on first call. */
    if (history == NULL) {
        history = malloc(sizeof(char *) * history_max_len);
        if (history == NULL)
            return 0;
        memset(history, 0, (sizeof(char *) * history_max_len));
    }

    /* Don't add duplicated lines. */
    if (history_len && !strcmp(history[history_len - 1], line))
        return 0;

    /* Add an heap allocated copy of the line in the history.
     * If we reached the max length, remove the older line. */
    linecopy = strdup(line);
    if (!linecopy)
        return 0;
    if (history_len == history_max_len) {
        free(history[0]);
        memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
        history_len--;
    }
    history[history_len] = linecopy;
    history_len++;
    return 1;
}

這個函式看起來沒有問題，因此錯誤應該不是發生在函式內部，接著看發生 memory leak 的地方是在 qtest.c 呼叫 history load 時所產生的，推測是結束時 histroy 的記憶體沒有被釋放掉，所以再來看 main 結束之前的動作，
TODO

2022q1 Homework1 (lab0)

實驗環境

作業要求

開發過程

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

shuffle

web

select 系統呼叫在本程式的使用方式

運用 Valgrind 排除 qtest 實作的記憶體錯誤

Read more

2022q1 Homework5 (quiz5)

DSAI_final_project

2022q1 Homework6 (ktcp)

2022q1 Homework3 (fibdrv)