Try   HackMD

2023q1 Homework1 (lab0)

contributed by < bonianlee >

開發環境

$ 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
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          6
On-line CPU(s) list:             0-5
Thread(s) per core:              1
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
Stepping:                        10
CPU max MHz:                     4400.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6000.00
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        9 MiB
NUMA node0 CPU(s):               0-5

開發過程

作業要求

  • 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: 移走佇列中間的節點並釋放之
  • q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點並釋放它們
  • q_swap: 交換佇列中鄰近的節點
  • q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
  • q_reverseK: 以K個節點為小組 (K-group) 進行分組，並以反向順序重新排列小組內的鏈結串列
  • q_sort: 以遞增順序來排序鏈結串列的節點
  • q_descend: 若佇列中任意節點的右端存在嚴格大於 (strictly greater) 的值 (value) ，則將該節點移去 (remove)
  • q_merge: 將所有佇列合併 (merge) 成一個以遞增順序排列好的鏈結串列

三個重要的結構體

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

/* Linked list element */
typedef struct {
    char *value;
    struct list_head list;
} element_t;

/* The context managing a chain of queues */
typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

q_new

建立新的「空」佇列，將其 linked list 的 next 與 prev 指向本身

  • 實作流程

    1. 使用 malloc 分配記憶體空間，並以 head 指向它
    2. 如果空間分配失敗， malloc 會回傳 NULL 並被 head 指向，此時讓 q_new 回傳 NULL
    3. 如果空間分配成功， if (head) 判斷式會執行，參考 list.h 中的函式 INIT_LIST_HEAD ，將其 linked list 的 next 與 prev 指向本身，做初始化的動作

  • list.h 參考函式 INIT_LIST_HEAD

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}
  • 實作程式碼
truct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (head) {
        INIT_LIST_HEAD(head);
        return head;
    }
    return NULL;
}

q_free

釋放所有由佇列佔用的記憶體空間

  • 實作流程

    1. 如果 list_head *l 不存在 (NULL) ，則不執行記憶體釋放
    2. 如果 list_head *l 存在，參考 list.h 中的函式 list_empty ，判斷 linked list 開頭 (head) 有沒有接著其他的 node ，若有則使用 q_remove_head 與 q_release_element 來連續清除記憶體空間，最後再將「空」佇列 l 佔用的記憶體空間清除

  • 實作程式碼

void q_free(struct list_head *l)
{
    if (l) {
        while (!list_empty(l))
            q_release_element(q_remove_head(l, NULL, 0));
        free(l);
    }
    return;
}

列出對應的 GitHub commit 超連結即可。
:notes: jserv

:::spoiler `q_remove_head` 與 `q_release_element` 程式碼
  • 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 *element = list_first_entry(head, element_t, list);
    if (bufsize && sp) {
        strncpy(sp, element->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    list_del_init(&element->list);
    return element;
}
  • q_release_element
static inline void q_release_element(element_t *e)
{
    test_free(e->value);
    test_free(e);
}

:::

q_insert_head

在佇列開頭 (head) 插入 (insert) 給定的新節點

  • 實作流程

    1. 使用 malloc 配置 element_t 的記憶體空間，若空間分配失敗，則回傳 false
    2. 使用 strlen 計算引數 s 的字串長度 (包含空格) ，作為分配記憶體空間給 element->value 的依據，如果 value 的記憶體配置失敗，記得要先將 element 的空間釋放掉，才可以回傳 false
    3. 使用 strncpy 將 s 複製給 element->value ，再參考 list.h 中的 list_add 將 element 插入 (insert) 到佇列開頭 (head)

  • list.h 參考函式 list_add

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;
}
  • 實作程式碼
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *element = malloc(sizeof(element_t));
    if (!element)
        return false;
    int len = strlen(s);
    element->value = malloc((len + 1) * sizeof(char));
    if (!element->value) {
        free(element);
        return false;
    }
    strncpy(element->value, s, len);
    *(element->value + len) = '\0';
    list_add(&element->list, head);
    return true;
}

q_insert_tail

在佇列尾端 (tail) 插入 (insert) 給定的新節點

  • 實作流程
    重複 q_insert_head 實作流程的 1 , 2 步驟，惟步驟 3 改成使用 list_add_tail 將新的 element 插入 (insert) 到在佇列尾端 (tail)

  • list.h 參考函式 list_add_tail

static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}
  • 實作程式碼
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *element = malloc(sizeof(element_t));
    if (!element)
        return false;
    int len = strlen(s);
    element->value = malloc((len + 1) * sizeof(char));
    if (!element->value) {
        free(element);
        return false;
    }
    strncpy(element->value, s, len);
    *(element->value + len) = '\0';
    list_add_tail(&element->list, head);
    return true;
}

q_remove_head

在佇列開頭 (head) 移去 (remove) 給定的節點

  • 實作流程

    1. 如果 head 不存在，或者為「空」佇列，則回傳 NULL
    2. 使用 list_first_entry 取得開頭的 element ，並使用 strncpy 將 element->value 複製給 sp
    3. 使用 list_del_init 將開頭 (head) 的 element 移去 (remove)

  • 實作程式碼

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *element = list_first_entry(head, element_t, list);
    if (bufsize && sp) {
        strncpy(sp, element->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    list_del_init(&element->list);
    return element;
}
list_first_entry 與 list_del_init 程式碼
  • lsit_first_entry
#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)
  • list_del_init
static inline void list_del_init(struct list_head *node)
{
    list_del(node);
    INIT_LIST_HEAD(node);
}

q_remove_tail

在佇列尾端 (tail) 移去 (remove) 給定的節點

  • 實作流程
    重複 q_remove_head 實作流程的步驟，惟步驟 2 的 list_first_entry 改成使用 list_last_entry ，取得尾端 (tail) 的 element

  • list.h 中的 list_last_entry

#define list_last_entry(head, type, member) \
    list_entry((head)->prev, type, member)
  • 實作程式碼
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *element = list_last_entry(head, element_t, list);
    if (bufsize && sp) {
        strncpy(sp, element->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    list_del_init(&element->list);
    return element;
}

q_size

計算目前佇列的節點總量

  • 實作流程
    1. 若 head 不存在，則傳回 0
    2. 使用 list.h 中的巨集 list_for_each 逐一走訪鏈結串列，每存取到 temp 則遞增 count，最後回傳 count

踩雷紀錄：迭代所使用的指標 temp 不要指向另外 malloc 的記憶體空間，因為若沒有 free 掉 temp 所佔用的記憶體空間，當 $ make test 執行重複呼叫 q_size 的 Trace 測試檔時，會導致 q_free 後仍有記憶體空間被佔用而沒被釋放掉，將 temp 改成指向 NULL ，則不會佔用到記憶體空間

  • 實作程式碼
int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    int count = 0;
    struct list_head *temp = NULL;
    list_for_each (temp, head)
        count++;
    return count;
}

q_delete_mid

移走佇列中間的節點並釋放之
參考你所不知道的 C 語言: linked list 和非連續記憶體

  • 思考方向

    1. 龜兔賽跑 (Tortoise and Hare Algorithm):
      使用兩個指標 fast 和 slow 指向 head->next ，其中 fast 的前進速度較快，一次走兩格節點，而 slow 的速度較慢，一次走一格節點，如此一來，只要當 if (fast == head || fast->next == head) 判斷式成立，指標 slow 所指向的節點即為佇列中間的節點，將之移走 (remove) 並且釋放掉 (release) 佔用的記憶體空間即可
    2. 頭尾逼近
      因為 struct list_head 是雙向的 linked list ，所以除了使用龜兔賽跑那樣同向的指標移動之外，還可以從頭跟尾互相接近的方式來找出佇列中間的節點位置，這種策略能夠減少指標移動的次數

  • 實作流程 (採用頭尾逼近)

    1. head 至少要接一個節點，才可以執行 delete mid 的動作，因此當 if(!head || list_empty(head)) 判斷式滿足，則傳回 false
    2. 建立兩個指標 forward 與 backward ， forward 指向 head->next ，而 backward 指向 head->prev ，我使用 while 迴圈來不斷移動指標，若滿足判斷式 forward != backward && forward != backward->prev ，則使 forward = forward->next 和 backward = backward->prev ，即互相靠近，並且每次只前進一個節點
    3. 當發生以下兩種情形之一，代表已經找出佇列中間的節點了
      • forward == backward
        若佇列除了 head 外，連接了奇數個節點，則這種情形就會發生，此時 forward 和 backward 指向的節點即為佇列中間的節點
      • forward == backward->prev
        若佇列除了 head 外，連接了偶數個節點，則這種情形就會發生，此時 backward 指向的節點即為佇列中間的節點
    4. 將步驟 3 的兩種情形用 if 判斷式做區別，即可找出佇列中間的節點，並做移去 (remove) 與釋放 (release) 記憶體的動作，這邊我使用 list.h 中的 list_del 與 list_first_entry ，再搭配 q_release_element 來完成

踩雷紀錄： list.h 內的 list_del 做的事情只有將節點從 linked list 中孤立出來，並沒有做記憶體釋放的動作，因此我使用 list.h 中的 list_first_entry 找出佇列中間 element 的前一個 element 的地址，再用 q_release_element 釋放掉佇列中間 element 佔用的記憶體空間

  • 實作程式碼
bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *forward = head->next;
    struct list_head *backward = head->prev;
    if (!forward)
        return false;
    if (!backward)
        return false;
    while (forward != backward && forward != backward->prev) {
        forward = forward->next;
        backward = backward->prev;
    }
    if (forward == backward) {
+       element_t *element = list_first_entry(forward->prev, element_t, list);
        list_del(forward);
+       q_release_element(element);
        return true;
    }
    if (forward == backward->prev) {
+       element_t *element = list_first_entry(forward, element_t, list);
        list_del(backward);
+       q_release_element(element);
        return true;
    }
    return true;
}

q_delete_dup

在已經排序的狀況，移走佇列中具備重複內容的節點並釋放它們

注意資訊科技詞彙翻譯
:notes: jserv

遍歷：著重在「完全」走訪每個節點
本項 q_delete_dup 的實作目的是要找出特定內容的節點並釋放之，使用「遍歷」可能會令焦點模糊不清，已修正不當的詞彙描述，謝謝教授！
:cat2: ccasdqwe

  • 實作流程

    1. 除了 head 指向的「空」節點外，至少還要連接兩個以上的節點才有可能發生重複內容的狀況，因此先做例外排除 if (!head || list_empty(head) || list_is_singular(head)) ，若滿足判斷式就傳回 false
    2. 宣告兩個新指標 curr 和 safe ，用來作為 list_for_each_safe 的引數，另外還宣告了布林變數 diff ，用來在之後的迭代過程判斷是否要繼續執行刪除的動作，將它初始化為 false
    3. 使用 list.h 中的巨集 list_for_each_safe 來做 curr 與 safe 的遍歷 –->逐一走訪，另外宣告一個指向 curr->next 的指標 next ，並宣告 curr_entry 與 next_entry 分別指向它們所屬的 element
    4. 判斷式中 !strcmp(curr_entry->value, next_entry->value) 用來比較 curr_entry 與 next_entry 的 value 是否相同，若相同 strcmp() 會回傳 0 ，加入邏輯運算子 ! 就會得到 true 的結果，如此一來，當 if 判斷式滿足，即代表兩個相鄰 element 的 value 重複出現，此時將 curr 移去 (remove) 並且釋放掉 (release) 它占用的記憶體空間，最後令 diff = true ，代表下一個 element 也是待釋放的目標
    5. 當 if ((next != head) && (!strcmp(curr_entry->value, next_entry->value))) 不再滿足，且 diff 仍為 true ，代表 curr 所指向的 element 為連續重複內容的最末端 element ，將它釋放掉後，令 diff = false 代表已刪除完其中一組重複內容的 element

  • 實作程式碼

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;
    bool diff = false;
    struct list_head *curr, *safe;
    list_for_each_safe (curr, safe, head) {
        struct list_head *next = curr->next;
        element_t *curr_entry = list_entry(curr, element_t, list);
        element_t *next_entry = list_entry(next, element_t, list);
        if ((next != head) && (!strcmp(curr_entry->value, next_entry->value))) {
            list_del(curr);
            q_release_element(curr_entry);
            diff = true;
        } else if (diff) {
            list_del(curr);
            q_release_element(curr_entry);
            diff = false;
        }
    }
    return true;
}

q_swap

交換佇列中鄰近的節點

  • 實作流程

    1. 例外處理
      q_swap 是在進行節點兩兩對調的動作，因此佇列除了 head 指向的節點外，若沒有額外連接兩個以上的節點，就無法執行對調的動作，故先使用 if 判斷式做例外處理
    2. 宣告指標
      我宣告了兩個指標 left 與 right ，分別指向 head->next 跟 head->next->next ，方便之後進行節點對調的動作
    





%0



e

Empty



1

1



e->1





5

5



e->5





1->e





2

2



1->2





2->1





3

3



2->3





3->2





4

4



3->4





4->3





4->5





5->e





5->4





h
head



h->e





l
left



l->1





r
right



r->2

    1. next 與 prev 的重新指向
      將 head 指向的節點改成與 2 號節點相鄰， 1 號節點接在 2 號節點的後面， 3 號節點再去與 1 號節點做 next 與 prev 的重新指向，最後成功對調 1 號與 2 號節點，此時 right 指向 2 號節點，而 left 則指向 1 號節點

      





%0



e

Empty



2

2



e->2





5

5



e->5





2->e





1

1



2->1





1->2





3

3



1->3





3->1





4

4



3->4





4->3





4->5





5->e





5->4





h
head



h->e





l
left



l->1





r
right



r->2

    2. 移動指標並重複步驟 3
      使用判斷式判斷 left->next 跟 left->next->next 是否為 head 所指向的節點，若滿足其中一個，則跳出 while 迴圈，代表剩餘的節點數已經不足 2 個，無法進行對調的動作
      如果 left->next 跟 left->next->next 都不是 head 所指向的節點，代表佇列尚未完全地完成兩兩對調，故移動指標並繼續進行步驟 3 的對調動作，直到跳出 while 迴圈的條件被滿足為止，最終結果如下圖

      





%0



e

Empty



2

2



e->2





5

5



e->5





2->e





1

1



2->1





1->2





4

4



1->4





4->1





3

3



4->3





3->4





3->5





5->e





5->3





h
head



h->e





l
left



l->3





r
right



r->4

  • 實作程式碼

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *left = head->next;
    struct list_head *right = head->next->next;
    head->next = right;
    right->next->prev = left;
    left->next = right->next;
    right->next = left;
    right->prev = head;
    left->prev = right;
    while (left->next != head) {
        if (left->next->next != head) {
            right = left->next->next;
            right->prev->next = right->next;
            right->next->prev = right->prev;
            right->next = right->prev;
            right->prev->prev = right;
            right->prev = left;
            left->next = right;
            left = right->next;
        } else
            break;
    }
    return;
}

q_reverse

以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點

  • 實作流程

    1. 例外處理
      q_reverse 的目的是要將佇列以反向順序重新排列 (除了 head 所指向的節點之外) ，因此至少要額外連接 2 個以上的節點，才可以執行此動作，故先排除掉可能發生的例外

    2. 排列節點
      q_reverse 可以使用 list.h 中的 list_for_each_safe 與 list_move 很簡單的達成，方法是透過 list_for_each_safe 遍歷 –->逐一走訪佇列，過程中用 list_move 不斷把節點移至開頭 (head) ，過程如下圖所示

      





%0



e

Empty



1

1



e->1





5

5



e->5





1->e





2

2



1->2





2->1





3

3



2->3





dummy




2:n->dummy:n


move to



3->2





4

4



3->4





4->3





4->5





5->e





5->4





h
head



h->e






      





%0



e

Empty



2

2



e->2





5

5



e->5





2->e





1

1



2->1





1->2





3

3



1->3





3->1





4

4



3->4





dummy




3:n->dummy:n


move to



4->3





4->5





5->e





5->4





h
head



h->e






      





%0



e

Empty



3

3



e->3





5

5



e->5





3->e





2

2



3->2





2->3





1

1



2->1





1->2





4

4



1->4





4->1





4->5





dummy




4:n->dummy:n


move to



5->e





5->4





h
head



h->e






      





%0



e

Empty



4

4



e->4





5

5



e->5





4->e





3

3



4->3





3->4





2

2



3->2





2->3





1

1



2->1





1->2





1->5





5->e





5->1





dummy




5:n->dummy:n


move to



h
head



h->e






      





%0



e

Empty



5

5



e->5





1

1



e->1





5->e





4

4



5->4





4->5





3

3



4->3





3->4





2

2



3->2





2->3





2->1





1->e





1->2





h
head



h->e

  • 實作程式碼

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *node = NULL;
    struct list_head *safe = NULL;
    list_for_each_safe (node, safe, head)
        list_move(node, head);
    return;
}

q_reverseK

以 k 個節點為小組 (k-group) 進行分組，並以反向順序重新排列小組內的鏈結串列

  • 實作流程

    1. 例外處理
      q_reverseK 會進行反向順序的重新排列，因此除了 head 所指向的節點外，至少還要連接兩個以上的節點，才能執行排列的動作，故先做例外排除
      同理， k < 2 無法執行排列的動作，因此也要做例外排除

    2. k == 2 與 k > 2 的情形
      k == 2 時 q_reverseK 的功能與 q_swap 相同，是在進行節點兩兩對調的動作，因此直接呼叫 q_swap 即可
      若 k > 2 ，我的作法是先數好總共要做幾次的反向順序重排，再由 for 迴圈執行相同的反向順序重排流程，其中變數 count 代表 head 以外的節點總數， repeat_times 則為反向順序重排流程所要執行的次數

    3. k 個節點為小組進行反向順序重新排列
      宣告指標 sub_head 與 cut_pos ，分別都指向 head ，它們之後會作為引數提供給 list_cut_position 跟 list_splice_init 使用

      為了圖形美觀，環狀佇列頭尾相連的鏈結省略不畫

      





%0



e

Empty



1

1



e->1





d

Empty



1->e





2

2



1->2





2->1





3

3



2->3





3->2





4

4



3->4





4->3





5

5



4->5





5->4





h
head



h->e





s
sub_head



s->e





c
cut_pos



c->e





t
head_temp



t->d

      假設 k = 3 ，則移動指標 cut_pos 至節點 3 的位置，並以 list_cut_position 將節點們移至另一個佇列

      





%0



e

Empty



4

4



e->4





d

Empty



1

1



d->1





4->e





5

5



4->5





5->4





1->d





2

2



1->2





2->1





3

3



2->3





3->2





h
head



h->e





s
sub_head



s->e





c
cut_pos



c->3





t
head_temp



t->d

      使用 q_reverse 將 head_temp 為頭端 (head) 的鏈結串列進行反向順序重新排列

      





%0



e

Empty



4

4



e->4





d

Empty



3

3



d->3





4->e





5

5



4->5





5->4





3->d





2

2



3->2





2->3





1

1



2->1





1->2





h
head



h->e





s
sub_head



s->e





c
cut_pos



c->3





t
head_temp



t->d

      使用 list_splice_init ，將 head_temp 為頭端 (head) 的鏈結串列除了 head_temp 指向的節點以外，其他的節點移回原佇列

      





%0



e

Empty



3

3



e->3





d

Empty



3->e





2

2



3->2





2->3





1

1



2->1





1->2





4

4



1->4





4->1





5

5



4->5





5->4





h
head



h->e





s
sub_head



s->e





c
cut_pos



c->3





t
head_temp



t->d

      最後移動指標 sub_head 與 cut_pos ，若 ( count / k ) > 1 ，則重複上述的流程

      





%0



e

Empty



3

3



e->3





d

Empty



3->e





2

2



3->2





2->3





1

1



2->1





1->2





4

4



1->4





4->1





5

5



4->5





5->4





h
head



h->e





s
sub_head



s->1





c
cut_pos



c->1





t
head_temp



t->d

  • 實作程式碼

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    if (k < 2)
        return;
    else if (k == 2)
        q_swap(head);
    else {
        int count = 0;
        struct list_head *node = NULL;
        list_for_each (node, head)
            count++;
        if (count < k)
            return;
        else {
            int repeat_times = count / k;
            LIST_HEAD(dummy);
            struct list_head *head_temp = &dummy;
            struct list_head *sub_head = head;
            struct list_head *cut_pos = head;
            for (int i = 0; i < repeat_times; i++) {
                for (int j = 0; j < k; j++)
                    cut_pos = cut_pos->next;
                list_cut_position(head_temp, sub_head, cut_pos);
                q_reverse(head_temp);
                list_splice_init(head_temp, sub_head);
                for (int j = 0; j < k; j++)
                    sub_head = sub_head->next;
                cut_pos = sub_head;
            }
        }
    }
    return;
}

q_sort

以遞增順序來排序鏈結串列的節點
參考 < 你所不知道的 C 語言: linked list 和非連續記憶體 > 與 < Merge Sort 與它的變化 >

  • 實作流程
    1. 例外處理
      除了 head 所指向的節點外，至少要連接 2 個以上的節點才能夠進行排序，因此做例外處理
    2. Merge sort
      參考 < Merge Sort 與它的變化 > ，先將鏈結串列尾端 (tail) 的 next 指向 NULL ，即斷開 next 方向的環狀結構，再使用撰寫好的 merge_sort 進行遞增順序的排序
    3. 重新連接環狀串列
      將 merge_sort 過程中切斷的 linked list 指標重新指向
  • 實作程式碼
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    head->prev->next = NULL;
    head->next = merge_sort(head->next);
    struct list_head *curr = head, *next = curr->next;
    while (next) {
        next->prev = curr;
        curr = next;
        next = next->next;
    }
    curr->next = head;
    head->prev = curr;
}

q_descend

若佇列中任意節點的右端存在嚴格大於 (strictly greater) 的值 (value) ，則將該節點移去 (remove)
參考 < KHLee529 > 的實作

  • 實作流程

    1. 參考 < KHLee529 > 同學的實作流程，他的作法是從佇列尾端 (tail) 往回比較 element->value 的大小，過程中不斷更新 (或者說紀錄) 擁有最大值的字串，並由 max 指向它，當碰到比 max 大小還要小的 value ，則將之移除 (remove and release)
    2. 在迭代過程中使用整數變數 total 與 n_del 分別紀錄 element 總數和移除的 element 總數，最後傳回兩者之差，即為剩下的 element 總數

  • 實作程式碼

int q_descend(struct list_head *head)
{
    char *max = NULL;
    element_t *entry = NULL, *safe = NULL;
    int total = 0, n_del = 0;
    for (entry = list_entry(head->prev, element_t, list),
        safe = list_entry(entry->list.prev, element_t, list);
         &entry->list != head;
         entry = safe, safe = list_entry(safe->list.prev, element_t, list)) {
        total += 1;
        if (!max || strcmp(entry->value, max) > 0) {
            max = entry->value;
        } else {
            list_del(&entry->list);
            q_release_element(entry);
            n_del += 1;
        }
    }
    return total - n_del;
}

q_merge

將所有佇列合併 (merge) 成一個以遞增順序排列好的鏈結串列
參考 < chiangkd > 的實作

  • 實作流程
    1. 使用 list_for_each_entry_safe 逐一走訪完每個節點，每當存取到 c_cont 就斷開部分連結，並以 mergeTwoLists 將 sorted 與 c_cont->q->next 合併
    2. 迭代完成後須復原環狀 doubly linked list 結構，因為過程中各個 linked list 的 prev 被 mergeTwoLists 打亂了，只有 next 的指向是正確的
    3. 使用 list_splice 將處理完的鏈結串列交還給 head 所屬的 element
  • 實作程式碼
int q_merge(struct list_head *head)
{
    // reference to @chiangkd
    if (!head)
        return 0;
    queue_contex_t *c_cont;
    queue_contex_t *n_cont;
    struct list_head *sorted = NULL;

    list_for_each_entry_safe (c_cont, n_cont, head, chain) {  // iterate context
        c_cont->q->prev->next = NULL;
        c_cont->q->prev = NULL;
        sorted = mergeTwoLists(sorted, c_cont->q->next);
        INIT_LIST_HEAD(c_cont->q);  // reconnect the lists which are moved and
                                    // merged to "sorted" list;
    }
    LIST_HEAD(tmp);
    struct list_head *t = &tmp;
    t->next = sorted;
    struct list_head *c = t;
    while (sorted) {
        sorted->prev = c;
        c = sorted;
        sorted = sorted->next;
    }
    c->next = t;
    t->prev = c;
    int size = q_size(t);  // store size before splice to main queue
    list_splice(t, list_first_entry(head, queue_contex_t, chain)->q);
    return size;
}

額外撰寫的函式

merge_sort

將佇列從中間切斷，產生的兩個子佇列再個別切斷中間的鏈結，以此種方式迭代，直到切成單個節點為止，再以 mergeTwoLists 進行遞增順序的合併

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 = slow->next;
    slow->next = NULL;
    struct list_head *left = merge_sort(head), *right = merge_sort(mid);
    return mergeTwoLists(left, right);
}

mergeTwoLists

將兩個串列以遞增的順序合併在一起

struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **node = NULL;
    while (L1 && L2) {
        element_t *L1_entry = list_entry(L1, element_t, list);
        element_t *L2_entry = list_entry(L2, element_t, list);
        node = strcmp(L1_entry->value, L2_entry->value) < 0 ? &L1 : &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
        *node = (*node)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

研讀 Linux 核心原始程式碼 < list_sort.c >

作業要求

  • 研讀 Linux 核心原始程式碼的 lib/list_sort.c
  • 嘗試引入 Linux 核心原始程式碼到 lab0-c 專案
  • 比較自己實作的 merge sort 和 Linux 核心程式碼之間效能落差

研讀 Linux 核心原始程式碼的 lib/list_sort.c

參考 < Risheng1128 > 的 < 研讀 Linux 核心原始程式碼 list_sort.c >

研讀原始程式碼 list_sort.c 發現主要是由三個函式 merge() 、 merge_final() 及 list_sort() 組成，接著要個別分析它們的作用

在分析之前，先探討函式屬性 __attribute__((nonnull())) 的作用，因為三個函式在宣告函式原型時都擁有這個屬性，參考 < __attribute__((nonnull)) function attribute > 可以得知 nonnull 的作用是當特定函式的引數為 NULL 時，編譯器會發出警告訊息

This function attribute specifies function parameters that are not supposed to be null pointers. This enables the compiler to generate a warning on encountering such a parameter.

merge()
merge() 原始碼 




























__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
				struct list_head *a, struct list_head *b)
{
	struct list_head *head, **tail = &head;

	for (;;) {
		/* if equal, take 'a' -- important for sort stability */
		if (cmp(priv, a, b) <= 0) {
			*tail = a;
			tail = &a->next;
			a = a->next;
			if (!a) {
				*tail = b;
				break;
			}
		} else {
			*tail = b;
			tail = &b->next;
			b = b->next;
			if (!b) {
				*tail = a;
				break;
			}
		}
	}
	return head;
}

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,const struct list_head *, const struct list_head *);

cmp 指向回傳型態為 int 的函式，該函式的引數為 void * 和 2 個 const struct list_head *

  • 宣告指標 ( line 5 )
    宣告兩個指標，一個是指向 struct list_head 資料型態的指標 head ，另一個則是指向指標的指標 tail ，並且將它初始化指向 head 的地址

  • for 迴圈 ( line 7 )
    沒有設定判斷式，為無限迭代的迴圈，使用 cmp 來判斷下一個節點是要從 a 或者 b 來取得，假如 linked list a 已經沒有節點時，則接上 linked list b ，反之，假如 linked list b 已經沒有節點時，則接上 linked list a

merge_final()

將所有節點的 prev 接回前一個節點

/* Finish linking remainder of list b on to tail */
	tail->next = b;
	do {
		/*
		 * If the merge is highly unbalanced (e.g. the input is
		 * already sorted), this loop may run many iterations.
		 * Continue callbacks to the client even though no
		 * element comparison is needed, so the client's cmp()
		 * routine can invoke cond_resched() periodically.
		 */
		if (unlikely(!++count))
			cmp(priv, b, b);
		b->prev = tail;
		tail = b;
		b = b->next;
	} while (b);

	/* And the final links to make a circular doubly-linked list */
	tail->next = head;
	head->prev = tail;
list_sort()

首先閱讀此函式的註解

 * This mergesort is as eager as possible while always performing at least
 * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
 * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
 *
 * Thus, it will avoid cache thrashing as long as 3*2^k elements can
 * fit into the cache.  Not quite as good as a fully-eager bottom-up
 * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
 * the common case that everything fits into L1.

由此可知，此 merge sort 總是等到 linked list 的長度比例為 2 : 1 時才會開始進行合併的動作，舉例來說，有兩個大小為

2k 的 linked list 時， merge sort 不會直接進行合併，而是會等到有第三個
2k 時，才開始合併，並且是以
2k+1 和
2k 兩個 linked list 進行合併，滿足前述的 2 : 1

若以這種方式進行 merge sort ，假如被合併的 linked list 都可以被放進 cache 裡，則可以避免 Cache thrashing 的問題

引入 Linux 核心原始程式碼到 lab0-c 專案

參考 < komark06 > 的方法引入原始程式碼，並且加入新的 qtest 命令 list_sort

實作流程

  1. 將檔案 lib/list_sort.c 加進 lab0-c
  2. 將位於其他檔案的巨集函式加進 list_sort.h
  3. 在 qtest.c 新增函式 cmp()
  4. 修改 qtest.c 的 do_sort() 函式

首先要在 lab0-c 專案裡面建立 lsit_sort.c 及 lsit_sort.h ，前者包含 Linux 核心原始程式碼，而後者則是包含 lab0-c 所缺少的必要定義
以下為 lsit_sort.h 的內容

#ifndef _LIST_SORT_H
#define _LIST_SORT_H
#include <stdint.h>
#include "list.h"
#define USE_LINUX_SORT  1
#define likely(x)	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *);
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif /* End of _LIST_SORT_H_ */

接著在 Makefile 中的 OBJS 新增 list_sort.o

OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o\
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        shannon_entropy.o \
        linenoise.o web.o

在 qtest.c 上建立函式 cmp()

__attribute__((nonnull(2,3)))
int cmp(void *priv, const struct list_head *list1, const struct list_head *list2)
{
    element_t *list1_entry = list_entry(list1, element_t, list);
    element_t *list2_entry = list_entry(list2, element_t, list);
    return strcmp(list1_entry->value, list2_entry->value) < 0 ? 0 : 1;
}

運用 Valgrind 排除 qtest 實作時的記憶體錯誤

作業要求

  • 運用 Valgrind 排除 qtest 實作時的記憶體錯誤，並且使用 Massif 進行視覺化記憶體使用情況的分析

當 queue.c 的實作基本上完成後，執行 $ make valgrind 進行動態分析，發現 trace-13-malloc.cmd 沒有通過測試，因此針對這個檔案進行分析，使用命令 valgrind -q --leak-check=full ./qtest -f traces/trace-13-malloc.cmd 對檔案 trace-13-malloc.cmd 進行測試

測試結果 
# Test of malloc failure on new
WARNING: Malloc returning NULL
l = NULL
l = []
WARNING: Malloc returning NULL
l = NULL
l = []
l = []
l = []
==76976== 32 bytes in 1 blocks are still reachable in loss record 1 of 3
==76976==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76976==    by 0x10CBCE: do_new (qtest.c:145)
==76976==    by 0x10DDFA: interpret_cmda (console.c:181)
==76976==    by 0x10E3AF: interpret_cmd (console.c:201)
==76976==    by 0x10E7B0: cmd_select (console.c:610)
==76976==    by 0x10F09C: run_console (console.c:705)
==76976==    by 0x10D1EC: main (qtest.c:1223)
==76976== 
==76976== 160 bytes in 5 blocks are possibly lost in loss record 2 of 3
==76976==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76976==    by 0x10CBCE: do_new (qtest.c:145)
==76976==    by 0x10DDFA: interpret_cmda (console.c:181)
==76976==    by 0x10E3AF: interpret_cmd (console.c:201)
==76976==    by 0x10E7B0: cmd_select (console.c:610)
==76976==    by 0x10F09C: run_console (console.c:705)
==76976==    by 0x10D1EC: main (qtest.c:1223)
==76976== 
==76976== 224 bytes in 4 blocks are still reachable in loss record 3 of 3
==76976==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76976==    by 0x10F110: test_malloc (harness.c:133)
==76976==    by 0x10F515: q_new (queue.c:23)
==76976==    by 0x10CC07: do_new (qtest.c:149)
==76976==    by 0x10DDFA: interpret_cmda (console.c:181)
==76976==    by 0x10E3AF: interpret_cmd (console.c:201)
==76976==    by 0x10E7B0: cmd_select (console.c:610)
==76976==    by 0x10F09C: run_console (console.c:705)
==76976==    by 0x10D1EC: main (qtest.c:1223)
==76976==

從錯誤訊息中發現有 still reachable 類型的記憶體遺失情形發生，且不是在 queue.c 實作中造成的，因此根據錯誤訊息的追隨路徑，開始檢查 qtest.c 中有無不合理的操作，但找了許久還是沒有頭緒，參考了 KHLee529 同學的筆記後，才發現 qtest.c 中的 q_quit 敘述第一行為 return true; ，也就是說這個函式第一行以後的敘述毫無作用，很明顯語意上有誤

still reachable: 程式結束時有尚未釋放的記憶體，且還被指標所指向，通常會發生在全域變數

q_quit 
static bool q_quit(int argc, char *argv[])
{
-   return true;
    report(3, "Freeing queue");
    if (current && current->size > BIG_LIST_SIZE)
        set_cautious_mode(false);

    if (exception_setup(true)) {
        struct list_head *cur = chain.head.next;
        while (chain.size > 0) {
            queue_contex_t *qctx, *tmp;
            tmp = qctx = list_entry(cur, queue_contex_t, chain);
            cur = cur->next;
            q_free(qctx->q);
            free(tmp);
            chain.size--;
        }
    }

    exception_cancel();
    set_cautious_mode(true);

    size_t bcnt = allocation_check();
    if (bcnt > 0) {
        report(1, "ERROR: Freed queue, but %lu blocks are still allocated",
               bcnt);
        return false;
    }

    return true;
}

當我將錯誤的語意清除後重新執行 valgrind -q --leak-check=full ./qtest -f traces/trace-13-malloc.cmd ，先前 still reachable 類型的記憶體遺失情形也隨之解決了

測試結果 
# Test of malloc failure on new
l = []
l = []
WARNING: Malloc returning NULL
l = NULL
WARNING: Malloc returning NULL
l = NULL
WARNING: Malloc returning NULL
l = NULL
l = []
Freeing queue

使用圖形化工具 < Massif > 來查看執行 trace-13-malloc.cmd 時記憶體的分配狀況，輸入命令 valgrind -v --tool=massif ./qtest -f traces/trace-13-malloc.cmd ，產生了檔案 massif.out.85066 ，接著使用 massif-visualizer 打開檔案，輸入命令 massif-visualizer ./massif.out.85066 ，最終結果為下圖

從動態記憶體配置的圖形發現，佔用的記憶體最終都歸零 –->歸還了，可見 qtest 在 trace-13-malloc.cmd 執行結束後，過程中佔用的記憶體都已成功被釋放

注意用語，請查詢辭典，理解「歸零」的意涵是否可對應到本例 malloc/free 操作。
:notes: jserv

歸零：將儀表或計量裝置的指示值調至零點或起點
本例的操作是對記憶體進行分配與釋放 (歸還) ，記憶體總量沒有減少，因此不適合用「歸零」來描述，已修正錯誤的詞彙使用，謝謝教授！
:cat2: ccasdqwe

Last changed by 
 
bonianlee
0
528

Read more

STM32 開發板學習筆記

STM32 NUCLEO-F446RE

May 29, 2025
2023q1 Homework3 (fibdrv)

contributed by &lt; bonianlee &gt; :::danger 不要打錯自己的 GitHub 帳號 :notes: jserv ::: 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

Jun 15, 2023
數位控制

Z-Transform 設 $x(k)$ 是 $x(t)$ 的離散時間，則 $x(k)$ 的單邊 Z-Transform 為 \begin{align*} x(z)=Z{x(k)}=\sum_{k=0}^\infty x(k)z^{-k},\tag{1} \end{align*} Z-Transform 是離散時間的函數做 Laplace transform 後，再做變數變換 $Z=e^{sT}$ 得到的 $Z^{-k}$ 屬於時間延遲 ($Z=e^{sT}$ 中的 T 是取樣週期) 特性 離散時間函數乘上 $a^k$ ( k 想像成是 t )

Jun 12, 2023
2023q1 Homework2 (quiz2)

contributed by &lt;bonianlee&gt; 測驗 1 參照 你所不知道的 C 語言: bitwise 操作，考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值，例如: next_pow2(7) = 8 next_pow2(13) = 16 next_pow2(42) = 64 測驗題題目中提到的一種實作方式為:

Apr 16, 2023
Read more from bonianlee
Published on HackMD