2022q1 Homework1 (lab0)

contributed by < ganoliz >

實驗環境

$ 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
每核心執行緒數：                 2
每通訊端核心數：                 4
Socket(s):                       1
NUMA 節點：                      1
供應商識別號：                   GenuineIntel
CPU 家族：                       6
型號：                           158
Model name:                      Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
製程：                           9
CPU MHz：                        2436.942
CPU max MHz:                     4200.0000
CPU min MHz:                     800.0000
BogoMIPS:                        7200.00
虛擬：                           VT-x
L1d 快取：                       128 KiB
L1i 快取：                       128 KiB
L2 快取：                        1 MiB
L3 快取：                        8 MiB
NUMA node0 CPU(s)：              0-7

作業要求

實做 queue.c 的相關程式碼：
- q_new: 建立新的「空」佇列;
- q_free: 釋放佇列所佔用的記憶體;
- q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點;
- q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點;
- q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
- q_release_element: 釋放特定節點的記憶體空間;
- q_size: 計算目前佇列的節點總量;
- q_delete_mid: 移走佇列中間的節點;
- q_swap: 交換佇列中鄰近的節點;
- q_reverse: 以反向順序重新排列鏈結串列;
- q_sort: 以遞增順序來排序鏈結串列的節點;
在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
指出現有程式的缺陷 (提示: 和 RIO 套件有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

開發過程

q_new:

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

    if (Queue == NULL)
        return NULL;

    INIT_LIST_HEAD(Queue);


    return Queue;
}

新增一個Queue:初期寫法是使用queue指標指向自身，後來詳讀你所不知道的 C 語言: linked list 和非連續記憶體與 list.h 的 The Linux Kernel API ，將寫法改為 macro 。

q_free:

void q_free(struct list_head *l)
{
    struct list_head *temp;

    if (l == NULL) {
        return;
    }

    if (list_empty(l)) {
        // printf("l is already release");
        free(l);
        return;
    }

    if (list_is_singular(l)) {
        element_t *node = container_of(l->next, typeof(element_t), list);
        q_release_element(node);
        free(l);

        return;
    }

    for (temp = l->next; temp != l;) {
        element_t *node = container_of(temp, typeof(element_t), list);
        temp = temp->next;
        q_release_element(node);
    }

    free(l);
    return;
}

釋放Queue:可以看到 q_free() 針對不同的節點數做了很多if判斷。
假如head沒有 element_t 節點，就將本身 new 出來的 list_head 釋放就可以了。若是有節點則使用 container_of(list_entry) 找出 element_t 的位置再將其 element_t 釋放，最後再將 head 釋放。
顯然程式碼是有改進空間的，針對不同節點的共同特性找出來，就可以精簡程式碼不用那麼多 if 判斷。

q_insert_head

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


    element_t *Node = malloc(sizeof(element_t));
    char *c = malloc(strlen(s) + 1);



    if (Node == NULL || c == NULL) {
        if (Node != NULL) {
            free(Node);
        }
        if (c != NULL) {
            free(c);
        }
        return false;
    }


    memcpy(c, s, strlen(s) + 1);
    Node->value = c;
    INIT_LIST_HEAD(&Node->list);
    list_add(&Node->list, head);


    return true;
}

新增節點:若是 malloc 不成功，要找出是 element_t 不成功還是 char 不成功，然後釋放掉另一個後回傳 false 。這是一個我很後面才改的小 Bug ，也讓我知道系統程式要考慮得很嚴謹，不能讓記憶體洩漏。
節點新增成功之後，將字串用 memcpy 複製到 element_t 的 value 成員。接著使用 API 初始化 element_t 的成員 list ，並將它的 list 新增到 head 的後面。

q_insert_tail

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

    element_t *Node = malloc(sizeof(element_t));
    char *c = malloc(strlen(s) + 1);
    // struct list_head *temp;

    if (Node == NULL || c == NULL) {
        if (Node != NULL) {
            free(Node);
        }
        if (c != NULL) {
            free(c);
        }
        return false;
    }


    memcpy(c, s, strlen(s) + 1);

    Node->value = c;
    INIT_LIST_HEAD(&Node->list);
    list_add_tail(&Node->list, head);


    return true;
}

新增節點至尾端:基本上跟 q_inset_head 相同，只是使用 list.h 的 API 不一樣，改使用 list_add_tail 。

q_remove_head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head)) {
        return NULL;
    }



    struct list_head *node = head->next;
    element_t *element;
    element = list_entry(node, typeof(element_t), list);



    if (sp) {
        memcpy(sp, element->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }



    list_del(node);

    return element;
}

移除從頭開始的第一個節點: 將節點移除，若Queue不存在或是為空則回傳NULL。一開始搞不太清楚 char * sp 的用途還寫了很多 if-else 判斷式。稍微觀摩一下同學的程式碼就理解到 sp 。若有提供 sp ，就將 element_t 的 value 複製過去，複製直到 bufsize-1 的大小(遇到'\0'會自動停止)。值得注意的是若 element_t 的 value 大小超過 bufsize-1 其餘就會被砍掉，然後 * (sp+bufsize-1) 的位置一定要放'\0'，否則系統不會知道結束位置在哪裡。

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;
    }

    struct list_head *node = head->prev;
    element_t *element;
    element = list_entry(node, typeof(element_t), list);

    if (sp) {
        memcpy(sp, element->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }

    list_del(node);
    return element;
}

從尾端移除節點:基本上和從頭移除節點相同，只是存取的 node 點變成 head->prev，當然也可以使用 list_last_entry 來取得最後一個節點的位置。

q_release_element

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

釋放節點:毫無疑問!就是個釋放節點。

q_size:

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


    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

Queue的大小:透過 list_for_eac 走訪每個 node，並每次對 len+1，最後返回 len 的長度。

q_delete_middle

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/

    if (head == NULL || list_empty(head))
        return false;
    else if (list_is_singular(head)) {
        // q_remove_head(head, NULL, 100);
        element_t *temp = list_entry(head->next, element_t, list);
        list_del(&temp->list);
        q_release_element(temp);
        return true;
    }


    struct list_head **indir = &head->next, *prev = NULL;
    for (struct list_head *fast = head->next;
         fast != head && fast->next != head; fast = fast->next->next) {
        prev = *indir;
        indir = &(*indir)->next;
    }
    struct list_head *next = (*indir)->next;

    element_t *temp = list_entry(*indir, element_t, list);
    list_del(*indir);
    q_release_element(temp);

    prev->next = next;

    return true;
}

移除中心點: 參考你所不知道的 C 語言: linked list 和非連續記憶體中所述之移除中心點方法，以快慢指標來實作( slow 走一格時 fast 走兩格)，找到中心點後將中心點使用 list_del 刪除(其實這樣就能將其前面的節點指向後面)。

q_delete_dup

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    if (list_is_singular(head)) {
        return true;
    }


    bool duplicate = false;


    struct list_head *current, *next;
    list_for_each_safe (current, next, head) {
        
        element_t *node = list_entry(current, element_t, list);
        element_t *safe = list_entry(next, element_t, list);
        if (next == head) {
            if (duplicate) {
                element_t *temp = node;
                // node=list_entry(node->list.prev,element_t,list);

                printf("remove node last:%c \n", *(temp->value));
                list_del(&temp->list);
                q_release_element(temp);
            }
            break;
        }

        
        if (strcmp(node->value, safe->value) == 0) {
            element_t *temp = node;
            // node=list_entry(node->list.prev,element_t,list);
            duplicate = true;

            // printf("remove node:%c \n",*(temp->value));

            list_del(&temp->list);
            q_release_element(temp);
        }
        else if (duplicate) {
            element_t *temp = node;
            // node=list_entry(node->list.prev,element_t,list);

            printf("remove node last:%c \n", *(temp->value));
            list_del(&temp->list);
            q_release_element(temp);
            duplicate = false;
        }
    }

    return true;
}

刪除重複的所有Node:參考同學設置一個 bool duplicate 的想法，假如有重複就設 duplicate 為 true並刪除，若是 strcmp 之後未重複，則是判斷前面是否為 duplicate，若是則代表前面有出現過並把該node刪除。這部分程式碼還是有保留一些冗餘的部分，比如當 current == tail 且 next == head的情況下，需要用這段程式碼第一個if述句來特別開一個條件給它，寫起來不夠 general。

q_swap

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *odd, *even, *temp;
    odd = head->next, even = head->next->next;
    while (odd != head && even != head) {
        odd->next = even->next;
        odd->prev->next = even;
        temp = odd->prev;
        odd->prev = even;

        even->next->prev = odd;
        even->next = odd;
        even->prev = temp;

        odd = odd->next;
        even = odd->next;
    }

節點倆倆交換位置:透過 odd 為奇數節點， even 為偶數節點走訪整個 Queue ，並兩兩指標交換。

根據圖，我們總共需要移動六個指標，首先移動

1. odd->next
1. odd->prev->next
1. odd->prev
1. even->next->prev
1. even->next
1. even->prev

然後因為現在 odd 實質上等於 even 的位置了，所以 odd 往 next 移動一次就等於新的要調整的 odd 了，然後 even 再順勢往 odd 的 next 再移動一次，就是新的要調整的 even 了(整體可讀性低了一些些)。

q_reverse

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

    temp = head->prev;
    head->prev = head->next;
    head->next = temp;

    list_for_each (li, head) {
        temp = li->prev;
        li->prev = li->next;
        li->next = temp;
    }
}

Queue 翻轉: 使用 list_for_each 走訪節點，然後將節點的 prev 與 next 對調(應該使用 list_for_each_safe 比較保險，因為有動到 Node 裡的東西)，走完每個節點對調完即完成。

q_sort

    if (!head || list_empty(head) || list_is_singular(head))
        return;


    struct list_head *temp = head->next;
    head->prev->next = NULL;
    head->prev = NULL;
    head->next->prev = NULL;
    head->next = NULL;


    struct list_head *sortlist = mergesort_list(temp);

MergeSort: 參考你所不知道的 C 語言: linked list 和非連續記憶體中的 merge sort 範例，在這個函式裡，我們先把 head 丟棄，避免它在我們後續使用 list_entrt 找 element_t 位置的時候指涉到 head 導致錯誤。接著我們把第一個元素 temp 丟進 mergesort_list() 裡:

static struct list_head *mergesort_list(struct list_head *head)
{
    if (!head)
        return NULL;

    if (head->next == NULL)
        return head;

    struct list_head *slow = head;
    for (struct list_head *fast = head->next;
         fast != NULL && fast->next != NULL; fast = fast->next->next) {
        slow = slow->next;
    }
    struct list_head *mid = slow->next;

    // element_t *t=list_entry(mid,element_t,list);
    // printf("mid= %c \n",*(t->value));

    mid->prev = NULL;
    slow->next = NULL;

    // element_t *temp_sl=list_entry(slow,element_t,list);
    // printf("slow= %c \t",*(temp_sl->value));

    struct list_head *left = mergesort_list(head), *right = mergesort_list(mid);

    return mergeTwoLists(left, right);

在這個函式裡我們會使用遞迴把所有 element_t 變為一個個互不相聯的元素使用 delete_mid的方法。所以說我們斷開了所有 prev 跟 next 。接著遞迴呼叫 mergeTwoLists 來兩兩合併 List :

static struct list_head *mergeTwoLists(struct list_head *L1,
                                       struct list_head *L2)
{
    struct list_head *head = NULL;
    struct list_head **ptr = &head;
    for (; L1 && L2; ptr = &(*ptr)->next) {
        element_t *l1 = list_entry(L1, element_t, list);
        element_t *l2 = list_entry(L2, element_t, list);
        if (strcmp(l1->value, l2->value) < 0) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

這裡就是參考老師的 merge two sorted lists ，非常漂亮。由於最後形成的是一個 Single-Linked-lists ，於是當我們最後回到 q_sort 裡時，需要將 prev 依序補上形成 Double-Linked-lists ，再把 head 接回來，大功告成。

    //struct list_head *sortlist = mergesort_list(temp);

// above ============================================================

    struct list_head *prev = sortlist;
    struct list_head *current = sortlist->next;
    for (; current != NULL; current = current->next, prev = prev->next) {
        current->prev = prev;
    }

    head->next = sortlist;  // let head connect to value
    sortlist->prev = head;
    head->prev = prev;  // finally prev will reach tail
    prev->next = head;