Try   HackMD

2025q1 Homework1 (lab0)

contributed by < blue76815 >

作業內容

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
  • 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
  • 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
  • HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
  • 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
  • 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
  • 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
  • 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
  • 避免使用不必要的 emoji 字元

開發環境

$ uname -a
Linux blue76815-tuf-gaming-fx504ge-fx80ge 6.8.0-45-generic #45-Ubuntu SMP PREEMPT_DYNAMIC Fri Aug 30 12:02:04 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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
架構：                    x86_64
  CPU 作業模式：          32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   12
  On-line CPU(s) list:    0-11
供應商識別號：            GenuineIntel
  Model name:             Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
    CPU 家族：            6
    型號：                158
    每核心執行緒數：      2
    每通訊端核心數：      6
    Socket(s):            1
    製程：                10
    CPU(s) scaling MHz:   34%
    CPU max MHz:          4100.0000
    CPU min MHz:          800.0000
    BogoMIPS:             4399.99

Virtualization features:  
  虛擬：                  VT-x
Caches (sum of all):      
  L1d:                    192 KiB (6 instances)
  L1i:                    192 KiB (6 instances)
  L2:                     1.5 MiB (6 instances)
  L3:                     9 MiB (1 instance)
NUMA:                     
  NUMA 節點：             1
  NUMA node0 CPU(s)：     0-11
Vulnerabilities:          
  Gather data sampling:   Mitigation; Microcode
  Itlb multihit:          KVM: Mitigation: VMX disabled
  L1tf:                   Mitigation; PTE Inversion; VMX conditional cache flush
                          es, SMT vulnerable
  Mds:                    Mitigation; Clear CPU buffers; SMT vulnerable
  Meltdown:               Mitigation; PTI
  Mmio stale data:        Mitigation; Clear CPU buffers; SMT vulnerable
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; IBRS
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prct
                          l
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointe
                          r sanitization
  Spectre v2:             Mitigation; IBRS; IBPB conditional; STIBP conditional;
                           RSB filling; PBRSB-eIBRS Not affected; BHI Not affect
                          ed
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Not affected

queue.c 實作

  • 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_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_reverseK: 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 LeetCode 25. Reverse Nodes in k-Group
  • q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;
  • q_ascend 及 q_descend: 參閱 LeetCode 2487. Remove Nodes From Linked List，注意節點間的順序
  • q_merge: 合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 LeetCode 23. Merge k Sorted Lists

q_new

此操作為建立新的「空」佇列，因此是建立 struct list_head head 頭端，而不是新建一個 element_t 節點

  1. 配置一個新 head
  2. 若配置失敗則回傳 NULL
  3. 調用 The Linux Kernel API INIT_LIST_HEAD()初始化head

Commit 71ffce9

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

q_free

  1. 調用 list_for_each_entry_safe 尋訪 struct list_head 環狀佇列
  2. list_del() 只是將 node 從其原本的 linked list 連接移除
  3. 還得用 q_release_element(node) 才能將節點記憶體釋放

Commit 71ffce9

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

    element_t *node = NULL, *tmp_node = NULL;
    list_for_each_entry_safe (node, tmp_node, l, list) {
        list_del(&node->list);
        q_release_element(node);
    }
    free(l);
}

q_insert_head

  1. malloc 配置新節點
  2. 將字串資料複製到 node->value
  3. list_add() 將指定的 node 插入到 linked list struct list_head head 的開頭

Commit 71ffce9

bool q_insert_head(struct list_head *head, char *s)
{
    if (s == NULL || head == NULL)
        return false;
    element_t *node = malloc(sizeof(element_t));
    if (node == NULL)
        return false;

    node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
    if (node->value == NULL) {
        q_release_element(node);
        return false;
    }
    memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
    memcpy(node->value, s, sizeof(char) * strlen(s));
    list_add(&node->list, head);
    return true;
}

注意事項

  1. 節點插入data 資料時，得用 element_t 才能配置
typedef struct {
    /* Pointer to array holding string.
     * This array needs to be explicitly allocated and freed
     */
    char *value;
    struct list_head list;
} element_t;

圖片來源：你所不知道的 C 語言: linked list 和非連續記憶體

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

  1. 要訪問 linked list 各別節點內的資料，可調用
list_entry(node, type, member)
list_first_entry(head, type, member)
list_last_entry(head, type, member)
  1. 配置 strlen(s) + 1 是因為
    Linux Programming Interface 查詢 strlen 有提到

DESCRIPTION

The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').

RETURN VALUE

The strlen() function returns the number of bytes in the string pointed to by s.

strlen() 計算字元個數到 null byte ('\0') 就停止，因此字數不包含 null byte ('\0')。
多加一格，是為了在字串結尾多填一格 NULL 值，
避免 strlen(const char str) 計算字串長度時，把字尾相鄰的記憶體殘值也列入字元個數

q_insert_tail

  1. malloc 配置新節點
  2. 將字串資料複製到 node->value
  3. 差別只在插入 link-list 時，得用 list_add_tail(&node->list, head); 插入到尾端

Commit 71ffce9

bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL || s == NULL)
        return false;

    element_t *node = malloc(sizeof(element_t));

    if (node == NULL)
        return false;


    node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
    if (node->value == NULL) {
        q_release_element(node);
        return false;
    }
    memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
    memcpy(node->value, s, sizeof(char) * strlen(s));
    list_add_tail(&node->list, head);
    return true;
}

q_remove_head

  • 調用 list_first_entry() ，取得 linked list 的開頭

Commit 7dc94e1

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;

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

    list_del_init(&(node->list));

    if (sp) {
        size_t length = strlen(node->value) + 1;
        length = length > bufsize ? bufsize : length;
        memset(sp, '\0', length);
        memcpy(sp, node->value, length - 1);
    }
    return node;
}

q_remove_tail

  • 調用 list_last_entry() ，取得 linked list 的結尾

Commit 1c58006

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head))
        return NULL;

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

    list_del_init(&(node->list));

    if (sp) {
        size_t length = strlen(node->value) + 1;
        length = length > bufsize ? bufsize : length;
        memset(sp, '\0', length);
        memcpy(sp, node->value, length - 1);
    }

    return node;
}

q_size

  1. 調用 list_for_each_entry_safe
  2. 尋訪 struct list_head 環狀佇列計次

Commit 71ffce9

int q_size(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return 0;

    int size = 0;
    struct list_head *node = NULL;

    list_for_each (node, head) {
        size++;
    }
    return size;
}

q_delete_mid

參考金刀的算法小册子 0876-链表的中间结点
改成快慢兩種指標做 Floyd’s Cycle detection

Commit 53c2ae4

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (head == NULL || list_empty(head))
        return false;
    
    struct list_head *fast = head->next;
    struct list_head *slow = head->next;
    while (fast!=head && fast->next !=head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    element_t *ele_node = list_entry(slow, element_t, list);
    list_del(slow);
    free(ele_node->value);
    free(ele_node);
    return true;
}

q_delete_dup

參考 SmallHanley 同學的方法

  1. 檢查 head 是否為 NULL，是則回傳 false。
  2. 用一個 bool 值 last_same_node 判斷相鄰重複的節點，是否已經刪除到最後一個。
  3. 呼叫 list_for_each_safe (node, tmp, head) 走訪每個節點
  4. 走訪節點時，此node內是儲存某 element_t 節點的記憶體位址，得用 list_entry(node, element_t, list) 和 list_entry(node, element_t, list) 才能解析出 element_t 節點內的 value 成員
  5. 判斷此 element_t 節點和下一個 element_t 節點的 value 是否相同，是則將 last_same_node 設為 true，然後從串列中移除此節點並釋放相關空間。
  6. 若 value 不同，而 last_same_node 依然是 true，代表此節點是相鄰重複的節點中的最後一個，將 last_same_node 設回 false 並釋放相關空間。
    例如 link-list 1==>1==>1==>2==>3
    當刪除到剩 1==>2==>3 時，此 1 節點就是相鄰重複節點中的最後一個

list_entry 介紹
内核双链表遍历：带 safe 和不带 safe 的区别

#define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)


#define list_for_each_safe(pos, n, head) \
        for (pos = (head)->next, n = pos->next; pos != (head); \
                pos = n, n = pos->next)

从两个接口的定义差别只看出，list_for_each_safe() 的定义多了一个参数 n，这个参数 n 用于缓存下一个节点，其余并没有什么逻辑上的差异。

所以寫 list_for_each_safe (node, tmp, head)
相當於用 node 節點 跑 for 迴圈

Commit 829bd87

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (head == NULL || list_empty(head))
        return false;
    struct list_head *node, *tmp;
    bool last_same_node = false;
    list_for_each_safe (node, tmp, head) {
        element_t *curr_element_t = list_entry(node, element_t, list);
        element_t *next_element_t = list_entry(node->next, element_t, list);
        if (node->next != head &&
            strcmp(curr_element_t->value, next_element_t->value) == 0) {
            last_same_node = true;
            list_del(node);
            free(curr_element_t->value);
            free(curr_element_t);
        } else if (last_same_node == true) {
            last_same_node = false;
            list_del(node);
            free(curr_element_t->value);
            free(curr_element_t);
        }
    }
    return true;
}

q_swap

在官方 linux/list.h 中，發現有 list_swap() 可調用

/**
 * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
 * @entry1: the location to place entry2
 * @entry2: the location to place entry1
 */
static inline void list_swap(struct list_head *entry1,
			     struct list_head *entry2)
{
	struct list_head *pos = entry2->prev;

	list_del(entry2);
	list_replace(entry1, entry2);
	if (pos == entry1)
		pos = entry2;
	list_add(entry1, pos);
}

調用 list_swap() 編譯時出現

$ make
  CC    queue.o
queue.c: In function ‘q_swap’:
queue.c:267:9: error: implicit declaration of function ‘list_swap’ [-Werror=implicit-function-declaration]
  267 |         list_swap(node,node->next);
      |         ^~~~~~~~~
cc1: all warnings being treated as errors
make: *** [Makefile:50：queue.o] 錯誤 1

發現我們 lab0 專案內的 list.h 中
沒有加入官方 linux/list.h 的 list_swap() 程式碼

於是我自己將官方 list_swap() 程式碼加在 lab0 專案內的 queue.c 中
再次編譯

$ make
  CC    qtest.o
In file included from qtest.c:16:
list.h: In function ‘list_swap’:
list.h:348:2: error: implicit declaration of function ‘list_replace’; did you mean ‘list_splice’? [-Werror=implicit-function-declaration]
  348 |  list_replace(entry1, entry2);
      |  ^~~~~~~~~~~~
      |  list_splice
cc1: all warnings being treated as errors
make: *** [Makefile:50：qtest.o] 錯誤 1

queue.c 中還要再補上 官方 linux/list.h list_replace()

/**
 * list_replace - replace old entry by new one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * If @old was empty, it will be overwritten.
 */
static inline void list_replace(struct list_head *old,
				struct list_head *new)
{
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}

編譯成功
Commit f1efcf0

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if ( head==NULL|| list_empty(head))
        return;

    struct list_head *node = head->next, *tmp_node;
    while (node != head && node->next != head) {
        tmp_node = node->next->next;//相鄰兩節點交換前，先備份第3個節點位址到 tmp_node 變數中
        list_swap(node, node->next);//相鄰兩節點交換
        node = tmp_node;//載入新的節點
    }
}

q_reverse

將 prev 與 next 兩個指標的內容交換(可藉由 tmp_node 暫存)

  1. struct list_head 為環狀佇列，當節點走訪一圈後就會回到 head 位址，利用此特點判斷 while(node!=head) 是否走訪一圈回到head

圖片來源：你所不知道的 C 語言: linked list 和非連續記憶體

  1. 先做 next_node=node->next ，備份好下個節點
  2. 每個節點逐一將 prev 與 next 兩個指標內儲存的地址交換(藉由 tmp_node 變數，暫存節點地址)
  3. 離開前，記得 head 節點的 prev 與 next 也要交換

Commit e8449fe

void q_reverse(struct list_head *head) {
    if ( head==NULL || list_empty(head)) {
        return;
    } 
    struct list_head *node=head->next,*next_node,*tmp_node;
    while(node!=head)//判斷是否走訪一圈回到 head
    {
	/* prev 與 next 交換前，先備份好下個節點*/	
       next_node=node->next;
		
       /*將 prev 與 next 兩個指標內儲存的地址交換*/	
       tmp_node=node->next;
       node->next=node->prev;
       node->prev = tmp_node; 
		
	/* 更新下一個節點*/
       node=next_node;
    } 
    /*離開前 記得 head 節點的 prev 與 next 也要交換*/
    tmp_node = head->next;
    head->next = head->prev;
    head->prev = tmp_node;      
}

q_reverseK

  1. 執行完 list_cut_position(&new_cut_list, origin_list, cut_node)，會形成兩個佇列。
  • new_cut_list： 收留要被剪切的節點的新鍊錶
  • origin_list： 要被剪切的舊鍊錶
  • cut_node：剪切入口

  1. 透過 q_reverse 反轉。
    q_reverse(&new_cut_list);

  2. 最後，透過 list_splice_init(&new_cut_list, origin_list) 將兩個佇列連結成一個佇列，並更新 origin_list 。
    origin_list 作用類似假的 head，紀錄下一次切分佇列和連結佇列的位置。

void q_reverseK(struct list_head *head, int k)
{
    if ( head==NULL || list_empty(head) || k <= 1) {
        return;
    } 
    struct list_head *cur, *safe, *origin_list = head;
	
    LIST_HEAD(new_cut_list);
    int count = 0;
    list_for_each_safe (cur, safe, head) {
        count++;
        if (count == k) {
	/* step1.
	執行完 list_cut_position(&new_cut_list, origin_list, cut_node)
	，會形成兩個佇列。*/			
            list_cut_position(&new_cut_list, origin_list, cur);
	/*step2.透過 q_reverse 反轉。 */			
            q_reverse(&new_cut_list);
	/*
	step3.最後，透過 list_splice_init(&new_cut_list, origin_list) 
	將兩個佇列連結成一個佇列，
	*/			
            list_splice_init(&new_cut_list, origin_list);
            count = 0;
	/* 並更新 origin_list 。 */
            origin_list = safe->prev;
        }
    }
}

q_descend

根據 LeetCode 2487. Remove Nodes From Linked List
函式功能:若左邊節點數值 < 右邊節點數值，則刪除左邊節點

  • list_del() 只是將 node 從其原本的 linked list 連接移除
    還得用 q_release_element(node) 才能將節點記憶體釋放

  • 使用 list_del() 和 q_release_element(node) 的好處，在於移除 link-list 節點時，不用煩惱如何將節點指向的 prev , next 位址做修正

  • q_descend 改從 linked list 尾端往回找，直到往回比較到 head 時，才停止

    • 因為若從 head 端開始比較 左邊節點數值 < 右邊節點數值，會頻繁的將 head 節點刪除替換掉（步驟變多，時間複雜度變高）
    • 所幸我們的 linked list 結構為 prev，next 雙向鍊結方向
    • 因此我們改成從 linked list 尾端往回比較節點，直到往回比較到 head 時，才停止
    • 這樣的優點是最多只移除1次 head 節點，不用重複多次步驟移除 head 節點

走訪整個 linked list 時，有考慮選用

list_for_each(node, head) 
list_for_each_entry(entry, head, member)

但是根據 你所不知道的 C 語言: linked list 和非連續記憶體-Linked list 在 Linux 核心原始程式碼

list_for_each

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

走訪整個 linked list。注意: node 和 head 不能在迴圈中被更改 (可能在多工環境中出現)，否則行為不可預期。

list_for_each_entry

#ifdef __LIST_HAVE_TYPEOF
#define list_for_each_entry(entry, head, member)                       \
    for (entry = list_entry((head)->next, __typeof__(*entry), member); \
         &entry->member != (head);                                     \
         entry = list_entry(entry->member.next, __typeof__(*entry), member))
#endif

走訪包含 struct list_head 的另外一個結構之 entry。node 和 head 不能在迴圈中被更改，否則行為不可預期。

使用上面這兩種 API node 和 head 不能在迴圈中被更改 (可能在多工環境中出現)，否則行為不可預期。

考慮到我們 q_descend 在走訪整個 linked list 時，會有 list head 移除的情況

因此改用

list_for_each_safe / list_for_each_entry_safe

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)
         
#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

透過額外的 safe 紀錄每個迭代 (iteration) 所操作的節點的下一個節點，因此目前的節點可允許被移走，其他操作則同為不可預期行為。

但是若從 head 端開始比較 左邊節點數值 < 右邊節點數值，
會頻繁的將 head 刪除替換掉（處理步驟變多，時間複雜度變高）

所幸我們的 linked list 結構為 prev，next 雙向鍊結方向，
因此我們改成從 linked list 尾端往回比較節點，
直到往回比較到 head 節點時，才停止，
這樣的優點是最多只移除1次 head 節點
不用重複多次步驟移除 head 節點

Commit ab7975a

/* 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 == NULL || list_empty(head) || list_is_singular(head)) {
		return 0;
	}
	// struct list_head *curr = head->prev, *next = curr->prev 從	linked list 尾端往回找，直到往回比較到head時，才停止 
	// 因為若從 head 端開始比較 左邊節點數值 < 右邊節點數值，會頻繁的將 head 刪除替換掉（步驟變多，時間複雜度變高）
	// 所幸我們的 linked list 結構為 prev，next 雙向鍊結方向，
	// 因此我們改成從 linked list 尾端往回比較節點，直到往回比較到head時，才停止，
	// 這樣的優點是最多只移除1次head節點
	// 不用重複多次步驟移除 head 節點	
	struct list_head *curr = head->prev;
	struct list_head *next = curr->prev; 
	while(next != head)
	{
		element_t *curr_entry = list_entry(curr, element_t, list);//取得節點資料
		element_t *next_entry = list_entry(next, element_t, list);		

		if (strcmp(curr_entry->value, next_entry->value) > 0) {
			list_del(next);// list_del() 只是將 node 從其原本的 linked list 連接移除
			q_release_element(next_entry);//還得用 q_release_element(node) 才能將節點記憶體釋放
		} else{
			curr = next;	
		}

		next = curr->prev; //從 linked list 尾端往回比較節點
	}
	return q_size(head);
}

驗證函式功能

leetcode 考題輸入的資料型態是 int val 數字變數

但是我們的 q_descend()，輸入的是 ASCII 字元或字串
因此輸入 cmd> it 13 時不是常數 13
而是2個ASCII 字元的字串1(0x31) 和 3(0x33)

因此將 cmd> it 13 改成單一字元的資料，
例如 ASCII 字元 9，就能符合 leetcode 考題結果

cmd> new
l = []
cmd> ih 5
l = [5]
cmd> it 2
l = [5 2]
cmd> it 9
l = [5 2 9]
cmd> it 3
l = [5 2 9 3]
cmd> it 8
l = [5 2 9 3 8]
cmd> descend
l = [9 8]
cmd>

q_ascend

釐清 q_ascend 定義
從 ./qtest help指令中，能查到

$ ./qtest
cmd> help
Commands:
...
  ascend                   | Remove every node which has a node with a strictly less value anywhere to the right side of it

  descend                  | Remove every node which has a node with a strictly greater value anywhere to the right side of it

ascend：刪除每個節點，只要該節點右側任意位置有一個值嚴格小於該值的節點

descend：刪除每個節點，只要該節點右側任意位置有一個嚴格大於該值的節點

回顧 q_descend

descend：刪除每個節點，只要該節點右側任意位置有一個嚴格大於該值的節點

參閱 LeetCode 2487. Remove Nodes From Linked List

Remove every node which has a node with a greater value anywhere to the right side of it.

/* 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 == NULL || list_empty(head) || list_is_singular(head)) {
        return 0;
    }
	struct list_head *curr = head->prev;
	struct list_head *next = curr->prev; 
	while(next != head)
	{
        	element_t *curr_entry = list_entry(curr, element_t, list);//取得節點資料
        	element_t *next_entry = list_entry(next, element_t, list);		
		
	    if (strcmp(curr_entry->value, next_entry->value) > 0) {
            list_del(next);//list_del() 只是將 node 從其原本的 linked list 連接移除
            q_release_element(next_entry);//還得用 q_release_element(node) 才能將節點記憶體釋放
        } else{
		curr = next;	
	}
            	
		next = curr->prev; //從 linked list 尾端往回比較節點
	}
    return q_size(head);
}

descend：刪除每個節點，只要該節點右側任意位置有一個嚴格大於該值的節點
是根據
if (strcmp(curr_entry->value, next_entry->value) > 0)

因此
ascend：刪除每個節點，只要該節點右側任意位置有一個值嚴格小於該值的節點
改成
if (strcmp(curr_entry->value, next_entry->value) < 0)
即可

Commit d0eff68

/* Remove every node which has a node with a strictly less value anywhere to
 * the right side of it */
int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (head == NULL || list_empty(head) || list_is_singular(head)) {
        return 0;
    }
    struct list_head *curr = head->prev;
    struct list_head *next = curr->prev;
    while (next != head) {
        element_t *curr_entry =
            list_entry(curr, element_t, list);  // 取得節點資料
        element_t *next_entry = list_entry(next, element_t, list);

        if (strcmp(curr_entry->value, next_entry->value) < 0) {
            list_del(next);  // list_del() 只是將 node 從其原本的 linked list
                             // 連接移除
            q_release_element(next_entry);  // 還得用 q_release_element(node)
                                            // 才能將節點記憶體釋放
        } else {
            curr = next;
        }

        next = curr->prev;  // 從 linked list 尾端往回比較節點
    }
    return q_size(head);
}

驗證 ascend 功能

$ ./qtest
cmd> new
l = []
cmd> ih 5
l = [5]
cmd> it 2
l = [5 2]
cmd> it 9
l = [5 2 9]
cmd> it 3
l = [5 2 9 3]
cmd> it 8
l = [5 2 9 3 8]
cmd> ascend
l = [2 3 8]
cmd>

比較

cmd> new
l = []
cmd> ih 5
l = [5]
cmd> it 2
l = [5 2]
cmd> it 9
l = [5 2 9]
cmd> it 3
l = [5 2 9 3]
cmd> it 8
l = [5 2 9 3 8]
cmd> descend
l = [9 8]
cmd>

q_sort（遞迴版）

參閱

Commit 4bf80c7

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (head == NULL || list_empty(head)) {
        return;
    }
    head->prev->next = NULL;
    head->next = mergesort_list(head->next,descend);
    struct list_head *ptr = head;
    while (ptr->next != NULL) {
        ptr->next->prev = ptr;
        ptr = ptr->next;
    }
    ptr->next = head;
    head->prev = ptr;
}

mergesort_list() 的詳細實做如下

//2025 年 新增 bool descend 項
// 用來判斷
// * @descend: whether or not to sort in descending order
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2 , bool descend)
{
    struct list_head *head = NULL;
    struct list_head **ptr = &head;
    for (; L1 && L2; ptr = &(*ptr)->next) {
        element_t *L1_element_t = list_entry(L1, element_t, list);
        element_t *L2_element_t = list_entry(L2, element_t, list);
        if ((strcmp(L1_element_t->value, L2_element_t->value) <= 0)!= descend) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}


/*
 * 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.
 */
static struct list_head *mergesort_list(struct list_head *head, bool descend)
{
    if (!head || !head->next || list_is_singular(head))
        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, descend), *right = mergesort_list(mid, descend);
    return mergeTwoLists(left, right, descend);
}

其中
if ((strcmp(L1_element_t->value, L2_element_t->value) <= 0)!= descend)

是參照 實做 ascend（）和 descend（）時的設計原理

// 遞增排序用
if (strcmp(curr_entry->value, next_entry->value) < 0)
來比較

/* Remove every node which has a node with a strictly less value anywhere to
 * the right side of it */
int q_ascend(struct list_head *head)
{
	if (strcmp(curr_entry->value, next_entry->value) < 0) {
		list_del(next);  // list_del() 只是將 node 從其原本的 linked list
						 // 連接移除
		q_release_element(next_entry);  // 還得用 q_release_element(node)
										// 才能將節點記憶體釋放
	} else {
		curr = next;
	}



}

// 遞減排序用
if (strcmp(curr_entry->value, next_entry->value) > 0)
來比較	

/* 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)
{
	if (strcmp(curr_entry->value, next_entry->value) > 0) {
		list_del(next);  // list_del() 只是將 node 從其原本的 linked list
						 // 連接移除
		q_release_element(next_entry);  // 還得用 q_release_element(node)
										// 才能將節點記憶體釋放
	} else {

	}

}

// 遞增排序用
if (strcmp(curr_entry->value, next_entry->value) < 0)
//來比較

// 遞減排序用
if (strcmp(curr_entry->value, next_entry->value) > 0)
//來比較	

//所以加入 `bool descend` 判斷式時，就能合併表示成
if ((strcmp(L1_element_t->value, L2_element_t->value) <= 0)!= descend) 
	
//用來切換 mode

q_merge

研讀 你所不知道的 C 語言: linked list 和非連續記憶體-Merge Sort 的實作

Commit 109b430

/* Merge all the queues into one sorted queue, which is in ascending/descending
 * order */
int q_merge(struct list_head *head, bool descend)
{
    // 1. 檢查 head 是否有效
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head)){
    // 只有一個元素就直接回傳該 queue 的大小
        queue_contex_t *single_node=list_entry(head->next, queue_contex_t, chain);
        return single_node->size;
    }

    // 2. 建立一個「暫存 list」及變數
    struct list_head tmp;
    INIT_LIST_HEAD(&tmp);

    int total_size = 0;
    queue_contex_t *entry;

    /*
     * 3. 逐一把 head 裏的所有 queue context 的佇列
     *    都 splice 到 tmp 這個暫存 list 中
     */
    list_for_each_entry (entry, head, chain) {
        // 將 entry->q 所有元素併到 tmp，並把 entry->q 清空
        list_splice_tail_init(entry->q, &tmp);
        total_size += entry->size;
        entry->size = 0;
    }

    // 4. 對暫存 list 進行排序（升冪或降冪由 descend 決定）
    q_sort(&tmp, descend);

    // 5. 將排序好的 list 塞回其中一個 queue (例如第一個 queue 做目標)
    queue_contex_t *target = list_entry(head->next, queue_contex_t, chain);
    list_splice_tail_init(&tmp, target->q);
    target->size = total_size;

    // 6. 回傳合併後的總大小
    return total_size;
}

驗證效能

目前在測試項

  • trace-13-malloc
  • trace-14-perf
  • trace-16-perf
  • trace-17-complexity

顯示以下異常，分析問題中

$ make test
....
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_reverse', and 'q_sort'
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 1000000.
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of 'q_sort' with random and descending orders: 'q_new', 'q_free', 'q_insert_head', 'q_sort', and 'q_reverse'
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', and 'q_reverse'
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of 'q_insert_tail', 'q_insert_head', 'q_remove_tail', and 'q_remove_head' is constant
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
Probably constant time
ERROR: Probably not constant time or wrong implementation
---     trace-17-complexity     0/5
---	TOTAL		95/100
make: *** [Makefile:61：test] 錯誤 1

開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤

$ make SANITIZER=1
$ make test

目前沒輸出有關 Address Sanitizer 異常的訊息

運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗

將 /traces 資料夾內的各測試項，各別做 Valgrind 測試

$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd  
$ valgrind -q --leak-check=full ./qtest -f traces/trace-02-ops.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-03-ops.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-04-ops.cmd     
$ valgrind -q --leak-check=full ./qtest -f traces/trace-05-ops.cmd          
$ valgrind -q --leak-check=full ./qtest -f traces/trace-06-ops.cmd          
$ valgrind -q --leak-check=full ./qtest -f traces/trace-07-string.cmd 
$ valgrind -q --leak-check=full ./qtest -f traces/trace-08-robust.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-09-robust.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-10-robust.cmd 
$ valgrind -q --leak-check=full ./qtest -f traces/trace-11-malloc.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-12-malloc.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-13-malloc.cmd 
$ valgrind -q --leak-check=full ./qtest -f traces/trace-14-perf.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-15-perf.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-16-perf.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-17-complexity.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-eg.cmd

$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd 
==70264==ASan runtime does not come first in initial library list; you should either link runtime to your application or manually preload it with LD_PRELOAD.

請教 chatgpt
Valgrind 顯示，

Address Sanitizer 與 Valgrind 同時插樁，造成載入順序不正確，以致出現「ASan runtime does not come first」的警告。最簡單的解法是：要測記憶體洩漏就單純用 Valgrind、要用 ASan 就單獨用 ASan，就不會遇到這個錯誤了。

先將 Address Sanitizer 關閉，再做 Valgrind 測試

$ make clean
$ make SANITIZER=0
$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd

$ valgrind -q --leak-check=full ./qtest -f traces/trace-14-perf.cmd 測出異常

  • 待分析原因
$ valgrind -q --leak-check=full ./qtest -f traces/trace-14-perf.cmd
cmd> # Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_reverse', and 'q_sort'
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih dolphin 1000000
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
cmd> it gerbil 1000000
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
l = [dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> sort
Warning: Skip checking the stability of the sort because the number of elements 514174 is too large, exceeds the limit 100000.
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
Freeing queue
ERROR: Freed queue, but 2 blocks are still allocated
==75940== 47 bytes in 1 blocks are still reachable in loss record 1 of 3
==75940==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==75940==    by 0x10F959: alloc (harness.c:146)
==75940==    by 0x10FAAC: test_malloc (harness.c:176)
==75940==    by 0x10FFB8: q_insert_tail (queue.c:64)
==75940==    by 0x10CF88: queue_insert (qtest.c:233)
==75940==    by 0x10D0A0: do_it (qtest.c:288)
==75940==    by 0x10E9AA: interpret_cmda (console.c:214)
==75940==    by 0x10ED54: interpret_cmd (console.c:234)
==75940==    by 0x10EFEC: cmd_select (console.c:604)
==75940==    by 0x10F8CD: run_console (console.c:684)
==75940==    by 0x10DB4C: main (qtest.c:1444)
==75940== 
==75940== 64 bytes in 1 blocks are still reachable in loss record 2 of 3
==75940==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==75940==    by 0x10F959: alloc (harness.c:146)
==75940==    by 0x10FAAC: test_malloc (harness.c:176)
==75940==    by 0x10FF9C: q_insert_tail (queue.c:58)
==75940==    by 0x10CF88: queue_insert (qtest.c:233)
==75940==    by 0x10D0A0: do_it (qtest.c:288)
==75940==    by 0x10E9AA: interpret_cmda (console.c:214)
==75940==    by 0x10ED54: interpret_cmd (console.c:234)
==75940==    by 0x10EFEC: cmd_select (console.c:604)
==75940==    by 0x10F8CD: run_console (console.c:684)
==75940==    by 0x10DB4C: main (qtest.c:1444)
==75940== 
==75940== 64 bytes in 1 blocks are definitely lost in loss record 3 of 3
==75940==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==75940==    by 0x10F959: alloc (harness.c:146)
==75940==    by 0x10FAAC: test_malloc (harness.c:176)
==75940==    by 0x10FEBB: q_insert_head (queue.c:37)
==75940==    by 0x10CEEB: queue_insert (qtest.c:234)
==75940==    by 0x10D0BC: do_ih (qtest.c:282)
==75940==    by 0x10E9AA: interpret_cmda (console.c:214)
==75940==    by 0x10ED54: interpret_cmd (console.c:234)
==75940==    by 0x10EFEC: cmd_select (console.c:604)
==75940==    by 0x10F8CD: run_console (console.c:684)
==75940==    by 0x10DB4C: main (qtest.c:1444)
==75940==

根據

==75940== by 0x10FFB8: q_insert_tail (queue.c:64)
==75940== by 0x10FF9C: q_insert_tail (queue.c:58)























/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL || s == NULL)
        return false;

    element_t *node = malloc(sizeof(element_t));

    if (node == NULL)
        return false;


    node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
    if (node->value == NULL) {
        q_release_element(node);
        return false;
    }
    memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
    memcpy(node->value, s, sizeof(char) * strlen(s));
    list_add_tail(&node->list, head);
    return true;
}

$ valgrind -q --leak-check=full ./qtest -f traces/trace-16-perf.cmd 測出異常

  • 待分析原因
$ valgrind -q --leak-check=full ./qtest -f traces/trace-16-perf.cmd
cmd> # Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', and 'q_reverse'
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih dolphin 1000000
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
cmd> it gerbil 1000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> it jaguar 1000
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
Freeing queue
ERROR: Freed queue, but 2 blocks are still allocated
==76718== 48 bytes in 1 blocks are still reachable in loss record 1 of 2
==76718==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76718==    by 0x10F959: alloc (harness.c:146)
==76718==    by 0x10FAAC: test_malloc (harness.c:176)
==76718==    by 0x10FED7: q_insert_head (queue.c:41)
==76718==    by 0x10CEEB: queue_insert (qtest.c:234)
==76718==    by 0x10D0BC: do_ih (qtest.c:282)
==76718==    by 0x10E9AA: interpret_cmda (console.c:214)
==76718==    by 0x10ED54: interpret_cmd (console.c:234)
==76718==    by 0x10EFEC: cmd_select (console.c:604)
==76718==    by 0x10F8CD: run_console (console.c:684)
==76718==    by 0x10DB4C: main (qtest.c:1444)
==76718== 
==76718== 64 bytes in 1 blocks are still reachable in loss record 2 of 2
==76718==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76718==    by 0x10F959: alloc (harness.c:146)
==76718==    by 0x10FAAC: test_malloc (harness.c:176)
==76718==    by 0x10FEBB: q_insert_head (queue.c:37)
==76718==    by 0x10CEEB: queue_insert (qtest.c:234)
==76718==    by 0x10D0BC: do_ih (qtest.c:282)
==76718==    by 0x10E9AA: interpret_cmda (console.c:214)
==76718==    by 0x10ED54: interpret_cmd (console.c:234)
==76718==    by 0x10EFEC: cmd_select (console.c:604)
==76718==    by 0x10F8CD: run_console (console.c:684)
==76718==    by 0x10DB4C: main (qtest.c:1444)
==76718==

根據

==76718== by 0x10FED7: q_insert_head (queue.c:41)
==76718== by 0x10FEBB: q_insert_head (queue.c:37)




















/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (s == NULL || head == NULL)
        return false;
    element_t *node = malloc(sizeof(element_t));
    if (node == NULL)
        return false;

    node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
    if (node->value == NULL) {
        q_release_element(node);
        return false;
    }
    memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
    memcpy(node->value, s, sizeof(char) * strlen(s));
    list_add(&node->list, head);
    return true;
}
Last changed by 
 
blue76815
0
46

Read more

Linux環境下 使用VS code debugging C設定步驟

問題: 在實做Lab0作業時, 依照GUN/Linux開發工具共筆中的編輯器:Visual Studio Code 偵錯教學去設定debug 環境 發現組態用GDB 設定時,在debug mode環境下,無法同時藉由終端機下command和debug mode程式連動 詳見實驗操作紀錄 vs code debug test 解決辦法 參考 Debugging C/C++ with Visual Studio Code 方法 step1. 在vs code開啟終端機頁面 先下make指令,產出qtest執行檔

Mar 9, 2025
2025q1 Homework1 (ideas)

2025q1 Homework1 (ideas)

Mar 3, 2025
2024q1 Homework2 (quiz1+2)

contributed by &lt; blue76815 &gt;

Aug 6, 2024
quit sort 非遞迴版 程式步驟詳解

根據作業 測驗 1 介紹的 qsort 演算法原理介紹

Apr 12, 2024
Read more from blue76815
Published on HackMD