2022q1 Homework1 (lab0)

contributed by < YiChianLin >

作業說明

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.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):                       16
On-line CPU(s) list:          0-15
Thread(s) per socket:         2
Core(s) per socket:           8
Socket(s):                    1
NUMA node(s):                 1
Vendor ID:                    GenuineIntel
CPU family:                   6
model:                        158
Model name:                   Intel(R) Core(TM) i9-9900KF CPU @ 3.60GHz
Stepping:                     12
CPU MHz:                      3600.000
CPU max MHz:                  5000.0000
CPU min MHz:                  800.0000
BogoMIPS:                     7200.00
L1d cache:                    256 KiB
L1i cache:                    256 KiB
L2 cache:                     2 MiB
L3 cache:                     16 MiB
NUMA node0 CPU(s):            0-15

作業要求

queue.c 僅提供界面(interface) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:

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

函式功能:
- 建立新的「空」佇列
程式運作
1.重新建立新的節點，使用 malloc 新配置記憶體空間
2.使用 lish.c API 中的 INIT_LIST_HEAD 將新建立的 list_head 連結成環狀的結構

struct list_head *q_new()
{
    struct list_head *new_head = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(new_head);

    return new_head;
}

INIT_LIST_HEAD 函式
將未形成 circlar doubly-linked list 的 head 節點串接再一起

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

但是發現並沒有考慮到 malloc 會失敗的問題，在 trace-12-malloc.cmd 會產生 Segmentation fault 的問題產生，所以必須考慮到 malloc 失敗的情形，將程式進行修改
trace-12-malloc.cmd 文件內容 option malloc 50 敘述會將 malloc 的失敗機率提升至 50%

# Test of malloc failure on new
option fail 10
option malloc 50
new
new
new
new
new
new

原程式的報錯內容

Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

程式修改
1.確認欲新增的 head 是否 malloc 成功
2.若成功建立新的 head 節點並回傳，若失敗則釋放配置失敗的空間並為傳 NULL

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

q_free

函式功能:
- 釋放佇列所佔用的記憶體
思考方式:
- 先判斷 queue 的 head 是否為 NULL (注意: empty 不等於 NULL )
- 參考:作業說明, 內文提到:
  - NULL 佇列 : 是指標值為 NULL;
  - 「空」(empty) 的佇列是指向有效結構，但開頭 ( head ) 的值為 NULL;
- 使用暫時的指標走訪每個節點
- 使用 list.h 的 list_entry 可找出每個 linked list 資料的起始位址
- 使用指標 ptr (element_t *ptr) 取得節點資料的位址
- 使用 queue.c 的 q_release_element() 將結構 element_t 的節點裡的 *value 與 linked list 的指標釋放，參考以下的 q_release_element() 程式碼
- 所有 node 釋放後，再將 linked list 的 head 釋放
程式運作:
1.先判斷 linked list 的 head (也就是引數中的 list_head *l) 是否為 NULL（注意 : 若是 empty 則判斷式不成立)
2.使用 tmp 指標走訪每個節點
3.建立 ptr (element_t *ptr) 取得節點資料的位址
4.tmp 指標走訪至下一個點
5.ptr 取得節點資料後再使用 q_release_element() 釋放記憶體空間
6.直到每個 node 釋放結束最後將 l (注意 : l 為沒有 value 的指標) 釋放

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

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

程式可改進之處
- 多使用 list.h 中的 API 進行實作

將 container_of 更換成 list_entry ，雖然兩個函式功能相同，但是在協作上的考量上要能有統一的規範!

除了列出程式碼，你應該說明程式運作和後續可改進之處。
:notes: jserv

q_release_element()

函式說明:
將 element_t 的資料釋放，分別有 element_t 內部的 char 與 element_t 本身的指標

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

q_insert_head

函式功能:
- 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
思考方式:
- 重新建立新的 node ，將資料新增且配置記憶體
- 透過 list_add 函式進行新增 node
程式運作方式
1.先判斷傳入的 head 是否為 NULL (如果是 empty 情況也可以執行)
2.配置 element_t *new 的記憶體，並也配置資料的記憶體 char* new->value 長度為 strlen(s)
3.使用 strncpy() 將 s 複製到 new->value 中(注意: 不能使用 strcpy() 這個函式是不安全的函式不可使用)
4.最後使用 list_add() 將新 node 加入 list 中

ISO/IEC 9899:1999
7.21.2.4 The strncpy function
char *strncpy(char * restrict s1, const char * restrict s2, size_t n);

Description : The strncpy function copies not more than n characters (characters that followanull character are not copied) from the array pointed to by s2 to the array pointed to by s1.
If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.

可以得知函式的使用方式為，將 s2 字符複製 n 個數量到 s1 中

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    } else {
        element_t *new = malloc(sizeof(element_t));
        new->value = malloc(strlen(s) * sizeof(char));
        strncpy(new->value, s, strlen(s));
        list_add(&new->list, head);
    }
    return true;
}

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;
}

程式運作:

*next = head->next; ，將 next 指向 head->next 也就是 A

next->prev = node; ，將 A->prev 指向 new_node

node->next = next; ，將 new_node->next 指向 A

node->prev = head; ，將 new_node->->prev 指向 head 也就是指回 A 的前一個

head->next = node; ，將 head->next 指回 new_node 完成 circular doubly-linked list 新加入一個 node 的操作

發現程式碼的問題:
- 尚未確認 s 是否為 NULL
- new->value 在配置記憶體的時候要多一個空間給結尾符號 \0
- 需要釋放 malloc 失敗的 node 指標

在測試 trace-12-malloc.cmd 時，發現上述程式碼會有問題，使用 malloc 失敗的指標佔用記憶體，需要將未配置成功的指標釋放，且將輸入的字串加入結尾符號 \0，因此經過調整

注意共筆書寫規範：中英文間用一個半形空白字元區隔
:notes: jserv

好的，學生會再多注意共筆書寫規範!YiChianLin

根據發現的問題進行修改:
- if (new && s) 判斷 new 是否能不能 malloc 成功，以及判斷 s 資料是否為 NULL
- 需要在複製的資料加上結尾符號，所以配置記憶體更改為 new->value = malloc((strlen(s) + 1) * sizeof(char))
- *(new->value + strlen(s)) = '\0';
- 最後要透過 free(new) 將有可能配置失敗的記憶體釋放

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

    element_t *new = malloc(sizeof(element_t));
    if (new && s) {
        new->value = malloc((strlen(s) + 1) * sizeof(char));
        if (new->value) {
            strncpy(new->value, s, strlen(s));
            *(new->value + strlen(s)) = '\0';
            list_add(&new->list, head);
            return true;
        }
    }
    free(new);
    return false;
}

q_insert_tail

函式功能:
- 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
程式運作的方式與 q_insert_tail() 相似
使用 list_add_tail() 函數

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    } else {
        element_t *new = malloc(sizeof(element_t));
        new->value = malloc(strlen(s) * sizeof(char));
        strncpy(new->value, s, strlen(s));
        list_add_tail(&new->list, head);
    }
    return true;
}

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;
}

程式運作方式與 list_add 相似，差別在於對 head->prev 操作
加入前

完成操作後

同理在 q_insert_tail() 發現與 q_inset_head() 一樣的問題，並加以修改

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

    element_t *new = malloc(sizeof(element_t));
    if (new &&s) {
        new->value = malloc((strlen(s) + 1) * sizeof(char));
        if (new->value) {
            strncpy(new->value, s, strlen(s));
            *(new->value + strlen(s)) = '\0';
            list_add_tail(&new->list, head);
            return true;
        }
    }
    free(new);
    return false;
}

q_removed_head

函式功能:
- 在佇列開頭 (head) 移去 (remove) 給定的節點;
思考方式:
- 透過 list_entry 函式進行找出節點 element_t 的資料
- 移除 head->next (注意:移除 remove 不等於刪除 delete )
- 確認 bufsize 與欲將移除的資料比較長度
- 將資料複製給 sp
程式運作方式:
1. 先判斷傳入的 linked list 是否為 NULL 或是 empty (只剩下單一的 head)

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

    element_t *rm_ele = list_entry(head->next, element_t, list);
    list_del(head->next);

    int char_len = strlen(rm_ele->value) < (bufsize - 1) ? strlen(rm_ele->value)
                                                         : (bufsize - 1);
    if (sp)
    {
        strncpy(sp, rm_ele->value, char_len);
        *(sp + char_len) = '\0';
        return rm_ele;
    }
    return rm_ele;
}

實作後發現誤解題目意思，原先認為在複製字串長度需要考慮到 bufsize 與 rm_ele->value 之長度，應修正為將 bufsize - 1 字串長度複製給 sp 並且在字串的尾端加入結尾符 \0，所以將其改寫

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

    element_t *rm_ele = list_entry(head->next, element_t, list);
    list_del(head->next);

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

程式運作前

程式運作後

q_removed_tail

函式功能:
- 在佇列尾端 (tail) 移去 (remove) 給定的節點;
思考方式:
- 與 q_removed_head 相似，相異之處在於移除目標改為 head->prev

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

    element_t *rm_ele = container_of(head->prev, element_t, list);
    list_del(head->prev);

    int char_len = strlen(rm_ele->value) < (bufsize - 1) ? strlen(rm_ele->value)
                                                         : (bufsize - 1);

    if (sp)
    {
        strncpy(sp, rm_ele->value, char_len);
        *(sp + char_len) = '\0';
        return rm_ele;
    }
    return rm_ele;
}

與 q_removed_head 遇到的問題相同，將程式加以修正

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

    element_t *rm_ele = list_entry(head->prev, element_t, list);
    list_del(head->prev);

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

程式運作前

程式運作後

q_size

程式功能:
- 計算目前佇列的節點總量;
使用 list.h 中的 list_for_each 可走訪 linked list 的每一個點進行長度的計算

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;
}

list_for_each 函式
在 for 迴圈透過 node 指標指向 head->next 也就是第一個元素，所以在迭代的次數為"linked list 的元素個數"，並不包含空資料的 head

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

q_delete_mid

參考 2095. Delete the Middle Node of a Linked List
程式功能:
- 移走佇列中間的節點;
思考方式:
- 先找出移動到中間點的次數
- head 走訪到該次數的節點(中間點)
- 移除中間節點
- 釋放掉中間節點的資料
程式運作
1. 判斷 linked list 是否存在或是為單一的 head，若是其中一條件符合則會回傳 false
2. 利用 q_size 函式先得出，中間元素的位置，且要判斷偶數或是奇數
3. for 迴圈走放置中間點
4. 使用 list_del 將中間點移除( remove )
5. 使用 list_entry 取得 element_t 的指標
6. 最後使用 q_release_element ，先將 element_t->value (內部資料)釋放，再將 element_t 本身的指標也釋放
程式運作前:

走訪至中間點，走訪到 C 節點

移除中間點 C

釋放 C 的資料

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

    int mid_pos =
        q_size(head) % 2 == 0 ? q_size(head) / 2 : q_size(head) / 2 + 1;

    for (int i = 0; i < mid_pos; i++)
        head = head->next;

    list_del(head);
    element_t *mid_ele = list_entry(head, element_t, list);
    q_release_element(mid_ele);
    return true;
}

程式改進之處:
- 不使用 q_size 函式，而是利用兩個不同速率的指標找到中間點，可增加程式的效率

找尋中間的節點方式好比龜兔賽跑的形式，當兔子到終點的時候，烏龜只跑了一半

將程式改寫

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    
    struct list_head *first = head->next;
    struct list_head *second = head->next;

    while (first != head && first->next != head) {
        first = first->next->next;
        second = second->next;
    }

    list_del(second);
    element_t *mid_ele = list_entry(second, element_t, list);
    q_release_element(mid_ele);
    return true;
}

程式運作先將 first 、 second 指標指向 head->next

struct list_head *first = head->next;
struct list_head *second = head->next;

first != head && first->next != head 直到 first 跑完整個 linked list ，所以 second 就會落在中間點的位置
while 迴圈中 first 每次都移動兩個節點， second 每次移動一個節點

first = first->next->next;
second = second->next;

移除中間點 C

釋放 C 的資料

q_delete_dup

參考 82. Remove Duplicates from Sorted List II
程式功能
- 在已經排序的狀況，移走佇列中具備重複內容的節點;
思考方式
- 走訪每一個節點確認當前節點的下一個節點是否是重複的
- 若有重複，則記錄重複點的起始位置，將下一個節點先移除( remove )再刪除( delete )，直到下一個點不是重複，將起始位置的節點刪除
- 若沒有重複，就會不斷的走訪下一個點，直到回到 head
程式運作

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_is_singular(head))
        return false;
    struct list_head *tmp = head->next;
    struct list_head *if_dup = NULL;

    while (tmp != head) {
        element_t *ele_dup = list_entry(tmp, element_t, list);
        element_t *ele_dup_next = list_entry(tmp->next, element_t, list);

        while (!strcmp(ele_dup->value, ele_dup_next->value)) {
            if_dup = tmp;
            list_del(tmp->next);
            q_release_element(ele_dup_next);
            ele_dup_next = list_entry(tmp->next, element_t, list);
            if (tmp->next == head)
                break;
        }

        tmp = tmp->next;
        if (if_dup) {
            element_t *ele_dup_a = list_entry(if_dup, element_t, list);
            list_del(if_dup);
            q_release_element(ele_dup_a);
            if_dup = NULL;
        }
        if (tmp->next == head)
            break;
    }
    return true;
}

用以下簡單的範例解釋:

tmp 指標指到第一個 node ， tmp->next 指標指到第二個 node ，利用判斷是否有重複元素的指標 if_dup 指向 NULL

tmp 指標指到 A ， tmp->next 指標指到 B 所以兩個元素的值不同，因此兩個指標走放置下一個節點，由於 tmp 與 tmp->next 的元素相同，使 if_dup 記住 tmp 的位置

將 tmp->next 也就是重複的元素 remove 與 delete

tmp 走訪至下一個節點，將有重複點的起始位置 if_dup 節點刪除，重複進行上述動作直到把具有重複的節點都刪除

q_swap

Leetcode swap node
程式功能:
- 交換佇列中鄰近的節點;
思考方式:
- 不直接改變 linked list 的連接串列，而是對 element_t 內部的 element_t->value 進行交換
- 走訪的次數為 linked list 長度的一半次數

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

    struct list_head *forward = head->next;
    struct list_head *forward_next = forward->next;
    char *tmp;
    int size = q_size(head) / 2;
    for (int i = 0; i < size; i++) {
        element_t *ele_first = list_entry(forward, element_t, list);
        element_t *ele_second = list_entry(forward_next, element_t, list);
        tmp = ele_first->value;
        ele_first->value = ele_second->value;
        ele_second->value = tmp;
        forward = forward_next->next;
        forward_next = forward->next;
    }

程式運作:

由 forward 與 forward->next 每次指向鄰近的兩個節點

使用 list_entry 取得 element_t 內部 value 值，再透過暫存的 char *tmp ，將資料進行交換

交換後 forward 與 forward->next 兩個指標前進到下兩個元素進行交換直到走訪全部的 linked list

與 StevenChou43 和 Risheng1128 同學討論後，發現這樣資料的交換方式對記憶體的處理會造成負擔，需要多配置暫存的記憶體空間，造成效率不彰的問題

改善方法:
- 用兩個指標指向前兩個節點
- 移除前面的節點再加入至後面的節點
程式運作:
主要透過 list.h 中的 list_del 與 list_add 進行操作

void q_swap(struct list_head *head)
{
    for (struct list_head *first = head->next,struct list_head *second = first->next;; !(first == head || second == head);
         second = first->next->next, first = first->next) {
        list_del(first);
        list_add(first, second);
    }
}

一開始由 first 與 second 指標指到前兩個元素

移除 first 指標的元素 A

first 指標移除後，再從 second 指標的位置使用 list_add 加入 A

second = first->next second 指到 C ， first = first->next->next first 移動兩個節點到 second 前面一個節點，持續上述的流程直到所有的節點交換完成

q_reverse

程式功能:
- 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
- 舉例: head -> 1 -> 2 -> 3 -> 4 -> head 經反轉後， head -> 4 -> 3 -> 2 -> 1 -> head
思考方式:
- 使用三個指標進行操作，分別為 prev 、 cur 、 next
- 由 cur 指標走訪至每個節點改變其 cur->next 、 cur->prev 指向的位置，分別指向 prev 與 next 指標的位置
- 最後三個節點一起移動直到走訪完整個 linked list

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

    struct list_head *prev = head->prev;
    struct list_head *cur = head;
    struct list_head *next = cur->next;
    do {
        cur->next = prev;
        cur->prev = next;
        prev = cur;
        cur = next;
        next = next->next;
    } while (cur != head);
}

程式運作

初始狀態:

更改 cur->next 從 A 改指到 C ， cur->prev ，從 C 改指到 A

更改後三個指標皆向前走訪， pre 走訪至 cur 的位置，cur 走訪至 next 的位置， next 走訪至 next->next 位置，完成一次的循環動作，直到將所有節點的反轉完成

q_sort

程式功能:
- 以遞增順序來排序鏈結串列的節點
思考方式:
- 使用 merge sort 演算法，使用參考連結的圖片解說運作模式
- 將整串資料進行兩兩分割
- 直到全部的資料為單一資料後，再進行比較、排序
- 所得到的時間複雜度為 ( NlogN )
分割兩串 linked list 自定義函式 sep_list
程式運作
找尋的方式參考至 SteveChou同學開發紀錄找尋中間點的方式

首先，由以下程式碼 6 ~ 11 行中，將兩指標 fast 與 mid 從 linked list 的頭尾兩端進行走訪，直到兩個指標相遇或是中間隔一個節點的時候，方可找到中間節點的位置
以 head 與 mid 中間點分別為兩串資料的起使節點，設定為left 與 right
在程式碼 17 ~ 25 行中，將 linked list 分割成兩段，分割方式使用圖解的方式說明:

初始狀態

left->prev = right->prev; ， left->prev 指向 A ， left->prev->next = left; 也就是 A->next 指回 head

node->next = right; ，,也就是 C->next 指向 B ，最後 right->prev = node; 也就是 B 指回 C ，最後得到分割後的兩段 linked list

而遞迴至剩兩個元素時，則使用 list_del_init 函數自成一個指向自己的節點，最後進入 merge_list 函式中將資料進行合併



























struct list_head *sep_list(struct list_head *head)
{
    if (head == head->next)
        return head;

    struct list_head *fast = head;
    struct list_head *mid = head->prev;
    while (fast != mid && fast->next != mid) {
        fast = fast->next;
        mid = mid->prev;
    }

    struct list_head *left = head;
    struct list_head *right = mid;
    struct list_head *node = left->prev;

    if (list_is_singular(left)) {
        list_del_init(left);
        list_del_init(right);
    } else {
        left->prev = right->prev;
        left->prev->next = left;
        node->next = right;
        right->prev = node;
    }
    return merge_list(sep_list(left), sep_list(right));
}

merge_list 函式說明
作法參考至 2020q1 第 1 週隨堂測驗解題思路共筆文章
將從 sep_list 函式中得到兩半部分的 linked list
程式運作說明:
1. 在 6 、 7 行中，先將兩段資料的尾端接到 NULL 作法類比至單向 linked list 的方式，為判斷式的依據
2. 建立 head 與 tmp 指標作為合併資料用的暫存點
3. 分為兩種情況:
  2.1 head (合併後的資料的起始位置)未建立，使用 strcmp 判斷左右邊的第一個資料，若 return < 0 則使 left 的第一個資料當作是 merge 後資料的 head ，若 return > 0 則反之
  2.2 head (合併後的資料的起始位置)已建立，則使用 list_add_tail 把判斷出較小的資料加入 linked list 中
4. 最後回傳整個 merge 後的結果

ISO/IEC 9899:1999

7.21.4.2 The strcmp function
Description : The strcmp function compares the string pointed to by s1 to the string pointed to by s2.
Returns : The strcmp function returns an integer greater than, equal to, or less than zero, pointed to by s2.

可用來比較字串間的大小，若 s1 較小會 return < 0 的數值，而 s1 較大則會 return > 0 的數值











































struct list_head *merge_list(struct list_head *left, struct list_head *right)
{
    struct list_head *head = NULL;
    struct list_head *tmp = NULL;

    left->prev->next = NULL;
    right->prev->next = NULL;

    while (left || right) {
        if (!right ||
            (left && strcmp(list_entry(left, element_t, list)->value,
                            list_entry(right, element_t, list)->value) < 0)) {
            if (!tmp) {
                head = tmp = left;
                left = left->next;
                if (left)
                    left->prev = tmp->prev;
                INIT_LIST_HEAD(tmp);
            } else {
                tmp = left;
                left = left->next;
                if (left)
                    left->prev = tmp->prev;
                list_add_tail(tmp, head);
            }
        } else {
            if (!tmp) {
                head = tmp = right;
                right = right->next;
                if (right)
                    right->prev = tmp->prev;
                INIT_LIST_HEAD(tmp);
            } else {
                tmp = right;
                right = right->next;
                if (right)
                    right->prev = tmp->prev;
                list_add_tail(tmp, head);
            }
        }
    }
    return head;
}

q_sort 函式說明
1. 將整個 linked list 未含有資料的 head 節點分離出
2. 再將整個 linked list 經過 sep_list 中透過 merge sort 方式，先將資料分段在兩兩合併
3. 排序好的 linked list 再將 head 加入

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

    struct list_head *new_head = head->next;
    list_del(head);
    new_head = sep_list(new_head);
    list_add_tail(head, new_head);
}

在 qtest 中加入 shuffle 指令

在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
在 qtest.c 檔案中加入 do_shuffle 與 q_shuffle 函式
思考方式:
- 每一輪的操作為將最後一個元素與前面的隨機一個元素進行交換
- 之後固定好當前輪次最後一個元素直到最後兩個元素進行交換
- 舉例來說:依順序為[1, 2, 3, 4, 5]
  1. 5 與 1~4其中一個交換，得到[1, 5, 3, 4, 2]
  2. 此時2就不再移動，下一輪要交換的元素為 4 和 1 5 3 其中一個元素
  3. 直到剩下最後兩個元素進行交換
程式運作
1. 先判斷傳入的 linked list 是否為 NULL 、 empty 、 singular
2. 設定兩個迴圈次數的變數，分別為 length 為總函式的操作次數(交換幾輪)，再來是 count 每次的交換後最後一個元素的位置，每經過一輪即遞減透過， rand() % (count - 1) + 1 獲取每一輪的隨機亂數位置
3. 將 3 個指標初始位置都指向 head ， tmp 指標指到隨機位置的前一個位置，主要用來獲得要加入交換來的位置， tail 指標則指到每一輪要交換的為最後一個元素， rand_ptr 為隨機位置的元素指標
4. 每一輪三個指標確定後先將 rand_ptr 隨機的元素移除後再加入在 tail 後方
5. 再來，移除 tail 元素加入至 rand_ptr 被交換前的位置，也就是 tmp 指標元素的下一個
6. 交換後將三個指標再回到 head 準備進行下一輪的交換

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

    srand(time(NULL));
    int length = q_size(head) - 1;
    int count = length + 1;
    struct list_head *tail = head, *tmp = head, *rand_ptr = head;

    for (int i = 0; i < length; i++) {
        int rand_num;
        rand_num = rand() % (count - 1) + 1;
        for (int j = 0; j < count; j++) {
            if (j < rand_num)
                rand_ptr = tmp = tmp->next;
            tail = tail->next;
        }
        tmp = rand_ptr->prev;
        list_del(rand_ptr);
        list_add(rand_ptr, tail);
        list_del(tail);
        list_add(tail, tmp);

        rand_ptr = tail = tmp = head;
        count--;
    }
}

在 qtest.c 中新增 shuffle 命令，觀察其他的宣告命令方式可以得知函式的兩個引數，分別為 argc 與 argv 分別為輸入 command 的引數數量與引數內輸入字元
舉例來說 : 增加 5 個元素為 dophin

cmd>>ih dophin 5

此時 argc = 3 ， argv[0] = ih 、 argv[1] = dophin 、 argv[2] = 5
因此建立一個 shuffle 命令，變數為 argc = 1 ， argv[0] = shuffle ，進入 do_shuffle 會先判斷命令的輸入是否為一個引數，若命令錯誤會顯示 shuffle takes no arguments 的錯誤訊息
l_meta.l 在 qtest.c 中可觀察為整個 linked list 所以判斷 l_meta.l 是否存在
兩者判斷式確認後就可即執行 q_shuffle 的函式中進行打亂元素的功能
最後透過 show_queue 函式將 shuffle 後的結果顯示

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!l_meta.l) {
        report(3, "Warning: Try to access null queue");
        return false;
    }

    q_shuffle(l_meta.l);

    return show_queue(0);
}

測試運行成果，從 ./qtest 進入命令模式，輸入以下指令測試
使用 RAND 指令填入隨機 6 個元素，測試命令的運作情況

cmd> new
l = []
cmd> ih RAND 6
l = [bshbasnli ewfdfyov anepx gqaokyijm xttlxhrjq fjpxj]
cmd> shuffle
l = [xttlxhrjq gqaokyijm fjpxj bshbasnli anepx ewfdfyov]
cmd> shuffle
l = [bshbasnli fjpxj xttlxhrjq ewfdfyov gqaokyijm anepx]
cmd> free
l = NULL

若輸入的引數不正確會跳出錯誤訊息

cmd> new
l = []
cmd> ih RAND 5
l = [lxgjf lqfnd djzywlcf tmbhkpywi ikfrzcsg]
cmd> shuffle 3
shuffle takes no arguments

引入 linux 的程式碼進行 sort 比較

參考 linux list.c 共筆文章

在 merge_final 函式中，處理了不平衡的兩個串列，為了減少過多不必要的迭代次數，以下是原文的附註

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.

list_sort.c 中，主要處理了非 2 倍數的串列，會進行 padding 的動作，引述自原文，在 mergesort 中會希望最差能有 2 : 1 的資料比例進行，主要能避免 cache thrashing 的情況產生，可避免 CPU 的效率急速下降

 * 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.

將 lib/list_sort.c 引入到 lab0-c 專案中
為了將程式碼引用將一些程式的宣告加入
可以看到在 2 、 3 行中，參考至此篇文章 likely and unlikely 的解說，__builtin_expect 為 gcc 引入，目的提高 cpu 的效率，讓 cpu 可以預先取出下一條指令，減少 cpu 的等待時間，在參數中 !!(x) 將 (x) 轉換成 bool 值，可以得到 true/false 所以在執行上 likely(x) 會用 if 的敘述的機會變大
可以看到在原始碼中有 list_cmp_func_t 的宣告，加入了 4 、 5 行的敘述，參考至 list_sort.h對 list_cmp_func_t 的宣告
__attribute__((nonnull(2,3)))確保在 2 3 位的引數中不為空指標

The nonnull attribute specifies that some function parameters should be non-null pointers
文件





typedef unsigned char u8;
#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 *);

這裡參考了 lanser同學的筆記加入了對引數的資料的比較方式，利用 strcmp 比較 merge list 中的兩元素的值(使用 list_entry 取出)

list_sort.c 內部的函式說明:

 * The comparison function @cmp must return > 0 if @a should sort after
 * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
 * sort before @b *or* their original order should be preserved.  It is
 * always called with the element that came first in the input in @a,
 * and list_sort is a stable sort, so it is not necessary to distinguish
 * the @a < @b and @a == @b cases.

int sort_comp(void *p, const struct list_head *a, const struct list_head *b)
{
    return strcmp(list_entry(a, element_t, list)->value,
                  list_entry(b, element_t, list)->value);
}

補完上述的一些宣告就可以使用 lib/list_sort.c 的函式做使用

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    list_sort(NULL, head, sort_comp);
}

比較 q_sort 與 list_sort 效率

在 trace 目錄下新增兩個測試的的檔案分別為 trace-18-sort.cmd 與 trace-19-sort.cmd
trace-18-sort.cmd 內容如下，主要測試以 RAND 指令給定下的隨機資料進行比較，分別進行 100000 、 500000 、 1000000 筆資料的比較
使用 time 指令可以得到 sort 的時間

# Test performance of sort with RAND
option fail 0
option malloc 0
new
ih RAND 100000
time
sort
time

測試的方式使用 perf 工具，參考至 perf 的使用說明

perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-18-sort.cmd

測試運行時間 (second):

Data Number	100000	500000	1000000
list_sort	0.029	0.318	0.721
q_sort	0.034	0.345	0.807
time improved	17.24%	8.5%	11.92%

以取 100000 筆資料的效能結果 (list_sort)

 Performance counter stats for './qtest -f traces/trace-18-sort.cmd' (5 runs):

         1,641,816      cache-misses              #   12.925 % of all cache refs      ( +-  1.74% )
        12,702,519      cache-references                                              ( +-  0.39% )
       280,380,864      instructions              #    0.98  insn per cycle           ( +-  0.00% )
       284,740,366      cycles                                                        ( +-  0.42% )

以取 100000 筆資料的效能結果 (q_sort)

 Performance counter stats for './qtest -f traces/trace-18-sort.cmd' (5 runs):

         1,823,005      cache-misses              #   13.040 % of all cache refs      ( +-  7.01% )
        13,980,297      cache-references                                              ( +-  0.24% )
       297,605,881      instructions              #    0.99  insn per cycle           ( +-  0.03% )
       301,111,612      cycles                                                        ( +-  0.79% )

總合上述的結果進行一點分析比較:
- 在時間的表現上使用 list_sort 的方法在亂數資料的排序下，比自己寫的 q_sort 都有約 10% 的速度提升
- 可以看到在效能上 cache-misses 與 instructions 上也 list_sort 的資源使用上也少了一些，整體是比較有效率的
trace-19-sort.cmd 內容如下，主要測試以給定固定的兩種重複性資料(分別為 gerbil 與 dolphin)，分別進行 100000 、 500000 、 1000000 筆資料的測試

# Test performance of sort with duplication
option fail 0
option malloc 0
new
ih gerbil 50000
ih dolphin 50000
time
sort
time

測試運行時間 (second):

Data Number	100000	500000	1000000
list_sort	0.010	0.085	0.172
q_sort	0.014	0.131	0.282
time improved	40%	54.11%	63.95%

以取 100000 筆資料的效能結果 (list_sort)

 Performance counter stats for './qtest -f traces/trace-18-sort.cmd' (5 runs):

         1,177,740      cache-misses              #   16.648 % of all cache refs      ( +-  6.72% )
         7,074,268      cache-references                                              ( +-  0.41% )
       182,706,651      instructions              #    1.32  insn per cycle           ( +-  0.01% )
       138,478,460      cycles                                                        ( +-  1.18% )

以取 100000 筆資料的效能結果 (q_sort)

 Performance counter stats for './qtest -f traces/trace-18-sort.cmd' (5 runs):

         1,383,044      cache-misses              #   13.986 % of all cache refs      ( +-  8.55% )
         9,888,627      cache-references                                              ( +-  0.63% )
       209,100,672      instructions              #    1.19  insn per cycle           ( +-  0.01% )
       175,059,692      cycles                                                        ( +-  0.64% )

測試的結果分析
- 可以看到在重複的資料進行排序的時候， list_sort 很明顯的就比 q_sort 所花的時間還要短，而且在越多筆資料的表現上，時間上的差距會越來越明顯(40% -> 54.11% -> 63.95%)，可見在 list_sort 對於重複性或預排好的資料處理的速度快了許多
- 而在效能上 cache-misses 與 instructions 上 list_sort 的資源使用上也相對使用的較少