2022q1 Homework1 (lab0)

contributed by < Ahsen-lab >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 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
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              1
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           165
Model name:                      Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz
Stepping:                        5
CPU MHz:                         2904.002
BogoMIPS:                        5808.00
Hypervisor vendor:               KVM
Virtualization type:             full
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        48 MiB
NUMA node0 CPU(s):               0-3

作業要求

作業要求

queue.c 僅提供介面 (interface) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:

• q_new: 建立新的「空」佇列。
• q_free: 釋放佇列所佔用的記憶體。
• q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)。
• q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)。
• q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點。
• q_remove_tail: 在佇列尾端 (tail) 移去 (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，再用INIT_LIST_HEAD function來初始化head，需要注意malloc有可能會 fail，若分配記憶體空間失敗，則回傳NULL。

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
struct list_head *q_new()
{
    struct list_head *head;
    head = (struct list_head *) malloc(sizeof(struct list_head));

    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);
    return head;
}

q_free

釋放佇列所佔用的記憶體

void q_free(struct list_head *l)
{
    if (!l)
        return;

    struct list_head *pos, *q;
    element_t *curr = NULL;

    list_for_each_safe (pos, q, l) {
        curr = list_entry(pos, element_t, list);
        list_del(pos);
        if (curr != NULL) {
            free(curr);
        }
    }
    free(q);
}

一開始對 Linux List Management API 還不是很熟，所以使用上方這種比較多此一舉的方式來實作，用 list_for_each_safe 走訪每個 node 並用 list_entry 取出對應的 element，然後釋放 element 所佔的記憶體空間。

後來重新讀了 list.h 檔裡的 API 說明，以及參考 laneser 的設計，改為使用 list_for_each_entry_safe API 來實作，程式碼如下，變得簡潔許多。

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *curr, *tmp;

    list_for_each_entry_safe (curr, tmp, l, list) {
        free(curr->value);
        free(curr);
    }
    free(l);
}

q_insert_head

在佇列開頭 (head) 插入 (insert) 給定的新節點

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *newh = (element_t *) malloc(sizeof(element_t));

    if (!newh || !head)
        return false;

    newh->value = (char *) calloc(strlen(s) + 1, sizeof(char));

    if (!(newh->value)) {
        free(newh->value);
        free(newh);
        return false;
    }

    memcpy(newh->value, s, strlen(s));
    list_add(&newh->list, head);
    return true;
}

我的作法是分配一段記憶體空間給一個新的 element ，再分配一段空間給 element 的成員變數 char *value 用來儲存字串，一開始我是使用 calloc 來分配空間給字串，原因是 calloc 分配的空間是一個 array ，而且會自動將 array 中的每個 bits 都初始化為 0，在字元中 0 與 NULL 相等，只要分配 strlen(str) + 1 長度的 array，再將字串複製進去，就不用手動在字串尾端加上 NULL。

#include <stdlib.h>
void *calloc(size_t nmemb, size_t size);

• C99 [7.20.3.1] The calloc function
  • The calloc function allocates space for an array of nmemb objects, each of whose size is size. The space is initialized to all bits zero.

但在實作過程中有遇到一個問題，若使用 calloc 來分配空間給 char *value ，在 q_free function 中 free char *value 會出現 error :

Error: Attempted to free unallocated block

但若是使用 malloc 則不會有這個問題，所以後來我改成下方那種寫法。

/*
 * Attempt to insert element at head of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    int len = strlen(s);
    element_t *newh = (element_t *) malloc(sizeof(element_t));

    if (!newh)
        return false;

    newh->value = (char *) malloc(len + 1);

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

    memcpy(newh->value, s, len);
    newh->value[len] = '\0';
    list_add(&newh->list, head);
    return true;
}

TODO : 造成 malloc 和 calloc 會導致不同結果的原因目前還在追蹤中。

q_insert_tail

在佇列尾端 (tail) 插入 (insert) 給定的新節點

/*
 * Attempt to insert element at tail of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    int len = strlen(s);
    element_t *newt = (element_t *) malloc(sizeof(element_t));

    if (!newt)
        return false;

    newt->value = (char *) malloc(len + 1);

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

    memcpy(newt->value, s, len);
    newt->value[len] = '\0';
    list_add_tail(&newt->list, head);
    return true;
}

實作概念與 q_insert_head 相同，只是將 list_add 換成 list_add_tail。

q_remove_head

在佇列開頭 (head) 移去 (remove) 給定的節點

/*
 * Attempt to remove element from head of queue.
 * Return target element.
 * Return NULL if queue is NULL or empty.
 * If sp is non-NULL and an element is removed, copy the removed string to *sp
 * (up to a maximum of bufsize-1 characters, plus a null terminator.)
 *
 * NOTE: "remove" is different from "delete"
 * The space used by the list element and the string should not be freed.
 * The only thing "remove" need to do is unlink it.
 *
 * REF:
 * https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
 */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *entry = list_first_entry(head, element_t, list);

    if (sp) {
        strncpy(sp, entry->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_del(head->next);
    return entry;
}

q_remove_tail

在佇列尾端 (tail) 移去 (remove) 給定的節點

/*
 * Attempt to remove element from tail of queue.
 * Other attribute is as same as q_remove_head.
 */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *entry = list_last_entry(head, element_t, list);

    if (sp) {
        strncpy(sp, entry->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->prev);
    return entry;
}

q_release_element

釋放特定節點的記憶體空間，包含節點裡儲存的 value 字串也一並釋放掉

/*
 * WARN: This is for external usage, don't modify it
 * Attempt to release element.
 */
void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

q_size

計算目前佇列的節點總量，設定一個變數 len，初始值為 0，再使用 list_for_each 來遍歷佇列中的所有節點，每經過一個節點 len 就加一，最後回傳 len 的值，若佇列為 NULL 或 empty 則返回 0，

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
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

移走佇列中間的節點，作法參考

你所不知道的 C 語言: linked list 和非連續記憶體 案例探討 : Leetcode 2095. Delete the Middle Node of a Linked List

原本的案例探討是針對單向的 linked list，我將其改為雙向環狀 linked list 的版本，若傳入的佇列為 NULL 或是空佇列，則回傳 false。

使用指標的指標，搭配快慢指標的技巧來找出中間的節點，首先設定一個指標的指標 indir，以及一個指標 fast，兩個指標都會指向 head->next，然後使用迴圈走訪節點，fast 每次會前進兩個節點，而 indir 每次前進一個，當 fast 本身等於 head 或是 fast->next 等於 head 時，代表已走訪完佇列，這時 indir 會指向佇列中間的節點。

找到中間節點後，使用 list_entry 來取得相對應的 element_t，然後用 list_del 及 q_release_element 來移除節點並釋放記憶體空間，最後回傳 true。

/*
 * Delete the middle node in list.
 * The middle node of a linked list of size n is the
 * ⌊n / 2⌋th node from the start using 0-based indexing.
 * If there're six element, the third member should be return.
 * Return true if successful.
 * Return false if list is NULL or empty.
 */
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 **indir = &head->next;
    struct list_head *fast;
    for (fast = head->next; (fast != head) && (fast->next != head);
         fast = fast->next->next)
        indir = &(*indir)->next;

    element_t *del = list_entry(*indir, element_t, list);
    list_del(*indir);
    q_release_element(del);
    return true;
}

q_delete_dup

在已經排序的狀況，移走佇列中具備重複內容的節點，若傳入的佇列為 NULL，回傳 false。

以下實作有參考 laneser 同學的作法。

設定兩個 element_t * 變數 cur、nex，以及兩個 struct list_head * 變數 curr、next，初始化 curr = head->next、next = head->next->next，使用迴圈來走訪節點，在走訪的過程中使用 list_entry 來取得 curr、next 所對應的 entry cur 和 nex。

另外，在走訪節點的過程中需要考慮兩個情況：

1. cur->value == nex->value：

   • 刪除 cur，並將 needDel 設成 true，表示所有與 cur 有相同字串的 entry 都是需要刪除的節點。

2. cur->value != nex->value：

   • 若 needDel == true 表示 cur 也是需要刪除的 entry。
   • 若 needDel == false 表示 cur 無須刪除。

/*
 * Delete all nodes that have duplicate string,
 * leaving only distinct strings from the original list.
 * Return true if successful.
 * Return false if list is NULL.
 *
 * Note: this function always be called after sorting, in other words,
 * list is guaranteed to be sorted in ascending order.
 */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;

    bool needDel = false;
    struct list_head *curr, *next;
    element_t *cur = NULL, *nex = NULL;

    for (curr = head->next, next = head->next->next; next != head;
         curr = next, next = next->next) {
        cur = list_entry(curr, element_t, list);
        nex = list_entry(next, element_t, list);

        if (strcasecmp(cur->value, nex->value) == 0) {
            list_del(curr);
            q_release_element(cur);
            needDel = true;
        } else if (needDel) {
            list_del(curr);
            q_release_element(cur);
            needDel = false;
        }
    }

    if (needDel) {
        cur = list_entry(curr, element_t, list);
        list_del(curr);
        q_release_element(cur);
    }
    return true;
}

在走訪完所有節點後 cur 會指向佇列的最後一個節點，若此時 needDel 依然為 true，則代表佇列最後的兩個節點所包含的字串是相同的，兩個節點都需要刪除，而迴圈過程中會刪除倒數第二個節點，最後一個節點則需透過刪除 cur 來刪除。

q_swap

交換佇列中鄰近的節點，若傳入的佇列為 NULL，則不做任何動作。

這個 function 中我主要是用 list_move 來完成實作：

/* list_move API */
static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

list_move 會將 node 移到佇列的開頭，也就是會讓 head->next 指向 node，利用這個功能，搭配迴圈走訪節點，一開始設定一個指標 h 指向 head。

每次迴圈 h 會前進兩個節點 h = h->next->next，將 h->next->next 當作新的 head 代入 list_move 中，就可達到交換佇列中鄰近的節點的目的。

/*
 * Attempt to swap every two adjacent nodes.
 */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;

    struct list_head *h;
    for (h = head; (h->next != head) && (h->next->next != head);
         h = h->next->next)
        list_move(h->next->next, h);
}

q_reverse

以反向順序重新排列鏈結串列

/*
 * Reverse elements in queue
 * No effect if q is NULL or empty
 * This function should not allocate or free any list elements
 * (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
 * It should rearrange the existing ones.
 */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *swap = head->next;
    struct list_head *stop = NULL;

    while (stop != head) {
        stop = swap->next;
        list_move(swap, head);
        swap = stop;
    }
}

q_sort

以遞增順序來排序鏈結串列的節點

list_append

void list_append(struct list_head *list, struct list_head *head)
{
    struct list_head *head_last = head->prev;
    struct list_head *list_last = list->prev;

    head_last->next = list;
    list_last->next = head;
    list->prev = head_last;
    head->prev = list_last;
}

mergeTwoLists

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

    do {
        element_t *entryL1 = list_entry(L1, element_t, list);
        element_t *entryL2 = list_entry(L2, element_t, list);

        if (strcasecmp(entryL1->value, entryL2->value) < 0) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }

        list_del_init(*ptr);
        list_add_tail(*ptr, head);
        ptr = &(*ptr)->next;

    } while ((L1->next != head) && (L2->next != head));

    L1->next == head ? list_append(L2, head) : list_append(L1, head);
    return head;
}

mergesort_list

struct list_head *mergesort_list(struct list_head *entryHead)
{
    if (entryHead->next == entryHead && entryHead->prev == entryHead)
        return entryHead;

    struct list_head *entryTail = entryHead->prev;
    struct list_head *slow = entryHead, *fast;

    for (fast = entryHead->next;
         (fast != entryHead) && (fast->next != entryHead);
         fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow->next;

    mid->prev = entryTail;
    entryTail->next = mid;

    slow->next = entryHead;
    entryHead->prev = slow;

    struct list_head *left = mergesort_list(entryHead);
    struct list_head *right = mergesort_list(mid);
    return mergeTwoLists(left, right);
}

q_sort

/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *entryHead = head->next;
    list_del_init(head);
    struct list_head *sorted = mergesort_list(entryHead);
    list_append(sorted, head);
}