2023q1 Homework1 (lab0)

contributed by < qiaoyi213 >

注意項目符號的使用，標題用 # 開頭，分項就該以 ## 開頭，並該維護階層關係。

登記在 https://hackmd.io/@sysprog/linux2023-homework1 的網址，要用「固定網址」(參見 用固定網址發布筆記)，也就是如 https://hackmd.io/@itsme/XXXX 的形式，設定公開發表。

jserv

開發環境

$ gcc --version
gcc (Ubuntu 12.2.0-3ubuntu1) 12.2.0

$ lscpu
Architecture:           aarch64
  CPU op-mode(s):       64-bit
  Byte Order:           Little Endian
CPU(s):                 4
  On-line CPU(s) list:  0-3
Vendor ID:              0x00
  Model name:           -
    Model:              0
    Thread(s) per core: 1
    Core(s) per socket: 4
    Socket(s):          1
    Stepping:           0x0
    BogoMIPS:           48.00

作業敘述與要求

不用抄題目，善用超連結。

jserv

進度表

• q_new
• q_free
• q_insert_head
• q_insert_tail
• q_remove_head
• q_remove_tail
• q_size
• q_delete_mid
• q_delete_dup
• q_swap
• q_reverse
• q_reverseK
• q_sort
• q_descend
• q_merge

閱讀 你所不知道的 C 語言: linked list 和非連續記憶體

indirect pointer

一開始並不懂 indirect pointer 的用意，看了許久還是不理解為什麼這麼做。

看不懂就該列出教材哪裡沒寫好。不要說「大概懂」，無法應用和指出如何改進就是不懂。

jserv

參考 Mes 的筆記 後就大概懂 indirect pointer 的技巧，但在實作上可能還需要熟悉。

常用結構與巨集

寫到一半發現真的對我自己寫的東西很不確定，所以回來重新審視 queue.h 以及 list.h。

幻滅是成長的開始。

jserv

list_head

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

element_t

typedef struct {
    char *value;
    struct list_head list;
} element_t;

開發過程

Null pointer deference

在執行下列命令時

$cppcheck queue.c

多次出現 Null pointer deference 的錯誤，目前還不知道怎麼解決。
例如：

queue.c:71:22: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
element_t *tmp = list_first_entry(head, element_t, list);

實作 queue.[ch]

q_new

參考 list.h 中的 INIT_LIST_HEAD 函式，此函式是將 linked list 中的 prev 指標以及 next 指標指向自己，形成一個環形的 linked list。

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

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

q_free

從頭開始依序迭代所有的節點，移除該節點後就釋放該節點記憶體。
利用 list.h 中的巨集 list_for_each_entry_safe 實作 q_free。

注意資訊科技詞彙翻譯

jserv

已將「遍歷」修正為「迭代」

void q_free(struct list_head *l)
{
   element_t *entry, *safe;
   list_for_each_entry_safe(entry, safe, l, list)
       q_release_element(entry);
   free(l);
}

q_insert_head

使用 list_add 巨集新增節點

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

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;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    new->value = strdup(s);
    if (!new->value) {
        free(new);
        return false;
    }
    list_add_tail(&new->list, head);
    return true;
}

q_size

遍歷所有節點並且記錄 linked list 的大小。

int q_size(struct list_head *head)
{
    if(!head)
        return 0;
    int size = 0;
    struct list_head *node;
    list_for_each(node, head)
        size++;
    return size;
}

q_remove_head

目前測試結果仍有錯誤：Probably not constant time or wrong implementation

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{

    if(!head || list_empty(head))
        return NULL;
    element_t *tmp = list_entry(head->next, element_t, list);
    if(sp){
        strncpy(sp, tmp->value, bufsize-1);
        sp[bufsize-1] = '\0';
    }
    list_del(&tmp->list);
    return tmp;
}

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 *tmp = list_entry(head->prev, element_t, list);
    if(sp){
        strncpy(sp, tmp->value, bufsize-1);
        sp[bufsize-1] = '\0';
    }
    list_del(&tmp->list);
    return tmp;
}

q_delete_mid

使用 slow 指標以及 fast 指標
每次移動 slow 指標一次、fast 指標兩次，即可找到中間的位置。

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;

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

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

    list_del(slow);
    element_t *e = list_entry(fast, element_t, list);
    list_del(fast);
    free(e->value);
    free(e);

    return true;
}

q_delete_dup

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

    list_for_each_entry_safe(node, safe, head, list){
        if(&safe->list != head && strcmp(node->value, safe->value) == false){
            list_del(&node->list);
            q_release_element(node);
            is_dup = true;
        } else if ( is_dup ){
            list_del(&node->list);
            q_release_element(node);
            is_dup = false;
        }
    }
    return true;
}

q_reverse

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

    struct list_head *node, *safe;
    list_for_each_safe(node, safe, head)
        list_move(node,head);
    return;
}

q_reverseK

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if(!head || list_empty(head) || k < 2)
        return;
    int list_length = q_size(head);
    for(struct list_head *now = head->next;now != head && now->next != head;now = now->next) {
        struct list_head **curr = &now->next, *tmp = now->prev;
        for(int i=1;i<k;i++)
            if(list_length >= k)
                list_move(*curr, tmp);
    }
}

q_swap

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if(!head || list_empty(head) || list_is_singular(head))
        return;
    for(struct list_head *curr = head->next; curr != head && curr->next != head; curr = curr->next)
        list_move(curr, curr->next);
}

merge_two_list

參考 你所不知道的 C 語言: linked list 和非連續記憶體 後重新實作一遍。
將兩個已排序好的 linked list 合併並排序。

疑惑：在原本的範例中是使用 uintptr_t，我不清楚為什麼這裡是使用 u_int64_t 才對。

struct list_head *merge_two_list(struct list_head *l1, struct list_head *l2)
{
    struct list_head *head, **ptr, **node;
    head = NULL;
    ptr = &head;
    for(node = NULL; l1 && l2; *node=(*node)->next){
        if(strcmp(list_entry(l1, element_t, list)->value,
                  list_entry(l2, element_t, list)->value) < 0)
            node = &l1;
        else
            node = &l2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((u_int64_t) l1 | (u_int64_t) l2);
    return head;
}

merge_sort

實作 merge sort，並且使用與 q_delete_mid 相同的方法找位於 queue 中間的節點以分治。

static inline struct list_head merge_sort(struct list_head *head)
{
    if(!head || !head->next)
        return head;
    struct list_head *fast, *slow;
    fast = head->next;
    slow = head->next;
    while (slow != fast && slow->next != fast) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct list_head *left, *right;
    right = slow->next;
    slow->next = NULL;
    left = merge_sort(head);
    right = merge_sort(right);

    return merge_list(left, right);
}

q_sort

首先要先將 linked list 斷開連接變成 singular linked list 之後進行 merge sort 之後再重新連接。

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    head->prev->next = NULL;
    head->next = mergesort(head->next);
    struct list_head *current = head, *next = head->next;
    while (next) {
        next->prev = current;
        current = next;
        next = next->next;
    }
    current->next = head;
    head->prev = current;
}

q_merge

int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return q_size(list_first_entry(head, queue_contex_t, chain)->q);
    int queue_size = 0;
    queue_contex_t *first, *second;
    first = list_first_entry(head, queue_contex_t, chain),
    second = list_entry(first->chain.next, queue_contex_t, chain);
    while (second->q) {
        queue_size = q_size(merge_two_list(first->q, second->q));
        second->q = NULL;
        list_move_tail(&second->chain, head);
        second = list_entry(first->chain.next, queue_contex_t, chain);
    }
    return queue_size;
}

q_descend

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    element_t *entry;
    list_for_each_entry (entry, head, list) {
        struct list_head *prev = entry->list.prev, *safe = prev->prev;
        for (; prev != head; prev = safe, safe = safe->prev) {
            element_t *prev_entry = list_entry(prev, element_t, list);
            if (strcmp(prev_entry->value, entry->value) >= 0)
                break;
            list_del(prev);
            q_release_element(prev_entry);
        }
    }
    return 0;
}

make test 分數：71/100