2022q1 Homework1 (lab0)

contributed by < extrovert7986 >

實驗環境

$ 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:                   43 bits physical, 48 bits virtual
CPU(s):                          16
On-line CPU(s) list:             0-15
Thread(s) per core:              2
Core(s) per socket:              8
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      23
Model:                           113
Model name:                      AMD Ryzen 7 3800X 8-Core Processor
Stepping:                        0
Frequency boost:                 enabled
CPU MHz:                         2200.000
CPU max MHz:                     4558.8862
CPU min MHz:                     2200.0000
BogoMIPS:                        7785.69
Virtualization:                  AMD-V
L1d cache:                       256 KiB
L1i cache:                       256 KiB
L2 cache:                        4 MiB
L3 cache:                        32 MiB
NUMA node0 CPU(s):               0-15

q_new

依據 list.h 定義

For an empty list,
both member variables point to the head.

可以得知 empty list 應該為一個 prev 與 next 都指向自己的東西

請用正式的術語，避免說「東西」。考慮到日後參加科技公司面試，你現在所紀錄的內容，可能就會在日後出現，現在就養成說專業術語的習慣。

jserv

Update:
可以得知 empty list 應該為一個prev 與 next 都指向自己的串列

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));

    if (q) {
        q->prev = q;
        q->next = q;
    }
    return q;
}

q_free

void q_free(struct list_head *l)
{
    l->prev->next = NULL;
    while (l) {
        struct list_head *tmp = l;
        l = l->next;
        free(tmp);
    }
}

上述的程式碼並為成功釋放 element_t 裡面字串的記憶體
更新為以下的形式

void q_free(struct list_head *l)
{
    struct list_head *cur;
    l->prev->next = NULL;

    for (cur = l->next; cur;) {
        element_t *tmp = list_entry(cur, element_t, list);
        cur = cur->next;
        if (tmp->value)
            free(tmp->value);
        free(tmp);
    }

    free(l);
}

2/26 Update: 需要判斷 l pointer 是否為 NULL

void q_free(struct list_head *l)
{
    struct list_head *cur;
+
+    if (!l)
+        return;
    l->prev->next = NULL;

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *ele = malloc(sizeof(element_t));
    size_t bufSiz = sizeof(char) * (strlen(s) + 1);

    if (!ele)
        return false;

    if (!(ele->value = malloc(bufSiz))) {
        free(ele);
        return false;
    }

    ele->value = strncpy(ele->value, s, bufSiz);

    list_add(&ele->list, head);

    return true;
}

開發過程中, 發現自己把 ele 加入 head 中（14 ~ 17）, 會導致 Memory leak 如下

Following files need to be cleaned up:
queue.c
queue.c:62:5: error: Memory leak: ele [memleak]
    return true;
    ^

Fail to pass static analysis.

但如果使用 list_add function, 就不會出現問題, 推測應該是 static analysis 的問題, 檢查 cppcheck 版本為 1.90 沒有問題, 暫時將程式碼改為以下形式
Original：

ele->list.prev = head;
ele->list.next = head->next;
head->next->prev = &(ele->list);
head->next = &(ele->list);

Updated：

list_add(&ele->list, head);

TODO: 查閱 Cppcheck 手冊，使用其 suppression 標注。

jserv

2/26 Update: 加入判斷確認 head 與 ele 是否為 NULL

bool q_insert_head(struct list_head *head, char *s)
{
+    if (!head)
+        return false;
+
    element_t *ele = e_new(s);

+    if (!ele)
+        return false;
+
    list_add(&ele->list, head);

q_insert_tail

由於 q_insert_tail 中 new element 的動作可以與 q_insert_head 中共用, 所以將該部份的 code 抽出共用

static inline element_t *e_new(char *s)
{
    element_t *ele = malloc(sizeof(element_t));
    size_t bufSiz = sizeof(char) * (strlen(s) + 1);

    if (!ele)
        return NULL;

    if (!(ele->value = malloc(bufSiz))) {
        free(ele);
        return NULL;
    }

    ele->value = strncpy(ele->value, s, bufSiz);
    return ele;
}

並且更改 q_insert_head 如下

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *ele = e_new(s);

    list_add(&ele->list, head);

    return true;
}

q_insert_tail 實做如下

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *ele = e_new(s);

    list_add_tail(&ele->list, head);

    return true;
}

2/26 Update: 加入判斷確認 head 與 ele 是否為 NULL

bool q_insert_tail(struct list_head *head, char *s)
{
+    if (!head)
+        return false;
+
    element_t *ele = e_new(s);

+    if (!ele)
+        return false;
+
    list_add_tail(&ele->list, head);

q_remove_head 與 q_remove_tail

這兩個 function 分別用來移除(remove)串列中的第一與最後一個節點,
移除時, 並不釋放目標節點的記憶體位置,
以下 2 段程式碼分別對串列開頭(head->next)與結尾(head->prev)節點進行移除相關的動作

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head)
        return NULL;

    element_t *tar = list_first_entry(head, element_t, list);

    head->next = tar->list.next;
    tar->list.next->prev = head;

    if (sp && bufsize > 0) {
        strncpy(sp, tar->value, bufsize - 1);
    }
    return tar;
}

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

    element_t *tar = list_last_entry(head, element_t, list);

    head->prev = tar->list.prev;
    tar->list.prev->next = head;

    if (sp && bufsize > 0) {
        strncpy(sp, tar->value, bufsize - 1);
    }

    return tar;
}

2/26 Update: 根據 manual, strncpy 不會幫忙寫入最後一個 byte 的 '\0', 需要由使用者補上

    if (sp && bufsize > 0) {
        strncpy(sp, tar->value, bufsize - 1);
+        sp[bufsize - 1] = '\0';
    }

q_delete_mid

q_delete_mid 暫時實做如下, 透過 Floyd’s Cycle Detection Algorithm 找出佇列的中心點並且 remove

「中心點」這詞不精準，需要定義

jserv

2/27 Update: 此處中心點的定義如下
在不包含 head ,長度為 n 的佇列中, 佇列中的第一個 element_t index 為 0, 最後一個 element_t index 為 n-1 的情況下, 中心點為第

$\lfloor n/2\rfloor$ 個 node

bool q_delete_mid(struct list_head *head)
{
    struct list_head **slow, **fast;

    if (!head)
        return false;

    for (slow = fast = &head; (*fast) && (*fast)->next;
         slow = &((*slow)->next), fast = &((*fast)->next->next))
        ;

    *slow = (*slow)->next;
    return true;
}

原本的作法為 remove 並非 delete
改為以下 delete 作法

bool q_delete_mid(struct list_head *head)
{
    element_t *tar;
    struct list_head **slow, **fast;

    if (!head)
        return false;

    for (slow = fast = &(head->next); (*fast) != head && (*fast)->next != head;
         slow = &((*slow)->next), fast = &((*fast)->next->next))
        ;

    tar = list_entry(&(**slow), element_t, list);
    tar->list.prev->next = tar->list.next;
    tar->list.next->prev = tar->list.prev;

    if (tar->value)
        free(tar->value);
    free(tar);
    return true;
}

q_reverse

將每一個 node 的 next 與 prev 交換即可

void q_reverse(struct list_head *head)
{
    if (!head || head->next == head) {
        return;
    }

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

q_swap

void q_swap(struct list_head *head)
{
    struct list_head *fir, *sec;
    for (fir = head->next, sec = fir->next; fir != head && sec != head;
         fir->prev->next = sec, sec->next->prev = fir, fir->next = sec->next,
        sec->prev = fir->prev, fir->prev = sec, sec->next = fir,
        fir = fir->next, sec = fir->next)
        ;
}

以 for_each 相關巨集改寫上述程式碼。

jserv

2/28 Update:

void q_swap(struct list_head *head)
{
     struct list_head *fir, *sec;
-    for (fir = head->next, sec = fir->next; fir != head && sec != head;
-         fir->prev->next = sec, sec->next->prev = fir, fir->next = sec->next,
-        sec->prev = fir->prev, fir->prev = sec, sec->next = fir,
-        fir = fir->next, sec = fir->next)
-        ;
+
+    list_for_each (fir, head) {
+        sec = fir->next;
+        if (sec == head)
+            return;
+        fir->prev->next = sec;
+        sec->next->prev = fir;
+        fir->next = sec->next;
+        sec->prev = fir->prev;
+        fir->prev = sec;
+        sec->next = fir;
+    }
}

q_sort

透過 merge sort 將佇列進行排序

1. 此處實作的 merge sort 可以讓使用者丟入不包含 head 的剩餘佇列並且進行排序

/**
 * sort list_head without include the first member
 */
struct list_head *q_merge_sort(struct list_head *head)
{
    struct list_head *fir, *sec;

    if (!head || !head->next)
        return head;

    fir = head;
    sec = q_devide(fir);

    fir = q_merge_sort(fir);
    sec = q_merge_sort(sec);

    return q_merge(fir, sec);
}

2. devide 函式將會從長度為 n 的 list 中找出 index 為
   $\lceil n/2\rceil$(起始 element_t index = 0 的情況下) 的結點, 作為第二個節點的開頭, 並斷開前後 2 個佇列(將第一個佇列的最後一個 element_t 的 next 改為 NULL)

struct list_head *q_devide(struct list_head *head)
{
    struct list_head **slow, **fast, *retVal;

    for (slow = fast = &(head); *fast && (*fast)->next;
         slow = &((*slow)->next), fast = &((*fast)->next->next))
        ;
    retVal = *slow;
    *slow = NULL;

    return retVal;
}

透過以下的 merge 函式將切開來的 2 個 list 排序並且 merge 回來

struct list_head *q_merge(struct list_head *l1, struct list_head *l2)
{
    struct list_head *indirect, head;

    indirect = &head;

    while (l1 && l2) {
        if (strcmp(list_val(l1), list_val(l2)) < 0) {
            indirect->next = l1;
            l1 = l1->next;
        } else {
            indirect->next = l2;
            l2 = l2->next;
        }
        indirect = indirect->next;
    }
    indirect->next =
        (struct list_head *) ((unsigned long int) l1 | (unsigned long int) l2);

    return head.next;
}

主要被 qtest 呼叫的 function
首先將最後一個 node 與 head 切開
然後在 sort 完之後, 將所有 node 的 prev link 回來外
處理最後一個 node 與 head 之間的 link

void q_sort(struct list_head *head)
{
    struct list_head *last;

    if (!head || head->next == head || head->next->next == head)
        return;

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

    for (last = head; last->next; last = last->next) {
        last->next->prev = last;
    }
    head->prev = last;
    last->next = head;
}

q_delete_dup

此 function 目前的演算法如下

FOR each node exclude head
    WHILE node equals to its next one
        delete next node
        isRemove = true
    IF isRemove
        delete current node

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;

    for (struct list_head *cur = head->next; cur && cur != head;) {
        bool isRemove = false;
        while (cur->next != head &&
               !strcmp(list_val(cur), list_val(cur->next))) {
            isRemove = true;
            cur->next = cur->next->next;
            q_delete_node(cur->next->prev);
        }
        if (isRemove) {
            struct list_head *tmp = cur;
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            cur = cur->next;
            q_delete_node(tmp);
        } else {
            cur = cur->next;
        }
    }
    return true;
}