# 2022q1 Homework1 (lab0)
contributed by <`curlyw819` >
###### tags: `linux2022`
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping: 9
CPU MHz: 2635.475
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-7
```
## 作業要求
> [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
```cpp
struct list_head *q_new()
{
struct list_head *new_node =
(struct list_head *) malloc(sizeof(struct list_head));
if (new_node == NULL) {
return NULL;
}
INIT_LIST_HEAD(new_node);
return new_node;
}
```
配置一塊記憶體空間給head，再使用container of的`INIT_LIST_HEAD`
### q_free
```cpp
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *current = l->next;
while (current != l) {
struct list_head *temp_pointer = current;
element_t *temp_node = list_entry(temp_pointer, element_t, list);
current = current->next;
list_del(temp_pointer);
free(temp_node->value);
free(temp_node);
}
free(l);
}
```
使用 `list_entry` 來得到 list 的內部節點，其中 `list_entry` 等價 `container of`
### q_insert_head
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
size_t slen = strlen(s) + 1;
element_t *new_node;
if (!(new_node = (element_t *) malloc(sizeof(element_t))))
return false;
if (!(new_node->value = (char *) malloc(sizeof(char) * slen))) {
free(new_node);
return false;
}
memcpy(new_node->value, s, slen);
list_add(&new_node->list, head);
return true;
}
```
若配置記憶體不成功則 `return false` ，若成功則使用 `list head` 將結點插入至 `head` 後
### q_insert_tail
```cpp
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
size_t slen = strlen(s) + 1;
element_t *new_node;
if (!(new_node = (element_t *) malloc(sizeof(element_t))))
return false;
if (!(new_node->value = (char *) malloc(sizeof(char) * slen))) {
free(new_node);
return false;
}
memcpy(new_node->value, s, slen);
list_add_tail(&new_node->list, head);
return true;
}
```
### q_remove_head
```cpp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head || head->prev == head)
return NULL;
element_t *temp_node = list_first_entry(head, element_t, list);
if (sp)
memcpy(sp, temp_node->value, bufsize);
list_del(head->next);
return temp_node;
}
```
### q_remove_tail
```cpp
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head || head->prev == head)
return NULL;
element_t *temp_node = list_last_entry(head, element_t, list);
if (sp)
memcpy(sp, temp_node->value, bufsize);
list_del(head->prev);
return temp_node;
}
```
### q_size
```cpp
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_delete_mid
```cpp
bool q_delete_mid(struct list_head *head)
{
if (!head || head->next == head)
return false;
struct list_head *slow_pointer = head;
struct list_head *fast_pointer = head;
do {
fast_pointer = fast_pointer->next->next;
slow_pointer = slow_pointer->next;
} while (fast_pointer != head && fast_pointer->next != head);
element_t *temp = list_entry(slow_pointer, element_t, list);
list_del(slow_pointer);
free(temp->value);
free(temp);
return true;
}
```
### q_delete_dup
原本的寫法只有前半段，但因為功能不正確導致後面幾個數字輸出錯誤，所以將程式複製一遍從後面再跑回來來使結果正確
```cpp
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
int count = 0;
struct list_head *current_pointer = head->next;
struct list_head *ref_pointer = current_pointer;
struct list_head *temp_pointer;
struct list_head *temp_temp_pointer;
element_t *current_node = list_entry(current_pointer, element_t, list);
element_t *temp;
element_t *temp_node;
char *sp, *ref;
ref = current_node->value;
while (current_pointer != head) {
current_node = list_entry(current_pointer, element_t, list);
sp = current_node->value;
if (count == 0) {
ref = current_node->value;
ref_pointer = current_pointer;
if (current_pointer->prev != head) {
temp = list_entry(current_pointer->prev, element_t, list);
if (strcmp(temp->value, ref) == 0) {
printf("HI\n");
current_pointer = current_pointer->prev;
ref_pointer = current_pointer;
}
}
}
if (strcmp(sp, ref) == 0 && current_pointer->next != head) {
count++;
} else {
if (count > 1) {
temp_pointer = ref_pointer;
for (int i = 0; i < count; i++) {
temp_temp_pointer = temp_pointer;
temp_pointer = temp_pointer->next;
temp_node = list_entry(temp_temp_pointer, element_t, list);
list_del(temp_temp_pointer);
free(temp_node->value);
free(temp_node);
}
count = 0;
current_pointer = temp_pointer;
} else {
count = 0;
}
}
current_pointer = current_pointer->next;
}
count = 0;
current_pointer = head->prev;
ref_pointer = current_pointer;
current_node = list_entry(current_pointer, element_t, list);
ref = current_node->value;
while (current_pointer != head) {
current_node = list_entry(current_pointer, element_t, list);
sp = current_node->value;
if (count == 0) {
ref = current_node->value;
ref_pointer = current_pointer;
if (current_pointer->next != head) {
temp = list_entry(current_pointer->next, element_t, list);
if (strcmp(temp->value, ref) == 0) {
printf("HI\n");
current_pointer = current_pointer->next;
ref_pointer = current_pointer;
}
}
}
if (strcmp(sp, ref) == 0 && current_pointer->prev != head) {
count++;
} else {
if (count > 1) {
temp_pointer = ref_pointer;
for (int i = 0; i < count; i++) {
temp_temp_pointer = temp_pointer;
temp_pointer = temp_pointer->prev;
temp_node = list_entry(temp_temp_pointer, element_t, list);
list_del(temp_temp_pointer);
free(temp_node->value);
free(temp_node);
}
count = 0;
current_pointer = temp_pointer;
} else {
count = 0;
}
}
current_pointer = current_pointer->prev;
}
return true;
}
```
### q_swap
```cpp
void q_swap(struct list_head *head)
{
struct list_head *current = head;
int count = 0;
while (current->next != head && current->next->next != head) {
count++;
struct list_head *first = current->next;
struct list_head *second = current->next->next;
first->next = second->next;
current->next = second;
second->next = first;
first->next->prev = first;
first->prev = second;
second->prev = current;
current = current->next->next;
}
printf("%d", count);
}
```
### q_reverse
```cpp
void q_reverse(struct list_head *head)
{
if (head == NULL || head->next == head)
return;
struct list_head *temp;
struct list_head *current = head->next;
while (current != head) {
temp = current->next;
current->next = current->prev;
current->prev = temp;
current = temp;
}
temp = head->next;
head->next = head->prev;
head->prev = temp;
}
```
### q_sort
參考程式碼 : [Chao-Shun-Cheng](https://hackmd.io/@Chao-Shun-Cheng/linux2022-lab0#queuec-%E5%AF%A6%E4%BD%9C) 同學之 q_sort 程式碼
#### mergetwolist
```cpp
void mergetwolist(struct list_head *head1,
struct list_head *head2,
struct list_head *head)
{
if (!head || !head1 || !head2 || (list_empty(head1) && list_empty(head2)))
return;
if (list_empty(head1)) {
list_splice_tail_init(head2, head);
return;
}
if (list_empty(head2)) {
list_splice_tail_init(head1, head);
return;
}
struct list_head *temp = NULL;
struct list_head *p_1 = head1->next;
struct list_head *p_2 = head2->next;
while (p_1 != head1 && p_2 != head2) {
if (strcmp(list_entry(p_1, element_t, list)->value,
list_entry(p_2, element_t, list)->value) > 0) {
temp = p_2;
p_2 = p_2->next;
list_move_tail(temp, head);
} else {
temp = p_1;
p_1 = p_1->next;
list_move_tail(temp, head);
}
}
list_splice_tail_init(head1, head);
list_splice_tail_init(head2, head);
}
```
#### mergesort
```cpp
void mergesort(struct list_head *head, int size)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
LIST_HEAD(head1);
LIST_HEAD(head2);
int mid = size / 2, count = 0;
struct list_head *node = NULL, *safe = NULL;
list_for_each_safe (node, safe, head) {
count++;
if (count == mid) {
list_cut_position(&head1, head, node);
list_splice_tail_init(head, &head2);
break;
}
}
mergesort(&head1, mid);
mergesort(&head2, size - mid);
mergetwolist(&head1, &head2, head);
}
```
#### qsort
```cpp
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
mergesort(head, q_size(head));
}
```
Sign in with Wallet
Connect another wallet