2022q1 Homework1 (lab0)

Reviewed by `kevinshieh0225`

使用 &node->list 來取得 dereference list of address. 因為在運算次序中 derefence -> 高於 ＆。這樣不必使用 // cppcheck-suppress memleak
請善用 linux kernel api list_for_each, list_for_each_entry, list_for_each_safe, list_for_each_entry_safe
q_remove_head 重複做了 list_del(head->next); 可再簡化。

實驗環境

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

$ 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):                          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-4770K CPU @ 3.50GHz
Stepping:                        3
CPU MHz:                         800.000
CPU max MHz:                     3900.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6999.56
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        8 MiB
NUMA node0 CPU(s):               0-7

開發紀錄

q_new

Create a empty queue.
Return NULL if could not allocate space.

流程
1.使用 malloc() 分配記憶體位置，並由 new 指標指向。如果空間分配失敗，則 malloc 會回傳 NULL，此時函式回傳NULL
2.使用 list.h 中的 INIT_LIST_HEAD 初始化

INIT_LIST_HEAD 的功能為將 linked list 的 next 及 prev指向本身

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

q_new 實際程式碼

struct list_head *q_new()
{
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return NULL;
    INIT_LIST_HEAD(&(new->list));
    // cppcheck-suppress memleak
    return &(new->list);
}

q_free

Free all storage used by queue

流程
1.先檢查 head 是否為空，若為空則直接return 結束函式
2.使用 container_of 取出節點的記憶體位置，並逐一釋放空間。
3.釋放 head 的記憶體空間

參考 Linux 核心原始程式碼巨集: container_of，得知 container_of 可以用來得到包含 ptr 之 object 的起始記憶體位址

q_free 實際程式碼

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *ptr = l->next;
    while (ptr != l) {
        element_t *node = container_of(ptr, element_t, list);
        ptr = ptr->next;        
        q_release_element(node);
    }
    element_t *node = container_of(ptr, element_t, list);
    free(node);
}

q_insert_head

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.

流程
1.如果 head 為 NULL 則 return false
2.使用 malloc() 分配 emelent_t 大小的記憶體空間，若失敗則 return false
3.使用 strlen() 取得字串長度，並分配複製字串所需的空間

分配時要多一個位元組存放 NULL pointer

4.使用 list.h 中的函式 list_add() 將節點加在 head之後

list_add() 的功能為，將 node 接在 head 之後，並把 link 接好
```
static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}
```

q_insert_head 實際程式碼

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;
    int s_size = strlen(s);
    char *s_copy = malloc(s_size + 1);
    if (!s_copy) {
        free(node);
        return false;
    }
    memcpy(s_copy, s, s_size);
    s_copy[s_size] = 0;
    node->value = s_copy;
    list_add(&node->list, head);
    return true;
}

q_insert_tail

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.

流程
q_insert_tail() 與 q_insert_head() 幾乎相同，區別只有加入節點時使用的是 list_add_tail()

q_insert_tail 實際程式碼

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *node = malloc(sizeof(element_t));
    if (!node)
        return false;
    int s_size = strlen(s);
    char *s_copy = malloc(s_size + 1);
    if (!s_copy) {
        free(node);
        return false;
    }
    memcpy(s_copy, s, s_size);
    s_copy[s_size] = 0;
    node->value = s_copy;
    list_add_tail(&node->list, head);
    return true;
}

q_remove_head

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

流程
1.檢查 head 是否為 NULL 及 queue 是否為空，若成立則回傳 NULL
2.因為要用到第一個節點的 value ，所以用 container_of 取出第一個節點的位址，並使用 memcpy 將其所存的字串複製下來，複製的大小根據 bufsize

q_remove_head 實際程式碼

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = container_of(head->next, element_t, list);
    if (!sp) {
        list_del(head->next);
        return node;
    }
    memcpy(sp, node->value, bufsize - 1);
    list_del(head->next);
    sp[bufsize - 1] = 0;
    return node;
}

q_remove_tail

Attempt to remove element from tail of queue.
Other attribute is as same as q_remove_head.

流程
與 q_remove_head 相似，不同處為取出的點為 head->prev 即最後一個節點

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 *node = container_of(head->prev, element_t, list);
    if (!sp) {
        list_del(head->prev);
        return node;
    }
    memcpy(sp, node->value, bufsize - 1);
    list_del(head->prev);
    sp[bufsize - 1] = 0;
    return node;
}

q_size

Return number of elements in queue.
Return 0 if q is NULL or empty

流程
使用 list.h 中的巨集函式 list_for_each() 走訪每個節點，以計算linked list的長度

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

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.

流程
1.參考你所不知道的 C 語言: linked list 和非連續記憶體，案例探討： Leetcode 2095. Delete the Middle Node of a Linked List，使用快慢指標的技巧

此案例中，快指標每一次往前進兩個節點，而慢指標每一次往前進一個節點。如此一來，當快指標指向最後一個節點時，慢指標恰好指向中間的節點

2.並且搭配 indirect pointer 的技巧，省去配置暫時節點的空間

q_delete_mid 實際程式碼

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head)
        return false;
    if (list_empty(head))
        return false;
    struct list_head **indir_slow = &head->next;
    for (struct list_head *fast = head->next;
         head != fast && head != fast->next; fast = fast->next->next) {
        indir_slow = &(*indir_slow)->next;
    }
    element_t *remove_point = container_of(*indir_slow, element_t, list);
    list_del(*indir_slow);
    q_release_element(remove_point);

    return true;
}

q_delete_dup

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.

流程
1.取出首個節點的字串，接著將字串跟後續節點的字串依序比較是否相同，若相同則刪去
2.並以 dup_flag 去記錄刪去這個行為是否有被執行，若有 (表示有與首個節點重複的點) 則將首個節點也刪去

實作時原本以為只需要刪去重複的多餘字串 (留下1個，e.g. 112233 留下123) 即可，但在 make test 時失敗，才發現要刪去所有重複的(e.g. 11223345 只留下 45)，使用了flag 的方式去紀錄，但是造成程式碼大量重複

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;
    struct list_head *ptr1 = head->next, *ptr2 = ptr1->next;
    element_t *node1 = container_of(ptr1, element_t, list);
    bool dup_flag = false;
    for (; ptr2 != head; ptr2 = ptr1->next) {
        element_t *node2 = container_of(ptr2, element_t, list);
        if (strcmp(node1->value, node2->value) == 0) {
            list_del(ptr2);
            q_release_element(node2);
            dup_flag = true;
        } else {
            if (dup_flag) {
                list_del(ptr1);
                q_release_element(node1);
                dup_flag = false;
            }
            ptr1 = ptr2;
            node1 = container_of(ptr1, element_t, list);
        }
    }
    if (dup_flag) {
        list_del(ptr1);
        q_release_element(node1);
    }
    return true;
}

q_swap

Attempt to swap every two adjacent nodes.

流程
Step1. 將 ptr 指標指向head ，將 tmp 指標指向third

Step2. second 的 next 指向 first

Step3. head 的 next 指向 second

Step4. first 的 next 指向 third，以上步驟將 next 皆布置完畢

Step5. 將各個節點的 prev 接好，並將 ptr 指向 third 準備進行下一個循環

q_swap 實際程式碼

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

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.

流程
將每個節點與其下一個節點做 swap 即可達成整個 queue reverse

q_reverse 實際程式碼

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *tmp = NULL, *ptr = NULL;
    for (ptr = head->next; ptr != head; ptr = ptr->prev) {
        tmp = ptr->next;
        ptr->next = ptr->prev;
        ptr->prev = tmp;
    }
    tmp = ptr->next;
    ptr->next = ptr->prev;
    ptr->prev = tmp;
}

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.

流程
參考你所不知道的 C 語言: linked list 和非連續記憶體案例探討: LeetCode 21.Merge Two Sorted Lists

q_sort 實際程式碼

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) {
        element_t *L1_node = container_of(L1, element_t, list);
        element_t *L2_node = container_of(L2, element_t, list);
        node = (strcmp(L1_node->value, L2_node->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_list(struct list_head *head)
{
    if (!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_list(head), *right = mergesort_list(mid);
    return mergeTwoLists(left, right);
}
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    head->prev->next = NULL;
    head->next = mergesort_list(head->next);
    struct list_head *ptr = head;
    for (; ptr->next; ptr = ptr->next)
        ptr->next->prev = ptr;
    ptr->next = head;
    head->prev = ptr;
}