2022q1 Homework1 (lab0)

contributed by < BWbwchen >

開發環境

$ uname -a
Linux bw_workstation 4.15.0-166-generic #174-Ubuntu SMP Wed Dec 8 19:07:44 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               60
Model name:          Intel(R) Core(TM) i7-4790S CPU @ 3.20GHz
Stepping:            3
CPU MHz:             3505.806
CPU max MHz:         4000.0000
CPU min MHz:         800.0000
BogoMIPS:            6385.43
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            8192K
NUMA node0 CPU(s):   0-7
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts md_clear flush_l1d

作業要求

q_new: 建立新的「空」佇列;
q_free: 釋放佇列所佔用的記憶體;
q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
q_release_element: 釋放特定節點的記憶體空間;
q_size: 計算目前佇列的節點總量;
q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List
q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;

實作

q_new

配置一個新的記憶體空間，但須注意 malloc 有沒有失敗，並做初始化，也需要將 head->val 指派為 NULL

struct list_head *q_new()
{
    element_t *new = (element_t *) malloc(sizeof(element_t));
    if (!new)
        return NULL;
    new->value = NULL;
    INIT_LIST_HEAD(&new->list);

    return &new->list;
}

q_free

一直用 list_empty 來判斷現在整個 list 是否只剩下 head 這一個 node，並將非 head node 都使用 list_del 移除，此處須將資源釋放
最後將 head node 資源釋放

void q_free(struct list_head *l)
{
    if (!l)
        return;
    while (!list_empty(l)) {
        struct list_head *d = l->next;
        list_del(d);

        // cppcheck-suppress nullPointer
        q_release_element(list_entry(d, element_t, list));
    }
    // remove head
    // cppcheck-suppress nullPointer
    q_release_element(list_entry(l, element_t, list));
}

q_insert_head

透過 list_add 來做 insert head

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

    element_t *new = (element_t *) malloc(sizeof(element_t));
    if (!new)
        return false;

    list_add(&new->list, head);
    new->value = (char *) malloc(strlen(s) + 1);
    if (!new->value)
        return false;

    strncpy(new->value, s, strlen(s) + 1);
    return true;
}

q_insert_tail

透過 list_add_tail 來做 insert head

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

    element_t *new = (element_t *) malloc(sizeof(element_t));
    if (!new)
        return false;

    list_add_tail(&new->list, head);
    new->value = (char *) malloc(strlen(s) + 1);
    if (!new->value)
        return false;

    strncpy(new->value, s, strlen(s) + 1);
    return true;
}

q_remove_head

需要注意 queue 只有 head node 的狀況，並透過 list_del 將 head->next 刪除
須注意 sp 是否為 NULL

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

    // cppcheck-suppress nullPointer
    element_t *p = list_entry(head->next, element_t, list);
    if (sp) {
        strncpy(sp, p->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&p->list);
    return p;
}

q_remove_tail

需要注意 queue 只有 head node 的狀況，並透過 list_del 將 head->prev(tail node) 刪除
須注意 sp 是否為 NULL

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

    // cppcheck-suppress nullPointer
    element_t *p = list_entry(head->prev, element_t, list);
    if (sp) {
        strncpy(sp, p->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&p->list);
    return p;
}

q_size

需要注意 queue 只有 head node 的狀況

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

q_delete_mid

透過 fast/slow pointer 找出 middle node(slow pointer)

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 = head->next;
    struct list_head *slow = head->next;

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

    // cppcheck-suppress nullPointer
    q_release_element(list_entry(slow, element_t, list));

    return true;
}

q_delete_dup

因為已知佇列會是事先排序過，所以走訪所有的非 head node，將 pointer i 與 pointer i->next 去做比較，若有一樣的 value 則須透過 count 變數來紀錄，在之後要將該 pointer i 做刪除

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

    int count = 0;
    struct list_head *i;
    for (i = head->next; i != head && i->next != head;) {
        // cppcheck-suppress nullPointer
        element_t *now = list_entry(i, element_t, list);
        // cppcheck-suppress nullPointer
        element_t *next = list_entry(i->next, element_t, list);
        if (strcmp(now->value, next->value) == 0) {
            count++;
            list_del(&next->list);
            q_release_element(next);
            i = i->next;
        } else {
            if (count) {
                list_del(&now->list);
                q_release_element(now);
            }
            i = &next->list;
            count = 0;
        }
    }

    if (count) {
        struct list_head *d = head->prev;
        list_del(d);
        // cppcheck-suppress nullPointer
        q_release_element(list_entry(d, element_t, list));
    }
    return true;
}

q_swap

兩個兩個 node 為一組，透過 list_move 去做 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 *i = head->next->next; i != head && i != head->next;
         i = i->next->next->next) {
        struct list_head *pseudo_head = i->prev->prev;
        list_move(i, pseudo_head);
    }
}

q_reverse

針對每個 node 的 prev, next 去做交換，最後要重新設置 head 的 prev, next

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

    struct list_head *prev = head->prev;
    struct list_head *next = head->next;
    struct list_head *i;
    struct list_head *modify;
    list_for_each_safe (modify, i, head) {
        struct list_head *t = modify->next;
        modify->next = modify->prev;
        modify->prev = t;
    }
    head->prev = next;
    head->next = prev;
}

q_sort

我採用 merge sort 的方式，一開始先將 list 變成一個單向的 list(只維護 next, 而忽略 prev)，在完全排序好之後再來設置每個 node 的 prev pointer
透過 get_mid 函式 list 區段的中間部位，如此才能達到複雜度
$O (n l o g n)$

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

    head->prev->next = NULL;
    struct list_head *new_head = merge_sort(head->next);
    head->next = new_head;
    new_head->prev = head;

    // repair the prev link
    for (; new_head != head; new_head = new_head->next) {
        if (new_head->next) {
            new_head->next->prev = new_head;
        } else {
            new_head->next = head;
            head->prev = new_head;
        }
    }
}

struct list_head *merge_sort(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    struct list_head *mid = get_mid(head);
    struct list_head *right = mid->next;
    mid->next = NULL;

    return merge_list(merge_sort(head), merge_sort(right));
}

get_mid()
用兩個走訪速率為 1 ： 2 的 pointer 去走訪到中間點

struct list_head *get_mid(struct list_head *head)
{
    if (!head)
        return head;
    struct list_head *slow = head;
    struct list_head *fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

merge_list

struct list_head *merge_list(struct list_head *left, struct list_head *right)
{
    struct list_head *needle = NULL;
    struct list_head *head = NULL;
    for (needle = NULL; left || right;) {
        // cppcheck-suppress nullPointer
        element_t *l = list_entry(left, element_t, list);
        // cppcheck-suppress nullPointer
        element_t *r = list_entry(right, element_t, list);
        if (!left || (right && strcmp(l->value, r->value) >= 0)) {
            if (!needle) {
                head = needle = right;
            } else {
                needle->next = right;
                needle = needle->next;
            }
            right = right->next;
        } else {
            if (!needle) {
                head = needle = left;
            } else {
                needle->next = left;
                needle = needle->next;
            }
            left = left->next;
        }
    }

    return head;
}

2022q1 Homework1 (lab0)

開發環境

作業要求

實作

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_sort

Read more

2020q1 Homework1 (lab0)

[2020q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 1 週測驗題