2020q1 Homework1 (lab0)

contributed by < pingsutw >

開發環境

$ uname -a
Linux kevin 5.0.0-38-generic #41-Ubuntu SMP Tue Dec 3 00:27:35 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 8.3.0-6ubuntu1) 8.3.0

$ lsb_release -a
No LSB modules are available.
Distributor ID:	Ubuntu
Description:	Ubuntu 19.04
Release:	19.04
Codename:	disco

$ 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:               60
Model name:          Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
Stepping:            3
CPU MHz:             1527.846
CPU max MHz:         3600.0000
CPU min MHz:         800.0000
BogoMIPS:            5188.08
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
NUMA node0 CPU(s):   0-7

作業要求

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
• q_size: 計算佇列中的元素數量。
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
• q_sort: 「Linux 核心設計」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法;

開發過程

queue_t

• 因為 q_insert_tail 和 q_size 需要將原本
  $O(n)$ 時間複雜度的實作改寫為
  $O(1)$ 時間複雜度，所以加了 *tail 和 qsize 來紀錄最後一個節點和 queue 大小

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

q_new

• 回傳一個空的 queue_t, 如果 malloc 失敗回傳 NULL

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->qsize = 0;
    return q;
}

q_free

• 當 queue_t 為 NULL 時直接 return，當 queue_t 不為 NULL 時，依序拜訪個節點並釋放記憶體空間

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

q_insert_head

• queue_t 為 NULL 時，直接 return false
• queue_t 不為 NULL 時, 先 malloc 記憶體空間給 list_ele_t 還有 list_ele_t->value，如果失敗 return false，如果成功再將字串寫到節點裡，注意字串最後一個字元需為 \0 表示字串結束
• 新節點指向 queue head

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    newh->value = (char *) malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    strncpy(newh->value, s, strlen(s));
    (newh->value)[strlen(s)] = '\0';
    newh->next = q->head;

    q->head = newh;
    (q->qsize)++;
    if (q->qsize == 1)
        q->tail = newh;
    return true;
}

q_insert_tail

• queue_t 為 NULL 時，直接 return false
• queue_t 不為 NULL 時, 先 malloc 記憶體空間給 list_ele_t 還有
  list_ele_t->value，如果失敗 return false，如果成功再將字串寫到節點裡，注意字串最後一個字元需為 \0 表示字串結束
• queue tail 指向新節點
• 必須使用 strncpy 而不是 strcpy, 因為 strcpy 沒有限制字串寫入 buffer 的大小，可能因為程式疏失，而導制記憶體使用過量

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    newh->value = (char *) malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    strncpy(newh->value, s, strlen(s));
    (newh->value)[strlen(s)] = '\0';
    newh->next = NULL;

    if (q->tail != NULL)
        q->tail->next = newh;
    q->tail = newh;
    (q->qsize)++;

    if (q->qsize == 1)
        q->head = q->tail;

    return true;
}

q_remove_head

• 當 queue 為 NULL 或 queue size 為 0 時，return 0
• 當 queue 不為 NULL，複製自傳到 buffer，buffer 的最後一個字元需為 \0 代表字串結束

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->qsize == 0)
        return false;
    if (sp != NULL) {
        memset(sp, '\0', bufsize);
        strncpy(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *prev = q->head;
    q->head = q->head->next;

    free(prev->value);
    free(prev);
    (q->qsize)--;
    return true;
}

q_size

queue_t 的大小已經紀錄在 queue_t 裡面可以直接取得，如果 queue_t 為空時 return 0.

int q_size(queue_t *q)
{
    if (q != NULL)
        return q->qsize;
    return 0;
}

q_reverse

• 當 queue 為 NULL 或 queue size 為 0 時，直接 return
• 建立三個指標分別指向當前節點, 前一個節點，下一個節點，依序拜訪各界點，再將當前節點指向前一個節點

void q_reverse(queue_t *q)
{
    if (q == NULL || q->qsize == 0)
        return;

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

• step 1 next = cur->next;

• step 2 cur->next = prev;

• step 3 prev = cur;

• step 4 cur = next;

q_sort

• 對 queue 中的元素進行排序
• 需用 merge sort，滿足時間複雜度
  $O(nlogn)$
• 遞迴的方式先將 queue 分兩半，在進行合併

void q_sort(queue_t *q)
{
    if (!q || q->qsize < 2)
        return;

    queue_t left, right;
    left.qsize = q->qsize / 2 + (q->qsize & 1);
    right.qsize = q->qsize / 2;

    list_ele_t *cur = left.head = q->head;
    right.tail = q->tail;

    for (int i = 0; i < left.qsize - 1; i++)
        cur = cur->next;

    left.tail = cur;
    right.head = cur->next;
    left.tail->next = right.tail->next = NULL;
    q->head = q->tail = NULL;

    q_sort(&left);
    q_sort(&right);
    merge(&left, &right, q);
}

is_less_then

• 比較兩個字串的大小
• 需判斷字串為空的狀態

//  compares two strings character by character.
static bool is_less_then(list_ele_t *x, list_ele_t *y)
{
    if (!x)
        return true;
    if (!y)
        return false;

    if (strcmp(x->value, y->value) < 0)
        return true;
    else
        return false;
}

merge

• 對兩個 queue 進行合併

queue_t *merge(queue_t *left, queue_t *right, queue_t *q)
{
    q->qsize = left->qsize + right->qsize;
    list_ele_t *l = left->head, *r = right->head;
    list_ele_t *tmp = NULL;

    if (is_less_then(left->head, right->head))
        q->head = left->head;
    else
        q->head = right->head;

    q->tail = q->head;
    for (int i = 0; i < q->qsize; i++) {
        if (!r || (l && is_less_then(l, r))) {
            tmp = l;
            l = l->next;
        } else {
            tmp = r;
            r = r->next;
        }
        q->tail->next = tmp;
        q->tail = tmp;
    }
    tmp->next = NULL;
    return q;
}

Pull Request

• 為了讓輸出更醒目，提了一個 pr，成功會顯示綠色，失敗會顯示紅色
  
  

參考資料

• Linux 核心設計: 線上/實體課程說明 (2020 年春季)
• H01: lab0
• Makefile 語法和示範
• 你所不知道的C語言: linked list 和非連續記憶體操作
• What is size_t in C?
• 深入理解c语言——‘\0’ ，‘0’， “0” ，0之间的区别
• Linked List Sort
• Common vulnerabilities guide for C programmers
• Is the function strcpy always dangerous?
• C99 規格書

tags: sysprog2020