2023q1 Homework1 (lab0)

contributed by < CYT701 >

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
    CPU family:          6
    Model:               78
    Thread(s) per core:  2
    Core(s) per socket:  2
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         2800.0000
    CPU min MHz:         400.0000
    BogoMIPS:            4800.00

---

開發過程

q_new

建立新的佇列並呼叫 malloc 動態配置記憶體，依要求此佇列的 next 與 prev 指標都指向自己，利用 list.h 中的 INIT_LIST_HEAD 來建立此 queue

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *q_head = malloc(sizeof(*q_head));
    if (!q_head) 
        return NULL;
    INIT_LIST_HEAD(q_head);
    return q_head;
}

q_free

list_for_each_safe 會從 l->next 開始遍歷所有節點，在每個節點都用 list_del 將節點從串列中移走並釋放記憶體，最後因為是從 l->next 開始遍歷，所以要記得釋放 l

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if(!l)
        return;
    struct list_head *cur_node;
    struct list_head *safe;
    list_for_each_safe(cur_node,safe,l)/*go over nodes from (l->next) to the end of list*/
    {
        list_del(cur_node);/*remove cur_node from list*/
        /*struct list_head *next = cur_node->next;
          struct list_head *prev = cur_node->prev;
          next->prev = prev;
          prev->next = next;*/
        free(cur_node);
    }
    free(l);
}

更新為使用 list_for_each_entry_safe ，能夠對整個 element_t 作改動

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *cur_node;
    element_t *safe;
    list_for_each_entry_safe (cur_node, safe, l, list) {
        list_del(&cur_node->list);   /* remove link of cur_node */
        q_release_element(cur_node); /* release cur_node */
    }
    free(l);
}

q_insert_head / q_insert_tail

不確定 char *s 是什麼用途，感覺用不到

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if(!head)
        return false;
    struct list_head *node = malloc(sizeof(*node));
    list_add(node,head);
    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if(!head)
        return false;
    struct list_head *node = malloc(sizeof(*node));
    list_add_tail(node,head);
    return true;
}

已找出問題點， list_head 這個結構包含在 element_t 中，而 element_t 中的 value 就是 char 型態，所以在插入新元素時應考慮 element_t 而非單純的串列，故先新增一個 new_element 並取得字串 s 的長度存於 len 中，再將字串 s 複製到 new_element->value ，並將 new_element->list 加入到 head 中

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *new_element = malloc(sizeof(element_t));
    new_element->value = malloc(sizeof(s)));
    strcpy(new_element->value, s);
    list_add(&new_element->list, head);
    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *new_element = malloc(sizeof(element_t));
    new_element->value = malloc(sizeof(s));
    strcpy(new_element->value, s);
    list_add_tail(&new_element->list, head);
    return true;
}

尚未解決的錯誤

Dangerous function detected in /home/cyt/linux2023/lab0-c/queue.c
46:    strcpy(new_element->value, s);
59:    strcpy(new_element->value, s);

已解決如下
Common vulnerabilities guide for C programmers 中提到 strcpy 並不會檢查暫存器的長度，且可能會覆蓋預期目標地址的連續記憶體空間，這表示 strcpy 並不是安全的動作，應使用 strlcpy 或 strncpy

• strlcpy (較推薦的方法)
  • 在 BSD system 中才有定義此函數，上述資料來源有說明如何自行定義
• strncpy （可用，但不一定會以 '\0' 作為字串結尾）

若給定 BUFFER_SIZE = 3, dst[BUFFER_SIZE], src[] = abcdef
    使用 strlcpy(dst,src,BUFFER_SIZE) 會得到 dst 為 ab\0
    使用 strncpy(dst,src,BUFFER_SIZE) 會得到 dst 為 abc
若給定 BUFFER_SIZE = 10, dst[BUFFER_SIZE], src[] = abcdef
    使用 strlcpy(dst,src,BUFFER_SIZE) 會得到 dst 為 abcdef\0
    使用 strncpy(dst,src,BUFFER_SIZE) 會得到 dst 為 abcdef\0\0\0\0

根據上述，修改程式碼如下，加入了自定義的 strlcpy 函數

測試 malloc failure 時發生錯誤

#ifndef strlcpy
#define strlcpy(dst, src, sz) snprintf((dst), (sz), "%s", (src))
#endif

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *new_element = malloc(sizeof(element_t));
    new_element->value = malloc(sizeof(s));
    strlcpy(new_element->value, s, sizeof(&new_element->value));
    list_add(&new_element->list, head);
    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *new_element = malloc(sizeof(element_t));
    new_element->value = malloc(sizeof(s));
    strlcpy(new_element->value, s, sizeof(&new_element->value));
    list_add_tail(&new_element->list, head);
    return true;
}

+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-11-malloc	0/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-12-malloc	0/6

由於這兩筆測資是在測試 malloc failure ，而我的程式碼中並未對 malloc 失敗的情況進行處理，所以在每次動態配置記憶體時，如果發生錯誤就會產生 segmentation fault ，於是在每次動態配置記憶體時都加入了判斷條件檢查是否成功，即可通過測資

字串並未完全加入佇列中

#ifndef strlcpy
#define strlcpy(dst, src, size) snprintf((dst), (size), "%s", (src))
#endif

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element) {
        return false;
    }
    new_element->value = malloc(sizeof(s));
    if (!new_element->value) {
        return false;
    }
    strlcpy(new_element->value, s, sizeof(&new_element->value));
    list_add(&new_element->list, head);
    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element) {
        return false;
    }
    new_element->value = malloc(sizeof(s));
    if (!new_element->value) {
        return false;
    }
    strlcpy(new_element->value, s, sizeof(&new_element->value));
    list_add_tail(&new_element->list, head);
    return true;
}

+++ TESTING trace trace-07-string:
# Test of truncated strings
ERROR: Removed value aardvar != expected value aardvark_bear_dolphin_gerbil_jaguar
ERROR: Removed value meerkat != expected value meerkat_panda_squirrel_vulture_wolf
ERROR: Removed value meerkat != expected value meerkat_panda_squirrel_vulture
ERROR: Removed value aardvar != expected value aardvark_bear_dolphin_gerbil
ERROR: Removed value aardvar != expected value aardvark_bear_dolphin
Error limit exceeded.  Stopping command execution
---	trace-07-string	0/6

這邊的問題出在 new_element->value = malloc(sizeof(s)); 這行，因為如果直接動態配置 sizeof(s) 則只會配置 char 的大小 8 給 new_element->value ，又因為使用 strlcpy 所以字串的最後一個字元會是 \0 ，故實際印出的只有 7 個字元

修改方法則是先宣告一個 int 變數 length ，並利用 strlen 取得 s 的字串長度，再利用 new_element->value = malloc(sizeof(char) *length); 來動態配置

並非以 constant time 實作

#ifndef strlcpy
#define strlcpy(dst, src, size) snprintf((dst), (size), "%s", (src))
#endif

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element) {
        return false;
    }
    int length = strlen(s) + 1;
    new_element->value = malloc(sizeof(char) *length);
    if (!new_element->value) {
        free(new_element);
        return false;
    }
    strlcpy(new_element->value, s, length);
    list_add(&new_element->list, head);
    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element) {
        return false;
    }
    int length = strlen(s) + 1;
    new_element->value = malloc(sizeof(char) *length);
    if (!new_element->value) {
        free(new_element);
        return false;
    }
    strlcpy(new_element->value, s, length);
    list_add_tail(&new_element->list, head);
    return true;
}

猜測這裡出現的問題是 strlen 的時間複雜度為 O(n) ，導致無法以常數時間執行 insert

尚未想到解法，參考其他同學的作法，有些人使用 strdup 複製字串，可以自動配置記憶體，說不定就能避免這個情況
如果要使用 strlcpy 似乎就一定要先計算出字串長度，待補充

q_remove_head / q_remove_tail

一開始沒有檢查 head 是否為空，但後來發現如果有對空佇列進行操作時會無法處理，於是在函式開始時加上檢查條件

建立 rm_element ，利用 list_first_entry 或 list_last_entry 來取得所要求的元素，利用 list_del 將其從佇列中移走（在 queue.h 中有強調在這裡只需要 unlink 不需要 free ），再利用之前定義好的 strlcpy 將 rm_element->value 複製到 sp

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *rm_element = list_first_entry(head, element_t, list);
    list_del(&rm_element->list);
    if (sp) {
        strlcpy(sp, rm_element->value, bufsize);
    }
    return rm_element;
}

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *rm_element = list_last_entry(head, element_t, list);
    list_del(&rm_element->list);
    if (sp) {
        strlcpy(sp, rm_element->value, bufsize);
    }
    return rm_element;
}

q_size

利用 list_for_each 走訪所有節點，每走過一個節點就讓 count++ ，回傳 count

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    int count = 0;
    struct list_head *cur_node;
    list_for_each (cur_node, head)
        count = count + 1;
    return count;
}

q_delete_mid

想法很單純，就是利用前面做的 q_size 來計算出 mid ，由於是刪除中間的元素，且如果有偶數個元素時取其下界，奇數個就刪除中間的元素

題意理解有誤

/* Delete the middle node in queue */
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;
    int mid = q_size(head) / 2 + q_size(head) % 2;
    int count = 0;
    struct list_head *cur_node;
    struct list_head *safe;
    list_for_each_safe (cur_node, safe, head) {
        count = count + 1;
        if (count == mid) {
            list_del(cur_node);
            q_release_element(list_entry(cur_node, element_t, list));
            return true;
        }
    }
    return false;
}

打一半突然覺得怪怪的，回去看 queue.h 發現題目是要求用 0-based indexing ，並取第 ⌊n / 2⌋ 個元素為中間，所以我是用錯誤的計算方式但不小心算出正確答案，程式碼應修正如下

/* Delete the middle node in queue */
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;
    int mid = (q_size(head) - 1) / 2; /*middle of 0-based indexing*/
    int count = -1;                   /*count 0 at first node*/
    struct list_head *cur_node;
    struct list_head *safe;
    list_for_each_safe (cur_node, safe, head) {
        count = count + 1;
        if (count == mid) {
            list_del(cur_node);
            q_release_element(list_entry(cur_node, element_t, list));
            return true;
        }
    }
    return false;
}

q_delete_dup

利用 strcmp 檢查 cur_node 和 safe 是否相同，若相同則刪除 cur_node ，由於 list_for_each_entry_safe 的定義，接下來 cur_node = safe, safe = cur_node->next，所以不會因為刪除 cur_node 而導致錯誤

無法正確刪除元素

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    element_t *cur_node;
    element_t *safe;
    list_for_each_entry_safe (cur_node, safe, head, list) {
        if (strcmp(cur_node->value, safe->value) == 0) {
            list_del(&cur_node->list);
            q_release_element(cur_node);
        }
    }
    return true;
}

上述程式碼出現的問題是，由於題目的要求是只要字串重複的節點就要一個不留的刪除，而不是保留其中一個，所以在原本的程式碼中加入了布林值 is_dup 用以記錄 cur_node 是否為重複的字串

出現 segmentation fault

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    bool is_dup = false; /*check if cur_node is duplicate*/
    element_t *cur_node;
    element_t *safe;
    list_for_each_entry_safe (cur_node, safe, head, list) {
        if (strcmp(cur_node->value, safe->value) == 0) {
            is_dup = true;
            list_del(&cur_node->list);
            q_release_element(cur_node);
        } else if (is_dup) { /*cur_node is duplicate, delete it*/
            is_dup = false;
            list_del(&cur_node->list);
            q_release_element(cur_node);
        }
    }
    return true;
}

發現問題出在使用 strcmp 檢查 cur_node 與 safe 之前，應先檢查 safe 是否已經走到 head ，否則直接使用 safe->value 會導致 segmentation fault

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    bool is_dup = false; /*check if cur_node is duplicate*/
    element_t *cur_node;
    element_t *safe;
    list_for_each_entry_safe (cur_node, safe, head, list) {
        if (&safe->list != head && strcmp(cur_node->value, safe->value) == 0) {
            is_dup = true;
            list_del(&cur_node->list);
            q_release_element(cur_node);
        } else if (is_dup) { /*cur_node is duplicate, delete it*/
            is_dup = false;
            list_del(&cur_node->list);
            q_release_element(cur_node);
        }
    }
    return true;
}

q_swap

利用 list_for_each_safe 遍歷整個佇列，每次都將 cur_node 移動到 safe 後面即可完成交換

swap 結果不如預期

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;
    struct list_head *cur_node;
    struct list_head *save;
    list_for_each_safe (cur_node, save, head) {
        list_move(cur_node, save);
    }
}

在檢查的時候發現這樣做會出現問題，因為在 list_for_each_safe 中，往下一個節點前進時使用了 cur_node = safe, safe = cur_node->next ，但是在這之前由於做了 list_move(cur_node, save) ，也就是 cur_node 會在 safe->next ，此時如果作 cur_node = safe, safe = cur_node->next ，則會把 safe 與 cur_node 對調，不能達到原本預期的兩兩交換效果

故調整 list_for_each_safe 的寫法，將原本 cur_node = safe, safe = cur_node->next 改為 cur_node = cur_node->next, safe = cur_node->next

swap 結果不如預期

/* 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 *cur_node;
    struct list_head *safe;
    for (cur_node = (head)->next, safe = cur_node->next; cur_node != (head);
         cur_node = cur_node->next, safe = cur_node->next) {
        list_move(cur_node, safe);
    }
}

在使用 ./qtest 檢查時發現結果仍然不如預期，且只有在奇數個元素時才會出現問題，發現問題出在 for 迴圈中判斷迴圈終止條件時只判斷了 cur_node != head ，應加入 safe != head 才能夠正確判斷

/* 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 *cur_node;
    struct list_head *safe;
    for (cur_node = (head)->next, safe = cur_node->next;
         cur_node != (head) && safe != (head);
         cur_node = cur_node->next, safe = cur_node->next) {
        list_move(cur_node, safe);
    }
}

q_reverse

利用 list_for_each_safe 走訪所有節點，每次都將當前節點移動到 head，即可完成反轉

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *cur_node;
    struct list_head *safe;
    list_for_each_safe (cur_node, safe, head) {
        list_move(cur_node, head);
    }
}

q_reverseK

反轉方式與上述相同，加入了 count 來計算走過得節點數，達到 k 時使用 list_cut_position ，將佇列切開後利用前面實作的 q_reverse 反轉，再接回原本的位置上

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;
    LIST_HEAD(temp_head);
    struct list_head *cur_node;
    struct list_head *safe;
    struct list_head *from = head;
    int count = 0;
    list_for_each_safe (cur_node, safe, head) {
        count = count + 1;
        if (count == k) {
            list_cut_position(&temp_head, from, cur_node);
            q_reverse(&temp_head);
            list_splice_init(&temp_head, from);
            count = 0;
            from = safe->prev;
        }
    }
}

q_sort

根據 你所不知道的 C 語言: linked list 和非連續記憶體中對於 merge sort 的實作，以及 Risheng1128 ， seasonwang0905 ， Lichiiiii 的程式碼
使用三個 function 來完成

/* Sort elements of queue in ascending order */
struct list_head *merge_two_list(struct list_head *l1, struct list_head *l2)
{
    struct list_head *temp = NULL;
    struct list_head **indirect = &temp;
    for (struct list_head **node = NULL; l1 && l2; *node = (*node)->next) {
        element_t *e1 = list_entry(l1, element_t, list);
        element_t *e2 = list_entry(l2, element_t, list);
        if (strcmp(e1->value, e2->value) < 0)
            node = &l1;
        else
            node = &l2;
        *indirect = *node;
        indirect = &(*indirect)->next;
    }
    *indirect = (struct list_head *) ((u_int64_t) l1 | (u_int64_t) l2);
    return temp;
}
struct list_head *merge_sort(struct list_head *head)
{
    if (!head || !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;
    mid = slow->next;
    slow->next = NULL;
    struct list_head *left = merge_sort(head);
    struct list_head *right = merge_sort(mid);
    return merge_two_list(left, right);
}
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    head->prev->next = NULL;
    head->next = merge_sort(head->next);
    struct list_head *current = head, *next = head->next;
    while (next) {
        next->prev = current;
        current = next;
        next = next->next;
    }
    current->next = head;
    head->prev = current;
}

q_descend

參照 list_for_each_entry_safe 的寫法，由 head->prev 開始反向檢查，每當 cur_element 大於 prev_element 時，就將 prev_element 刪除，但是如果直接刪除 prev_element 的話會導致 for 迴圈出現錯誤，所以在迴圈中以 temp 暫存 prev_element ，將 prev_element 指向 cur_element ，再刪除 temp

Segmentation fault

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head) {
        return 0;
    }

    element_t *cur_element;
    element_t *prev_element;
    for (cur_element = list_entry((head)->prev, element_t, list),
        prev_element = list_entry(cur_element->list.prev, element_t, list);
         &cur_element->list != (head); cur_element = prev_element,
        prev_element = list_entry(prev_element->list.prev, element_t, list)) {
        if (strcmp(cur_element->value, prev_element->value) > 0) {
            element_t *temp = prev_element;
            prev_element = cur_element;
            list_del(&temp->list);
            q_release_element(temp);
        }
    }
    return q_size(head);
}

與 delete_dup 的錯誤相同，未檢查 prev_element 是否已經走到 head，加上判斷條件就正確了

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head) {
        return 0;
    }

    element_t *cur_element;
    element_t *prev_element;
    for (cur_element = list_entry((head)->prev, element_t, list),
        prev_element = list_entry(cur_element->list.prev, element_t, list);
         &cur_element->list != (head); cur_element = prev_element,
        prev_element = list_entry(prev_element->list.prev, element_t, list)) {
        if (&prev_element->list != head &&
            strcmp(cur_element->value, prev_element->value) > 0) {
            element_t *temp = prev_element;
            prev_element = cur_element;
            list_del(&temp->list);
            q_release_element(temp);
        }
    }
    return q_size(head);
}

q_merge

/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head)) {
        return 0;
    }
    if (list_is_singular(head)) {
        return list_entry(head->next, queue_contex_t, chain)->size;
    }
    queue_contex_t *merged_list = list_entry(head->next, queue_contex_t, chain);
    struct list_head *node = NULL, *safe = NULL;
    list_for_each_safe (node, safe, head) {
        if (node == head->next) {
            continue;
        }
        queue_contex_t *temp = list_entry(node, queue_contex_t, chain);
        list_splice_init(temp->q, merged_list->q);
    }
    q_sort(merged_list->q);
    return merged_list->size;
}

make test 評分結果

---	TOTAL		95/100