Try   HackMD

2022q1 Homework1 (lab0)

contributed by < komark06 >

開發環境

$ 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:                   43 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      23
Model:                           8
Model name:                      AMD Ryzen 5 2600 Six-Core Processor
Stepping:                        2
Frequency boost:                 disabled
CPU MHz:                         3500.000
CPU max MHz:                     3500.0000
CPU min MHz:                     1550.0000
BogoMIPS:                        6999.18
Virtualization:                  AMD-V
L1d cache:                       192 KiB
L1i cache:                       384 KiB
L2 cache:                        3 MiB
L3 cache:                        16 MiB
NUMA node0 CPU(s):               0-11

作業要求

  • 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 得知實作手法;

queue.c實作

q_new 實作

q_new: 建立新的「空」佇列。
根據linux2022-lab0的定義： 「空」(empty) 的佇列是指向有效結構，但開頭 (head) 的值為 NULL

定義都有了，那就先看 queue.h 的函式宣告：

struct list_head *q_new();

由於函式不需要參數，個人偏好以下寫法：

struct list_head *q_new(void);

加入 void 後，可以避免不必要的參數傳遞。如果傳遞了參數，編譯器也可以偵測並報錯。但由於無法變更 queue.h，所以維持原樣。
q_new實作：

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    head->next = NULL;
    head->prev = NULL;
    return head;
}

以上實作透過 qtest 裡的 new 檢查後，會出現錯誤。

$ ./qtest 
cmd> new
ERROR:  Queue is not doubly circular

說明佇列必須要是雙向環狀鏈結串列。改為以下程式碼：

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

INIT_LIST_HEAD 函式位於 list.h，是 linux/list.h 簡化版的實作。差異在於 WRITE_ONCE 的使用(詳見： Linux 核心原始程式碼)。以下是 list.h 的 INIT_LIST_HEAD:






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

初始化 list_head，將 head 的成員 next 和 prev 都指向 head。

再一次用 qtest 測試，成功通過測試。

$ ./qtest 
cmd> new
l = []

q_free 實作

在進入如何實作 q_free 前，必須先確定要如何建立 element_t 型態的物件 (佇列的元素)，根據 queue.h，element_t 包含一個字串和 list_head 結構體。

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

直觀的做法，會先為 element_t 配置記憶體，再為字串配置記憶體。
以下情況不考慮 malloc 失敗的情況：

element_t *e_new(const char *s)
{
    element_t *ne = malloc(sizeof(element_t));
    size_t len = strlen(s);
    ne->value = malloc(len + 1);
    strncpy(ne->value, s , len);
    ne->value[len] = '\0';
    return ne;
}

但是參考過 Redis 的字串函式庫 SDS 後，決定只呼叫 malloc 一次，便能分配 element_t 結構體與字串。這樣的好處是，增加 cache hit 的機會。改成以下程式碼：

static inline element_t *e_new(const char *s)
{
    size_t len = strlen(s);
    element_t *ne = malloc(sizeof(element_t) + len + 1);
    if (!ne)
        return NULL;
    ne->value = (char *) ne + sizeof(element_t);
    strncpy(ne->value, s, len);
    ne->value[len] = '\0';  // Make sure string is Null terminated.
    return ne;
}

TODO: 設計實驗來說明 cache 效益的討論

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

知道如何建立 element_t 型態的物件後，就可以著手 q_free 了。

void q_free(struct list_head *l)
{
    element_t *obj, *save;
    list_for_each_entry_safe (obj, save, l, list) {
        free(obj);
    }
    free(l);
}

list_for_each_entry_safe，是為了避免釋放 obj 後，無法走向下一個元素。而多使用了 save 保存下一個元素的位置。

q_release_element free invalid pointer

static inline element_t *e_new(const char *s)
{
    size_t len = strlen(s);
    element_t *ne = malloc(sizeof(element_t) + len + 1);
    if (!ne)
        return NULL;
    ne->value = (char *) ne + sizeof(element_t);
    strncpy(ne->value, s, len);
    ne->value[len] = '\0';  // Make sure string is Null terminated.
    return ne;
}

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

比較 e_new 和 q_release_element，可預期 free(e->value) 會失敗，因為沒有在 e->value 配置 malloc。使用 qtest 測試 q_remove_head 後，錯誤確實出現了。

l = [1 2]
cmd> rh
ERROR: Attempted to free unallocated block.  Address = 0x562590b4df38
ERROR: Attempted to free unallocated or corrupted block.  Address = 0x562590b4df38
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
Aborted (core dumped)

free invalid pointer 可以透過以下程式碼解決：

void q_release_element(element_t *e)
{
    free(e);
}

但在 queue.c 註解提到不能更動 q_release_element，所以將 e_new 和 q_free 改成兩次 malloc 的版本。此外，考量輸入字串不是 Null-terminated string 的情況。將 strlen 改為 strnlen (老師建議)。

#define MAX_STR_SIZE \
    1024  // It stands for max string size that is used for strnlen.

static inline element_t *e_new(const char *s)
{
    element_t *ne = malloc(sizeof(element_t));
    if (!ne)
        goto ele_Fail;
    size_t len = strnlen(s, MAX_STR_SIZE);
    ne->value = malloc(len + 1);
    if (!ne->value)
        goto val_Fail;
    strncpy(ne->value, s, len);
    ne->value[len] = '\0';
    return ne;
val_Fail:
    free(ne);
ele_Fail:
    return NULL;
}

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *obj, *save;
    list_for_each_entry_safe (obj, save, l, list) {
        free(obj->value);
        free(obj);
    }
    free(l);
}

q_insert_head 和 q_insert_tail 實作

有了 e_new 後，要插入元素就變得簡單許多，只要考量插入的位置，並使用對應的函式即可。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ne = e_new(s);
    if (!ne)
        return false;
    list_add(&ne->list, head);
    return true;
}

list_add 將元素插入佇列的開頭，需要注意，用 & 取出 list_head 的地址

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ne = e_new(s);
    if (!ne)
        return false;
    list_add_tail(&ne->list, head);
    return true;
}

與 q_insert_head 雷同，換成 list_add_tail 即可。

q_remove_head 和 q_remove_tail 實作

注意到 q_remove_head 只要 remove 就好，所以不用額外 free。使用 list_first_entry 和 list_last_entry 取代 container_of，增加程式碼可讀性。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *obj = list_first_entry(head, element_t, list);
    list_del(&obj->list);
    if (sp) {
        strncpy(sp, obj->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return obj;
}

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *obj = list_last_entry(head, element_t, list);
    list_del(&obj->list);
    if (sp) {
        strncpy(sp, obj->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return obj;
}

q_size 實作

在 作業 就有提供程式碼了，稍微改一下變數名字。

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

q_delete_mid 實作

透過指標前後走訪，就能找到中間節點。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *tail = head->prev;
    for (struct list_head *start = head->next;
         start->next != tail && start != tail;
         start = start->next, tail = tail->prev)
        ;
    list_del(tail);
    q_release_element(container_of(tail, element_t, list));
    return true;
}

q_delete_dup 實作

透過兩個節點的比較，來刪除重複的節點。最後還會剩下一個節點並未刪除。所以加入 del 來刪除最後一個節點。







G



n1

1

 



n2

1

 



n1:c->n2






n3

1

 



n2:c->n3






none



n3:c->none













G



n2

1

 



n3

1

 



n2:c->n3






none



n3:c->none













G



n3

1

 



none



n3:c->none







bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    element_t *n, *s;
    bool del = false;
    list_for_each_entry_safe (n, s, head, list) {
        if (n->list.next != head &&
            !strncmp(n->value, s->value, MAX_STR_SIZE)) {
            list_del(&n->list);
            q_release_element(n);
            del = true;
        } else if (del) {
            list_del(&n->list);
            q_release_element(n);
            del = false;
        }
    }
    return true;
}

參考 blueskyson 的作法，加入一個指標指向前一個字串作比較。減少 branch 的時候，程式碼也更簡潔了。

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    element_t *n, *s;
    char *pval = "";
    list_for_each_entry_safe (n, s, head, list) {
        if (!strncmp(n->value, pval, MAX_STR_SIZE)) {
            list_del(&n->list);
            q_release_element(n);
        } else {
            pval = n->value;
        }
    }
    return true;
}

q_swap 實作

透過 list_move 實作， list_move 本質上就是先 list_del 再 list_add。需要注意的地方，是 cur 只需要移動一次就好，因為 cur 已經透過list_move 移動過一次了。







G



1

1

 



2

2

 



1:c->2






3

3

 



2:c->3






none



3:c->none






cur
cur



cur->1:s

經過 list_move 和 cur = cur->next：







G



1

1

 



3

3

 



1:c->3






2

2

 



2:c->1






none



3:c->none






cur
cur



cur->3:s






void q_swap(struct list_head *head)
{
    if (!head)
        return;
    for (struct list_head *cur = head->next; cur != head && cur->next != head;
         cur = cur->next)
        list_move(cur, cur->next);
}

q_reverse 實作

走訪每一個節點，將連結反向串連。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *cur = head->next;
    head->next = head->prev;
    head->prev = cur;
    while (cur != head) {
        struct list_head *temp = cur->next;
        cur->next = cur->prev;
        cur->prev = temp;
        cur = temp;
    }
}

q_sort 實作

使用 merge sort 實作，先將串列對半，直到剩下一個節點後，再合併。
透過快慢指標，將串列切成一半，分割的方法參考 jserv。

如果想將串列切成三分之一，只要讓快指標一次走三步即可。

static struct list_head *mergesort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *slow = head, *fast = head->next;
    for (; fast && fast->next; fast = fast->next->next, slow = slow->next)
        ;
    fast = slow->next;  // middle of list
    slow->next = NULL;

    struct list_head *left = mergesort(head), *right = mergesort(fast);
    return mergeTwoLists(left, right);
}

接下來就是合併了，這裡使用 strncmp，是延續 e_new 使用 strnlen，讓 srrcmp 不會因為非 Null-terminated string ，進入無限迴圈。這部分參考 jserv。

struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head;
    for (struct list_head **cur = NULL; L1 && L2; *cur = (*cur)->next) {
        if (strncmp(container_of(L1, element_t, list)->value,
                    container_of(L2, element_t, list)->value,
                    MAX_STR_SIZE) >= 0)
            cur = &L2;
        else
            cur = &L1;
        *ptr = *cur;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}
  • ISO/IEC 9899:TC2 [7.18.1.4] uintptr_t
    • The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer: uintptr_t These types are optional.

因此轉型成 uintptr_t 前，應該先轉型成 void*，相對的，從 uintptr_t 轉型成原本型態，也要先轉型成 void*，故上面的程式碼應該改成：

*ptr = (struct list_head *)(void*) ((uintptr_t)(void*) L1 | (uintptr_t)(void*) L2);

mergesort 和 mergeTwoLists 將串列當作單向串列，是由於 mergesort 完成前，大多數節點都會再次合併，與其花費時間維持環狀鏈結串列，不如等合併完，再補上環狀鏈結串列的特徵。這部分在 q_sort 實現。

void q_sort(struct list_head *head)
{
    if (!head || head->next == head->prev)
        return;
    head->prev->next = NULL;
    head->next = mergesort(head->next);
    struct list_head *ptr = head;
    for (; ptr->next; ptr = ptr->next)
        ptr->next->prev = ptr;
    ptr->next = head;
    head->prev = ptr;
}

trace-17-complexity

Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

自己的電腦上跑測試沒問題，不過在 Github Action 上顯示 q_insert_tail 錯誤。

ERROR: Probably not constant time

透過修改 traces/trace-17-complexity.cmd 分別測試 q_insert_tail, q_insert_head, q_remove_tail, q_remove_head。發現 q_insert_tail 其實沒問題，但 q_remove_tail 有時候無法通過測試，那就著手來改。
原先的 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 *obj = list_last_entry(head, element_t, list);
    list_del(head->prev);
    if (sp && bufsize) {
        strncpy(sp, obj->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return obj;
}

將第7行的 bufsize 去除，原先的用意是，避免無號整數取負值，造成不符預期的狀況。例如-1變成18446744073709551615(依照平台不同會有不同數值)。
成功召喚出皮卡丘了！


額外測試原版程式碼，竟然通過了。此外，拿一些同學通過 Github Action 的程式碼來測試，也會有錯誤產生。這部份的原因還有待商榷。
研讀 Linux 核心原始程式碼的 lib/list_sort.c(未完成)

Last changed by 
 
komark06
1
547

Read more

AD RMS

資訊保護技術

Jun 6, 2025
實作和管理 AD FS

允許跨組平台界限的身分識別、驗證和授權

Jun 6, 2025
AD CS

可讓組織部署 PKI 憑證架構

Jun 5, 2025
安裝及設定網域控制站

PDCEmulator

Jun 4, 2025
Read more from komark06
Published on HackMD