owned this note   changed 5 years ago  
Published Linked with GitHub

2020q1 Homework1 (lab0)

contributed by < gpwork4u >

實驗環境

$ uname -a
Linux 5.3.0-28-generic #30~18.04.1-Ubuntu SMP Fri Jan 17 06:14:09 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0

作業要求

  • 詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式
  • 修改排序所用的比較函式，變更為 natural sort，在 “simulation” 也該做對應的修改，得以反映出 natural sort 的使用。
  • 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
  • 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理;
  • 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
    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 →
    為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)

開發過程

queue.h

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

根據老師提供的作業說明所作的修改，加上一個 int size 變數在每次增減元素時做紀錄。

在實作q_insert_tail時，要求要將原本 \(O(n)\) 的時間修改為 \(O(1)\) ，因此在 queue_t 中增加一個 tail 指標，以便直接在 queue 的尾端新增元素。

參考 OscarShiang 同學指標的使用方法，改用 list_ele_t *tmp 指標進行操作。

queue.c

q_new

  • 回傳一個空的 queue
  • 當 malloc 失敗時需要回傳 NULL
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_size

  • return queue 的元素數量
  • queue 為 NULL 時 return 0;
int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}

把 q->size 直接傳回去就是
一開始實作的時候沒考慮 queue 為 NULL 的情形，加進去之後分數會多六分

q_free

  • 將 queue 中佔用的記憶體釋放
  • 當 queue 為 NULL 時，直接 return 結束
void q_free(queue_t *q)
{
    if (!q)
        return;
    while (q->head) {
        list_ele_t *tmp;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);  
}

從 head 依序拜訪各個元素並作釋放
最後再將 queue 的指標釋放

q_insert_head

  • 從 queue 的 head 插入一個元素
  • 當 queue 為 NULL 或分配位置時失敗 return false
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (!q)
        return false;
     newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(sizeof(char)*(strlen(s) + 1))
    if (!newh->value) {
        free(newh);
        return false;
    }
    snprintf(newh->value, strlen(s) + 1, "%s", s);
    newh->next = q->head;
    q->head = newh;
    if (!q->tail)
        q->tail = newh;
    q->size++;
    return true;
}

在 queue 為空時需要另外將 tail 也指向新增的元素

於作業說明中提到

依據 CERN Common vulnerabilities guide for C programmers
建議而移除 gets / sprintf / strcpy 等不安全的函式;

因此在將資料傳給 newh->value 時為了避免使用 strcpy ，改採用根據 CERN 所提供的建議中的snprintf函式來進行操作。

int snprintf(char * restrict s, size_t n, const char * restrict format, …);

在使用snprintf時，將參數 size_t n 設為 strlen(s)時，會發現輸出結果跟預期的不一樣，如下

cmd> new
q = []
cmd> ih 123
cmd> ih 123
q = [12]

在經查閱C99規格書之後，其對於 snprintf的敘述如下

The snprintf function is equivalent to fprintf, except that the output is written into an array (specified by argument s) rather than to a stream. If n is zero, nothing is written, and s may be a null pointer. Otherwise, output characters beyond the n-1st are discarded rather than being written to the array, and a null character is written at the end of the characters actually written into the array. If copying takes place between objects that overlap, the behavior is undefined.

從中可以知道， snprintf 會根據 size_t n ，將第 n-1 個位置以後的字串捨棄，並在第 n 位放入 NULL，因此在利用 strlen(s) 作為 Buffer size 時，須加一才能將完整的 s 值傳進 newh->value 。

在 value 做 malloc 的時候，一開始是使用 sizeof(s) 配置記憶體空間，後來在後續的測試中發現傳入的字串大小大於等於 8 時，在進行釋放的時候會出現。

ERROR: Corruption detected in block with address 0x558b91c49ce0 when attempting to free it

後來測試的時候發現 malloc(sizeof(s)) 並不會配置一個跟 s 一樣的記憶體大小，而是 pointer 大小，導致在只用 sizeof(s) 作分配時不夠大，在用snprintf 放入字串過大導致在釋放記憶體時動到了原本沒分配的部份，最後改用 sizeof(char)*strlen(s)+1 就可解掉這個 error，在 q_insert_tail 更新了一樣的作法。

根據 C 規格書中對 sizeof 的描述，如傳入的 sizeof(s) 中 s 是個陣列的話，是可以直接用的，當是 pointer 時就只會是 pointer 的大小，而在 64 位元的系統中，一個 pointer 的大小即是8個 byte 。

When sizeof is applied to an operand that has type char, unsigned char, or signed char, (or a qualified version thereof) the result is 1.
When applied to an operand that has array type, the result is the total number of bytes in the array.
103) When applied to an operand that has structure or union type, the result is the total number of bytes in such an object, including internal and trailing padding.

q_insert_tail

  • 從 queue 的尾端新增一個元素
  • 成功return true
  • 若 queue 為 NULL 或分配位置失敗時則 return false
  • 時間複雜度須為 \(O(1)\) ，即不論 queue 的長度為何執行時間，操作步驟為固定數量。
bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(sizeof(char)*(strlen(s) + 1))
        free(newh);
        return false;
    }
    snprintf(newh->value, strlen(s) + 1, "%s", s);
    newh->next = NULL;
    q->size++;
    if (!q->tail) {
        q->head = newh;
        q->tail = newh;
        return true;
    }
    q->tail->next = newh;
    q->tail = newh;
    return true;
}

在 queue 為空時需要另外將 head 也指向新增的元素

q_remove_head

  • 將 queue head 刪除
  • 成功刪除 return true
  • 當 queue 為空或 NULL 時 return false
  • 若 sp 不是 NULL 且 remove 執行成功時要將被 remove 的元素值的前bufsize - 1 位放進 sp 中，並且 sp 的最後一位須為 null terminator。
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if(!q || !q->head)
        return false;
    list_ele_t *tmp;
    tmp = q->head;
    if (sp) {
        snprintf(sp, bufsize, "%s", tmp->value);
    }
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

在將被 remove 值放進 sp 中，要求要取被 remove 的元素值前 bufsize - 1 位，在 insert 時用到的 snprintf，剛好就可以拿來使用。

q_reverse

  • 將 queue 的內容反轉
  • queue 為 NULL 或 empty 時直接結束
  • 不能 allocate 新的記憶體位址和 free 原有的記憶體位址
void q_reverse(queue_t *q)
{
    if (!q)
        return;
    if (q->size <= 1)
        return;
    list_ele_t *tmp;
    q->tail->next = q->head;
    while (q->head->next != q->tail) {
        tmp = q->head->next;
        q->head->next = tmp->next;
        tmp->next = q->tail->next;
        q->tail->next = tmp;
    }
    q->tail = q->head;
    q->head = q->head->next;
    q->tail->next = NULL;
}

除了 queue 為 NULL 和 empty 時，q->size 為 1 時也可以直接結束。
一開始的想法是用拆一個接一個的方式從 q->head 依序將元素拆掉並重新反向接上，在接完之後需要另外將 q->tail 歸位。
後來想到先把 q->tail 接到 q->head 上，並依序將 q->head 到 q->tail 之間的元素接到 q->tail 後面，最後只須將q-tail 和 q->head 互換位置，再將q->tail->next 接到 NULL 即可，示意圖如下。

digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> a :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> a;
    tail [shape=box];
    tail -> c;
}

digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    a:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> b :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> a;
    tail [shape=box];
    tail -> c;
}

digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    a:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> b :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> c;
    tail [shape=box];
    tail -> a;
}

q_sort

  • 將 queue 中元素小到大做排序
  • 使用 natual sort (未完成)
void q_sort(queue_t *q)
{
    if (!q)
        return;
    if (q->size <= 1)
        return;
    merge_sort(&(q->head));
    while (q->tail->next)
        q->tail = q->tail->next;
}
sort.c
#include <stdio.h>
#include <string.h>

#include "queue.h"

void split(list_ele_t *source, list_ele_t **pre_head, list_ele_t **post_head)
{
    list_ele_t *fast, *slow;
    fast = source->next;
    slow = source;
    while (fast) {
        fast = fast->next;
        if (fast) {
            fast = fast->next;
            slow = slow->next;
        }
    }
    *pre_head = source;
    *post_head = slow->next;
    slow->next = NULL;
}

list_ele_t *merge(list_ele_t *pre_head, list_ele_t *post_head)
{
    list_ele_t *start, *current;
    start = pre_head;
    pre_head = pre_head->next;
    current = start;
    while (pre_head && post_head) {
        if (strcmp(pre_head->value, post_head->value) > 0) {
            current->next = post_head;
            post_head = post_head->next;
        } else {
            current->next = pre_head;
            pre_head = pre_head->next;
        }
        current = current->next;
    }
    if (pre_head)
        current->next = pre_head;
    else if (post_head)
        current->next = post_head;
    return start;
}

void merge_sort(list_ele_t **head)
{
    list_ele_t *pre_head, *post_head;
    if (!(*head))
        return;
    if (!(*head)->next)
        return;
    split(*head, &pre_head, &post_head);
    merge_sort(&pre_head);
    merge_sort(&post_head);
    if (strcmp(pre_head->value, post_head->value) <= 0) {
        *head = merge(pre_head, post_head);
    } else {
        *head = merge(post_head, pre_head);
    }
}

採用 merge sort 進行排序，即使在 worst case，merge sort 也是 \(O(nlog{n})\) 的時間複雜度。實作的部份參考 Linked List Sort

TODO:

  1. 在 merge 和 merge_sort 這二個函式都呼叫到 strcmp，也就是 comparator，倘若想更換後者為其他函式 (或傳遞函式指標)，那就需要在這兩個函式內容變更，不僅不便利，還會隱藏風險;
  2. split 函式通用性不足，可改為巨集或 inline function 實作;
  3. 考慮到 merge_sort 函式原型宣告的變更: 
    ​​​​static list_ele_t *merge_sort(list_ele_t *head);
    輸入原本的 head，回傳因為排序而得到新的 head，在實作和使用上都會更便利;

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 a repo