# 2020q3 Homework1 (lab0)
contributed by < `Rsysz` >
###### tags: `sysprog`
## Outline
[TOC]
## 環境
```shell=
$ uname -a
Linux itlab-right 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 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.
```
## 作業要求
* `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`: 以==遞增順序==來排序鏈結串列的元素
## 實作流程
### queue.h
根據作業提示
> Return number of elements in queue.
Return 0 if q is NULL or empty
Remember: It should operate in O(1)time
> You will need to add more fields to this structure to efficiently implement `q_size` and `q_insert_tail`
新增 **int size** 與 **list_ele_t * tail** 到 `struct queue_t`:
```cpp=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
### queue.c
* **q_new**
* 初始化`queue_t`前先檢測是否成功分配記憶體空間，避免==Segmentation fault==
```cpp=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* DONE: What if malloc returned NULL? */
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
* **q_free**
* 新增**list_ele_t * tmp**暫存`q->head`指標，遍歷`queue_t`將內部所有記憶體空間釋放
```cpp=
void q_free(queue_t *q)
{
/* DONE: How about freeing the list elements and the strings? */
/* Free queue structure */
if (!q)
return;
while (q->head) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
* **q_insert_head**
* 新增節點`newh`後先行判定有無記憶體空間
* 利用`newh->value = malloc(sizeof(char) * (strlen(s) + 1))`於**list_ele_t * newh**結構內取得記憶體空間後判定有無取得==結構內==記憶體空間
* 使用`strncpy(newh->value, s, strlen(s) + 1)`複製==strlen(s) + 1==長度的字串(含'\0')至`newh->value`的記憶體空間中
1. 將`newh->next`指向`q->head`，後取代原先的`q->head`
2. 當新增的元素為`queue_t`中第一個元素時`q->tail`指向`newh`
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
/* DONE: What should you do if the q is NULL? */
if (!newh)
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1)); /*add 1 for '\0'*/
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s) + 1);
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
newh->next = q->head;
q->head = newh;
if (!q->tail)
q->tail = q->head;
q->size++;
return true;
}
```
* **q_insert_tail**
* 新增節點`newt`後先行判定有無記憶體空間
* 利用`newt->value = malloc(sizeof(char) * (strlen(s) + 1))`於**list_ele_t * newt**結構內取得記憶體空間後判定有無取得==結構內==記憶體空間
* 使用`strncpy(newh->value, s, strlen(s) + 1)`複製==strlen(s) + 1==長度的字串(含'\0')至`newt->value`的記憶體空間中
1. 當新增的元素為`queue_t`中第一個元素時`q->head`指向`newt`
2. 若非第一個元素將`q->tail->next`指向`newt`
3. 上述兩者執行完後將`q->tail`指向`newt`，更新`q->tail`指標
```cpp=
bool q_insert_tail(queue_t *q, char *s)
{
/* Remember: It should operate in O(1) time */
if (!q)
return false;
list_ele_t *newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
newt->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newt->value) {
free(newt);
return false;
}
strncpy(newt->value, s, strlen(s) + 1);
newt->next = NULL;
if (q->tail)
q->tail->next = newt;
else
q->head = newt;
q->tail = newt;
q->size++;
return true;
}
```
* **q_remove_head**
* 利用**list_ele_t * tmp**暫存`q->head`以便於將待刪除節點內的`value`存入`char *sp`
* 當傳入的buffer`sp`不為NULL時，利用snprintf比較`bufsize`與`sp`的大小以確保'\0'的存入，避免==Memory overflow==
* 釋放刪除節點記憶體空間，當刪除的節點為最後一個時將`q->tail`指向`NULL`
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q_size(q))
return false;
list_ele_t *tmp = q->head;
q->head = q->head->next;
if (sp)
snprintf(sp, bufsize, "%s", tmp->value);
free(tmp->value);
free(tmp);
q->size--;
if (!q_size(q))
q->tail = NULL;
return true;
}
```
* **q_size**
* 原本使用?做三元條件運算，但發現額外的else會導致超時，因此修改為單純if做判斷
```cpp=
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
* **q_reverse**
* 利用`cursor`遍歷`queue_t`，重定`q->head->next`指標方向
```cpp=
void q_reverse(queue_t *q)
{
if (!q || q->head == q->tail) // Empty 0 | 1
return;
list_ele_t *cursor = NULL;
q->tail = q->head;
while (q->head) {
list_ele_t *next = q->head->next;
q->head->next = cursor;
cursor = q->head;
q->head = next;
}
q->head = cursor;
}
```
* **q_sort**
* `q_sort`僅作為副函數接口使用
* 為確保每種情況皆符合$O(nlog(n))$的時間複雜度使用Top-down方法遞迴實現`merge_sort`
* 利用原生`strcmp`比較兩字串長度並將較小值放入遞迴中的**list_ele_t * head**進行merge
```cpp=
void q_sort(queue_t *q)
{
if (!q || q->head == q->tail) // Empty 0 | 1
return;
q->head = q->tail = merge_sort(q->head);
while (q->tail->next)
q->tail = q->tail->next;
}
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *l_head = head;
list_ele_t *l_tail = head->next;
/*split*/
while (l_tail && l_tail->next) {
l_head = l_head->next;
l_tail = l_tail->next->next;
}
l_tail = l_head->next;
l_head->next = NULL;
l_head = head;
/*sorting*/
list_ele_t *l_h = merge_sort(l_head);
list_ele_t *l_t = merge_sort(l_tail);
return merge(l_h, l_t);
}
list_ele_t *merge(list_ele_t *l_h, list_ele_t *l_t)
{
list_ele_t *head = NULL;
list_ele_t **cur = &head;
while (l_h && l_t) {
if (strcmp(l_h->value, l_t->value) > 0) {
*cur = l_t;
l_t = l_t->next;
} else {
*cur = l_h;
l_h = l_h->next;
}
cur = &((*cur)->next);
}
*cur = l_t ? l_t : l_h;
return head;
```
### qtest.c
* **fill_rand_string**
```cpp=
static void fill_rand_string(char *buf, size_t buf_size)
{
size_t len = 0;
if (buf_size < MIN_RANDSTR_LEN) // not gonna happen cuz buf_size is set to
// MAX_RADNSTR_LEN
buf_size = MAX_RANDSTR_LEN;
while (len < MIN_RANDSTR_LEN)
len = rand() % buf_size;
for (size_t n = 0; n < len; n++) {
buf[n] = charset[rand() % (sizeof charset - 1)];
}
buf[len] = '\0';
}
```
* **do_sort**
* 為了使`make test`正常運行 也修改了 traces 裡面的腳本 將`sort`改為`sort a`
* 另外將trace-16-perf內部`sort`與`reverse`整合為`sort d`
```cpp=
bool do_sort(int argc, char *argv[])
{
if (argc != 2) {
report(1, "%s usage:[a/d]", argv[0]);
return false;
}
if (!q)
report(3, "Warning: Calling sort on null queue");
error_check();
int cnt = q_size(q);
if (cnt < 2)
report(3, "Warning: Calling sort on single node");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_sort(q);
exception_cancel();
set_noallocate_mode(false);
if (!strcasecmp(argv[1], "d"))
q_reverse(q);
bool ok = true;
if (q) {
for (list_ele_t *e = q->head; e && --cnt; e = e->next) {
/* Ensure each element in ascending order */
/* DONE: add an option to specify sorting order */
if (!strcasecmp(argv[1], "a")) {
if (strcasecmp(e->value, e->next->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
} else {
if (strcasecmp(e->value, e->next->value) < 0) {
report(1, "ERROR: Not sorted in descending order");
ok = false;
break;
}
}
}
}
show_queue(3);
return ok && !error_check();
}
```
## 疑難排解
**q_size**
* 利用 ? 做三元條件運算
* `!q ? 0 : q->size;`相當於`if (!q) {return 0;} else {return q->size;}`
* 後來發現這種方法會導致當==無元素==的`queue_t`不斷調用`q_size`時無法符合$O(1)$的時間複雜度的需求
* 然後現在還不是很確定 究竟`if(!q || !q->head)`是省掉的時間 還是佔用的時間多
```cpp=
int q_size(queue_t *q)
{
return !q ? 0 : q->size;
}
```
**q_sort**
* 過程中的辛酸血淚待補
```cpp=
void q_sort(queue_t *q)
{
if (!q || q->head == q->tail) // empty 0 1
return;
q->head = q->tail = merge_sort(q->head);
while (q->tail->next)
q->tail = q->tail->next;
}
```
## Valgrind & Massif
* 使用以下指令測試Massif圖像化功能
```shell=
$ valgrind --tool=massif ./qtest -v 3 -f traces/trace-eg.cmd
$ ms_print massif.out.[PID]
```
* 沒視窗介面不能使用Massif-Visualizer 可憐阿
```
--------------------------------------------------------------------------------
Command: ./qtest -v 3 -f traces/trace-eg.cmd
Massif arguments: (none)
ms_print arguments: massif.out.12119
--------------------------------------------------------------------------------
KB
11.16^ #
| : ::@::@::#:
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| ::@::@::::::::@: @::#::
| :@:@::@::::::::@: @::#::@
0 +----------------------------------------------------------------------->ki
0 312.1
```
## 參考資料
* https://hackmd.io/@ZhuMon/lab0-c
* https://hackmd.io/@jwang0306/lab0-c
* https://npes87184.github.io/2015-09-12-linkedListSort/
* https://wirelessr.gitbooks.io/working-life/content/snprintf_miao_wu_qiong.html
## TODO
- [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
Sign in with Wallet
Connect another wallet