# 2018q3 Homework2 (lab0)
contributed by < `danielian1121` >
>* 請同步更新原專案最新的 commit
>* commit message
> * [Singly linked list](https://github.com/danielian1121/lab0-c/commit/c42bb96d390ebdb4dd6832a3817d356a892144f7) 請遵循 commit message 的規範撰寫
> * [Finish, add comments and make code cleaner](https://github.com/danielian1121/lab0-c/commit/e1d6c4039f4ec5594a9ce891bd0ebe0cfd608324) 不需要寫出 Finish, 與您的修改無關
> * [Change strdup to malloc](https://github.com/danielian1121/lab0-c/commit/121ac7488be36c5276b36bbbd32c7dd6c4e71146) 增加說明為什麼要抽換為 malloc，且此有一個 Makefile 的修改與此 commit 描述無關
>
>[name=課程助教][color=red]
>
## 實驗環境
```bash
sukamo:~$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.1 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.1 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic
```
## struct 架構
```clike
typedef struct ELE {
char *value;
struct ELE *next;
struct ELE *prev;
} list_ele_t;
typedef struct {
list_ele_t *head;
list_ele_t *tail;
unsigned int count;
} queue_t;
```
:::info
`You may add other fields to the structure list_ele, although you need not do so.`
題目貌似沒有規定不能用 doubly linked list，但看到其他同學的共筆幾乎都沒有改到 `list_ele_t` 的架構，之後會開一個 branch 來實做 singly linked list
:::
## funtion 實做
#### q_new
```clike
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL) {
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->count = 0;
return q;
}
```
#### q_free
```clike
void q_free(queue_t *q)
{
if (q == NULL)
return;
list_ele_t *temp = q->head;
list_ele_t *readyFree;
while (temp) {
readyFree = temp;
temp = temp->next;
//free(readyFree->value);
free(readyFree);
}
free(q);
}
```
* 合理來說，註解掉的那一行應該要存在，否則每個 element 的 value 會沒有被 free 掉，但是加上去後 make test 又會跑不過，真的是很奇怪......
* 有看到同學的共筆也有提起這件事情([來源](https://hackmd.io/s/HkWLADMK7))
* harness.h 有下列這段程式
```clike
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
```
* 因此我們程式中所用的 malloc and free 是使用測試程式中的某個函式，而我在 copy value 的時候使用了 strdup，此函式會在裡面呼叫 malloc ，因而繞過測試程式，因此在準備 free 的時候，也會誤判為此區段沒有事先 malloc 而發生錯誤
:::info
目前已改成用 malloc 搭配 strcpy 的方式來 copy value
:::
#### q_insert_head
```clike
bool q_insert_head(queue_t *q, char *s)
{
/** If q is NULL, return false. */
if (q == NULL)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
/** If malloc failed, return false. */
if (newh == NULL)
return false;
char *s_copy = malloc(strlen(s) + 1);
/** If malloc failed, return false. */
if (s_copy == NULL) {
free(newh);
return false;
}
strcpy(s_copy, s);
/** Set the new element. */
newh->value = s_copy;
newh->next = q->head;
newh->prev = NULL;
q->head = newh;
/** If the new element is the first, set q->tail as q->head. */
if (q->head->next == NULL)
q->tail = q->head;
else
q->head->next->prev = q->head;
/** Add count. */
q->count++;
return true;
}
```
#### q_insert_tail
* 作業有要求，此函式的時間複雜度必須為 $O(1)$ ，因此 queue_t 中才有一個指向 tail 的 pointer 存在
* 與 insert_head 大同小異，只是指標指向的位置要特別注意
```clike
bool q_insert_tail(queue_t *q, char *s)
{
/** If q is NULL, return false. */
if (q == NULL)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
/** If malloc failed, return false. */
if (newh == NULL)
return false;
char *s_copy = malloc(strlen(s) + 1);
/** If malloc failed, return false. */
if (s_copy == NULL) {
free(newh);
return false;
}
strcpy(s_copy, s);
/** Set the new element. */
newh->value = s_copy;
newh->prev = q->tail;
newh->next = NULL;
q->tail = newh;
/** If the new element is the first, set q->head as q->tail. */
if (q->tail->prev == NULL)
q->head = q->tail;
else
q->tail->prev->next = q->tail;
/** Add count. */
q->count++;
return true;
}
```
#### q_remove_head
* 在刪除之際，也必須把即將刪除的 element 的 value 保存 bufsize 大小存到 sp 中
* 無法直接用 `strcpy(q->head->value, sp)` ，因為有可能會造成 Buffer Overflow
* 因此必須先知道 q->head->value 的長度，再依照結果來作不同的事情
```clike
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/** If q is NULL or q->head is NULL, return false. */
if (q == NULL || q->head == NULL)
return false;
/** If len > bufsize, use strncpy to copy.
* Otherwise, use strcpy.
*/
if (sp != NULL) {
size_t len = strlen(q->head->value);
if (len > bufsize - 1) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
strcpy(sp, q->head->value);
}
}
/** Check the element is the last or not. */
if (q->head == q->tail)
q->tail = NULL;
/** Delete the head element. */
list_ele_t *temp;
temp = q->head;
q->head = q->head->next;
if (q->head != NULL)
q->head->prev = NULL;
/** Free the head element. */
free(temp->value);
free(temp);
/** Subtract count. */
q->count--;
return true;
}
```
#### q_size
* 題目要求時間複雜度必須為 $O(1)$，因此也在 queue_t 中加入變數 count 來計算 size
```clike
int q_size(queue_t *q)
{
return q ? q->count : 0;
}
```
#### q_reverse
* 在 doubly linked list 中，此函式實做比較簡單，只須交換 queue 中的 next and prev ，再交換 queue_t 的 head and tail 即可
```clike
void q_reverse(queue_t *q)
{
if (q == NULL || q->head == NULL)
return;
list_ele_t *temp = q->head;
list_ele_t *swap;
/** Swap next and prev in every element from head to tail. */
while (temp) {
swap = temp->next;
temp->next = temp->prev;
temp->prev = swap;
temp = swap;
}
/* swap head and tail */
swap = q->head;
q->head = q->tail;
q->tail = swap;
}
```
## Singly linked list
:::info
已有新 branch "singly"
:::
#### q_reverse
```graphviz
digraph G {
rankdir=LR;
node [shape=record];
subgraph cluster_4 {
a4[label=A];
b4[label=B];
c4[label=C];
d4[label=D];
head4->d4;a4->NULL4;
d4->c4;
b4->a4;c4->b4;
}
prev4[label=prev,shape=plaintext];
now4[label=now,shape=plaintext];
next4[label=next,shape=plaintext];
head4[label=head,shape=plaintext];
NULL4[label=NULL,shape=plaintext];
prev4->b4;
now4->c4;
next4->d4;
subgraph cluster_3 {
a3[label=A];
b3[label=B];
c3[label=C];
d3[label=D];
head3->a3->b3;d3->NULL3;
b3->a3;c3->b3;
}
prev3[label=prev,shape=plaintext];
now3[label=now,shape=plaintext];
next3[label=next,shape=plaintext];
head3[label=head,shape=plaintext];
NULL3[label=NULL,shape=plaintext];
prev3->b3;
now3->c3;
next3->d3;
subgraph cluster_2 {
a2[label=A];
b2[label=B];
c2[label=C];
d2[label=D];
head2->a2->b2;c2->d2->NULL2;
b2->a2;
}
prev2[label=prev,shape=plaintext];
now2[label=now,shape=plaintext];
next2[label=next,shape=plaintext];
head2[label=head,shape=plaintext];
NULL2[label=NULL,shape=plaintext];
prev2->b2;
now2->c2;
next2->d2;
subgraph cluster_1 {
a1[label=A];
b1[label=B];
c1[label=C];
d1[label=D];
head1->a1->b1;c1->d1->NULL1;
b1->a1;
}
prev1[label=prev,shape=plaintext];
now1[label=now,shape=plaintext];
next1[label=next,shape=plaintext];
head1[label=head,shape=plaintext];
NULL1[label=NULL,shape=plaintext];
prev1->a1;
now1->b1;
next1->c1;
subgraph cluster_0 {
a0[label=A];
b0[label=B];
c0[label=C];
d0[label=D];
head0->a0->b0->c0->d0->NULL0;
}
prev0[label=prev,shape=plaintext];
now0[label=now,shape=plaintext];
next0[label=next,shape=plaintext];
head0[label=head,shape=plaintext];
NULL0[label=NULL,shape=plaintext];
prev0->a0;
now0->b0;
next0->c0;
}
```
Sign in with Wallet
Connect another wallet