---
tags: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < `fennecJ` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 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.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 6
On-line CPU(s) list: 0-5
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
```
### Reviewed by `WeiHongWi`
* 針對每一個 function 並未詳盡自己的想法和開發紀錄
* 缺少利用 Valgrind 來評估程式的效能
## q_new()
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
配置記憶體後檢查是否有配置成功，若是則用 `INIT_LIST_HEAD` 將 `head` 初始化為 circular linked list 。
`INIT_LIST_HEAD` 的效果是將 head->next 和 head->prev 都指向 head 。
## q_free
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *cur, *backup;
list_for_each_entry_safe (cur, backup, l, list) {
free(cur->value);
free(cur);
}
free(l);
}
```
檢查 list_head l 是否為 NULL，之後用 list.h 中提供的 MACRO 走完並 free 整個 list ，因為途中會有 list node 被 free 掉，因此要用 safe 結尾的巨集，`list_for_each_entry_safe` 會對途中的 node 進行備份，避免 node 被 free 掉後存取發生問題。
## q_insert_{head,tail}
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *newEle = malloc(sizeof(element_t));
if (!newEle)
return false;
newEle->value = strdup(s);
if (!newEle->value) {
free(newEle);
return false;
}
list_add(&newEle->list, head);
return true;
}
```
比較需要注意的是如果 `strdup` 時無法順利配置記憶體，要記得釋放 `newEle`。
另外用 `list_add`/`list_add_tail` 將 newEle 中嵌入的 list node 加入 queue 。
## q_remove_head/tail
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_first_entry(head, element_t, list);
list_del(&ele->list);
if (!ele)
return NULL;
strncpy(sp, ele->value, bufsize);
return ele;
}
```
## q_delete_mid
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *front = head->next;
struct list_head *rear = head->prev;
while (front->next != rear && front != rear) {
front = front->next;
rear = rear->prev;
}
element_t *midEle = list_entry(rear, element_t, list);
list_del(&midEle->list);
free(midEle->value);
free(midEle);
return true;
}
```
## q_delete_dup
```c!
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head) || list_is_singular(head))
return false;
element_t *curEle, *preEle;
element_t *safEle;
bool dup = false;
preEle = NULL;
list_for_each_entry_safe (curEle, safEle, head, list) {
if (preEle && strcmp(curEle->value, preEle->value) == 0) {
list_del(&curEle->list);
free(curEle->value);
free(curEle);
dup = true;
} else {
if (dup) {
list_del(&preEle->list);
free(preEle->value);
free(preEle);
}
preEle = curEle;
dup = false;
}
}
if (dup) {
list_del(&preEle->list);
free(preEle->value);
free(preEle);
}
return true;
}
```
## q_swap
```c!
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node;
list_for_each (node, head) {
if (list_empty(node))
break;
list_move(node, node->next);
}
}
```
## q_reverse
```c!
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node, *saf;
list_for_each_safe (node, saf, head)
list_move(node, head);
}
```
## q_reverseK
```c!
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node, *tmp, *start;
node = head->next;
start = head; // begining of sublist to be reverse
while (node != head) {
tmp = node;
for (int i = 0; i < k; i++) {
// If remaining nodes cnt < k then leave without reversing the sub
// list
if (tmp == head)
return;
tmp = tmp->next;
}
for (int i = 0; i < k; i++) {
tmp = node->next;
list_move(node, start);
node = tmp;
}
start = node->prev;
}
}
```
## q_sort
```c!
void q_sort(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head list_less, list_greater;
char *sp = NULL;
element_t *item = NULL, *is = NULL;
element_t *pivot = q_remove_head(head, sp, 0);
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (strcmp(item->value, pivot->value) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
q_sort(&list_less);
q_sort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
## q_descend
```c!
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head) || list_is_singular(head))
return q_size(head);
q_reverse(head);
element_t *maxEle = list_first_entry(head, element_t, list);
element_t *curEle, *safEle;
int eleCnt = 0;
list_for_each_entry_safe(curEle, safEle, head, list){
if(strcmp(curEle->value, maxEle->value) < 0){
list_del(&curEle->list);
free(curEle->value);
free(curEle);
}
else {
maxEle = curEle;
eleCnt++;
}
}
q_reverse(head);
return eleCnt;
}
```
Sign in with Wallet
Connect another wallet