2022q1 Homework1 (lab0)

contributed by < BensonYang1999 >

tags: linux2022

實驗環境

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

$ uname -r
5.13.0-28-generic

$ 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):                          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:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz
Stepping:                        10
CPU MHz:                         1570.377
CPU max MHz:                     5000.0000
CPU min MHz:                     800.0000
BogoMIPS:                        7399.70
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        12 MiB
NUMA node0 CPU(s):               0-11

作業要求

lab0

依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改。

• q_new: 創一個空的 queue
• q_free: 釋放掉一個 queue
• q_insert_head: 在 head 插入一個 element (LIFO)
• q_insert_tail: 在 tail 插入一個 element (FIFO), O(1)
• q_remove_head: 把 head 的 element 移除
• q_size: return queue 的大小
• q_reverse: 將 queue 反轉，不配置或釋放任何的 element
• q_sort: 將 queue 由小排到大, sort by nature sort

開發過程

q_new

建立空的list_head，並利用list.h內建函數初始化

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    // check memory allocation
    if(!q)
        return NULL;
    // using INIT_LIST_HEAD function to initialize
    INIT_LIST_HEAD(q);
    return q;
}

q_free

list_for_each_entry_safe 會將entry的下一個element存在safe當中，因此可以安全的移除entry，而不會造成list中斷（找不到下一個element)

void q_free(struct list_head *l) 
{
    // list is empty -> return
    if(!l)
        return;
    element_t *entry, *safe;
    //safely delete every elememt
    list_for_each_entry_safe (entry, safe, l, list) {
        q_release_element(entry);
    }
}

q_insert_head

1. 先確認head是否存在
2. 分配記憶體空間給新的節點
3. 將string複製到節點中
4. 將節點加到head的前面

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    // allocate memory for new node
    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;
    // copy string
    node->value = strdup(s);
    list_add(&node->list, head);
    return true;
}

測試時發現無法通過測資，判定需要考慮value未更改成功因此加入以下程式

    if (!node->value) {
        q_release_element(node);
        return false;
    }

q_insert_tail

與q_insert_head類似，只有把list_add改成list_add_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    // allocate memory for new node
    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;
    // copy string
    node->value = strdup(s);
    if (!node->value) {
        q_release_element(node);
        return false;
    }
    list_add_tail(&node->list, head);
    return true;
}

q_remove_head

1. 確認head是否存在及head是否是空的
2. 找到元素，並將其remove
3. 將元素的值複製到sp

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    // find target element
    element_t *node = list_first_entry(head, element_t, list);
    // remove
    list_del_init(head->next);
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

q_remove_tail

與q_remove_head類似，只有修改找元素的function

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    // find target element
    element_t *node = list_last_entry(head, element_t, list);
    // remove
    list_del_init(head->prev);
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return node;
}

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

q_delete_mid

利用q_size取得佇列大小，計算中間值得位置，在利用迴圈找到要刪除的節點

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    int count = q_size(head) / 2;
    struct list_head *node = head->next;
    while (count--)
        node = node->next;
    list_del(node);
    q_release_element(list_entry(node, element_t, list));
    return true;
}

q_delete_dup

利用雙層while迴圈，當找到相同的元素時刪除，無相同則繼續尋找下個元素。

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;
    struct list_head *node = head->next, *node_del;
    while (node != head) {
        while (strcmp(list_entry(node, element_t, list)->value, list_entry(node->next, element_t, list)->value) == 0 &&
               node->next != head) {
            node_del = node;
            node = node->next;
            list_del(node_del);
            q_release_element(list_entry(node_del, element_t, list));
        }
        node = node->next;
    }
    return true;
}

上述版本執行時會產生dereference a null pointer，代表刪除錯誤的指標，因此更改第二層迴圈，利用if else做判斷

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;
    struct list_head *node = head->next, *node_del;
    while (node->next != head) {
        if (strcmp(list_entry(node, element_t, list)->value,
                   list_entry(node->next, element_t, list)->value) == 0) {
            node_del = node->next;
            list_del(node_del);
            q_release_element(list_entry(node_del, element_t, list));
        } else {
            node = node->next;
        }
    }
    return true;
}

q_swap

利用基礎prev及next原則實做這題

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return false;
    struct list_head *node = head->next;
    struct list_head *node_next = node->next;
    while (node != head && node->next != head) {
        // swap node & node_next
        node->prev->next = node_next;
        node_next->next->prev = node;
        node->next = node_next->next;
        node_next->prev = node->prev;
        node->prev = node_next;
        node_next->next = node;

        node = node->next;
        node_next = node->next;
    }
}

q_reverse

修改每個list_head的prev & next

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *node = head->next, *temp;
    while (node != head) {
        temp = node->prev;
        node->prev = node->next;
        node->next = temp;
        node = node->prev;
    }
    temp = head->prev;
    head->prev = head->next;
    head->next = temp;
}

q_sort

參考 你所不知道的 C 語言: linked list 和非連續記憶體 中的排序程式
執行sorting前必須將head斷開，避免產生無窮迴圈，執行後在將全部元素的prev修正，並補回head。

struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (strcmp(list_entry(L1, element_t, list)->value,
                       list_entry(L2, element_t, list)->value) < 0)
                   ? &L1
                   : &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}
struct list_head *mergesort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *slow = head;
    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow->next;
    slow->next = NULL;

    struct list_head *left = mergesort(head), *right = mergesort(mid);
    return mergeTwoLists(left, right);
}
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    // cut head link
    head->prev->next = NULL;
    head->next->prev = NULL;

    // merge sort
    struct list_head *sorted = mergesort(head->next);

    // link head & fix prev
    head->next = sorted;
    sorted->prev = head;
    struct list_head *temp = sorted;
    while (temp->next) {
        temp->next->prev = temp;
        temp = temp->next;
    }
    head->prev = temp;
    temp->next = head;
}

參考資料

• 格式：共筆示範
• 同學作業：ccs100203, laneser, jim12312321
• 其他：
  • 作業說明
  • C語言中的strdup()函式和其與strcpy()函式的區別
  • Linux 核心原始程式碼巨集: container_of