2022q1 Homework1 (lab0)

contributed by < jim12312321 >

Reviewed by `kevinshieh0225`

在執行節點逐一刪除時，可以用 linux kernel api 中的 list_for_each_safe。
有一些我自己沒有注意到的實作細節，比如在移除節點時使用 list_del_init，可讓整體程式碼更安全。
可以在實作函式的改寫版本加上小標題，較容易追蹤文章結構
現在使用 container_of 應該不再需要 cppcheck-suppress nullPointer 了
q_delete_dup 的規則判定有變，所有在原本佇列中發生重複的節點都要刪除，目前程式碼實作並不符合要求。
文件程式碼適時註解。
可實作看看迭代版本的 q_sort 並比較結果。

實驗環境

$ gcc --version
gcc (Ubuntu 11.2.0-7ubuntu2) 11.2.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):                          20
On-line CPU(s) list:             0-19
Thread(s) per core:              1
Core(s) per socket:              14
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           154
Model name:                      12th Gen Intel(R) Core(TM) i7-12700H
Stepping:                        3
CPU MHz:                         2700.000
CPU max MHz:                     6000.0000
CPU min MHz:                     400.0000
BogoMIPS:                        5376.00
Virtualization:                  VT-x
L1d cache:                       336 KiB
L1i cache:                       224 KiB
L2 cache:                        8.8 MiB
NUMA node0 CPU(s):               0-19

作業要求

詳細閱讀 lab0 說明，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改。

q_new: 建立新的「空」佇列
q_free: 釋放佇列所佔用的記憶體
q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點
q_release_element: 釋放特定節點的記憶體空間
q_size: 計算目前佇列的節點總量
q_delete_mid: 移走佇列中間的節點
q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
q_swap: 交換佇列中鄰近的節點
q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
q_sort: 以遞增順序來排序鏈結串列的節點

針對佇列的操作

q_new

建立空佇列，若沒有配置指定大小的記憶體，則回傳 NULL。

commit 1be837

struct list_head *q_new()
{
    element_t *q = malloc(sizeof(element_t));
    if (!q)
        return NULL;
    
    q->value = NULL;
    q->list.next = &q->list;
    q->list.prev = &q->list;
    return &q->list;
}

「當每次提交一些東西時，Git 會產生一個快照，將所有檔案放置在一個物件記錄著，可以輸入 git log（歷史紀錄）會看到提交後 40 個字元長 16 進位的 SHA-1（Secure Hash Algorithm 1）雜湊演算碼，這可以做為提交後的識別碼，使用命令配合 commit 識別碼，一般只需要 6~8 個數字即可辨識。」 – 摘自 git

後來發現在 list.h 中有可以直接初始話佇列的函式（INIT_LIST_HEAD），因此更新。

commit 870612

struct list_head *q_new()
{
    element_t *q = malloc(sizeof(element_t));
    if (q == NULL) {
        return NULL;
    }
    INIT_LIST_HEAD(&q->list);
    return &q->list;
}

q_free

釋放佇列所佔用的記憶體

由於嘗試許久仍寫不出來，因此以下內容有去參考kevinshieh0225、laneser中q_free的寫法

commit c26a4e

void q_free(struct list_head *l)
{
    if (!l)
        return;
        
    struct list_head *node = l->next;
    while (node != l) {
        // cppcheck-suppress nullPointer
        element_t *e = container_of(node, element_t, list);
        node = node->next;
        q_release_element(e);
    }
    // cppcheck-suppress nullPointer
    element_t *head = container_of(l, element_t, list);
    free(head);
}

q_insert_head

給定要插入的新字串，將新字串加入新節點並中在佇列開頭插入給定的新節點。
若新節點為 NULL 或沒有配置記憶體空間，則回傳 false 。若順利加入佇列開頭則回傳 true 。

commit 870612

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (！q) {
        return false;
    }
    q->value = malloc(sizeof(s));
    memset(q->value, '\0', strlen(q->value));
    strncpy(q->value, s, strlen(s));
    list_add(&q->list, head);
    return true;
}

踩坑紀錄

複製字串 (strnpy) 時用 strlen(s) 當作第三個參數（ERROR: Corruption detected in block with address 0x555c8c87df10 when attempting to free it）
- 用設立一個變數計算字串字數取代 strlen

commit c26a4e

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (q == NULL || head == NULL) {
        return false;
    }
    int charsize = 0;
    while (*(s + charsize))
        charsize += 1;
    q->value = malloc(charsize + 1);
    if (q->value == NULL) {
        free(q);
        return false;
    }
    strncpy(q->value, s, charsize);
    q->value[charsize] = '\0';
    list_add(&q->list, head);
    return true;
}

加入檢查 head 是否為 NULL 的判斷式讓程式更加 robust

commit 58c193

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

    int charsize = 0;
    while (*(s + charsize))
        charsize += 1;
    q->value = malloc(charsize + 1);
    if (q->value == NULL) {
        free(q);
        return false;
    }
    strncpy(q->value, s, charsize);
    q->value[charsize] = '\0';
    list_add(&q->list, head);
    return true;
}

q_insert_tail

給定要插入的新字串，將新字串加入新節點並中在佇列結尾插入給定的新節點。
若新節點為 NULL 或沒有配置記憶體空間，則回傳 false 。若順利加入佇列結尾則回傳 true 。

commit 870612

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (！q) {
        return false;
    }
    q->value = malloc(sizeof(s));
    memset(q->value, '\0', strlen(q->value));
    strncpy(q->value, s, strlen(s));
    list_add_tail(&q->list, head);
    return true;
}

跟 q_insert_head 有一樣問題故修正。

commit c26a4e

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (q == NULL || head == NULL) {
        return false;
    }
    int charsize = 0;
    while (*(s + charsize))
        charsize += 1;
    q->value = malloc(charsize + 1);
    if (q->value == NULL) {
        free(q);
        return false;
    }
    strncpy(q->value, s, charsize);
    q->value[charsize] = '\0';
    list_add_tail(&q->list, head);
    return true;
}

加入檢查 head 是否為 NULL 的判斷式讓程式更加 robust

commit 58c193

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *q = malloc(sizeof(element_t));
    if (!q)
        return false;

    int charsize = 0;
    while (*(s + charsize))
        charsize += 1;
    q->value = malloc(charsize + 1);
    if (q->value == NULL) {
        free(q);
        return false;
    }
    strncpy(q->value, s, charsize);
    q->value[charsize] = '\0';
    list_add_tail(&q->list, head);
    return true;
}

q_remove_head

將佇列開頭的節點移除。

回傳 NULL （移除失敗）
- 佇列為空或 NULL
回傳被移除的節點（移除成功）
- 還需將被移除的節點中儲存的值複製到 sp 中

踩坑紀錄

沒有搞清楚 sp 是什麼，胡亂 malloc ，結果不意外的跳出錯誤訊息（ERROR: Failed to store removed value）
- 查看 qtest.c 後發現 remove (在 qtest.c 中傳入 q_remove_head 的變數) 並且他已經配置好記憶體跟初始化內容，因此不需要多此一舉，去掉 malloc 後錯誤訊息即消失。

commit c26a4e

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head) != 0) {
        return NULL;
    }
    if (sp == NULL) {
        return NULL;
    }
    // cppcheck-suppress nullPointer
    element_t *cur_e = list_entry(head->next, element_t, list);
    list_del_init(head->next);
    strncpy(sp, cur_e->value, bufsize - 1);

    return cur_e;
}

將 sp 根據 bufsize 的大小規定，在尾端加上 '\0'

commit fd5f90

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    if (!sp)
        return NULL;
    // cppcheck-suppress nullPointer
    element_t *cur_e = list_entry(head->next, element_t, list);
    list_del_init(head->next);
    strncpy(sp, cur_e->value, bufsize - 1);

    sp[bufsize - 1] = '\0';
    return cur_e;
}

q_remove_tail

將佇列結尾的節點移除。

回傳 NULL （移除失敗）
- 佇列為空或 NULL
回傳被移除的節點（移除成功）
- 還需將被移除的節點中儲存的值複製到 sp 中

commit c26a4e

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head) != 0) {
        return NULL;
    }
    if (sp == NULL) {
        return NULL;
    }
    // cppcheck-suppress nullPointer
    element_t *cur_e = list_entry(head->prev, element_t, list);
    list_del_init(head->prev);
    strncpy(sp, cur_e->value, bufsize - 1);

    return cur_e;
}

將 sp 根據 bufsize 的大小規定，在尾端加上 '\0'

commit fd5f90

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    if (!sp)
        return NULL;
    // cppcheck-suppress nullPointer
    element_t *cur_e = list_entry(head->prev, element_t, list);
    list_del_init(head->prev);
    strncpy(sp, cur_e->value, bufsize - 1);

    sp[bufsize - 1] = '\0';
    return cur_e;
}

q_size

回傳佇列長度,若佇列是為 NULL 或空佇列則回傳 0。

以下程式碼源自老師的 lab0 作業要求
commit 392750

int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

移除佇列中間的節點並將其佔用記憶體釋放。

回傳 true (移除成功)
- 移除並釋放中間的節點
回傳 false (移除失敗)
- 佇列為 NULL 或空佇列

commit 16e285

bool q_delete_mid(struct list_head *head)
{
    if (head == NULL || list_empty(head) != 0) {
        return false;
    }

    if (list_is_singular(head)) {
        head = head->next;
        // cppcheck-suppress nullPointer
        element_t *e = container_of(head, element_t, list);
        list_del(head);
        q_release_element(e);
        return true;
    }

    int del_n_index = 0;
    struct list_head *node = head->next;
    /* even nodes  */
    if (q_size(node) % 2 == 0) {
        del_n_index = q_size(node) / 2;
    } else { /* odd nodes  */
        del_n_index = (q_size(node) + 1) / 2 - 1;
    }
    while (del_n_index > 0) {
        node = node->next;
        del_n_index--;
    }
    // cppcheck-suppress nullPointer
    element_t *e = container_of(node, element_t, list);
    list_del(node);
    q_release_element(e);
    return true;
}

利用你所不知道的 C 語言: linked list 和非連續記憶體中提到的 fast/slow 指標找中間節點的方法重新改寫。

commit 430645






























bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    if (list_is_singular(head)) {
        head = head->next;
        // cppcheck-suppress nullPointer
        element_t *e = container_of(head, element_t, list);
        list_del(head);
        q_release_element(e);
        return true;
    }

    struct list_head *fast = head, *slow = head;
    while (true) {
        if (fast->next == head || fast->next->next == head)
            break;
        fast = fast->next->next;
        slow = slow->next;
    }
    slow = slow->next;

    // cppcheck-suppress nullPointer
    element_t *e = container_of(node, element_t, list);
    list_del(node);
    element_t *e = container_of(slow, element_t, list);
    list_del(slow);
    q_release_element(e);
    return true;
}

q_delete_dup

將佇列中存有重複的節點移除並釋放其記憶體空間。

commit ec6546

void q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *node, *del;
    element_t *del_node;
    node = head->next;
    while (node != head) {
        char *cstr, *nstr;
        // cppcheck-suppress nullPointer
        cstr = list_entry(node, element_t, list)->value;
        if (node->next == head) {
            break;
        }
        // cppcheck-suppress nullPointer
        nstr = list_entry(node->next, element_t, list)->value;
        if (strcmp(cstr, nstr) == 0) {
            del = node;
            node = node->next;
            list_del_init(del);
            // cppcheck-suppress nullPointer
            del_node = list_entry(del, element_t, list);
            q_release_element(del_node);
        } else {
            node = node->next;
        }
    }
    return true;
}

q_swap

將佇列中兩兩相鄰的節點互換。

commit 0508d3

void q_swap(struct list_head *head)
{
    struct list_head *odd, *even;
    odd = head->next;
    even = odd->next;
    while (true) {
        // swap odd and even
        odd->next = even->next;
        odd->next->prev = odd;
        even->prev = odd->prev;
        even->prev->next = even;
        odd->prev = even;
        even->next = odd;
        // end
        odd = odd->next;
        even = odd->next;
        if (odd == head || even == head) {
            break;
        }
    }
}

q_reverse

反向順序重新排列鏈結串列，並且不能釋放或配置新的記憶體空間。

commit 3cd169

void q_reverse(struct list_head *head)
{
    if (head == NULL || list_empty(head) != 0) {
        return;
    }
    struct list_head *node, *temp;
    for (node = head->next; node != head; node = node->prev) {
        temp = node->next;
        node->next = node->prev;
        node->prev = temp;
    }
    temp = head->next;
    head->next = head->prev;
    head->prev = temp;
}

q_sort

利用 merge sort q_delete_dup將佇列依照佇列節點中的字串遞增排序。

以下程式優化太糟，無法通過效能測試，已更新較有效率的版本

commit 94ee22

struct list_head *merge(struct list_head *left, struct list_head *right)
{
    struct list_head *head, *cur;

    // cppcheck-suppress nullPointer
    char *lstr = list_entry(left, element_t, list)->value;
    // cppcheck-suppress nullPointer
    char *rstr = list_entry(right, element_t, list)->value;

    int cmp = strcmp(lstr, rstr);
    if (cmp > 0) {  // left > right
        head = right;
        right = right->next;
        right->prev = head->prev;
        right->prev->next = right;
        head->next = head;
        head->prev = head;
    } else {  // left <= right
        head = left;
        left = left->next;
        left->prev = head->prev;
        left->prev->next = left;
        head->next = head;
        head->prev = head;
    }
    cur = head;

    if (head == left) {
        left = NULL;
    } else if (head == right) {
        right = NULL;
    }

    while (true) {
        if (left == NULL) {
            cur->next = right;
            head->prev = right->prev;
            right->prev->next = head;
            right->prev = cur;
            break;
        } else if (right == NULL) {
            cur->next = left;
            head->prev = left->prev;
            left->prev->next = head;
            left->prev = cur;
            break;
        }
        // cppcheck-suppress nullPointer
        lstr = list_entry(left, element_t, list)->value;
        // cppcheck-suppress nullPointer
        rstr = list_entry(right, element_t, list)->value;
        cmp = strcmp(lstr, rstr);

        if (cmp > 0) {  // left > right
            cur->next = right;
            if (q_size(right) == 0) {
                right->prev = cur;
                right = NULL;
            } else {
                right = right->next;
                right->prev = right->prev->prev;
                right->prev->next = right;
                cur->next->prev = cur;
            }
            cur = cur->next;
            cur->next = head;
            head->prev = cur;
        } else {  // left <= right
            cur->next = left;
            if (q_size(left) == 0) {
                left->prev = cur;
                left = NULL;
            } else {
                left = left->next;
                left->prev = left->prev->prev;
                left->prev->next = left;
                cur->next->prev = cur;
            }
            cur = cur->next;
            cur->next = head;
            head->prev = cur;
        }
    }

    return head;
}

struct list_head *mergesort(struct list_head *head)
{
    if (head->next == head) {
        return head;
    }
    int mid_index = q_size(head) / 2;
    struct list_head *mid, *temp = head;
    while (mid_index > 0) {
        temp = temp->next;
        mid_index--;
    }
    mid = temp->next;
    temp->next = head;
    mid->prev = head->prev;
    head->prev->next = mid;
    head->prev = temp;

    struct list_head *left = mergesort(head), *right = mergesort(mid);
    return merge(left, right);
}

void q_sort(struct list_head *head)
{
    if (head == NULL || list_empty(head) != 0 || list_is_singular(head) != 0) {
        return;
    }
    struct list_head *node = head->next;

    node->prev = head->prev;
    node->prev->next = node;
    head->prev = NULL;
    head->next = NULL;

    node = mergesort(node);

    head->next = node;
    head->prev = node->prev;
    node->prev->next = head;
    node->prev = head;
}

看完你所不知道的 C 語言: linked list 和非連續記憶體後，利用裡面老師示範的技巧改寫 mergesort

解惑紀錄

在理解程式碼並實作的過程中，我對於 mergeTwoLists 中的這段程式碼不了解，經過查閱一些資料後，總算理解這樣做的用意，因而紀錄。（~~以下內容為我個人理解，若有誤，歡迎題點。~~）

不用在開發紀錄中說客套話。

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

    *ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);

一開始我對這段程式碼存有幾點疑惑

uintptr_t 是什麼？
為什麼這樣可以取代 if-else ？
為什麼這樣可以增進效能？

uintptr_t 是什麼？
根據 C99 中的規範，提供如 intptr_t,uintptr_t 讓任何可指向 void 的指標可以與之相互轉換且內容不變，因此便可以對指標所指向之地址進行操作 (e.g. void * 無法進行如++或–等數值操作) 。
TODO: 翻閱 C 語言規格書
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
jserv
參考資料：
~~intptr_t、uintptr_t数据类型的解析~~
避免看這種二手資訊，無助於你理解，而且屆時語言標準更動時，你無從掌握
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
jserv
C99 standard §7.18.1.4 (p.257)
為什麼這樣可以取代 if-else ？
因為 NULL 經過 uintptr_t 的轉換後就會變成 0 ，因此就可以透過 or 的操作，直接得到不是 NULL 的另一個指標。
為什麼這樣可以增進效能？
跟處理器面對分支 (branch) 時的處理方式有關，若預測錯分支就會造成效能損耗。因此能減少分支的使用就有可能增進效能 (如果每次分支處理都猜對，那有沒有用 if-else 是沒有差別的)
以講義提供的範例程式碼來說，if 和 else 成立的機會約略是各 50%，於是分支預測器就很難總是猜對，你可以翻閱 CS:APP 第 3 章，得知如何分析產生的組合語言輸出，屆時你就會發現，最初的程式碼存在比較和分支跳躍等指令，反過來說，調整後的程式碼只要單純的 bitwise OR 操作，從而省下 CPU 週期。
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
jserv
參考資料：

代码里写很多if会影响效率吗?
分支預測器 -wiki
去翻閱計算機組織/結構的教科書，裡頭有 branch predictor 的說明，你需要「完整」的認識，而非從隻字片語中找線索，後者的難度比認真讀教科書還高，畢竟你變成「偵探」了
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
jserv

commit b7014e
commit 39f6ca

struct list_head *mergeTwoLists(struct list_head *left, struct list_head *right)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; left && right; *node = (*node)->next) {
        // cppcheck-suppress nullPointer
        node = (strcmp(list_entry(left, element_t, list)->value,
                       // cppcheck-suppress nullPointer
                       list_entry(right, element_t, list)->value) < 0)
                   ? &left
                   : &right;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);

    return head;
}

struct list_head *mergesort(struct list_head *head)
{
    if (!head->next)
        return head;

    struct list_head *fast = head, *slow = head, *mid;
    while (true) {
        if (!fast->next || !fast->next->next)
            break;
        fast = fast->next->next;
        slow = slow->next;
    }

    mid = slow->next;
    slow->next = NULL;

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

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *node = head->next, *temp;

    head->prev->next = NULL;
    head->next = NULL;

    node = mergesort(node);

    temp = head;
    temp->next = node;
    while (temp->next) {
        temp->next->prev = temp;
        temp = temp->next;
    }
    temp->next = head;
    head->prev = temp;
}

參考資訊

白耀升

2022/02/16 14:27:09

老師您好，我沒找到您說的錯誤耶？請問是哪個位置的中英文間沒有滿足一個半形空白的要求？再麻煩您指點，感謝。 (Edited)

Jim Huang

2022/02/16 23:20:04

```cpp int q_size(struct l

不需要在此標注日期，你只要提及 git commit 的 SHA-1 即可識別程式碼的變更內容和精確的日期時間 (Edited)

maromaSamsa

2022/04/08 09:55:24

```cpp struct list_head *q_new() { element_t *q = malloc(sizeof(element_t)); if (q == NULL) { return NULL; } INIT_LIST_HEAD(&q->list); return &q->list; } ```

您好，想請問若這樣修改的話，看起來並未初始化 q->value ，這是否會造成影響？謝謝 (Edited)

2022q1 Homework1 (lab0)

Reviewed by kevinshieh0225

實驗環境

作業要求

針對佇列的操作

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

參考資訊

Reviewed by `kevinshieh0225`