# 進階電腦系統理論與實作 lab0
[I01: lab0 宅色夫](https://hackmd.io/@sysprog/2020-lab0#I01-lab0)
[My github](https://github.com/a5932016)
# 作業要求
* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github)
* 詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。
* 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
* 不用理會 [Autolab](https://autolabproject.com/) 和檔案下載的描述，這兩者都是 CMU 專屬
* 除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
* 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
* 挑戰題
* 參照 [antirez/linenoise](https://github.com/antirez/linenoise)，強化 qtest 命令列功能，使其支援單行或多行編輯、歷史命令處理、命令自動補完 (例如輸入 h 之後按下 Tab 按鍵，自動接續補上 elp，成為完整的 help 命令)。除了整合程式碼外，應當說明 antirez/linenoise 的運作原理，注意到 [termios](https://man7.org/linux/man-pages/man3/termios.3.html) 的運用
* 思考如何預設開啟 AddressSanitizer，卻又能滿足效能測試所需 (可能需要兩種以上的 build target)
* 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request
# 環境
```
$ uname -a
Linux zihyan 5.7.0-kali1-amd64 #1 SMP Debian 5.7.6-1kali2 (2020-07-01) x86_64 GNU/Linux
$ gcc --version
gcc (Debian 10.2.0-9) 10.2.0
Copyright (C) 2020 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.
```
# 在 GitHub 上 fork lab0-c
照教學步驟完成即可
[我的lab0-c](https://github.com/a5932016/lab0-c)
# 開始撰寫queue.[ch]
## 如何測試
在目標資料夾後執行
方法1
```
make check
```
方法2
```
make test
```
方法3
```
make
./qtest
help
#依自行需求執行測試
```
結束後皆要執行`make clean`做清除
## q_size
### queue.h
`queue_t`結構新增`int size`
```
typedef struct {
list_ele_t *head; /* Linked list of elements */
int size; /* Size of queue */
} queue_t;
```
### queue.c
修改function`q_size`，確認參數是否為NULL，如果為TRUE則傳回`q->size`
```
int q_size(queue_t *q)
{
if (!q || !q->size)
return 0;
return q->size;
}
```
## q_new
### queue.h
`queue_t`結構新增`list_ele_t *tail;`
```
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size; /* Size of queue */
} queue_t;
```
### queue.c
`queue_t`因新增`size`和`tail`故需要做初始化
要確認是否成功分配記憶體，避免操作到空指標
```
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
## q_free
傳入參數`queue_t`
先確認參數是否為NULL
依參數`q`使用`while loop`依序對`head`和`value`執行`free`
最後結束不要忘記對`q`執行`free`
```
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
## q_insert_head
加入新值在`head`前
指派一個新的`list_ele_t`，確認是否有建立成功
指派一個`char`，長度為`sizeof(char) * (strlen(s) + 1)`，額外留一個空間存`\0`
`tmp`指派到`newh`並指派為`q->head`，若`!q->tail`則指派到`q->tail`
`q->size`加1
```
bool q_insert_head(queue_t *q, char *s)
{
if (!q || !s)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
int len = sizeof(char) * (strlen(s) + 1);
char *tmp = malloc(len);
if (!tmp) {
free(newh);
return false;
}
memcpy(tmp, s, len);
newh->value = tmp;
newh->next = q->head;
q->head = newh;
if (!q->tail) {
q->tail = q->head;
}
q->size += 1;
return true;
}
```
## q_insert_tail
作法大致上與`q_insert_head`一樣
```
bool q_insert_tail(queue_t *q, char *s)
{
if (!q || !s)
return false;
list_ele_t *newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
int len = sizeof(char) * (strlen(s) + 1);
char *tmp = malloc(len);
if (!tmp) {
free(newt);
return false;
}
memcpy(tmp, s, len);
newt->value = tmp;
newt->next = NULL;
if (!q->head) {
q->head = newt;
}
if (q->tail) {
q->tail->next = newt;
}
q->tail = newt;
q->size += 1;
return true;
}
```
## q_remove_head
確認q是否為空
暫存`q->head`
將`q->head`指派`q->head->next`
`q->size -= -1` 如果`size`為`0`，則將`q->tail`指派為`NULL`
如果`sp`不為空，則把欲`free`的值指派到`sp`
最後執行對`tmp`和`tmp->value`執行`free`
```
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *tmp = q->head;
q->head = q->head->next;
q->size -= 1;
if (!q->size) {
q->tail = NULL;
}
if (sp) {
size_t len =
bufsize > strlen(tmp->value) ? strlen(tmp->value) : bufsize - 1;
memset(sp, '\0', len + 1);
strncpy(sp, tmp->value, len);
}
free(tmp->value);
free(tmp);
return true;
}
```
## q_reverse
反轉鏈結串列
參考 [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
`while loop`完成後要記得`q->head->next = NULL`和指派新的`head` `tail`
```
void q_reverse(queue_t *q)
{
if (!q || q->size <= 1)
return;
list_ele_t *tmp;
list_ele_t *prev = NULL;
list_ele_t *curr = q->head;
while (curr) {
tmp = curr->next;
curr->next = prev;
prev = curr;
curr = tmp;
}
q->head->next = NULL;
tmp = q->head;
q->head = q->tail;
q->tail = tmp;
}
```
## q_sort
使用合併排序法
```
void mergeSort(list_ele_t **head)
{
if (!*head || !(*head)->next)
return;
list_ele_t *l1 = (*head)->next;
list_ele_t *l2 = *head;
while (l1 && l1->next) {
l2 = l2->next;
l1 = l1->next->next;
}
l1 = l2->next;
l2->next = NULL;
l2 = *head;
mergeSort(&l2);
mergeSort(&l1);
*head = NULL;
list_ele_t **tmp = head;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
*tmp = l1;
l1 = l1->next;
} else {
*tmp = l2;
l2 = l2->next;
}
tmp = &((*tmp)->next);
}
*tmp = l1 ? l1 : l2;
}
void q_sort(queue_t *q)
{
if (!q || !q->head || q->size <= 1)
return;
mergeSort(&q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
# Valgrind 實驗
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
## 透過 Massif 視覺化 simulation 過程中的記憶體使用量
## 設計對應的實驗
//TODO
# 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
//TODO
Sign in with Wallet
Connect another wallet