2022q1 Homework1 (lab0)

contributed by < Tcc0403 >

實驗環境

$ 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:                   48 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      25
Model:                           33
Model name:                      AMD Ryzen 5 5600X 6-Core Processor
Stepping:                        0
Frequency boost:                 enabled
CPU MHz:                         2200.000
CPU max MHz:                     4650.2920
CPU min MHz:                     2200.0000
BogoMIPS:                        7385.57
Virtualization:                  AMD-V
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        3 MiB
L3 cache:                        32 MiB
NUMA node0 CPU(s):               0-11

針對佇列的操作

q_new

為佇列建立 list_head 結構體後，透過 INIT_LIST_HEAD 為其初始化

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

q_free

利用 list_for_each_entry_safe 走訪每個 element_t ，呼叫 q_relase_element 函式釋放空間

void q_free(struct list_head *l)
{
    if (l == NULL)
        return;
    element_t *e, *s;
    list_for_each_entry_safe (e, s, l, list) {
        q_release_element(e);
    }
    free(l);
}

q_insert_head

課程文章中題的到 Head 跟 q_insert_head 的 head 是不一樣的東西，這裡所指的是圖片所標記的 Node 0 ，也就是 head->next

建立 element_t 結構體 new ，利用 strdup 儲存字串內容，接著將 element_t 結構體中包含的 list_head 結構體作為參數傳入list_add 函式，使其加入佇列

bool q_insert_head(struct list_head *head, char *s)
{
    if(head == NULL)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if(new == NULL)
        return false;
    new->value = strdup(s);
    if(new->value == NULL){
        q_release_element(new);
        return false;
    }        
    list_add(&(new->list), head);
    return true;
}

目前無法通過 pre-commit 的靜態分析，顯示第 60 行出錯

$ git commit
queue.c:60:5: error: Memory leak: new [memleak]
    return true;
    ^

把 &(new->list) 改成 &new->list 就通過了

bool q_insert_head(struct list_head *head, char *s)
{
    if (head == NULL)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (new == NULL)
        return false;
    new->value = strdup(s);
    if (new->value == NULL) {
        free(new);
        return false;
    }
    list_add(&new->list, head);
    return true;
}

q_insert_tail

與上面操作類似，差別在 list_add 改成 list_add_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL)
        return false;
    element_t *new = malloc(sizeof(element_t));
    if (new == NULL)
        return false;
    new->value = strdup(s);
    if (new->value == NULL) {
        free(new);
        return false;
    }
    list_add_tail(&new->list, head);
    return true;
}

q_remove_head

利用 list_del_init 將第一項 element_t 結構體移出佇列

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;
    element_t *ele = list_entry(head->next, element_t, list);
    list_del_init(&ele->list);
    if (sp != NULL) {
        strncpy(sp, ele->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    return ele;
}

使用 list_del_init 而非 list_del 的原因，是擔心未來對回傳的 element_t 結構體做額外操作，導致錯誤發生

時間複雜度測試沒過，待研究
發現 eric88525 筆記 有類似情況，自己上傳後在 GitHub Actions 中也有通過

q_remove_tail

跟上方作法類似

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;
    element_t *ele = list_entry(head->prev, element_t, list);
    list_del_init(&ele->list);
    if (sp != NULL) {
        strncpy(sp, ele->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    return ele;
}

同上

q_size

利用 list_for_each 走訪每個節點

int q_size(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return 0;
    int count = 0;
    struct list_head *n;
    list_for_each (n, head) {
        count++;
    }
    return count;
}

原本以為 list_for_each 會走到 head 本身，但仔細看才發現是從 head->next 開始

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

q_delete_mid

利用環狀雙向鏈結串列的特性，透過兩個指標反向走訪串列，一個向前、一個向後，當兩個指標相遇或相鄰時， 向前走的指標所指向的節點即是中間節點

bool q_delete_mid(struct list_head *head)
{
    if(head == NULL || list_empty(head))
        return false;
    struct list_head *forward, *backward;
    forward = head->next;
    backward = head->prev;
    while(forward != backward && forward->next != backward)
    {
        forward = forward->next;
        backward = backward->prev;
    } 
    list_del(forward);
    q_release_element(list_entry(forward, element_t, list));    
    return true;
}

之後排序會使用到中間節點，因此將取得中間節點寫成函式 q_get_mid

struct list_head *q_get_mid(struct list_head *head)
{
    if (list_is_singular(head))
        return head->next;
    struct list_head *forward, *backward;
    forward = head->next;
    backward = head->prev;
    while (forward != backward && forward->next != backward) {
        forward = forward->next;
        backward = backward->prev;
    }
    return forward;
}

改寫 q_delete_mid

bool q_delete_mid(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return false;
    struct list_head *mid = q_get_mid(head);
    list_del(mid);
    q_release_element(list_entry(mid, element_t, list));
    return true;
}

q_delete_dup

透過 list_for_each_entry_safe 來走訪佇列並刪除與相鄰節點有相同值的節點

bool q_delete_dup(struct list_head *head)
{
    if (head == NULL)
        return false;
    element_t *e, *s;
    list_for_each_entry_safe (e, s, head, list)
        if (strcmp(e->value, s->value) == 0) {
            list_del(&e->list);
            q_release_element(e);
        }
    return true;
}

會發生 Segmentation fault

問題發生在 list_for_each_entry_safe 巨集的 safe 會走回串列的 head 節點，由於該節點並非 element_t 結構體，試圖讀取不存在的成員便會出錯

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

修正如下，在比對字串前先確認是 safe 是否為串列的 head

bool q_delete_dup(struct list_head *head)
{
    if (head == NULL)
        return false;
    element_t *e, *s;
    list_for_each_entry_safe (e, s, head, list)
        if (&s->list != head && strcmp(e->value, s->value) == 0) {
            list_del(&e->list);
            q_release_element(e);
        }
    return true;
}

近期的 commit de856da 修正 q_delete_dup 函式的定義，上述程式碼需要進行修改

修正如下

多宣告一個 bool 變數來幫忙紀錄是否重複

bool q_delete_dup(struct list_head *head)
{
    if (head == NULL)
        return false;
    element_t *e, *s;
    bool is_dup = false;
    list_for_each_entry_safe (e, s, head, list)
        if (&s->list != head && strcmp(e->value, s->value) == 0) {
            is_dup = true;
            list_del(&e->list);
            q_release_element(e);
        } else if (is_dup) {
            is_dup = false;
            list_del(&e->list);
            q_release_element(e);
        }
    return true;
}

q_swap

直接重新指派兩兩一組節點相連的六個指標

void q_swap(struct list_head *head)
{
    struct list_head *node1, *node2;
    node1 = head->next;
    node2 = node1->next;
    while (node1 != head && node2 != head) {
        node1->prev->next = node2;
        node2->prev = node1->prev;
        node2->next->prev = node1;
        node1->next = node2->next;
        node2->next = node1;
        node1->prev = node2;
        node1 = node1->next;
        node2 = node1->next;
    }
}

閱讀 lanser 同學的作法後，發現可以將 q_swap 視作將奇數節點移除後插入偶數節點之後
List API 中的list_move 函式正好是 list_delete 和 list_add 的連續操作
將以上程式改寫為更精簡易讀的版本

void q_swap(struct list_head *head)
{
    struct list_head *node1, *node2;
    node1 = head->next;
    node2 = node1->next;
    while (node1 != head && node2 != head) {
        list_move(node1, node2);
        node1 = node1->next;
        node2 = node1->next;
    }
}

q_reverse

利用 list_for_each_safe 走訪串列交換 next 和 prev ，因為不會走到佇列的 head ，所以要額外處理

void q_reverse(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return;
    struct list_head *n, *s;
    list_for_each_safe (n, s, head) {
        n->next = n->prev;
        n->prev = s;
    }
    struct list_head *tmp;
    tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

q_sort

原本打算參考 Merge Sort 與它的變化 ，但跟本次實驗的資料結構略為不同，這次實驗是採用Intrusive linked lists

一開始想另外宣告 list_head 結構體並存放在 list_head * 陣列當中，以便進行上述筆記的分割方法，但寫完發現本次實驗不允許在 q_sort 當中進行 malloc 和 free 等操作

參考幾位同學的筆記後，決定利用 LIST_HEAD 巨集宣告區域變數接收分割出來的串列，維持雙向環狀的結構，以便透過 List API 操作串列

void q_sort(struct list_head *head)
{
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;

    LIST_HEAD(tmp);
    list_cut_position(&tmp, head, q_get_mid(head));
    q_sort(head);
    q_sort(&tmp);
    mergeTwoLists(head, &tmp);
}

在 mergeTwoLists 函式中，因為兩個引數 L1, L2 都是用來管理串列的 Head ，可以利用此特性，將兩條串列合併至其中一個 Head 之下

list_move_tail(node, head) 函式等價於把 node 節點移出原本其所在的串列，再將其插入 head 節點之前

void mergeTwoLists(struct list_head *L1, struct list_head *L2) {
    struct list_head *node = L1->next;
    element_t *E1, *E2;
    while(!list_empty(L2) && node != L1){        
        E1 = list_entry(node, element_t, list);
        E2 = list_entry(L2->next, element_t, list);
        if(strcmp(E1->value, E2->value) > 0){
            list_move_tail(&E2->list, &E1->list);
        } else {
            node = node->next;
        }
    }
    list_splice_tail(L2, L1);
}

q_shuffle

嘗試撰寫一個 Linux 風格的 List API

struct list_head *list_node_at(struct list_head *head, int index)
{
    struct list_head *node = head->next;
    while(--index)
        node = node->next;
    return node;
}

依照 Fisher-Yates shuffle 演算法實作

因為每次迭代都會縮小選取範圍，直接將選到的節點移至串列最尾端即可

void q_shuffle(struct list_head *head)
{
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;
    srand(time(NULL));
    for(int i = q_size(head); i > 1 ; i--){
        list_move_tail(list_node_at(head, rand()%i), head);
    }
}

在 qtest.c 中參考 do_sort 函式，實作 do_shuffle 函式

static bool do_shuffle(int argc, char *argv[])
{
     if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!l_meta.l)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();

    int cnt = q_size(l_meta.l);
    if (cnt < 2)
        report(3, "Warning: Calling shuffle on single node");
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();
    set_noallocate_mode(false);
    
    show_queue(3);
    return !error_check();
}

console_init 函式中新增 Shuffle 的相關命令

ADD_COMMAND(shuffle,
                "                | Perform Fisher-Yates shuffle in queue");

透過 qtest 進行測試

$ ./qtest
cmd> new
l = []
cmd> it 1
l = [1]
cmd> it 2
l = [1 2]
cmd> it 3
l = [1 2 3]
cmd> shuffle
l = [3 2 1]
cmd> shuffle
l = [2 1 3]
cmd> it 4
l = [2 1 3 4]
cmd> shuffle
l = [3 2 1 4]

git commit 的時候發現不能更動 queue.h 和 list.h，將所有程式移至 qtest.c