# 2019q3 Homework2 (lab0)
contributed by < `uccuser159` >
## 開發環境
作業系統：Ubuntu 18.04.2 LTS
---
## Overview
* 在 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 中要使用 Linked list 來實作 Queue
在`queue.h` 有宣告兩個結構：
```cpp
/* Linked list element */
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
} queue_t;
```
`value` 會指向字串的一個指標
`next` 會指向下一個 linked-list
`head` 為 queue 中的第一個 linked-list
定義 ==NULL queue== 和 ==empty queue== ：
NULL queue 表示沒有 queue
empty queue 表示的是一個空的 queue
在`queue.c`中要執行下列這些 task：
- **q_new**：製造出一個新的 queue (empty queue)
- **q_free**：將 queue 所佔的記憶體給釋放掉
- **q_insert_head** : 在 queue 的 head 插入元素( LIFO )
- **q_insert_tail** : 在 queue 的 tail 插入元素( FIFO )
- **q_remove_head** : 從 queue 的 head 移除元素
- **q_size** : 回傳目前 queue 的大小
- **q_reverse** : 把 queue 做反轉
---
## 實作
* 為了確認 `q_insert_tail` 和 `q_size` 的時間複雜度為 $O(1)$ ，所以在`queue.h`中加入指向 queue 尾端的 pointer 以及儲存 size 大小。
```cpp
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
* **q_new**
```cpp
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (q == NULL)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
```
* **q_free**
```cpp
void q_free(queue_t *q)
{
/*No effect if q is NULL*/
if (q == NULL)
return;
/* How about freeing the list elements and the strings? */
list_ele_t *delete;
while (q->head) {
delete = q->head;
q->head = q->head->next;
free(delete->value);
free(delete);
// q->head = q->head->next;
}
/* Free queue structure */
free(q);
}
```
* **q_insert_head**
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/* What should you do if the q is NULL? */
if (q == NULL)
return false;
newh = malloc(sizeof(list_ele_t));
/* Don't forget to allocate space for the string and copy it */
char *add = malloc((strlen(s) + 1) * sizeof(char));
/* What if either call to malloc returns NULL? */
if (newh == NULL || add == NULL) {
free(newh);
free(add);
return false;
}
strcpy(add, s);
newh->value = add;
newh->next = q->head;
q->size = q->size + 1;
if (q->head == NULL) // first insert
q->tail = newh;
q->head = newh;
return true;
}
```
* **q_insert_tail**
```cpp
/* You need to write the complete code for this function */
/* Reme mber: It should operate in O(1) time */
if (q == NULL)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
char *add = malloc((strlen(s) + 1) * sizeof(char));
if (newh == NULL || add == NULL) {
free(newh);
free(add);
return false;
}
strcpy(add, s);
newh->value = add;
newh->next = NULL;
q->size = q->size + 1;
if (q->tail == NULL) { // first insert
q->head = newh;
q->tail = newh;
} else {
q->tail->next = newh;
q->tail = newh;
}
return true;
```
* **q_remove_head**
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if (q == NULL || q->size == 0)
return false;
if (sp) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
// strcat(sp,'\0');
}
list_ele_t *replace;
replace = q->head;
q->head = q->head->next;
free(replace->value);
free(replace);
q->size = q->size - 1;
return true;
}
```
* **q_size**
```c=
int q_size(queue_t *q)
{
/* You need to write the code for this function */
/* Remember: It should operate in O(1) time */
if (q == NULL)
return 0;
return q->size;
}
```
* **q_reverse**
```c=
void q_reverse(queue_t *q)
{
if (q == NULL || q->size == 0 || q->size == 1)
return;
list_ele_t *cur = q->head->next;
q->head->next = NULL;
list_ele_t *temp;
q->tail = q->head;
while (cur != NULL) {
temp = cur->next;
cur->next = q->head;
q->head = cur;
cur = temp;
}
```
---
## 自動評分運作
* 由於是執行`make test`指令來跑評分系統，所以進入 Makefile 檔中的`test`部分：
```
test: qtest scripts/driver.py
scripts/driver.py
```
可以得知進行自動評分，需要`scripts/driver.py`來執行`qtest`。
* 往`scripts/driver.py`看：
```python=
traceDirectory = "./traces"
qtest = "./qtest"
command = qtest
verbLevel = 0
autograde = False
useValgrind = False
```
```python=
def run(name, args):
prog = ""
tid = 0
vlevel = 1
levelFixed = False
autograde = False
useValgrind = False
optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])
for (opt, val) in optlist:
if opt == '-h':
usage(name)
elif opt == '-p':
prog = val
elif opt == '-t':
tid = int(val)
elif opt == '-v':
vlevel = int(val)
levelFixed = True
elif opt == '-A':
autograde = True
elif opt == '--valgrind':
useValgrind = True
else:
print("Unrecognized option '%s'" % opt)
usage(name)
if not levelFixed and autograde:
vlevel = 0
t = Tracer(qtest = prog, verbLevel = vlevel, autograde = autograde, useValgrind = useValgrind)
t.run(tid)
```
在`optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])`中：
- `getopt.getopt` 回傳的是兩個陣列： optlist 和 args ： optlist是分析出的格式，而 args 為不屬於格式訊息的剩下參數。
- `'hp:t:v:A'` 此處為短選項。**沒有" : "的短選項**就像一個開關，若有在 optlist 中有回傳此格式即觸發；而**有" : "的短選項**表示後面帶一個參數 arg。
- `['valgrind']` 此處為長選項。**沒有" = "的長選項**就像一個開關，若有在 optlist 中有回傳此格式即觸發；而**有" = "的長選項**表示後面帶一個參數 arg。
在`if`條件式中有各項功能。
```python
if opt == '-h':
usage(name)
elif opt == '-p':
prog = val
elif opt == '-t':
tid = int(val)
elif opt == '-v':
vlevel = int(val)
levelFixed = True
elif opt == '-A':
autograde = True
elif opt == '--valgrind':
useValgrind = True
else:
print("Unrecognized option '%s'" % opt)
usage(name)
```
在函式`usage(name)`中有個短選項的各項功能，而`['valgrind']`這個長選項是在決定`useValgrind`功能要不要開啟：
```python
def usage(name):
print("Usage: %s [-h] [-p PROG] [-t TID] [-v VLEVEL] [--valgrind]" % name)
print(" -h Print this message")
print(" -p PROG Program to test")
print(" -t TID Trace ID to test")
print(" -v VLEVEL Set verbosity level (0-3)")
sys.exit(0)
```
最後在呼叫`Tracer`這個 class，來做自動評分：
```python
t = Tracer(qtest = prog, verbLevel = vlevel, autograde = autograde, useValgrind = useValgrind)
t.run(tid)
```
* Reference
-[sys.argv和getopt.getopt()的用法](https://www.cnblogs.com/zz22--/p/9336569.html)
-[Makefile語法和示範](https://hackmd.io/@sysprog/SySTMXPvl?type=view)
---
## qtest 的 signal handler
* [C99規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
* 7.14中提到 signal 是 conditions that may be reported during program execution.
> 7.14.1 Synopsis
> ```cpp
> #include <signal.h>
> void (*signal(int sig, void (*func)(int)))(int);
> ```
> 7.14.2 Description
The **signal** function chooses one of three ways in which receipt of the signal number **sig** is to be subsequently handled. If the value of func is **SIG_DFL**, default handling for that signal will occur. If the value of func is **SIG_IGN**, the signal will be ignored. Otherwise, **func** shall point to a function to be called when that signal occurs. ==An invocation of such a function because of a signal, or (recursively) of any further functions called by that invocation (other than functions in the standard library), is called a signal handler.==
```cpp
/* Signal handlers */
void sigsegvhandler(int sig)
{
trigger_exception(
"Segmentation fault occurred. You dereferenced a NULL or invalid "
"pointer");
}
void sigalrmhandler(int sig)
{
trigger_exception(
"Time limit exceeded. Either you are in an infinite loop, or your "
"code is too inefficient");
}
static void queue_init()
{
fail_count = 0;
q = NULL;
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
}
```
* **SIGALRM** : Time limit exceeded
在`harness.h`中有`exception_setup` . `exception_cancel` . `trigger_exception`三個函式：
```c
bool exception_setup(bool limit_time)
{
if (sigsetjmp(env, 1)) {
/* Got here from longjmp */
jmp_ready = false;
if (time_limited) {
alarm(0);
time_limited = false;
}
if (error_message) {
report_event(MSG_ERROR, error_message);
}
error_message = "";
return false;
} else {
/* Got here from initial call */
jmp_ready = true;
if (limit_time) {
alarm(time_limit);
time_limited = true;
}
return true;
}
}
void exception_cancel()
{
if (time_limited) {
alarm(0);
time_limited = false;
}
jmp_ready = false;
error_message = "";
}
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
* [sigsetjmp(sigjmp_buf env, int savemask)](http://www.qnx.com/developers/docs/qnxcar2/index.jsp?topic=%2Fcom.qnx.doc.neutrino.lib_ref%2Ftopic%2Fs%2Fsigsetjmp.html) 會保存目前 stack ，然後將目前的地址記錄起來，而在其他函數用 [siglongjmp()](http://www.qnx.com/developers/docs/qnxcar2/index.jsp?topic=%2Fcom.qnx.doc.neutrino.lib_ref%2Ftopic%2Fs%2Fsigsetjmp.html) 時便會直接跳到所記錄的位址，還原 stack ，再繼續執行其他函式。
env : A buffer where the function can save the calling environment.
savemask : Nonzero if you want to save the process's current signal mask, otherwise 0.
* [alarm(unsigned int seconds)](http://man7.org/linux/man-pages/man2/alarm.2.html) 當呼叫了alarm(n)後，等待n秒後，就會觸發一次的SIGALRM的signal，如果 alarm 的參數 seconds 為0，則之前設置的 Timer 會被取消，並將剩下的時間返回。
所以`bool exception_setup(bool limit_time)` 是用來判別程序執行時是否超過指定時間( time_limit = 1)。
- [ ]**若超過時間**：
`jmp_ready == true` → 呼叫`trigger_exception`儲存錯誤訊息( error_message )且將 error_occurred 設成 true → 由 `siglongjmp` 返回 `exception_setup` 進入 if 迴圈 重新計時且顯示錯誤訊息，最後回傳false。
- [ ]**若沒有超過時間**：
`time_limited == true`→ 呼叫`exception_cancel`重新計時且將`jmp_ready`設回 false ， error_message 也設為空白字元使其不顯示
Sign in with Wallet
Connect another wallet