# 2019q1 Homework1 (lab0)
contributed by < [`leexun`](https://github.com/LeeXun) >
###### tags: 李洵, leexun

## 開發環境

$ uname -a
Linux c2b1d6fd7613 4.9.93-linuxkit-aufs #1 SMP Wed Jun 6 16:55:56 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              2
On-line CPU(s) list: 0,1
Thread(s) per core:  1
Core(s) per socket:  1
Socket(s):           2
Vendor ID:           GenuineIntel
CPU family:          6
Model:               61
Model name:          Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
Stepping:            4
CPU MHz:             2697.971
BogoMIPS:            5395.94
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            3072K
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht pbe syscall nx pdpe1gb lm constant_tsc rep_good nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq dtes64 ds_cpl ssse3 sdbg fma cx16 xtpr pcid sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand hypervisor lahf_lm abm 3dnowprefetch kaiser fsgsbase bmi1 avx2 bmi2 erms xsaveopt arat

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=18.04
DISTRIB_CODENAME=bionic
DISTRIB_DESCRIPTION="Ubuntu 18.04.1 LTS"

## C Programming Lab
### 程式實作與註解
#### queue_t

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* 使 q_insert_tail 複雜度可為 O(1) */
    int size;         /* 使 q_size 複雜度可為 O(1) */
} queue_t;

#### q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q == NULL) {
        // perror("q_new q malloc failed");
        /* 這邊原本預期會有錯誤訊息，但是因為我們的 malloc 失敗是用 script
        假裝的，所以 perror 會印出 Success 的字樣，所以我把後面的 perror
        都註解起來了，不然 qtest 跑起來會很亂。*/
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

#### q_free

void q_free(queue_t *q)
{
    if (q != NULL) {
        while (q->size != 0) {
            q_remove_head(q, NULL, 0);
        }
        free(q);
    }
}

#### q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }

    list_ele_t *newh;
    newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    }
    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh); /* 剛剛 malloc 的 newh 不用了*/
        return false;
    }
    strcpy(newh->value, s);

    if (q->size == 0) {
        q->tail = newh;
    }
    newh->next = q->head;
    q->head = newh;
    q->size += 1;
    return true;
}

#### q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL) {
        return false;
    }

    list_ele_t *newt;

    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        return false;
    }
    newt->value = malloc(strlen(s) + 1);
    if (newt->value == NULL) {
        free(newt); /* 剛剛 malloc 的 newt 不用了，不然不小心被用到會產生
                       segment fault */
        return false;
    }
    strcpy(newt->value, s);

    if (q->size == 0) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
    newt->next = NULL;
    q->tail = newt;
    q->size += 1;
    return true;
}

#### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->size == 0) {
        return false;
    }

    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_ele_t *tmp = q->head; /* 要用一個 tmp 記住原本 head 的 addr，等下 head
                                  換人後才能 free */
    q->head = q->head->next;
    q->size -= 1;
    free(tmp->value);
    free(tmp);
    return true;
}

int q_size(queue_t *q)
{
    /* 在 queue 的 struct 裡面增加 int size 紀錄大小，並在此使用*/
    if (q == NULL)
        return 0;
    return q->size;
}

#### q_reverse

void q_reverse(queue_t *q)
{
    if (q == NULL || q->size == 0 || q->size == 1)
        return;

    list_ele_t *cur = q->head->next;
    list_ele_t *next = cur->next;

    q->head->next = NULL;
    q->tail = q->head;

    while (next != NULL) {
        next = cur->next;
        cur->next = q->head;
        q->head = cur;
        cur = next;
    }
}

#### 實作思路

- 首先跟著作業的提示，將 struct, q_new, q_size 修改，加上 size, tail。
- 因為已經有測項了，所以打算用類似 TDD 的方式做開發。
- new 好了之後的下一步，就是實作 insert，insert 有 insert_head, insert_tail 兩種，兩種的實作非常像，不過要注意在最後安插的順序。
- 插入寫好後因為 01 有 remove_head，所以繼續實作 remove_head。
- 寫好了跑了測資，沒過還噴了 segment fault，之前沒有使用 gdb 的經驗，查了一下別人是如何用來找 SF 的錯誤後並實作，才發現原來兩個 insert 在 new 有 malloc 成功但是 new->value 沒有 malloc 成功的時候，應該要把 new free 掉才行。
- 過了 01, 02, 08, 09, 10 後拿到 33/100
- 03 有 reverse 我還沒做，所以先跳過。
- 看看 04 為何沒過，才發現我沒有修改 free 裡面的實作。這樣是不是代表 01, 02 沒有做 q_free 呢？<b>看了 trace 裡面的 01, 02 指令之後，發現真的沒有測試 free</b>。
- 用 q_remove_head 實作出 q_free 之後，剩下 test 03, 05, 06, 07 沒過。
- reverse 的部分，原本使用了 prev, next, tmp 三個指標變數來實作，但是後來發現這樣 q->head 並沒有被修改到，所以把 prev 的部分用 q->head 來移動。
- reverse 過了之後剩下 06, 07 有 segment fault，這邊直接找了 `trace-06-string.cmd` 的指令來手動配合 gdb 試試看，結果發現是 next = cur->next 這邊 cur 是 NULL ptr，原來 reverse 不只在 q = NULL, q->size == 0 的時候不用做事情，我還忘記了在 q->size == 1 的時候也是不用做事的。也因為少了這個條件， cur 才有可能在做完一輪後會是 NULL 而且還沒有被 while(next != NULL) 的條件擋下來。
- 剩下 07 沒有過，也一樣複製整個 `trace-07-string.cmd` 的指令貼上到 qtest 裡面用 gdb 做 backtrace。結果發現是 size 指令的時候會噴錯，這邊就不用 trace 了，因為原本我只有把 q_size 直接回傳 q->size，完全沒有做檢查過濾。
- 加上 q == NULL 的 return 0 之後得到 100/100

### 解釋自動評分系統運作的原理
- 最主要是有發現測項的指令都寫在 `./trace` 資料夾中，這樣在用 gdb 的時候可以直接複製貼上使用。
- TODO
### 提及 qtest 的行為和裡頭的技巧
- TODO
- 閱讀 [0xff07](https://hackmd.io/s/SJnc7dtSN), [Naetw](https://hackmd.io/s/BysQssYHN)
### 額外心得
- 在寫 reverse 這樣的操作時，可以動手把圖畫下來，會比較好理解和思考。
- 這邊在處理 malloc 回傳 NULL 的時候，很好奇 Linux 是如何去撰寫這樣的錯誤處理。經過搜尋後，發現可以用 perror 去配合印出錯誤訊息，還有一些有趣的 marco，例如 [FAIL_IF](https://github.com/torvalds/linux/blob/master/tools/testing/selftests/powerpc/include/utils.h#L63-L71)，使用 `__LINE__` 可以印出錯誤該行的行數。
- 關於測試時如何觸發 malloc 錯誤，想到以下兩種方式：
1. 故意 malloc 一個比 RAM 還要大的空間。
2. 去看一下測試 script 怎麼做的，TODO。
- 看到回傳值是 bool 覺得有點奇怪，C 印象中應該是用 _Bool，bool 應該是 C++ 的 type 才是。
:::danger
請參閱 C99 規格的 `<stdbool.h>`，詳閱並摘要相關內容
工程人員說話不要用「印象中」，不僅不專業，也是對自己所學的褻瀆，務必參照第一手材料
:notes: jserv
:::
:::danger
收到！感謝老師的指教
:notes: leexun
:::
- 修改 git commit 的編輯器
- `$ git config --global core.editor vim`
- 被 git hooks 把 format 擋下來並修改完之後，要記得重新 git add 一次才會生效。
- 瀏覽同學的筆記學到 `strdup`，[點這邊](https://hackmd.io/s/HJ0Wv9dYm)有一些問題可以參考
- 學到 [perror](http://man7.org/linux/man-pages/man3/perror.3.html), [strerror](http://man7.org/linux/man-pages/man3/strerror.3.html)
- 閱讀了 [0xff07](https://hackmd.io/s/SJnc7dtSN), [Naetw](https://hackmd.io/s/BysQssYHN) 的筆記後發現自己觀察的太淺了，會根據他們已經研究到了方向再做了解。
### TODO
- valgrind

$ valgrind ./qtest
$ valgrind --leak-check=full ./qtest