# 2020q1 Homework1 (lab0)
contributed by < `shihtiy` >
## 目標
- 使用 linked list 來實作 queue 的 operation
- [github: lab0](https://github.com/shihtiy-tw/lab0-c)
- [H01: lab0](https://hackmd.io/@sysprog/linux2020-lab0)
- [2020q1 Homework1 (作業區)](https://hackmd.io/@sysprog/linux2020-homework1)
<s>
大綱
- Implementation
- 檢討與討論
</s>
:::danger
不需要特別去撰寫大綱，HackMD 可自動建立
:notes: jserv
:::
## 開發環境
- OS
```shell
$ lsb_release -a
LSB Version: core-9.20170808ubuntu1-noarch:security-9.20170808ubuntu1-noarch
Distributor ID: Ubuntu
Description: Ubuntu 18.04.2 LTS
Release: 18.04
Codename: bionic
```
- Compiler
```shell
$ gcc --version
gcc (Ubuntu 8.3.0-6ubuntu1~18.04.1) 8.3.0
```
## Programming Tasks
完成以下的 oprations:
- q_new: Create a new, empty queue.
- q_free: Free all storage used by a queue.
- q_insert head: Attempt to insert a new element at the head of the queue (LIFO discipline).
- q_insert tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
- q_remove head: Attempt to remove the element at the head of the queue.
- q_size: Compute the number of elements in the queue
- **q_sort: Sort elements of queue in ascending order**
> q_sort 目前還在卡關中... [name=Stanley Yuan]
# Implementation
## queue_t
因應題目要求 q_insert_tail 和 q_size 時間複雜度爲 O(1)，再 queue_t 中加上指向 queue 尾端的 pointer tail 和記錄大小的 size;
```c
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
## queue_new
這邊需要特別注意的是 malloc 執行失敗的 case，如果 malloc 執行失敗就會 return NULL[[1]](https://linux.die.net/man/3/malloc)。
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = q_size(q);
return q;
}
return NULL;
}
```
## q_free
使用一個 global variable tmp 來記錄要被 free 的 element。這個 tmp 還會被其他 function 使用。
```cpp=
list_ele_t *tmp;
void q_free(queue_t *q)
{
if (q) {
if (q->head) {
while (q->head != NULL) {
tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
}
free(q);
}
}
```
## q_insert_head
這邊我遇到兩個問題:
第一個是不可以使用 strcpy，用 snprintf 定義一個 strlcpy 來做限定長度的 string copy。
第二個是我對 string 和 pointer 的理解錯誤，見 [string size 檢討](https://hackmd.io/pgebahqjT4S07kkO3xK7WA#string-size-%E6%AA%A2%E8%A8%8E)。
```cpp
#ifndef strlcpy
#define strlcpy(dst, src, sz) snprintf((dst), (sz), "%s", (src))
#endif
bool q_insert_head(queue_t *q, char *s)
{
if (q) {
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
int s_size = strlen(s) + sizeof(char);
if (newh) {
newh->next = q->head;
q->head = newh;
newh->value = malloc(s_size);
if (newh->value) {
/*use strlcpy instead*/
strlcpy(newh->value, s, s_size);
q->size += 1;
if (q->size == 1)
q->tail = q->head;
return true;
}
}
}
return false;
}
```
## q_insert_tail
這裏使用在 queue_t 中定義的 tail 實作，要注意的是我之前一直沒有把 newl->value malloc 失敗的時候 free 而一直失敗。加上 free(newl->value); 後才成功。
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if (q) {
list_ele_t *newl;
newl = malloc(sizeof(list_ele_t));
int s_size = strlen(s) + sizeof(char);
if (newl) {
newl->next = NULL;
newl->value = malloc(s_size);
if (newl->value) {
if (q->tail) {
q->tail->next = newl;
}
q->tail = newl;
/*use strlcpy instead*/
strlcpy(newl->value, s, s_size);
q->size += 1;
if (q->size == 1)
q->head = q->tail;
return true;
}
free(newl->value);
}
free(newl);
}
return false;
}
```
## q_remove_head
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q && q->head) {
if (sp) {
/*using strlcpy instead*/
strlcpy(sp, q->head->value, bufsize);
}
tmp = q->head;
q->head = q->head->next;
q->size -= 1;
if (!(q->head))
q->tail = q->head;
free(tmp->value);
free(tmp);
return true;
}
return false;
}
```
## q_reverse
這裏用兩個 pointer headl 和 headr 來輔助 q->head 記錄上一個 element 的位址和下一個 element 的位址來做 reverse 的動作。
```cpp
void q_reverse(queue_t *q)
{
if (q && q->head && q->head != q->tail) {
list_ele_t *headl = NULL, *headr = q->head->next;
q->tail = q->head;
while (headr) {
q->head->next = headl;
headl = q->head;
q->head = headr;
headr = q->head->next;
}
q->head->next = headl;
}
}
```
## q_size
```cpp
int q_size(queue_t *q)
{
if (q && q->head)
return q->size;
return 0;
}
```
## q_sort
這裏本來寫不出來，是在答對 quiz 1 後移植過來。但遇到 performance 的問題。目前還沒解決...
```cpp
list_ele_t *merge_sort(list_ele_t *start)
{
if (!start || !start->next)
return start;
list_ele_t *left = start;
list_ele_t *right = left->next;
left->next = NULL;
left = merge_sort(left);
right = merge_sort(right);
for (list_ele_t *merge = NULL; left || right;) {
if (!right || (left && (strcasecmp(left->value, right->value) < 0))) {
if (!merge) {
start = merge = left;
} else {
merge->next = left;
merge = merge->next;
}
left = left->next;
} else {
if (!merge) {
start = merge = right;
} else {
merge->next = right;
merge = merge->next;
}
right = right->next;
}
}
return start;
}
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(queue_t *q)
{
if (q && q->head && q->head != q->tail) {
q->head = merge_sort(q->head);
q->tail = q->head;
while (q->tail->next != NULL) {
q->tail = q->tail->next;
}
}
}
```
# 檢討與討論
## string size 檢討
我用 snprintf 定義一個 strlcpy 來做限定長度的 string copy。但我原本的適用 sizeof(s) 來算我的 string 長度，因爲用 sizeof 會把結尾的 NULL 字元也算進去。所以原本 s_size 的程式碼是：
```cpp
int s_size = sizeof(s);
```
但一直出錯，這時我也沒有細究，我就把他改成：
```cpp
int s_size = sizeof(s) * sizeof(char *);
```
就過了，我就不追究了。但後來和別人討論時發現我這個寫法不夠精確。也發現我的理解有錯誤。我用以下程式碼測試：
```cpp
char greeting[] = "HHelloHelloHelloello";
char *test_string;
test_string = malloc(sizeof(char) * (strlen(greeting) + sizeof(char)));
strcpy(test_string, greeting);
printf("greeting strlen %ld\n", strlen(greeting));
printf("greeting sizeof %ld\n", sizeof(greeting));
printf("test_string strlen %ld\n", strlen(test_string));
printf("test_string sizeof %ld\n", sizeof(test_string));
// output
// greeting strlen 20
// greeting sizeof 21
// test_string strlen 20
// test_string sizeof 8
```
sizeof 確實回傳 greeting 包含 NULL 字元的字串長度，而把 greeting copy 到 test_string 後 sizeof 卻只有回傳 8 bytes。上網查時看到資料解釋兩者的差異，當宣告 string 的時候會是在記憶體中 stack 的位置，而 malloc 會在 heap 的位值。用 GDB 測試也顯示不同的結果：
```shell
(gdb) whatis greeting
type = char [21]
(gdb) whatis test_string
type = char *
```
但如果把 greeting 和 test_string 都傳入一個 function 的時候，這時候傳入的都是指向 greeting 和 test_string 的 pointer，用 sizeof 時兩者都會回傳記憶體位址的大小，而不會是 string 包含 NULL 字元的長度。但我目前還沒有找到一個滿意的實證的方式。
我在這個 [commit](https://github.com/shihtiy-tw/lab0-c/commit/b7104682fa38f61de7e5d15b048e43ebf5069e03) 有做了想對應的修正也有照老師說的補上 commit message。
---
https://www.youtube.com/watch?v=scLFY2CRtFo 1:10:00
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf 6.5.3.2 Address and indirection operators
## q_sort
還在努力中... 按照 qtest 的測資會有 segment fault 的錯誤。
## 和去年比...
這是第二次挑戰老師的課程，和去年比較掙扎的寫作業的情況比有明顯的不同，遇到問題時會先朝 offical document 或是規格書找答案，也會試着用 GDB 來先自己 debug。
Sign in with Wallet
Connect another wallet