2022q1 Homework1 (lab0)

contributed by < ChenBoSyun >

實驗環境

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

$ lscpu

架構：                           x86_64
CPU 作業模式：                   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
每核心執行緒數：                 1
每通訊端核心數：                 8
Socket(s):                       1
NUMA 節點：                      1
供應商識別號：                   GenuineIntel
CPU 家族：                       6
型號：                           158
Model name:                      Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
製程：                           13
CPU MHz：                        3000.000
CPU max MHz:                     4700.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6000.00
虛擬：                           VT-x
L1d 快取：                       256 KiB
L1i 快取：                       256 KiB
L2 快取：                        2 MiB
L3 快取：                        12 MiB
NUMA node0 CPU(s)：              0-7

實作佇列操作

q_new

• q_new 初始化一個空的佇列，並且配置一段 struct list_head 的空間。此外，q_new 回傳的 struct list_head* 只是 linked list 的進入點，因此不需要配置 element 空間

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

q_free

• 為了遍歷 linked list，我先用 tmp 暫存 node，直到 node 指到下一個 node，才釋放 tmp node
• 參考同學的課堂問答，改成用 list API 來實作
• 從 C99 規格書上確認 free(NULL) 不會有問題

  The free function causes the space pointed to by ptr to be deallocated, that is, made available for further allocation. If ptr is a null pointer, no action occurs. - ISO/IEC 9899:1999 7.20.3.1

原先的版本

void q_free(struct list_head *l)
{
    if (!l)
        return;

    struct list_head *node = l->next;
    while (node != l) {
        struct list_head *tmp = node;
        node = node->next;
        element_t *ele = list_entry(tmp, element_t, list);
        free(ele->value);
        free(ele);
    }
    free(l);

    return;
}

使用 list API

void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *ele = NULL, *safe = NULL;
    list_for_each_entry_safe(ele, safe, l, list) {
        free(ele->value);
        free(ele);
    }
    free(l);
    
    return;
}

q_insert_head

• 若是配置字串的記憶體失敗，要記得把 element 也釋放掉
• strcpy 有潛在的 overflow 問題，這邊使用 strncpy。
• strlen 回傳字串本身的長度，還需要加上 null terminator ('\0')

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_ele = (element_t *) malloc(sizeof(element_t));
    if (!new_ele)
        return false;

    new_ele->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
    if (!new_ele->value) {
        free(new_ele);
        return false;
    }

    strncpy(new_ele->value, s, strlen(s) + 1);
    list_add(&new_ele->list, head);

    return true;
}

q_insert_tail

• 步驟與 q_insert_head 幾乎相同，只差在最後呼叫 list_add_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_ele = (element_t *) malloc(sizeof(element_t));
    if (!new_ele)
        return false;

    new_ele->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
    if (!new_ele->value) {
        free(new_ele);
        return false;
    }

    strncpy(new_ele->value, s, strlen(s) + 1);
    list_add_tail(&new_ele->list, head);

    return true;
}

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 *ele = list_first_entry(head, element_t, list);
    if (sp) {
        if (strlen(ele->value) + 1 <= bufsize)
            strncpy(sp, ele->value, strlen(ele->value) + 1);
        else {
            strncpy(sp, ele->value, bufsize - 1);
            *(sp + bufsize - 1) = '\0';
        }
    }
    list_del(&ele->list);
    return ele;
}

q_remove_tail

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ele = list_last_entry(head, element_t, list);
    if (sp) {
        if (strlen(ele->value) + 1 <= bufsize)
            strncpy(sp, ele->value, strlen(ele->value) + 1);
        else {
            strncpy(sp, ele->value, bufsize - 1);
            *(sp + bufsize - 1) = '\0';
        }
    }
    list_del(&ele->list);
    return ele;
}

q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

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

q_delete_mid

• 用 fast 走兩步，slow 走一步的方式找到中間點

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *fast = head->next, *slow = head->next;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }
    list_del(slow);
    element_t *ele = list_entry(slow, element_t, list);
    free(ele->value);
    free(ele);

    return true;
}

q_delete_dup

• q_delete_dup 有指明是在 sort 後呼叫，因此只要檢查 prev 跟 curr 是否相同

原先下述的程式碼可以通過 qtest，但是 fetch lab0-c 後，無法通過 qtest
從 ＠kdnvt 同學提交的 commit 得知，我誤會了 q_delete_dup 的意思，應該要把所有 duplicate 的字串都刪除，而且剛好原先的 qtest 沒有檢查到

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 *prev = head->next, *curr = head->next->next;
    while (curr != head) {
        element_t *ele_prev = list_entry(prev, element_t, list);
        element_t *ele_curr = list_entry(curr, element_t, list);

        if (strcmp(ele_prev->value, ele_curr->value) == 0) {
            list_del(prev);
            free(ele_prev->value);
            free(ele_prev);
        }
        prev = curr;
        curr = curr->next;
    }

    return true;
}

正確的 q_delete_dup

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 *prev = head->next, *curr = head->next->next;
    bool is_dup = false;
    while (curr != head) {
        element_t *ele_prev = list_entry(prev, element_t, list);
        element_t *ele_curr = list_entry(curr, element_t, list);

        if (!strcmp(ele_prev->value, ele_curr->value)) {
            is_dup = true;
            list_del(prev);
            free(ele_prev->value);
            free(ele_prev);
        } else if (is_dup) {
            is_dup = false;
            list_del(prev);
            free(ele_prev->value);
            free(ele_prev);
        }
        if (is_dup && curr->next == head) {
            list_del(curr);
            free(ele_curr->value);
            free(ele_curr);
            break;
        }
        prev = curr;
        curr = curr->next;
    }

    return true;
}

q_swap

• 實作的想法是: 在 node 為奇數時，移除 node->next，再把 node->next 接到 node 前面
• 迴圈結束條件需要加上 node->next != head，避免遇到奇數個 node 的情況

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node = head->next;
    while (node != head && node->next != head) {
        struct list_head *next = node->next;
        list_del(next);
        list_add_tail(next, node);
        node = node->next;
    }
}

q_reverse

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *curr = head, *prev;
    do {
        prev = curr->prev;
        curr->prev = curr->next;
        curr->next = prev;
        curr = curr->prev;
    } while (curr != head);
}

q_sort

• 首先為了判斷佇列的結尾，我將原本的 circular linked list 改成 Singly linked list
• 我採用遞迴方式的 merge sort 來實作 q_sort，分成三個部份
  1. merge_list: 合併兩個排序過的佇列，這部份有用到"指標的指標"技巧，不需要額外判斷是否為 linked list 開頭
  2. mergesort: 遞迴的主體
  3. q_sort: 呼叫 mergesort，最後要把 prev 接回去

static struct list_head *merge_list(struct list_head *l1, struct list_head *l2)
{
    struct list_head **head_ptr, *head = NULL;
    head_ptr = &head;

    while (l1 && l2) {
        element_t *ele_1 = list_entry(l1, element_t, list);
        element_t *ele_2 = list_entry(l2, element_t, list);
        if (strcmp(ele_1->value, ele_2->value) < 0) {
            *head_ptr = l1;
            l1 = l1->next;
        } else {
            *head_ptr = l2;
            l2 = l2->next;
        }
        head_ptr = &(*head_ptr)->next;
    }
    *head_ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
    return head;
}

static struct list_head *mergesort(struct list_head *head)
{
    if (!head || !head->next) {
        return head;
    }

    struct list_head *fast = head->next, *slow = head;
    struct list_head *l1, *l2;


    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    fast = slow->next;
    slow->next = NULL;

    l1 = mergesort(head);
    l2 = mergesort(fast);
    return merge_list(l1, l2);
}

/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    head->prev->next = NULL;
    head->next = mergesort(head->next);

    struct list_head *curr = head->next, *prev = head;
    while (curr) {
        curr->prev = prev;
        curr = curr->next;
        prev = prev->next;
    }
    prev->next = head;
    head->prev = prev;
}