2020q1 Homework 1 (lab0)

contributed by < hankchang805 >

tags : linux2020

開發紀錄

queue.h

queue_t

為了讓 q_insert_tail 以及 q_size 可以在

$O(1)$ 的時間複雜度內完成，所以增加 tail (指向 queue 中最後一個元素)以及 size （紀錄目前 queue 有幾個元素)

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

queue.c

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

void q_free(queue_t *q)
{
    if (!q)
        return;
    while (q->head) {
        list_ele_t *ptr = q->head;
        q->head = q->head->next;
        free(ptr->value);
        free(ptr);
    }

    free(q);
}

q_insert_head

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;
    char *in = malloc(sizeof(char) * (strlen(s) + 1));
    if (!in) {
        free(newh);
        return false;
    }
    int len = strlen(s);
    strncpy(in, s, len);
    in[len] = '\0';
    newh->value = in;
    newh->next = q->head;
    q->head = newh;
    if (!q->tail) {
        q->tail = q->head;
    }
    q->size = q->size + 1;
    return true;
}

q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    if (!q)
        return false;
    newt = malloc(sizeof(list_ele_t));
    if (!newt)
        return false;
    char *in = malloc((strlen(s) + 1) * sizeof(char));
    if (!in) {
        free(newt);
        return false;
    }
    int len = strlen(s);
    strncpy(in, s, len);
    in[len] = '\0';
    newt->value = in;
    newt->next = NULL;
    if (!q->tail) {
        q->head = q->tail = newt;
        q->size = q->size + 1;
        return true;
    }
    q->tail->next = newt;
    q->tail = newt;
    q->size = q->size + 1;
    return true;
}

q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;
    if (sp) {
        strncpy(sp, q->head->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *ptr = q->head;
    q->head = q->head->next;
    q->size = q->size - 1;
    free(ptr->value);
    free(ptr);
    return true;
}

q_size

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

q_reverse

void q_reverse(queue_t *q)
{
    if (!q)
        return;
    list_ele_t *temp = q->head;
    list_ele_t *middle = NULL;
    list_ele_t *last = NULL;
    while (temp) {
        last = middle;
        middle = temp;
        temp = temp->next;
        middle->next = last;
    }
    temp = q->head;
    q->head = q->tail;
    q->tail = temp;
}

q_sort

這邊是採用 MergeSort 的方式進行排序，q_sort 將 list 分成兩段，如果 list 大小是 2 的倍數則分成剛好

$size/2$，若不為 2 的倍數則左半將會切成

$\lceil size/2\rceil$，再將左右分別遞迴下去切直到遇到 Base Case ；接著執行 q_merge 將左右兩半排好

void q_sort(queue_t *q)
{
    if (!q || q->size < 2)
        return;
    queue_t left;
    queue_t right;
    left.head = q->head;
    right.tail = q->tail;
    left.size = (q->size >> 1) + (q->size & 1);
    right.size = (q->size >> 1);
    list_ele_t *ptr = q->head;
    for (int i = 0; i < left.size - 1; i++) {
        ptr = ptr->next;
    }
    left.tail = ptr;
    right.head = ptr->next;
    left.tail->next = NULL;
    q->tail = q->head = NULL;
    q_sort(&left);
    q_sort(&right);
    q_merge(&left, &right, q);
}

• q_merge

void q_merge(queue_t *left, queue_t *right, queue_t *q)
{
    list_ele_t *l = left->head;
    list_ele_t *r = right->head;
    if (less_than(l, r)) {
        q->head = l;
        l = l->next;
    } else {
        q->head = r;
        r = r->next;
    }
    q->tail = q->head;
    list_ele_t *cur = NULL;
    while (l && r) {
        if (less_than(l, r)) {
            cur = l;
            l = l->next;
        } else {
            cur = r;
            r = r->next;
        }
        q->tail->next = cur;
        q->tail = cur;
    }
    while (l) {
        q->tail->next = l;
        q->tail = l;
        l = l->next;
    }
    while (r) {
        q->tail->next = r;
        q->tail = r;
        r = r->next;
    }
}

• less_than

比較 list_ele_t 的字典序

bool less_than(list_ele_t *l, list_ele_t *r)
{
    char *str_l = l->value;
    char *str_r = r->value;
    while (*str_l && *str_r) {
        if (*str_l > *str_r)
            return false;
        else if (*str_l++ < *str_r++)
            return true;
    }
    if (!*str_l && *str_r)
        return true;
    return false;
}

Valgrind 和 Massif 工具的使用

Valgrind

利用 make valgrind 來查看是否有 Memory leak …等記憶體錯誤發生，此階段並沒有發生什麼記憶體失誤

利用 Massif 查看記憶體的使用

用 valfrind --tool=massif ./qtest 來執行 Massif 工具的分析
實驗的方式如下：

./qtest
(qtest)new
(qtest)ih RAND 10
(qtest)reverse
(qtest)sort
(qtest)rh
....10 times
(qtest)quit

再利用 massif-visualizer [massif_output_file] 來把實驗結果輸出成以下圖表

可以看見一開始直線上升，應該是在執行 insert head ，後面一段雖在下降但是稍微平緩一點，應該是在執行 reverse 跟 sort ，之後開始較劇烈下降是在執行 rh 直到結束之後記憶體用量就將至0

(後續想再設計不同的方式去追蹤記憶體的使用)

TODO

研讀論文

Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理;

select 系統呼叫

解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示

為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)

Reference

colinyoyo26

AndybnACT

Valgrind massif manual