# 2020q1 Homework1 (lab0)
contributed by < `LuChungYing` >
:::danger
注意作業要求已清楚規範共筆寫作格式，請依循。從小處做起！
:notes: jserv
:::
說明
- [作業說明](https://hackmd.io/s/BJA8EgFB4)
- [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 實驗環境
```shell
$ uname -a
Linux lulu-GP62-6QE 5.3.0-40-generic #32~18.04.1-Ubuntu SMP Mon Feb 3 14:05:59 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
```
---
### 作業要求
在 `queue.[c/h]` 中完成以下實作
* `q_new`: 建立新的「空」佇列;
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* `q_sort`: 以遞增順序來排序鏈結串列的元素
### 實驗流程
1. 從 github fork 程式碼到自己的帳號
2. 使用 git clone 將檔案載到本地端
3. 開始修改程式碼
* 修改 *queue.h* 裡 structure queue_t，多加了 int size
```cpp
typedef struct {
list_ele_t *head;
/* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
* 修改 *queue.c* 裡 function q_size()
```cpp=
int q_size(queue_t *q)
{
return q->size;
}
```
做一次commit message: Change q_size return value to q->size
---
* 修改 ***queue.c*** function `q_new()`
檢查 `q` 是否為 NULL 是的話則直接回傳
否則做 queue 出初始，然後回傳 `queue_t` 的pointer
```cpp=
queue_t *q_new()
{
queue_t *q=malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
* 修改 ***queue.c*** 裡 funtion `q_free()`
* 檢查 `q` 是否為 NULL 是則直接回傳
* 否則以 `q->head` 當作紀錄點(紀錄free到哪裡)
* 再重頭free到最後
* 最後再 free `q`
```cpp=
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *tmp;
tmp = q->head;
free(tmp->value);
free(tmp);
q->head = q->head->next;
}
free(q);
}
```
* 修改 ***queue.h*** 裡 structure `queue_t`
加入 `*tail`
```cpp=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
做一次commit message: Change q_new() q_free() in .c, add tail in .h
---
* 修改 ***queue.c*** 裡 function `q_insert_head()`
* 先檢查q是否為NULL 是則直接回傳`false`
* 否則向 OS 請求兩塊記憶體 一塊為 element 的 pointer 一塊為 字串的空間
* 然後把 element 放在 `q->head`
* 如果 element 只有一個 表示一開始在放 所以要把 `tail` 指過去唯一的 element
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q)
return false;
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
newh->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
if (newh->value == NULL) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
newh->next = q->head;
q->head = newh;
q->size++;
if (q->size == 1)
q->tail = newh;
return true;
}
```
* 修改 ***queue.c*** 裡 function `q_insert_tail()`
* 與 `q_insert_head()` 差不多 但是指的方向要注意
* `next` 是往後指的 所以新的指標的 `next` 要指向原本的 `tail`
```cpp=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newt;
if (!q)
return false;
newt = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newt == NULL)
return false;
newt->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
if (newt->value == NULL) {
free(newt);
return false;
}
strncpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
q->tail->next = newt;
q->tail = newt;
q->size++;
if (q->size == 1)
q->head = newt;
return true;
}
```
* 修改 ***queue.c*** 裡 function `q_remove_head()`
* 先檢查 `q` 是否存在 還有element是否至少一個 否則回傳 `false`
* 檢查 sp 是否存在 是則 給它一塊記憶體空間 複製要刪除的字串給它 長度為 bufsize
* 需要一個 `tmp` 的 `list_ele_t` 指標 指向要刪除的 node
* 先把 `tmp` 裡的字串釋放 再釋放 `tmp`
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if(!q)
return false;
if(q->size == 0)
return false;
if(sp){
sp = char*(malloc(sizeof(q->head->value)));
strncpy(sp, q->head->value, bufsize);
}
list_ele_t *tmp = q->head;
q->head = q->head->next;
tmp->next = NULL;
free(tmp->value);
free(tmp);
q->size--;
if(q->size == 0)
q->tail = NULL;
return true;
}
```
做一次commit message: Modify q_insert_head q_insert_tail q_remove_head
---
* 修改 ***queue.c*** 裡 function `q_reverse()`
* 方式是重頭(head)開始，把每一個 element 接到 `tail` 上 以 `tail->next` 和 `head->next` 當作兩個 tmp 依序的接到 head 前面 直到換到 `tail`
```cpp=
void q_reverse(queue_t *q)
{
if (q == NULL)
return;
if (q->size <= 1)
return;
list_ele_t *tmp;
q->tail->next = q->head;
while (q->head->next != q->tail) {
tmp = q->head->next;
q->head->next = tmp->next;
tmp->next = q->tail->next;
q->tail->next = tmp;
}
q->tail = q->head;
q->head = q->head->next;
q->tail->next = NULL;
}
```
* 修改 ***queue.c*** 裡 function `q_sort()`
* 無論在平均最佳最差的情況下時間複雜度都是 O(nlogn) 的 sort 就只有 mergesort 了
* 在 quiz1 有看到 mergesort 的 C code 但是發現它切 element 的方式是一個一個切，花費的時間複雜度是 O(n) 跟原先的 O(logn) 不一樣
* 我實做一個時間複雜度為 O(logn) 切法的mergesort，重點在於設兩個指標(fast, slow)，一個指標以兩倍速的方式漸增到 tail ，一個則以一倍速的方式漸增，直到尾巴 slow指的剛好是第一個 list 最後一個位置， 然後在 fast = slow->next 就切分為二個 list了
* 然後以遞迴的方式切到剩一個 element
* merge 的部份比較簡單，以 `strcmp()` 就可以比較字串的大小，重點在於要宣告一塊記憶體空間供紀錄要回傳的指標
* 在測試的時候發現，一直跳出 `in merge()` 不可以 `malloc` ，不知道確切原因，所以我就先判斷第一個位置是L1 還是 L2，merge 完後回傳第一個位置
```cpp=
list_ele_t *merge(list_ele_t* l1, list_ele_t* l2)
{
if (l2 == NULL)
return l1;
if (l1 == NULL)
return l2;
list_ele_t *tmp = (list_ele_t*) malloc(sizeof(list_ele_t));
list_ele_t *re = tmp;
while (l1 != NULL && l2 != NULL){
if (strcmp(l1->value, l2->value) < 0){
tmp->next = l1;
l1 = l1->next;
}
else{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
if (l1)
tmp->next = l1;
if (l2)
tmp->next = l2;
list_ele_t *head = re->next;
free(re);
return head;
}
```
```cpp=
list_ele_t *mergesort(list_ele_t *h)
{
if (h == NULL || h->next == NULL)
return h;
list_ele_t *fast = h->next;
list_ele_t *slow = h;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = mergesort(h);
list_ele_t *l2 = mergesort(fast);
return merge(l1, l2);
}
void q_sort(queue_t *q){
if (!q)
return;
if (q->size <= 1)
return;
q->head = mergesort(q->head); }
```
做 make test 的時候 發現 insert_tail
要求 O(1) 未過， 查了一下其他人的作法，
在[有品味的code 14:20](https://www.ted.com/talks/linus_torvalds_the_mind_behind_linux#t-862314)有提到 需要使用 double pointer to the address of 最後一個 element 指的 `next`才可以在 insert_tail 不需要判斷是否 queue 為空 code 修改為：
```cpp=
newt->next = NULL;
*(q->indirect_tail) = newt;
q->indirect_tail = &newt->next;
q->size++;
if (q->size == 1)
q->head = newt;
return true;
```
透過 make test 除了 truncated strings
目前尚未得知怎麼做 其他都有達成
```
CC queue.o
LD qtest
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
...
--- trace-17-complexity 5/5
--- TOTAL 94/100
```
## Valgrind
```
valgrind --tool=memcheck --show-possibly-lost=no ./qtest
```
利用動態偵測記憶體遺漏，發現除非我輸入尚未定義的指令會出現：
```
==4422== 32 bytes in 1 blocks are still reachable in loss record 1 of 25
==4422== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4422== by 0x10B436: malloc_or_fail (report.c:189)
==4422== by 0x10BF48: add_cmd (console.c:123)
==4422== by 0x10C029: init_cmd (console.c:93)
==4422== by 0x10AC52: main (qtest.c:757)
```
的錯誤，裡面出現了 still reachale ，說明是library 函式的記憶體位置尚未釋放所導致
在 harness.c `(size_t) b` 的用意是，如果不轉的話，做指標位置的數字加減，會是加減這個指標指的位置大小的加減
```cpp
static size_t *find_footer(block_ele_t *b)
{
// cppcheck-suppress nullPointerRedundantCheck
size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
return p;
}
```
Sign in with Wallet
Connect another wallet