2022q1 Homework1 (lab0)

contributed by < as200188 >

作業要求

• fork lab-c
• 依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
  • 詳閱 如何寫好 Git Commit Message
  • 詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」
  • 研讀 Linux 核心原始程式碼的 lib/list_sort.c 比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
• 在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
• 在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令。
  • 嘗試整合 tiny-web-server
• 編輯「作業區」
  • 增添開發紀錄和 GitHub 連結
  • 提及你如何逐步達到自動評分程式的要求
  • 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
  • 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
  • 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點
  • 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案
• 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處

測試環境

使用虛擬機器

$ gcc --version                             
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
架構：                           x86_64
CPU 作業模式：                   32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   46 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
每核心執行緒數：                 1
每通訊端核心數：                 4
Socket(s):                       1
NUMA 節點：                      1
供應商識別號：                   GenuineIntel
CPU 家族：                       6
型號：                           151
Model name:                      12th Gen Intel(R) Core(TM) i5-12600K
製程：                           2
CPU MHz：                        3686.406
BogoMIPS:                        7372.81
Hypervisor 供應商：              KVM
虛擬型態：                       全部
L1d 快取：                       192 KiB
L1i 快取：                       128 KiB
L2 快取：                        5 MiB
L3 快取：                        80 MiB
NUMA node0 CPU(s)：              0-3

功能要求

• q_new: create new "empty" queue.
• q_free: release memory of queue.
• q_insert_head: insert new node after head.
• q_insert_tail: insert new node after tail.
• q_remove_head: 在佇列開頭 (head) 移去 (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: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;

功能實作

queue_new:

Create a new, empty queue.

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

After allocating queue memory (element_t), use linux/list.h macro INIT_LIST_HEAD to initialize list_head member element.

queue_free:

Free all storage used by a queue.

1. Free up list elements:
   Use previous pionter and point to queue head. Move forward the queue head to next list element while free up the previous pointer.
2. Free up queue element:
   Free up the queue element when queue head pointing to same location as queue tail does (There is no element in between).

 void q_free(queue_t* q)
 {
    list_ele_t* prev = q->head;
    while (q->head != q->tail) {
       q->head =  q->head->next;
       free(prev);
       prev = q->head;
    }
    /* Free queue structure */
    free(q)
}

queue_insert_head

Attempt to insert a new element at the head of the queue (LIFO discipline).

1. Allocate memory for list_ele_t and char array
2. Let new node piont to queue head and move q head to new node
3. Increment queue size counter

/*
 * Attempt to insert element at head of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* TODO: What should you do if the q is NULL? */
    newh =  malloc(sizeof(list_ele_t));
    if (newh == NULL) {
       fprintf(stderr, "Failed to allocate memory for inserting head");
       return false;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = malloc(sizeof(char)* (strlen(s)+1));
    if (newh->value == NULL) {
       fprintf(stderr, "Failed to allocate memory of char array for inserting head");
       return false;
    }
    newh->next = q->head;
    q->head = newh;
    return true;
}

queue_insert_tail

Attempt to insert a new element at the tail of the queue (FIFO discipline).
1. Allocate memory for list element and char array.
2. Insert it to the end of list
3. Increment the queue size counter.

/*
 * Attempt to insert element at head of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* TODO: What should you do if the q is NULL? */
    newh =  malloc(sizeof(list_ele_t));
    if (newh == NULL) {
       fprintf(stderr, "Failed to allocate memory for inserting head");
       return false;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = malloc(sizeof(char)* (strlen(s)+1));
    if (newh->value == NULL) {
       fprintf(stderr, "Failed to allocate memory of char array for inserting head");
       return false;
    }
    newh->next = q->head;
    q->head = newh;
    return true;
}

queue_remove_head

Attempt to remove the element at the head of the queue.

1. Use strdup to allocate memory and copy the string to sp
2. move queue head to next node and free up previous node

/*
 * Attempt to remove element from head of queue.
 * Return true if successful.
 * Return false if queue is NULL or empty.
 * If sp is non-NULL and an element is removed, copy the removed string to *sp
 * (up to a maximum of bufsize-1 characters, plus a null terminator.)
 * The space used by the list element and the string should be freed.
 */
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL) {
      return false;
    }
    sp = strdup(q->head->value);
    list_ele_t* prev = q->head;
    q->head = q->head->next;
    free(prev);
    q->size--;
    return true;
}

queue_size:

Compute the number of elements in the queue.

1. Create queue size counter in queue.h

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    /* TODO: You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    return q->size;
}

queue_reverse:

Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.

queue_sort:

參考資訊

• 共筆格式參考：共筆示範