# 2020q1 Homework1 (lab0)
contributed by < `jaxbau` >

## :penguin: 作業要求
* 截止日期： Mar 21, 2020 (含) 之前

- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [x] 詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
- [ ] 依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，
記得也該實作 `q_sort` 函式。
- [ ] 修改排序所用的比較函式，變更為 [natural sort](https://github.com/sourcefrog/natsort)，
在 "simulation" 也該做對應的修改，得以反映出 [natural sort](https://github.com/sourcefrog/natsort) 的使用。
- [ ]也要編輯「[作業區](https://hackmd.io/@sysprog/linux2020-homework1)」，增添開發紀錄和 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) 及程式實作的原理;

#### 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) :arrow_forward: 為避免「舉燭」，請比照 `qtest` 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)

#### 記錄
先把 git 切到 dev 分支再來對程式碼做測試

照老師說的使用 clang-format 後執行 make check 結果跳很多錯誤

  CC	report.o
In file included from report.c:1:
report.h:35:22: error: unknown type name ‘size_t’
   35 | void *malloc_or_fail(size_t bytes, char *fun_name);
      |                      ^~~~~~
report.h:6:1: note: ‘size_t’ is defined in header ‘<stddef.h>’; did you forget to ‘#include <stddef.h>’?
    5 | #include <stdbool.h>
  +++ |+#include <stddef.h>
    6 | 
report.h:38:22: error: unknown type name ‘size_t’
   38 | void *calloc_or_fail(size_t cnt, size_t bytes, char *fun_name);
      |                      ^~~~~~
report.h:38:22: note: ‘size_t’ is defined in header ‘<stddef.h>’; did you forget to ‘#include <stddef.h>’?
report.h:38:34: error: unknown type name ‘size_t’
   38 | void *calloc_or_fail(size_t cnt, size_t bytes, char *fun_name);
      |                                  ^~~~~~
report.h:38:34: note: ‘size_t’ is defined in header ‘<stddef.h>’; did you forget to ‘#include <stddef.h>’?
report.h:44:26: error: unknown type name ‘size_t’
   44 | void free_block(void *b, size_t len);
      |                          ^~~~~~
report.h:44:26: note: ‘size_t’ is defined in header ‘<stddef.h>’; did you forget to ‘#include <stddef.h>’?
report.h:47:26: error: unknown type name ‘size_t’
   47 | void free_array(void *b, size_t cnt, size_t bytes);
      |                          ^~~~~~
report.h:47:26: note: ‘size_t’ is defined in header ‘<stddef.h>’; did you forget to ‘#include <stddef.h>’?
report.h:47:38: error: unknown type name ‘size_t’
   47 | void free_array(void *b, size_t cnt, size_t bytes);
      |                                      ^~~~~~
report.h:47:38: note: ‘size_t’ is defined in header ‘<stddef.h>’; did you forget to ‘#include <stddef.h>’?
make: *** [Makefile:39: report.o] Error 1

去查看 clang-format 對我做了什麼好事

vim .clang-format

  1 BasedOnStyle: Chromium
  2 Language: Cpp
  3 MaxEmptyLinesToKeep: 3
  4 IndentCaseLabels: false
  5 AllowShortIfStatementsOnASingleLine: false
  6 AllowShortCaseLabelsOnASingleLine: false
  7 AllowShortLoopsOnASingleLine: false
  8 DerivePointerAlignment: false
  9 PointerAlignment: Right
 10 SpaceAfterCStyleCast: true
 11 TabWidth: 4
 12 UseTab: Never
 13 IndentWidth: 4
 14 BreakBeforeBraces: Linux
 15 AccessModifierOffset: -4

其實看不出來是哪條設定去更動 include 順序
直接對 include 順序調動做測試
發現 report.h 在 signal.h 後就不會報錯
先去 report.h 加上 include signal.h 後做測試

jax@jax:~/Documents/C/lab0-c$ clang-format -i *.[ch]
jax@jax:~/Documents/C/lab0-c$ make check
  CC	report.o
  LD	qtest
./qtest -v 3 -f traces/trace-eg.cmd
cmd> 
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
q = NULL
cmd> # Create empty queue
cmd> new
q = []
cmd> # Fill it with some values.  First at the head
cmd> ih dolphin
q = [Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
make: *** [Makefile:42: check] 取消 (core dumped)

至少維持在原樣又能用clang-format了
commit

:::spoiler
我不是故意不讀資料，但作業交期快到了
前面好長一段時間都在學 git markdown 跟 c 還是希望能交出一點作業 至少把lab0做完
:::

### 再來是牛刀小試
queue.h

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    int size;
    /* TODO: You will need to add more fields to this structure
     *        to efficiently implement q_size and q_insert_tail.
     */
    /* TODO: Remove the above comment when you are about to implement. */
} queue_t;

queue.c

int q_size(queue_t *q)
{
    return q->size;
}

cmd> new
cmd> new
q = []
cmd> size
cmd> size
ERROR: Computed queue size as 1431655765, but correct value is 0

又錯了…
原來在 qnew 還要加上 init 值
queue

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* TODO: What if malloc returned NULL? */
    q->head = NULL;
    q->size = 0;
    return q;
}

再make一次並做測試

cmd> new
cmd> new
q = []
cmd> size
cmd> size
Queue size = 0
q = []

commit

### ih q_insert_head 實做

./qtest -v 3 -f traces/trace-eg.cmd
cmd> 
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
q = NULL
cmd> # Create empty queue
cmd> new
q = []
cmd> # Fill it with some values.  First at the head
cmd> ih dolphin
q = [Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
make: *** [Makefile:42: check] 取消 (core dumped)

輸出可以看到 ih dolphin 會報錯，所以先把ih的部份寫好
修改 queue.c

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));
    newh->value =  s;
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    q->head = newh;
    return true;
}

輸出

  CC	queue.o
  LD	qtest
./qtest -v 3 -f traces/trace-eg.cmd
cmd> 
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
q = NULL
cmd> # Create empty queue
cmd> new
q = []
cmd> # Fill it with some values.  First at the head
cmd> ih dolphin
ERROR: Need to allocate and copy string for new list element
q = [dolphin]
cmd> ih bear
ERROR: Need to allocate and copy string for new list element
q = [bear ih]
...

可以看到讀得到字串但有告警說 Need to allocate and copy string for new list element

應該是因為 q_new q->head NULL

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* TODO: What if malloc returned NULL? */
    q->head = NULL;
    q->size = 0;
    return q;
}