# 2021q2 Homework1 (lab0)
contributed by < `Hooje` >
###### tags: `linux202
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 165
Model name: Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz
Stepping: 2
CPU MHz: 1200.073
CPU max MHz: 5000.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
```
## 作業要求
> [lab0](https://hackmd.io/@sysprog/2020-lab0)
詳細閱讀 [C Programming Lab ](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。
- q_new: 創一個空的 queue
- q_free: 釋放掉一個 queue
- q_insert_head: 在 head 插入一個 element (LIFO)
- q_insert_tail: 在 tail 插入一個 element (FIFO), O(1)
- q_remove_head: 把 head 的 element 移除
- q_size: return queue 的大小
- q_reverse: 將 queue 反轉，不配置或釋放任何的 element
- q_sort: 將 queue 由小排到大, sort by nature sort
## 開發過程
### q_new
用INIT_LIST_HEAD指向自己
```c=
queue_t *q_new()
{
element_t *e = malloc(sizeof(element_t));
if (!e)
return NULL;
INIT_LIST_HEAD(&e->list); // prev and next point to itself
return &e->list;
}
```
### q_free
利用container_of()找出他的element_t
```c
void q_free(queue_t *q)
{
// value is a pointer, so if you only free struct, you just clean the
// address, value still there use container_of to find the element_t
if (!l)
return;
struct list_head *p = l->next;
element_t *e = container_of(p, element_t,list);
// head is the "list" in the "element_t"
while (p != l) // last one's next is head
{
p = p->next;
q_release_element(e);
// free(e->value);
// free(e);
}
}
```
### q_insert_head
```c
bool q_insert_head(queue_t *q, char *s)
{
if (!head)
return false; // q is null
element_t *new_node = malloc(sizeof(element_t));
new_node->value =
malloc(sizeof(char) * (strlen(s) + 1)); // sizeof char = 1
memcpy(new_node->value, s, strlen(s) + 1); // include last '\0'
list_add(&new_node->list, head); // add element after head
// not sure, i try to change the head to new_node
// and i found that the head is queue head, head->next is the list head
/*
struct list_head **pp = &head;
*pp = new_node
*/
return true; // succeed
}
```
### q_insert_tail
```c
bool q_insert_tail(queue_t *q, char *s)
{
if (!head)
return false; // q is null
element_t *new_node = malloc(sizeof(element_t));
new_node->value =
malloc(sizeof(char) * (strlen(s) + 1)); // sizeof char = 1
memcpy(new_node->value, s, strlen(s) + 1); // include last '\0'
list_add_tail(&new_node->list, head); // add element after head
return true;
}
```
### q_remove_head
照著註解的方式去做，一開始 `q->size` 忘記扣，導致 size 錯誤
```c
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!head)
return NULL;
struct list_head *p = head->next;
element_t *e = container_of(p, element_t, list);
memcpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(p); // it mean remove, not delete
return e;
}
```
### q_remove_tail
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
struct list_head *p = head->prev;
element_t *e = container_of(p, element_t, list);
memcpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(p); // it mean remove, not delete
return e;
}
```
### q_size
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
```c
int q_size(queue_t *q)
{
sz = 0;
struct list_head *p;
list_for_each(p,head) //from head->next go to last one
sz += 1;
return sz;
}
```
### q_delete_mid
先算出中間的，然後remove, then free
```c
bool q_delete_mid(struct list_head *head)
{
int list_num;
list_num = q_size(head);
int middle_num = list_num / 2;
struct list_head *p = head;
int cnt = 0;
for(;cnt < middle_num;cnt+=1)
{
p = p->next;
}
list_del(p); //this function is remove, not delete
element_t *e = container_of(p, element_t,list);
q_release_element(e); //delete it
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
return true;
}
```
### q_delete_dup
利用雙層迴圈＋strcmp (回傳前面減後面，＝0 表示相同)
```c
bool q_delete_dup(struct list_head *head)
{
if(!head)
return false;
struct list_head *il = head->next;
struct list_head *jl = il->next;
for(;il!=head; il=il->next)
{
for(;jl!=head; jl=jl->next)
{
element_t *inode = container_of(il,element_t,list);
element_t *jnode = container_of(jl,element_t,list);
char *istring = inode->value;
char *jstring = jnode->value;
if(!strcmp(istring,jstring))
{
list_del(jl); //this function is remove, not delete
q_release_element(jnode); //delete it
}
}
}
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
return true;
}
```
### q_swap
```c
void q_swap(struct list_head *head)
{
struct list_head *p = head;
struct list_head *tmp, *first, *second;
while(p->next!=head && p->next->next!=head)
{
first = p->next;
second = p->next->next;
*tmp = *first;
*first = *second;
*second = *tmp;
p = second;
}
// https://leetcode.com/problems/swap-nodes-in-pairs/
}
```
### q_reverse
```c
void q_reverse(struct list_head *head)
{
struct list_head *p = head;
struct list_head *tmp;
do
{
tmp = p->next;
p->next = p->prev;
p->prev = tmp;
p = p->prev;
}while(p!=head)
}
```
Sign in with Wallet
Connect another wallet