2022q1 Homework1 (lab0)

contributed by < tseng0201 >

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

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

前置作業:

queue.c實現進度:

了解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();
}

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

2022q1 Homework1 (lab0)

前置作業:

queue.c實現進度:

更多

實驗環境:

queue.c實現:

自定義struct

q_head

定義queue節點

queue_member

自定義函式

void list_swap()

實現的函式

q_new()

q_free()

q_insert_head

q_insert_tail

q_size

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap()

q_reverse

q_sort

merge_two_list()

merge_two_list()

q_sort()

更多

在 qtest 提供新的命令 shuffle

shuffle實現

修改qtest