# 2020q3 Homework1 (lab0)
contribute by <`simpson0114`>
###### tags: `sysprog2020`
## Outline
[TOC]
## 環境
```shell
$ uname -a
Linux simpson-HP-Laptop-15-bs0xx 5.4.0-47-generic #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 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.
```
## 作業要求
==詳細閱讀 [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)== ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式。
## queue實作
### q_new:
如果`malloc`失敗，則回傳`NULL`。
```c=79
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
if (q == NULL)
return NULL;
q->head = NULL;
q->size = 0;
return q;
}
```
### q_free:
如果傳入的`queue`是`NULL queue`，則直接`return`不做任何操作。
如果不是空的，則從`head`往後推，慢慢把所有element都`free`掉。
```c=91
void q_free(queue_t *q)
{
/* TODO: How about freeing the list elements and the strings? */
if (!q)
return;
while (q->head != NULL) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
/* Free queue structure */
free(q);
}
```
### q_insert_head:
如果傳入的`queue`是`NULL queue`或者 insert 進去的 element 或他的 value `malloc`失敗，則回傳`false`。
接著再把傳入的 char 指標放進`newh`的`value`裡面，並把 `queue` 的 `size` 加一。
```c=113
bool q_insert_head(queue_t *q, char *s)
{
/* TODO: What should you do if the q is NULL? */
if (q == NULL)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
if (newh == NULL)
return false;
newh->value = malloc(strlen(s) + 1);
if (newh->value == NULL) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s));
newh->value[strlen(s)] = '\0';
newh->next = q->head;
q->head = newh;
if (q->head->next == NULL)
q->tail = newh;
q->size++;
return true;
}
```
### q_insert_tail:
因為要求時間複雜度$O$(1)，所以我另外加了一個`tail`在`queue_t`裡面。
```c=26
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
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`是`NULL queue`或者 insert 進去的 element 或他的 value `malloc`失敗之類的問題後(可參考`q_insert_head`)，直接在`q->tail`後插入新的 element。
```c=162
strncpy(newh->value, s, strlen(s));
newh->value[strlen(s)] = '\0';
newh->next = NULL;
if (q->head != NULL) {
q->tail->next = newh;
q->tail = newh;
} else {
q->head = newh;
q->tail = newh;
}
q->size++;
return 0;
}
```
### q_remove_head:
如果 queue 不為`NULL`且 queue 不是空的，則將第一個 element 的`value`放進`*sp`中，並且刪除 element。
```c=183
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* TODO: You need to fix up this code. */
/* TODO: Remove the above comment when you are about to implement. */
if (q == NULL || q->head == NULL)
return false;
list_ele_t *tmp;
tmp = q->head;
q->head = q->head->next;
if (sp != NULL) {
strncpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
### q_size:
因為要求時間複雜度$O$(1)，所以`queue_t`這個 structure 裡面多加入一個變數`size`。
```c=26
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
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;
```
有了`size`之後，在`q_size`function 內直接回傳`q->size`就好了。
```c=206
int q_size(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* Remember: It should operate in O(1) time */
/* TODO: Remove the above comment when you are about to implement. */
if (q == NULL)
return 0;
return q->size;
}
```
### q_reverse:
把所有 element 從 head 到 tail 的前一個按順序都接到`q->tail`的後面，直到`cur == q->tail`，最後再將`q->tail = q->head; q->head = cur;`。
```c=223
void q_reverse(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* TODO: Remove the above comment when you are about to implement. */
if (q != NULL && q->head != NULL) {
list_ele_t *cur, *tmp;
cur = q->head;
while (cur != q->tail) {
tmp = q->tail->next;
q->tail->next = cur;
cur = cur->next;
q->tail->next->next = tmp;
}
q->tail = q->head;
q->head = cur;
}
}
```
### q_sort:
由於要盡量減少 sort 的時間複雜度，所以選擇了 Merge Sort 來實作，這個方法的時間複雜度為$O$($nlogn$)。
除此之外，此題目要求要使用 [nature sort](https://github.com/sourcefrog/natsort)，因此必須先將 [nature sort](https://github.com/sourcefrog/natsort) 上所需的程式碼存入資料夾，在使用了相關 function 後，還要將Makefile做稍微的修改。
```c=6
NAT_DIR := natsort
```
```c=29
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
natsort/strnatcmp.o
```
```c=64
clean:
rm -f $(OBJS) $(deps) *~ qtest /tmp/qtest.*
rm -rf .$(DUT_DIR) .$(NAT_DIR)
rm -rf *.dSYM
(cd traces; rm -f *~)
```
主程式我產生了兩個 function 來實做 merge sort，分別是`list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)`以及`list_ele_t *mergeSortList(list_ele_t *head)`。
由於系統會阻擋記憶體的浪費(e.g.隨意 malloc)因此，我本來用`malloc`一個新的 element，最後再將其刪除的方法失敗，最好才改成先今版本。
```c=9
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
// merge with pseudo node
if (!l2)
return l1;
if (!l1)
return l2;
list_ele_t *head, *temp;
if (strnatcmp(l1->value, l2->value) < 0) {
head = l1;
temp = l1;
l1 = l1->next;
} else {
head = l2;
temp = l2;
l2 = l2->next;
}
while (l1 && l2) {
if (strnatcmp(l1->value, l2->value) < 0) {
temp->next = l1;
temp = temp->next;
l1 = l1->next;
} else {
temp->next = l2;
temp = temp->next;
l2 = l2->next;
}
}
if (l1)
temp->next = l1;
if (l2)
temp->next = l2;
return head;
}
```
```c=50
list_ele_t *mergeSortList(list_ele_t *head)
{
// merge sort
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// split list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
// sort each list
list_ele_t *l1 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
// merge sorted l1 and sorted l2
return merge(l1, l2);
}
```
之後只要在 `q_sort` function 中避免 q 為`NULL`或 `size` 為 1 或 0 就好了。
```c=246
void q_sort(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* TODO: Remove the above comment when you are about to implement. */
if (!q || q->head == NULL || q->size == 1)
return;
q->head = mergeSortList(q->head);
list_ele_t *tmp = q->head;
while (tmp->next != NULL)
tmp = tmp->next;
q->tail = tmp;
}
```
## 記憶體使用量實驗
程式碼完成後測試記憶體使用，首先先使用以下命令
```shell
$ valgrind --tool=missif <program>
```
可得到一個記憶體資料的純文字檔 `miss.out.<number>`，得到之後再以以下命令:
```shell
$ massif-visualizer massif.out.<program>
```
即可由 massif 分析為視覺化輸出。看到圖片中最後成功釋放所有記憶體。
為了測試記憶體的使用，我將程式碼`q_free()`中的某部份註解掉。
```c=91
void q_free(queue_t *q)
{
/* TODO: How about freeing the list elements and the strings? */
if (!q)
return;
while (q->head != NULL) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
// free(tmp);
}
/* Free queue structure */
free(q);
}
```
再用 `trace-12-malloc.cmd` 測試，結果為
可看到圖中最後有將近 2kB 的記憶體為被釋放掉。
Sign in with Wallet
Connect another wallet