2022q1 Homework1 (lab0)

contributed by < ShawnLu31 >

實驗環境

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

$ 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):                          16
On-line CPU(s) list:             0-15
Thread(s) per core:              2
Core(s) per socket:              8
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           165
Model name:                      Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
Stepping:                        5
CPU MHz:                         2900.000
CPU max MHz:                     4800.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5799.77
Virtualization:                  VT-x
L1d cache:                       256 KiB
L1i cache:                       256 KiB
L2 cache:                        2 MiB
L3 cache:                        16 MiB
NUMA node0 CPU(s):               0-15

作業要求

lab0

開發過程

佇列架構

lish.h 巨集參考

INIT_LIST_HEAD() - Initialize empty list head
Add new node
- list_add() - Add a list node to the beginning of the list
- list_add_tail() - Add a list node to the end of the list
- list_splice() - Add list nodes from a list to beginning of another list
- list_splice_tail() - Add list nodes from a list to end of another list
- list_splice_init() - Move list nodes from a list to beginning of another list
- list_splice_tail_init() - Move list nodes from a list to end of another list
Remove node
- list_del() - Remove a list node from the list
- list_del_init() - Remove a list node from the list and reinitialize it
Check
- list_empty() - Check if list head has no nodes attached
- list_is_singular() - Check if list head has exactly one node attached
Move
- list_cut_position() - Move beginning of a list to another list
- list_move() - Move a list node to the beginning of the list
- list_move_tail() - Move a list node to the end of the list
Entry
- list_first_entry() - get first entry of the list
- list_last_entry() - get last entry of the list
iteraton
- list_for_each - iterate over list nodes
- list_for_each_entry - iterate over list entries

針對佇列的實作

`q_new`

用 malloc 取得 struct list_head 大小的記憶體。

如果失敗回傳 NULL 。
成功則用 INIT_LIST_HEAD() 做初始化。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

注意共筆書寫規範：中英文間用一個半形空白區隔

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

`q_free`

此函式須釋放佇列所有空間，所以須釋放 element 和 l 。

用 list_for_each_entry_safe() 走訪節點。

entry ，對應 element 物件。
safe ，允許移除目前節點。

用 list_del() 移出佇列， q_release_element() 釋放節點空間。
釋放佇列 l 。

void q_free(struct list_head *l)
{
    if (!l)
        return; /* queue is NULL */
    element_t *del, *next;
    /* del, the element to be free. next, the next element of del */
    list_for_each_entry_safe (del, next, l, list) {
        list_del(&del->list);
        q_release_element(del);
    }
    free(l);
    return;
}

`q_insert_head`

若佇列是NULL 立刻回傳 false 。
用 malloc 取得 element_t 大小的記憶體。失敗回傳 false 。
用 malloc 取得 s 字串大小的記憶體。失敗釋放 e 的空間並回傳 false 。
用 memcpy 複製字串和 INIT_LIST_HEAD() 初始化新節點，再用 list_add 加入佇列最前端。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false; /* queue is NULL */
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return NULL; /* could not allocate space */
    int len = strlen(s) + 1;
    e->value = malloc(sizeof(char) * len);
    if (!e->value) {
        free(e);
        return NULL; /* could not allocate space */
    }
    memcpy(e->value, s, len);
    INIT_LIST_HEAD(&e->list);
    list_add(&e->list, head);
    return true;
}

更新：

用 gen_element 取代與 q_insert_tail 相同的程式。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head || !s)
        return false; /* queue is NULL or s is NULL*/
    element_t *e = gen_element(s);
    if (!e)
        return false;
    list_add(&e->list, head);
    return true;
}

`q_insert_tail`

大致與 q_insert_head() 相同。用 list_add_tail() 加入佇列尾端。

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false; /* queue is NULL */
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return NULL; /* could not allocate space */
    int len = strlen(s) + 1;
    e->value = malloc(sizeof(char) * len);
    if (!e->value) {
        free(e);
        return NULL; /* could not allocate space */
    }
    memcpy(e->value, s, len);
    INIT_LIST_HEAD(&e->list);
    list_add_tail(&e->list, head);
    return true;
}

更新：

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head || !s)
        return false; /* queue is NULL or s is NULL*/
    element_t *e = gen_element(s);
    if (!e)
        return false;
    list_add_tail(&e->list, head);
    return true;
}

`gen_element`

element_t *gen_element(char *s)
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return NULL; /* could not allocate space */
    int len = strlen(s) + 1;
    e->value = malloc(sizeof(char) * len);
    if (!e->value) {
        free(e);
        return NULL; /* could not allocate space */
    }
    memcpy(e->value, s, len);
    INIT_LIST_HEAD(&e->list);
    return e;
}

`q_remove_head`

若佇列為 NULL 或空，回傳 NULL 。
list_first_entry() 取得第一個節點位置， list_del_init() 移除該節點。
若 sp 不為 NULL ，複製節點的 value 到 sp 。
回傳該節點。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *e = list_first_entry(head, element_t, list);
    list_del_init(head->next);
    if (sp)
        memcpy(sp, e->value, strlen(e->value) + 1);
    return e;
}

`q_remove_tail`

用 q_remove_head() 實作，傳入 head->prev->prev ，其取得的節點便是 head->prev 。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    return q_remove_head(head->prev->prev, sp, bufsize);
}

`q_size`

一開始檢查佇列是否為 NULL 或空。
使用 list_for_each() 走訪佇列，計算節點數量，並回傳。

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

`q_delete_mid`

根據你所不知道的 C 語言: linked list 和非連續記憶體中的範例實作

一開始檢查佇列是否為 NULL 或空。

使用快慢指標找到中間的節點。

indir 指標一個迴圈走到下個節點（一個節點）， fast 指標一個迴圈走到下下個節點（兩個節點)。
當 fast = head (q_size is even) 或 fast->next = head (q_size is odd) 時，fast 已走 n 個節點， *indir 指向第
$n / 2$ 節點，即為中間的節點 (0-based indexing)。
- 若 q_size = 6, fast 停在 5th 節點，*indir 指向 3th 節點。
- 若 q_size = 5, fast 停在 3th 節點，*indir 指向 2th 節點。
list_del() 移除要刪除的節點，用 list_entry() 找到節點位置，再釋放空間。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head **indir = &head->next, *fast = head->next;
    for (; fast != head && fast->next != head; fast = fast->next->next)
        indir = &(*indir)->next;
    struct list_head *del_node = *indir;
    list_del_init(del_node);
    element_t *del_e = list_entry(del_node, element_t, list);
    q_release_element(del_e);
    return true;
}

`q_delete_dup`

若佇列為 NULL 回傳 false 。
用 list_for_each_entry_safe() ，因為它允許在走訪佇列時刪除節點。

若是 str 與 node->value 字串相同。移除 node 並釋放空間。否則將 node->vale 複製給 str ，成為下一個要比較的字串。
- 因為使用此函式的佇列須為已排序好的狀態，有相同字串的節點一定相鄰。一旦發現下個節點字串不同，目前節點的字串便不會再後續出現，不須再比較。
經由迴圈，會將 n 個有相同字串的節點的後 n-1 個節點刪除，因為第一次偵測到存在相同字串 str 時，同時至少有兩個節點，前一個是更新 str 時走訪，目前的節點是發現重複字串且將被刪除的節點，後續重複節點也被走訪後刪除。
為了刪除第一個節點，再刪除目前節點後檢查 str 和 next->value，若是不同，表示重複的 n-1 個節點已被刪除完畢，此時 next 的前一個節點就是重複的第一個節點（兩節點之前的其他節點都被移除），用 list_entry() 取得該節點 first_dup ，移除並釋放空間。
變數
- str 存目前比要對的字串。
- node 目前的節點，可被 delete 。
- next , node 的下一個節點。
- first_dup ， n 個有相同字串的節點中的第一個節點。

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    element_t *first_dup, *node, *next;
    char *str = malloc(sizeof(char) * 1024);
    list_for_each_entry_safe (node, next, head, list) {
        if (strcmp(str, node->value) == 0) {
            list_del_init(&node->list);
            q_release_element(node);
            if (strcmp(str, next->value) != 0) {
                /* delete the frist node that have duplicate string */
                first_dup = list_entry(next->list.prev, element_t, list);
                list_del_init(&first_dup->list);
                q_release_element(first_dup);
            }
        } else {
            memcpy(str, node->value, strlen(node->value) + 1);
        }
    }
    free(str);
    return true;
}

改進：
將 str 指標指向目前比對的節點的 value ，取代原本的 malloc 和 memcpy ，減省記憶體空間。初始化則改為指向 \0 。

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    element_t *node, *next;
    char *str = "\0";
    list_for_each_entry_safe (node, next, head, list) {
        if (strcmp(str, node->value) == 0) {
            ...
            if (strcmp(str, next->value) != 0) {
                /* delete the frist node that have duplicate string */
                element_t *first_dup = list_entry(next->list.prev, element_t, list);
                list_del_init(&first_dup->list);
                q_release_element(first_dup);
                str = "\0";
            }
        } else {
            str = node->value;
        }
    }
    return true;
}

`q_swap`

若佇列為 NULL 、空，或只有一個節點，則回傳，不須 swap 。
根據 list_for_each_safe 迴圈，加上 safe != head 的條件，用來在節點為奇數時，剩下最後一個時停止迴圈。
交換節點位置：

safe 後移一個節點，原本 safe 的位置為 node->next ，交換 node 和 node->next 兩節點。
更新連接 node->prev 和 node->next 。
更新連接 node 和 node->next 。
更新連接 node 和 safe 。

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *node, *safe;
    for (node = head->next, safe = node->next; node != head && safe != head;
         node = safe, safe = node->next) {
        safe = safe->next;
        node->prev->next = node->next;
        node->next->prev = node->prev;
        node->prev = node->next;
        node->next->next = node;
        safe->prev = node;
        node->next = safe;
    }
}

`q_reverse`

確認佇列是否為 NULL 或空。
用 list_for_each_safe 走訪節點，交換 node 的兩個指標 node->prev node-。next 指向的位址。因為 list_for_each_safe 是從第一個節點開始，迴圈結束後交換 head 的兩個指標 prev next 指向的位址（此時 node == head）。

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

`q_sort`

若佇列為 NULL 、空或只有一個節點，則不做排序。
根據 Quick sort 實作排序，將傳入的第一個節點 head 當作比較的基準值，數值小的節點移動到 head 前，數值相同或大於則維持原位。再用遞迴繼續排序 head 的左右子佇列。
用 prev 和 next 兩個指標的指標操作。

立即回傳，不做迴圈
- tail->next == head 表示上一層遞迴後左子佇列或右佇列為空。
- head == tail 表示上一層遞迴後左子佇列或右佇列只有移的節點。
迴圈
- 初始 prev next 都指向 head 。
- 若 *next->next value 小於 head value ，移到 *prev 節點的前面，然後 prev 指標指向該節點。
- 否則（*next->next value 大於等於 head value）， next 指向下一個節點。
- 若 *next == tail （*prev == tail）表示此子佇列已比較完所有節點且最後一個節點大於等於（小於）head 。
遞迴呼叫
- prev 和 next 再比較後都會指向比較後的節點，因此分別作為左子佇列的 head 和右子佇列 tail 。

void sort(struct list_head *head, struct list_head *tail)
{
    if (tail->next == head || head == tail)
        return;
    struct list_head **prev = &head, **next = &head;
    char *head_str = list_entry(head, element_t, list)->value;
    for (; (*next) != tail && (*prev) != tail;) {
        char *str = list_entry((*next)->next, element_t, list)->value;
        if (strcmp(str, head_str) < 0) {
            (*prev)->prev->next = (*next)->next;
            (*next)->next->prev = (*prev)->prev;
            (*prev)->prev = (*next)->next;
            (*next)->next = (*next)->next->next;
            (*next)->next->prev = *next;
            (*prev)->prev->next = *prev;
            prev = &(*prev)->prev;
        } else {
            next = &(*next)->next;
        }
    }
    sort(*prev, head->prev);
    sort(head->next, *next);
    return;
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    sort(head->next, head->prev);
}

參考資訊

共筆格式參考：共筆示範

2022q1 Homework1 (lab0)

實驗環境

作業要求

開發過程

佇列架構

lish.h 巨集參考

針對佇列的實作

q_new

q_free

q_insert_head

更新：

q_insert_tail

更新：

gen_element

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort