2022q1 Homework1 (lab0)

contributed by < tseng0201 >

在「作業區」以「固定網址」填寫 HackMD 超連結，請注意細節！

jserv

前置作業:

• 閱讀 你所不知道的C語言：指標篇
• 閱讀 你所不知道的 C 語言: linked list 和非連續記憶體
• 詳閱 lab0 作業需求

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_release_element: 釋放特定節點的記憶體空間;
• 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_sort: 以遞增順序來排序鏈結串列的節;

更多

• 了解lab0中提到的分析工具 Cppcheck Valgrind Perf
• 在 qtest 提供新的命令 shuffle
• 在 qtest 提供新的命令 web
• 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。
• 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
• 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

實驗環境:

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):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           94
Model name:                      Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
Stepping:                        3
CPU MHz:                         816.656
CPU max MHz:                     4000.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6799.81
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        8 MiB
NUMA node0 CPU(s):               0-7

queue.c實現:

想法 ：利用 linux 已經實現的 struct list_head 與其相關巨集/函式進行 queue 節點間的移動,再透過 container_of / list_entry 取得其他該節點的成員進行操作

自定義struct

q_head

在原有的head定義下新增 count 用於計算queue的長度,
count 為0時代表一個空的 queue

typedef struct {
    int count;
    struct list_head group;
} q_head;

定義queue節點

queue_member

已定義於queuq.h
藉由定義好的 struct list_head 進行節點間的移動, 以成員 value(pointer to char）紀錄該節點的資料

* Linked list element */
typedef struct {
    /* Pointer to array holding string.
     * This array needs to be explicitly allocated and freed
     */
    char *value;
    struct list_head list;
} element_t;

自定義函式

q_delete_element()
delete 一個 queue member 先移出 queue 再釋放其記憶體位置

void q_delete_element(struct list_head *node)
{
    if (!node) {
        return;
    }
    list_del(node);
    free(list_entry(node, element_t, list)->value);
    free(list_entry(node, element_t, list));

}

void list_swap()

交換兩個 list_head* 所指向的位置

void list_swap(struct list_head **list_addr1 ,struct list_head **list_addr2 )
{
        struct list_head *temp = *list_addr2;
        *list_addr2 = *list_addr1;
        *list_addr1 = temp;
}

實現的函式

q_new()

建立一個空的queue head，並將 count 設為0
並透過 INIT_LIST_HEAD() 將 prev, next指標都指向自己
當 memory allocate 失敗將會返回 NULL
新增
當 allocate 失敗時回傳 NULL 不再進行後續操作

struct list_head *q_new()
{
    q_head *temp = malloc(sizeof(q_head));
    if (!temp) {
        return NULL;
    }
    temp->count = 0;
    INIT_LIST_HEAD(&temp->list);
    return &temp->list;
}

q_free()

將整個 queue 包含 queue head 所佔用的記憶體釋放,由於 queue 的資料是由 pointer 紀錄,所以要先釋放掉其指向的記憶體,再釋放掉節點本身

函式透過 temp 紀錄要消除的節點, 並修改 queue head 的 next 紀錄下一個要消去的節點, 最後才將queue head 釋放

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

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

    free(list_entry(l, q_head, list));
    return;
}

q_insert_head

建立一個新的節點插入在 head next, 由於字串是由 pointer傳入 無法使用 sizeof 取得字串長度所以直接使用 for loop 計算長度後再分配適當的空間
建立新的節點後使用 list_add 自動將其指標指向正確位置
使用strlcpy 而非 strncpy 兩者都可以防止輸入大於分配的空間,但strlcpy還會將最後一個改為 '\0' 用起來更安全
新增
當 data malloc 失敗時函式回傳 false,且要將剛建立的 element_t 物件釋放 (free)

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *temp_member = malloc(sizeof(element_t));
    if (!temp_member) {
        return false;
    }
    int count = 0;
    for (; s[count]; count++) {
    };
    temp_member->value = malloc(count + 1 * sizeof(char));
    //check successful malloc 
    if (!temp_member->value ) {
        free(temp_member);
        return false;
    }
    strlcpy(temp_member->value, s, count + 1);
    list_add(&temp_member->list, head);
    list_entry(head, q_head, list)->count += 1;
    return true;
}

q_insert_tail

同 q_insert_head ,但指標操作改為list_add_tail
新增
當 data malloc 失敗時函式回傳 false,且要將剛建立的 element_t 物件釋放 (free)

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *temp_member = malloc(sizeof(element_t));
    if (!temp_member) {
        return false;
    }
    int count = 0;
    for (; s[count]; count++) {
    };
    temp_member->value = malloc(count + 1 * sizeof(char));
    if (!temp_member->value ) {
        free(temp_member);
        return false;
    }
    strlcpy(temp_member->value, s, count + 1);
    list_add_tail(&temp_member->list, head);
    list_entry(head, q_head, list)->count += 1;
    return true;
}

q_size

回傳 queue 的長度, 直接回傳 q_head 的 count 即可

int q_size(struct list_head *head)
{
    if (!head) {
        return 0;
    }
    return list_entry(head, q_head, group)->count;
}

q_remove_head

將第一個 queue 節點從 queue 中斷開, 並將其 value 轉移至
sp
當 head 為 NULL 或 empty 時回傳 NULL
使用strlcpy 進行字串複製這樣會自動在最後加上 '\0'
並使用list_del進行 queue之間的修改

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head)){
        return NULL;
    }
    element_t *temp = list_entry(head->next, element_t, list);
    list_del(head->next);
    if (sp) {
        strlcpy(sp, temp->value, bufsize);
    }
    list_entry(head, q_head, list)->count -= 1;
    return temp;
}

q_remove_tail

刪除queue中最後的節點 ,概念q_remove_head

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head)){
        return NULL;
    }
    element_t *temp = list_entry(head->prev, element_t, list);
    list_del(head->prev);
    if (sp) {
        strlcpy(sp, temp->value, bufsize);
    }
    list_entry(head, q_head, list)->count -= 1;
    return temp;
}

q_size

回傳 queue 的長度, 直接回傳 q_head 的 count 即可

int q_size(struct list_head *head)
{
    if (!head) {
        return 0;
    }
    return list_entry(head, q_head, group)->count;
}

q_delete_mid

移除queue中間的節點, 透過 queue head 的 count 即可快速求出該中間節點,透過ptr移動至該節點後先移出(remove) queue 再進行刪除(delete)
count 要減1
待改進的點 :
head 其實算完 count 後不需要了可以直接拿來當ptr

bool q_delete_mid(struct list_head *head)
{
    
    if (!head || list_empty(head)) {
        return false;
    }
    int n = list_entry(head, q_head, list)->count-- / 2;
    // list_entry(head, q_head, list)->count -= 1;
    struct list_head *ptr = head->next;
    while (n--) {
        ptr = ptr->next;
    }
    q_delete_element(ptr);
    return true;
}

q_delete_dup

把重複的節點都刪除 e.g. old: 1->2->2->3 改為 1->3
注意 ：此程式必須為排序過的 list 才適用
設定 ptr 為當前節點的節點並與 ptr->next 比較,如果相同則刪除ptr->next 否則該節點保留
kill_self 用來紀錄當前 ptr 是否為duplicate的一部分 如果kill_self 為 true 則節點也應該刪除

bool q_delete_dup(struct list_head *head)
{
    if (!head) {
        return false;
    }
    
    if (list_empty(head) || list_is_singular(head)) {
        return true;
    }
    int count = list_entry(head, q_head, list)->count;
    struct list_head * ptr = head->next;
    bool kill_self = false;
    while (ptr != head && ptr->next != head) {
        while (ptr->next != head && !strcmp(list_entry(ptr, element_t, list)->value, list_entry(ptr->next, element_t, list)->value)) {
            q_delete_element(ptr->next);
            count--;
            kill_self = true;
        }
        ptr = ptr->next;
        if (kill_self) {
            q_delete_element(ptr->prev);
            kill_self = false;
            count--;
        }
    }
    list_entry(head, q_head, list)->count = count;
    return true;
}

q_swap()

將 queue 中的節點每兩個兩個相反,且不能改變node value
e.g. a->b->c->d 改為b->a->d->c
此程式以單向 link_list 方向思考,最後再以 while 迴圈將prev 指向正確的節點
ptr 紀錄當前節點 first second 紀錄當前節點的下個與下下個
代表要交換的兩個節點

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

    struct list_head * ptr = head;
    while (ptr->next != head && ptr->next->next != head) {
        struct list_head * first = ptr->next;
        struct list_head * second = ptr->next->next;
        first->next = second->next;
        ptr->next = second;
        ptr->next->next = first;
        ptr = ptr->next->next;
    }
    ptr = head;
    while (ptr->next != head) {
        ptr->next->prev = ptr; 
        ptr = ptr->next;
    }
    head->prev = ptr;
    return ;
}

q_reverse

由於 queue是雙向的環 所以只要將每個節點(包含 head)的 prev 與 next 指向的位置換就好

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return;
    }
    struct list_head *temp = head;
    do {
        struct list_head *t = temp->next;
        temp->next = temp->prev;
        temp->prev = t;
        temp = temp->prev;
    } while (temp != head);
}

q_sort

以三個函式實現
1.q_sort : 呼叫界面
2.list_mergesort() : 執行mergesort
3.merge_two_list : 執行merge

merge_two_list()

引用：你所不知道的 C 語言: linked list 和非連續記憶體中的實做
進行
概念是讓一個指標 ptr 每次都走向 q_1 或 q_2 value 比較小的節點,然後移動被選中的節點至其下一個,當ptr走完兩個 list 便可得到一個依 value 由小到大串在一起的list

程式碼解析
在引用的實做中, 使用** 進行對指標的紀錄與移動

1.ptrㄧ開始指向節點本身而之後都是指向節點的 next

2.node 為紀錄目前比較小的那個節點並進行操作

*node = (*node)->next

上列函式可看做

if(l1 < l2)
    l1 = l1->next;
else
    l1 = l1->next;

3.透過 node 紀錄當前較小的節點並透過 ptr 串起走訪的節點

    struct list_head** ptr ;
    *ptr = *node;
    可以看作
    struct list_head* ptr;
    ptr->next = (q_1 < q_2) ? q_1 : q_2

4.地址的 bitwise操作
c 不允對指標指向的地址做 or 所以將地址強制轉形成 unsigned int 進行操作後再轉回本的型態
C99規格書上面寫道

6.5.12 BitwiseinclusiveORoperator
Constraints:
Each of the operands shall have integer type.

    (struct list_head *) ((__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2);

以下為完整程式碼

struct list_head* merge_two_list(struct list_head *q_1,struct list_head *q_2)
{
    if (!q_1 || !q_2) return (struct list_head *) ((__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2);
    struct list_head *head = NULL, **ptr = &head, **node;
    for (node = NULL; q_1 && q_2; *node = (*node)->next) {
        node = (strcmp(list_entry(q_1, element_t, list)->value, list_entry(q_2, element_t, list)->value) <= 0 ) ? &q_1: &q_2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *)( (__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2 );
    return head;
}

merge_two_list()

利用 divine and counquer 的概念進行分割與合併,將原本 queue
分隔為多個長度為1的 queue 後再進行合併,分割使 用slow、fast 指標取的中間的節點、並分為left 與 right 處理
最後回傳merge後的queue

struct list_head* list_mergesort(struct list_head * head)
{
    if (!head || !head->next) {
        return head;
    }
    struct list_head *slow = head;
    struct list_head *fast = head->next;
    for (; fast && fast->next; fast = fast->next->next) {
        slow = slow->next;
    }
    fast = slow->next;
    slow->next = NULL;
    struct list_head * left = list_mergesort(head);
    struct list_head * right = list_mergesort(fast);
    return merge_two_list(left, right);
}

q_sort()

首先先將環狀的queue 斷開成直線的queue

head->prev->next = NULL;

再將queue進行sort

head->next = list_mergesort(head->next);

最後透過迴圈將 prev 修正並修復回環狀的queue

    struct list_head *ptr = head;
    while (ptr->next) {
        ptr->next->prev = ptr; 
        ptr = ptr->next;
    }
    ptr->next = head;
    head->prev = ptr;
    ptr = head;

以下為完整程式碼

void q_sort(struct list_head *head) 
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    head->prev->next = NULL;
    head->next = list_mergesort(head->next);
    struct list_head *ptr = head;
    while (ptr->next) {
        ptr->next->prev = ptr; 
        ptr = ptr->next;
    }
    ptr->next = head;
    head->prev = ptr;
    ptr = head;
    return;
}

更多

在 qtest 提供新的命令 shuffle

shuffle實現

使用 Fisher–Yates shuffle 演算法,每次隨機選擇一個節點與最後一個尚未交換過的節點交換其 value (不改變節點順序)

void q_shuffle(struct list_head *head)
{
    //檢查head 是否需要進行shuffle
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    //取的目前的節點數
    int count = list_entry(head, q_head, list)->count;
    //紀錄最後一個尚未交換過的節點
    struct list_head *last = head->prev;
    //不斷的進行隨機的交換
    for (; count >1; count--) {
        int need_change = rand()%count;
        struct list_head *ptr = head->next;
        //移動指標至被選到的節點
        for(; need_change > 0; need_change--) {
            ptr = ptr->next;
        }
        //交換被選到的節點與最後的節點
        char *temp =  list_entry(last, element_t, list)->value;
        list_entry(last, element_t, list)->value = list_entry(ptr, element_t, list)->value;
        list_entry(ptr, element_t, list)->value = temp;
        last = last->prev;
    }
    return;
}

修改qtest

根據 lab0 的引導在 console_init()新增指令shuffle, 並實現 do_shuffle 函式進行 q_shuffle
此函式參考 do_swap() 實現

static bool do_shuffle(int argc, char *argv[])
{
    //檢查時否有輸入其他參數
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    //檢查queue是否已建立
    if (!l_meta.l)
        report(3, "Warning: Try to access null queue");
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();

    set_noallocate_mode(false);

    show_queue(3);
    return !error_check();
}