# 2018q3 Homework2 (lab0)
contributed by < [wingard](https://github.com/wingard) >
###### tags: `HW2`
## 作業進度表
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github)
- [x] 詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* (英文閱讀正是我們想強化的議題)，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改。
* 在提交程式前，務必詳閱 [如何寫好 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](http://www.autolabproject.com/) 和檔案下載的描述，這兩者都是 CMU 專屬
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/s/rJwiDHGKQ)」，增添開發紀錄和 GitHub 連結，提及如何逐步達到要求，以及如何改善效能
* 解釋自動評分系統運作的原理
* 提及 `qtest` 的行為和裡頭的技巧
## 實驗環境
```
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0
Copyright (C) 2017 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.
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.1 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.1 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/
legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic
```
## [如何寫好 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/) -- 重點摘要
* 好的 commit messages 的 7 個規則: [Source](https://hackmd.io/s/SJvojkBtG#Git-commit-messages)
1. Separate subject from body with a blank line
標題與內文以一個空白行分隔，這樣可在使用 `$ git log` 閱讀時較易區分標題
2. Limit the subject line to 50 characters
標題字數最多 50。因為標題字數超過 50 在 github 上會被隱藏到 `…` 裡面，需要額外點開才能完整知道這個 commit 在做什麼。並且超過 50 字可能就不是一個精簡的標題
3. Capitalize the subject line
標題首字大寫
4. Do not end the subject line with a period
標題結尾不要句點
5. Use the imperative mood in the subject line
標題用命令口吻
6. Wrap the body at 72 characters
內文一行字數不超過 72
這樣在 `$ git log` 裡面看會比較清楚，排版比較好看
7. Use the body to explain what and why vs. how
內文說明是什麼、為什麼而不是如何做。因為看 commit 的人是想知道你為什麼要做這件事，而不是要知道你如何做這件事的 (動機比細節更重要)
### 標題
* 一個正確的 Git commit 標題應該要能夠讓完成下面的句子，使之完整：
* If applied, this commit will *你的標題*
舉例而言：
If applied, this commit will **refactor subsystem X for readability**
If applied, this commit will **update getting started documentation**
If applied, this commit will **remove deprecated methods**
If applied, this commit will **release version 1.0.0**
If applied, this commit will **merge pull request #123 from user/branch**
* 如果你很難總結出標題，這代表你可能在一個 commit 裏面做了太多的改變。請儘量讓 commits 原子化 (atomic commits)。
### 內文
* 在大多數的情況下，你可以省略掉描述這些變更的細節。程式碼本身就已經能自我說明了 (如果程式碼太複雜，必須要有說明的話，這時候就是程式碼本身的註解啦)。你只需要專注在解釋做出這樣改變的原因 ─ 事情在改變前為什麼可行 (以及他的錯誤)，他們目前運作的狀況，以及為什麼你決定要以這個方法解決問題。
---
## [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
### Overview
* queue_t Structure
* singly-linked list
* Note: 在只有一個 element 時，head 與 tail 都會指向此 element
* NULL queue: A NULL queue is one for which the pointer has value NULL.
* `q==NULL`
* Empty queue: An empty queue is one pointing to a valid structure, but the head field has value NULL.
* `q->head = NULL`
### queue_t struct 內容修改
* 增加 tail pointer 欄位
* 增加 number of elements 欄位
```C=1
/* Queue structure */
typedef struct {
list_ele_t *head; /* pointer to head */
list_ele_t *tail; /* pointer to tail */
unsigned int elementNum; /* Number of elements */
} queue_t;
```
## Programming Task
### q_new: Create a new, empty queue.
* 註解有提到 Return NULL if could not allocate space ，故 malloc 失敗時可以直接 return NULL pointer，malloc 成功時對 q 作初始化
```C=1
/*
Create empty queue.
Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (q != NULL)
{
q->head = q->tail = NULL;
q->elementNum = 0;
}
return q;
}
```
* 參考 [Stackoverflow 的討論](https://stackoverflow.com/a/605858/500983) ，由於 malloc 回傳的 pointer 由於已經是 generic pointer `void *`，故不需要再做轉型
```C
queue_t *q = malloc(sizeof(queue_t)); //OK
queue_t *q = (queue_t *) malloc(sizeof(queue_t)); // Cast is not required
```
### q_free: Free all storage used by a queue.
* 先確認 q 不是 null pointer
* 根據 malloc manpage ，傳 NULL pointer 進去 free() 不會有問題，但為了減少內層的處理成本，在外層先作判斷
> The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc(), or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior occurs. **If ptr is NULL, no operation is performed.**
* 使用 *n 暫存當前 element 指向的下一個 element ，分別 free element 指向的 string 以及 element 自身後，將 *n 回存回 *pos
* 概念類似 [linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf) 課程提到的 [list_for_each_safe](https://github.com/torvalds/linux/blob/master/include/linux/list.h#L472)
```C=1
/* Free all storage used by queue */
void q_free(queue_t *q)
{
if (!q)
{
return;
}
list_ele_t *pos = q->head;
while(pos)
{
list_ele_t *n = pos->next;
free(pos->value); /* free string */
free(pos); /* free list element */
pos = n;
}
/* Free queue structure */
q->elementNum = 0;
free(q);
}
```
### q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
* 基本操作
* 將新增的 `element->next` 指向當前的 head element
* 將 `q->head` 指向此 element
* 若 insert 時 queue 為 NULL queue ，則 `queue->tail` 必為 `NULL`
* 將 `queue->tail` 也指向此 element
* 最後將 `queue->element` 數目加 1
```C=1
/*
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)
{
if (!q)
{
return false;
}
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
{
return false;
}
/* Don't forget to allocate space for the string and copy it */
newh->value = malloc(strlen(s)+1);
if (newh->value == NULL)
{
free(newh);
return false;
}
memcpy(newh->value, s, strlen(s)+1);
newh->next = q->head;
q->head = newh;
if (!q->tail)
{
q->tail = newh;
}
q->elementNum++;
return true;
}
```
### q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
* 基本操作
* 原先 `q->tail` element的 next 指向此新增的 element
* 將 `q->tail` 指向此 element
* 新增的 `element->next = NULL`
* 若 insert 時 queue 為 NULL queue ，則 `queue->head` 必為 `NULL`
* 將 `queue->head` 也指向此 element
* 最後將 `queue->element` 數目加 1
```C=1
/*
Attempt to insert element at tail 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_tail(queue_t *q, char *s)
{
list_ele_t *newt;
if (!q)
{
return false;
}
newt = malloc(sizeof(list_ele_t));
if (!newt)
{
return false;
}
/* Don't forget to allocate space for the string and copy it */
newt->value = malloc(strlen(s)+1);
if (!newt->value)
{
free(newt);
return false;
}
memcpy(newt->value, s, strlen(s)+1);
if (q->tail)
{
q->tail->next = newt;
}
q->tail = newt;
newt->next = NULL;
if (!q->head)
{
q->head = newt;
}
q->elementNum++;
return true;
}
```
:::info
一開始作 q_insert_head() 與 q_insert_tail() 內的 allocate space for the string 時，是透過 strdup() ，但跑自動測試時會失敗，百思不得其解...
後來閱讀了 [pjchiou](https://hackmd.io/s/HkTJUodY7#%E7%82%BA%E4%BB%80%E9%BA%BC%E4%B8%8D%E8%83%BD%E7%94%A8-strdup) 的共筆，才知道是 harness.c 的實作，對於 malloc() 與 free() 會導向自行定義的 test_malloc() 與 test_free()，如果呼叫 strdup() 會變成 malloc() 對應 test_free()，變成對不上而導致自動測試失敗
```C=1
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
```
:::
### q_size: Compute the number of elements in the queue.
* 練習 ternary operator
```C=1
/*
Return number of elements in queue.
Return 0 if q is NULL or empty
*/
int q_size(queue_t *q)
{
return q? q->elementNum; 0;
}
```
### q_remove_head: Attempt to remove the element at the head of the queue.
* 指標 ptr 指向要移除的 head element
* 如果要移除的 `element->next` 為 `NULL` ，表示此時 queue 中只有一個 element ，移除 element 後需要同時將 `q->tail` 設為 `NULL`
```C=1
/*
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 || !q->head) // NULL queue or empty queue
{
return false;
}
list_ele_t *ptr = q->head;
q->head = q->head->next;
if (!q->head) //case for only one element in the queue
{
q->tail = NULL;
}
if (sp)
{
memcpy(sp, ptr->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
free(ptr->value);
free(ptr);
q->elementNum--;
return true;
}
```
### q_reverse: Reorder the list so that the queue elements are reversed in order.
* 最難的一個實作，看了 `pjchiou` 的共筆才理解
* 使用三個指標去暫存 前一個/目前/下一個 element
* 三個指標同時往前移動一步後，將當前 element->next 指向前一個 element
```C=1
/*
Reverse elements in queue
No effect if q is NULL or empty
This function should not allocate or free any list elements
(e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
It should rearrange the existing ones.
*/
void q_reverse(queue_t *q)
{
if (!q || !q->head) { // NULL or empty
return;
}
list_ele_t *head = q->head;
list_ele_t *tail = q->tail;
list_ele_t *pos = q->head;
list_ele_t *prev;
list_ele_t *n = pos->next;
while (n) {
prev = pos;
pos = n;
n = n->next;
pos->next = prev;
}
q->head = tail;
q->tail = head;
q->tail->next = NULL;
}
```
---
## 程式碼格式檢查(clang-format)
* git add 時如果 source code 格式不符合規定的話，會跳出指示要求透過 `clang-format -i <source code>` 來修改格式
* 參考了 [Kernel.org 上的 clang-format 簡介](https://www.kernel.org/doc/html/v4.17/process/clang-format.html)，透過 clang-format 可以將程式碼整理成統一格式，確保大家同步開發以及 code review 時，能有相同的 coding style
---
## 自動評分系統
* 從 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 可得知，`$make test` 與 `scripts/driver.py` 有相同效果，可以從 Makefile 中得到證實:
```
test: qtest scripts/driver.py
scripts/driver.py
```
* 輸入`-h` 可以看使用說明
* -h: 印出
* -v: 印出訊息的資料量大小（ 類似debug message level )
*
```
$ ./scripts/driver.py -h
Usage: ./scripts/driver.py [-h] [-p PROG] [-t TID] [-v VLEVEL]
-h Print this message
-p PROG Program to test
-t TID Trace ID to test
-v VLEVEL Set verbosity level (0-3)
```
* help message 少提到一個 `-A` ，
---
## qtest 之行為與技巧
* 設計一個 switch 來接受 command arguments
```C=1
while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
switch (c) {
case 'h':
usage(argv[0]);
break;
case 'f':
strncpy(buf, optarg, BUFSIZE);
buf[BUFSIZE - 1] = '\0';
infile_name = buf;
break;
case 'v':
level = atoi(optarg);
break;
case 'l':
strncpy(lbuf, optarg, BUFSIZE);
buf[BUFSIZE - 1] = '\0';
logfile_name = lbuf;
break;
default:
printf("Unknown option '%c'\n", c);
usage(argv[0]);
break;
}
}
```
* queue_init()
*
* init_cmd();
* console_init();
* set_verblevel(level);
Sign in with Wallet
Connect another wallet