2023q1 Homework1 (lab0)

contributed by < Jacobchen142 >

開發環境

$ 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:         36 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-2400 CPU @ 3.10GHz
    CPU family:          6
    Model:               42
    Thread(s) per core:  1
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            7
    CPU max MHz:         3400.0000
    CPU min MHz:         1600.0000
    BogoMIPS:            6185.67
  Virtualization:        VT-x
Caches :     
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    6 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-3

實作queue.c 開發紀錄

說好的進度呢？

jserv

老師抱歉，因為我發現我有太多基礎需要補上，所以一直沒開始做作業

結構

list_head 為 doubly-linked list 的 head 或是 node

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

element_t 為 doubly-linked list 的 element

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

• 參考 chiangkd
• 參考你所不知道的 C 語言：linked list 和非連續記憶體

問題紀錄

1. 我遇到的第一個大問題就是對於整體結構沒有概念，一知半解。透過詳讀你所不知道的 C 語言：linked list 和非連續記憶體，就可以對於 doubly-linked list 的結構有所掌握。
   指向串列開頭的指標，是單一個list_head結構。
   而在串列的元素中，list_head結構則是嵌入在自定義的結構中，本次作業中即為element_t
   

q_new

1. 串列的開頭是一個指向list_head的指標，透過malloc()建立該指標
2. 利用list.c所提供的INIT_LIST_HEAD()進行初始化

實際程式碼

struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    if (!new)
        return NULL;

    INIT_LIST_HEAD(new);
    return new;
}

q_free

• 想法：走訪整個串列，每經過一個節點，就 remove 該節點，並釋放該節點的記憶體空間。重複動作，直到剩下指向開頭的指標。最後釋放指向開頭的指標之記憶體空間。
• 實作流程：
  1. 若傳入的l(指向開頭的指標) 為NULL則直接return
  2. 若除了l之外還有其他list_head的節點，利用list_del()移除節點的連結，再透過list_entry()找到串列節點的位置，用q_release_element（）釋放記憶體
  3. 重複步驟 2 直到整個串列只剩下l
  4. 用free()釋放l

程式碼

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

    struct list_head *node = l->next;
    while (node != l) {
        struct list_head *del = node;
        node = node->next;
        list_del(del);
        q_release_element(list_entry(del, element_t, list));
    }
    free(l);
}

q_insert_head

• 實作流程：
  1. 排除head或s為NULL的情況
  2. 用malloc()取得節點所需的記憶體空間，要注意malloc()失敗的情況
  3. 設置節點的內容並用list_add()加入串列中
• 提醒：複製字串的函式不要用strcpy()

程式碼

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;

    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;

    int str_space = (strlen(s) + 1) * sizeof(char);
    new->value = malloc(str_space);

    if (!new->value) {
        free(new);
        return false;
    }
    strncpy(new->value, s, str_space);
    *(new->value + str_space) = '\0';
    list_add(&new->list, head);

    return true;
}

q_insert_tail

• 想法 1：比照q_insert_head()的方法

• 想法 2：直接利用q_insert_head()來實作

• 參考alanjian85

程式碼

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;
    return q_insert_head(head->prev, s);
}

q_remove_head

• 實作流程：
  1. 排除head為NULL或是串列為空的情況
  2. 用list_first_entry()取得第一個節點的記憶體位置，並用list_del()從串列中移除該節點
  3. 將節點中的字串內容複製到sp

程式碼

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = list_first_entry(head, element_t, list);
    list_del(&node->list);

    if (bufsize) {
        strncpy(sp, node->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    return node;
}

q_remove_tail

• 實作流程：
  1. 排除head為NULL或是串列為空的情況
  2. 用list_last_entry()取得第一個節點的記憶體位置，並用list_del()從串列中移除該節點
  3. 將節點中的字串內容複製到sp

程式碼

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

q_delete_mid

• 想法 1: 利用快慢指標。慢的指標每次走訪一個節點；快的指標每次走訪兩個節點。當快的指標到達串列最後一個節點時，慢的指標剛好在串列的中心點。
• 想法 2: 本次的串列是 circular doubly-linked list ，可以利用雙向環狀的特性，用兩個指標分別以不同方向（prev和next)走訪串列。當兩個指標相遇或是即將交錯位置，即可判斷中心節點。

程式碼

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;

    struct list_head *front = head->next, *back = head->prev;

    while (front != back && front->next != back) {
        front = front->next;
        back = back->prev;
    }

    list_del(back);
    q_release_element(list_entry(back, element_t, list));
    return true;
}

q_delete_dup

• 想法：在已經排序好的串列中，value相同之節點一定是相鄰的。順著串列的next方向走訪，若相鄰的兩個節點內容一樣，則刪除當前節點。
• 實作方法：
  1. 排除例外狀況
  2. 利用list_for_each_entry_safe()走訪串列，並定義兩個布林變數紀錄狀態：equal，表示相鄰兩節點之字串內容是否相同；flag，表示前一次的equal
  3. 只要equal或flag為其一true，表示當前的節點為與下一個或前一個相同，刪除該節點
  4. 走到最後一個節點（head->prev)時，equal必為false(equal中有定義當前節點的next不能是head的條件)，所以要另外單獨用flag判斷

程式碼

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head) || list_is_singular(head))
        return true;
    element_t *cur_node, *next_node;
    bool flag = false;
    list_for_each_entry_safe (cur_node, next_node, head, list) {
        bool equal = &next_node->list != head &&
                     !strcmp(cur_node->value, next_node->value);
        if (flag || equal) {
            list_del(&cur_node->list);
            q_release_element(cur_node);
            flag = equal;
        }
    }
    if (flag) {
        list_del(&cur_node->list);
        q_release_element(cur_node);
    }

    return true;
}

q_swap

程式碼

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;
    struct list_head *first = head->next, *second = first->next;
    while (first != head && second != head) {
        list_del_init(first);
        list_add(first, second);
        first = first->next;
        second = first->next;
    }
}

q_reverse

• 想法：從head的next方向開始走訪，每經過一個節點便將該節點加到head->next

• 參考25077667

程式碼

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *cur = head->next, *next = cur->next;
    while (cur != head) {
        list_del_init(cur);
        list_add(cur, head);
        cur = next;
        next = cur->next;
    }
}

q_reverseK

• 想法：每次取K個節點來進行q_reverse()
• 注意：q_reverse()的參數是串列的開頭，所以呼叫q_reverse()之後，下次若要再次呼叫該函式，要傳入的引數是尚未做q_reverse()節點的前一個(第14行)

程式碼

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (q_size(head) <= 1)
        return;
    struct list_head *curr, *next, *tmp_head_from = head, tmp_head_to;
    int i = 1;
    INIT_LIST_HEAD(&tmp_head_to);
    list_for_each_safe (curr, next, head) {
        if (i == k) {
            list_cut_position(&tmp_head_to, tmp_head_from, curr);
            q_reverse(&tmp_head_to);
            list_splice_init(&tmp_head_to, tmp_head_from);
            tmp_head_from = next->prev;
            i = 0;
        }
        i++;
    }
}

q_sort

• 想法：使用 merge sort
• 步驟：
  1. 先把環狀鏈結串列改成非環狀
  2. 從串列的中心點分割程兩個串列
  3. 若串列中只剩一個節點則開始合併，否則繼續步驟2
  4. 合併兩個串列
  5. 將串列復原成環狀鏈結串列

q_merge

Valgrind 檢查記憶體錯誤

執行命令make valgrind會發現以下訊息

+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==12489== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==12489==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12489==    by 0x10CBCE: do_new (qtest.c:145)
==12489==    by 0x10DDFA: interpret_cmda (console.c:181)
==12489==    by 0x10E3AF: interpret_cmd (console.c:201)
==12489==    by 0x10E7B0: cmd_select (console.c:610)
==12489==    by 0x10F09C: run_console (console.c:705)
==12489==    by 0x10D1EC: main (qtest.c:1223)
==12489== 
==12489== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==12489==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12489==    by 0x10F110: test_malloc (harness.c:133)
==12489==    by 0x10F605: q_new (queue.c:18)
==12489==    by 0x10CC07: do_new (qtest.c:149)
==12489==    by 0x10DDFA: interpret_cmda (console.c:181)
==12489==    by 0x10E3AF: interpret_cmd (console.c:201)
==12489==    by 0x10E7B0: cmd_select (console.c:610)
==12489==    by 0x10F09C: run_console (console.c:705)
==12489==    by 0x10D1EC: main (qtest.c:1223)
==12489== 
---	trace-01-ops	5/5

關鍵字still reachable，根據Valgrind FAQ可得知，當still reachable發生時，程式可以正常執行但是仍有指標指向未釋放的記憶體。再參考yanjiew的筆記，發現是qtest.c中的q_quit()第一行就直接return true，移除該行程式即可

static bool q_quit(int argc, char *argv[])
{
    return true;
    report(3, "Freeing queue");

學習機率與統計