2023q1 Homework1 (lab0)

contributed by < LiChiiiii >

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
    CPU family:          6
    Model:               94
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4000.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6799.81

完成 queue.c

TOTAL SCORE : 100/100

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

已修正
LiChiiiii

`q_new`

利用 malloc() 配置記憶體空間，若記憶體配置失敗回傳 NULL，成功則使用 list.h 中的 INIT_LIST_HEAD() 來初始化 head。

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

`q_free`

使用 list.h 中的 list_for_each_entry_safe() 走訪佇列中每個節點，並使用 q_release_element() 釋放每一個元素，迴圈做完只會剩下指向佇列的 l，最後free(l)完成此功能。

list_for_each_entry_safe() 會額外使用一個指標 safe 來暫存下一次循環的 entry，使得每次在執行 q_release_element() 時不會影響迴圈的執行。

void q_free(struct list_head *l)
{
    if(!l)
        return;
    element_t *itm=NULL, *is=NULL;
    list_for_each_entry_safe (itm, is, l, list)
    {
        q_release_element(itm);   
    }
    free(l);
}

`q_insert_head`

先替 new_itm （欲新增至佇列的元素）配置一個資料結構為 element_t 的記憶體空間。

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

計算 s （欲新增至 new_itm->value 的字元）大小，並依據計算出的大小配置記憶體空間至 new_itm->value ，透過條件式確認配置成功後，利用 memcpy() 將 s 複製到 new_itm->value 中，最後呼叫 list_add() 將 new_itm 元素加入佇列的第一個。

剛開始忘記在判斷配置失敗後要執行 free(new_itm) （第11行），導致報錯 error: Memory leak: new_itm [memleak] 。

















bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_itm = malloc(sizeof(*new_itm));
    if (!new_itm)
        return false;
    size_t size = strlen(s) + 1;
    new_itm->value = malloc(size * sizeof(char));
    if (!new_itm->value) {
        free(new_itm);
        return false;
    }   
    memcpy(new_itm->value, s, size);
    list_add(&new_itm->list, head);
    return true;
}

`q_insert_tail`

與 q_insert_head 的思路一樣，將第15行改成 list_add_tail() 。

















bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_itm = malloc(sizeof(*new_itm));
    if (!new_itm)
        return false;
    size_t size = strlen(s) + 1;
    new_itm->value = malloc(size * sizeof(char));
    if (!new_itm->value) {
        free(new_itm);
        return false;
    }   
    memcpy(new_itm->value, s, size);
    list_add_tail(&new_itm->list, head);
    return true;
}

`q_remove_head`

使用 list_first_entry() 找到佇列中第一個元素，並透過 list_del() 刪除此元素。
使用 strncpy() 來複製字串至 sp 以避免 buffer overflow 的問題，但會產生以下狀況，若來源字元數小於限制複製字元的個數，剩下未填滿的部分會全部補上 '\0'，反之則要手動補 '\0'（第9行）。












element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    element_t *itm = list_first_entry(head, element_t, list);
    list_del(&itm->list);
    if (sp != NULL) {
        strncpy(sp, itm->value, bufsize - 1); 
        sp[bufsize - 1] = '\0';
    }   
    return itm;
}

`q_remove_tail`

與 q_remove_head 的思路一樣，將第5行改成 list_last_entry() 。












element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    element_t *itm = list_last_entry(head, element_t, list);
    list_del(&itm->list);
    if (sp != NULL) {                             
        strncpy(sp, itm->value, bufsize - 1); 
        sp[bufsize - 1] = '\0';
    }   
    return itm;
}

`q_size`

使用 list.h 中的 list_for_each() 走訪佇列，紀錄佇列長度。

int q_size(struct list_head *head)
{
    int size = 0;
    if (!head)
        return size;
    struct list_head *itm;
    list_for_each (itm, head) {
        size++;
    }   
    return size;
}

`q_delete_mid`

利用 doubly-linked list 的特性，宣告兩個指標 front 和 rear 分別從前向後和從後到前同時移動，直到重疊即可找到 mid 並刪除。利用 front!=rear->prev 條件式來尋找含偶數個元素的佇列之 mid ，利用 front!=rear 條件式來尋找含奇數個元素的佇列之 mid （第6行）。

原本的寫法是先寫 q_release_element(mid) ，才接著寫 list_del(front) ，這樣會先把 front 指向的元素之記憶體空間釋放掉，導致報錯： Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)















bool q_delete_mid(struct list_head *head)
{
    if (!head)
        return false;
    struct list_head *front = head->next, *rear = head->prev;
    while (front != rear->prev && front != rear) {
        front = front->next;
        rear = rear->prev;
    }
    element_t *mid = list_entry(front, element_t, list);
    list_del(front);
    q_release_element(mid);
    return true;
}
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/

`q_delete_dup`

flag ：決定當前元素是否為應被刪除的元素
利用迴圈比較當前元素 cur_el 以及前一個元素 cur_prev_el 之值是否相同，若相同則刪除 cur_prev_el 並設定 flag=1 ，若不相同但 flag=1 則代表當前元素 cur_el 為重複元素中最後一個元素，也就是應被刪除的元素。

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

    int flag = 0;
    struct list_head *cur, *safe = NULL;
    list_for_each_safe (cur, safe, head) {
        if (cur->prev == head)
            continue;
        element_t *cur_el = list_entry(cur, element_t, list);
        element_t *cur_prev_el = list_entry(cur->prev, element_t, list);
        if (!strcmp(cur_el->value, cur_prev_el->value)) {
            list_del(cur->prev);
            q_release_element(cur_prev_el);
            flag = 1;
            if (cur == head->prev){
                list_del(cur);
                q_release_element(cur_el);
                return true;
            }
        } else if (flag == 1) {
            list_del(cur->prev);
            q_release_element(cur_prev_el);
            flag = 0;
        }
    }
    return true;
}
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

`q_swap`

flag ：決定當前元素是否與前一個元素交換
若 flag=0 則設定 flag=1並跳過此元素，若 flag=1 則當前元素與前一個元素交換（前一個元素移到當前元素後面）並設定 flag=0 。

void q_swap(struct list_head *head)
{
    if (!head || list_is_singular(head) || list_empty(head))
        return;
    int flag = 0;
    struct list_head *cur, *safe = NULL;

    list_for_each_safe (cur, safe, head) {
        if (cur->prev == head || flag == 0) {
            flag = 1;
            continue;
        } else if (flag == 1) {
            list_move(cur->prev, cur);
            flag = 0;
        }
    }
    return;
}
// https://leetcode.com/problems/swap-nodes-in-pairs/

`q_reverse`

list_move() 會先執行 list_del() 將當前指向的元素刪除，在執行 list_add() 將元素新增至佇列最前端。第 7 行使用 list_for_each_safe() 可以允許當前節點從佇列中移除，用 list_for_each() 會導致 infinite loop 。










void q_reverse(struct list_head *head) 
{
    if(!head || list_is_singular(head) || list_empty(head))
        return;
    struct list_head *cur , *safe=NULL;
        
    list_for_each_safe(cur, safe, head){
        list_move(cur, head);
    }   
}

`q_reverseK`

讓指標邊走邊數 k 個元素，到第 k 個元素進行 reverse 。
cur_prev_k 存放 top 為 1 的元素之記憶體位址，也就是記錄當前元素要進行 reverse時的前 k 個元素之記憶體位址。

宣告改成 *cur_prev_k = head->next 會出現無限迴圈，因為 cur_prev_k 會跟著指向的元素做移動，導致 cur_prev_k 永遠不會等於 tmp ，也就是離不開 while 迴圈。

void q_reverseK(struct list_head *head, int k)
{
    if(!head || list_is_singular(head) || list_empty(head))
        return;

    int top = 0;
    struct list_head *cur, **cur_prev_k = &(head->next),
    struct list_head *safe=NULL, *tmp=NULL;
    
    list_for_each_safe(cur, safe, head){
        top++;
        if(top%k==0){
            tmp = cur;
            while(*cur_prev_k != tmp){
                list_move(tmp->prev, cur);
                cur = cur->next;
            }
            cur_prev_k = &(cur->next);
        }
    } 
    // https://leetcode.com/problems/reverse-nodes-in-k-group/  
}

`q_sort`

參考你所不知道的 c 語言: linked list 和非連續記憶體、 Linked List Sort 中提到的 Merge Sort 以及 seasonwang0905 的程式碼實作。

避免張貼完整程式碼，列出關鍵程式碼並闡述你的觀察、推論，和考慮議題。
jserv

已修正
LiChiiiii

排序實作總共用到三個函式：

merge_two_list() ：將兩個佇列合併成一個已完成排序的佇列
mergesort()：將未排序的佇列進行不斷的分割，直到剩一個節點即開始執行merge_two_list()，直到遞迴結束。
q_sort()：先將尚未排序的佇列變成 singly-linked list ，這樣排序過程中就不用維持 doubly-linked list 。等到執行完 mergesort() 排序完畢後，再重新連結 prev 即可。

/* Merge two list into one queue */
struct list_head *merge_two_list(struct list_head *l1, struct list_head *l2)
{   
    struct list_head *temp = NULL;
    struct list_head **indirect = &temp; 
    for (struct list_head **node = NULL; l1 && l2; *node = (*node)->next) {
        element_t *e1 = list_entry(l1, element_t, list);
        element_t *e2 = list_entry(l2, element_t, list);
        if (strcmp(e1->value, e2->value) < 0)
            node = &l1;
        else
            node = &l2;
        *indirect = *node;
        indirect = &(*indirect)->next;
    }
    *indirect = (struct list_head *) ((u_int64_t) l1 | (u_int64_t) l2);
    return temp;
}

/* Divide the queue and sort every element */
struct list_head *mergesort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *fast = head, *slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = slow;
    slow->prev->next = NULL;
    struct list_head *l1 = mergesort(head);
    struct list_head *l2 = mergesort(fast);
    return merge_two_list(l1, l2);
}

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    head->prev->next = NULL;
    head->next = mergesort(head->next);
    struct list_head *current = head, *next = head->next;
    while (next) {
        next->prev = current;
        current = next;
        next = next->next;
    }
    current->next = head;
    head->prev = current;
}

`q_descend`

從 list 尾端向前比較大小，比從 list 前端向後比較大小來的簡單。前者只要反向比較下一個元素小於當前元素即可刪除，後者則是順向比較當前元素之前的所有元素是否小於當前元素。

int q_descend(struct list_head *head)
{
    if (!head || list_is_singular(head) || list_empty(head))
        return 0;

    struct list_head *cur = head->prev;

    while (cur->prev != head) {
        element_t *cur_el = list_entry(cur, element_t, list);
        element_t *cur_prev_el = list_entry(cur->prev, element_t, list);
        int cmp = strcmp(cur_el->value, cur_prev_el->value);
        if (cmp > 0) {
            list_del(cur->prev);
            q_release_element(cur_prev_el);
        } else {
            cur = cur->prev;
        }   
    }   

    return q_size(head);
}
// https://leetcode.com/problems/remove-nodes-from-linked-list/

`q_merge`

使用 queue.h 中定義的資料結構 queue_contex_t 來表示每一個queue。

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

透過 list_for_each_entry() 查看所有的佇列，並將佇列合併，最後將合併起來的queue做排序。

/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    else if(list_is_singular(head))
        return list_entry(head, queue_contex_t,chain)->size;
    
    queue_contex_t *que = list_entry(head->next, queue_contex_t,chain);
    queue_contex_t *cur_que = NULL;
    list_for_each_entry(cur_que, head, chain)
    {
        if(cur_que == que)
            continue;

        list_splice_init(cur_que->q, que->q);
        que->size = que->size + cur_que->size;
        cur_que->size = 0;
    }

    q_sort(que->q);
    return que->size;
    
    // https://leetcode.com/problems/merge-k-sorted-lists/
}

改進 `web` 命令

原始程式碼執行 web 命令可開啟網頁伺服器，一旦 web_fd > 0 表示成功開啟 web server 。

/* console.c */
static int web_fd;
static bool do_web(int argc, char *argv[])
{
    int port = 9999;
    if (argc == 2) {
        if (argv[1][0] >= '0' && argv[1][0] <= '9')
            port = atoi(argv[1]);
    }

    web_fd = web_open(port);
    if (web_fd > 0) {
        printf("listen on port %d, fd is %d\n", port, web_fd);
        use_linenoise = false;
    } else {
        perror("ERROR");
        exit(web_fd);
    }
    return true;
}

在 web.c 可以看到已經寫好在 web 接收訊息和傳送訊息的處理方式。

/* web.c */
char *web_recv(int fd, struct sockaddr_in *clientaddr)
{
    http_request_t req;
    parse_request(fd, &req);

    char *p = req.filename;
    /* Change '/' to ' ' */
    while (*p) {
        ++p;
        if (*p == '/')
            *p = ' ';
    }
    char *ret = malloc(strlen(req.filename) + 1);
    strncpy(ret, req.filename, strlen(req.filename) + 1);

    return ret;
}

void web_send(int out_fd, char *buf)
{
    writen(out_fd, buf, strlen(buf));
}

問題在於網頁伺服器開啟後，處理命令列的 linenoise 套件無法使用，因此嘗試改寫 linenoise.c 用 select() 同時處理 stdin 及 socket。
在line_edit 新增參數 web_fd ，當 web_fd != 0 就使用 select() 監聽。若從 web 輸入訊息（第33行），則將訊息複製到 buf 中並透過 linenoise 處理命令，同時也傳送 HTTP 回應的 header 訊息給客戶端，表示回應成功，並關閉 socket 。若從命令列輸入訊息（第43行），則保持原本做法處理。

























































/* linenoise.c */
static int line_edit(int stdin_fd,
                     int stdout_fd,
                     char *buf,
                     size_t buflen,
                     const char *prompt,
                     int web_fd)
{    
    ...
    while (1) {
        signed char c;
        int nread;
        char seq[5];

        if (web_fd) {
            fd_set set;
            FD_ZERO(&set);
            FD_SET(web_fd, &set);
            FD_SET(stdin_fd, &set);
            int rv = select(web_fd + 1, &set, NULL, NULL, NULL);
            struct sockaddr_in clientaddr;
            socklen_t clientlen = sizeof(clientaddr);
            int connfd;
            
            switch (rv) {
            case -1:
                perror("select"); /* an error occurred */
                continue;
            case 0:
                printf("timeout occurred\n"); /* a timeout occurred */
                continue;
            default:
                if (FD_ISSET(web_fd, &set)) {
                    FD_CLR(web_fd, &set);
                    connfd = accept(web_fd, (struct sockaddr *) &clientaddr, &clientlen);
                    
                    strncpy(buf, web_recv(connfd, &clientaddr), buflen);
                    char *header =
                        "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
                    web_send(web_connfd, header);
                    close(web_connfd);
                    return strlen(buf);
                } else if (FD_ISSET(stdin_fd, &set)) {
                    nread = read(l.ifd, &c, 1);
                    if (nread <= 0)
                        return l.len;
                }
                break;
            }
        } else {
            nread = read(l.ifd, &c, 1);
            if (nread <= 0)
                return l.len;
        }
    }
    ...
}

參考老師的整合網頁伺服器

實作 `shuffle` 命令

利用 Fisher–Yates shuffle 演算法來實作洗牌。

/* queue.c */
void value_swap(struct list_head *node1, struct list_head *node2)
{
    element_t *node1_ele = list_entry(node1, element_t, list);
    element_t *node2_ele = list_entry(node2, element_t, list);
    char *temp;

    temp = node1_ele->value;
    node1_ele->value = node2_ele->value;
    node2_ele->value = temp;
        
}

void q_shuffle(struct list_head *head)
{
    if (!head || list_is_singular(head) || list_empty(head))
        return;
    
    struct list_head *last = head->prev; 
    struct list_head *cur = head->next;
    
    int len = q_size(head);
    srand(time(NULL));
    while(len)
    {
        int i = rand() % len;

        while(i)
        {   
            cur = cur->next;
            i--;
        }   

    value_swap(cur,last);
        last = last->prev;
        cur = head->next;

        len--;
    }   
}

原本 swap 的寫法是透過 list_move() 來移動兩個節點位置，但執行 shuffle 時偶爾會失敗，後來才改成交換 value 的方法。

void node_swap(struct list_head *node1, struct list_head *node2)
{
    struct list_head *node1_prev = node1->prev;
    struct list_head *node2_prev = node2->prev;
    list_move(node2, node1_prev);
    list_move(node1, node2_prev);
    
}

除了實作程式碼，還需要在 qtest.c 新增命令和執行函式。

ADD_COMMAND(shuffle, "Implement Fisher–Yates shuffle","");

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

    if (!current) {
        report(3, "Warning: Try to operate null queue");
        return false;
    }    
    error_check();

    set_noallocate_mode(true);
    if (current && exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();
    set_noallocate_mode(false);

    return q_show(3);
}

Address Sanitizer

在 Makefile 中發現已定義一個變數稱 SANITIZER ，當 SANITIZER 變數設置為 1，即可啟用 address sanitizer。

# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
    # https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
    CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
    LDFLAGS += -fsanitize=address
endif

執行下列命令開啟 address sanitizer ，並重新編譯，沒有出現任何關於記憶體之錯誤。

make clean
make SANITIZER=1
make test

執行結果

$ make test
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---	trace-05-ops	6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
---	trace-06-ops	6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---	trace-07-string	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---	trace-10-robust	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

Valgrind

執行 make valgrind 沒有出現相關問題

執行結果

$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/lichi/Documents/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  CC	qtest.o
  CC	report.o
  CC	console.o
  CC	harness.o
  CC	queue.o
  CC	random.o
  CC	dudect/constant.o
  CC	dudect/fixture.o
  CC	dudect/ttest.o
  CC	shannon_entropy.o
  CC	linenoise.o
  CC	web.o
  LD	qtest
make[1]: Leaving directory '/home/lichi/Documents/lab0-c'
cp qtest /tmp/qtest.J1q9iz
chmod u+x /tmp/qtest.J1q9iz
sed -i "s/alarm/isnan/g" /tmp/qtest.J1q9iz
scripts/driver.py -p /tmp/qtest.J1q9iz --valgrind 
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---	trace-05-ops	6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
---	trace-06-ops	6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---	trace-07-string	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---	trace-10-robust	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

使用 Massif 查看記憶體的狀況

valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd

以下是 traces/trace-17-complexity.cmd 的記憶體使用狀況

在 trace-17 執行了 q_insert_head() 、 q_insert_tail() 、 q_remove_head() 以及 q_remove_tail() 四個函式，在圖中的最右邊可以看到，執行結束後記憶體並沒有釋放完全，此部分待確認。

Linux 核心原始程式碼的 `lib/list_sort.c`

比較 `lib/list_sort.c` 與自行實作的合併排序演算法差異

由於無法新增 queue.h 的定義，所以就把 lib_sort.c 的程式放進 qtest.c ，新增一個 option 來切換 sort 的實作，這樣很快就可以看看自己實作的效能跟 Linux 核心程式碼的差距。
在 qtest.c 當中把 do_sort() 函式的部分改為這樣：

 if (exception_setup(true)) {
        if (is_enable_linux_sort()) {
            q_sort_linux(l_meta.l);
        } else {
            q_sort(l_meta.l);
        }
    }

參考 komark06 對 list_sort.c 的修改方法，將程式放入 qtest.c 執行。
接著利用以下的 command 來比較排序時間：

option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverseK 100
time sort
option linux_qsort 1
new
ih dolphin 1000000
it gerbil 1000000
reverseK 100
time sort

執行 list_sort.c 會出現 Segmentation fault occurred. ，應是引入程式碼時有錯誤，待處理。

研讀論文〈Dude, is my code constant time?〉

論文中提出了工具 dudect ，可以用來檢測一段程式是否 constant time 執行。
測試方式主要分成三個步驟：

Measure execution time : 輸入固定資料和隨機資料來量測目標函式耗費的時間。每次隨機選擇一種類型資料並重複執行得到量測結果。
Apply post-processing：大於某個 threshold 的執行時間不列入統計檢定。
Apply statistical test：論文中提及兩個檢驗方式 t-test （採用 Welch's t-test ）和 Non-parametric tests

t-test
t-test 是一個常用來協助判斷比較兩組資料是否具有顯著差異的統計方法之一。在這裡我們試圖反證兩組資料時間分佈相等，也就是說當 t-test 拒絕假說（無法證明平均值的差異），表示執行時間為 constant time。

程式實作原理

在 lab0-c 中，當 simulation 開啟後會將 is_xx_xx_const() 作為目標函式進行時間複雜度測試 test_const() \(\rightarrow\) doit() ，並根據論文中的三個步驟實作：

measure() 和 differentiate()：計算目標函式執行時間
update_statistics()：處理取得的資料
report()：利用 Welch's t-test 驗證目標函式是否為 constant time

/* dudect/fixture.c */
static bool doit(int mode)
{
    ...

    bool ret = measure(before_ticks, after_ticks, input_data, mode);
    differentiate(exec_times, before_ticks, after_ticks);
    update_statistics(exec_times, classes);
    ret &= report();

    ...

    return ret;
}

在 measure() 函式發現計算過程中直接減掉要做刪除的次數（第10行），但測試流程應該要是紀錄所有資料再去做第二步驟的資料處理。

/* dudect/constant.h */
#define N_MEASURES 150
#define DROP_SIZE 20



























/* dudect/constant.c */
bool measure(int64_t *before_ticks,
             int64_t *after_ticks,
             uint8_t *input_data,
             int mode)
{
    ...
        
    switch (mode) {
    case DUT(insert_head):
        for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
            char *s = get_random_string();
            dut_new();
            dut_insert_head(
                get_random_string(),
                *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
            int before_size = q_size(l);
            before_ticks[i] = cpucycles();
            dut_insert_head(s, 1);
            after_ticks[i] = cpucycles();
            int after_size = q_size(l);
            dut_free();
            if (before_size != after_size - 1)
                return false;
        }
        break;
    ...

因此將該部分改成做完 N_MEASURES 次的紀錄後進行排序再刪除前後各 DROP_SIZE 個資料點，即可每次皆通過 trace-17-complexity 的測試。

參考 KHLee529 解決方法

Debug 紀錄

編譯時出現以下錯誤訊息

gcc: internal compiler error: Segmentation fault signal terminated program as
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-11/README.Bugs> for instructions.
make: *** [Makefile:54: qtest.o] Error 4

檢查gcc版本

檢查可用的記憶體空間

重新啟動主機

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.

2023q1 Homework1 (lab0)

開發環境

完成 queue.c

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_reverseK

q_sort

q_descend

q_merge

改進 web 命令

實作 shuffle 命令

Address Sanitizer

Valgrind

使用 Massif 查看記憶體的狀況

Linux 核心原始程式碼的 lib/list_sort.c

比較 lib/list_sort.c 與自行實作的合併排序演算法差異

研讀論文〈Dude, is my code constant time?〉

程式實作原理

Debug 紀錄

`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_reverseK`

`q_sort`

`q_descend`

`q_merge`

改進 `web` 命令

實作 `shuffle` 命令

Linux 核心原始程式碼的 `lib/list_sort.c`

比較 `lib/list_sort.c` 與自行實作的合併排序演算法差異